k-D trees are an acceleration data structure that can enhance ray tracing. They let you organize primitives in a scene to allow efficient execution of intersection operations between rays and the primitives.

Highest quality k-D trees use greedy cost optimization based on a surface area heuristc (SAH). While the high quality makes possible very fast ray tracing times, k-D tree construction time remains prohibitively expensive. This cost is unreasonable for rendering dynamic scenes for visual computing applications on emerging multicore and many-core systems.

Consequently, computer scientists have focused on parallel k-D tree. In their paper entitled Parallel SAH k-D Tree Construction Byn Choi, Rakesh Komuravelli, Victor Lu, Hyojin Sung, Robert L. Bocchino, Sarita V. Adve, and John C. Hart present ParKD, a package of parallel algorithms for building precise SAH-optimized k-D trees, with different tradeoffs between the total work done and parallel scalability. The algorithms achieve up to 8x speedup on 32 cores, without degrading tree quality and rendering time, yielding the best reported speedups so far for precise-SAH k-D tree construction.

One parallel algorithm ParKD offers is a depth-first task parallelization of sequential k-D tree construction that nests geometry-level parallelism within the node-level parallelism for these upper level nodes. The other algorithm builds the upper nodes of the hierarchy breadth-first, one level at a time, storing in each triangle the node(s) it belongs to at that level. This reduces geometry data movement and allows an entire level's nodes to be computed across a single data parallel geometry stream.

ParKD is written in C++ using Intel Threading Building Blocks and implemented on an Intel 32-processor many-core CPU. The complete ParKD package, along with user documentation, can be downloaded here.