A Scalable parallel method for large scale collision detection problems

This paper discusses a scalable collision detection algorithm. The algorithm, implemented using software executed on ubiquitous Graphics Processing Unit (GPU) cards, demonstrates two orders of magnitude speedup over state-of-the art sequential implementations when handling multi-million object collision detection tasks. GPUs are composed of many (on the order of hundreds) scalar processors that can simultaneously execute an operation; this strength is leveraged in the proposed algorithm, which combines the use of multiple CPU cores with multiple GPUs. The software implementation of the algorithm can be used to detect collisions between five million objects in less than two seconds and was used to detect 1.4 billion contact events in less than 40 seconds. A spherical padding approach is used to represent the surface geometries as large collections of spheres when dealing with collision detection of bodies with complex geometries. The proposed methodology is expected to be relevant in computational mechanics with applications in granular flow dynamics and smoothed particle hydrodynamics, where the number of contact events ranges from millions to billions. copyright (c) 2010 by JSME.