Discrete oriented polytopes with orthogonal bases for the construction of tighter Bounding Volume Hierarchies

Abstract

A myriad of intersection tests is necessary for culling algorithms to answer intersection queries in the field of ray tracing. BVHs are employed to accelerate such queries. OBB-based BVHs usually outperform their AABB-based counterparts in terms of culling efficiency but OBBs are more expensive to compute than AABBs. On the other hand, state-of-the-art BVH builders require linear complexity OBB building algorithms. PCA-based methods run in linear time but demand high memory bandwidth and offer poorly fitting OBBs due to statistical bias. To address these problems, we propose building OBBs with the intermediate use of an orthogonal set of polytopes bases (ODOPs) that stores the unbiased topological features of the scene and enables a straightforward conversion to OBB without the need for vertex processing. Our method supports both vertices and parametric differentiable swept volumes. This approach interfaces to state-of-the-art BVH builders by swapping AABBs in favor of ODOP routines. Our analysis focus on static scenes, highlighting the potential of ODOPs in accelerating geometric computations within ray tracing frameworks. Experiments show that OBB-BVHs built using this method usually outperform AABB-BVHs in terms of SAH costs. Moreover, the OBB-BVHs tested are observed to return query results using fewer intersection tests compared to AABB-BVHs. These measurements are consistent with the decreased rendering times observed by the adoption of our methodology in ray tracing.