Authors Jesper Damkjær and Kenny Erleben ( 2009 )

Abstract The performance bottleneck of physics based animation, is often the collision detection. It is well-known by practitioners that the collision detection may consume more than half of the simulation time. In this work we will introduce a novel approach for collision detection using bounding volume hierarchies. Our approach makes it possible to perform non-convex object versus non-convex object collision on the GPU, using tandem traversals of bounding volume hierarchies. Prior work only supports single traversals on GPUs. We introduce a blocked hierarchy data structure, using imaginary nodes and a simultaneous descend in the tandem traversal. The data structure design and traversal are highly specialized for exploiting the parallel threads in the NVIDIA GPUs. As proof-of-concept we demonstrate a GPU implementation for a multibody dynamics simulation, showing an approximate speedup factor of up to 8 compared to a CPU implementation.

Online Version EuroGraphics
Paper download
Slides download