A Hierarchical Volumetric Shadow Algorithm for Single Scattering

Ilya Baran     Jiawen Chen     Jonathan Ragan-Kelley     Frédo Durand     Jaakko Lehtinen

Rendering volumetric shadows in participating media requires integrating scattering over view rays. Left: The visibility component of this integral has a special structure: once a light ray hits an occluder, that light ray does not contribute to the integral along any view ray past the occluder. Middle: Our method exploits this structure by computing the integrals in an epipolar coordinate system, in which light rays (dashed grey) and view rays (solid black) are orthogonal and the integration can be performed asymptotically efficiently using a partial sum tree. Right: This enables us to compute high-quality scattering integrals much faster than the previous state of the art.

Paper: PDF (SIGGRAPH Asia 2010)
Video: MP4 (98MB, no sound)
Slides from SIGGRAPH Asia 2010: PPTX (Powerpoint 2007, download the linked video below to see the clip embedded in the slides)
Linked video: WMV (27 MB)


Volumetric effects such as beams of light through participating media are an important component in the appearance of the natural world. Many such effects can be faithfully modeled by a single scattering medium. In the presence of shadows, rendering these effects can be prohibitively expensive: current algorithms are based on ray marching, i.e., integrating the illumination scattered towards the camera along each view ray, modulated by visibility to the light source at each sample. Visibility must be determined for each sample using shadow rays or shadow-map lookups. We observe that in a suitably chosen coordinate system, the visibility function has a regular structure that we can exploit for significant acceleration compared to brute force sampling. We propose an efficient algorithm based on partial sum trees for computing the scattering integrals in a single-scattering homogeneous medium. On a CPU, we achieve speedups of 17-120x over ray marching.


Since publication, we realized that we did not fairly measure the performance of epipolar sampling [Engelhardt and Dachsbacher 2010]. We reported their per-frame scattering time to be 27 and 42 milliseconds on Sibenik and Trees, respectively. Although we bypassed their direct illumination shaders for this measurement, these numbers still include overhead not related to the scattering computation. We also neglected to mention that our GPU implementation incurs a 10ms GPU/Direct3D interop overhead, which we do not count towards the scattering timing.

To enable us to make more accurate measurements, Thomas Engelhardt was kind enough to send us a version of his code that allowed us to turn off the scattering computation. It also enabled using 2264 epipolar slices, rather than 1000, to better match the quality of our other results. With 2264 slices, the total per-frame time on the Sibenik scene is 41ms, while the direct lighting time is 2ms, so the scattering-only time on Sibenik is 39ms. Our scattering-only time on Sibenik at 2264 slices is 31ms (a 1.25x speedup). The speedup is greater than initially reported because at 1000 slices our method was not saturating the GPU. On the Trees scene, epipolar sampling uses 83ms per-frame total, of which 5ms is used for direct lighting and 78ms for scattering. Our per-frame time on Trees is 43ms (a 1.8x speedup). Therefore, at these settings, our method is slightly faster, while producing higher-quality results on both scenes.


We have followup paper at i3D 2011.