Abstract
This paper discusses a parallel collision detection algorithm. Implemented using software executed on ubiquitous Graphics Processing Unit (GPU) cards, the algorithm demonstrates two orders of magnitude speedup over a state-of-the art sequential implementation when handling multimillion 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 surface geometries as large collections of spheres when dealing with collision detection between 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 (SPH), where the number of contact events ranges from millions to billions.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Heyn, T.: Simulation of tracked vehicles on granular terrain leveraging GPU computing. M.S. Thesis, Department of Mechanical Engineering, University of Wisconsin–Madison. http://sbel.wisc.edu/documents/TobyHeynThesis_final.pdf (2009)
Tasora, A., Negrut, D., Anitescu, M.: Large-scale parallel multi-body dynamics with frictional contact on the graphical processing unit. Proc. Inst. Mech. Eng., Proc. Part K, J. Multi-Body Dyn. 222(4), 315–326 (2008)
Tasora, A., Negrut, D., Anitescu, M.: GPU-based parallel computing for the simulation of complex multibody systems with unilateral and bilateral constraints: An overview. In: Blajer, W., Arczewski, K., Fraczek, J., Wojtyra, M. (eds.) Multibody Dynamics: Computational Methods and Applications, pp. 45–55. Springer, Berlin (2010)
Negrut, D., Tasora, A., Mazhar, H., Heyn, T., Hahn, P.: Leveraging parallel computing in multibody dynamics. Multibody system dynamics. Under review (2011). This paper was submitted in December with manuscript number MUBO-10-79
Gonthier, Y., McPhee, J., Lange, C., Piedbuf, J.-C.: A regularized contact model with asymmetric damping and dwell-time dependent friction. Multibody Syst. Dyn. 11, 209–233 (2004). 10.1023/B:MUBO.0000029392.21648.bc
Förg, M., Pfeiffer, F., Ulbrich, H.: Simulation of unilateral constrained systems with many bodies. Multibody Syst. Dyn. 14, 137–154 (2005). 10.1007/s11044-005-0725-x
Najafabadi, S.M., Kövecses, J., Angeles, J.: Impacts in multibody systems: modeling and experiments. Multibody Syst. Dyn. 20, 163–176 (2008). 10.1007/s11044-008-9117-3
Choi, J., Ryu, H., Kim, C., Choi, J.: An efficient and robust contact algorithm for a compliant contact force model between bodies of complex geometry. Multibody Syst. Dyn. 23, 99–120 (2010). 10.1007/s11044-009-9173-3
Fleissner, F., Gaugele, T., Eberhard, P.: Applications of the discrete element method in mechanical engineering. Multibody Syst. Dyn. 18, 81–94 (2007). 10.1007/s11044-007-9066-2
Baraff, D.: Dynamic simulation of non-penetrating rigid bodies. Ph.D. Thesis, Cornell University (1992)
Baraff, D.: An introduction to physically based modeling: rigid body simulation IIóNonpenetration constraints. In: An Introduction to Physically Based Modelling, SIGGRAPH’97 Course Notes (1997)
Cohen, J.D., Lin, M.C., Manocha, D., Ponamgi, M.: I-COLLIDE: An interactive and exact collision detection system for large-scale environments. In: Proceedings of the 1995 Symposium on Interactive 3D Graphics, p. 189. ACM, New York (1995)
Govindaraju, N.K., Redon, S., Lin, M.C., Manocha, D.: CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. In: Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware, pp. 25–32. Eurographics Association, Geneve (2003)
Govindaraju, N.K., Lin, M.C., Manocha, D.: Fast and reliable collision culling using graphics hardware. In: IEEE Transactions on Visualization and Computer Graphics, pp. 143–154 (2006)
Govindaraju, N.K., Lin, M.C., Manocha, D.: Quick-CULLIDE: fast inter-and intra-object collision culling using graphics hardware. In: ACM SIGGRAPH 2005 Courses, p. 218. ACM, New York (2005)
Harada, T.: Real-time rigid body simulation on GPUs. GPU Gems 3, 611–632 (2007)
Harada, T., Koshizuka, S., Kawaguchi, Y.: Sliced data structure for particle-based simulations on gpus. In: Proceedings of the 5th International Conference on Computer Graphics and Interactive Techniques in Australia and Southeast Asia, pp. 55–62. ACM, New York (2007)
NVIDIA. CUDA Programming Guide. Available online at http://developer.download.nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_CUDA_Programming_Guide_2.3.pdf (2009)
Le Grand, S.: Broad-phase collision detection with cuda. GPU Gems 3, 697–721 (2007)
Satish, N., Harris, M., Garland, M.: Designing efficient sorting algorithms for manycore GPUs. In: Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium, pp. 1–10. IEEE Press, New York (2009)
NVIDIA Corporation. Tesla c1060 datasheet. Available online at http://www.nvidia.com/docs/IO/43395/NV_DS_Tesla_C1060_US_Jun08_FINAL_LowRes.pdf (2008)
Harris, M., Sengupta, S., Owens, J.D.: Parallel prefix sum (scan) with CUDA. GPU Gems 3(39), 851–876 (2007)
Hoberock, J., Bell, N.: Thrust: a parallel template library. Available online at http://code.google.com/p/thrust/ (2009)
NVIDIA Corporation. Compute unified device architecture occupancy calculator (2009)
NVIDIA Corporation. Compute unified device architecture software development kit (2009)
Pazouki, A., Mazhar, H., Negrut, D.: Parallel ellipsoid collision detection with application in contact dynamics-DETC2010-29073. In: Fukuda, S., Michopoulos, J.G. (eds.) Proceedings to the 30th Computers and Information in Engineering Conference. ASME International Design Engineering Technical Conferences (IDETC) and Computers and Information in Engineering Conference (CIE) (2010)
BULLET: Physics simulation forum. Bullet physics library. Available online at http://www.bulletphysics.com/Bullet/wordpress/ (2010)
Tasora, A.: Chrono::Engine, an open source physics–based dynamics simulation engine. Available online at www.deltaknowledge.com/chronoengine (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mazhar, H., Heyn, T. & Negrut, D. A scalable parallel method for large collision detection problems. Multibody Syst Dyn 26, 37–55 (2011). https://doi.org/10.1007/s11044-011-9246-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11044-011-9246-y