Jump to content
  • Advertisement
Sign in to follow this  
RealMarkP

Need advice: Frustum culling, BSP, etc

This topic is 3716 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

Hello all, I've been looking around for different ways of partitioning space and culling objects and I am confused as to which way is the optimal ways for indoor and outdoor scenes. I know the theory behind such things as Octrees, BSP trees, frustum culling but I don't know when to use them. I was thinking of using an Octree to narrow down the objects that I need to render and then do simple frustum culling to narrow it down further. Suggestions? My engine is just a pet project and is mostly there to keep my programming skills sharp, so I don't want to rely on 3rd party libraries to do this sort of thing for me.

Share this post


Link to post
Share on other sites
Advertisement
As I understand it, Octrees are a type of BSP tree - and best in outdoor scenes with lots of objects. For indoor scenes, though, you might look into portal rendering or antiportal rendering - much better optimizations.

Share this post


Link to post
Share on other sites
Unfortunately, there really isn't a one-size-fits-all solution for this kind of thing. You need to look at the tradeoffs of each, in the context of the situation.

Off the top of my head:

*BSP-Tree or Kd-Tree (Kd-Tree is just an axis-aligned BSP-Tree):
Require a "baking" phase (generally done off-line), as determining optimal splits takes time. As a result, these types aren't conducive to modifications at run time, or dynamic objects in general.

*Dynamic Quadtrees/Octrees
Basically Kd-Tree in 2 or 3 dimensions (Quadtree/Octree respectively), but with fixed split planes (half the axis of the parent). These are more suited to dynamic stuff, and generally easier to work with as well, as you don't need to worry about "where do I split the cell." They also work well enough in practice that you don't need to bother with BSP/Kd-Trees.
By "dynamic," I mean that the cells are not pre-split. This means you split/collapse cells dynamically as you add/remove objects. It also means you add an object by starting at the root and recursing as far as you can go. If you're doing a lot of this, and splitting/collapsing a lot, you might find some overhead involved there, though it's not necessarily an incredibly expensive operation to split/collapse.

*Loose Quadtrees/Octrees
Like the above, but with the added aspect that they're "loosened" so that you can determine an object's appropriate exact cell (depth in the tree included) based simply off its position and bounding extents. These trees are pre-split down to some maximum depth; as such, they generally require a lot of memory, but are well suited to dynamic objects, as moving an object can be done in constant time (for the computation of which cell to move it to, plus no splitting).

Anyway, there's a few notes to go on at least. Obviously the choice between 2D-3D (quad/oct -tree) depends on your source data as well, and how well you expect the 3rd dimension to be utilized. I'm sure others can add to or debate what I've said. I'd advise using a combination - you don't necessarily just need one big container for everything... or rather, you might start with one big container that holds all objects, but then objects/scene nodes might implement custom spatial partitioning schemes to suit their expected behavior (i.e., objects that hold other objects, or that hold lists of triangles, etc).

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!