On the Use of Local Ray Termination for Efficiently Constructing Qualitative BSPs, BIHs and (S)BVHs

Abstract

Acceleration data structures (ADSs) exploit spatial coherence by distributing a scene's geometric primitives into spatial groups, effectively reducing the cost of ray tracing queries. The most effective ADSs are hierarchical, adaptive tree structures such as BSPs, BIHs and (S)BVHs. The de facto standard cost metric for building these structures is the Surface Area Heuristic (SAH), which assumes a scene-exterior isotropic ray distribution of non-terminating rays. Despite its restrictive assumptions, the SAH remains competitive against many fundamentally different cost metrics targeting more common ray distributions. Our goal is not to radically change and replace the SAH, but to adapt it by introducing the concept of local ray termination in the context of voxel partitioning during the ADS construction and voxel traversal order during ADS traversal. We develop heuristics to approximate local ray termination efficiently without additional preprocessing or ray (sub)sampling. Our heuristics are used for approximating the visibility probabilities in the Ray Termination Surface Area Heuristic (RTSAH) for constructing BSPs, BIHs and (S)BVHs for accelerating closest-hit ray queries and for approximating the hit probabilities in the Shadow Ray Distribution Heuristic (SRDH) for constructing dedicated BVHs for accelerating any-hit ray queries. The main aim of our paper is to analyse the potential of including local ray termination into the SAH. The results indicate rendering performance close to the references (SAH and NodeSATO) on average due to small and/or compensating gains in the number of ray-triangle intersection tests and ADS node traversal steps. Furthermore, prerendering build times are higher for the RTSAH due to triangle clipping.