Patrick's Blog

Bites: Axis-Aligned Bounding Boxes (AABB)

Bites: Simpler posts with bits of info. Sort of intended to be used as a reference for myself.

AABB

Axis-aligned bounding-boxes (AABB) are useful for things like frustum culling and collision detection. It's generally a fairly conservative representation but works well-enough for a few applications.

Generally an AABB is calculated in model space when importing your meshes:

class AABB3f {
    Vector3f min;
    Vector3f max;
    AABB3f(const Vector3f& _min, const Vector3f& _max) : min(_min), max(_max) {}
public:
    AABB3f() // Init max as min and min as max
        : min(std::numeric_limits<float>::max(), std::numeric_limits<float>::max(), std::numeric_limits<float>::max())
        , max(std::numeric_limits<float>::lowest(), std::numeric_limits<float>::lowest(), std::numeric_limits<float>::lowest())
    {}

    static AABB3f FromMinMax(const Vector3f& _min, const Vector3f& _max) {
        return AABB3f(_min, _max);
    }

    void Update(const Vector3f& v) {
        // Element-wise min and max
        min.x = std::min(min.x, v.x);
        min.y = std::min(min.y, v.y);
        min.z = std::min(min.z, v.z);
        max.x = std::max(max.x, v.x);
        max.y = std::max(max.y, v.y);
        max.z = std::max(max.z, v.z);
    }
    Vector3f GetMin() { return min; }
    Vector3f GetMax() { return max; }
};

std::vector<Vector3f> modelVertexPositions = ...; // Populated somewhere else...

AABB3f modelAABB;

for (const auto& vertex : modelVertexPositions) {
	modelAABB.Update(vertex);
};

Be careful when transforming this into other spaces, namely world space. There's no guarantee that the transformed min/max will be valid. For example, rotating the AABB means it's potentially no longer axis aligned, or the actual min/max are no longer the min/max in world space. Let's say our model-to-world transform is a simple 180 degree rotation around the Z-axis:

// Our box is a simple 2x2x2 AABB centered in model space
AABB3f aabb = AABB3f::FromMinMax(Vector3f(-1.0f, -1.0f, -1.0), Vector3f(+1.0f, +1.0f, +1.0));
// I didn't have a Matrix3f class on hand when writing this so 
// ignore the homogeneous coordinate :)
Vector4f min(aabb.GetMin(), 1.0f);
Vector4f max(aabb.GetMax(), 1.0f);
// When we rotate 180 degrees around Z, we essentially 
// will flip the signs of the X and Y components:
Matrix4f zRotate = Matrix4f::MakeRotateZ(deg2rad(180));
Vector4f newMin = zRotate * min;
Vector4f newMax = zRotate * max;

std::cout << std::format("newMin: {}, {}, {}\n", newMin.x, newMin.y, newMin.z);
std::cout << std::format("newMax: {}, {}, {}\n", newMax.x, newMax.y, newMax.z);

The result is still axis-aligned, but the min/max relationship no longer holds:

newMin: 0.99999994, 1.0000001, -1
newMax: -0.99999994, -1.0000001, 1

Not exactly 1.0f or -1.0f due to floating point precision errors

What you want to do is actually recalculate the AABB. Naively you could just loop over all world space mesh vertices like you originally did in model space, but generally you're entering real-time territory by the time you get to world space, so this approach is infeasible.

A somewhat inefficient but straightforward approach is to first extract the 8 corners of the box that the untransformed min/max implicitly represent, apply the transform to each, and then use our Update() function to re-compute the AABB by looping over those 8 transformed corners:

const std::array<Vector4f, 8> transformedPoints = {
      zRotate * min
    , zRotate * Vector4f(max.x, min.y, min.z, 1.0f)
    , zRotate * Vector4f(min.x, max.y, min.z, 1.0f)
    , zRotate * Vector4f(min.x, min.y, max.z, 1.0f)
    , zRotate * Vector4f(max.x, max.y, min.z, 1.0f)
    , zRotate * Vector4f(min.x, max.y, max.z, 1.0f)
    , zRotate * Vector4f(max.x, min.y, max.z, 1.0f)
    , zRotate * max
};

AABB3f transformedAabb;
for (const Vector4f& point : transformedPoints) {
    transformedAabb.Update(Vector3f(point.x, point.y, point.z));
}

std::cout << std::format("Transformed Min: {}, {}, {}\n", transformedAabb.GetMin().x, transformedAabb.GetMin().y, transformedAabb.GetMin().z);
std::cout << std::format("Transformed Max: {}, {}, {}\n", transformedAabb.GetMax().x, transformedAabb.GetMax().y, transformedAabb.GetMax().z);

We get the same exact result as the original min/max because all we did was rotate the box 180 degrees:

Transformed Min: -1.0000001, -1.0000001, -1
Transformed Max: 1.0000001, 1.0000001, 1

There is a much more efficient way, however, which involves only computing a few sums. It's described in 3D Math Primer for Graphics and Game Development. There's no need to rehash that explanation here.

Neither of these approaches usually results in an optimal AABB in the transformed space as the book points out, but it's typically good enough.

Some other useful functions include getting the center and radius:

Vector3f GetCenter() {
    return (max + min) * 0.5f; // Midpoint formula
}
float GetRadius() {
    return ((max - min) * 0.5f).Length();
}

std::cout << std::format("Center: {}, {}, {}\n", transformedAabb.GetCenter().x, transformedAabb.GetCenter().y, transformedAabb.GetCenter().z);
std::cout << std::format("Radius: {}\n", transformedAabb.GetRadius());

Center: 0, 0, 0
Radius: 1.7320509 // sqrt(3)

This gives a bounding sphere that is non-optimal (think about the case where none of the mesh vertices coincide with the AABB corners), but still useful as a conservative representation. It's better to think of it as a bounding sphere of the AABB, not the original mesh.