A fast contact detection algorithm insensitive to object sizes

Presents a new contact detection algorithm based on double-ended spatial so rting (DESS) that is insensitive to variations in object size. It was devel oped to address the problems that arise when objects with non-spherical geo metry and non-uniform sizes are simulated using discrete element techniques . The algorithms applicable to general spatial reasoning problems. While te chniques based on spatial hashing (sometimes called bining methods) perform well for objects of similar size, they degrade significantly when the obje cts vary in size. The DESS algorithm overcomes this problem by using a spat ial sorting technique applied to both ends of the object's projection along each orthogonal axis. Discrete element test simulations comparing DESS and spatial hashing (NBS) are detailed. The results demonstrate that when obje ct sizes vary significantly (size ratios greater than 8:1), DESS out perfor ms NBS up to around 100,000 objects. It is noted, however, that the superio r scaling properties of NBS will always outperform DESS for some large numb ers of objects.