Rapid k-d Tree Construction for Sparse Volume Data

Abstract

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. We pick a serial state of the art implementation that is based on summed-volume tables and propose a parallel version of the construction algorithm for multi-core CPUs. Our parallel k-d tree construction algorithm can be used to rapidly perform full hierarchy rebuilds for moderately sized to large volume data sets. We reformulate the original, highly serial construction algorithm by replacing the summed-volume table (SVT) that is used to perform fast occupancy queries with a list of partial summed-volume tables. This gives rise to parallelism at several stages of the algorithm. We show how to achieve high scalability with a carefully crafted parallelization scheme. As a side effect, our construction algorithm also relaxes the tremendous memory overhead imposed by full SVTs. For our scalability study, we have integrated the parallel k-d tree implementation into a ray casting volume rendering pipeline. We present comparisons for various sparse 3-D volumetric data sets where k-d trees are first built interactively and then later used to skip over empty space.