Clip shadow frustum to scene bounds

Question

I have a global light in my scene. It casts shadows using shadow mapping and has an associated camera (for rendering to the shadow map). I'm going to refer to it as my "shadow camera" from now on.

I need to find a way to place my shadow camera's near plane as close as possible to my scene's bounding box (clip it to the scene bounds).
I need to do this so the shadow casters are never clipped by the shadow camera's near plane (otherwise I'd get holes inside of shadows) and to make sure I don't accidentally cull any shadow casters behind the camera. This would also allow me to increase the shadow mapping precision, because it lets me move the near and far planes closer together.

Example 1 (possible to do using a simple plane check):

Example 2 (NOT possible to do using a simple plane check):

• The black box is the scene's AABB (but it would be nice if this would work for OBBs or other shapes too).
• The yellow arrow represents the light direction.
• The green box is the shadow camera's frustum without any modifications.
• The red box is my desired result.

At the moment I'm constructing the red box by projecting the black box onto the global light's direction vector and use the closest vertex's distance to compute the shadow camera's near plane. But this makes it impossible to get something as seen in the 2nd image. Instead the red box starts above the scene's AABB.
I have thought of using SAT for this, but it doesn't seem to be the solution.

Answer 1

This is how I'd do it:

1. Generate convex hull from all planes
   • Note: this includes both light frustum and scene AABB planes, so there should be a total of 12 planes
   • Note: make sure all planes have matching orientation (normal outwards or inwards - doesn't matter much but it has to be consistent across all data and functions)
   • Intersect every three planes (all possible combinations) to try and get an intersection point
     • One way: plane[1]/plane[2] -> ray; ray/plane[3] -> point
     • ...but you might be able to find better algorithms for this, for example...
       • I see here - https://stackoverflow.com/a/18092154/1648140 - that there's a solution for immediately intersecting all three planes and getting a point, you might be able to use that instead
   • Remove those generated points that are not in the hull (they're behind any of the planes)
2. Project hull on axes to generate OBB
   • this is just dot(point,axis) for a list of 6 axes (or if you need just the near plane, then 1 axis) and all hull points

Answer 2

Here's the approach I ended up implementing:

1. Generate the regular shadow camera frustum (the green box from my question) and only extract the four side planes (up, down, left, right). I only use the four side planes because I want to offset the near and far planes.
2. Convert the scene bounding volume into a triangle mesh (if it's an AABB => 12 triangles, but it works with any kind of mesh).
3. Iterate through all triangles and for each:
   • A: Iterate through all planes and for each:
     1. Check if the triangle and plane intersect. If they do, calculate the line segment on the triangle that is formed by the cut. If the triangle and plane don't intersect, continue with the next plane.
     2. Iterate through all the remaining planes (start with the first one again), but skip the plane that produced the triangle cut (because it's redundant and leads to numerical precision errors). Each additional line segment vs plane check will either:
        • shorten the line segment (the plane intersects the line segment, and we only care about the segment in front of the plane)
        • not do anything (the line segment is in front of the plane => contininue with the next plane)
        • discard the line segment (the line segment is completely behind the plane => go back to A and continue with the next plane).
     3. Now you have the shortest line segment. Use it to reposition the near and far planes (using the signed distance between the plane and the end points). I use two offsets (one for the near plane, one for the far plane) which are continuously updated using the shortest line segments. After the algorithm finished, I add the offsets to the near and far planes.

---

If you render all the line segments produced by the algorithm, you should end up with something like this (The green lines are the line segments created by the algorithm. The shadow map camera encompasses the main camera frustum and the four side planes pass through the green lines.):

There might be some possible optimizations and simplifications and I'd gladly hear about them.