8
\$\begingroup\$

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

Improve this question
\$\endgroup\$

3 Answers 3

Reset to default
6
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ I have read that even Depth Peeling techniques to handle per-fragment sorting often obtain good results. Do you think that this is feasible on a small game engine? Do AAA games use these techniques? \$\endgroup\$
    – tunnuz
    Aug 10, 2010 at 13:36
  • \$\begingroup\$ What do you think is better/easier to implement between Kd-trees and Octrees? \$\endgroup\$
    – tunnuz
    Aug 10, 2010 at 13:38
  • \$\begingroup\$ I'd be very surprised if there wasn't a C# implementation for both of them already out there: it's the kind of thing where the meat of it (the subdivision and the querying) is the same for all implementations, but the interesting bits (how do you iterate/query/associate items with the nodes) can vary. Oct/quad-trees are, to my mind, conceptually simpler, but as has been pointed out, kd-trees are more efficient in a variety of ways. I'd probably go kd-tree just because if you can do that, you can do oct-trees (but the reverse isn't necessarily true). \$\endgroup\$
    – MrCranky
    Aug 10, 2010 at 13:47
  • 1
    \$\begingroup\$ As for per-fragment sorting: without knowing anything about your engine it's hard to say, but it feels like a bit of a premature optimisation. Yes, AAA games might use those techniques, but they'll also be shuffling more objects than an XNA engine will be able to manage, and so require more extreme optimisation techniques to get the most out of it. My advice would always be to get the basics (transparency sorting) done solidly, and if you find that performance just isn't up to scratch, then go the whole hog and do finer grained sorting. Chances are something else will bound performance first. \$\endgroup\$
    – MrCranky
    Aug 10, 2010 at 13:50
  • 1
    \$\begingroup\$ There are actually AAA-developers out there that skip using BV-tree's since doing it brute-force while making sure that you actually use most of the clockcycles efficiently (No LHS/L2+L1 Cache misses etc) provides good enough performance. It's amazing how many tests you can push out with a well-designed system. \$\endgroup\$
    – Simon
    Aug 10, 2010 at 14:40
3
\$\begingroup\$

McCranky covered amazingly all the data structures you mentioned, however I see that you havent considered R-Trees. The body of knowledge on those structures is huge, and they are very suitable for spatial range queries (most of the work have been done by database theorists and practitioners) in the last 30 years. Recently Sebastian Sylvain from Rare has given a course on the GDC on why they work for games too (specially on consoles with in-order processors). You can learn more from its pdf: http://www.gdcvault.com/play/1012452/R-Trees-Adapting-out-of

A naive and simple implementation is pretty easy, and the basic structure gives you lots of room for improvement (better management of splitting heuristics, prefetching oportunities, parallel searching, etc).

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

The answer highly depends on the amount of models that you are planning to use. I haven't really worked with these kind of things for XNA, but if you use AABB's for the tests and don't have too many models you might be good enough with a brute force test. Perhaps even throw it out on a thread. I'm not sure how/if there are any SSE/VMX optimizations that can be used for C# but if you manage to get the AABB's linearly in memory (so that you get no cache-misses for the CPU), you should be able to push through a high amount of tests in quite little time.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .