Frustum Culling - Does this sound about right?

Before I go and turn my pages of hand-written notes into code, can anyone comment on this and let me know if I’m on the right track?

I need to test a bounding box against the current view frustum. I don’t need to differentiate between boxes that are partially in the frustum and totally in the frustum, they can either be rejected completely or they need further processing. Speed is, of course, of the essence.

So… here’s what I’ve come up with. I know how to code all this, I just want to know if it makes sense to you experts.

  • I extract the equations for the 6 planes of the frustum from a concatenation of the current projection and modelview matrices. I only do this if/when the “camera” moves.

  • Given a bounding box with 8 vertices, I loop through all 6 planes doing the following:

  • Loop through the 8 vertices, calculating the distance of the vertex from the plane. A positive distance means it’s in front of the plane (or outside of the frustum) while a negative value means it’s behind the plane (possibly inside the frustum). If I find a vertex that is behind the plane, then I can refrain from testing the remaining vertices (if any) because at least some part of the bounding box is behind the plane.

  • If all 8 vertices are in front of any of the six planes, then I can refrain from testing against the remaining planes because it’s totally outside the frustum.

  • If, for each plane, at least one vertex is behind the plane, then some portion of the box is visible and it cannot be rejected.

Does this sound about right?

Testing a bounding sphere would be similar, faster in fact, since I only have to test a single point and compare the distance from the plane to the sphere’s radius.

Toom

[This message has been edited by Toom (edited 12-01-2000).]

Could you possibly post some of that code? I know to some it may be simple, but I am trying to do just that, and I can’t seem to get it right. I really don’t know how to extract the frustrum planes fromthe ModelView Matrix. That would be GREAT help!

Well at this point I’ve just collected info from various resources and thought it out on paper. I haven’t written the code yet, but I know how to. I’m trying to get feedback on the overall algorithm before coding it - someone might tell me that it’ll be far too slow, or that it won’t work at all.

If/when I do code it I’ll summarize it all in a paper and put it online somewhere though (if anyone is interested).

Toom

Depending on your hardware, it may be more
efficient (or at least less hassle) to fully
render any object that at least partially
intersects the viewing frustum.

I e download all your vertexes to graphics
memory or AGP memory, and then fire them
wholesale when you know they’re close enough
to matter. The speed-up from being able to
use static geometry parts is probably much
bigger than the slow-down from drawing a
few hundred vertexes too many.

Yeah, that’s pretty much what I was thinking. I’m just going to cull space using an octree, then individual objects based on their bounding sphere. If any part of an object is potentially visible I’ll send the whole thing (or a variation of it based on LOD) down the pipeline and let OGL cull individual polygons.

Toom