Dev Fjord: JOGL Part 3 - Shadow Volumes

Next: Shadow Maps

This section will be about one of the shadow techniques I've used in my project: Shadow Volumes. This method was mostly popularized by id Softwares Carmack and Doom 3. While it has pretty much vanished from todays engines (unreal engine 3 still supports them, maybe others), it's a perfect example on how shadows can add to the atmosphere.

First some moving pictures:

The main idea behind this technique is to draw a volume around the area where the light should not hit the geometry (hence shadow). The method consists basically of two steps:

Constructing the shadow volume
Getting the light to not hit the area inside that volume

This image shows two shadow volumes cast by one light source. The green edges indicate the shadowed areas visible from the camera.

A Light casting Shadow Volumes on Objects

Constructing the Shadow Volume

To build the shadow volume for an object one has to calculate the objects silhouette from the viewpoint of the light. This silhouette is then extruded away from the light resulting in the shadow volume boundaries. The silhouette is determined by finding all the edges that lie between a face that points to the light and one that points away. This can be done by comparing the vector from the light to the face and the face normal. A pseudocode way of doing this:

// e.g. some map class
  EdgeContainer silhouetteContainer;
 
  foreach shadowcasting object
    foreach face of the object
      if face is pointing to the light
        foreach edge of face
          if edge is in silhouetteContainer
            remove edge from silhouetteContainer
          else 
            add edge to silhouetteContainer
          end
        end
      end
    end
  end
  
  silhouetteContainer now contains all edges of the object silhouette

Finding the Silhouette

One note on this algorithm: it only works for edges that have at most two neighboring faces. The extrusion of the silhouette is simply done by adding the vector from the light to the edge vertices as a vector pointing to infinity (w component = 0).

Depending on the used render method the shadow volume needs additional caps at the front and/or back. The front cap is created by duplicating every face that points to the light. The back cap is created by extruding every of these faces to infinity.

Building the shadow volume is a computationally intensive task since the algorithm has to iterate over all faces of the occluders for each light and compare their alignment to the light. With rising geometric complexity of the scene and objects, it takes longer to compute the volume. On the bright side, it's a perfect candidate for multi-threading. Every calculation only requires read-only access on the light and objects and has the volume as the output.

Rendering the Light

The stencil buffer is used to mark every pixel that should not be lit by a light. There are plenty methods with which the buffer can be filled (see here), each with their own pros and cons. One problem came up by incorporating the shadow volumes with the deferred renderer. The lights already use the stencil buffer to render a light volume that marks the lit pixels. To make this work I use another, more coarse, stencil method for the light volumes if it casts shadows. Also, after a light is drawn with shadow volumes, a full clear of the stencil buffer is necessary which is not required if the light does not use this kind of shadows (see last post).

The use of the stencil buffer results in pixel-perfect hard-edged shadows which is pretty different to shadow maps (see next post (not done yet)). Since shadow volumes are using the geometry of objects to generate the shadows it is difficult to add shadows from transparent or alpha masked objects since they are normally encoded in the textures. It may be possible using another technique that creates the shadow volume from a shadow map (see here).

Depending on the chosen shadow volume algorithm, another problem arises with the backcap of the shadow volume. Some techniques require that the backcap is rendered all the time while not being cut off by the far plane. This can be achieved by setting the far plane to infinity (see here), using a specialized shader to draw the shadow volume or using the NVidia-specific GL_DEPTH_CLAMP_NV extension. While I was using GL_DEPTH_CLAMP_NV on NVidia cards, I put the far plane to infinity on ATI cards. When doing that, one has to make sure that the encoded position of the G-Buffer is still reversible.

An optimization that comes in handy with shadow volumes is the scissor test (GL_SCISSOR_TEST). This restricts the whole filling of the stencil-buffer and rendering to a portion of the screen to a fixed screen-rectangle. The rectangle should have just the size of the light radius, projected to the screen.