First Iteration of Frustum Culling: A Starting Point for Optimization

Frustum culling is a fundamental technique in real-time 3D rendering that helps improve performance by quickly determining which objects in a scene are potentially visible. In this post, we introduce the first iteration of our frustum culling implementation, a solid starting codebase that you can build upon and customize as your engine grows.

What is Frustum Culling?

Frustum culling is the process of eliminating objects that fall completely outside the camera's view. This is done by defining a view frustum, a pyramid-like volume (often truncated by near and far clipping planes), and testing whether an object's bounding volume (such as an Axis-Aligned Bounding Box or AABB) intersects with this volume. If an object is completely outside the frustum, it is culled (i.e., not sent to the GPU for rendering), saving valuable processing time.

Why Use Frustum Culling?

• Performance: By ignoring objects outside the camera's view, we reduce the number of draw calls and unnecessary computations, which can significantly improve frame rates.
• Efficiency: This technique allows us to manage large scenes by only focusing on visible elements.
• Scalability: Starting with a basic implementation provides a strong foundation. As your project scales, you can add further optimizations such as occlusion culling, level-of-detail (LOD) techniques, and even shadow-specific culling.

How We Use Frustum Culling

Our current iteration revolves around a simple Frustum class that serves two main functions:

1. Setup: The SetViewProjection function sets the view-projection matrix for the current frame and extracts the frustum planes.
2. Visibility Check: The IsVisible function checks whether a given object (represented by its model transformation and AABB) intersects with the view frustum.

In the IsVisible function, note that the AABB is assumed to be defined using world coordinates for its minimum (MIN) and maximum (MAX) values. This is critical because the culling test needs to account for the object's placement in the world, ensuring accurate intersection tests with the frustum.

Understanding the View-Projection Matrix

The view-projection matrix is central to 3D graphics. It is a combination of:

• View Matrix: Transforms world coordinates into camera space.
• Projection Matrix: Transforms camera space coordinates into clip space.

By combining these matrices, we get a transformation that directly converts object coordinates to clip space, from which we can extract the frustum planes.

Extracting the Projection Planes

In our implementation, the frustum is represented by six planes (left, right, bottom, top, near, far). The extraction process involves:

1. Combining Matrix Rows:
2. Since our matrix is stored in column-major order, we combine elements from different columns to compute the coefficients of each plane. For instance:

• The left plane is calculated as the sum of the fourth column and the first column.
• The right plane is the difference between the fourth column and the first column.

1. Normalizing the Planes:
2. After computing the plane coefficients, we normalize them. This ensures that the distance calculations during the culling test are accurate.

Here’s a closer look at the relevant code snippet:

void Frustum::SetViewProjection(const glm::mat4& vp)
{
   // Avoid recomputation if the view-projection matrix hasn't changed
   if (m_ViewProjection == vp) 
       return;

    m_ViewProjection = vp;
    const glm::mat4 transposed = glm::transpose(vp);
    
    // Extract planes (Vulkan coordinate system)
    // Order: Left, Right, Bottom, Top, Near, Far
    m_Planes[0] = transposed[3] + transposed[0]; // Left
    m_Planes[1] = transposed[3] - transposed[0]; // Right
    m_Planes[2] = transposed[3] + transposed[1]; // Bottom
    m_Planes[3] = transposed[3] - transposed[1]; // Top
    m_Planes[4] = transposed[2];                 // Near
    m_Planes[5] = transposed[3] - transposed[2]; // Far
    
    // Normalize planes
    for (auto& plane : m_Planes)
    {
        float length = glm::length(glm::vec3(plane));
        if (length > std::numeric_limits<float>::epsilon())
        {
            plane /= length;
        }
    }
}

This code sets up the frustum once per frame by recalculating the six planes using the latest view-projection matrix.

Testing Object Visibility

Once the frustum is established, we need to determine if an object is within it. The IsVisible method uses the AABB’s world-space Min and Max values to calculate the center and extents, then transforms the center using the object's model matrix, and finally performs a series of tests against each frustum plane.

For each plane, the method:

• Computes the signed distance from the AABB's center to the plane.
• Determines the projection radius of the AABB onto the plane’s normal.
• If the sum of the center distance and the radius is less than zero for any plane, the AABB is entirely outside the frustum, and the object is culled.

Here’s the relevant snippet:

bool Frustum::IsVisible(const AABB& worldAABB)
{
    // Quick bounds check against each plane
    for (const auto& plane : m_Planes)
    {
        // Compute the point furthest away from the plane (negative half-space)
        glm::vec3 positiveVertex = worldAABB.Min;
        glm::vec3 negativeVertex = worldAABB.Max;

        // Use the first three components of the plane equation as the normal
        const glm::vec3 normal = glm::vec3(plane);

        // Adjust vertices based on plane normal direction
        if (normal.x >= 0) {
            positiveVertex.x = worldAABB.Max.x;
            negativeVertex.x = worldAABB.Min.x;
        }
        if (normal.y >= 0) {
            positiveVertex.y = worldAABB.Max.y;
            negativeVertex.y = worldAABB.Min.y;
        }
        if (normal.z >= 0) {
            positiveVertex.z = worldAABB.Max.z;
            negativeVertex.z = worldAABB.Min.z;
        }

        // Check if the entire bounding box is outside any plane
        // Compute signed distance of furthest point from plane
        float d1 = glm::dot(normal, positiveVertex) + plane.w;
        if (d1 < 0)
        {
            return false; // Entire AABB is outside this plane
        }
    }
    return true; // AABB is potentially visible
}

This function is designed to be efficient and easy to understand, making it a great candidate for further experimentation or integration into larger projects.

Shadow Pass Considerations

In addition to standard view frustum culling, it's worth noting that a similar approach can be applied during the shadow pass. For shadow mapping, you might want to cull game objects using the light’s view-projection matrix instead of the camera's. This ensures that only objects potentially casting shadows are processed, thereby optimizing the shadow rendering process.

Extending the Code

This implementation represents the “first iteration” of our frustum culling system. As you integrate this into your project, you might consider the following enhancements:

• Optimization: Caching results or integrating spatial partitioning structures (like octrees or BVHs) can further improve performance.
• Robustness: Extend the implementation to handle more complex bounding volumes (e.g., spheres or oriented bounding boxes).
• Debugging Tools: Develop visualizations to display the frustum and AABB boundaries, which can help in debugging and refining the culling process.
• Edge Cases: Address potential precision issues or special cases (like objects straddling multiple frustum planes).

Additional Resources:

Article about collisions detection: A wonderful resource for collision detection and another approach about volume, culling and mathematic concept.

Learn OpenGL's Frustum Culling explanation: Another wonderful resource explaining how frustum culling works.