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

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

doi:10.1145/1866158.1866180

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

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

Department of Computer Science & Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

47 Scopus citations

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.

Original language	English
Title of host publication	Proceedings of ACM SIGGRAPH Asia 2010, SIGGRAPH Asia 2010
Volume	29
Edition	6
DOIs	https://doi.org/10.1145/1866158.1866180
State	Published - 2010
Event	ACM SIGGRAPH Asia 2010, SIGGRAPH Asia 2010 - Seoul, Korea, Republic of Duration: 15 Dec 2010 → 18 Dec 2010

Conference

Conference	ACM SIGGRAPH Asia 2010, SIGGRAPH Asia 2010
Country/Territory	Korea, Republic of
City	Seoul
Period	15/12/10 → 18/12/10

Keywords

collision detection
dynamics simulation
graphics hardware

Access to Document

10.1145/1866158.1866180

Cite this

@inproceedings{7445918398414653994a98a06d6dcb04,

title = "Real-time collision culling of a million bodies on graphics processing units",

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.",

keywords = "collision detection, dynamics simulation, graphics hardware",

author = "Fuchang Liu and Takahiro Harada and Youngeun Lee and Kim, {Young J.}",

year = "2010",

doi = "10.1145/1866158.1866180",

language = "English",

isbn = "9781450304399",

volume = "29",

booktitle = "Proceedings of ACM SIGGRAPH Asia 2010, SIGGRAPH Asia 2010",

edition = "6",

note = "ACM SIGGRAPH Asia 2010, SIGGRAPH Asia 2010 ; Conference date: 15-12-2010 Through 18-12-2010",

}

TY - GEN

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

AU - Liu, Fuchang

AU - Harada, Takahiro

AU - Lee, Youngeun

AU - Kim, Young J.

PY - 2010

Y1 - 2010

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

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

KW - collision detection

KW - dynamics simulation

KW - graphics hardware

UR - http://www.scopus.com/inward/record.url?scp=78650856937&partnerID=8YFLogxK

U2 - 10.1145/1866158.1866180

DO - 10.1145/1866158.1866180

M3 - Conference contribution

AN - SCOPUS:78650856937

SN - 9781450304399

VL - 29

BT - Proceedings of ACM SIGGRAPH Asia 2010, SIGGRAPH Asia 2010

T2 - ACM SIGGRAPH Asia 2010, SIGGRAPH Asia 2010

Y2 - 15 December 2010 through 18 December 2010

ER -

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

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this