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.

Benchmarking Scenarios

1. Random Configurations:

We used a benchmark setup similar to the Bullet collision Library, in which a set of AABBs are uniformly distributed in space and moving randomly. As we changed the number of AABBs from 16K to 960K, we measured the performance of our algorithm and that of the three broad-phase CD algorithms provided in Bullet, which are BoxPruning, ArraySaP and an AABB dynamic tree. The first two algorithms are based on SaP and the last one using a dynamic bounding volume hierarchy. All of these algorithms run on CPU. The size of the AABBs also varies from 0.5% to 8% to the size of the bounding box of the workspace. As shown Figure below, our algorithm outperforms the fastest of the Bullet implementations (i.e. the AABB dynamic tree) by a factor of 71 times.

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 Rigid-Body Dynamics:

We approximated a rigid model with a set of uniform spheres, and used a penalty-based approach running in parallel on GPUs.  This avoids narrow-phase Collision Detection. We simulated 16K torus models approximated by six spheres of varying size moving under gravity. We were able to simulate the approximate rigid-body dynamics entirely running on GPUs in 18 ms, including collision detection.

RELATED LINKS

Bullet collision Library:

    http://bulletphysics.org

Real-Time 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