13 replies to this topic

[bronxbomber92]

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.

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?

[.oisyn]

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"

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

[.oisyn]

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.

[.oisyn]

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.

[bronxbomber92]

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.

[bronxbomber92]

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

[.oisyn]

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

[bronxbomber92]

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.

[anubis]

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

[Reedbeta]

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.

[bronxbomber92]

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)

[.oisyn]

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.

[Reedbeta]

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