/999 /Mail /How to
Screen coverage of a 3D scene's shadow can be calculated by enclosing the shaded region in a special volume mesh and then rasterizing this mesh in a certain way to a dedicated stencil buffer. After all the volume meshes in the scene have been calculated and rendered, the stencil buffer contains certain values wherever a light affects or does not affect a pixel. The creation of this volume mesh involves finding certain edges between triangles in the source mesh, extruding these edges away from the light source towards infinity, and creating quadrilaterals between these edges and their extruded counterparts. Depending on the rasterization technique used, additional so-called 'cap' geometry, which is constructed by selecting certain input triangles and their extruded versions, is also required.
The classical method for constructing shadow volume meshes is to try to figure out which edges form the so-called 'silhouette' that separates the surfaces of the source mesh that face the light and those that face away from it and then extrude those edges. An extensive description of this technique can be read here (link goes to gamasutra.com). One issue with this approach is that only a certain class of meshes (those where every edge is shared by exactly two triangles) may cast shadows or else visual artifacts will appear.
(The teapot model contains some edges that have only one triangle neighbor. The classical technique only works for edges with two neighbor triangles.)
Another technique that always produces correct results exists, though: simply extrude and render every edge in the source mesh. The major downside of this (possibly among other things) is that fillrate and performance requirements can increase extremely.
It may become apparent that not every edge needs to be extruded: some neighboring edges should cancel each other out. For this, we keep track of how often each edge is visited, as if it were rendered -- each time an edge is visited, an associated edge render count (a signed integer) is updated. After considering every edge of every triangle, we know exactly how often each edge needs to be extruded/drawn, likely not at all. Additionally, this technique also handles other edge topologies, like many triangles sharing a single edge, nicely.
A description of this algorithm is as follows:
N1The integer can be of very limited range: only the
range of all the edges that meet needs to be stored here. An 8-bit
quantity should be more than enough. For input meshes where every
edge neighbors exactly two triangles, only 1 bit should suffice.
N2Orientation is in this case defined as the dot product between the triangle's plane equation and the light's position. The algorithm only supports casting shadows from triangles that either face the light or face away from it but not both at the same time, hence only mostly robust volumes.
N3Care should be taken of the winding of these triangles and quadrilaterals: they need to always either point inside or outside of the shadow volume. N4This is the slowest part of the algorithm. Luckily, the edges and their associated vertices in the input mesh can be precomputed.
(Most artifacts are gone but surfaces that do not face the light source still do not cast a shadow.)