2.2 Calculating the New Shadow Caster Volume Planes

Now that we have the points of intersection of the planes, we need to test if they are near the polyhedron, and are therefore vertices of the polyhedron. To check if a point lies in or on the polyhedron, we find the distance from each plane to the point. We say the point lies in or on the polyhedron if every distance is greater than some very small negative value. Note that in Listing 2, this “small negative value” is not a constant, but proportional to the plane's distance from the origin. This is because of the cancellation that occurs when subtracting two floating point numbers that are similar in value [GOLD91] .

From the vertices, we need to determine the edges of the polyhedron, where an edge is simply a pair of vertices. To do this, we loop through each pair of vertices, and if the vertices share two common planes, then we output an edge. Notice that this requires us to store the plane indices with each calculated vertex.

Now that we have a method for finding the edges of a polyhedron, we return to the problem of constructing the new planes needed for the shadow caster volume.

Given three distinct points we can construct a plane as follows. First we need to calculate the plane's normal. For this we use a cross product, but to get the direction correct, we need to impose a winding order on the points. For a clockwise winding order of points P₁, P₂ and P₃, the normal can be calculated as follows,

Now we have reduced the problem to calculating the plane given the normal N and a point P on the plane. So we need to calculate D, the distance to the origin.

Let Q be the point on the plane closest to the origin, so

And since Q lies on the plane,

Substituting for Q ,

So given three distinct points with clockwise winding order, the plane they form is

To form a new shadow caster volume plane, we have three points, the two silhouette edge endpoints, and the point light source's location, but we do not have a defined winding order. So to calculate the plane, we use the above method for three points, then flip the direction of the normal if necessary. We use a point known to be within the frustum to test if the normal needs to be flipped. If the signed distance from the plane to the point is negative, then the normal is pointing in the wrong direction. A simple way to get a point known to be inside the frustum, is to take the average of all the frustum's vertices.

3.0 Directional Light Sources