AABB

From DmWiki

An AABB is a Axis Aligned Bounding Box. Basically, it's a box used as a bounding volume to make a simplier approximation of a complex geometrical object in collision detection or ray tracing. The AABB is a rectangular box (2D, 3D, ...) that tightly fits the object to be bounded, and has as a requirement that the edges of the box must be parallel to the axes of space.

This page would benefit from the use of an image. You can help improve the article by creating one.

Table of contents

1 AABB representation 2 Test if an AABB contains a point 3 Creating an AABB from a mesh 4 Empty AABB 5 Collision of two AABB's, a.k.a separating axis test

AABB representation

This allows for a very easy representation. You only have to store the minima and maxima per axis. Let's do this in 2D; you can easily expand it to 3D.

Disclaimer: this code would obviously benefit of having some proper Point classes with operator overloading and all that.

struct Point
{
    float x;
    float y;
};

struct AABB
{
    Point min;
    Point max;
};

Test if an AABB contains a point

To know if some point (x, y) is in the AABB, you just check it against the minima and maxima

bool point_is_in_AABB(const AABB& aabb, const Point& point)
{
    return (point.x >= aabb.min.x && point.x <= aabb.max.x) &&
           (point.y >= aabb.min.y && point.y <= aabb.max.y);
}

That wasn't too difficult, was it?

Creating an AABB from a mesh

The cool thing is that it's very easy to create an AABB from a complex mesh. You just iterate over all vertices and determine minimum and maximum of x and y

AABB make_AABB(const Point* begin, const Point* end)
{
    AABB result;
    if (begin == end)
    {   // no points, empty box
        result.min.x = result.min.y = +1;
        result.max.x = result.max.y = -1;
        return result;
    }

    result.min.x = result.max.x = begin->x;
    result.min.y = result.max.y = begin->y;

    for (const Point* p = begin + 1; p != end; ++p)
    {
        aabb.min.x = std::min(aabb.min.x, p->x);
        aabb.min.y = std::min(aabb.max.y, p->y);
        aabb.max.x = std::max(aabb.min.x, p->x);
        aabb.max.y = std::max(aabb.max.y, p->y);
    }

    return result;
}

// ...
int num_vertices = 1000000;
Point* vertices = new Point[num_vertices];
// ...
AABB aabb == make_AABB(vertices, vertices + num_vertices);

Empty AABB

What's the deal with +1 and -1 in the previous code? Well, an AABB can have an empty state what means it doesn't contain any points. By setting the minima greater to the maxima (+1 > -1), there isn't a single point for which the function point_is_in_AABB will fail.

Collision of two AABB's, a.k.a separating axis test

To know whether two AABB's collide (or intersect), one might think it is sufficient to test if one of the corners of one box is contained by the others. That's not the case. But fortunately, it's even easier ... well ... at least cheaper :) The trick is to check if the centers are closer than half the sum of the sizes, per axis. Ok, that sounds crazy. Let's try again.

If, for all the axes, the centers of the boxes get closer than the sum of half their extents along that axis, then the boxes collide.

Or ... if, for all the axes, the doubled distance between the centers gets smaller than the sum of the full extents along that axis, than the boxes collide.

An image and some code might help.

This page would benefit from the use of an image. You can help improve the article by creating one.

bool do_collide(const AABB& a, const AABB& b)
{
    if (is_empty(a) || is_empty(b))
    {
        return false;
    }

    Vector sum_extents;
    sum_extents.x = (a.max.x - a.min.x) + (b.max.x - b.min.x);
    sum_extents.y = (a.max.y - a.min.y) + (b.max.y - b.min.y);

    Vector double_center_to_center;
    double_center_to_center.x = (b.min.x + b.max.x) - (a.min.x + a.max.x);
    double_center_to_center.y = (b.min.y + b.max.y) - (a.min.y + a.max.y);

    return fabsf(double_center_to_center.x) < sum_extents.x &&
           fabsf(double_center_to_center.y) < sum_extents.y;     
}

(ayqazi:) Alternatively, another way of doing it by doing a few simple comparisions (which I think evaluate to the same thing as the above method) is specified here: http://www.flipcode.com/articles/tp_issue01.shtml. Note the nice images in that link :-)