Parallel Locally-Ordered Clustering for Bounding Volume Hierarchy Construction.

Area of Science:

• Computer Graphics
• Parallel Algorithms
• Computational Geometry

Background:

• Bounding Volume Hierarchies (BVHs) are crucial for efficient ray tracing.
• Existing BVH construction methods can be computationally expensive, especially for complex scenes.
• Massively parallel approaches are needed to leverage modern hardware for faster BVH generation.

Purpose of the Study:

• To introduce a novel, massively parallel algorithm for constructing Bounding Volume Hierarchies (BVHs).
• To improve the efficiency of BVH construction and subsequent ray tracing performance.
• To leverage locally-ordered agglomerative clustering and Morton curve ordering for parallel neighbor finding.

Main Methods:

• A novel massively parallel construction algorithm for BVHs.
• Utilizes locally-ordered agglomerative clustering for iterative bottom-up merging of cluster pairs.
• Employs Morton curve ordering to efficiently identify neighboring clusters in parallel.
• Implementation in CUDA for GPU acceleration.

Main Results:

• Achieves up to a twofold reduction in BVH build times for complex scenes.
• Provides up to 17 percent faster ray tracing times compared to state-of-the-art methods.
• Demonstrates efficient parallel neighbor finding through Morton curve ordering.

Conclusions:

• The proposed algorithm offers significant performance improvements in both BVH construction and ray tracing.
• The combination of agglomerative clustering and Morton curve ordering is effective for parallel BVH generation.
• This method presents a viable and efficient solution for real-time rendering and complex scene processing on GPUs.