Jump to content
  • Advertisement
Sign in to follow this  
Norman Barrows

frustrum culling methods

This topic is 1997 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

HI i was wondering what frustrum culling methods folks are using?

 

i've seen testing bounding spheres vs planes mentioned. 

Edited by Norman Barrows

Share this post


Link to post
Share on other sites
Advertisement

Sticking with the basic beginner friendly methods, there is pretty much the "classic" approach of extracting frustum planes and checking the distance again each of them and the "radar" approach, where you transform things to camera space and just compare z vs. near/far and x/y vs half the width/height of the frustum for the given z.

 

There is no huge difference in terms of complexity or performance, so I'd simply use whatever seems more intuitive to you.

Share this post


Link to post
Share on other sites

and the "radar" approach, where you transform things to camera space and just compare z vs. near/far and x/y vs half the width/height of the frustum for the given z.
 
There is no huge difference in terms of complexity or performance, so I'd simply use whatever seems more intuitive to you.

 

well i started with a world space clip in x-z only, then went to a camera space clip in x-z only. but i'm computing headings to the center and corners of bounding boxes. x/y vs 1/2 width/height @ given Z sounds more efficient. my only problem is when a bounding box spans the frustrum and is so big that the center and all four corners fall outside the frustrum. 

Share this post


Link to post
Share on other sites

Some interesting reading:

http://www.cse.chalmers.se/~uffe/vfc_bbox.pdf

http://fgiesen.wordpress.com/2010/10/17/view-frustum-culling/

 

A simple one is to extract the 6 planes from your view-projection, and then test each object's bounding sphere against those planes, taking it's radius into account.

The above describe a similar scheme extended to AABB's. To support OBBs, you can rotate the planes by the boxes inverse orientation so that the box becomes axis aligned.

Share this post


Link to post
Share on other sites

What I have done in the past and it worked very well was simple sphere vs frustum with plane caching.

 

The idea being if a sphere vs frustum plane fails the test, the store that plane and test it first next time round as it will most likely be behind that same plane on the next frame.

I wrote a little about it here:

http://blog.bwhiting.co.uk/?p=355

 

It works very very quickly and was fine with anything upto 10,000 objects culled in about 1ms. With c++ this could probably be 10 times faster.

Share this post


Link to post
Share on other sites

well i started with a world space clip in x-z only, then went to a camera space clip in x-z only. but i'm computing headings to the center and corners of bounding boxes. x/y vs 1/2 width/height @ given Z sounds more efficient. my only problem is when a bounding box spans the frustrum and is so big that the center and all four corners fall outside the frustrum. 

 

That shouldn't be a problem, unless you make the mistake of completely ignoring which plane the corners are outside of. All corners have to be outside of the same plane, even if that means not culling a few special cases. Usually that's not a big deal and you're better off with conservative quick and dirty frustum culling than being super precise and wasting more time on culling objects than it would have taken to render them.

 

Which also means that spheres are usually more than sufficient and if you can easily group a bunch of objects into chunks, it's a waste of time to cull every single object individually.

 

For a large terrain, I use a sphere tree. It's crude and draws the occasional invisible chunk, but culling takes almost no time at all.

Share this post


Link to post
Share on other sites

The other useful property of any kind of hierarchical partitioning that's rarely mentioned is: if a given node is fully inside the frustum, then all of it's child nodes are guaranteed to also be fully inside; this generalizes to: frustum checks only need to be done for nodes where the parent intersects the frustum (and for the root node, where there is no parent).  Using this knowledge you can quite easily (and quickly) skip over a huge number of tests with trivial accept and reject cases.

Edited by mhagain

Share this post


Link to post
Share on other sites

A simple one is to extract the 6 planes from your view-projection, and then test each object's bounding sphere against those planes, taking it's radius into account.
The above describe a similar scheme extended to AABB's. To support OBBs, you can rotate the planes by the boxes inverse orientation so that the box becomes axis aligned.

 

the title in question is a FPS/RPG. as such, there's very little to clip above and below the frustrum, so i don't bother with clipping to the upper and lower frustrum planes. i'm trying to keep the culling overhead as low as possible, so i'm trying to stay away from complex intersection tests, additional transforms, etc. I was forced to go to camera space, because you can look down over the edge of a 100 foot cliff down into a canyon below (and actually climb up and down the cliff face too).

 

i was just curious how the "real world" does it.   sphere/AABB vs plane etc all just sounds like overkill to me. do people really have clock cycles to burn on such trivialities?  please explain, am i missing something here? are there situations where things like AABB vs plane are required?

 

the problem with large bboxes that more than "double span" the frustrum is the same idea as "spanning triangle clipping" in a poly engine. easily dealt with with a couple extra checks.

 

am i correct in assuming that in camera space "abs(x) > 1/2 frustrum width @ given z" is faster than "plane-sphere intersection test" (assuming everything is pre-computed) ?   I haven't looked up the formulas, other than those clever "change of coord system" dots in the article cited above (metal gear 3 was it?).

Share this post


Link to post
Share on other sites

The idea being if a sphere vs frustum plane fails the test, the store that plane and test it first next time round as it will most likely be behind that same plane on the next frame.

 

very clever. optimize cull order on the fly!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!