Generate Mesh of Shadow Volume

Question

Given a mesh, I want to generate another mesh that is effectively a shadow volume of this mesh.

I am looking for an algorithm/solution/implementation/reference that can do this under the following constraints:

1. I have a single, point light source. Thus:
   • Not a polygon;
   • I want hard edges/faces (not soft shadows)
2. The light source is at infinity, in fact can be assumed to by directly above the mesh. Thus:
   • The projection is actually orthographic and depends only on a single direction.
3. I want an exact solution.
   • The result mesh is not used for display so cannot be based on resolution dependent rasterization as many algorithms are.

A naive algorithm is to extrude all mesh triangles in the direction away from the light, e.g. downward, and do a CSG union of all these extruded "prisms".
The drawback here is that:

1. It does this for all triangles and not just the visible ones (how to do exact visibility?);
2. it requires a massive amount of CSG operations which are expensive.

I'm looking for a more efficient algorithm.

Answer 1

(Geometry shader option at the end. General concept stays the same. Not all platforms support geometry shaders yet and the vertex shader option might still be faster on some systems)

Mesh pre-processing:

1. Copy the original mesh.
2. Break/Split each vertex to be unique per poly.
3. Set each vertex normals to the polygon's normal (making the mesh flat-shaded).
4. insert collapsed quads (2 triangles, shown as the green line) inside every edges between the original triangles reusing each triangle's vertices (quick if the mesh is indexed, just add to the index array).

The normals on each side of the quad "edge" must match the triangle on each side (see the yellow normals in the picture).

Then, in the vertex shader (pseudo code, assuming all coordinates are in world space):

if (dot(light_normal, in.normal) <= 0){
    out.position = in.position;
} else {
    out.position = in.position + light_normal * volumetric_shadow_distance;
}

or the 1-line version (that may or may not be faster depending on GPU/drivers):

out.position = in.position + (light_normal * volumetric_shadow_distance) * max(0, sign(dot(light_normal, in.normal)));

This is for a directional light. For point & spot lights light_normal = normal(in.position - light_position)

This will expand the shadow mesh away from your light source. It only requires vertex shader support.

If you have geometry shader support you can generate the edge quad geometry on the fly (skip step 4 above) by adding only 1 triangle per edge per source triangle in the geometry shader. The other source triangles will add the 2nd half of the quad for every edge (as long as they are oriented the same way: all CW or all CCW). You don't need full adjacency data, only the normal of the neighbor triangle for that edge's half-quad which you can put in the regular vertex data as a 2nd normal, a custom attribute, or stash it in the tangent, color, or 3D uv depending on the engine you use. Just make sure the 2 normals matches exactly (loses the same amount of precision) or you'll have visual glitches when only one half of the quad edge expands.