What is AABB? An AABB is an axis aligned bounding box. AABB vs AABB is a box vs box or bounding box collision detection. It’s mainly used in broadphase physics detection.

Assume that a center point and halfwidth extents or radius are the basic properties of an AABB (there are several methods to represent AABB structure).

This is a C++ code example for AABB structure:

struct AABB { AABB() : c(), r() {} AABB(const Point & center, const Point & halfwidths) : c(center) , r(halfwidths) {} Point c; // center point Point r; // halfwidths };

The bounding box (AABB) structure uses a Point class structure. Here is a C++ Point class example implementation:

struct Point { Point() {} Point( double x, double y, double z ) : x(x) , y(y) , z(z) {} double x = 0.0; double y = 0.0; double z = 0.0; double w = 0.0; const double operator[](const int idx) const { if (idx == 0) return x; if (idx == 1) return y; if (idx == 2) return z; if (idx == 3) return w; assert(0); } };

Now we can write a bounding box collision detection example in C++. We use a test to check if there is an overlap between the bounding boxes.

double Abs(double a) { return std::fabs(a); } bool testAABBAABB(const AABB &a, const AABB &b) { if ( Abs(a.c[0] - b.c[0]) > (a.r[0] + b.r[0]) ) return false; if ( Abs(a.c[1] - b.c[1]) > (a.r[1] + b.r[1]) ) return false; if ( Abs(a.c[2] - b.c[2]) > (a.r[2] + b.r[2]) ) return false; // We have an overlap return true; };

Read also:Simple Sphere-Sphere collision detection

*Update:*

There is a discussion in the comments about the validity of this test. There was a couple of issues raised.

**Only diagonally offset AABBs will pass the test**

There was a typo in the test making it not compilable, and it could have been misleading. The last parenthesis in the if-sentences where missing. This could have led one to believe all axes must pass the test. That is not true. If one axis is not intersecting, both AABBs aren’t intersecting at all. All axes must overlap to have an actual overlap.

**Must account for floating point precision errors**

There is no need to take floating point precision errors into account when you’re not comparing with equals (operator ==). When you’re using larger-than or lesser-than operators, you’ll only shift the error by whatever value you choose for you epsilon.

Read also:Sphere vs AABB collision detection

In corner cases, where axis aligned bounding boxes are aligned next to each other, you as a programmer have to decide the desired outcome. Where you’re simulating physics with moving bounding boxes, those errors are negligible. The only consequence is to have a positive test in “this frame” or the “next frame”.

I’ve also made some tests, based on the three versions (1 in the article, 2 in the comments). The source code is available at https://github.com/Studiofreya/code-samples/tree/master/physics.

The results from the test are:

AABB 1: AABB center(0 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(0 0 0) halfs(0.5 0.5 0.5) Post result 1 Anon result 1 CJM result 1 AABB 1: AABB center(0 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(1 0 0) halfs(0.5 0.5 0.5) Post result 1 Anon result 1 CJM result 1 AABB 1: AABB center(0 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(1.5 0 0) halfs(0.5 0.5 0.5) Post result 0 Anon result 1 CJM result 0 AABB 1: AABB center(0 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(15 0 0) halfs(0.5 0.5 0.5) Post result 0 Anon result 1 CJM result 0 AABB 1: AABB center(1 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(1 0 0) halfs(0.5 0.5 0.5) Post result 1 Anon result 1 CJM result 1 AABB 1: AABB center(1 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(1.5 0 0) halfs(0.5 0.5 0.5) Post result 1 Anon result 1 CJM result 1 AABB 1: AABB center(1 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(15 0 0) halfs(0.5 0.5 0.5) Post result 0 Anon result 1 CJM result 0 AABB 1: AABB center(1.5 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(1.5 0 0) halfs(0.5 0.5 0.5) Post result 1 Anon result 1 CJM result 1 AABB 1: AABB center(1.5 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(15 0 0) halfs(0.5 0.5 0.5) Post result 0 Anon result 1 CJM result 0 AABB 1: AABB center(0 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(0 1.5 0) halfs(0.5 0.5 0.5) Post result 0 Anon result 1 CJM result 0 AABB 1: AABB center(0 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(0 2.5 0) halfs(0.5 0.5 0.5) Post result 0 Anon result 1 CJM result 0 AABB 1: AABB center(0 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(0 3.5 0) halfs(0.5 0.5 0.5) Post result 0 Anon result 1 CJM result 0 AABB 1: AABB center(0 0 0) halfs(0.5 0.5 0.5) AABB 2: AABB center(15 15 15) halfs(0.5 0.5 0.5) Post result 0 Anon result 0 CJM result 0

The post and CJ have identical results. Do not use Anons test.

**Bonus**

Here is a SIMD-optimizied test, removing the conditional branches.

bool testAABBAABB_SIMD(const AABB &a, const AABB &b) { // SIMD optimized AABB-AABB test // Optimized by removing conditional branches bool x = Abs(a.c[0] - b.c[0]) <= (a.r[0] + b.r[0]); bool y = Abs(a.c[1] - b.c[1]) <= (a.r[1] + b.r[1]); bool z = Abs(a.c[2] - b.c[2]) <= (a.r[2] + b.r[2]); return x && y && z; }

Professional Software Developer, doing mostly C++. Connect with Kent on Twitter.

*

BlazeXJanuary 7, 2011What is the “float t;” for? You never use this var.

kentJanuary 7, 2011It can be safely removed.

It’s probably some leftovers from trying to do continuous collision detection (CCD).

geekygeniusMay 17, 2012Is is common to optimize this by changing around the order of the axis’s being checked? Like, check ZYX instead of XYZ if it makes more sense in a particular platform?

kentMay 17, 2012If you know there is a bigger chance of overlap on Z, then you can check Z first.

But I’d say there is a bigger benefit of testing in the order data is structured, because of code readability and CPU pipelining.

AnonymousJanuary 28, 2013Should be:

if ( Abs(a.c[0] – b.c[0]) > (a.r[0] + b.r[0]){

if ( Abs(a.c[1] – b.c[1]) > (a.r[1] + b.r[1]){

if ( Abs(a.c[2] – b.c[2]) > (a.r[2] + b.r[2]){

return false;

}

}

}

otherwise it will return false whenever the object is aligned on any of the axis, so the only time it will return true is when the object a is diagonally offset from object b. Here we are just checking to make sure that it is touching on all of the axis.

CJMarch 17, 2014THIS ALGORITHM WILL NOT WORK.

It’s disappointing that many will be mislead by this “solution,” since Google puts this very near the top of AABB overlap-detection searches.

The most obvious error is partially corrected by Anonymous, in that only a diagonally-offset AABB on all 3 axes will be considered a miss. However, his suggestion is incomplete, as you must check all axes INDEPENDENTLY. A more accurate answer would be the following:

bool xOverlap = true;

bool yOverlap = true;

bool zOverlap = true;

bool anyOverlap = false;

if (Abs(a.c[0] – b.c[0]) > (a.r[0] + b.r[0])) xOverlap = false;

if (Abs(a.c[1] – b.c[1]) > (a.r[1] + b.r[1])) yOverlap = false;

if (Abs(a.c[2] – b.c[2]) > (a.r[2] + b.r[2])) zOverlap = false;

anyOverlap = xOverlap && yOverlap && zOverlap;

`return anyOverlap;`

The above ANDs together the results of the 3 axes’ overlap tests, and will only return “true” if ALL THREE tests fail, indicating that overlaps cannot be ruled out on any axes. Just to clarify, in order for an overlap to occur, the AABB of A must be breached by B, and this scenario requires overlapping ALL THREE axes, otherwise it would have missed in some dimension.

However, we still do not have a complete solution, thanks to the lovely “gotchas” of floating point arithmetic. A workaround would be to use integers for our coordinates, but this would place a more stringent upper-limit on coordinates than floats or doubles, and also complicate physics calculations. So, sticking with floating point numbers for our coordinate system requires us to account for their fundamental imprecision. It is extremely unlikely that any two floats can be subtracted to equal EXACTLY 0. Although you may have initialized them both to 1.4, they are not represented as exactly 1.4 internally, they’re probably something like 1.4000000023 and 1.4000000017. Subtracting these numbers will obviously yield a nonzero result. Therefore, to account for this, you must define margins of error. You then consider AABBs to be overlapping if their bounds are within this margin of error of each other on a given axis.

I have to go do important things now, so I’ll leave the final, complete solution to the next poor sap.

kentMarch 19, 2014Hi CJ,

Thank you for taking your time to respond!

I’ll review this post and update it.

Kent

CJMarch 19, 2014Awesome!

I thought my post was doomed to obscurity, since the OP was over 4 years old. Thanks man!

kentJuly 4, 2014Hi CJ,

It took some time, but I’ve updated the post with more information and discussion about the tests.

benAugust 12, 2015Hey,

I’m trying to understand how this works and was just wondering what the half-width is.

Thanks is advance.

kentAugust 13, 2015Hi Ben,

The half-width is just half the length of each side stored in a

`Point`

.Think of it as from a center point in the box, having the half-widths as a

`Point`

, it’s the length to either of the sides.SogomnAugust 17, 2015This doesn’t work when the AABB is rotated, does it?

kentAugust 25, 2015Hi, AABB is an acronym for Axis Aligned Bounding Box.

That means the box is fixed to the axes, thus no rotation.