gProximity: Hierarchical GPU-based Operations for Collision and Distance Queries

Christian Lauterbach, Qi Mo, and Dinesh Manocha
University of North Carolina at Chapel Hill


We present fast parallel algorithms to construct, update and traverse bounding volume hierarchies on many-core GPUs. Our approach is general and based on a new work distribution scheme that can easily adapt to dynamically changing work loads that arise in interactive applications. This enables us to exploit all cores to perform hierarchical operations using tight-fitting OBBs with little overhead as compared to widely-used AABBs. We use our fast hierarchy refitting for interactive ray tracing and collision detection on complex and deforming models such as the problem of self-collision. In practice, we observe more than an order of magnitude improvement in the performance of continuous collision queries as compared to prior GPU-based algorithms, competitive or better performance compared to multi-core CPU methods, and much higher speed for hierarchy refitting with applications to ray tracing.


gProximity: Hierarchical GPU-based operations for collision and distance queries (PDF)
Proc. of Eurographics 2010


Source Code

Related Links

GAMMA Research Group
Interactive Ray Tracing Research at GAMMA



Models courtesy of Disney Animation.