# Clip shadow frustum to scene bounds

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.

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...
• 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
• To be sure: Your solution is to basically "carve out" a part of the scene AABB using the green box and then project the generated vertices onto the light vector to construct the red box? – Tara Jul 1 '15 at 16:32
• @Dudeson yes, that's about right – snake5 Jul 1 '15 at 18:37
• @snak5: I see. That's a good idea. I could simplify it by converting the scene AABB (or whatever shape) to a triangle mesh first and then do the cutting using the four frustum planes (up, down, left, right). I never did plane-plane intersections, but that sounds more complex to me (especially because I'd have to check if the resulting corner is inside the scene AABB). Cutting a triangle using a plane basically consists of just three interpolations. – Tara Jul 1 '15 at 19:57
• @Dudeson that might actually be more complex - triangle clipping may produce new triangles, so there have to be multiple variable-size buffers; and checking for points in plane hull is simple - for each plane, check if it's behind plane, if so - discard it -- and there is no additional checking necessary if you meant that, since this check would test for points being in both scene AABB and light frustum – snake5 Jul 2 '15 at 5:14
• Cutting a triangle ALWAYS results in three triangles (or two new vertices). You don't have to store them. That is unnecessary. Just iterate through the triangles, cut, and then use the signed distance of the new vertices to the near-plane to calculate the red box. But seems like I misread a step of your solution. Looks like it already takes care that the points are inside the scene AABB. – Tara Jul 2 '15 at 14:22

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.