Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am developing a platformer game with XNA framework like Metroid but in 3D. Now I have to draw models and I have the question of the title. I read many post and I know that the main data structures for draw polygons are octrees, quadtrees, BSP and Portals but I read and read and I don't know what is best. What do you think?

Thanks in advance.

share|improve this question
These are all space partitioning techniques, usually used for culling. They are performance optimisations - so which one is best will depend on what you are doing. So you need to provide significantly more information. – Andrew Russell Jul 18 '12 at 12:42
up vote 4 down vote accepted

The first thing you should do is get your game working. You can always change the data structure you use to store polygon data later on. It might be a lot of work, but you can still do it. The most important thing is to get your game working as soon as possible, even if it is inefficient.

This means getting a character on the screen, allowing the player to control them, adding some platforms to jump on and having some basic goal to complete. Worry about efficient rendering later - you might not need to worry at any point.

Once your game is working a bit you will have a clearer idea of what you want to do and this will help you decide whether a BSP tree or an Octree (or quad tree if you only need 2d partitioning) is the most appropriate for your game. Also keep in mind that you can use both of these storage structures by using them in different situations or merging them together.

It is my preference to use an octree to spatially partition the separate objects in my world. So that's where the tables, cars, characters, guns etc go. I would class these objects as the dynamic ones (although I won't necessarily allow them to move I will allow that possibility in my data structure). So in this situation I'm not splitting up the polygon meshes for each object, I'm just finding a box to put the whole thing in. This is useful for collision detection and also for just getting rid of things that are definitely outside of the view frustum. I do it this way because it's easier to rebuild an octree on the fly that is built in this way, so when things move, I just work out where in the tree they belong now.

The static mesh that makes up the world, if you use one, won't sit well in the octree. It's gonna be big. This will be one huge mesh that defines all the buildings and all the roads and rooms. In this situation I would either put it in a BSP tree or I would carve it up so each part fits in an octree leaf.

So in conclusion, what I think is you shouldn't worry about spatially partitioning polygon meshes at this stage, just get some basic stuff working and MAYBE give thought to putting those whole objects in an octree.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.