TL;DR
This paper presents two novel parallel algorithms for rapidly constructing Bounding Volume Hierarchies (BVHs) on GPUs. The first algorithm optimizes BVHs for ray tracing using the surface area heuristic (SAH) with a hybrid approach to overcome GPU construction bottlenecks. The second algorithm, using spatial Morton codes, builds hierarchies extremely quickly, offering a trade-off between construction speed and hierarchy quality.
What Problem Does This Paper Address?
Ray tracing, a powerful technique for realistic image generation, relies heavily on acceleration structures like Bounding Volume Hierarchies (BVHs) to efficiently determine which objects a ray intersects. Traditionally, BVHs have been constructed serially on CPUs. However, with the increasing parallelism of modern GPUs and the demand for real-time rendering of dynamic scenes (e.g., with deformable models or changing geometry), there's a critical need for fast, parallel BVH construction methods that can leverage GPU architectures. Prior attempts to parallelize BVH construction on multi-core CPUs have faced limitations, particularly with memory bandwidth and the inherent serial nature of early construction steps. This paper aims to bridge this gap by developing GPU-native algorithms that can construct high-quality BVHs at interactive rates.
Methods
The paper introduces two primary parallel algorithms for BVH construction on GPUs:
- SAH-Optimized BVH Construction (GPU SAH): This algorithm adapts the well-known Surface Area Heuristic (SAH) for building BVHs. The key innovation is a hybrid approach that addresses bottlenecks in traditional top-down SAH construction. It uses a breadth-first processing strategy with work queues managed on the GPU, allowing multiple splits to occur in parallel. A novel geometry sorting approach is also employed to rapidly build object hierarchies. This method aims to produce hierarchies comparable in quality to CPU-based SAH constructions but with significantly reduced build times.
- Linear Bounding Volume Hierarchy (LBVH) Construction: This algorithm takes a different approach by first linearizing primitives using spatial Morton codes (a type of space-filling curve). This linearization creates a sequence of primitives ordered in a spatially coherent manner. The BVH is then constructed by recursively splitting this linear sequence. This method is significantly faster than SAH-based construction, though it results in hierarchies that are slightly less optimized for traversal.
The authors also propose a Hybrid GPU Construction Algorithm that combines the speed of LBVH with the quality of SAH. It uses LBVH to build a shallow hierarchy and then switches to the GPU SAH algorithm for the remaining splits, aiming to achieve a balance between construction speed and traversal performance.
Datasets
The paper evaluates its algorithms on several benchmark scenes:
- Flamenco (49K triangles)
- Sibenik (82K triangles)
- Fairy (174K triangles)
- Bunny/Dragon animation (252K triangles)
- Conference room (284K triangles)
- Soda Hall (2M triangles)
These scenes are described as architectural, CAD, and scanned models, chosen to allow comparison with other published approaches and to cover various model characteristics. No new benchmarks were introduced; rather, existing models were used to demonstrate the performance of the proposed algorithms.
Key Insights and Ideas
- GPU Parallelism for BVH Construction is Viable: Contrary to the perception that GPUs are unsuited for hierarchy construction due to memory latency, this paper demonstrates that by exposing substantial fine-grained parallelism, GPUs can be highly effective.
- Work Queues and Breadth-First Processing: The use of work queues and a breadth-first traversal strategy is crucial for parallelizing the split operations across GPU cores, overcoming the serial nature of traditional depth-first construction.
- Morton Codes for Fast Linearization: Spatial Morton codes provide an efficient way to linearize primitives, enabling a much faster construction process compared to SAH, albeit with a slight compromise in hierarchy quality.
- Hybrid Approach Balances Speed and Quality: Combining LBVH for initial rapid construction with SAH for finer optimization offers a compelling trade-off, achieving near-SAH quality with significantly improved build times.
- Small Split Optimization: Optimizing the handling of small splits (those with few primitives) using a dedicated kernel and local memory significantly boosts performance, especially at the lower levels of the hierarchy.
Key Results
- Competitive Performance: The GPU SAH algorithm is competitive with, and at times faster than, previously published results for 8-core CPU systems.
- LBVH Speedup: The LBVH algorithm is 2-15 times faster than SAH construction.
- LBVH Traversal Penalty: Traversal of LBVH hierarchies is only 2-15% slower than SAH-based hierarchies.
- Hybrid Performance: The hybrid approach achieves roughly half the construction speed of LBVH while retaining essentially all the quality of pure SAH-based construction.
- Interactive Rates: The algorithms can construct BVHs for models with up to several million triangles at interactive rates, enabling real-time ray tracing of dynamic scenes. For instance, the Flamenco benchmark (49K triangles) can be processed in 23ms per frame.
- Memory Efficiency: The construction algorithm uses a low memory footprint, approximately 113 bytes per triangle, allowing for the construction of hierarchies for multi-million triangle models on current GPUs.
Limitations and Future Work
Limitations:
- Static Scheduling: Current GPU architectures have relatively static scheduling, and the lack of true shared work queues in main memory prevents the implementation of a fully synchronized global work queue, leading to some overhead.
- Main Memory Access: Main memory accesses can be slow if threads do not access data in a totally linear fashion. Caching or improved reordering could mitigate this.
Future Work:
- Integration with Rendering Pipelines: Integrating the construction algorithm into full rendering pipelines, potentially combining hybrid rasterization and ray tracing.
- Visibility Culling: Utilizing BVHs for visibility culling in rasterization.
- GPU-Generated Primitives: Investigating hierarchy construction directly on geometric primitives created on the GPU, such as using tessellation techniques.
- Other Bounding Volumes: Exploring the use of other bounding volumes like Oriented Bounding Boxes (OBBs) or k-DOPs, which GPUs are well-suited for due to their computational power.
- New Applications: Investigating BVHs for applications like continuous collision detection, response computation, and multi-agent navigation.
Summary updated