Fast
BVH Construction on GPUs
Christian Lauterbach1, Michael Garland2, Shubhabrata Sengupta3, David Luebke2, and Dinesh Manocha1
1University of North Carolina at Chapel Hill
2NVIDIA Research
3University of California Davis
 |
| Flamenco benchmark: Screenshots from dynamic scene with 49K triangles. Our novel algorithm can build the optimized BVH on a NVIDIA G80 GPU in 23ms per frame, allowing full real-time ray tracing of fully dynamic scenes on the GPU. |
Abstract
We present two novel parallel algorithms for rapidly constructing
bounding volume hierarchies on manycore GPUs. The first uses a
linear ordering derived from spatial Morton codes to build hierarchies
extremely quickly and with high parallel scalability. The second is a
top-down approach that uses the surface area heuristic (SAH) to build
hierarchies optimized for fast ray tracing. Both algorithms are combined
into a hybrid algorithm that removes existing bottlenecks in the algorithm
for GPU construction performance and scalability leading to significantly
decreased build time. The resulting hierarchies are close in to optimized
SAH hierarchies, but the construction process is substantially faster,
leading to a significant net benefit when both construction and traversal
cost are accounted for. Our preliminary results show that current GPU
architectures can compete with CPU implementations of hierarchy
construction running on multicore systems. In practice, we can construct
hierarchies of models with up to several million triangles and use them
for fast ray tracing or other applications.
Paper
Fast BVH Construction on GPUs (PDF)
to appear in Proc. Eurographics 2009
Video (AVI DivX, 8 MB)
Related Links
GAMMA Research Group
NVIDIA
Ray Tracing Research at GAMMA
Acknowledgements
NVIDIA
RDECOM
NSF
ARO
DARPA
Models courtesy of Disney Animation, the Stanford Scanning Repository and Marko Dabrovic.