I'm currently working a 3D space game with A LOT of dynamic objects that are all moving (there is pretty much no static environment). I have the collision detection and resolution working just fine, but I am now trying to optimize the collision detection (which is currently O(N2) -- linear search). I thought about multiple options, a bounding volume hierarchy, a Binary Spatial Partitioning tree, an Octree or a Grid. I however need some help with deciding what's best for my situation. A grid seems unfeasible simply due to the space requirements and cache coherence problems.

Since everything is so dynamic however, it seems to be that trees aren't ideal either, since they would have to be completely rebuilt every frame. I must admit I never implemented a physics engine that required spatial partitioning, do I indeed need to rebuild the tree every frame (assuming that everything is constantly moving) or can I update the trees after integrating?

Advice is much appreciated - to give some more background: You're flying a space ship in an asteroid field, and there are lots and lots of asteroids and some enemy ships, all of which shoot bullets.

EDIT: I came across the "Sweep an Prune" algorithm, which seems like the right thing for my purposes. It appears like the right mixture of fast building of the data structures involved and detailed enough partitioning. This is the best resource I can find.

If anyone has any suggestions whether or not I'm going in the right direction, please let me know.

  • 1
    \$\begingroup\$ How large is your world, and how many objects exist in it? In rough figures, so we get an idea of the load that algorithms would be under. \$\endgroup\$ – Trevor Powell Nov 21 '11 at 9:24

I unfortunatelly now don't have time to read about that SAP algorithm, but what I have read few months ago (but I don't know, if it's suitable for your problem, it's much more suitable for points - not objects):

You can use some special case of kd-Tree - for example octree - which uses half partitioning in each axis (in article I have read, they were using quarter partitioning - each axis is split to 4 peaces). You use dynamic version of it.

First you build your structure at the beginning. This means, you split space into kd-Tree. Leaf of tree should have some limited number of objects (for our example let's take 64). Each node knows of course how many objects is in it.

When you update positions of objects, you transfer them also in structures nodes. After that, you update whole structure according to these rules:

1) When inner node has less then limited number of points (sum of its leafs is less then 64), then you merge leafs and inner node becomes leaf.

2) When some leaf has more then 64 objects, you split this node.

If you want, I can try to find that article - when I will have some time.

  • \$\begingroup\$ So I have found that article: ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4293643 When I was reading it, I had access to IEEE, but now I don't have :( \$\endgroup\$ – zacharmarz Nov 21 '11 at 19:19
  • \$\begingroup\$ Wouldn't this virtually be rebuilding the entire tree every frame though, since everything is moving thus has to be updated? It's a shame that this article is freely available, I would've liked to see more of it. \$\endgroup\$ – Millianz Nov 21 '11 at 21:14
  • \$\begingroup\$ No - if your object move just a bit, they stay in the same leaf as they were frame before. And if some objects really move between leafs, it's possible you will have to rebuild just few leaves and inner nodes - not whole tree. And if you want that article, I can send it to you for example by email (I have got it still on my hard disk). \$\endgroup\$ – zacharmarz Nov 21 '11 at 21:25

I don't have enough experience with Sweep-and-Prune to know whether it's a good fit as the highest-level broad-phase algorithm, so I can't comment on that.

You may want to take a look at loose octrees, which are a variation of octrees that are designed for frequent alteration. I'm not sure what the best reference would be, however; I have often heard that loose octrees with k = 2 work pretty well, but I don't have an online source handy.


I'd take a look at dynamic icoseptrees.

1 ) Icoseptrees overall fares very well for large spaces due to its sparse nature. The memory requirements of the tree is directly proportional to the number of objects in the scene.

2 ) You can use it for rendering as well ( in fact, that is the primary application of Icoseptrees ).

3 ) Icoseptrees can deffer optimization of the tree while providing no false negatives.

4 ) Terrific worst case performance.

Icoseptrees loose vs pre processed octrees of static objects, but this is obviously no con for your use case.

  • \$\begingroup\$ Hi, could you post some resources for this structure? I can't seem to find anything about it except this master thesis: cs.nmsu.edu/~joshagam/Solace/papers/master-writeup-print.pdf \$\endgroup\$ – Millianz Nov 21 '11 at 20:33
  • \$\begingroup\$ There isn't much information on it, I think that was the resource I used as well ( although I seem to recall a second paper which I fail to locate ). If you have any questions I can most likely answer :) \$\endgroup\$ – Ylisar Nov 21 '11 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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