AABB collision

Bbcc6fa5b81ebe338e3e8cb2f2db01f1
0
bronxbomber92 101 Jul 16, 2007 at 14:27

Hi, I’ve read this article on the wiki: http://www.devmaster.net/wiki/AABB and I believe the article is incorrect about the AABB-AABB collision.

If for at least one axis, the centers of the boxes get closer than the sum of half their extents along that axis, than the boxes collide.

Doesn’t each axis need to pass this test to result in a collision, not just one?

13 Replies

Please log in or register to post a reply.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jul 16, 2007 at 14:43

You are correct, it’s worded the other way around

if for at least one axis, the condition […] does not hold, they do not collide.

Also, it should be “then”, not “than” :)

Bbcc6fa5b81ebe338e3e8cb2f2db01f1
0
bronxbomber92 101 Jul 16, 2007 at 14:45

Thanks! Do you know of a way to find if the intersection is just just where they clip/touch each other, or if one contains the other?

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jul 16, 2007 at 14:49

Btw, the make_AABB() code is also incorrect. They initialize the aabb to (+1,+1)-(-1,-1). But if the minimum of points of a particular axis is greater than +1, or if the maximum of points of a particular axis is less than -1, the box’ extents will not be updated, thus yielding an aabb that is not minimal enclosing the set of points.

.edit: I’ll make the required changes to the wiki… done.

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jul 16, 2007 at 14:57

@bronxbomber92

Thanks! Do you know of a way to find if the intersection is just just where they clip/touch each other, or if one contains the other?

I think the discription on that wiki page is overly complicated, because it’s really easy, and it is similar to what you are asking here. Boxes do not intersect if, for an axis, the minimum of box A is further away than the maximum of box B, or the other way around. In code:

bool boxesIntersect(aabb a, aabb :)
{
    return
        a.min.x > b.max.x || a.max.x < b.min.x ||
        a.min.y > b.max.y || a.max.y < b.min.y ||
        a.min.z > b.max.z || a.max.z < b.min.z;
}

Similarly, if box A is fully contained within box B, that means, for any axis, A’s minimum is larger-or-equal than B’s minimum and A’s maximum is less-or-equal than B’s maximum.
In code:

bool boxIsContainedWithinBox(aabb inner, aabb outer)
{
    return
        a.min.x >= b.min.x && a.max.x <= b.max.x &&
        a.min.y >= b.min.y && a.max.y <= b.max.y &&
        a.min.z >= b.min.z && a.max.z <= b.max.z;
}

Of course, this function only tests whether A is in B. If you want to test the other way around as well, swap A and B and call the same function.

Bbcc6fa5b81ebe338e3e8cb2f2db01f1
0
bronxbomber92 101 Jul 16, 2007 at 15:05

Thanks a lot! This is what I came up with:

int AABB::IntersectsAABB( const AABB& box )
{
    
    if( box.min.x >= min.x && box.max.x <= max.x &&
        box.min.y >= min.y && box.max.y <= max.y &&
        box.min.z >= min.z && box.max.z <= max.z )
    {
        return INSIDE;
    }
    
    if( max.x < box.min.x || min.x > box.max.x )
        return OUTSIDE;
    if( max.y < box.min.y || min.y > box.max.y )
        return OUTSIDE;
    if( max.z < box.min.z || min.z > box.max.z )
        return OUTSIDE;
        
    return INTERSECTS;
}

where INSIDE means this AABB contains box. OUTSIDE means no collision and INTERSECTS means they touch/clip each other.

Bbcc6fa5b81ebe338e3e8cb2f2db01f1
0
bronxbomber92 101 Jul 18, 2007 at 17:46

Is this correct for AABB-Plane?

bool AABB::IntersectsPlane( const CVector3D& normal, const float distanceFromOrigin )
{
    CVector3D diagMin, diagMax;
    
    if( normal.x >= 0 )
    {
        diagMin.x = min.x;
        diagMax.x = max.x;
    }
    else
    {
        diagMin.x = max.x;
        diagMax.x = min.x;
    }
    
    if( normal.y >= 0 )
    {
        diagMin.y = min.y;
        diagMax.y = max.y;
    }
    else
    {
        diagMin.y = max.y;
        diagMax.y = min.y;
    }
    
    if( normal.z >= 0 )
    {
        diagMin.z = min.z;
        diagMax.z = max.z;
    }
    else
    {
        diagMin.z = max.z;
        diagMax.z = min.z;
    }
    
    float test = DotProduct( normal, diagMin ) + distanceFromOrigin;
    if( test > 0.0f )
        return false;
        
    test =  DotProduct( normal, diagMax ) + distanceFromOrigin;
    if( test >= 0.0f )
        return true;
    else
        return false;
}

Thanks

Edit - I tested it, and it works great :)

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jul 18, 2007 at 23:20

Yes that is correct, but if you store the box using a center and an extents vector (center = 0.5 * (min + max), extents = 0.5 * (max - min)), it is somewhat easier:

bool AABB::Intersects(const Vector & normal, float dist)
{
    Vector absNormal(fabs(normal.x), fabs(normal.y), fabs(normal.z))

    float c = Dot(center, normal);
    float e = Dot(extents, absNormal);
    return dist < (c - e) || dist > (c + e);
}

The absNormal can be calculated very vast if you make use of SSE optimizations (simply bitwise AND the SSE vector register with 0x7fffffff 7fffffff 7fffffff 7ffffffff).

Bbcc6fa5b81ebe338e3e8cb2f2db01f1
0
bronxbomber92 101 Jul 19, 2007 at 04:15

Thanks for that! I don’t store my AABB like that, but I could do that if I calculated the Center and each extent (which I do for when calculating the position of my AABB…). Can you explain more what the SSE vector register is? I know *what* a register is, but I’ve never heard of the SSE register. It sounds architecture specific (ie, not portable). I’m on an Intel Mac and I want to target Windows, Intel Macs, PPC Macs, possibly linux, and the MIPS architecture (Sony PSP). So, keeping my code cross-platform is crucial.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Jul 19, 2007 at 06:39

SSE is an extension supported on Intel and AMD cpus, which allows you to execute a single instruction on four floating point values. So you could for example perform four dot products at once. An SSE register is just like a normal register, but it stores 4 single precision floating point values or 2 double precision values. It is rather expensive to set up such a register (loading data into it) but if you keep all of those registers working, you get very cheap and efficient floating point calculations (a lot of instruction finish in one to three cycles).

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jul 19, 2007 at 16:40

Also, a lot of other architectures have very similiar features, for instance PPC has the VMX/Altivec instructions, and I understand the PSP has a vector processor unit as well although it seems to be separate from the MIPS main processor. Of course you would have to write different code paths for each architecture, but the speedup that SIMD (single instruction, multiple data) processing can give your graphics routines shouldn’t be underestimated.

Bbcc6fa5b81ebe338e3e8cb2f2db01f1
0
bronxbomber92 101 Jul 20, 2007 at 04:48

Thanks for the explanation. I do know the PSP has the VFPU (http://wiki.fx-world.org/doku.php and http://mrmrice.fx-world.org/vfpu.html)

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Jul 20, 2007 at 10:02

@Reedbeta

Of course you would have to write different code paths for each architecture

Not really, we have a math library with common operations that are optimized for each platform (thanks to the compiler intrinsics available on most implementations like VC++ and gcc). Regular code that makes use of vector/matrix math just uses these classes and is out-of-the-box optimized for every platform :). It helps that SSE, VMX and SPU vector code (PS3) are pretty much the same thing.

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Jul 20, 2007 at 16:56

@.oisyn

Not really, we have a math library with common operations that are optimized for each platform (thanks to the compiler intrinsics available on most implementations like VC++ and gcc).

Yep, we are doing the same thing. :) It still might be necessary to do something special for the PSP though, I don’t know enough about it to say.