Archived

This topic is now archived and is closed to further replies.

Palidine

Frustum Culling Bounding Boxes

Recommended Posts

Alright, i've got a bit of a theoretical non-comprehension about frustum culling of axis-aligned bounding boxes. I understand that the prevailing practice is to test each of the 8 vertices of the box agains the 6 planes of the frustum. cool no problem. What gives me pause is the assumption that if all 8 vertices are outside of the frustum, then the box is not visible. I can think of plenty of rotations of the frustum in which the frustum intersects the bounding box but does not contain any of it's vertices. how do people deal with that case? is it just ignored, b/c it's not as likely? or do people also run a sphere check on the box, using the boxes's center point and 1/2 a side length as the radius (for cubes), and an ellipse for boxes? also, for the case where the bounding box is much much bigger than the frustum, do you have to check to see if any of the frustum vertices are inside the bounding box? i've looked at several tutorials and theoretical explainations of this type of culling, but they all seem to either gloss over these issues or to not explain them in sufficient theoretical detail for me to be satisfied. -me [edited by - Palidine on July 30, 2002 2:10:30 PM]

Share this post


Link to post
Share on other sites
When you are testing a bounding box (regardless of whether it is axis-aligned or not) against the frustum, you are really wanting to find out if the vertices of the box lie on the inside of all the frustum planes (in the case of the box being totally inside the frustum), or if the vertices of the box lie on both sides of any of the planes (in the case that the box is partially inside the frustum... this also includes the box enclosing the frustum).

As you probably know, the trivial case for rejecting a box is when all vertices of the box lay outside any one plane of the frustum. With all these cases combined, you cover pretty much everything, but there is one catch... it can produce some false-positives (ie when a box has vertices which lie inside some of the planes, but the actual box does not intersect the frustum... sorry its kinda hard to explain that without a picture)

Anyho, to avoid this you could test the bounding sphere of the frustum (wildly inaccurate, i know) with the bounding sphere of the node, then perform the usual box/frustum tests if this passes. In actual fact, its probably more expensive to try and perfectly detect these false-positives than it is to just accept them and move on

I hope that wasn''t simply a vague rehash of what you already know
Just as an aside, what I did for my frustum intersction tests with an octree was:

  
test bounding sphere of node against frustum
if completely outside
{
reject it
}
else if completely inside
{
include it with no further testing of children
}
else
{
if this node has children
{
recurse to children
}
else // only resort to bounding box test on leaves which are partially intersecting

{
test bounding box of node against frustum
if completely outside
{
reject it
}
else
{
include it
}
}
}

I have found this to be nice and quick, and it satisfactorily covers possible visibility cases (well good enough for my liking)

BTW: the radius of the bounding sphere for a node should really be the distance from the centre to any corner/vertex (not half the side length), otherwise the sphere doesn''t enclose the whole box.

Share this post


Link to post
Share on other sites
thanks for the reply. you solved my problem, though perhaps not in the way you think

i was being too literal and thinking of the 'planes' of the frustum as limited planes and not as infinite planes. So i was imagining boxes that were intersected by an edge of the frustum, without having any of their vertices inside the bounded area. but since the planes are infinite as far as the equations are concerned, that condition, and the condition where the frustum is contained by a box, do not have the reprecussions that i was thinking they did.

sad when you think stupidly and are caught at it in a public forum

for whatever reason that "vague rehash of what you already know" was phrased perfectly to snap me out of my loop.

tks.

-me

[edited by - Palidine on July 31, 2002 1:18:44 AM]

Share this post


Link to post
Share on other sites