Urbana-ChampaignUPCRC Illinois 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.

Full Story