0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Disclosure: Although a lot of research has been done on the subject within the computer graphics and gaming community, it is, in fact, a computational geometry question, so I also cross-posted this question here. \$\endgroup\$ – Adi Shavit Sep 3 '15 at 12:49
  • \$\begingroup\$ if the geometry doesn't change then it only needs to be done once \$\endgroup\$ – ratchet freak Sep 3 '15 at 14:16
  • \$\begingroup\$ @ratchetfreak: indeed. My meshes are actually very complex and high poly. \$\endgroup\$ – Adi Shavit Sep 3 '15 at 17:38
  • \$\begingroup\$ You need to look at this gpu gems article. You basically use triangle adjacency data to extrude shadow volumes. \$\endgroup\$ – Soapy Sep 4 '15 at 10:47
  • \$\begingroup\$ @Soapy: the article talks about rendering shadows, e.g. using the resolution and view dependent stencil buffer. This means that the results are rasterized so that small regions might be missed. I am looking for an exact solution. \$\endgroup\$ – Adi Shavit Sep 4 '15 at 13:53
1
\$\begingroup\$

(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).

enter image description here

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.

\$\endgroup\$
  • \$\begingroup\$ If you could add a description of what this does actually it would be very helpful :-). If I understand it correctly, the approach basically does the triangle extrusion if the triangle is facing towards the light source (in the vertex shader). Is this correct? If so, then I see the following issues that may be problematic: (1) The result might contain self intersections of the "prisms"; (2) A post-processing step is needed to remove any of the remaining non-extruded degenerate quads of step 4 and reconnect the triangles. \$\endgroup\$ – Adi Shavit Sep 6 '15 at 6:17
  • \$\begingroup\$ If this is for game-engine use you do not need to eliminate degenerate quads, the GPU will do that for you. If it is for calculating if an object is in-or-out shadow ray-casting might be better. Otherwise this may be not game-related and the question may be off-topic. What is the actual purpose of this shadow volume? \$\endgroup\$ – Stephane Hockenhull Sep 8 '15 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.