Background

Shadow maps [4] and shadow volumes [2] are two popular means for the real-time rendering of shadows. Shadow maps are efficient and flexible, but they are prone to aliasing. Shadow volumes are accurate, but they have large fillrate requirements and thus do not scale well to complex scenes. Achieving both accuracy and scalability is challenging for real-time shadow algorithms.

Sen et al. [3] observed that shadow-map aliasing is only noticeable at the discontinuities between shadowed and lit regions, i.e. at the shadow silhouettes (see Figure 1). On the other hand, shadow volumes compute shadows accurately at every pixel, but this accuracy is needed only at the silhouettes. This observation suggests a hybrid algorithm that uses a slower but accurate algorithm near the shadow discontinuities and a faster, less exact algorithm everywhere else.

Figure 1. (a) The cylinder's shadow exhibits aliasing due to shadow-map undersampling. However, aliasing is only apparent at the shadow edges. (b) Pixels that lie near shadow edges (shown in red) account for only a small fraction of the total image size.

Method

We propose a hybrid shadow rendering algorithm, illustrated in Figure 2. We first use a shadow map (2a) to find quickly pixels in the image that lie near shadow silhouettes (2b, green pixels), then apply the shadow volume algorithm only at these pixels (2c); the shadow map determines shadows for the remaining non-silhouette pixels (2d). This approach greatly reduces the fillrate needed for drawing shadow volumes, because the number of silhouette pixels is often a small fraction of the shadow polygons' total screen area. Our method produces accurate hard shadows and has substantially lower fillrate requirements than the original shadow volume algorithm.

Figure 2. Hybrid algorithm overview.

Figure 3 visualizes how we mix shadow maps and shadow volumes. We see the shadow of a ball cast onto the ground plane. (a) Aliasing is evident when the ball's shadow is rendered using a 256x256 shadow map. The rest of the images illustrate how our method minimizes aliasing. In (b) and (c), non-silhouette pixels are shaded red and blue; for these pixels, the shadow map determines which ones are in shadow (red) and which ones are lit (blue). Silhouette pixels are shaded black and green; shadow volumes determine which ones are in shadow (black) and which ones are lit (green). Shadow-map resolutions of 256x256 and 512x512 were used for (b) and (c), respectively. The final shadow is shown in (d).

Figure 3. Visualization of mixing shadow maps and shadow volumes.

Figure 4 shows three scenes from three viewpoints, all rendered using our hybrid shadow algorithm. These scenes have high shadow complexity and render significantly faster (1.3x-2x framerate) than regular shadow volumes.

Figure 4. Three test scenes with high shadow complexity. Rows contain different scenes, and columns show different views. Each scene is illuminated using a single point light source.

To avoid processing non-silhouette pixels during shadow volume rasterization, we propose an extension to graphics hardware called a computation mask. A computation mask allows the programmer to identify a small set of pixels in the scene that are "interesting"; all other pixels are masked off. Expensive per-pixel algorithms can then operate on this subset of pixels without incurring the cost over the entire framebuffer. This strategy of decomposing a problem into two parts -- a large part that relies on a fast but inexact technique, and a small part that uses a slower but accurate technique -- is applicable to a number of multipass rendering algorithms.

Figure 5 shows how computation masks are used to accelerate shadow rendering in the Dragon Cage scene. The shadow volume polygons, shaded yellow in (a), cover the entire image and have an overdraw factor of 79; brighter yellow corresponds to higher overdraw. Our hybrid method restricts drawing shadow polygons to the silhouette pixels, shaded green in (b); these pixels cover just 5% of the image. The image on the right (c) illustrates the resulting stencil buffer: black pixels on the floor and walls are in shadow and represent non-zero stencil values.

Figure 5. Fillrate consumption and overdraw in the Dragon Cage scene.

Although computation masks are not directly exposed in current hardware, we show how to simulate them efficiently using available features related to early z-occlusion culling. Since computation masks exploit existing culling hardware, adding native hardware support requires minimal changes to modern graphics chips.

We believe that the benefits of hardware computation masks will become more significant as pixel shaders increase in complexity. Current hardware already performs aggressive occlusion culling to avoid unnecessary shading. Computation masks represent a logical step in this direction.

Progress

We have published a paper [1] on this work in the Eurographics Symposium on Rendering 2004.

Research Support

This work is supported by an ASEE National Defense Science and Engineering Graduate fellowship.

References

[1] Eric Chan and Frédo Durand. An efficient hybrid shadow rendering algorithm. In Proceedings of the Eurographics Symposium on Rendering, pp. 185--195, 2004.

[2] Frank C. Crow. Shadow algorithms for computer graphics. In Proceedings of ACM SIGGRAPH, pp. 242--248, 1977.

[3] Pradeep Sen, Mike Cammarano, and Pat Hanrahan. Shadow silhouette maps. In ACM Transactions on Graphics (TOG), 22, 3, pp. 521--526, 2003.

[4] Lance Williams. Casting curved shadows on curved surfaces. In Proceedings of ACM SIGGRAPH, pp. 270--274, 1978.