1.0 Introduction

To efficiently render a scene, the minimal possible amount of geometry must be passed to the GPU. Objects that do not intersect the view frustum can be ignored. When rendering using an additive shadow algorithm (stencil shadow volumes or shadow mapping), the scene is rendered in multiple passes, one pass for each light source. In this case objects can be ignored when they do not intersect both the view frustum and the light source's bounding volume.

For shadow casters though, checking only against the view frustum is not sufficient. Objects that lie outside the view frustum (herein “the frustum”) can still cast shadows into the visible area. Diagram 1 shows a simple case.

Diagram 1: B lies outside of the frustum, yet it casts a shadow into the frustum

If instead, the light source's bounding volume is used to determine potential shadow casters, then all correct shadow casters will be returned. But this approach is too conservative. It will also return true for objects that cannot cast a shadow into the frustum. The final results on the screen will look the same, but it will take longer to render as all the vertex calculations must be performed. Diagram 2 shows such a case.

Diagram 2: C intersects the light's bounding volume, yet it cannot cast a shadow into the frustum

To solve this problem, we instead check against a shadow caster volume. The shadow caster volume is the convex polyhedron that intersects any objects that can cast a shadow into the view frustum. It is calculated by extending the view frustum to include the light source. Diagram 3 shows the shadow caster volume for the scene in Diagram 2.

Diagram 3: The shadow caster volume for the light source includes B, but not C

Note that as well as checking potential shadow casters against the shadow caster volume, they should also be tested against the light source's bounding volume. This is particularly important for small point light sources.

This article will cover the calculation of shadow caster volumes, and in the process of doing this, will also cover LUP decomposition of matrices. LUP decomposition turns out to be necessary for the numerical stability of this algorithm, even when using double precision IEEE 754 calculations.

The way the shadow caster volume is generated depends on the type of the light source. To start with we will cover point lights, then later directional lights. Finally, the special case of shadow caster volumes for semi-transparent objects is discussed.

2.0 Point Light Sources