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

Fuchang Liu, Youngeun Lee, Young J. Kim, Takahiro Harada

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.

Original languageEnglish
Pages (from-to)1-8
Number of pages8
JournalACM Transactions on Graphics
Issue number6
StatePublished - 2010


  • Collision detection
  • Dynamics simulation
  • Graphics hardware


Dive into the research topics of 'Real-time Collision Culling of a Million Bodies on Graphics Processing Units'. Together they form a unique fingerprint.

Cite this