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

While k-d trees are known to be effective for spatial indexing of sparse 3-d volume data, full reconstruction, e.g. due to changes to the alpha transfer function during rendering, is usually a costly operation with this hierarchical data structure. In a recent publication we showed how to port a clever state of the art k-d tree construction algorithm to a multi-core CPU architecture and by means of thorough optimization we were able to obtain interactive reconstruction rates for moderately sized to large data sets. The construction scheme is based on maintaining partial summed-volume tables that fit in the L1 cache of the multi-core CPU and that allow for fast occupancy queries. In this work we propose a GPU implementation of the parallel k-d tree construction algorithm and compare it with the original multi-core CPU implementation. We conduct a thorough comparative study that outlines performance and scalability of our implementation.

Automated summary

The paper discusses how to port an advanced k-d tree construction algorithm to a multi-core CPU architecture, achieving interactive reconstruction rates for moderately sized to large data sets through optimization. It also proposes a GPU implementation of the parallel k-d tree construction algorithm and compares it with the original multi-core CPU implementation, conducting a thorough study on performance and scalability.