Sign in to follow this  
Deebo

AABB and plane intersection test

Recommended Posts

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 this post


Link to post
Share on other sites
AABox/Plane is very speedy with the nearest point trick, as fast as Sphere/Plane.
Imagine your AABox is :


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 this post


Link to post
Share on other sites
Quote:
Original post by LilBudyWizer
Just 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,
linky.

Share this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
In your post you had:
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Deebo
Wow, ....
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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this