Frustum Culling

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 D3DXPLANE structures, which represent the left, right, top, bottom, near, and far planes. Each D3DXPLANE 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 transforming 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.0 )
{
    // Point is in front of plane
}

There just so happens to be a function in the D3DX library that performs this calculation: D3DXPlaneDotCoord.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Summary: Set the CMesh reference
Parameters:
[in] pMesh - Pointer to a CMesh
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void CMeshInstance::SetMesh( CMesh* pMesh )
{
    Release();
    m_pMesh = pMesh; 

    // Compute bounding sphere
    if ( m_pMesh )
    {
        D3DXVECTOR3 center;
        LPD3DXMESH pD3DXMesh = m_pMesh->GetMesh();
        DWORD numVertices = pD3DXMesh->GetNumVertices();
        DWORD fvfSize = D3DXGetFVFVertexSize( pD3DXMesh->GetFVF() );
        char* pData = NULL;
        if ( FAILED( pD3DXMesh->LockVertexBuffer( 0, (void**)&pData ) ) )
        {
            SHOWERROR( "Failed to lock mesh vertex buffer.", __FILE__, __LINE__ );
            return;
        }
        D3DXComputeBoundingSphere( (D3DXVECTOR3*)pData, numVertices, fvfSize, &center, &m_boundingRadius );
        if ( FAILED( pD3DXMesh->UnlockVertexBuffer() ) )
        {
            SHOWERROR( "Failed to unlock mesh vertex buffer.", __FILE__, __LINE__ );
            return;
        }
    }
}

To calculate the radius of the bounding sphere, we’ll use the D3DXComputeBoundingSphere function. To use this function, we have to get access to the vertices in the mesh’s vertexbuffer. We can do this with ID3DXMesh::LockVertexBuffer. Note that to use the D3DXComputeBoundingSphere function, we’ll need the number of vertices, obtained with ID3DXMesh::GetNumVertices, and the vertex stride, obtained with D3DXGetFVFVertexSize and ID3DXMesh::GetFVF.

if ( m_camera.SphereInFrustum( m_box.GetPosition(), m_box.GetBoundingRadius() ) )
{
    m_box.Render( pDevice );
}

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 CCamera 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.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Summary: Build the view frustum planes using the current view/projection matrices
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
void CCamera::BuildViewFrustum()
{
    D3DXMATRIX viewProjection;
    D3DXMatrixMultiply( &viewProjection, &m_view, &m_projection );
    //D3DXMatrixMultiply( &viewProjection, &m_mView, &m_mProjection );
    // Left plane
    m_frustum[0].a = viewProjection._14 + viewProjection._11;
    m_frustum[0].b = viewProjection._24 + viewProjection._21;
    m_frustum[0].c = viewProjection._34 + viewProjection._31;
    m_frustum[0].d = viewProjection._44 + viewProjection._41;

    // Right plane
    m_frustum[1].a = viewProjection._14 - viewProjection._11;
    m_frustum[1].b = viewProjection._24 - viewProjection._21;
    m_frustum[1].c = viewProjection._34 - viewProjection._31;
    m_frustum[1].d = viewProjection._44 - viewProjection._41;

    // Top plane
    m_frustum[2].a = viewProjection._14 - viewProjection._12;
    m_frustum[2].b = viewProjection._24 - viewProjection._22;
    m_frustum[2].c = viewProjection._34 - viewProjection._32;
    m_frustum[2].d = viewProjection._44 - viewProjection._42;

    // Bottom plane
    m_frustum[3].a = viewProjection._14 + viewProjection._12;
    m_frustum[3].b = viewProjection._24 + viewProjection._22;
    m_frustum[3].c = viewProjection._34 + viewProjection._32;
    m_frustum[3].d = viewProjection._44 + viewProjection._42;

    // Near plane
    m_frustum[4].a = viewProjection._13;
    m_frustum[4].b = viewProjection._23;
    m_frustum[4].c = viewProjection._33;
    m_frustum[4].d = viewProjection._43;

    // Far plane
    m_frustum[5].a = viewProjection._14 - viewProjection._13;
    m_frustum[5].b = viewProjection._24 - viewProjection._23;
    m_frustum[5].c = viewProjection._34 - viewProjection._33;
    m_frustum[5].d = viewProjection._44 - viewProjection._43;

    // Normalize planes
    for ( int i = 0; i < 6; i++ )
    {
        D3DXPlaneNormalize( &m_frustum[i], &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 D3DXPlaneNormalize.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Summary: Checks whether a sphere is inside the camera's view frustum.
Parameters:
[in] pPosition - Position of the sphere.
[in] radius - Radius of the sphere.
Returns: TRUE if the sphere is in the frustum, FALSE otherwise
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
BOOL CCamera::SphereInFrustum( D3DXVECTOR3* pPosition, float radius )
{
    for ( int i = 0; i < 6; i++ )
    {
        if ( D3DXPlaneDotCoord( &m_frustum[i], pPosition ) + 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 D3DXPlaneDotCoord. Since we’re dealing with sphere and not points, we add the radius to the dot product before coming up with a verdict.