performance - What's a good data structure solution for a scene manager in XNA?

I'm playing with XNA for a game project of myself, I had previous exposure to OpenGL and worked a bit with Ogre, so I'm trying to get the same concepts working on XNA.

Specifically I'm trying to add to XNA a scene manager to handle hierarchical transforms, frustum (maybe even occlusion) culling and transparency object sorting.

My plan was to build a tree scene manager to handle hierarchical transforms and lighting, and then use an Octree for frustum culling and object sorting. The problem is how to do geometry sorting to support transparencies correctly. I know that sorting is very expensive if done on a per-polygon basis, so expensive that it is not even managed by Ogre. But still images from Ogre look right.

Any ideas on how to do it and which data structures to use and their capabilities? I know people around is using:

• Octrees


• Kd-trees (someone on GameDev forum said that these are far better than Octrees)


• BSP (which should handle per-polygon ordering but are very expensive)


• BVH (but just for frustum and occlusion culling)

Thank you

Tunnuz

Answer

Octtrees (or even just quadtrees) and Kd-trees are both good general purpose spatial partitioning schemes, and if your build pipeline and/or engine is generating them, then you will find they come in useful in all sorts of different ways for optimising queries/iterations. They work by sub-dividing a fixed volume in a hierarchical way, which makes queries like raycasting into your object space very cheap to query for (great for collision checks).

Bounding Volume Hierarchies work in a slightly different way (they aggregate the volumes of the objects in the tree rather than sub-dividing spaces), and are a simple way of trimming unnecessary things from being iterated over. But because BVH doesn't put any restrictions on how two sibling nodes are related, it's not such a good scheme for figuring out rendering order, or for arbitrary collision queries.

BSP systems are good when you're subdividing the world based on individual polygons, but for larger objects a volume based approach makes more sense.

Above all though, it's worth noting that none of these systems are perfect for determining render order for transparency, even the BSP approach. It will always be possible to construct geometry which breaks your algorithm, unless you are able to subdivide polygons on the fly. What you're most likely looking for is a 'best effort' solution, where geometry can be ordered correctly in the majority of the cases; and the art team can subdivide models for any of the cases which don't work (because the model/polygons are abnormally large, long, or self-intersecting). Smaller models/nodes are always much easier to sort 'correctly', but you pay for it in terms of iteration overhead.

Kd-trees and Oct/quad-trees are both good general purpose solutions, for which a platform friendly implementation can be written, but in the end you are going to have to balance the depth/complexity of your spatial partitioning tree against the cost of iterating it, and the overhead per model (i.e. draw call cost). If you're targetting XNA, I'd recommend you keep it simple and high level, and if there is sorting problems with some of the content, then strongly consider changing the content before trying to improve your engine until it can cope with it; the returns diminish very quickly after the most basic render sorting is implemented.