SATO: Surface-Area Traversal Order for Shadow Ray Tracing

Jae-Ho Nah and Dinesh Manocha
University of North Carolina at Chapel-Hill

green bar

We present the surface-area traversal order (SATO) metric to accelerate shadow ray traversal. Our formulation uses the surface area of each child node to compute the traversal order. In this metric, we give a traversal priority to the child node with the larger surface area to quickly find occluders. Our algorithm reduces the preprocessing overhead significantly, and is much faster than other metrics. Overall, the SATO is useful for ray tracing large and complex dynamic scenes (e.g. a few million triangles) with shadows.


[Teaser Image] 

    

Ray-traced images in the dense crowd simulation scenario with different numbers of agents: (left) 1,000 agents, (middle) 4,000 agents, and (right) 16,000 agents. Each agent corresponds to a dynamic object in the scene, and at each frame we update the hierarchy. Our surface-area traversal order (SATO) metric only requires 1.6 ms with a 4-core Core i7 CPU to calculate the traversal order for 16,000 agents with 10.9M triangles, which makes it attractive for large dynamic scenes. Moreover, the SATO metric decreases the ray-tracing time by 15% in this complex dynamic scene.
 

[Publication]