2.0 Point Light Sources

For the purpose of this article, we will assume that the frustum is stored as a set of planes. Where the frustum volume is the intersection of the plane's positive half spaces. This means that each plane's normal points inwards as shown below.

Diagram 4: View frustum plane normals point inwards

For a point light source, when the light lies within the frustum, the shadow caster volume is the same as the frustum.

When the light lies outside of the frustum, the frustum must be extended to include the light. We create a new polyhedron, using all the frustum planes that the light source lies on the positive side of, and creating new planes for each edge that is shared by one plane that points towards the light and one that points away.

Diagram 5: Shadow volume planes. Unused frustum planes also shown in light red.

But the devil is in the details. Firstly we need to be able to calculate the edges of the frustum, then we need to ensure the normals of the new planes point inwards, not outwards.

If we know that the view frustum is always a simple six plane pyramidal frustum, then we can use the known view space edges, and transform them into world space. But to handle more general cases (such as the frustums formed by portal clipping, or the bounding volumes of semi-transparent objects discussed below) we treat the frustum as a convex polyhedron.

To find the edges of a convex polyhedron, we first need to find the vertices of the polyhedron. Finding the vertices involves checking all three plane combinations to see if they intersect at a point, then checking that the point is on the polyhedron's surface. We define a plane P as a unit length normal vector N and a scalar distance D to the origin.

D is the signed distance from the plane to the origin in the direction of N .

The signed distance from a plane P to a point Q in the direction of N is,

A point Q lies on a plane if Q · N + D = 0. So to find the intersection of three planes, we need to solve a system of three linear equations,

In matrix form,

There is not necessarily a solution to this system of equations, and neither is there necessarily only one solution if they are solvable. But we are only interested in the case of three planes intersecting at a single point, and this corresponds to the case where there is a single solution to the system of equations.

The method that most people are probably familiar with for solving such a system of equations, is to multiply both sides by the matrix inverse like so,

While mathematically correct for real numbers, this unfortunately gives inaccurate results when using floating point numbers. If we do not solve this system of equations accurately, then for a valid polyhedron vertex, we are liable to discard it as may end up on the negative side of a plane. A much better way to solve the equations is LUP decomposition (also known as LU decomposition) [CLRS01] , [PTVF88].

2.1 LUP Decomposition