A Binary Stack Tandem Traversal and an Ancestor Counter Data Structure for GPU friendly Bounding Volume Hierarchies.

The performance bottleneck of physics based animation is often the collision detection. It is well-known by prac-titioners that the collision detection may consume 80-90 % of the simulation time. In this work we will introduce a novel approach for collision detection using bounding volume hierarchies. Instead of the traditional stack, a binary stack is used, containing information about which of the two bounding volume hierarchies has been descended. Our new algorithm and data structure can be used on GPUs and on hardware platforms, where memory is sparse. As proof-of-concept we demonstrate a GPU implementation for a multibody dynamics simulation, showing an overall speedup of a factor of 4-5