Memory-Scalable GPU Spatial Hierarchy Construction

Area of Science:

• Computer Graphics
• Parallel Computing
• Geometric Modeling

Background:

• Breadth-first search (BFS) construction order for GPU spatial hierarchies offers high performance but suffers from excessive memory usage, limiting interactive applications with complex models.
• High memory consumption of BFS hinders the construction of spatial hierarchies for models exceeding a few million triangles on GPUs.

Purpose of the Study:

• To introduce a partial breadth-first search (PBFS) construction order to mitigate memory consumption while maintaining high performance in GPU-based spatial hierarchy construction.
• To adapt PBFS for kd-tree and bounding volume hierarchy (BVH) construction algorithms, enhancing scalability and handling of complex and large-scale models.

Main Methods:

• Applied the PBFS order to kd-tree construction, balancing parallelism and memory usage, and implemented memory allocation strategies to reduce fragmentation.
• Developed an out-of-core BVH construction algorithm using PBFS, transferring nodes to CPU memory iteratively to manage GPU memory constraints for very large scenes.

Main Results:

• The PBFS-based kd-tree algorithm efficiently controls peak memory, scales with GPU memory, and constructs large kd-trees at interactive rates on low-memory GPUs (1 GB).
• The PBFS-based out-of-core BVH algorithm successfully constructs hierarchies for scenes with up to 20 million triangles, significantly exceeding the capacity of previous GPU algorithms.
• Achieved an order of magnitude greater scalability for kd-tree construction compared to existing algorithms within a given GPU memory bound.

Conclusions:

• PBFS is an effective strategy for optimizing memory usage and performance in GPU-accelerated spatial hierarchy construction, enabling interactive rates for complex models.
• The proposed PBFS-based algorithms significantly enhance the scalability of constructing kd-trees and out-of-core BVHs, allowing for the processing of much larger datasets than previously possible on GPUs.