Part of the nerve-tingling pleasure of the immersive gaming experience is entering and exploring elaborately modeled worlds-the more realistic, the better. Games can transport us to an endless variety of locales, from fantastical worlds of magic and mystery to realistic environments of danger and excitement. Improvements in graphics accelerators have let programmers advance beyond the limitations of 2D games and create 3D environments with remarkable realism, while steadily escalating processor speeds and graphics optimization techniques provide new opportunities for refining 3D realism and advancing to new levels of interactivity.

But despite the rich, vibrant colors, the intricately rendered textures, and the dazzling effects exhibited in modern games, the human brain still senses something is missing. The mind perceives that the onscreen image is just a trick, an elaborate ruse played on the intellect by a collaboration of electrons, mathematics, and glowing phosphor. Even with fancy perspective divides and texture perspective correction, the onscreen rendering still lacks a true sense of depth. What's missing? The missing element could be shadows. Without them, the 3D illusion is sorely lacking.

Real-time dynamic shadowing represents a huge leap forward in realism, depth perception, and the overall presence of objects within a 3D environment. This article discusses one method for generating and rendering shadows using shadow volumes. First, we will explore the concepts involved in representing shadow volumes and explain our particular method for accomplishing this. Then we will examine the pros and cons of this method and consider additional issues that arise when using shadow volumes.

Let the Shadows Fall Where They May

Many methods currently exist for determining and displaying real-time shadows, including plane projections, texture mapping, shadow volumes, and ray tracing techniques. For an excellent explanation of the texture-mapping method, refer to Hubert Nguyen's article "Casting Shadows on Volumes" in the March 1999 issue of Game Developer. Our initial efforts to implement real-time shadowing used a method very similar to the one described by Nguyen. Unfortunately, we found this method hampered by the same negative factors that were recognized and described by Nguyen: slow texture rendering, the large overhead required to self-shadow, the excessive iterations required for complex scenes, and hefty texture dimensions needed to avoid pixelation. Our explorations for a more effective technique led us to shadow casting.

Rapid improvements in graphics accelerator technology have made it possible to achieve high-end workstation performance in the PC desktop environment. Given these improvements, many graphics techniques can be incorporated into the real-time 3D game space from their original workstation-based roots. Now that 8-bit stencil buffers are appearing on a wide assortment of graphics accelerator cards, shadow-casting methods can be employed for generating real-time shadows with only a minimal performance hit.

The algorithm includes three important components: a means for generating the 'outside' edge of an object, a method for drawing the shadow volume polygons, and a technique for rendering the actual shadow. We will discuss each of these components conceptually and then provide the actual implementation details in later sections.

Figure 1. Shadows can be shaped and positioned through the use of a shadow volume.

The 'outside' edge of an object does not necessarily relate to the convex hull of that object. We need to locate all edges of the object that form the object silhouette from the perspective of the current light source. Once the edges are located, we can create and project the shadow volume. Where the object edges interrupt the cone of light from the light source in the scene, a shadow is cast. Imagine the beam projected from a flashlight, but rather than bathing a scene in light, we use the object to cast a shadow into the scene. Figure 1 sheds some light on this concept (pun intended). Once the silhouette edges are determined, new polygons are formed by the extension of these edges in the direction indicated by the current light source. Collectively, these polygons are referred to as the shadow volume. By correctly combining this volume with stencil buffer operations, shadows can be shaped and positioned within a scene.

The entire scene is initially rendered without any consideration for shadowing. The trick of the matter is to actually render the shadow volume twice within the scene, invisibly both times. First, the volume is rendered into the scene, incrementing the stencil buffer value for every pixel that passes a normal z depth test. Next, the cull mode for the graphics card is reversed, and the volume is re-rendered. The stencil buffer is decremented for every pixel that again passes a normal z depth test. Figure 2 illustrates this technique. As a result of these operations, the stencil buffer holds a positive value for all pixels that lie within the shadow volume region. This fact logically leads to the next step in the algorithm: the actual rendering of the shadow.

Figure 2. The trick is to render the shadow volume twice within the scene, invisibly both times.

After this same series of operations has been performed for all objects in the scene, an alpha-blended quad is rendered to the entire screen. The graphics card is set up to render only the pixels in the stencil buffer that have a positive value associated with them. Shadows now appear in the scene as intended. The stencil buffer should be cleared, and the entire process repeated for the next light in the scene. By correctly configuring the stencil buffer settings during the visible shadow render, the overhead associated with stencil clearing can be minimized. The graphics card can set the stencil buffer value to zero every time the stencil check passes and a shadow pixel is drawn. This operation ensures a zero-filled stencil buffer that is ready for the next light or frame.