Pratyush Mohanty

Posted on Aug 31

The Math Behind Bounding Box Collision Detection - AABB vs OBB(Separate Axis Theorem)

#gamedev #unity3d

Collision detection is one of the most important building blocks in computer graphics, physics simulations, and game development. A common and powerful way to handle collision between complex shapes is to use bounding volumes, and among them, the bounding box provides a good balance between simplicity and efficiency.

In this article, we will first look at Axis-Aligned Bounding Boxes (AABB), then move on to Oriented Bounding Boxes (OBB), and finally show how the Separating Axis Theorem (SAT) allows us to detect collisions in 2D and 3D.

Axis-Aligned Bounding Box (AABB)

An Axis-Aligned Bounding Box (AABB) is the simplest bounding volume. It is a box aligned with the coordinate axes, which makes it very easy to compute but less flexible when objects rotate.

Checking whether an AABB intersects another AABB is similar to testing whether a point lies inside a box. The difference is that we must perform one test per axis, using the boundaries of both boxes.

For example, along the X-axis, we simply ask whether the intervals $[A_{minX}, A_{maxX}]$ and $[B_{minX}, B_{maxX}]$ overlap. If they do not overlap on any axis, the boxes are separated and thus not colliding.

Mathematical formula:

f(A, B) = (A_{minX} \leq B_{maxX} \wedge A_{maxX} \geq B_{minX}) \ \wedge (A_{minY} \leq B_{maxY} \wedge A_{maxY} \geq B_{minY}) \ \wedge (A_{minZ} \leq B_{maxZ} \wedge A_{maxZ} \geq B_{minZ})

This means the ranges must overlap along all three axes for the AABBs to collide.

In JavaScript, the check might look like this:

function intersectAABB(a, b) {
  return (a.minX <= b.maxX && a.maxX >= b.minX) &&
         (a.minY <= b.maxY && a.maxY >= b.minY) &&
         (a.minZ <= b.maxZ && a.maxZ >= b.minZ);
}

In C#, an equivalent implementation would be:

public struct AABB
{
    public float MinX, MinY, MinZ;
    public float MaxX, MaxY, MaxZ;

    public AABB(float minX, float minY, float minZ, float maxX, float maxY, float maxZ)
    {
        MinX = minX; MinY = minY; MinZ = minZ;
        MaxX = maxX; MaxY = maxY; MaxZ = maxZ;
    }
}

public static class Collision
{
    public static bool IntersectAABB(AABB a, AABB b)
    {
        return (a.MinX <= b.MaxX && a.MaxX >= b.MinX) &&
               (a.MinY <= b.MaxY && a.MaxY >= b.MinY) &&
               (a.MinZ <= b.MaxZ && a.MaxZ >= b.MinZ);
    }
}

This simple check is widely used in real-time applications because of its efficiency.

Oriented Bounding Box (OBB)

An Oriented Bounding Box (OBB) is a bounding box that can rotate with the object it encloses. It is defined by a center point, local axes, and half-extents. Because it can rotate, it fits shapes more tightly than an AABB. However, this makes collision detection more complex.

To check for collisions between OBBs, we use the Separating Axis Theorem (SAT).

The Separating Axis Theorem (SAT)

The SAT states:

Two convex shapes do not collide if and only if there exists an axis along which their projections do not overlap.

This means if we can find even a single separating axis, then the OBBs are not colliding. If no separating axis exists, then the OBBs must intersect.

Applying SAT in 2D (Rectangle vs. Rectangle)

For 2D OBBs (rectangles), possible separating axes are the edges of both rectangles. Since each rectangle has two unique directions, we only need to test four axes.

Steps:

Take the two edge directions of rectangle A and rectangle B.
Use them as candidate separating axes.
Project both rectangles onto each axis.
If projections fail to overlap on any axis, the rectangles do not collide.
If projections overlap on all four axes, they are colliding.

Applying SAT in 3D (OBB vs. OBB)

For 3D OBBs, the candidate separating axes are:

3 axes from OBB A,
3 axes from OBB B,
9 axes from the cross products of edges from A and B.

That makes a total of 15 axes. If projections overlap on all of them, the OBBs are colliding. If even one axis provides a gap, they are not.

The Projection Inequality (2D Example)

Let’s look at the math for testing overlap along one axis. Suppose we test along $A_x$ , an axis of rectangle A. The check is:

|T \cdot A_x| > W_A + |(W_B B_x) \cdot A_x| + |(H_B B_y) \cdot A_x|

Where:

$T$ is the vector from the center of A to the center of B,
$A_x, A_y$ are A’s axes,
$B_x, B_y$ are B’s axes,
$W_A, H_A$ are half-width and half-height of A,
$W_B, H_B$ are half-width and half-height of B.

The left-hand side represents the projected distance between the centers. The right-hand side represents the sum of the projected half-widths. If the distance is greater than the combined projection radius, the rectangles do not collide along this axis.

Computational Efficiency (FLOPs)

Each axis test requires only a handful of operations:

Dot products to compute projections,
Absolute values,
A few additions.

In total, a single axis test costs around 10–12 floating-point operations (FLOPs). In 2D, we only need around 40–50 FLOPs, while in 3D, testing 15 axes costs around 200 FLOPs. This is efficient enough for real-time collision detection.

Summary

AABB: Simple bounding box aligned with coordinate axes, tested with range overlap checks per axis.
OBB: Bounding box that rotates with the object, more accurate but requires SAT.
SAT: If a separating axis exists, shapes do not collide.
2D OBB: 4 axes need to be checked.
3D OBB: 15 axes need to be checked.
Efficiency: Only a few hundred FLOPs, practical for real-time use in games and simulations.

DEV Community