# AABB collision

13 replies to this topic

### #1bronxbomber92

New Member

• Members
• 10 posts

Posted 16 July 2007 - 02:27 PM

Quote

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?

### #2.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 16 July 2007 - 02:43 PM

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"
-
Currently working on: the 3D engine for Tomb Raider.

### #3bronxbomber92

New Member

• Members
• 10 posts

Posted 16 July 2007 - 02:45 PM

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?

### #4.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 16 July 2007 - 02:49 PM

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.
-
Currently working on: the 3D engine for Tomb Raider.

### #5.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 16 July 2007 - 02:57 PM

bronxbomber92 said:

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.
-
Currently working on: the 3D engine for Tomb Raider.

### #6bronxbomber92

New Member

• Members
• 10 posts

Posted 16 July 2007 - 03:05 PM

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.

### #7bronxbomber92

New Member

• Members
• 10 posts

Posted 18 July 2007 - 05:46 PM

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 :)

### #8.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 18 July 2007 - 11:20 PM

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).
-
Currently working on: the 3D engine for Tomb Raider.

### #9bronxbomber92

New Member

• Members
• 10 posts

Posted 19 July 2007 - 04:15 AM

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.

### #10anubis

Senior Member

• Members
• 2225 posts

Posted 19 July 2007 - 06:39 AM

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).
If Prolog is the answer, what is the question ?

### #11Reedbeta

DevMaster Staff

• 5344 posts
• LocationSanta Clara, CA

Posted 19 July 2007 - 04:40 PM

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.
reedbeta.com - developer blog, OpenGL demos, and other projects

### #12bronxbomber92

New Member

• Members
• 10 posts

Posted 20 July 2007 - 04:48 AM

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)

### #13.oisyn

DevMaster Staff

• Moderators
• 1842 posts

Posted 20 July 2007 - 10:02 AM

Reedbeta said:

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.
-
Currently working on: the 3D engine for Tomb Raider.

### #14Reedbeta

DevMaster Staff

• 5344 posts
• LocationSanta Clara, CA

Posted 20 July 2007 - 04:56 PM

.oisyn said:

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.
reedbeta.com - developer blog, OpenGL demos, and other projects

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users