Object Culling

Hi there !

I have been reading several article on culling and there is something I can’t figure out.

I am talking here about view frustrum culling (by the way, how the hell do I do that ?! )

Imagine I have a STATIC scene of 350000+ triangles with something like 1000 objects.

Everybody says that a STATIC scene should be rendered in a display list (and that’s what I do by the way !).

Would I gain anything by stopping using display lists and start doing view frustrum culling ??? Obviously not in the case where all objects are visible at once but…

Well, I think the question is : when you render such a scene, is there a more efficient way than putting everything into a display list ? For information, the scene I am talking about is an open-space (vr model of a construction site) so I am not sure either if BSP-trees could be useful here…

Any hints welcome !


hi eric.

i think yes, anything at the application stage wich prevents things to be sent to opengl is good.

about view frustum culling, i currently use a solid angle approach: i consider the frustum to be a cone, wich is a good approximation, for a 4:3 window.
all you have to do is take a point in eye 3-space, then operate a test like this:

if(xx+yy>zzk) culled
else visible

i use this because i have access for free to the squared distance from screen center.

to operate a real view frustum cull, you could start with the same point in eye 3-space, and do some tests:

if(z>0) culled;
if( abs(x) > -zw ) culled;
if( abs(y) > -z
h ) culled;

w and h represent the aperture of your frustum: it depends on the tangent of the aperture half angle, since for a 90 degrees fov in either directions, w and h = 1.

i’ve employed this approach somewhere, but i don’t exactly remember the exact formula to obtain w and h.
you could recalc it from scratch, or wait until i’ve done it for myself

but probably you need something more resembling to a frustum-sphere collision detector… i’ve never done it.
to cull objects, i simply enlarge the solid angle and cull away the 80% of the geometry.
the opengl clipper will do the rest.


Another way to do it, if you use distance from the view point as a key, is to decide on what distance you want to cull at (say 2500.0f). You calculate a point that represents the approximate centre of your frustum (if your frustum is 0.5f, -0.5f, 0.5f, -0.5f, 1.0f, 5000.0f then this point is 2500.0f in front of your camera location).

For each object you then calculate the distance from the calculated point to the center of the object. Use Pythagora’s - don’t square root the value to get C (or D) just compare the SQUARED value to the square of the distance you are clipping to (2500.0f * 2500.0f).

For asthetic reasons it is wise to use a clipping distance equal to 1/2 of the distance from your near plane to the far plane of the frustum (hence 2500 in the above example).

I have used this with great success. I have a display list for my objects (Eg. trees) and do this calc before drawing each one. If they pass then I do the transformations and draw the “Tree” display list. Hope this make sense.

Hi guys.
I have something to say here.
I’m currently working on octrees for my own project and I recommend it.
It’s a great way to do frustum culling for large scale open level (like big outside terrain…)
The goal is simple : Eliminate what you don’t see real fast by dividing your whole world in 8 parts and then divide each part into 8 other parts and again and again until you’ve reached the desired subdivision level.

for a huge level you’ll eliminate like the 3/4 of the level in one pass…
I recommend you do a little search for yourself to have the right explaination on how octrees work because I’m not a real pro with octrees, I’m working on it right now and it’s about to work but not yet.

wait a minute…
I just remembered a good site where I learned about octress http://www.gametutorials.com/
check there for good octree tutorials.

Hope it helps !

Let’s have a funny day

one more thing…
it’s always important to send the minimum number of instructions to opengl because graphics operations are slow.

so it’s recommended to do good culling (because math operations are really fast) to send the minimum geometry to opengl.

Let’s have an happy day

I want to add something as well

Culling is nice, but you shouldn’t overburden your processor with it. Any T&L hardware can clip lots of polys pretty fast and that’s what you really want to optimize for.

So you should divide your static scene into smaller pieces. Yes, you can of course keep the smaller pieces in display lists, just don’t put the whole scene into one huge display list.

For the T&L optimization thingy, only coarsely divide your scene, say, at least 2k polys per display list, probably larger. Then make it so that you can cull them pretty fast, create bounding spheres for the lists and cull them against a view cone instead of a true frustum. This will be a lot easier on the processor and instead puts the load on the graphics card which should be able to handle it.

This is probably not a good idea for cards without T&L hardware, so you may have to make a tradeoff in list size if you want to support these. I think 2k polys per list are a good starting point.

Guys, thanks for the info but I just have one question: how did you come accross this topic which was started in April 2000 ???

Anyway, I am happy, that is my 1000th post here !



that’s really funny…
why the hell did I answered to that post haha
I’m pretty sure it was in the first page on the advanced forum…

Let’s have a funny day

Just to continue the longest conversation in history…
I believe this guy is on to a good thing, regarding terrain culling:- http://chat.carleton.ca/~eszoka/tstriplod/tstrip.htm

He’s using a polygon rasterizer kind of approach

knackered: I believe this guy is on to a good thing, regarding terrain culling:- http://chat.carleton.ca/~eszoka/tstriplod/tstrip.htm

I wasn’t that impressed. If you read the paper it only does distance based LOD. When he tried to use it for geometric LOD (error values etc) it was slower than ROAM. Terrain LOD just doesn’t tri-strip well I guess.

  • mib

Terrain topology error metric in the LOD algorithm slows it down to the crawl. ROAM, adaptive quadtrees, …, they are all just too CPU expensive. Screen space error metric is even worse (part of the original ROAM algo).

IMO for current hardware it is simply better to use a not-so-good error metric, which is relatively performant, and send more triangles to the GPU. What we “need” is a kind of “mixture” of an accurate error metric LOD algorithm and brute force rendering.


[This message has been edited by Lev (edited 05-19-2002).]