Real-Time Shadow Casting Using Shadow Volumes

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.

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.

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.

Implementation: Birth of a Shadow Volume

The first step in creating a shadow volume is to develop an effective method for identifying the shadowing edges of any object. Among the many available techniques for determining the edges, we discovered that the quickest method entails generating face connectivity information before runtime. Connectivity data is stored as an internal list of all neighboring faces for every triangle. Listing 1 shows pseudo-code that suggests how to generate the connectivity. This can be accomplished either during the loading of the model, or the data can be preprocessed and stored into the file format. Once this information is available, an application can efficiently determine boundary edges of an object. Edges are determined by culling faces that are not viewable from the current light perspective, and then identifying edges that lie along the boundary of the culled and not-culled faces. Listing 2 shows the pseudo-code that represents this routine. Source code for all methods described in this article can be found in the demo project, which is downloadable from the Game Developer website.

After the boundary edges have been detected, polygons can be generated to form the actual shadow volume. This can be accomplished simply, or it can be a more difficult task, depending on the approach. At the most basic level, two new vertices need to be created in the direction of the light, away from the vertices of the current edge. With the resulting four points, two simple triangles can be formed. A number of complexities arise depending on how far you want to extend the new points.

Three possible implementations are as follows:

Implementation: The Baby Grows Up

Once the shadow volume has been generated and stored in memory, the real fun begins. As mentioned in the overview, the volume must be rendered in its entirety to the stencil buffer only; no color information should be displayed. Listing 3 shows the Direct3D implementation of the appropriate renderstate settings. The polygons are rendered in flat shading mode, as we do not want the card to waste cycles on gouraud shading that will never be displayed. The stencil buffer values are incremented for every pixel that the card renders during this pass.

Just when you thought your volume rendering days were over, we must make another render pass using the same polygons. This time we must really shake up the natural order of the universe and reverse the cull mode, as well. Listing 3 shows the Direct3D implementation for setting the appropriate second-pass rendering. Note the changes in the stencil functionality, as well as the cull mode reversal. The volume is then rendered to the stencil buffer in the same style as the first pass, but this time decrementing the stencil values rather than incrementing them. Remember to set the Z-buffer, stencil buffer, and cullmode back to their proper settings before proceeding to render the next scene.

The application must repeat the volume generation and rendering for every shadowed object, for the current light, before rendering the actual shadow. This not only increases performance (since rendering the true shadows can be costly, as we will soon find out), but this method avoids creating multi-darkened artifacts in the shadows.

At this point, the visual representation of the shadow can be rendered. The principle is very simple. Two large, gray, alpha-blended triangles are rendered to the entire screen. The stencil operations are set to only render pixels that have a corresponding positive value in the stencil buffer. Listing 4 shows the renderstates used to accomplish this operation.

The Darkness and the Light: Pros and Cons

Employing shadow casting in real-time 3D interactive environments, using the techniques we've presented in this article, has both advantages and disadvantages. In this section, we will consider both. Positive benefits include greatly improved realism, achieved without requiring texture manipulation or undue loss of rendering speed. On the negative side, the programmer must deal with stencil buffer support, fill-rate limitations, sharp shadows, small polygon anomalies, and advanced scene-management concerns.

Greatly improved realism is the most significant gain offered by real-time shadow casting. When you use full shadow casting, an entire scene behaves realistically with any number of polygons and objects. Scenes can be completely dynamic, with no previous lighting calculations necessary (excluding the connectivity information mentioned earlier). Objects will also shadow themselves, something that is not easily done with texture-mapping techniques, due to the intensive computations and the number of texture passes that are necessary.

Reducing the number of texture passes required for a scene is another large benefit of the shadow casting method. With texture-based shadows, as described in earlier articles in this publication, the number of texture modifications and renders needed to shadow a well-populated scene becomes excessive and unbearably complex. Hardware graphics accelerators are unpredictable in their texture-rendering performance across different chipsets. The shadow-casting method is more fill limited, a metric that is more easily understood when coding for the widest range of accelerators.

For all its benefits, shadow casting also has a dark side (this time, the pun was initially unintentional), as many new technologies do. The foremost problem is the reliance upon 8-bit stencil support on the graphics hardware. This factor was especially significant at the time the sample code was originally written. Looking towards the future, however, we predict that 8-bit stencil support will become standard within the next hardware generation. Card fill rate also ranks as an important concern, as the number of polygons that must be manipulated rises dramatically with shadow casting. Shadow rendering can easily become the application bottleneck. The only upside to this is that more CPU cycles can be spent in other application areas without affecting frame rate beyond the shadow bottleneck.

A smaller concern is the generation of 'sharp' shadows as a by-product of the technique itself. Since shadows are generated by polygonal edges, they are perfectly crisp on their boundary. In many situations, 'soft' shadows that either attenuate or dither at the edges provide a more pleasing complement to the lighting in a scene. Since the actual polygon rendering is performed blindly across the entire screen, these kinds of softening operations are extremely difficult to perform and slow down processing considerably (to the point of being impractical to implement). Also, if an object is either extremely detailed or very small on the screen, the shadow cone polygons can become single pixel width or smaller. This causes visual anomalies onscreen in the form of gaps or shadow flickering.

The last potential problem with shadow casting involves the complexities of advanced scene management, particularly in cases where more than simple overhead lights are used (note that most shadow casting demos only show the simple case). The next section addresses this issue and other problems in more detail, with some suggestions on how to alleviate potential issues.

The Path to Enlightenment

The basic algorithm and the high-level details for successful shadow casting are short and simple. We hope that these have been presented in an enlightening manner. Generally, however, we have only touched on the basic principles of shadow casting. We could easily fill another half-dozen articles with additional perspectives and discussions of related issues. Before concluding this article, we would at least like to touch upon a number of real-world implementation issues that you may want to keep in mind as you approach any project that involves shadow casting. Many of these issues are essential concerns in a real-world shadow casting application.

Earlier, we introduced the problem of sub-pixel width polygons being produced from high density or small object shadow volumes. Computing and rendering shadow volumes from an invisible level of detail (LOD) model can spare us this problem, as well as minimizing the calculation and rendering time. While this method produces some visual artifacts of its own, primarily objects that shadow themselves, the overall effect is usually acceptable. It is also faster and it reduces the nasty-looking artifacts often associated with sub-pixel rendering. Most overhead involved with LOD shadowing can be amortized if LOD models are being used in the application for other purposes, such as collision detection.

The most difficult problems encountered with shadow casting involve scene and geometry considerations. You may have noticed that most shadow-casting demos demonstrate the technique using only a single overhead light with a non-moveable camera. This carefully contrived approach helps to build the excitement of the observer (and future implementer) without reckoning with the additional problems of point of view and light source changes. At some point, either during or after the demo, the programmer may latch on to the difficult question, 'What if the camera lies within the shadow volume?' The basis of this shadow casting algorithm relies on the fact that a beam cast from the user's eyeball to any shadowed point in the scene must pass through both the front and back side of the shadow volume. Once the volume swings toward the near plane, this effect is lost. In essence, the user is left staring down the barrel of a corrupt shadow implementation.

Our solution to this problem involved 'capping' the shadow volume whenever this special case was detected. To implement capping, the object geometry was converted to a two-dimensional version and then transformed to the near plane, perfectly capping the open volume. See Figure 4 for a visual example of this technique.

Aggressive frustum culling and high-level scene culling can also cause problems when shadow casting. Even if geometry and lights exist outside the current viewing frustum, the shadow of the geometry can still penetrate into the visible scene. For example, as a shadow volume nears the parallel plane of the ground, it can extend for enormous distances before actually connecting with the ground. This factor must be handled in some manner within in the scene manager, depending on the individual application. Possible solutions include limiting shadow distances (to help the scene manager culling), and performing simple checks to determine if a piece of geometry could possibly shadow the visible scene. Errors in this implementation might cause noticeable 'popping' of shadows as objects are recognized as shadow casters too late in the process.

The frustum near plane can also cause related problems. Assuming that the application prevents objects from piercing the viewable near plane, a special case still exists in which geometry pierces the non-viewable near plane, yet the light direction causes the shadow volume to cross into view space. This again creates a situation where a given pixel may not lie between both sides of the volume, resulting in undesired effects. Detecting and fixing this case is much more difficult than the 'capping' scenario, because of the intersection with the near plane. One possible solution is to generate a new silhouette to shadow, taking into account the near plane. Another solution is to prevent this case from occurring by handling it at the scene manager level. You may produce popping effects by doing so, but this approach will generally be the simpler of the two.

Turning Shadows into Special Effects

Rather than just being a source of potential problems, the shadow casting algorithm can also present new effects possibilities. Shadow coloring is one easy addition to the algorithm that can produce highly realistic or amazing creative effects. By altering the color of the overdraw surface from the basic gray presented here in our examples, you can achieve shadow regions with vivid colors or elaborate textures. This effect can be used for accurate shadow colors in multiple colored-light environments, or even strange otherworldly effects, where shadows seem to be swirling, eerie domains of doom and darkness.

There is no rule that the cast volumes must be used for shadows. By choosing a non-invisible alpha blend mode, and perhaps even textures, you can create interesting spotlight, projector or flare effects from a light source. This technique works well when choosing additive blend modes for the overdraw polygon, creating a realistic light-mapping effect rather than shadows.

As the Light Source Sets in the West

Throughout this article, we have tried to demystify the process of creating shadows in 3D environments. We have also tried to provide some concrete methods that programmers can employ to add that extra element of realism that real-time shadows can add to an imaginatively rendered world. We hope that the examples and the algorithms will encourage programmers to experiment with these techniques and perhaps adapt them for actual applications.

Improvements in hardware acceleration techniques and software graphics handling techniques will continue to raise the range of possibilities for creative professionals. As processors become blindingly fast, and graphics accelerators process more triangles than a Doritos factory, we can take advantage of all these extra capabilities to produce some extremely interesting applications.

Jason Bestimt graduated from Virginia Tech and went to work for Intel's developer relations group working on 3D apps. Recently he joined the team at Firaxis Games working on their upcoming products.

Bryant Freitag is an Application Engineer in the Developer Relations Division at Intel Corporation. When not optimizing, analyzing, and in general doing 'real' work, he strives to make video gaming better for all mankind. This evidently involves playing lots of games as well.