Tutorial 74: Frustum Culling

CNA Tutorials  ·  Performance

What is frustum culling?

The view frustum is the pyramid-shaped region of 3D space that is visible to the camera — bounded by the near plane, far plane, and four side planes. Any object entirely outside the frustum cannot contribute pixels to the frame and should be skipped before submitting it to the GPU. This CPU-side rejection is frustum culling.

In a scene with 1000 objects where only 150 are visible, frustum culling reduces draw calls by ~85%. For GPU-bound workloads this is one of the highest-impact optimisations available and is nearly free on the CPU.

BoundingFrustum from the ViewProjection matrix

CNA provides BoundingFrustum in the Microsoft::Xna::Framework namespace. Construct it from the combined view-projection matrix each frame:

#include "Microsoft/Xna/Framework/BoundingFrustum.hpp"
#include "Microsoft/Xna/Framework/BoundingSphere.hpp"
#include "Microsoft/Xna/Framework/BoundingBox.hpp"

// Rebuild every frame (cheap — just 6 plane extractions)
BoundingFrustum frustum(view_ * projection_);

The constructor extracts the six frustum planes from the matrix in one pass. You can also update an existing BoundingFrustum via frustum.setMatrix(view_ * projection_) to avoid reallocating.

BoundingSphere per object

Each game object needs a bounding volume. A BoundingSphere (centre + radius) is the cheapest to test against a frustum (six dot products, one comparison each). Store the sphere in object-local space and transform it to world space before testing:

struct SceneObject {
    Matrix        world;
    BoundingSphere localBounds;  // pre-computed from mesh vertices
    VertexBuffer* vb;
    IndexBuffer*  ib;
    int           primitiveCount;
};

// Transform the local bounding sphere to world space
BoundingSphere WorldSphere(const SceneObject& obj) {
    return obj.localBounds.Transform(obj.world);
}

To pre-compute localBounds from a mesh, use BoundingSphere::CreateFromPoints:

// After loading vertex data into a std::vector<VertexPositionNormalTexture>
std::vector<Vector3> positions;
positions.reserve(verts.size());
for (auto& v : verts) positions.push_back(v.Position);

BoundingSphere bounds = BoundingSphere::CreateFromPoints(
    positions.data(), static_cast<int>(positions.size()));

BoundingFrustum.Intersects()

BoundingFrustum::Intersects(const BoundingSphere&) returns a ContainmentType enum:

  • ContainmentType::Contains — sphere is fully inside the frustum.
  • ContainmentType::Intersects — sphere straddles a frustum plane.
  • ContainmentType::Disjoint — sphere is entirely outside; cull this object.

For culling purposes, treat Contains and Intersects identically (draw the object).

Culling loop: 1000 objects

void Draw(const GameTime&) override {
    auto& gd = getGraphicsDeviceProperty();
    gd.Clear(Color::CornflowerBlue);

    // Rebuild frustum from current camera matrices
    BoundingFrustum frustum(view_ * proj_);

    int drawn   = 0;
    int culled  = 0;

    effect_->setView(view_);
    effect_->setProjection(proj_);

    for (auto& obj : sceneObjects_) {  // 1000 objects
        BoundingSphere worldSphere = obj.localBounds.Transform(obj.world);

        if (frustum.Contains(worldSphere) == ContainmentType::Disjoint) {
            ++culled;
            continue;  // skip — not visible
        }

        // Object is visible — submit draw call
        ++drawn;
        effect_->setWorld(obj.world);
        for (auto& pass : effect_->getCurrentTechnique().Passes) {
            pass.Apply();
            gd.setVertexBuffer(*obj.vb);
            gd.setIndexBuffer(*obj.ib);
            gd.DrawIndexedPrimitives(
                PrimitiveType::TriangleList,
                0, 0, obj.vertexCount, 0, obj.primitiveCount);
        }
    }

    // Display stats
    std::string stats = "Drawn: " + std::to_string(drawn) +
                        "  Culled: " + std::to_string(culled);
    spriteBatch_->Begin();
    spriteBatch_->DrawString(*font_, stats, Vector2(8, 8), Color::Yellow);
    spriteBatch_->End();

    gd.Present();
}

AABB culling

For objects that are not well approximated by a sphere (e.g. long buildings, terrain tiles), an axis-aligned bounding box (BoundingBox) gives a tighter fit and fewer false positives. The test is more expensive (up to 12 dot products vs 6 for a sphere) but still negligible compared to the GPU draw call it avoids:

// Per-object: test AABB in world space
BoundingBox worldAABB = BoundingBox::Transform(obj.localAABB, obj.world);
if (frustum.Contains(worldAABB) == ContainmentType::Disjoint)
    continue;  // cull

A common hybrid: use the BoundingSphere for a fast rejection test first, then the BoundingBox for a more precise accept/reject only on the small number of objects that pass the sphere test.

Scene graph vs brute force

Iterating all 1000 objects each frame to test them against the frustum is the brute-force approach. For scenes with tens of thousands of objects, organise objects into a spatial structure (see Tutorial 76) so the frustum query only visits objects near the camera. For most games up to ~2000 visible objects, the brute-force O(n) test is fast enough and simpler to maintain.

Frame latency of culling

Frustum culling is computed on the CPU using the camera matrices from the current frame's Update. Because the GPU renders the frame slightly later, there is theoretically a one-frame lag — but at 60 Hz this is 16 ms and the camera typically does not move far enough in one frame for a just-culled object to pop into view. The XNA original games used the same single-frame-delay approach without issue.