frustrum culling

hi! until now i thought BSP’s together with portals is best way to make good 3D engine for games like 3D shooters, but… but recently i heard BSP’s are of no use nowadays - with present 3D accelerators - instead frustrum culling is what is implemented in modern games…could anyone explain me a bit on what it exactly does and if it’s really that good?

I do not believe BSP are no more usefull nowadays, everyone is still using them.
Frustum culling is a way to know if a point is inside the view frustum (a pyramid formed by the “viewable” space).
You can build a list of planes using the current matrix, then you check if a point it’s if front or on the back of a plane, so u can test if a point is in the visible space.

search mark morley tutorial, it’s easy to understand and a good point to start from.


You can also combine the frustum culling with a BSP tree to fast cull large portions of the static geometry. If the view frustum is completely in front of the current plane in the BSP tree you can cull the whole back tree, if it’s completely behind the plane you can cull the whole front tree. That’s how I’m doing it in my engine . While it doesn’t save any fillrate it does save loads of CPU time, and maybe more important, it saves lots of state changes. My framerate went from 120fps to 430fps in non fillrate heavy situations when I put frustum culling in there.

ok, i think i understand what frustrum culling is (in fact i’ve always been using this), but i still don’t understand why your (Humus) engine with frustrum culling is so much faster than without… cause i think when you send to openGL triangle to draw, openGL realizes on it’s own weather to draw it or not depending on where that triangle would appear on the screen - so it’s more or less same fast as your frustrum culling algorithm…or i don’t understand something?
ok, you could gain a bit performance when using frustrum culling with BSP tree - then you can faster decide whether to display or not bigger groups of polys, but even then this shouldn’t be so relevant improvement…
could you please explain what has exactly changed in your engine after adding frustrum culling? thx

[This message has been edited by Masm (edited 02-26-2002).]

surely you jest masm?..

by culling large slabs of geometry early on (as is the case using a BSP tree), you are not only reducing the work that OpenGL must do to clip away invisible triangles, you are saving memory bandwidth by not pushing a whole lot of useless crap over to the video card… this is the key principle behind frustum culling… it should not be performed on a per-primitive basis, but on an per-object basis.

using a BSP (or any other) tree gives a boost over and above simply culling by objects (an O(N) operation) by quickly eliminating large numbers of objects/primitives in the initial stages of culling (approaching O(logN) in many cases)

aside from the sheer volume of rendering you can save, the statement about saving on state changes is also valid… what use is it binding textures, setting up lights, etc and drawing geometry, only to have it entirely clipped away by OpenGL… expensive and pointless.

[edit] as an aside, I understand it is often even quicker at runtime to use a PVS in conjunction with a BSP tree (basically each node holds a list of other nodes that are visible from any point in that node), and frustum cull this subset rather than trverse the whole tree. Unfortunately PVS seems to involve quite a bit of pre-processing effort (how much i cant say, as I am yet to implement it in my own little octree project )

[This message has been edited by BadMmonkey (edited 02-26-2002).]

ok, ok… but i stilll can’t imagine improvement from 120 to 430 fps (as Humus writes) just by not sending all that invisible 3d stuff to openGL…

[This message has been edited by Masm (edited 02-26-2002).]

Originally posted by Masm:
[b]ok, ok… but i stilll can’t imagine improvement from 120 to 430 fps (as Humus writes) just by not sending all that invisible 3d stuff to openGL…

[This message has been edited by Masm (edited 02-26-2002).][/b]

Masm, imagine a nice little green and grassy land with hundreds of sheeps on it.
They all live nice together and have all the space they need on the large land.
However, on a bad day, the farmer comes.
He wants all sheeps to walk through the gate (or however you call that in english), but the gate isn’t wide enough…
The farmer pushes all sheeps through the gate at once, well… that’s a bit too heavy, because the gate doesn’t hold all those sheeps.
Result: Sheeps fall into the water under the gate and the farmer learned that you can’t push hundreds of sheeps at once through that gate.

Well, in 3d life, the gate is the memory bandwidth to the 3d card, and you are the farmer trying to push all those sheeps (triangles) at once over the gate.

Sounds like impossible to do?

You are totally right!

You cannot push all sheeps at once over the gate because the width of the gate is too limited.

Hope you understand it now

(and sorry for the weird english)

richardve, you’re a poet !


that was a classic answer richardve

to take that a bit further (hope you dont mind richardve), it is a waste of the farmers time trying to push a whole bunch of skanky diseased sheep through the gate, just so they can be shot when they get to the other side anyway. His time is better spent gathering up the healthy sheep, herding them through the gate, and leaving the others to their fate

This way, he can fit more healthy sheep through the gate, and thus have a bigger better flock of sheep on the other side (ie prettier graphics with higher poly-counts)

And no, it is not acceptable to just “get a bigger sheep gate”… new shiny sheep gates are expensive

hmmmm… after reading that back, maybe i need some sleep now

[This message has been edited by BadMmonkey (edited 02-26-2002).]

Originally posted by Masm:
ok, ok… but i stilll can’t imagine improvement from 120 to 430 fps (as Humus writes) just by not sending all that invisible 3d stuff to openGL…

Note that this improvement is only in situations where the fillrate/bandwidth isn’t too heavy. In my demo, before implementing frustum culling I’d get 120fps when looking straight into the roof with nothing but the black roof visible. That roof is too far from any light to be lit by anything, thus it get drawn without texture with the color black. But the state change overhead, cpu limitation, bus bandwidth or whatever it was did limit my fps to 120fps anyway. By putting the frustum culling in there I got rid of most of it though, pushing the framerate up to 430fps where it should be due to the very simple things getting drawn. Now in very fillrate limited situations the performance difference was much smaller, a few percent maybe.

thx all for answering…
and i like explanations the way richardve does very much
so finally frustrum culling is useful when having larger scene than our bandwidth can shelter…
but last question - does this mean openGL doesn’t draw polygon after sending it’s last vertex coordinates to it, but puts all informations on what we’re going to draw and draws this somehow later (after glEnd() or?)…