GPU accelerated tandem traversal of blocked bounding volume hierarchy collision detection for multibody dynamics

TY - GEN

T1 - GPU accelerated tandem traversal of blocked bounding volume hierarchy collision detection for multibody dynamics

AU - Damkjær, Jesper

AU - Erleben, Kenny

N1 - Conference code: 6

PY - 2009

Y1 - 2009

N2 - The performance bottleneck of physics based animation is often the collision detection. It is well known by practitionersthat the collision detection may consume more than half of the simulation time. In this work, we willintroduce a novel approach for collision detection using bounding volume hierarchies. Our approach makes itpossible to perform non-convex object versus non-convex object collision on the GPU, using tandem traversalsof bounding volume hierarchies. Prior work only supports single traversals on GPUs. We introduce a blockedhierarchy data structure, using imaginary nodes and a simultaneous descend in the tandem traversal. The datastructure 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 anapproximate speedup factor of up to 8 compared to a CPU implementation.

AB - The performance bottleneck of physics based animation is often the collision detection. It is well known by practitionersthat the collision detection may consume more than half of the simulation time. In this work, we willintroduce a novel approach for collision detection using bounding volume hierarchies. Our approach makes itpossible to perform non-convex object versus non-convex object collision on the GPU, using tandem traversalsof bounding volume hierarchies. Prior work only supports single traversals on GPUs. We introduce a blockedhierarchy data structure, using imaginary nodes and a simultaneous descend in the tandem traversal. The datastructure 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 anapproximate speedup factor of up to 8 compared to a CPU implementation.

U2 - 10.2312/PE/vriphys/vriphys09/115-124

DO - 10.2312/PE/vriphys/vriphys09/115-124

M3 - Article in proceedings

SN - 978-3-905673-73-9

SP - 115

EP - 124

BT - VRIPHYS 09

T2 - Virtual Reality Interaction and Physical Simulation (VRIPHYS)

Y2 - 5 November 2009 through 6 November 2009

ER -