Simpler and Faster HLBVH with Work Queues

"Simpler and Faster HLBVH with Work Queues"
Kirill Garanzha, Jacopo Pantaleoni, David McAllister, in High Performance Graphics 2011, August 2011
Research Area: Ray Tracing
Author(s): Kirill Garanzha, Jacopo Pantaleoni, David McAllister
Date: August 2011

A recently developed algorithm called Hierachical Linear Bounding Volume Hierarchies (HLBVH) has demonstrated the feasibility of reconstructing the spatial index needed for ray tracing in real-time, even in the presence of millions of fully dynamic triangles. In this work we present a simpler and faster variant of HLBVH, where all the complex bookkeeping of pre x sums, compaction and partial breadth- rst tree traversal needed for spatial partitioning has been replaced with an elegant pipeline built on top of ecient work queues and binary search. The new algorithm is both faster and more memory ecient, removing the need for temporary storage of geometry data for intermediate computations. Finally, the same pipeline has been extended to parallelize the construction of the top-level SAH optimized tree on the GPU, eliminating round-trips to the CPU, accelerating the overall construction speed by a factor of 5 to 10x.