Projective Shadow Mapping
June 30, 2000
cbloom@cbloom.com

--------------------------------------------------------

This is quite an old trick, but it seems most people do it wrong, and
there're no good tutorials on how to do it right on the web.  I'm going
to start off by assuming that you have a 3d engine which uses vertex
buffers and is fully T&L compliant, and pushed about 50k triangles per
frame (if not, then stop reading this and get to work!!).

So first, a quicky on the basic idea of projective shadow mapping, as
described in Watt & Watt and elsewhere. The idea is that you render an
object (the shadow-caster) from the view of the light source (looking at
that object), into a white texture, with the object colored black.
Imagine a piece of tracing paper held between the light source and the
object; you've just darkened in the spots where you can see the object
from the light source. Then, for all the objects that are behind the
shadow-caster (the shadow-receivers), you put your black & white texture
on the shadow-receivers using UV's generated by projecting from the
"tracing paper" (like a movie projector; imagine the light going through
the tracing paper). You should use grays instead of black for non-opaque
shadows.

So, how do we do this fast on modern hardware?  The keys are to use
optimized vertex buffers, do NOTHING per-poly or per-vertex on the CPU,
and to only touch each object to be rendered once per frame.

The first step is to generate the shadow maps. You do this at the
beginning of your render loop for any shadow-caster which is "near" the
view frustum. You do this by using SetRenderTarget to a texture,
clearing it to white, and then rendering the shadow-caster object into
the texture in black. If your hardware is less than a geForce, then you
should just use a low resolution texture and write your own software
rasterizer to generate the shadow map (this avoids the SetRenderTarget
stall). You only need to re-generate the shadow maps when the light
source or the shadow-caster changes, eg. rarely.

The next bit is to cast these shadow maps onto all the shadow receivers.
To do this, each shadow-caster computes a frustum which is bounded by
the shadow map virtual image plane (the tracing paper) and terminates at
the light source (this frustum corresponds to the view matrix used to
render the object into the shadow map). So, when you render each object,
you simply test its AABB (axial-aligned bounding box) against all the
frusta of the active shadow casters. If you like, you could use some
heirarchical technique to speed this up further.

Now we need to get the shadow maps on the shadow-receivers. We do this
with texgen. We first fire the object's VB with normal texturing. Then
for each shadow map, we set the shadow map as the active texture, and
fire the VB with projective texture coordinates (texgen) using the view
matrix of the light, using the multiplicative raster combiner to darken
the areas in shadow. Note that the polygons are NOT clipped to the
shadow frusta. Instead, the texture UV's are clamped, and we make sure
that the edges of the shadow map are white (eg. no-ops). If you want to
run even a bit better, you can use single-pass multi-stage to do normal
texturing + several shadows in one pass.

The result is that verts are only transformed and lit once, and sent to
the hardware once. The hardware does all the shadow projective mapping
for you. The CPU work is only in setting up the shadow maps, eg. almost
none.

If you are doing your own transform & lighting, you can still make just
one pass over the verts.  You walk your verts list, do skinning, T&L,
and projective texture uv-mapping, then fire the transformed list.  This
minimizes memory touches and is best for cache coherency.  Note that if
you do any one of these things (eg. skinning or uv-mapping) in software,
you might as well do them all, since you're already touching the memory,
which is the worst part.

Obvious enhancements :

1. blur the shadow using hardware tricks (either rendering it to itself
   at an offset so the bilerping will get you, or letting hardware generate
   mipmaps)

2. fading out the shadow based on distance from the light source (this one is
   perhaps not possible without vertex shaders, or is pretty difficult anyway;
   I want to get the alpha of the shadowing pass from a texture lookup from
   the distance to the light).

3. you should be using VIPM for your objects, so when you render them into
   the shadow map, you can automagically use a lower-poly version (eg. exactly
   the right number of polys to give you pixel-perfect rendering in the
   lower-resolution shadow map texture (such as 128x128)).