Generalized Spatial Binning of Bodies of Different Sizes
Eric Perkins, John R. Williams · 2002
This paper presents an algorithm that determines the spatial relationships between bodies and can be used for contact detection. The process of contact detection can be divided into two phases, called neighbor search and contact resolution. Neighbor search identifies and creates lists of object "near" to the target object, usually using some approximate geometry for the objects. The geometric resolution then compares the detailed geometric representation of each object with the target object to resolve contact. Based on the details of the contact, forces or some other constraint enforcement technique is used to penalize and remove any overlap that has occurred due to the discrete time stepping algorithm. In simulations the spatial algorithm usually becomes the computational bottleneck as the number of objects increases. It is therefore critical to develop algorithms that scale well, preferably linearly, with respect to the number of bodies and polygons. In addition the algorithms should be general enough to be applicable across a wide spectrum of problems.