The Blog

Tutorial: Tightly Culling Shadow Casters for Directional Lights (Part 2)

Continued…

In the previous tutorial we came to the conclusion that the below image highlights the planes we want to pull towards ourselves, assuming we are the light source.

Representing planes in 2D is not easy, but imagine each black line segment represents a plane that is coming from our eyes and is rotated along its respective line segment.  This is the tightest possible collection of planes that fully encloses the player’s view frustum, from the light’s point-of-view.  Also remember that the left, bottom, and far planes are on the opposite side of the frustum.  They form the back faces of the k-DOP we are trying to create.

On input, we have 8 points, representing the 8 corners of the frustum, and with this input our goal is to create all of the planes necessary to make the outline shown above, and at the same time make sure all of the planes are facing towards the inside of the volume.

 

Gathering the Corner Points

Our first goal is to get the 8 corner points.  A good idea is to name both the planes and the points, so we will start with the following enumerations.

	/** Frustum planes. */
	enum LSM_FRUSTUM_PLANES {
		LSM_FP_LEFT,
		LSM_FP_RIGHT,
		LSM_FP_TOP,
		LSM_FP_BOTTOM,
		LSM_FP_NEAR,
		LSM_FP_FAR,
		LSM_FP_TOTAL
	};

	/** Frustum points. */
	enum LSM_FRUSTUM_POINTS {
		LSM_FP_FAR_BOTTOM_LEFT,
		LSM_FP_FAR_TOP_LEFT,
		LSM_FP_FAR_TOP_RIGHT,
		LSM_FP_FAR_BOTTOM_RIGHT,
		LSM_FP_NEAR_BOTTOM_LEFT,
		LSM_FP_NEAR_TOP_LEFT,
		LSM_FP_NEAR_TOP_RIGHT,
		LSM_FP_NEAR_BOTTOM_RIGHT,
	};

When working with these points and planes here forth we will strictly adhere to this order.  Creating a specific order for the points is important for ensuring the planes we add to our final k-DOP will be pointing consistently inwards.

The 8 corner points, named via our enumeration. The red points form the outline we want to extract.

We can determine the locations of each point by intersecting the 3 planes that make that corner.  While this sounds difficult to do, it is in fact a very small and efficient function.

	/**
	 * Gets the intersection point of 3 planes if there is one.  If not, false is returned.
	 *
	 * \param _pP0 Plane 1.
	 * \param _pP1 Plane 2.
	 * \param _pP2 Plane 3.
	 * \param _vRet The returned intersection point, valid only if true is returned.
	 * \return Returns true if the 3 planes intersect at a single point.
	 */
	LSE_INLINE LSBOOL LSE_CALL CIntersect::ThreePlanes( const CPlane3 &_pP0, const CPlane3 &_pP1, const CPlane3 &_pP2, CVector3 &_vRet ) {
		CVector3 vU = _pP1.n % _pP2.n;
		LSREAL fDenom = _pP0.n * vU;
		if ( CMathLib::Abs( fDenom ) <= LSM_FLT_EPSILON ) { return false; }
		_vRet = (vU * _pP0.dist + _pP0.n.Cross( _pP1.n * _pP2.dist - _pP2.n * _pP1.dist )) / fDenom;
		return true;
	}

Note that the vector % operator is a cross product, and the vector * operator is a dot product, and LSM_FLT_EPSILON is defined as 1.192092896e-07f.

The next step is to use this to get the 8 corner points, which is straight-forward.

	/**
	 * Fills an array of 8 points with the corner points of a frustum.
	 *
	 * \param _fFrustum The frustum whose corners are to be extracted.
	 * \param _vRet The array of exactly 8 points into which the frustum corners are extracted.
	 */
	LSVOID LSE_CALL CPhysUtils::FrustumCorners( const CFrustum &_fFrustum, CVector3 _vRet[8] ) {
		CIntersect::ThreePlanes( _fFrustum[LSM_FP_FAR], _fFrustum[LSM_FP_BOTTOM], _fFrustum[LSM_FP_LEFT], _vRet[LSM_FP_FAR_BOTTOM_LEFT] );
		CIntersect::ThreePlanes( _fFrustum[LSM_FP_FAR], _fFrustum[LSM_FP_TOP], _fFrustum[LSM_FP_LEFT], _vRet[LSM_FP_FAR_TOP_LEFT] );
		CIntersect::ThreePlanes( _fFrustum[LSM_FP_FAR], _fFrustum[LSM_FP_TOP], _fFrustum[LSM_FP_RIGHT], _vRet[LSM_FP_FAR_TOP_RIGHT] );
		CIntersect::ThreePlanes( _fFrustum[LSM_FP_FAR], _fFrustum[LSM_FP_BOTTOM], _fFrustum[LSM_FP_RIGHT], _vRet[LSM_FP_FAR_BOTTOM_RIGHT] );

		// Again with the near plane.
		CIntersect::ThreePlanes( _fFrustum[LSM_FP_NEAR], _fFrustum[LSM_FP_BOTTOM], _fFrustum[LSM_FP_LEFT], _vRet[LSM_FP_NEAR_BOTTOM_LEFT] );
		CIntersect::ThreePlanes( _fFrustum[LSM_FP_NEAR], _fFrustum[LSM_FP_TOP], _fFrustum[LSM_FP_LEFT], _vRet[LSM_FP_NEAR_TOP_LEFT] );
		CIntersect::ThreePlanes( _fFrustum[LSM_FP_NEAR], _fFrustum[LSM_FP_TOP], _fFrustum[LSM_FP_RIGHT], _vRet[LSM_FP_NEAR_TOP_RIGHT] );
		CIntersect::ThreePlanes( _fFrustum[LSM_FP_NEAR], _fFrustum[LSM_FP_BOTTOM], _fFrustum[LSM_FP_RIGHT], _vRet[LSM_FP_NEAR_BOTTOM_RIGHT] );
	}

Here, a special class acts as a wrapper for a frustum, but it is still just 6 planes.  And we always access those planes via our enumerations above.  Our array of 8 vectors used to store the points is also always accessed via our enumerations.  We don’t check for a false return from the intersection function because if the frustum is not well formed, we have bigger problems on our hands than this.  If other parts of the engine are not breaking and we come to this point, we can assume the frustum is well formed and all 8 points are valid.

Finding the Outline and Putting it All Together

With the 8 corner points at our disposal, we need a way to determine which points outline the view frustum from the light’s point-of-view.  That is, which points were used to make the black outline in the first image above.  The best way to do that is to find neighboring planes such that one plane is facing towards the light and the other facing away from it.  In order to do this we need a table of neighboring planes.  On input, we provide the plane we want to examine, and on output the function gives us its 4 neighbors.

	/**
	 * Given a plane, the 4 neighbors of that plane are returned.
	 *
	 * \param _fpPlane The plane for which to locate neighbors.
	 * \param _fpRet Holds the returned neighbors.  Must be at least 4 elements in the array.
	 */
	LSVOID LSE_CALL CFrustum::GetNeighbors( LSM_FRUSTUM_PLANES _fpPlane, LSM_FRUSTUM_PLANES _fpRet[4] ) {
		static const LSM_FRUSTUM_PLANES fpTable[LSM_FP_TOTAL][4] = {
			{	// LSM_FP_LEFT
				LSM_FP_TOP,
				LSM_FP_BOTTOM,
				LSM_FP_NEAR,
				LSM_FP_FAR
			},
			{	// LSM_FP_RIGHT
				LSM_FP_TOP,
				LSM_FP_BOTTOM,
				LSM_FP_NEAR,
				LSM_FP_FAR
			},
			{	// LSM_FP_TOP
				LSM_FP_LEFT,
				LSM_FP_RIGHT,
				LSM_FP_NEAR,
				LSM_FP_FAR
			},
			{	// LSM_FP_BOTTOM
				LSM_FP_LEFT,
				LSM_FP_RIGHT,
				LSM_FP_NEAR,
				LSM_FP_FAR
			},
			{	// LSM_FP_NEAR
				LSM_FP_LEFT,
				LSM_FP_RIGHT,
				LSM_FP_TOP,
				LSM_FP_BOTTOM
			},
			{	// LSM_FP_FAR
				LSM_FP_LEFT,
				LSM_FP_RIGHT,
				LSM_FP_TOP,
				LSM_FP_BOTTOM
			},
		};

		for ( LSUINT32 I = 4UL; I--; ) {
			_fpRet[I] = fpTable[_fpPlane][I];
		}
	}

Nothing magic about this.  It is just a table.  If my for loop looks strange, it is because it is meant to be efficient.  It is always more efficient to count down towards 0 than to count up to a given number, as the compiler has countless ways to check against 0 in very few clock cycles.  But to be more efficient the loop could be unrolled.

Now we can loop over the 6 planes of a frustum and get the neighbors of that plane.

		// For each plane.
		for ( LSUINT32 I = LSM_FP_TOTAL; I--; ) {
			// If this plane is facing away from us, move on.
			LSREAL fDir = _fFrustum[I].n * vDir;
			if ( fDir > LSM_ZERO ) { continue; }
			// For each neighbor of this plane.
			LSM_FRUSTUM_PLANES fpNeighbors[4];
			CFrustum::GetNeighbors( static_cast<LSM_FRUSTUM_PLANES>(I), fpNeighbors );
			for ( LSUINT32 J = 4UL; J--; ) {
			}
		}

And as mentioned above, if one plane is facing towards us and its neighbor is facing away from us, we have found an edge.

		// For each plane.
		for ( LSUINT32 I = LSM_FP_TOTAL; I--; ) {
			// If this plane is facing away from us, move on.
			LSREAL fDir = _fFrustum[I].n * vDir;
			if ( fDir > LSM_ZERO ) { continue; }
			// For each neighbor of this plane.
			LSM_FRUSTUM_PLANES fpNeighbors[4];
			CFrustum::GetNeighbors( static_cast<LSM_FRUSTUM_PLANES>(I), fpNeighbors );
			for ( LSUINT32 J = 4UL; J--; ) {
				LSREAL fNeighborDir = _fFrustum[fpNeighbors[J]].n * vDir;
				// If this plane is facing away from us, the edge between plane I and plane J
				//	marks the edge of a plane we need to add.
				if ( fNeighborDir > LSM_ZERO ) {
					// These planes form an edge on the outline.  We need to find the two points that they share.
				}
			}
		}

Each plane in the frustum shares exactly 2 corner points with each of its neighbors.  We have found an edge between two planes that lies in the outline shown in the first image above, but what are the points that create that edge?  The easiest thing to do is to make another table.

On input, we are going to provide 2 planes, and on output we want the indices of the 2 corners those planes share.  As simple as a table such as this seems, there is an important note to be made.  We need the planes we are about to add to consistently face inwards.  In graphics programming, triangles on the outside of a mesh using a specific winding order in order to achieve this type of consistency.  Borrowing from the world of graphics programming, we will also specify our points in a very precise order which will allow us to create planes that face in the direction we desire.

We start with the declaration of our table.

		static const LSM_FRUSTUM_POINTS fpTable[LSM_FP_TOTAL][LSM_FP_TOTAL][2] = {

This declares a 3-dimensional array in which the first 2 dimensions are the two input planes, and the third are the 2 points shared by that plane.  In order to create the table, we must imagine we are looking directly at one plane and visualize from that perspective which 4 sides neighbor it.

Maintaining a counter-clockwise order, we add the points for each plane to the table.

			{	// LSM_FP_LEFT
				{	// LSM_FP_LEFT
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_FAR_BOTTOM_LEFT,		// Invalid combination.
				},
				{	// LSM_FP_RIGHT
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_FAR_BOTTOM_LEFT,		// Invalid combination.
				},
				{	// LSM_FP_TOP
					LSM_FP_NEAR_TOP_LEFT, LSM_FP_FAR_TOP_LEFT,
				},
				{	// LSM_FP_BOTTOM
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_NEAR_BOTTOM_LEFT,
				},
				{	// LSM_FP_NEAR
					LSM_FP_NEAR_BOTTOM_LEFT, LSM_FP_NEAR_TOP_LEFT,
				},
				{	// LSM_FP_FAR
					LSM_FP_FAR_TOP_LEFT, LSM_FP_FAR_BOTTOM_LEFT,
				},
			},

The left/left and left/right combinations are invalid.  The rest can be seen easily in the image above.  When we get to the left/top pair, we can look at the image and see that, going counter-clockwise, those planes share the near-top-left and far-top-left points.  Moving on to the right side, things are fairly simple.

The right side shares all of the same planes as the left side, but the winding is reversed.  The next entries in our table are easy to add.  Copy, replace LEFT with RIGHT, and reverse the order of each entry.

			{	// LSM_FP_RIGHT
				{	// LSM_FP_LEFT
					LSM_FP_FAR_BOTTOM_RIGHT, LSM_FP_FAR_BOTTOM_RIGHT,		// Invalid combination.
				},
				{	// LSM_FP_RIGHT
					LSM_FP_FAR_BOTTOM_RIGHT, LSM_FP_FAR_BOTTOM_RIGHT,		// Invalid combination.
				},
				{	// LSM_FP_TOP
					LSM_FP_FAR_TOP_RIGHT, LSM_FP_NEAR_TOP_RIGHT,
				},
				{	// LSM_FP_BOTTOM
					LSM_FP_NEAR_BOTTOM_RIGHT, LSM_FP_FAR_BOTTOM_RIGHT,
				},
				{	// LSM_FP_NEAR
					LSM_FP_NEAR_TOP_RIGHT, LSM_FP_NEAR_BOTTOM_RIGHT,
				},
				{	// LSM_FP_FAR
					LSM_FP_FAR_BOTTOM_RIGHT, LSM_FP_FAR_TOP_RIGHT,
				},
			},

Repeat this for every plane and the final table and function becomes this:

	/**
	 * Given two planes, returns the two points shared by those planes.  The points are always
	 *	returned in counter-clockwise order, assuming the first input plane is facing towards
	 *	the viewer.
	 *
	 * \param _fpPlane0 The plane facing towards the viewer.
	 * \param _fpPlane1 A plane neighboring _fpPlane0.
	 * \param _fpRet An array of exactly two elements to be filled with the indices of the points
	 *	on return.
	 */
	LSVOID LSE_CALL CFrustum::GetCornersOfPlanes( LSM_FRUSTUM_PLANES _fpPlane0, LSM_FRUSTUM_PLANES _fpPlane1,
		LSM_FRUSTUM_POINTS _fpRet[2] ) {
		static const LSM_FRUSTUM_POINTS fpTable[LSM_FP_TOTAL][LSM_FP_TOTAL][2] = {
			{	// LSM_FP_LEFT
				{	// LSM_FP_LEFT
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_FAR_BOTTOM_LEFT,		// Invalid combination.
				},
				{	// LSM_FP_RIGHT
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_FAR_BOTTOM_LEFT,		// Invalid combination.
				},
				{	// LSM_FP_TOP
					LSM_FP_NEAR_TOP_LEFT, LSM_FP_FAR_TOP_LEFT,
				},
				{	// LSM_FP_BOTTOM
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_NEAR_BOTTOM_LEFT,
				},
				{	// LSM_FP_NEAR
					LSM_FP_NEAR_BOTTOM_LEFT, LSM_FP_NEAR_TOP_LEFT,
				},
				{	// LSM_FP_FAR
					LSM_FP_FAR_TOP_LEFT, LSM_FP_FAR_BOTTOM_LEFT,
				},
			},
			{	// LSM_FP_RIGHT
				{	// LSM_FP_LEFT
					LSM_FP_FAR_BOTTOM_RIGHT, LSM_FP_FAR_BOTTOM_RIGHT,	// Invalid combination.
				},
				{	// LSM_FP_RIGHT
					LSM_FP_FAR_BOTTOM_RIGHT, LSM_FP_FAR_BOTTOM_RIGHT,	// Invalid combination.
				},
				{	// LSM_FP_TOP
					LSM_FP_FAR_TOP_RIGHT, LSM_FP_NEAR_TOP_RIGHT,
				},
				{	// LSM_FP_BOTTOM
					LSM_FP_NEAR_BOTTOM_RIGHT, LSM_FP_FAR_BOTTOM_RIGHT,
				},
				{	// LSM_FP_NEAR
					LSM_FP_NEAR_TOP_RIGHT, LSM_FP_NEAR_BOTTOM_RIGHT,
				},
				{	// LSM_FP_FAR
					LSM_FP_FAR_BOTTOM_RIGHT, LSM_FP_FAR_TOP_RIGHT,
				},
			},

			// ==

			{	// LSM_FP_TOP
				{	// LSM_FP_LEFT
					LSM_FP_FAR_TOP_LEFT, LSM_FP_NEAR_TOP_LEFT,
				},
				{	// LSM_FP_RIGHT
					LSM_FP_NEAR_TOP_RIGHT, LSM_FP_FAR_TOP_RIGHT,
				},
				{	// LSM_FP_TOP
					LSM_FP_NEAR_TOP_LEFT, LSM_FP_FAR_TOP_LEFT,		// Invalid combination.
				},
				{	// LSM_FP_BOTTOM
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_NEAR_BOTTOM_LEFT,	// Invalid combination.
				},
				{	// LSM_FP_NEAR
					LSM_FP_NEAR_TOP_LEFT, LSM_FP_NEAR_TOP_RIGHT,
				},
				{	// LSM_FP_FAR
					LSM_FP_FAR_TOP_RIGHT, LSM_FP_FAR_TOP_LEFT,
				},
			},
			{	// LSM_FP_BOTTOM
				{	// LSM_FP_LEFT
					LSM_FP_NEAR_BOTTOM_LEFT, LSM_FP_FAR_BOTTOM_LEFT,
				},
				{	// LSM_FP_RIGHT
					LSM_FP_FAR_BOTTOM_RIGHT, LSM_FP_NEAR_BOTTOM_RIGHT,
				},
				{	// LSM_FP_TOP
					LSM_FP_NEAR_BOTTOM_LEFT, LSM_FP_FAR_BOTTOM_LEFT,	// Invalid combination.
				},
				{	// LSM_FP_BOTTOM
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_NEAR_BOTTOM_LEFT,	// Invalid combination.
				},
				{	// LSM_FP_NEAR
					LSM_FP_NEAR_BOTTOM_RIGHT, LSM_FP_NEAR_BOTTOM_LEFT,
				},
				{	// LSM_FP_FAR
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_FAR_BOTTOM_RIGHT,
				},
			},

			// ==

			{	// LSM_FP_NEAR
				{	// LSM_FP_LEFT
					LSM_FP_NEAR_TOP_LEFT, LSM_FP_NEAR_BOTTOM_LEFT,
				},
				{	// LSM_FP_RIGHT
					LSM_FP_NEAR_BOTTOM_RIGHT, LSM_FP_NEAR_TOP_RIGHT,
				},
				{	// LSM_FP_TOP
					LSM_FP_NEAR_TOP_RIGHT, LSM_FP_NEAR_TOP_LEFT,
				},
				{	// LSM_FP_BOTTOM
					LSM_FP_NEAR_BOTTOM_LEFT, LSM_FP_NEAR_BOTTOM_RIGHT,
				},
				{	// LSM_FP_NEAR
					LSM_FP_NEAR_TOP_LEFT, LSM_FP_NEAR_TOP_RIGHT,		// Invalid combination.
				},
				{	// LSM_FP_FAR
					LSM_FP_FAR_TOP_RIGHT, LSM_FP_FAR_TOP_LEFT,		// Invalid combination.
				},
			},
			{	// LSM_FP_FAR
				{	// LSM_FP_LEFT
					LSM_FP_FAR_BOTTOM_LEFT, LSM_FP_FAR_TOP_LEFT,
				},
				{	// LSM_FP_RIGHT
					LSM_FP_FAR_TOP_RIGHT, LSM_FP_FAR_BOTTOM_RIGHT,
				},
				{	// LSM_FP_TOP
					LSM_FP_FAR_TOP_LEFT, LSM_FP_FAR_TOP_RIGHT,
				},
				{	// LSM_FP_BOTTOM
					LSM_FP_FAR_BOTTOM_RIGHT, LSM_FP_FAR_BOTTOM_LEFT,
				},
				{	// LSM_FP_NEAR
					LSM_FP_FAR_TOP_LEFT, LSM_FP_FAR_TOP_RIGHT,		// Invalid combination.
				},
				{	// LSM_FP_FAR
					LSM_FP_FAR_TOP_RIGHT, LSM_FP_FAR_TOP_LEFT,		// Invalid combination.
				},
			},
		};
		_fpRet[0] = fpTable[_fpPlane0][_fpPlane1][0];
		_fpRet[1] = fpTable[_fpPlane0][_fpPlane1][1];
	}

Now we have detected edges and we have a way to get the points that form that edge.

		// For each plane.
		for ( LSUINT32 I = LSM_FP_TOTAL; I--; ) {
			// If this plane is facing away from us, move on.
			LSREAL fDir = _fFrustum[I].n * vDir;
			if ( fDir > LSM_ZERO ) { continue; }
			// For each neighbor of this plane.
			LSM_FRUSTUM_PLANES fpNeighbors[4];
			CFrustum::GetNeighbors( static_cast<LSM_FRUSTUM_PLANES>(I), fpNeighbors );
			for ( LSUINT32 J = 4UL; J--; ) {
				LSREAL fNeighborDir = _fFrustum[fpNeighbors[J]].n * vDir;
				// If this plane is facing away from us, the edge between plane I and plane J
				//	marks the edge of a plane we need to add.
				if ( fNeighborDir > LSM_ZERO ) {
					LSM_FRUSTUM_POINTS fpPoints[2];
					CFrustum::GetCornersOfPlanes( static_cast<LSM_FRUSTUM_PLANES>(I), fpNeighbors[J], fpPoints );
				}
			}
		}

The main plane we are examining is the I plane.  The J planes are neighbors.  We pass the I plane first and the J plane second to maintain a winding consistent with what we designed in our above table.

If we have 3 points, we have all the information we need to form a plane.  Before we get our 3rd point, I will present the math for creating a plane from 3 points.

	LSE_INLINE LSE_CALLCTOR CPlane3::CPlane3( const CVector3 &_vPoint0, const CVector3 &_vPoint1, const CVector3 &_vPoint2 ) {
		n = CVector3::CrossProduct( _vPoint1 - _vPoint0, _vPoint2 - _vPoint0 );
		n.Normalize();
		dist = n.Dot( _vPoint0 );
	}

So the last step is to find a 3rd point, and luckily this is the easiest step of all.  Since we are a directional light, we have a vector that points directly away from us.  We can find our 3rd point simply by adding it to either of the first 2 points.

				if ( fNeighborDir > LSM_ZERO ) {
					LSM_FRUSTUM_POINTS fpPoints[2];
					CFrustum::GetCornersOfPlanes( static_cast<LSM_FRUSTUM_PLANES>(I), fpNeighbors[J], fpPoints );
					CPlane3 pAddMe( _vCorners[fpPoints[0]], _vCorners[fpPoints[1]], _vCorners[fpPoints[0]] + vDir );
					m_ckdKDop.AddPlane( pAddMe );
				}

The whole function, including the code to add the back planes of the frustum, follows.

	/**
	 * Createe the k-DOP for this directional light based on the corner points of a frustum.
	 *
	 * \param _fFrustum The frustum.
	 * \param _vCorners The 8 corner points of the frustum.
	 */
	LSVOID LSE_CALL CDirLight::MakeKDop( const CFrustum &_fFrustum, const CVector3 _vCorners[8] ) {
		m_ckdKDop.Reset();
		CVector3 vDir = GetDir();
		// Add planes that are facing towards us.
		for ( LSUINT32 I = LSM_FP_TOTAL; I--; ) {
			LSREAL fDir = _fFrustum[I].n * vDir;
			if ( fDir < LSM_ZERO ) {
				m_ckdKDop.AddPlane( _fFrustum[I] );
			}
		}
		// We have added the back sides of the planes.  Now find the edges.
		// For each plane.
		for ( LSUINT32 I = LSM_FP_TOTAL; I--; ) {
			// If this plane is facing away from us, move on.
			LSREAL fDir = _fFrustum[I].n * vDir;
			if ( fDir > LSM_ZERO ) { continue; }
			// For each neighbor of this plane.
			LSM_FRUSTUM_PLANES fpNeighbors[4];
			CFrustum::GetNeighbors( static_cast<LSM_FRUSTUM_PLANES>(I), fpNeighbors );
			for ( LSUINT32 J = 4UL; J--; ) {
				LSREAL fNeighborDir = _fFrustum[fpNeighbors[J]].n * vDir;
				// If this plane is facing away from us, the edge between plane I and plane J
				//	marks the edge of a plane we need to add.
				if ( fNeighborDir > LSM_ZERO ) {
					LSM_FRUSTUM_POINTS fpPoints[2];
					CFrustum::GetCornersOfPlanes( static_cast<LSM_FRUSTUM_PLANES>(I), fpNeighbors[J], fpPoints );
					CPlane3 pAddMe( _vCorners[fpPoints[0]], _vCorners[fpPoints[1]], _vCorners[fpPoints[0]] + vDir );
					m_ckdKDop.AddPlane( pAddMe );
				}
			}
		}
	}

Here, the directional light maintains its own k-DOP.  The routine begins by going over the 6 planes of the frustum and adding the back planes.  Then it goes through all of the planes facing towards us, and for each neighbor of those it seeks planes facing away from us.  When found, the 2 points shared by those faces are retrieved and plugged into the array of points that was passed to the function.  The only important member of the directional light here is its k-DOP.

		/**
		 * The k-DOP bounding volume for this light.
		 */
		CCappedKDop<13UL>		m_ckdKDop;

The maximum number of planes that can be generated by this algorithm is 11, but we use 13 because, in the future, we will want to add 2 fake planes (a discussion for another time).  Assume an orthogonal projection aligned perfectly along each of the world axis, and a light pointing directly towards it exactly along the X axis.  The only real back plane of the frustum is the one to the -X side, but due to floating-point errors it is conceivable that the +Y, -Y, +Z, and -Z planes may be redundantly added.  In general, the planes should pass either the back-side test or the edge test and not both, but a stable implementation must assume the worst can happen.  Note that if it does happen, it will not affect the stability of the culling test, only its efficiency.

If you find your edge planes pointing in the wrong direction, use – vDir instead of + vDir for the 3rd point.

 

Closing

The k-DOP we have created can be fed into the same function I presented for culling objects from the frustum and can be used to determine the bare minimum of objects that may cast visible shadows.  This routine can also be extended to create occlusion boxes for AABB’s and even OBB’s.  If you define an occluder with either of these, the same edge detection and k-DOP construction can be used to form a type of k-DOP that is used to exclude objects from a cull (here, we keep objects that are fully or partially inside the k-DOP, whereas with occlusion culling we reject objects that are fully inside the k-DOP).

An astute reader may have noticed that we never closed the k-DOP.  From our point of view as the light, we never added a near plane.  This basically allows the k-DOP to extend infinitely towards us from the view frustum.  If you don’t want objects to cast shadows from 10 miles away, you can add a near plane whose normal is the same as the directional light’s direction, and whose distance is ((PlayerPos DOT LightDir) – SomeDistance).  If your plane distances are not negated, you will need to negate this value to get the actual plane distance.

Creating an air-tight k-DOP around a view frustum is not such a difficult task conceptually, and its implementation is efficient.  I hope this guide can help those who have either not yet implemented shadows or have implemented directional-light shadows but without an air-tight k-DOP.

 

 

L. Spiro

About L. Spiro

L. Spiro is a professional actor, programmer, and artist, with a bit of dabbling in music. || [Senior Core Tech Engineer]/[Motion Capture] at Deep Silver Dambuster Studios on: * Homefront: The Revolution * UNANNOUNCED || [Senior Graphics Programmer]/[Motion Capture] at Square Enix on: * Luminous Studio engine * Final Fantasy XV || [R&D Programmer] at tri-Ace on: * Phantasy Star Nova * Star Ocean: Integrity and Faithlessness * Silent Scope: Bone Eater * Danball Senki W || [Programmer] on: * Leisure Suit Larry: Beach Volley * Ghost Recon 2 Online * HOT PXL * 187 Ride or Die * Ready Steady Cook * Tennis Elbow || L. Spiro is currently a GPU performance engineer at Apple Inc. || Hyper-realism (pencil & paper): https://www.deviantart.com/l-spiro/gallery/4844241/Realism || Music (live-played classical piano, remixes, and original compositions): https://soundcloud.com/l-spiro/

21 Awesome Comments So Far

Don't be a stranger, join the discussion by leaving your own comment
  1. belfegor
    December 16, 2012 at 6:28 AM #

    Just to say thank you very much.

    I got this working “somewhat”, but i think i made a mistake somewhere, because when i display count of objects rendered seen by “sun” light and by “player” camera there is huge difference then i expected, but it is still better then to render everything from “sun” point of view. Shadow maps are rendered correctly (i think) because there is no sudden and unexpected disappearance when i “walk” thru scene.

    I needed to negate -vDir as you mentioned:
    CPlane3 pAddMe( _vCorners[fpPoints[0]], _vCorners[fpPoints[1]], _vCorners[fpPoints[0]] – vDir );

    I failed to use your Clasify::AABox & CTest::AabbKDop functions properly as those didn’t work for me somehow, but instead i used functions from other tutorial on the net i have found earlier:
    http://pastebin.com/Xg7zXuVV
    and everything else is the same.

    If you find time could you possibly edit “CascadedShadowMaps11″ sample from DX SDK and add this culling technique?

    Thanks again.

    • L. Spiro
      December 19, 2012 at 8:18 AM #

      If you had to invert vDir then either your winding is in reverse order or your planes are stored in reverse. So to get the culling test to work, inside CClassify::Aabb(), try adding _pPlane.dist instead of subtracting it.
      I might look into modifying the DirectX samples in the future.

      L. Spiro

  2. chenQuan
    January 13, 2013 at 3:41 PM #

    I think your method is very efficient way to find out the point inside three plane , but I don’t really understand this line of code “_vRet = (vU * _pP0.dist + _pP0.n.Cross( _pP1.n * _pP2.dist – _pP2.n * _pP1.dist )) / fDenom;” Would you please explain the math behind this code ?

    • L. Spiro
      January 14, 2013 at 1:50 AM #

      That is quite a long line of math and a lot happening there. Is there a specific part of it that you don’t understand? You will also be able to find more through Google than I could tell you. The search terms would be “Intersection point of Bundle of Planes”.

      L. Spiro

      • chenQuan
        January 15, 2013 at 11:42 AM #

        that is my first time leaving a comment to an English blog,it looks not bad at least you understood what I said.I found the answer in today.Thank you :-)

        • chenQuan
          January 15, 2013 at 11:48 AM #

          in “real time collision detection” the book name between Book bracket disapeard ~

  3. belfegor
    January 24, 2013 at 7:16 AM #

    Actually this works great for me now. This time i have created k-dop for each split in “cascades”, previously i was creating just one from “whole” cam frustum witch was wrong.

    Again, thank you very much.

  4. belfegor
    May 13, 2013 at 6:05 AM #

    I got question about creating plane from 3 points, last line you say:
    dist = n.Dot( _vPoint0 );

    In some implementations i have seen that it is:
    dist = -n.Dot( _vPoint0 );

    Did you made a typo or it should be like that?

    • L. Spiro
      May 13, 2013 at 7:52 AM #

      As I mentioned in the post some implementations use the reversed distance because it makes certain equations slightly faster, since many planar equations require the reversed distance over the actual distance.
      You have to pick one convention or the other and be sure to be consistent. The code I posted is consistent within its convention, but if you get your planar equations from multiple sources you have to be careful about which convention they are using.

      L. Spiro

  5. belfegor
    May 13, 2013 at 8:51 PM #

    I am trying to figure out why do i had to subtract instead add light direction like in this tutorial:
    //CPlane3 pAddMe( _vCorners[fpPoints[0]], _vCorners[fpPoints[1]], _vCorners[fpPoints[0]] + vDir );
    CPlane3 pAddMe( _vCorners[fpPoints[0]], _vCorners[fpPoints[1]], _vCorners[fpPoints[0]] – vDir );

    And few more stupid question if you don’t mind.
    1.
    CVector3 vDir = GetDir(); // direction of light
    Is it to light, or to light target?
    lightPos – lightTarget
    lightTarget – lightPos

    2.
    I see in some functions you use Dot product function,
    like this: dist = n.Dot( _vPoint0 );
    but somewhere: LSREAL fDir = _fFrustum[I].n * vDir;
    Since it returns Real i assume it is same as dot? Is it?

    Thank you for your help so far.

    • L. Spiro
      May 14, 2013 at 1:32 AM #

      For #1, lights don’t have target positions. At a high level you could lock them to point at certain things, but at a normal level they just have directions, and these are the directions they actually face, not inversed. Again using the inverse direction is a popular choice since it simplifies some equations but here it is not.

      #2: I have some old code in which I used CVector3::Dot(), but it is all being ported to use the * operator. They are the same.

      L. Spiro

      • M. Coder
        May 20, 2014 at 6:24 PM #

        Great article overall, and very useful but I’d like to shine a light ;) on a few things, just for posterity.

        - It’s a bad idea to use CVector3::operator*(const CVector3&) for a dot product. It is ambiguous to read and generally that operator should be used for a component wise multiply. Same with operator % for cross product in which the notation just doesn’t make sense. I used to do these kinds of things many years ago and ended up regretting it. I find v1.dot(v2) style notation best for math library calls.

        - I know it’s a point of choice and has been pointed out a few times in prior comments&answers but a plane equation, mathematically speaking, really should be in the form Ax+By+Cz+D = 0. Changing it around to hope for a compiler optimisation is breaking the rules and probably wont yield any performance benefit, and can (and does) cascade issues into other math/classes expecting the “correct” way and thus not playing nice.

        Picky I know, but I think these points are worth noting.
        Regardless it’s a fantastic article, very well written and understandable. I’m sure it’s helped heaps of people.

  6. belfegor
    May 13, 2013 at 9:08 PM #

    I am really sorry to bother you again with noobish questions, i forgat about one more. If i want to know relation with point against this plane created this way, how do i calculate it?

    I’ve seen implementation like this when distance is -dot(point, normal):
    relation = plane.normal.dot(point) + plane.distance;

    Thank you.

    • L. Spiro
      May 14, 2013 at 1:27 AM #

      The way my planes are stored, the equation is:
      /**
      * Gets the distance from this plane to a point. This plane must be normalized.
      *
      * \param _vPoint Point from which to get the distance to this plane.
      * \return Returns the distance from the point to this plane, signed.
      */
      LSE_INLINE _tType LSE_FCALL SignedDistance( const _tVec3Type &_vPoint ) const {
      return n.Dot( _vPoint ) – dist;
      }

      L. Spiro

  7. belfegor
    May 14, 2013 at 1:53 AM #

    Thank you very much for patience and answers.

  8. Louise
    November 27, 2013 at 7:10 PM #

    Hi

    Fine tutorial, i’v added this to my engine, but it’s (not a suprise)
    not working. My coords system is RightHanded, Y-Up.
    The problem is probably with frustum, my frustum planes are defived from CameraProjectionMatrix (comboMatrix) as follows:

    // matrix is realy XMFLOAT4X4 (row-major order)

    // Left clipping plane
    m_pPlanes[LSM_FP_LEFT] = CSPlane(comboMatrix._14 + comboMatrix._11, comboMatrix._24 + comboMatrix._21, comboMatrix._34 + comboMatrix._31, -(comboMatrix._44 + comboMatrix._41));
    // Right clipping plane
    m_pPlanes[LSM_FP_RIGHT] = CSPlane(comboMatrix._14 – comboMatrix._11, comboMatrix._24 – comboMatrix._21, comboMatrix._34 – comboMatrix._31, -(comboMatrix._44 – comboMatrix._41));
    // Top clipping plane
    m_pPlanes[LSM_FP_TOP] = CSPlane(comboMatrix._14 – comboMatrix._12, comboMatrix._24 – comboMatrix._22, comboMatrix._34 – comboMatrix._32, -(comboMatrix._44 – comboMatrix._42));
    // Bottom clipping plane
    m_pPlanes[LSM_FP_BOTTOM] = CSPlane(comboMatrix._14 + comboMatrix._12, comboMatrix._24 + comboMatrix._22, comboMatrix._34 + comboMatrix._32, -(comboMatrix._44 + comboMatrix._42));
    // Near clipping plane
    m_pPlanes[LSM_FP_NEAR] = CSPlane(comboMatrix._13, comboMatrix._23, comboMatrix._33, -comboMatrix._43);
    // Far clipping plane
    m_pPlanes[LSM_FP_FAR] = CSlane(comboMatrix._14 – comboMatrix._13, comboMatrix._24 – comboMatrix._23, comboMatrix._34 – comboMatrix._33, -(comboMatrix._44 – comboMatrix._43));

    the – at the ‘d’ component of plane is here to store positive distance (that you also use) not the -d
    if i draw the frustum by taking for each plane an enormously big quad and clipping it to 5 remaining planes looks just fine – so the frustum itself should be fine i think.

    but then when i dra the points calculated by CIntersect::ThreePlanes fro your sample, they do not go into corners of frustum, instead they are scattered all over in space.
    http://imageshack.com/a/img812/1641/zpej.jpg (the image is taken by ‘external debuging camera’, the real camera frustum is where it is imaged)

    green stars are the calculated frustum corners.

    If i replace those calculated by CIntersect::ThreePlanes with my own ones that lies where I thing they should be (at the corners of the white frustum outline)
    the algorithm works but only when my camera direction is mainly that same as the light direction (+/- about 30 degrees)

    if that magic barrier is crossed the second part of CDirLight::MakeKDop get screved (the one with edges) and I end up with KDop that have so weird planes orientation that it encloses nothing ;(

    my light direction is fine (assuming the light is from top of the sky it would be (0, -1, 0))

    any ideas what may be wrong ?
    do the corners calculated by CIntersect::ThreePlanes should lie exacly where the frustum corners are ?
    (if so, i have idea that the order of frustum planes is wrong for me) or they are free to go as in the image ?

    Thanks for any ideas where to check.

    • L. Spiro
      November 29, 2013 at 11:13 PM #

      Sorry, this was marked as spam so I did not see it until now. But glad you could solve the problem.

      L. Spiro

  9. Louise
    November 27, 2013 at 11:48 PM #

    Ok :) I’ managed to get it working:
    all I need was to swap places of LEFT and RIGHT planes in my frustum planes calculations AND
    provide new version of IntersectThreePlanes function

    Quick replacement using DXMath:

    static bool IntersectThreePlanes(const CSPlane &_pP0, const CSPlane &_pP1, const CSPlane &_pP2, XMFLOAT4 &_vRet)
    {

    XMVECTOR PNS = XMVectorSet(1.0f, 1.0f, 1.0f, -1.0f);
    XMVECTOR LNP0 = XMVectorZero();
    XMVECTOR LNP1 = XMVectorZero();
    XMVECTOR P0 = XMVectorMultiply(XMLoadFloat4(&_pP0.n), PNS);
    XMVECTOR P1 = XMVectorMultiply(XMLoadFloat4(&_pP1.n), PNS);
    XMVECTOR P2 = XMVectorMultiply(XMLoadFloat4(&_pP2.n), PNS);

    XMPlaneIntersectPlane(&LNP0, &LNP1, P0, P1);

    XMVECTOR Res = XMPlaneIntersectLine(P2, LNP0, LNP1);

    XMStoreFloat4(&_vRet, Res);

    return true;
    }

  10. Fabian
    August 26, 2014 at 11:57 PM #

    Is there a way of creating the new planes without regard to the winding? Atm I’m just finding 2 points the two planes share, and ignore those planes which have one / non point in common. I tried inverting the Normal of the new plane if LightDir.Dot(Plane.Normal) < 0.f but that doesn't work either. I dont want to copy your GetCornersOfPlanes table because I have a different enumeration for the planes. Is it really necessary to your fake points like: LSM_FP_FAR_BOTTOM_RIGHT, LSM_FP_FAR_BOTTOM_RIGHT, // Invalid combination. ?

    Thanks for your help!

    • L. Spiro
      August 27, 2014 at 9:32 PM #

      Deterministic winding is the best way, but you should be able to reverse normals on generated planes based on the relation to the direction of the light, yes.

      Invalid combinations are never accessed and can be any values. I put “accurate” values there because there is no reason to choose any other set of values, but you need placeholders there to fill in the table.

  11. Michael
    May 17, 2015 at 11:22 AM #

    Hi
    Great article, I have learned a lot reading this and I am quite new to the subject.

    I have a question regarding finding the 8 corner points of the frustum.
    If V is the view matrix and P the projection matrix. Then am I right that the 8 corners of the frustum multiplied by the VP matrix form a cube of dimensions of width, height and depth 2 centered on the origin (x =[-1 1], y=[-1 1] and z = [-1 1])?
    If that was correct could one not use the inverse VP matrix and transform the known corner points [-1 -1 -1],[-1 -1 1],… back to get the frustum points in world space?
    I might be completely wrong here, but if not, would that me more efficient?

    Thanks a lot for any help
    Michael

Leave a Comment to L. Spiro

Remember to play nicely folks, nobody likes a troll.