# AABB and plane intersection test

## Recommended Posts

Deebo    128
Currently, for my octree-frustum test code, I test the AABB against all 6 frustum planes. I consider the AABB inside as soon as one of it's corners is found inside the positive halfspace of any plane. Now I am ready to upgrade my frustum-octree intersection test code. I have been looking for a information on a fast method for doing this. I need it to return inside, outside, or intersecting. I have googled but can't find exactly what I am looking for. Anyone have any resources or know a way of doing this? [Edited by - Deebo on November 8, 2004 7:54:57 AM]

##### Share on other sites
LilBudyWizer    491
Just a thought, but you should check if any of the corners of the frustrum are inside the AABB as well.

##### Share on other sites
Charles B    863
AABox/Plane is very speedy with the nearest point trick, as fast as Sphere/Plane.

struct AABox{ float x[2], y[2], z[2]; };// Get the sign bits.sx = (*(uint32*)Plane.x)>>31;sy = (*(uint32*)Plane.y)>>31;sz = (*(uint32*)Plane.z)>>31;dmin = Plane.x*Box.x[sx] + Plane.y*Box.y[sy]+ Plane.z*Box.z[sz] + Plane.w;sx^=1; sy^=1; sz^=1;dmax = ...;

Now it's easy to have a generic routine that tests an AABox against a convex and returns OUTSIDE, INSIDE or STRADDLE.

- If one of the planes is separating (dmin>0), then OUTSIDE.
- If dmax is negative for every plane, then the AABox is fully INSIDE.
Else you can respond INTERSECTING (or STRADDLES).

So the pseudo code is something like this :

flag = INSIDE;for( each plane ){  if( dmin > 0 ) return OUTSIDE;  if( dmax > 0 ) flag = STRADDLE;}return flag;

Note that the algo is not complete. It tests vertices against planes. It does not test edges versus edges. So in some rare cases, the algo returns STRADDLES, while it should return OUTSIDE. But it's harmless for octree/quadtree culling. The algo is conservative.

Note that once one octree node AABox is known as fully inside you can flag a boolean (bCulling = false) and avoid the tests for the children.

##### Share on other sites
Charles B    863
Quote:
 Original post by LilBudyWizerJust a thought, but you should check if any of the corners of the frustrum are inside the AABB as well.

I did not mention it but the algo should start with an AABox/AABox conservative test. This solves this issue (frustum inside huge AABox). This also deals with the cases where AABox planes reject frustum vertices on one side of the box.

EDIT :
If you wish to find additional data, here is a pointer to another related GameDev thread,

##### Share on other sites
Deebo    128
Thanks alot for the info and especially the link. Some good info there. I was about to give up on a reply and just count how many corners were on which side of the plane, then test all the possibilities to see if it was in/out/intersecting. Im gonna give this a try and see how it works. Thanks.

##### Share on other sites
Deebo    128
sx = (*(uint32*)Plane.x)>>31;

Did you mean:
sx = (*(uint32*)(&(Plane.x))>>31;

And was the algorithm explicitly:
flag = INSIDE;for( each plane ){  if( dmin > 0 ) return OUTSIDE;  if( dmax > 0 ) flag = STRADDLE;}return flag;

Because I think it would save loop iterations to use:
for( each plane ){  if( dmin > 0 ) return OUTSIDE;  if( dmax > 0 ) return STRADDLE;}return INSIDE;

Here is what I have come up with based on your code. I can't test it yet because I am rewriting some other parts of the engine. Just wanted to see if you can spot any obvious error before this thread is dead.
TFrustumAABBTest TestOctreeNode(const COctree* const pNode) const{	CHECK(pNode != 0)	const TBounds&		b = pNode->m_Bounds;	TFrustumAABBTest	retval = Inside;	// test the octree's cube against each side of the frustum	for(u32 i = 0; i < 6; i++)	{		const CVector3D& p	= m_Sides[i];		const u32	sx	= (*((u32*)(&(p.x)))) >> 31;		const u32	sy	= (*((u32*)(&(p.y)))) >> 31;		const u32	sz	= (*((u32*)(&(p.z)))) >> 31;		const _float	min	= p.x * b.x[sx] + p.y * b.y[sy] + p.z * b.z[sz] + p.w;		if(min > 0.0f)			return Outside;		const _float	max	= p.x * b.x[sx ^ 1] + p.y * b.y[sy ^ 1] + p.z * b.z[sz ^ 1] + p.w;		if(max > 0.0f)			return Intersecting;	}	return Inside;}

[Edited by - Deebo on November 10, 2004 3:58:48 AM]

##### Share on other sites
Deebo    128
Wow, I really need to catch up on some sleep. I looked at my post a second time and realize that the loop should be:
flag = INSIDE;for( each plane ){  if( dmin > 0 ) return OUTSIDE;  if( dmax > 0 ) flag = STRADDLE;}return flag;

Returning STRADDLE early will assume some AABB's are STRADDLE when the could be OUSTIDE. Looks like I answered my own post. :)

##### Share on other sites
LogicalError    293
also, suppose you have a tree of bounding boxes
(or basically just a bounding box inside another bounding box)

if the parent bounding box is completely inside or outside the frustum, you *know* that the child bounding box is completely inside or outside, so you don't have to test it again.

if the parent bounding box intersects a couple of planes, then you only have to check the child bounding box against -those- planes, since you already know that you're not intersecting the other planes

ofcourse this only applies if the child bounding box is INSIDE the parent bounding box and is not INTERSECTING the parent bounding box

but it's a good way to speed up octtree/frustum testing for example.

##### Share on other sites
Charles B    863
Quote:
 Original post by DeeboWow, ....return flag;

Glad you saw it by yourself ...

EDIT :
and ...

sx = (*(uint32*)(&(Plane.x))>>31;
... yes you were totally right to correct me on this typo (dereferencing an object). I wrote it very quickly since I know the algo by heart.

Also it would be cleaner to replace it by something like :

sx = sign_bitf(Plane.x);

where sign bit does the same in an inline function, in a header. Why ? Because in rare cases, floats may not follow the IEEE 754 standard. Some consoles, or weird machines, may use some kind of fixed point and have float emulations in the CRT (C Runtime library). I got spanked once for this in my carrier. So then you just change the code in one place, and it keeps portable.

[Edited by - Charles B on November 18, 2004 7:56:06 PM]