Tutorial 44: Bounding Volumes and Spatial Queries

CNA — C++ XNA 4.0 reimplementation

CNA implements the full XNA 4.0 set of bounding volumes. They are CPU-side structs used for collision detection, frustum culling, and spatial partitioning — not rendered directly.

BoundingBox — axis-aligned box

#include <optional>
#include <random>
#include <vector>
#include "Microsoft/Xna/Framework/BoundingBox.hpp"
#include "Microsoft/Xna/Framework/BoundingSphere.hpp"
#include "Microsoft/Xna/Framework/BoundingFrustum.hpp"
#include "Microsoft/Xna/Framework/Ray.hpp"          // the bounding headers only forward-declare Ray
#include "Microsoft/Xna/Framework/Matrix.hpp"
#include "Microsoft/Xna/Framework/MathHelper.hpp"
using namespace Microsoft::Xna::Framework;

// Construct from min/max corners
BoundingBox box(Vector3(-1, 0, -1), Vector3(1, 2, 1));

// The box has a fixed centre and half-extents
Vector3 centre = (box.Min + box.Max) * 0.5f;
Vector3 half   = (box.Max - box.Min) * 0.5f;

BoundingSphere — sphere defined by centre and radius

BoundingSphere sphere(Vector3(0, 1, 0), 1.5f); // centre, radius

BoundingFrustum — camera view frustum

Matrix view = Matrix::CreateLookAt(
    Vector3(0, 5, 10), Vector3::Zero, Vector3::Up);
Matrix proj = Matrix::CreatePerspectiveFieldOfView(
    MathHelper::PiOver4, 800.0f / 600.0f, 0.1f, 100.0f);

// Construct from the combined view-projection matrix
BoundingFrustum frustum(view * proj);

Intersects() — between types

BoundingBox   boxA(Vector3(-1,-1,-1), Vector3(1,1,1));
BoundingBox   boxB(Vector3( 0, 0, 0), Vector3(2,2,2));
BoundingSphere sph(Vector3(3, 0, 0), 1.0f);

bool bbOverlap = boxA.Intersects(boxB);    // true (shared region)
bool bsOverlap = boxA.Intersects(sph);     // false (sphere is outside)

// Ray intersection
Ray ray(Vector3(-5, 0, 0), Vector3::Right);
std::optional<float> hit = ray.Intersects(boxA);
if (hit.has_value()) {
    Vector3 hitPoint = ray.Position + ray.Direction * hit.value();   // hit.value() == 4 here
}

BoundingFrustum::Intersects(Ray) is the one ray test that is only partly implemented, unlike XNA 4.0, which computes a real entry distance: a ray whose origin is inside the frustum returns 0, one whose origin is outside returns no hit (even if it would cross the frustum), and only a ray origin lying exactly on a frustum face throws System::NotImplementedException. For picking, test rays against your objects’ boxes and spheres instead.

Contains() — point and volume tests

Returns ContainmentType::Contains, Intersects, or Disjoint.

Vector3 point(0.5f, 0.5f, 0.5f);

ContainmentType ct = boxA.Contains(point);
// ct == ContainmentType::Contains

ContainmentType ct2 = boxA.Contains(sph);
// ct2 == ContainmentType::Disjoint (the sphere spans x in [2, 4], the box ends at x = 1)

// Frustum contains test (used for culling)
ContainmentType vis = frustum.Contains(sph);
if (vis == ContainmentType::Disjoint) {
    // object is outside the frustum — skip drawing
}

CreateFromPoints() — fit a volume to geometry

std::vector<Vector3> meshVerts = { /* ... loaded from model ... */ };

BoundingBox   aabb   = BoundingBox::CreateFromPoints(meshVerts);
BoundingSphere bsph  = BoundingSphere::CreateFromPoints(meshVerts);

// Or fit a sphere to an existing box
BoundingSphere fromBox = BoundingSphere::CreateFromBoundingBox(aabb);

BoundingSphere::CreateFromPoints follows XNA’s algorithm literally, including its tie-break when several axes have the same extent and its wider-than-float distance accumulation, so it produces the same sphere XNA would for the same points. The sphere is a good fit, not the minimal enclosing sphere; if you need a tight bound, refine it yourself.

Merging bounding volumes

BoundingBox child1(Vector3(-2,-1,-1), Vector3(0,1,1));
BoundingBox child2(Vector3( 1,-1,-1), Vector3(3,1,1));

// Parent AABB encompassing both children
BoundingBox parent = BoundingBox::CreateMerged(child1, child2);
// parent.Min ≈ (-2,-1,-1), parent.Max ≈ (3,1,1)

BoundingSphere s1(Vector3(-2, 0, 0), 1.0f);
BoundingSphere s2(Vector3( 2, 0, 0), 1.0f);
BoundingSphere merged = BoundingSphere::CreateMerged(s1, s2);

Code example: frustum culling with BoundingFrustum and BoundingSphere array

struct SceneObject {
    Vector3       position;
    BoundingSphere bounds;   // in world space
    bool          visible = false;
};

class FrustumCullDemo final : public Game {
public:
    FrustumCullDemo() : graphics_(this) {}

protected:
    void Initialize() override {
        Game::Initialize();
        // Scatter 200 objects at random positions
        std::mt19937 rng(42);
        std::uniform_real_distribution<float> dist(-30.0f, 30.0f);
        objects_.resize(200);
        for (auto& obj : objects_) {
            obj.position = Vector3(dist(rng), 0.0f, dist(rng));
            obj.bounds   = BoundingSphere(obj.position, 1.0f);
        }
    }

    void LoadContent() override {
        effect_ = std::make_unique<BasicEffect>(getGraphicsDeviceProperty());
        effect_->VertexColorEnabled = true;
        // ... build sphere mesh into vb_ ...
    }

    void Update(GameTime& gameTime) override {
        float t = static_cast<float>(gameTime.getTotalGameTimeProperty().getTotalSecondsProperty());
        camPos_ = Vector3(20 * std::cos(t * 0.2f), 5,
                          20 * std::sin(t * 0.2f));

        Matrix view = Matrix::CreateLookAt(camPos_, Vector3::Zero, Vector3::Up);
        Matrix proj = Matrix::CreatePerspectiveFieldOfView(
            MathHelper::PiOver4, 800.0f / 600.0f, 0.1f, 60.0f);
        BoundingFrustum frustum(view * proj);

        visibleCount_ = 0;
        for (auto& obj : objects_) {
            ContainmentType ct = frustum.Contains(obj.bounds);
            obj.visible = (ct != ContainmentType::Disjoint);
            if (obj.visible) ++visibleCount_;
        }
    }

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

        Matrix view = Matrix::CreateLookAt(camPos_, Vector3::Zero, Vector3::Up);
        Matrix proj = Matrix::CreatePerspectiveFieldOfView(
            MathHelper::PiOver4, 800.0f / 600.0f, 0.1f, 60.0f);
        effect_->setViewProperty(view);
        effect_->setProjectionProperty(proj);

        gd.SetVertexBuffer(vb_.get());
        for (const auto& obj : objects_) {
            if (!obj.visible) continue; // culled
            effect_->setWorldProperty(Matrix::CreateTranslation(obj.position));
            for (auto& pass : effect_->getCurrentTechniqueProperty()->getPassesProperty()) {
                pass.Apply();
                gd.DrawPrimitives(PrimitiveType::TriangleList, 0, primitiveCount_);
            }
        }
        // visibleCount_ tells you how many were drawn vs 200 total
        // (Game presents the frame after Draw() returns; no gd.Present() needed.)
    }

private:
    GraphicsDeviceManager         graphics_;
    std::unique_ptr<BasicEffect>  effect_;
    std::unique_ptr<VertexBuffer> vb_;
    int                           primitiveCount_ = 0;
    std::vector<SceneObject>      objects_;
    Vector3                       camPos_;
    int                           visibleCount_ = 0;
};