SAH-Optimized k-DOP Hierarchies for Ray Tracing

Martin Káčerik Jiří Bittner
Czech Technical University in Prague
Faculty of Electrical Engineering

Proceedings of the ACM on Computer Graphics and Interactive Techniques (Proceedings of HPG 2024)
Denver, CO -- July, 2024
https://doi.org/10.1145/3675391

We revisit the idea of using hierarchies of k-sided discrete orientation polytopes (k-DOPs) for ray tracing. We propose a method for building a k-DOP-based bounding volume hierarchy while optimizing its topology using the surface area heuristic. The key component of our method is a fast and exact algorithm for evaluating the surface area of a 14-DOP combined with the parallel locally ordered clustering algorithm (PLOC). Our k-DOP PLOC builder has about 40% longer build times than AABB PLOC, but for scenes with oblong slanted objects, the resulting BVH provides up to 2.5x ray tracing speedup over AABB BVH. We also show that k-DOPs can be used in combination with other techniques, such as oriented bounding boxes (OBBs). Transforming k-DOP BVH into OBB BVH is straightforward and provides up to 12% better trace times than the transformation from AABB to OBB BVH.
Source code repository


Corrigendum
There is a mistake in Appendix A of the original published article. The constant on the line 42 of Listing 1 is inconsistent with the derived Equation 4. Pre-multiplied value of the constant depends on the distance s2, where s itself is scaled by the value of 0.5 (see Equation 3). Therefore, the constant has to be scaled by 0.52 = 0.25 instead of 0.5 as in the published version.
The correct pre-computed constant value valid in the context of provided function is 0.06698729810778067 instead of 0.13397459621556135. Corrected source code is available in the repository.