Computing frustum planes.

Computing the planes for the viewing frustum in any space can be easily done by taking advantage of clip space.

Clip space:

Clip space (or projection space) is a post-projection space that represents the viewable area of a scene. In clip space the corners of the view frustum map to the corners of a cube that spans [-1, 1] on the x and y axes, and [0, 1] on the z axis, as you can see on this image shamelessly stolen from the MSDN:

Basically this means that in clip space, there is a well defined frustum volume that is no more than a cube who’s plane normals are the following:

// the normal are defined to be pointing inside the volume.
near plane:	[0, 0, 1]
far plane:	[0, 0, -1]
left plane:	[1, 0, 0]
right plane:	[-1, 0, 0]
top plane:	[0, -1, 0]
bottom plane:	[0, 1, 0]

We now have our viewing frustum in clip space.

Points in 3D:

You may need to perform frustum culling in view or world space. Observing how a point gets transformed from one space to another, to end up in clip space will give us an intuition on how to transform the clip space planes to any other space.

Let’s take a random point Q in 3D space, such that Q = (x, y, z), a view matrix M and a projection matrix P. If we transform this point by the view matrix, we get the point Q’ in view space, and if we then transform Q’ by the projection matrix, we get the point Q” in clip space.
We know from trivial matrix maths, that matrices have the associative property under multiplication, so the following is true:

(QV)P = Q(VP)

Transforming Q by the concatenated view-projection matrix will give us the point Q’ in clip space.

Now, to go from the point Q in clip space to Q’ in view space, we need to transform it by the inverse of the projection matrix, and to go from there to world space, we need to transform Q’ by the inverse of the view matrix. Given associative property under multiplication, to go from Q in clip space to Q’ in world space we can transform the point Q by the inverse of the view-projection matrix:

(Q(V–¹))(P-¹) = Q((VP)–¹)

Transforming the planes:

The same rules can be applied to the planes from the clip space viewing frustum. There is one little difference. According to the rules of transformation of normal vectors we must transform the normal vector by the inverse-transpose of the matrix.

Let’s say we want to find the planes in world space. We know that to transform a point from clip space to world space, we transform it by the inverse of the view-projection matrix. According to what was said above, to go from a normal vector in clip space to world space, we must transform it by the inverse-transpose of the inverse of the view-projection matrix.

Given a normal vector N in clip space, we find N’ in world space like this:

N(((VP)-¹)-¹)T = N'

We can simplify this as we know that the inverse of the transformation matrix that transforms a point from clip space to world space is actualy none other than the view-projection matrix. In other words the inverse-transpose of the inverse of the view-projection matrix, is the transpose of the view-projection matrix:

((VP)-¹)-¹ = VP
N(((VP)-¹)-¹)T = N'
N(VP)T = N'

To find the frustum planes in world space, we simply need to transform each clip space plane normal by the transpose of the view-projection matrix.
We can simplify this even further. Because we have so many zeroes in our clip space normals, we don’t need to do a full vector-matrix product.
This shows the process for the near plane N:

N = (0, 0, 1, 1)
 
VP = [ 
	  _11, _12, _13, _14,
	  _21, _22, _23, _24,
	  _31, _32, _33, _34,
	  _41, _42, _43, _44
	]
 
N(VP)T = [
	   0 * _11 + 0 * _21 + 1 * _31 + 1 * _41
	   0 * _12 + 0 * _22 + 1 * _32 + 1 * _42
	   0 * _13 + 0 * _23 + 1 * _33 + 1 * _43
	   0 * _14 + 0 * _24 + 1 * _34 + 1 * _44
	 ]
 
N(VP)T = [
	   _31 + _41
	   _32 + _42
	   _33 + _43
	   _34 + _44
	 ]

Using this optimization we find the world space normal by adding the third and forth rows of the transpose of the view-projection matrix. It’s the exact same process for each plane normal:

near = (0, 0, 1, 1)
near = (0, 0, 1, 1)(VP)T
near = [_31 + _41, _32 + _42, _33 + _43, _34 + _44]
 
far = (0, 0, -1, 1)
far = (0, 0, -1, 1)(VP)T
far = [-(_31 + _41), -(_32 + _42), -(_33 + _43), -(_34 + _44)]
 
top = (0, -1, 0, 1)
top = (0, -1, 0, 1)(VP)T
top = [-(_21 + _41), -(_22 + _42), -(_23 + _43), -(_24 + _44)]
 
bottom = (0, 1, 0, 1)
bottom = (0, 1, 0, 1)(VP)T
bottom = [_21 + _41, _22 + _42, _23 + _43, _24 + _44]
 
left = (1, 0, 0, 1)
left = (1, 0, 0, 1)(VP)T
left = [_11 + _41, _12 + _42, _13 + _43, _14 + _44]
 
right = (-1, 0, 0, 1)
right = (-1, 0, 0, 1)(VP)T
right = [-(_11 + _41), -(_12 + _42), -(_13 + _43), -(_14 + _44)]

A little extra step:

Often, frustum culling tutorials use the transpose of the view-projection matrix to extract the frustum planes. Even though computing the transpose of a matrix is cheap, there is no reason to do such a thing.
Since we are not using vector-matrix multiplication any more, we don’t need to compute the transpose of the view-projection matrix, we can just use the view-projection matrix as it is. If we do this, care must be taken to add the columns of the matrix, and not the rows:

near = (0, 0, 1, 1)
near = (0, 0, 1, 1)(VP)T
near = [_13 + _14, _23 + _24, _33 + _34, _43 + _44]
 
far = (0, 0, -1, 1)
far = (0, 0, -1, 1)(VP)T
far = [-(_13 + _14), -(_23 + _24), -(_33 + _34), -(_43 + _44)]
 
top = (0, -1, 0, 1)
top = (0, -1, 0, 1)(VP)T
top = [-(_12 + _14), -(_22 + _24), -(_32 + _34), -(_42 + _44)]
 
bottom = (0, 1, 0, 1)
bottom = (0, 1, 0, 1)(VP)T
bottom = [_12 + _14, _22 + _24, _32 + _34, _42 + _44]
 
left = (1, 0, 0, 1)
left = (1, 0, 0, 1)(VP)T
left = [_11 + _14, _21 + _24, _31 + _34, _41 + _44]
 
right = (-1, 0, 0, 1)
right = (-1, 0, 0, 1)(VP)T
right = [-(_11 + _14), -(_21 + _24), -(_31 + _34), -(_41 + _44)]

In order to get the planes in view space, all those steps are exactly the same, but instead of using the view-projection matrix, you just use the projection matrix.

Tags: C-C++, linear algebra, math