ParKD offers speed and precision for building k-D trees with multicore

Cheri Helregel, Outreach Coordinator, UPCRC Illinois, USA.

ILLINOIS, USA: UPCRC (Universal Parallel Computing Research Center) Illinois has announced the release of ParKD, a package of new, faster multicore algorithms for building precise SAH-optimized k-D trees.

The k-D tree is a well-studied hierarchical acceleration data structure for ray tracing for photorealistic rendering of scenes. It is used to organize objects in a scene to allow efficient execution of intersection operations between rays of light and the objects. The highest quality k-D tree can be obtained using greedy cost optimization based on a surface area heuristic (SAH).

While the high quality enables very fast ray tracing times, a key drawback is that the k-D tree construction time remains prohibitively expensive, especially the computation of the SAH values used to subdivide the hierarchy.

Parallel approaches to compute k-D trees for ray tracing avoid SAH when constructing the k-D tree at levels where the number of nodes is less than the number of processors. This is fine for present day multicore, but as the number of processors continue to double every couple of years, this will cause present day parallel k-D tree construction algorithms to produce increasingly worse k-D trees that will degrade ray tracing performance.

ParKD offers two new parallel algorithms for improving throughput when constructing initial upper levels of a k-D tree. The first algorithm, “nested,” 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 second algorithm, “in-place,” 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.

These new algorithms regain throughput without sacrificing spatial hierarchy quality, as measured by rendering performance gains. They compute a precise surface area heuristic (SAH) that subdivides geometry into regions of small surface area that contain many triangles.

Spatial hierarchies formed by subdividing at the spatial median (e.g., the octree) or at the object median (e.g., into children of approximately equal numbers of primitives) can be computed faster than SAH but the resulting hierarchies render slower than SAH hierarchies for the spatial median.

ParKD was developed by Byn Choi, Rakesh Komuravelli, Victor Lu, Hyojin Sung, Robert L. Bocchino, Sarita V. Adve, and John C. Hart. The ParKD package contains implementations of all the SAH k-D tree construction algorithms discussed in their paper published in the 2010 Proceedings of High-Performance Graphics.

All implementations are written in C++ using Intel Threading Building Blocks. ParKD was implemented on an Intel 32-processor multicore CPU, and is shown to scale better than previous ray tracing k-D tree construction algorithms implemented on the GPU as well as smaller-core CPU’s. The approach can also be utilized for generating bounding volume hierarchies instead of k-D trees.Parallel k-D Tree Patterns: Each level of the upper (green) portion of the tree has fewer nodes than cores, so multiple cores must cooperate on node creation leading to a breadth-first stream process that organizes all of the triangles into the current level’s nodes. When the number of nodes at a level meets or exceeds the number of cores, then each node’s subtree can be processed per core independently. The dashed dividing line (orange) where the number of nodes equals the number of processors descends one level every 1.5 to 2 years, indicating that the upper (green) pattern will eventually dominate k-D tree construction.