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 in place via frustum.setMatrixProperty(view_ * projection_). Matrices are multiplied in XNA’s row-vector order, view * projection, exactly as in Tutorial 33.

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
    BoundingBox    localAABB;    // optional tighter box (see "AABB culling")
    VertexBuffer*  vb;           // not owned
    IndexBuffer*   ib;           // not owned
    int            vertexCount;
    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);   // takes a std::vector<Vector3>
BoundingBox    box    = BoundingBox::CreateFromPoints(positions);

BoundingFrustum.Intersects() / Contains()

BoundingFrustum::Contains(BoundingSphere) returns a ContainmentType enum. (As in XNA, Intersects(BoundingSphere) returns a plain bool instead: true for “touches or is inside”. Use it when you do not need to tell Contains from Intersects.)

• 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), which is exactly what frustum.Intersects(sphere) answers with one bool.

Culling loop: 1000 objects

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

    // SpriteBatch changed these during last frame's stats overlay and does not restore them
    gd.setBlendStateProperty(BlendState::Opaque);
    gd.setDepthStencilStateProperty(DepthStencilState::Default);
    gd.setRasterizerStateProperty(RasterizerState::CullCounterClockwise);

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

    int drawn   = 0;
    int culled  = 0;

    effect_->setViewProperty(view_);
    effect_->setProjectionProperty(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_->setWorldProperty(obj.world);
        gd.SetVertexBuffer(obj.vb);
        gd.setIndicesProperty(obj.ib);
        for (auto& pass : effect_->getCurrentTechniqueProperty()->getPassesProperty()) {
            pass.Apply();
            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();
    // No gd.Present(): Game presents in EndDraw, after Draw() returns.
}

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:

BoundingBox has no Transform (neither has XNA’s). To move a box into world space, transform its eight corners and re-fit an axis-aligned box around them:

BoundingBox WorldAABB(const BoundingBox& local, const Matrix& world) {
    std::vector<Vector3> corners = local.GetCorners();          // the 8 corners
    for (Vector3& c : corners) c = Vector3::Transform(c, world);
    return BoundingBox::CreateFromPoints(corners);               // re-fit an axis-aligned box
}

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

Re-fitting after a rotation makes the box larger than the rotated original, so it is conservative (it never culls something visible), just less tight.

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, and the frustum built in Draw comes from exactly the same view and projection matrices that the draw calls that follow use, so the culling result and the picture agree by construction: an object is never skipped for a camera position it is not drawn with. Staleness only appears if you build the frustum from last frame’s matrices, or cache the visibility result across frames (for example to amortise a large scene). If you do that, cull with a slightly enlarged sphere or refresh the result every frame the camera moves.