Contents

Real-Time Dynamic Shadow-Casting Implementations / Pros and Cons The Path to Enlightenment

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.

Allocate the memory for the connectivity data (one structure per face) For (a = every face) {   //Edge 0   If ( The first edge does not already have a neighbor )   For (b = every other face)   {     If ( The first edge of a = any edge in b )     {       They are neighbors !!!        Quit looking for a neighbor for this edge     }   }      Do the same for Edge 1   Do the same for Edge 2 }

Listing 1. Generating the connectivity

Light Direction = Direction of the light in the object's local space Extension Vector = Light Direction * "Infinity" // Length of the shadow volume /////////////////////////////////////////////////////// For ( f = Every face in the Mesh ) {   if ( Face Normal * Light Direction = Visible )   {     Face is not culled   }   else   {     Face is culled   } } ////////////////////////////////////////////////////// For ( f = Every face in the Mesh ) {   if ( f = visible )   {     if (( f's first edge does not have a neighbor ) OR (f's first  edge neighbor is NOT visible))     {       // This is a shadow casting edge       Add vertex 0       Add vertex 0 + Extension Vector       Add vertex 1       Add vertex 1 + Extension Vector       Add 2 faces     }     Do the same for edge 1     Do the same for edge 2   } }

Listing 2. Generating Silhouette Information

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:

1. Extend the edges a sufficient distance to guarantee extension beyond the view frustum (a.k.a. the Brute Force approach). Listing 2 shows an example of this method.
   
   While this method works perfectly well, two performance concerns should be noted. First, the graphics hardware or custom clip code will be forced to clip these polygons. This may result in potential performance problems. Second, the shadow volume polygons generated in this manner will pierce all of the geometry in the scene. Depending on the extent of your shadowing, this can be a good thing or a bad thing. Refer to item 2 for further information…
   
   
2. Clip the shadow volume vertices upon contact with scene geometry.
   
   This approach is useful if you are not shadowing every object in your scene. Refer to Figure 3 for an example of this method. For example, if an object is located on one side of a wall, and the current view shows the other side as well, the object's shadow will normally penetrate the wall (if you are using method #1). This technique is perfectly fine, as long as the wall also generates a shadow.
   
   

   Figure 3. Clipping the shadow volume vertices upon contact with scene geometry.

   Using this technique, no artifacts will be visible to the viewer as long as every object in the scene is shadowed. In this example, if the application was not creating shadows for the walls, the shadows from each object would have to be clipped to the plane of the wall to avoid artifacts. Keep in mind that if the scene-clipping method was used, and the wall had a hole in it, the shadow would not pierce through the hole using this method alone. Further computation must be performed to accomplish this properly.
   
   
3. Clip the shadow volume to the view frustum.
   
   This approach is a variation of the edge-extension method previously described. The technique avoids the performance hits that come from depending on the hardware for clipping. However, the same problems mentioned for the previous method will still exist.

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.

//Draw the volume opening side dev->SetRenderState(D3DRENDERSTATE_STENCILPASS, D3DSTENCILOP_INCR); dev->SetRenderState(D3DRENDERSTATE_CULLMODE, D3DCULL_CCW); dev->DrawIndexedPrimitive {   D3DPT_TRIANGLELIST,   D3DFVF_VERTEX,   VtxPool,   vnum,   FaceList,   fnum,   0 }; //Draw the volume closing side dev->SetRenderState(D3DRENDERSTATE_CULLMODE, D3DCULL_CW); dev->SetRenderState(D3DRENDERSTATE_STENCILPASS, D3DSTENCILOP_DECR); dev->DrawIndexedPrimitive {   D3DPT_TRIANGLELIST,   D3DFVF_VERTEX,   VtxPool,   vnum,   FaceList,   fnum,   0 };

Listing 3. D3D shadow volume rendering

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.

static D3DTLVERTEX box[4]; static WORD box_faces[6] = {0,2,1,0,3,2}; static bool first = true; static DWORD color = 0x00E0E0E0; m_dev->SetRenderState(D3DRENDERSTATE_SRCBLEND, D3DBLEND_DESTCOLOR); m_dev->SetRenderState(D3DRENDERSTATE_DESTBLEND, D3DBLEND_ZERO); m_dev->SetRenderState(D3DRENDERSTATE_STENCILFUNC, D3DCMP_LESSEQUAL); m_dev->SetRenderState(D3DRENDERSTATE_STENCILPASS, D3DSTENCILOP_ZERO); if (first) {   first = false;   Zero Memory for vertices   Assign 4 vertices to the 4 corners of your screen } m_dev->DrawIndexedPrimitive(D3DPT_TRIANGLELIST, D3DFVF_TLVERTEX,   box, 4, box_faces, 6,   D3DDP_DONOTCLIP);

Listing 4. D3D shadow fill rendering

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