Raytracing Prefiltered Occlusion for Aggregate Geometry

Figure 1: Computing shadows using a prefiltered BVH is more efficient than using an ordinary BVH. (a) Using an ordinary BVH with 4 shadow rays per shading point requires 112 seconds for shadow rays, and produces significant visible noise. (b) Using a prefiltered BVH with 9 shadow rays requires 74 seconds, and visible noise is decreased. (c) Reducing noise to a similar level with an ordinary BVH requires 25 shadow rays and 704 seconds (about 9.5 times slower). All images use 5 x 5 samples per pixel. The scene consists of about 2M triangles, each of which is semi-opaque (alpha=0.85) to shadow rays.

Abstract:

We prefilter occlusion of aggregate geometry, e.g., foliage or hair, storing local occlusion as a directional opacity in each node of a bounding volume hierarchy (BVH). During intersection, we terminate rays early at BVH nodes based on ray differential, and composite the stored opacities. This makes intersection cost independent of geometric complexity for rays with large differentials, and simultaneously reduces the variance of occlusion estimates. These two algorithmic improvements result in significant performance gains for soft shadows and ambient occlusion. The prefiltered opacity data depends only on geometry, not lights, and can be computed in linear time based on assumptions about the statistics of aggregate geometry.

The definitive version of this paper appeared in the proceedings of the IEEE Syposium on Interactive Raytracing 2008.

• Look at the high resolution Figure 1
• Download the pdf preprint.
• Download the Powerpoint presentation from IRT 2008.

@inproceedings{lacewell08prefilter,
    author      = {Dylan Lacewell and Brent Burley and Solomon Boulos and Peter Shirley},
    title       = {Raytracing Prefiltered Occlusion for Aggregate Geometry},
    booktitle   = {IEEE Symposium on Interactive Raytracing 2008},
    year        = {2008}
}

Q & A

The following questions and comments came up in response to our presentation at IRT 2008:

• Did you try spherical harmonics compression yet?

  Yes, and it appears that the first 9 coefficients are sufficient, 3 of which are always zero due to the order-independence of opacity. The figure below shows a cubemap with 3x3 resolution per face (top) and the corresponding spherical harmonics reconstruction with 6 coefficients (bottom).

  
• Would prefiltering work for meshes like the Stanford Buddha and dragon models?

  These types of connected meshes violate our assumption that the opacities of nodes are uncorrelated. Prefiltering each node separately will cause light leaks. For example, if we prefilter each brick in a brick wall separately, then bricks that are not axis aligned will not fill their bounding boxes from every viewing angle and will be incorrectly classified as translucent. For these models it would be better to classify nearly all nodes as opaque.

  Below is a test with the Stanford Buddha (~1M triangles), comparing a reference solution (a) to a solution with prefiltering above height 7 in the BVH (b), and a solution where we terminated rays early but forced every node to be fully opaque (c). The prefiltering causes significant light leaks, and while there is some thickening in the shadow in image (c), this seems less objectionable than the light leaks in image (b). The bottom row of images shows corresponding worm's eye views. There is some interesting transparency along the silhouettes for the worm's eye view of the opaque nodes (f); this is due to lerping between levels in the BVH and is probably beneficial since it smooths the sharp silhouette edge a bit. Click for larger versions.

  
  

• Comment: The DC and ad-hoc results would be fine for games even though they're too dark.

  We think the DC approach is the sweet spot; even though the ad-hoc approach results in shorter build times, it may require manual adjustment by an artist on a case by case basis.

• What if you slowly rotated the axes of the BVH, or alternatively rotated the scene while the BVH remained stationary. Would this cause visible coherency artifacts?

  Yes, we tried this animation test and saw some pulsing in the shadow, although there were no sudden pops. The problem is that as the BVH rotates the boxes change shape to adapt to the geometry, and the overlap of boxes in depth may also change. Bounding spheres would not have this problem, but would probably be slower to raytrace. We haven't thought of a way to solve the problem for axis aligned boxes, and haven't done any other tests yet with dynamic geometry.

• How does raytracing compare to rasterization-based approaches for area-light shadows and occlusion?

  Shadow map approaches break down for large lights, as discussed in the paper. Other than shadow maps, rasterization could be used for a shooting approach, where the scene is rasterized from viewpoints distributed over an area light or hemisphere, or a gathering approach where the scene is rasterized from a shading point. A shooting approach requires an intermediate data structure to store visibility samples, and a prefiltered scene representation could not be used. I suspect structured artifacts would also be a problem in a shooting approach since nearby visibility samples might be computed from very similar directions.

  Switching to a gathering approach with rasterization would offer no clear advantages of algorithmic complexity, assuming the same type of geometry prefiltering was used for both. Rasterization is most efficient relative to raytracing when triangles are much larger than pixels, but the scenes in our paper do not have this property. Rasterization would require a small alpha buffer (or depth buffer, for color bleeding) at each shading point, but this is not a significant cost, and the buffer could be rotated randomly to avoid structured artifacts. Raytracing has the benefit of also being able to handle specular rays in the same framework or use importance sampling for a non-diffuse surface brdf. Whether to implement gathering with raytracing or rasterization is a matter of taste for the software architect.

• Could other acceleration structures besides a BVH be prefiltered?

  Similar methods could be used for an octree or a multi-res grid. These structures might be even faster to prefilter in bottom-up fashion because of their regular organization. Ray intersections with a BVH are usually faster than with octrees or grids for arbitrary scenes, but we have not measured whether a BVH is actually faster for aggregate geometry.

• What effects other than soft shadows might benefit from prefiltering?

  Indirect diffuse, glossy specular, motion blur, depth of field, and perhaps subsurface scattering. All these would require prefiltering not just opacity, but also color, and (for relighting) surface normal distribution functions. Inaccuracies will probably be more objectionable for primary rays. The correlation problem makes exact, view-independent prefiltering extremely difficult. We think the best attempt at prefiltering geometry for primary rays is still the thesis work of Neyret.

Addendum

• Pixar posted a tech report in July 2008 giving details of PRMan's point-based occlusion and color bleeding method, which approximates geometry as a hierarchy of opaque disks. This seems to work well for dense opaque geometry, while our method is intended for sparse aggregate geometry which is non-opaque at some scale. Another difference: the PRMan method uses ray tracing for nearby disks, and hemicube rasterization for distant disks, while our method ray traces all scales.

  Point-Based Approximate Color Bleeding
  Per H. Christensen
  Pixar Technical Memo #08-01 (available at graphics.pixar.com)

• The following tech report from UT Austin accelerates shadow rays for point lights by using a KD-Tree as proxy geometry:

  Using Annotated KD-Trees to Accelerate Shadow Ray Queries
  Peter Djeu and Stan Volchenok
  The University of Texas at Austin, Department of Computer Sciences
  Technical Report TR-08-36, August 30, 2008
  [Project Page]

updated 09/18/08