Efficient Shadows from Sampled Environment Maps

To appear in Journal of Graphics Tools  

Aner Ben-Artzi : Columbia University, aner@cs.columbia.edu
Ravi Ramamoorthi : Columbia University
Maneesh Agrawala : Microsoft Research

This image was generated using the method described in this work.  400 directional lights were used to approximate a high-dynamic range environment map.  A standard ray-tracer, augmented with our technique, was then used to compute cast shadows.  Only 4.3% or the shadow rays (400 per pixel) was actually traced.  The other 95.7% were predicted by our coherence-based method.  The rendering time needed to compute this image was about 1/10th the time required to render the image using the unmodified ray-tracer.

Abstract:  This paper addresses the problem of efficiently calculating shadows from environment maps. Since accurate rendering of shadows from environment maps requires hundreds of lights, the expensive computation is determining visibility from each pixel to each light direction, such as by ray-tracing. We show that coherence in both spatial and angular domains can be used to reduce the number of shadow rays that need to be traced. Specifically, we use a coarse-to-fine evaluation of the image, predicting visibility by reusing visibility calculations from four nearby pixels that have already been evaluated. This simple method allows us to explicitly mark regions of uncertainty in the prediction. By only tracing rays in these and neighboring directions, we are able to reduce the number of shadow rays traced by up to a factor of 20 while maintaining error rates below 0.01%. For many scenes, our algorithm can add shadowing from hundreds of lights at twice the cost of rendering without shadows.

The process:

In order to find a correct and efficient algorithm, we explored various possibilities for the components of our coherence-based framework. The SHAPES scene was most useful for interactive exploration of the possible algorithms. We used a visualization tool (link below) to examine the effects of changes to the algorithm. In the end, we chose a very simple algorithm that was both fast and accurate.

The results:

Our results show that for only twice the running-time of rendering a shadow-less scenes, complex shadows can be added with our method. In addition, the final algorithm is very simple to add to existing ray-tracers. It is also robust to variations in implementation, so that an approximate implementation suffices in most cases.
latex source as 33 MB in a zip file

The links:

The paperA pdf of the paper to appear in JGT1.3MB
A 36in x 48in poster from SIGGRAPH 2004 Poster Session 1.7MB
Bunny animation, OPT An animation of the Bunny scene, computed with OPT, showing the sampled environment (~400 lights) being rotated. ~12MB
Plant animation, OPT An animation of the Plant scene, computed with OPT, showing the sampled environment (~400 lights) being rotated. ~38MB
Plant animation, TRUE The same animation of the Plant scene, computed with TRUE. The high frequency shadows cause the leaves to shimmer during the animation. Here, we can see that this is not a result of the CBVS algorithm. ~38MB
Shapes animation, OPT An animation of the Shapes scene, computed with OPT, showing the sampled environment (~400 lights) being rotated. ~12MB
Shapes animation, OPT_FLO An animation of the Shapes scene, computed with OPT but the flooding restrictions are performed at the Finest Level Only. This removes the incorrectly filled shadow of the torus noticeable in the OPT animation. The performance of this method is roughly 25% worse than OPT ~3MB
VisView This package contains code and executable for the visualization tool used to explore the methods dexcribed in the paper. (comes with only 1 sample data-set). The fastest way to start using VisView is to unzip this .zip file and open visview.exe in teh Debug directory. Alternetavly, use one of the datasets below that comes with command-line arguments (copy visview.exe into the same direcotyr as the other files in the data-sets). ~5MB
CBVS data-sets This package contains the data needed by VisView. It also explains how to generate data for new scenes, and contains a batch file with command-line arguments to recreate all the figures in the paper. ~127MB
CBVS data-set for Figure 6 only Same as the above package, but only has support for Figure 6 of the paper. ~10MB