Simple AABB vs AABB collision detection

By , last updated October 8, 2016

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.

Comments

  1. BlazeX January 7, 2011 Leave a Reply

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

  2. kent January 7, 2011 Leave a Reply

    It can be safely removed.

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

  3. geekygenius May 17, 2012 Leave a Reply

    Is 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?

  4. kent May 17, 2012 Leave a Reply

    If 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.

  5. Anonymous January 28, 2013 Leave a Reply

    Should 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.

  6. CJ March 17, 2014 Leave a Reply

    THIS 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.

    • kent March 19, 2014 Leave a Reply

      Hi CJ,

      Thank you for taking your time to respond!

      I’ll review this post and update it.

      Kent

      • CJ March 19, 2014 Leave a Reply

        Awesome!

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

        • kent July 4, 2014 Leave a Reply

          Hi CJ,

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

  7. ben August 12, 2015 Leave a Reply

    Hey,

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

    Thanks is advance.

  8. kent August 13, 2015 Leave a Reply

    Hi 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.

  9. Sogomn August 17, 2015 Leave a Reply

    This doesn’t work when the AABB is rotated, does it?

    • kent August 25, 2015 Leave a Reply

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

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

Leave a Reply


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*