SRDH: Specializing BVH Construction and Traversal Order Using Representative Shadow Ray Sets

Nicholas Feltman, CMU
Minjae Lee, CMU
Kayvon Fatahalian, CMU

Proceedings of High Performance Graphics 2012, Paris

A large percentage of shadow rays intersect the middle set of shades (highlighted in red) in this scene. Two BVHs, one constructed using the traditional SAH and one constructed using SRDH are shown at right. (Numbers indicate subtree node counts, and subtrees containing the shades geometry are marked in red.) The SRDH tree pushes the highlighted blinds geometry towards the root and selects constant traversal kernels (red arrows) that guide rays to this subtree.


We derive the Shadow Ray Distribution Heuristic (SRDH), an accurate cost estimator for shadow ray traversal through a bounding volume hierarchy (BVH). The SRDH leverages up-front knowledge of the distribution and intersection results of previously traced shadow rays to construct a shadow-ray-specialized BVH and choose an associated traversal order policy which together promote early termination by quickly finding occlusions. In scenes containing large amounts of occlusion, SRDH reduces the number of BVH node traversal steps needed for shadow computations between 22% and 56% compared to average-case traversal through SAH-constructed trees. Evaluating the SRDH using a sparse shadow ray set recorded from a 16x16 pixel rendering of the scene consistently produces BVHs whose traversal cost is within 6% of those built when all shadow rays are available to the metric at the time of construction. The benefits of the SRDH come at the cost of storing an additional BVH in memory and a 2.4x increase (on average) in BVH construction time.


Download Paper (pdf)