Edge cases of a bounding box vs the view frustum

Recommended Posts

Nextgenneo    122
So I've implemented the basic view frustum culling algorithm but in my case the edge case of counting bounding boxes completely out of the frustum in is really effecting performance. Here's an image of what I am referring to: With the basic test the orange box is recorded as intersecting. Whats the fastest way to test for this case? Thanks

Share on other sites
Codeka    1239
I would imagine the simplest way would be to calculate a plane which is perpendicular to the far plane and where the far plane intersects with the frustum, and if the box is on the other side of that plane, cull it.

I hope you can understand what I wrote in that last paragraph without a diagram :-)

But I can't imagine there'd be all that many cases where this would actually have any effect... unless your bounding boxes are really huge, which kind of defeats the purpose (use an octree in that case).

Share on other sites
Nextgenneo    122
in more specific terms I am looking for exact frustum culling of an AABB.

and yeah, the above does make sense and I will implement this but is there a faster way?

Share on other sites
Nextgenneo    122
well I've researched it and I need to do a Separating Axis Test. I've figured out how to do this for an OBB and OBB but am not sure about a Frustum and an OBB.

Thanks

Share on other sites
LogicalError    293
see:
"Optimized View Frustum Algorithms for Bounding Boxes"

here:
http://www.ce.chalmers.se/~uffe/vfc_bbox.pdf

it contains the fastest AABB-frustum intersection testing algorithm that i know of.

Share on other sites
dave    2187
It's outside the frustum when all of the points of the AABB are outside of the same side.

Share on other sites
LogicalError    293
Quote:
 Original post by DaveIt's outside the frustum when all of the points of the AABB are outside of the same side.

Unless the frustum is inside the AABB...

Share on other sites
Nextgenneo    122
Hi. Thanks for the replies and these are what I am currently implementing for my basic VF culling.

However let me show you the bug with some screenshots. I've captured what is drawn and the corresponding view frustum. The first screen shot is with the camera directly above the terrain and not rotated. The terrain is made up of concentric rings of increasing size (each ring made of 4 parts). You can see it correctly culls everything. I've also drawn the VF intercepts with the XZ Plane.

However when I rotate the camera as shown here the culling gets all messed up. I am fairly sure this is to do with the corner of the VF case and because my bounding box double in size every ring it causes lots of problems.

Any ideas?

Share on other sites
Codeka    1239
I think it might help if you also draw the bounding boxes. From what I can tell, the bounding box goes around a "ring" of the terrain, so the larger rings' bounding boxes actually go around the entire frustum, hence they're not being culled. That's what you would expect.

I think you need to break the terrain up differently -- i.e. not concentric rings, but instead into blocks. You could still use your current layout, but instead of one bounding box for the whole ring, you have 4 - one for each "side".

At least, that's assuming I'm understanding the situation here...

Share on other sites
Nextgenneo    122
Hi,

Sorry for not being clear enough. I've updated one of the screenshots to include some quickly drawn bounding boxes. So yeah, I split the rings into 4 rectangles.

Share on other sites
Nextgenneo    122
Here's a perfect example of this edge case I am referring to. The pink rectangle is the shape bounding box being culled and the black 3d trap is the view frustum. This VF returns intersecting with that bounding box when the bounding box is clearly outside.

If you extend the VF planes in your head you can see its the edge case (orange rectangle) in the originally post.

Share on other sites
Rockoon1    104
Quote:
 Original post by DaveIt's outside the frustum when all of the points of the AABB are outside of the same side.

While this is true, it doesnt cover all outside cases.

No false negatives, but some false positives.

For example in the first post the orange rectangle is not in the frustum but is also is not classified correctly by this rule.

Share on other sites
dave    2187
Quote:
Original post by LogicalError
Quote:
 Original post by DaveIt's outside the frustum when all of the points of the AABB are outside of the same side.

Unless the frustum is inside the AABB...

No. If the frustum is inside the AABB then how can all of the points of the AABB be on the same side of any of the frustum sides.

Share on other sites
Nextgenneo    122
you're rule is fine except it does create false positives like the orange box in the first example or the pink rectangle above. this is why I need EXACT View Frustum culling.

Share on other sites
KRIGSSVIN    172
Search for BoxOnPlaneSide in Doom3, Q2 or Q3 code.

Share on other sites
Rockoon1    104
A little epiphany here

While the rule "It's outside the frustum when all of the points of the AABB are outside of the same side of the frustum" isnt sufficient..

...you can also use the rule "It's outside the AABB when all points of the Frustum are outside the same side of the AABB"

These rules (combined) at least covers the specific false positive detailed in the original post, and may possible handle most/all false positives.

Share on other sites
Nextgenneo    122
Quote:
 Original post by Rockoon1A little epiphany hereWhile the rule "It's outside the frustum when all of the points of the AABB are outside of the same side of the frustum" isnt sufficient.....you can also use the rule "It's outside the AABB when all points of the Frustum are outside the same side of the AABB"These rules (combined) at least covers the specific false positive detailed in the original post, and may possible handle most/all false positives.

oooooo. this makes total sense in my mind. will implement this tomorrow and I expect it to work. awesome.

Share on other sites
Rockoon1    104
Quote:
 Original post by Nextgenneooooooo. this makes total sense in my mind. will implement this tomorrow and I expect it to work. awesome.

Indeed, I now think that it will work flawlessly for all convex geometry..

I'm wondering if as combined they are equivilent to a seperating axis test tho, expressed slightly differently but essentialy implemented the same..