Fuchang Liu
Young J. Kim
Abstract
We cull collisions between very large numbers of moving bodies using graphics processing units (GPUs). To perform massively parallel sweep-and-prune (SaP), we mitigate the great density of intervals along the axis of sweep by using principal component analysis to choose the best sweep direction, together with spatial subdivisions to further reduce the number of false positive overlaps. Our algorithm implemented entirely on GPUs using the CUDA framework can handle a million moving objects at interactive rates. As application of our algorithm, we demonstrate the real-time simulation of very large numbers of particles and rigid-body dynamics.
Supplemental Material
Available for Download
- Andrecut, M. 2009. Parallel GPU implementation of iterative PCA algorithms. Journal of Computational Biology 16, 11.Google Scholar
Cross Ref
- Baraff, D. 1992. Dynamic Simulation of Non-Penetrating Rigid Bodies. PhD thesis, Cornell University. Google ScholarDigital Library
- Brown, S., 2008. The scalable city project. http://scalablecity.net.Google Scholar
- Cohen, J., Lin, M., Manocha, D., and Ponamgi, M. 1995. I-COLLIDE: An interactive and exact collision detection system for large-scale environments. In Proc. of ACM Interactive 3D Graphics Conference, 189--196. Google ScholarDigital Library
- Coming, D. S., and Staadt, O. G. 2006. Kinetic sweep and prune for multi-body continuous motion. Computers and Graphics 30, 439--449. Google ScholarDigital Library
- Coming, D. S., and Staadt, O. G. 2008. Velocity-aligned discrete oriented polytopes for dynamic collision detection. IEEE Transactions on Visualization and Computer Graphics 14, 1. Google ScholarDigital Library
- Edelsbrunner, H., and Maurer, H. A. 1981. On the intersection of orthogonal objects. Inf. Process. Lett. 13, 177--181.Google ScholarCross Ref
- Ericson, C. 2005. Real-Time Collision Detection. Morgan Kaufmann.Google Scholar
- Grand, S. L. 2008. GPU Gems 3. Addison-Wesley, ch. Broad-Phrase Collision Detection with CUDA, 697--721.Google Scholar
- Harada, T., Koshizuka, S., and Kawaguchi, Y. 2007. Smoothed particle hydrodynamics on GPUs. In Computer Graphics International.Google Scholar
- Harada, T. 2007. GPU Gems3. Addison-Wesley Pearson Education, ch. Real-time Rigid Body Simulation on GPUs.Google Scholar
- Jolliffe, I. T. 2002. Principal Component Analysis. Springer.Google Scholar
- Lauterbach, C., Garland, M., Sengupta, S., Luebke, D., and Manocha, D. 2009. Fast BVH construction on GPUs. In Eurographics.Google Scholar
- Lauterbach, C., Mo, Q., and Manocha, D. 2010. gProximity: Hierarchical GPU-based operations for collision and distance queries. In Eurographics.Google Scholar
- Lin, M., and Manocha, D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.Google Scholar
- Lin, M. C. 1993. Efficient Collision Detection for Animation and Robotics. PhD thesis, University of California, Berkeley, CA. Google ScholarDigital Library
- Mazhar, H., Heyn, T., Tasora, A., and Negrut, D. 2009. Collision detection using spatial subdivision. In Multibody Dynamics.Google Scholar
- Mirtich, B. V. 1996. Impulse-based Dynamic Simulation of Rigid Body Systems. PhD thesis, University of California, Berkeley. Google ScholarDigital Library
- NVIDIA. 2010. NVIDIA CUDA Best Practice Guide.Google Scholar
- Ponamgi, M., Manocha, D., and Lin, M. 1995. Incremental algorithms for collision detection between general solid models. In Proc. ACM Symposium on Solid Modeling and Applications, 293--304. Google ScholarDigital Library
- Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 1992. Numerical Recipes in C. Cambridge University Press.Google Scholar
- Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. Google ScholarDigital Library
- Seiler, L., Carmean, D., Sprangle, E., Forsyth, T., Abrash, M., Dubey, P., Junkins, S., Lake, A., Sugerman, J., Cavin, R., Espasa, R., Grochowski, E., Juan, T., and Hanrahan, P. 2008. Larrabee: a many-core x86 architecture for visual computing. ACM Trans. Graph. 27, 3, 1--15. Google ScholarDigital Library
- Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Graphics Hardware, 97--106. Google ScholarDigital Library
- Tang, M., Curtis, S., Yoon, S.-E., and Manocha, D. 2009. ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling. IEEE Transactions on Visualization and Computer Graphics 15, 544--557. Google ScholarDigital Library
- Tang, M., Manocha, D., and Tong, R. 2010. MCCD: Multicore collision detection between deformable models. Graphical Models 72, 2, 7--23. Google ScholarDigital Library
- Terdiman, P. 2007. Sweep-and-prune. http://www.codercorner.com/SAP.pdf.Google Scholar
- Tracy, D. J., Buss, S. R., and Woods, B. M. 2009. Efficient large-scale sweep and prune methods with AABB insertion and removal. In Proc. IEEE Virtual Reality, 191--198. Google ScholarDigital Library
- Wald, I. 2007. On fast construction of SAH-based bounding volume hierarchies. In IEEE/EG Symposium on Interactive Ray Tracing, 33--40. Google ScholarDigital Library
- Woulfe, M., Dingliana, J., and Manzke, M. 2007. Hardware accelerated broad phase collision detection for realtime simulations. In Workshop in Virtual Reality Interactions and Physical Simulation.Google Scholar
- Zerodin, 2010. Zerodin games. http://www.zerodingames.com.Google Scholar
- Zhou, K., Hou, Q., Wang, R., and Gui, B. 2008. Real-time KD-tree construction on graphics hardware. ACM Transactions on Graphics. Google ScholarDigital Library
Index Terms
- Real-time collision culling of a million bodies on graphics processing units
Recommendations
Real-time collision culling of a million bodies on graphics processing units
SIGGRAPH ASIA '10: ACM SIGGRAPH Asia 2010 papersWe cull collisions between very large numbers of moving bodies using graphics processing units (GPUs). To perform massively parallel sweep-and-prune (SaP), we mitigate the great density of intervals along the axis of sweep by using principal component ...
Real-time multi-perspective rendering on graphics hardware
SIGGRAPH '06: ACM SIGGRAPH 2006 SketchesMulti-perspective rendering has a variety of applications; examples include lens refraction, curved mirror reflection, caustics, as well depiction and visualization. However, multi-perspective rendering is not yet practical on polygonal graphics ...
Fast continuous collision detection among deformable models using graphics processors
We present an interactive algorithm to perform continuous collision detection between general deformable models using graphics processors (GPUs). We model the motion of each object in the environment as a continuous path and check for collisions along ...
Comments