AABB and plane intersection test
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]
Just a thought, but you should check if any of the corners of the frustrum are inside the AABB as well.
AABox/Plane is very speedy with the nearest point trick, as fast as Sphere/Plane.
Imagine your AABox is :
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 :
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.
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.
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.
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.
In your post you had:
Did you mean:
And was the algorithm explicitly:
Because I think it would save loop iterations to use:
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.
[Edited by - Deebo on November 10, 2004 3:58:48 AM]
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; 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]
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:
Returning STRADDLE early will assume some AABB's are STRADDLE when the could be OUSTIDE. Looks like I answered my own post. :)
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. :)
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.
(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.
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement