“Real-time Collision Culling of a Million Bodies on Graphics Processing Units” by Liu, Harada, Lee and Kim – ACM SIGGRAPH HISTORY ARCHIVES

“Real-time Collision Culling of a Million Bodies on Graphics Processing Units” by Liu, Harada, Lee and Kim

  • ©

Conference:


Type(s):


Title:

    Real-time Collision Culling of a Million Bodies on Graphics Processing Units

Session/Category Title:   From Rigid to Soft

Presenter(s)/Author(s):


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.

References:


    [1] Andrecut, M. 2009. Parallel GPU implementation of iterative PCA algorithms. Journal of Computational Biology 16, 11.
    [2] Baraff, D. 1992. Dynamic Simulation of Non-Penetrating Rigid Bodies. PhD thesis, Cornell University.
    [3] Brown, S., 2008. The scalable city project. http://scalablecity.net.
    [4] 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.
    [5] Coming, D. S., and Staadt, O. G. 2006. Kinetic sweep and prune for multi-body continuous motion. Computers and Graphics 30, 439–449.
    [6] 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.
    [7] Edelsbrunner, H., and Maurer, H. A. 1981. On the intersection of orthogonal objects. Inf. Process. Lett. 13, 177–181.
    [8] Ericson, C. 2005. Real-Time Collision Detection. Morgan Kaufmann.
    [9] Grand, S. L. 2008. GPU Gems 3. Addison-Wesley, ch. Broad-Phrase Collision Detection with CUDA, 697–721.
    [10] Harada, T., Koshizuka, S., and Kawaguchi, Y. 2007. Smoothed particle hydrodynamics on GPUs. In Computer Graphics International.
    [11] Harada, T. 2007. GPU Gems3. Addison-Wesley Pearson Education, ch. Real-time Rigid Body Simulation on GPUs.
    [12] Jolliffe, I. T. 2002. Principal Component Analysis. Springer.
    [13] Lauterbach, C., Garland, M., Sengupta, S., Luebke, D., and Manocha, D. 2009. Fast BVH construction on GPUs. In Eurographics.
    [14] Lauterbach, C., Mo, Q., and Manocha, D. 2010. gProximity: Hierarchical GPU-based operations for collision and distance queries. In Eurographics.
    [15] Lin, M., and Manocha, D. 2003. Collision and proximity queries. In Handbook of Discrete and Computational Geometry.
    [16] Lin, M. C. 1993. Efficient Collision Detection for Animation and Robotics. PhD thesis, University of California, Berkeley, CA.
    [17] Mazhar, H., Heyn, T., Tasora, A., and Negrut, D. 2009. Collision detection using spatial subdivision. In Multibody Dynamics.
    [18] Mirtich, B. V. 1996. Impulse-based Dynamic Simulation of Rigid Body Systems. PhD thesis, University of California, Berkeley.
    [19] NVIDIA. 2010. NVIDIA CUDA Best Practice Guide.
    [20] 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.
    [21] Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. 1992. Numerical Recipes in C. Cambridge University Press.
    [22] Samet, H. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann.
    [23] 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.
    [24] Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Graphics Hardware, 97–106.
    [25] 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.
    [26] Tang, M., Manocha, D., and Tong, R. 2010. MCCD: Multicore collision detection between deformable models. Graphical Models 72, 2, 7–23.
    [27] Terdiman, P. 2007. Sweep-and-prune. http://www.codercorner.com/SAP.pdf.
    [28] 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.
    [29] Wald, I. 2007. On fast construction of SAH-based bounding volume hierarchies. In IEEE/EG Symposium on Interactive Ray Tracing, 33–40.
    [30] 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.
    [31] Zerodin, 2010. Zerodin games. http://www.zerodingames.com.
    [32] Zhou, K., Hou, Q., Wang, R., and Gui, B. 2008. Real-time KD-tree construction on graphics hardware. ACM Transactions on Graphics.

Keyword(s):


ACM Digital Library Publication:


Overview Page:


Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org