# Frustum Culling

CU_MDX_FrustumCulling.zip (96.3 KiB, 3,155 hits)

CUnitFramework.zip (101.1 KiB, 20,514 hits)

Extract the C-Unit Framework
inside the project (not solution) directory.

When we tell DirectX to render geometry, it will perform a culling test to see if a vertex is within the view frustum before rendering the vertex. DirectX will only render a vertex if it is within the view frustum. However, this test occurs after the geometry has been transformed and lit by the world and view matrices. In more complex scenes, thousands of vertices would be transformed just to be rejected by the frustum test in DirectX. We can speed up performance quite a bit if we implement a view frustum culling test prior to our render calls.

By reading through some computer graphics books like Real-Time Rendering (buy it already!), you may learn that a camera’s view frustum is defined in the projection matrix. Therefore, if we concatenate the view and projection matrices, we’ll get a matrix that defines the view frustum in world space. To store the frustum information, we’ll use 6 Plane structures, which will represent the left, right, top, bottom, near, and far planes of the view frustum. Each Plane structue represents the a, b, c, and d of the general plane equation: ax + by + cz + dw = 0, where a, b, and c form the normal of the plane and d is the distance from the origin.

Every frame, we’ll update_ the camera to rebuild this view frustum so we can use it to reject geometry prior to rendering it. There are various methods we can use in order to test whether a mesh lies within the view frustum. The most expensive method would be to test every single vertex in a vertex buffer whether it lies within the frustum. That would be silly of course, so we won’t do it. Instead, we’ll use the bounding sphere test. We’ll use the position of each mesh and a radius, which would form a sphere surrounding the mesh, to test whether the mesh is within the view frustum. Using our clever math skills, we know a point is in front of a plane if the dot product of the plane normal and the point added to the distance of the plane from the origin is greater than 0. In other words:

if ( dot( plane.normal, point ) + plane.distance > 0 )
{
// Point is in front of plane
}

There just so happens to be a function in the Plane structure that performs this calculation: Plane.Dot.

/// Creates anew MeshInstance
/// Mesh to reference
public MeshInstance( Mesh mesh )
{
m_mesh = mesh;

// Compute bounding sphere
using ( D3D.VertexBuffer buffer = m_mesh.SourceMesh.VertexBuffer )
{
GraphicsBuffer graphicsBuffer = buffer.Lock( 0, 0, D3D.LockFlags.None );
m_boundingSphere = D3D.Geometry.ComputeBoundingSphere( graphicsBuffer, m_mesh.SourceMesh.NumberVertices, m_mesh.SourceMesh.VertexFormat );
buffer.Unlock();
}
}

To calculate the radius of the bounding sphere, we’ll use the Geometry.ComputeBoundingSphere method. To use this method, we have to get the GraphicsBuffer of the Mesh’s VertexBuffer by calling VertexBuffer.Lock.

if ( m_camera.SphereInFrustum( m_box.Position, m_box.Radius ) )
{
m_box.Render( device );
}

Before we render a mesh, we check if it is inside the camera’s view frustum to see if we should render it. The SphereInFrustum method of the Camera class uses the camera’s view frustum to determine whether the mesh’s bounding sphere is inside the view frustum. However, before we can call this method, we need to know how to build the view frustum.

///
/// Build the view frustum planes using the current view/projection matrices
///

public void BuildViewFrustum()
{
Matrix viewProjection = m_view * m_projection;

// Left plane
m_frustum[0].A = viewProjection.M14 + viewProjection.M11;
m_frustum[0].B = viewProjection.M24 + viewProjection.M21;
m_frustum[0].C = viewProjection.M34 + viewProjection.M31;
m_frustum[0].D = viewProjection.M44 + viewProjection.M41;

// Right plane
m_frustum[1].A = viewProjection.M14 – viewProjection.M11;
m_frustum[1].B = viewProjection.M24 – viewProjection.M21;
m_frustum[1].C = viewProjection.M34 – viewProjection.M31;
m_frustum[1].D = viewProjection.M44 – viewProjection.M41;

// Top plane
m_frustum[2].A = viewProjection.M14 – viewProjection.M12;
m_frustum[2].B = viewProjection.M24 – viewProjection.M22;
m_frustum[2].C = viewProjection.M34 – viewProjection.M32;
m_frustum[2].D = viewProjection.M44 – viewProjection.M42;

// Bottom plane
m_frustum[3].A = viewProjection.M14 + viewProjection.M12;
m_frustum[3].B = viewProjection.M24 + viewProjection.M22;
m_frustum[3].C = viewProjection.M34 + viewProjection.M32;
m_frustum[3].D = viewProjection.M44 + viewProjection.M42;

// Near plane
m_frustum[4].A = viewProjection.M13;
m_frustum[4].B = viewProjection.M23;
m_frustum[4].C = viewProjection.M33;
m_frustum[4].D = viewProjection.M43;

// Far plane
m_frustum[5].A = viewProjection.M14 – viewProjection.M13;
m_frustum[5].B = viewProjection.M24 – viewProjection.M23;
m_frustum[5].C = viewProjection.M34 – viewProjection.M33;
m_frustum[5].D = viewProjection.M44 – viewProjection.M43;

// Normalize planes
for ( int i = 0; i < 6; i++ )
{
m_frustum[i] = Plane.Normalize( m_frustum[i] );
}
}

This function is called every frame when the camera is updated. A more efficient approach would be to just update_ the view frustum whenever the camera moves, but hey, functionality first, optimizations last. To get a better understanding of the math behind this, buy Real-Time Rendering. Basically, the fourth column of the culling matrix represents the camera’s Z-axis. The first, second, and third columns represent the normals of the planes that form the view frustum. So we just add or subtract them together to extract the corresponding view frustum plane. We also need to normalize the planes so our dot product calculations will be accurate. We do this by calling Plane.Normalize.

/// Checks whether a sphere is inside the camera’s view frustum.
/// Position of the sphere.
/// true if the sphere is in the frustum, false otherwise
public bool SphereInFrustum( Vector3 position, float radius )
{
Vector4 position4 = new Vector4( position.X, position.Y, position.Z, 1f );
for ( int i = 0; i < 6; i++ )
{
if ( Plane.Dot( m_frustum[i], position4 ) + radius < 0 )
{
// Outside the frustum, reject it!
return false;
}
}
return true;
}

And finally, the culling test. A sphere is inside the view frustum if it is in front of all the planes of the view frustum. As mentioned at the start of this tutorial, we determine what side of a plane a point is located by calculating the dot product with Plane.Dot. Since we’re dealing with spheres and not points, we add the radius to the dot product before coming up with a verdict.

When viewing a single crate, my fps jumped from 120 fps to 450 fps with the use of frustum culling.

## One thought on “Frustum Culling”

#### Pingback: Thomas Sampson » Reading List

You may use these HTML tags and attributes:
```<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

<code> For inline code.
[sourcecode] For multiline code.
```