Realtime
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 sweepandprune (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 realtime simulation of very large numbers
of particles and rigidbody dynamics.




Benchmarking Scenarios
1. Random
Configurations:
2. Particle Simulation: We benchmarked on large
sets of particles of varying sizes. We did this by modifying an open particle
simulation demo, originally from NVIDIA (Particles sample code in CUDA SDK).
As shown in Figure below, we introduced 100K and 0.3M spheres of the size varying
from 0.3% to 20% of the dimension of the workspace and simulated their
motions under gravity. We then measure the performance of our algorithm and
that of a uniform subdivision algorithm that also runs GPUs. While CD takes
up most of the computation, it is hard to decouple the collision times from
the simulation times using NVIDIA's uniform subdivision method. However, for
100K and 0.3M particles, our algorithm takes 56 ms and 252 ms on
average for both collision detection and particle simulation while uniform
subdivision 4452 ms and 53464 ms; thus our algorithm outperforms
uniform subdivision by a factor of 212 times.
3. Approximate
RigidBody Dynamics:
RELATED LINKS
Bullet
collision Library: RealTime Rigid Body Simulation on GPUs(GPU Gem3): http://http.developer.nvidia.com/GPUGems3/gpugems3_ch29.html
Particles: http://developer.download.nvidia.com/compute/cuda/sdk/website/C/src/particles/doc/particles.pdf
http://developer.download.nvidia.com/compute/cuda/sdk/Projects/particles.zip


