Shadow Volume Culling

A standard feature of any modern graphics engine is support for dynamic lights and shadows. Independent of the actual shadowing algorithm used is the collection of objects known to cast shadows onto the portion of the scene visible to the camera. For bounded lights (lights with a finite spatial extent) the collection of shadow casters is a simple matter of testing an object’s bounding volume against the light’s bounding volume. In the case of unbounded, directional lights such as the sun or moon this problem is considerably more complex. An object-to-light bounding volume test is meaningless since the light’s bounding volume is infinite. Testing objects against the view frustum only gets the job half done; there is still a high probability of objects outside the view frustum casting shadows onto the view frustum. The most obvious solution to this problem appears to be straight forward:

1) Extrude the bounding volumes of potential shadow casters away from the light source thereby generating capsules for bounding spheres and convex hulls for bounding boxes.

2) Cull the capsules and convex hulls from step one against the view frustum; volumes not visible to the frustum can be discarded by the shadow algorithm.

Unfortunately there are three significant problems to this approach:

1) The initial collection of potential shadow casters is nontrivial; many implementations simply consider all objects that are currently loaded. There are high level rejection tests that can be formulated based on assumptions placed on the configuration of the scene but such tests are implementation specific and only marginally cut down on the number of objects considered.

2) The minimum required extrusion distance changes from object to object and is often times expensive to accurately calculate.

3) Poorly fitting bounding volumes generate extremely large and extremely loose bounding shadow volumes.

Robust solutions to these problems are cumbersome to implement, potentially expensive and difficult to debug. An elegant solution to shadow culling can be achieved by conceptually inverting the problem. Instead of extruding the bounding volumes of objects away from the light the view frustum can be extruded towards the light by an infinite distance. The resulting topology is an unbounded, convex volume defined by a set of bounding planes which can then be used to collect shadow casters. The extrusion process is very similar to constructing a stencil-shadow-volume from an arbitrary mesh where the front cap is kept and the back cap is discarded. This method necessitates the ability to cull objects against an unconventional but still mathematically simple convex region of space. Such functionality is not typical of your average scene manager but is nonetheless simple to add.

The process of extruding a view frustum begins with the detection of silhouette edges. An edge is classified as a silhouette edge when the normal vectors of its two adjacent faces point in opposite directions with respect to the direction of incoming light. That’s something of a mouthful so here is some code:

bool FrustumEdge::IsSilhouette(const Vector3& a_vLight)
{
    float32 fDotA = m_vFaceNormalA * a_vLight;
    float32 fDotB = m_vFaceNormalB * a_vLight;

    if((fDotA * fDotB) > 0.0f)
        return false;

    return true;
}

In practice this test should be done from inside the frustum class where the dot products of the 6 face normals and the light vector are computed once and cached. The next step is to construct plane equations from the silhouette edges; this part is a bit tricky. Culling algorithms require the plane normals to point in a consistent direction, usually outside of the constructed volume. To achieve this each edge on the frustum needs to know which one of its adjacent faces have a winding order that coincides with the edge direction. This data can be explicitly computed at extrusion time via a series of cumbersome tests or the frustum can be constructed in a specific way such that the direction pairing is an implicit property of the data. Suppose the following set of conventions is chosen:

1) Light vector points toward the light source
2) Face normals point outside the volume
3) The vertex winding of a face is counter clockwise
4) The first face associated with an edge is the face with the vertex winding that coincides with the edge direction.

The construction of the bounding plane from a silhouette edge can then be constructed in a consistent manner:

bool FrustumEdge::IsSilhouette(const Vector3& a_vLight,
                               Plane3D&       a_kPlane)
{
    float32 fDotA = m_vFaceNormalA * a_vLight;
    float32 fDotB = m_vFaceNormalB * a_vLight;

    if((fDotA * fDotB) < 0.0f)
        return false;

    Vector3 vNormal;

    if(fDotA > 0.0f)
        a_kPlane.vNormal = Vector3::Cross(m_vMyDirection, a_vLight);
    else
        a_kPlane.vNormal = Vector3::Cross(a_vLight, m_vMyDirection);

    a_kPlane.fDist = -(m_vMyOrigin * a_kPlane.vNormal);

    return true;
}

Finally, any frustum faces that point away from the light source should be added to the set of bounding planes and faces that point towards the light source should be discarded. The resulting set of bounding planes can then be used to collect objects for the shadows pass.

There are a number of different techniques that can be used when culling against an infinitely extruded frustum. My current preference is to construct a set of unique plane normals and edge directions from the extruded frustum and then perform a separating axis test against potential shadow casters. As always once the system is up and running an enormous number of potential optimization await.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s