research-article

Real-time collision culling of a million bodies on graphics processing units

Authors:

Takahiro Harada,

Young J. KimAuthors Info & Claims

SIGGRAPH ASIA '10: ACM SIGGRAPH Asia 2010 papers

Article No.: 154, Pages 1 - 8

https://doi.org/10.1145/1866158.1866180

Published: 15 December 2010 Publication History

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.

Supplementary Material

Supplemental material. (154-158-0072-auxiliary.zip)

Download
47.60 MB

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.

Digital Library

[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.

Digital Library

[5]

Coming, D. S., and Staadt, O. G. 2006. Kinetic sweep and prune for multi-body continuous motion. Computers and Graphics 30, 439--449.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[24]

Sengupta, S., Harris, M., Zhang, Y., and Owens, J. D. 2007. Scan primitives for GPU computing. In Graphics Hardware, 97--106.

Digital Library

[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.

Digital Library

[26]

Tang, M., Manocha, D., and Tong, R. 2010. MCCD: Multicore collision detection between deformable models. Graphical Models 72, 2, 7--23.

Digital Library

[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.

Digital Library

[29]

Wald, I. 2007. On fast construction of SAH-based bounding volume hierarchies. In IEEE/EG Symposium on Interactive Ray Tracing, 33--40.

Digital Library

[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.

Digital Library

Cited By

Weller RDebowski NZachmann G(2017)kDetComputer Graphics Forum10.1111/cgf.1311336:2(131-141)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1111/cgf.13113
Du PZhao JCao WWang Y(2017)DCCD: Distributed N-Body Rigid Continuous Collision Detection for Large-Scale Virtual EnvironmentsArabian Journal for Science and Engineering10.1007/s13369-016-2411-042:8(3141-3147)Online publication date: 28-Jan-2017
https://doi.org/10.1007/s13369-016-2411-0
Zhang ZXin YLiu BLi WLee KNg CStoyanov DCheung RKwok K(2016)FPGA-Based High-Performance Collision Detection: An Enabling Technique for Image-Guided Robotic SurgeryFrontiers in Robotics and AI10.3389/frobt.2016.000513Online publication date: 31-Aug-2016
https://doi.org/10.3389/frobt.2016.00051
Show More Cited By

Index Terms

Real-time collision culling of a million bodies on graphics processing units
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Real-time collision culling of a million bodies on graphics processing units

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 ...
Real-time multi-perspective rendering on graphics hardware
SIGGRAPH '06: ACM SIGGRAPH 2006 Sketches

Multi-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

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH ASIA '10: ACM SIGGRAPH Asia 2010 papers

December 2010

510 pages

ISBN:9781450304399

DOI:10.1145/1882262

Conference Chair:
George Drettakis
REVES/Inria Sophia-Antipolis

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

In-Cooperation

SIGCHI: ACM Special Interest Group on Computer-Human Interaction

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 December 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

SA '10

Sponsor:

SIGGRAPH

SA '10: SIGGRAPH ASIA 2010

December 15 - 18, 2010

Seoul, South Korea

Acceptance Rates

SIGGRAPH ASIA '10 Paper Acceptance Rate 49 of 274 submissions, 18%;

Overall Acceptance Rate 178 of 869 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
875
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Weller RDebowski NZachmann G(2017)kDetComputer Graphics Forum10.1111/cgf.1311336:2(131-141)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1111/cgf.13113
Du PZhao JCao WWang Y(2017)DCCD: Distributed N-Body Rigid Continuous Collision Detection for Large-Scale Virtual EnvironmentsArabian Journal for Science and Engineering10.1007/s13369-016-2411-042:8(3141-3147)Online publication date: 28-Jan-2017
https://doi.org/10.1007/s13369-016-2411-0
Zhang ZXin YLiu BLi WLee KNg CStoyanov DCheung RKwok K(2016)FPGA-Based High-Performance Collision Detection: An Enabling Technique for Image-Guided Robotic SurgeryFrontiers in Robotics and AI10.3389/frobt.2016.000513Online publication date: 31-Aug-2016
https://doi.org/10.3389/frobt.2016.00051
Serpa YRodrigues M(2014)Parallelizing Broad Phase Collision Detection for Animation in GamesProceedings of the 2014 Brazilian Symposium on Computer Games and Digital Entertainment10.1109/SBGAMES.2014.29(80-88)Online publication date: 12-Nov-2014
https://dl.acm.org/doi/10.1109/SBGAMES.2014.29
Lo SLee CChung IChung Y(2013)Optimizing Pairwise Box Intersection Checking on GPUs for Large-Scale SimulationsACM Transactions on Modeling and Computer Simulation10.1145/2499913.249991823:3(1-22)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1145/2499913.2499918
Glondu LSchvartzman SMarchal MDumont GOtaduy MBoulic RKomura T(2012)Efficient collision detection for brittle fractureProceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/2422356.2422397(285-294)Online publication date: 29-Jul-2012
https://dl.acm.org/doi/10.5555/2422356.2422397
Glondu LSchvartzman SMarchal MDumont GOtaduy M(2012)Efficient collision detection for brittle fractureProceedings of the 11th ACM SIGGRAPH / Eurographics conference on Computer Animation10.5555/2421731.2421772(285-294)Online publication date: 29-Jul-2012
https://dl.acm.org/doi/10.5555/2421731.2421772
Morris DAnderson EPeters C(2012)A modular framework for deformation and fracture using GPU shaders2012 18th International Conference on Virtual Systems and Multimedia10.1109/VSMM.2012.6365934(267-274)Online publication date: Sep-2012
https://doi.org/10.1109/VSMM.2012.6365934
Pan JChitta SManocha D(2012)FCL: A general purpose library for collision and proximity queries2012 IEEE International Conference on Robotics and Automation10.1109/ICRA.2012.6225337(3859-3866)Online publication date: May-2012
https://doi.org/10.1109/ICRA.2012.6225337

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents