Sphere-Based Frustum Culling

Sphere based frustum culling reduces vertex draw calls to improve performance.

The following sections explain how to perform optimized frustum culling on the Xbox One dev kit using spheres:

The tutorial describes a simple implementation of sphere based frustum culling. For a working example, see the RenderTechniques XDK sample. For more information on running the XDK samples, see Running the XDK Samples.

What is Sphere-Based Frustum Culling?

Sphere-based frustum culling is an optimized form of traditional frustum culling, using a sphere to represent an entire model instead of checking each individual vertex.

What is a View Frustum?

The view frustum is the volume of space within your game world that can be seen by the camera, and will therefore be drawn onscreen. It is called a frustum because the volume of space looks like a truncated pyramid, otherwise known as a frustum.

What is Frustum Culling?

Any vertices inside the view frustum will appear onscreen. Any vertices outside the frustum will not be drawn. The GPU automatically performs this task for every vertex in the current Draw() call.

What is Sphere-Based Frustum Culling?

Checking each vertex in the world against the view frustum every frame is an inefficient process. We cannot prevent the GPU from performing frustum culling on every vertex it recieves, but we can reduce the number of Draw() calls by determining which objects are not onscreen beforehand. Sphere-based culling is an easy, efficient method to achieve this. The basic concept is to encase every game object in it’s own sphere, then compare those spheres against the view frustum. If the sphere falls inside the view frustum, you know the object is onscreen, and you can draw the object. If the sphere intersects the frustum, then we know that model is probably at least partially onscreen, so we can call Draw() and let the GPU determine which vertices are onscreen and which arent. Any spheres that do not touch the frustum at all are entirely offscreen, and you don’t need to draw them.

Necessary Data:

Sphere-based view frustum culling will make use of the following data:

C++

// View Frustum Data
XMMATRIX    g_View;          // Camera View Matrix: stores position and orientation of camera
XMMATRIX    g_Projection;    // Projection Matrix: stores screen dimensions, FOV, and view distance
XMMATRIX    g_ViewProj;      // The product of g_View * g_Projection. Used to derive Frustum Planes

XMVECTOR*   g_FrustumPlanes; // Pointer to array of 6 vectors, one representing each frustum plane

// Object Data
XMMATRIX    g_World;    // World matrix for a game object
float       g_Radius;   // Radius of object bounding sphere

Initialization:

Initialize View Frustum

Create a View matrix and a Projection matrix. Use DirectX::XMMATRIX to store the data. To populate the View matrix with data, determine the location of your camera, the up vector for your camera, and what the camera is looking at. Call DirectX::XMMatrixLookAtLH() to set the View matrix data. To populate the Projection matrix with data, call DirectX::XMMatrixPerspectiveFovLH().

Mulitply the View and Projection matrices together, and store the result in another matrix. The resulting matrix will be used to calculate equations for the six planes of the view frustum.

Note Every time the camera is moved or adjusted, the View matrix needs to be recalculated. As a result, you will need to recalculate the product of View * Projection as well.

C++

// Initialize the projection matrix
g_Projection = XMMatrixPerspectiveFovLH( XM_PIDIV2, 1920 / (FLOAT)1080, 0.01f, 100.0f );

// Initialize the view matrix
XMVECTOR Eye = XMVectorSet( 0.0f, 1.0f, -5.0f, 0.0f );
XMVECTOR At = XMVectorSet( 0.0f, 1.0f, 0.0f, 0.0f );
XMVECTOR Up = XMVectorSet( 0.0f, 1.0f, 0.0f, 0.0f );
g_View = XMMatrixLookAtLH( Eye, At, Up );

// Calculate the product of view * projection
g_ViewProj = XMMatrixMultiply( g_View, g_Projection );

// Allocate array of frustum planes
g_FrustumPlanes = new XMVECTOR[6];  // A frustum has six sides: Top, Bottom, Left, Right, Near, Far

Calculate Sphere Radius for a mesh:

We only want to calculate the radius of each mesh once during initialization. To determine the sphere radius for a particular mesh, examine every vertex in that mesh and determine which vertex is furthest from the origin(center) of the mesh. The distance between that vertex and the origin is equal to the radius of your bounding sphere.

C++

//  Determine the radius of the bounding sphere for the given object
float Game::CalculateRadius( UINT VertexCount, XMFLOAT3 Scale, SimpleVertex* VertexBuffer )
{
    float radius = 0.0f;
    float tempRadius = 0.0f;
    float ScaleXPos, ScaleYPos, ScaleZPos;
    
    // Walk the vertex list, determining the distance of each vertex
    for( UINT i = 0; i < VertexCount; ++i )
    {
        // Account for scale modifications
        ScaleXPos = VertexBuffer[i].Pos.x * Scale.x;
        ScaleYPos = VertexBuffer[i].Pos.y * Scale.y;
        ScaleZPos = VertexBuffer[i].Pos.z * Scale.z;
        
        // Use pythagorean theorem to derive distance from origin to vertex.   D^2 = (A^2 + B^2 + C^2)
        tempRadius = (ScaleXPos * ScaleXPos) + (ScaleYPos * ScaleYPos) + (ScaleZPos * ScaleZPos);

        if( tempRadius > radius )
            radius = tempRadius;
    }

    return sqrtf(radius);
}

Derive Frustum Planes:

In order to determine if a sphere is intersecting the view frustum, we need to check the sphere against the planes that border the frustum. If the sphere intersects any plane, or is inside all six planes, draw the corresponding object.

Note It is possible for a bounding sphere to be in the view frustum without any of the object vertices being within the frustum.

The ViewProj matrix contains everything we need to calculate the six planes. Derive each plane and store the results in an array of DirectX::XMVECTOR’s. Normalize the plane equations, so they may be used later as scalars. The frustum planes change and must be recalculated every time the camera moves or changes orientation.

C++

// Compute the plane equation for each of the 6 faces of the view frustum. 
void Game::ExtractFrustumPlanes( XMVECTOR* const frustumPlanes, const BOOL negatePlanes )
{
    XMVECTOR &nearPlane         = frustumPlanes[0];
    XMVECTOR &leftPlane         = frustumPlanes[1];
    XMVECTOR &rightPlane        = frustumPlanes[2];
    XMVECTOR &bottomPlane       = frustumPlanes[3];
    XMVECTOR &topPlane          = frustumPlanes[4];
    XMVECTOR &farPlane          = frustumPlanes[5];

    // Calculate plane equations from g_ViewProj matrix data
    for( UINT i = 0; i < 4; ++i )
    {
        leftPlane.m128_f32[i]    = g_ViewProj.r[i].m128_f32[3] + g_ViewProj.r[i].m128_f32[0];
        rightPlane.m128_f32[i]    = g_ViewProj.r[i].m128_f32[3] - g_ViewProj.r[i].m128_f32[0];    
    
        bottomPlane.m128_f32[i]    = g_ViewProj.r[i].m128_f32[3] + g_ViewProj.r[i].m128_f32[1];
        topPlane.m128_f32[i]    = g_ViewProj.r[i].m128_f32[3] - g_ViewProj.r[i].m128_f32[1];
    
        nearPlane.m128_f32[i]    = g_ViewProj.r[i].m128_f32[3];
        farPlane.m128_f32[i]    = g_ViewProj.r[i].m128_f32[3] - g_ViewProj.r[i].m128_f32[2];
    }
    
    // Determine whether plane normals face inwards or outwards. if negatePlanes == TRUE, normals face outwards
    const float oneSigned        = ( negatePlanes ) ? -1.0f : 1.0f;
    
    // Normalize plane equations.
    for( UINT i = 0; i < 6; ++i )
    {
        XMVECTOR &plane             = frustumPlanes[i];
    
        // Calculate the inverse magnitude
        float invMag             = oneSigned / sqrtf( ( plane.m128_f32[0] * plane.m128_f32[0] ) + ( plane.m128_f32[1] * plane.m128_f32[1] )
                                                    + ( plane.m128_f32[2] * plane.m128_f32[2] ) );
        plane.m128_f32[0]        *= invMag;
        plane.m128_f32[1]        *= invMag;
        plane.m128_f32[2]        *= invMag;
        plane.m128_f32[3]        *= invMag;
    }
}

Compare Sphere to Frustum:

To determine if a sphere is onscreen we must compare it against each plane. For each plane, calculate the distance from the center of the sphere to the plane. (Distance = Ax + By + Cz + D) where A,B,C,D are the four values stored in the XMVECTOR that contains the normalized plane equation, and x,y,z are the coordinates of the center of the sphere. The distance from the plane can be either positive or negative. If the result is positive, then point (x,y,z) is on the correct side of the plane, negative values mean the point is on the wrong side of the plane. A value of zero means that the point is directly on the plane.

The formula above tells us if the center of the sphere is on the correct side of the current plane. However, we want to check if any of the sphere is onscreen, not just the center. Fortunately, spheres have a uniform radius, so this check is as simple as adding the sphere radius to the distance. If the result is positive, then the sphere is inside the plane.

Note As an optimization, if the sphere intersects any plane, then we know that object is partially onscreen, and can skip any remaining planes.

C++

// Compare sphere coordinates against frustum planes to determine if the sphere is inside or intersecting the frustum
// NOTE: This function assumes that all of the plane equation normal vectors are facing INWARD.
bool Game::SphereInFrustum( XMMATRIX worldPos, float radius )
{
    float XPos = worldPos.r[3].m128_f32[0];
    float YPos = worldPos.r[3].m128_f32[1];
    float ZPos = worldPos.r[3].m128_f32[2];

    float DistanceFromPlane = 0.0f;

    // Compare sphere position against all six planes. If a single check fails, the sphere is not in the frustum, return false
    for ( UINT i = 0; i < 6; ++i )
    {
        XMVECTOR &plane = g_FrustumPlanes[i];

        // Distance = Ax + By + Cz + D 
        // (Normally, we would have to divide by sqrt(A^2 + B^2 + C^2), but the plane equation has already been normalized)
        DistanceFromPlane = (plane.m128_f32[0] * XPos) + (plane.m128_f32[1] * YPos) + (plane.m128_f32[2] * ZPos) + plane.m128_f32[3];

        // Add radius to distance to find the leading point of the sphere
        DistanceFromPlane += radius;

        // If the resulting value is positive, then the sphere is on the correct side of the current plane
        if( DistanceFromPlane >= 0 )
        {
            continue;
        }
        else  // If the sphere is on the wrong side of any plane, then it is not in the view frustum
        {
            return false;
        }
    }

    return true;
}

See also

DirectX