Binned k-d Tree Construction for Sparse Volume Data on Multi-Core and GPU Systems.

Area of Science:

• Computer Graphics
• Scientific Visualization
• Parallel Computing

Background:

• K-d trees are effective for spatial indexing of sparse 3D volume data.
• Reconstruction with k-d trees can be computationally expensive, especially during rendering modifications.
• Previous work optimized k-d tree construction for multi-core CPUs, achieving interactive rates.

Purpose of the Study:

• To propose and evaluate a GPU implementation of a parallel k-d tree construction algorithm.
• To compare the performance and scalability of the GPU implementation against a multi-core CPU version.

Main Methods:

• Developed a GPU-based parallel k-d tree construction algorithm.
• Utilized partial summed-volume tables for efficient occupancy queries, adapted for GPU architecture.
• Conducted a comparative performance and scalability study between CPU and GPU implementations.

Main Results:

• The GPU implementation demonstrates competitive performance for k-d tree construction.
• Scalability analysis highlights the benefits of the GPU approach for large datasets.
• Interactive reconstruction rates are achievable with the proposed GPU method.

Conclusions:

• The GPU implementation offers a viable and potentially faster alternative for parallel k-d tree construction.
• This work advances efficient spatial indexing and reconstruction techniques for large-scale 3D volume data.