Highlights

The authors thank Sandia National Laboratory for their financial support, which has made this work possible. This work is the result of a collaboration between Sandia National Laboratory, Albuquerque, NM, and the Massachusetts Institute of Technology, Cambridge, MA. Sandia National Laboratory is operated by Sandia Corporation, a Lockheed Martin Company, for the US Department of Energy.

Keywords Particle physics, Algorithmic languages

Abstract A new spatial reasoning algorithm that can be used in multi-body contact detection is presented. The algorithm achieves the partitioning of N bodies of arbitrary shape and size into N lists in order O(N) operations, where each list consists of bodies spatially near to the target object. The algorithm has been tested for objects of arbitrary shape and size, in two and three dimensions. However, we believe that it can be extended to dimensions of four and higher. The algorithm (CGRID) is a binning algorithm that extends traditional binning algorithms so that the arbitrary sizes and shapes can be handled efficiently. The algorithm has applications in discrete element, finite element, molecular dynamics, meshless methods, and lattice-Boltzmann codes and also in domains such as path planning, target acquisition and general clustering problems.

Introduction

This...