(big, over-descriptive post :D) Some time ago I was looking around for ways to manage objects and somebody recommended octrees. I couldn't find anything that practically implemented it anywhere (at least not in a way I was likely to readily understand) so I went ahead and wrote a very basic octree class. This is the way I currently use it: Every solid object performs a test every step to locate itself in space, i.e. it basically associates itself to the nearest node in the tree. It's just an integer ID so while checking for collisions, this value is the first one that is checked. I figured this would be simpler than to have to make an array of pointers for every node. But here's the problem: When some object's bounding sphere is spread across several partitions, the collisions don't happen as wanted. Obviously, the little projectiles associated with a certain node don't collide with a big object that's associated with a neighboring node even though it shoots through parts of it. The only straightforward "solution" I can think of is to split the bounding sphere up into smaller spheres and have every one of them check for their spatial IDs. Then in the checking bit, I'd have to cycle through all the spheres to check with ones intersect with the projectiles path, if the IDs match. This is probably a very stupid thing to do because having everything check their positions every step is inefficient as it is. And the problem is still likely to persist (but to a lesser extent). So I guess the main problem is that large objects have parts of it protruding into a projectile's octant without actually being in the same logical spatial partition, and no collision happens. Anyone got any suggestions/methods I might try? The way I'm currently using the tree is quite literal. I just went ahead and made a static tree and if I render it, it looks like a gigantic.. well, tree. Also, having every object find it's node every step doesn't seem like too much of an efficient way to me. Am I doing it right at all? Thanks in advance.

Hmm.. Multiple object references, you say.. I was hoping to avoid actually referencing an object so I implemented an identification system that's only relevant to the tree. But if I were to find out which nodes the object overlaps, how do I go about it? The node selection is based on a single point (the sphere's center). It seems pretty expensive to have to find out which partitions the sphere actually intersects. How is this generally done?

I am looking into AABB trees now. Thanks.

For dynamically moving objects I can heartily recommend the Dynamic Bounding Volume Tree found in Bullet 2.70, or at least use the implementation as reference.

We've tried numerous data structures, and even though we have a totally different collision engine, the DBVT performs the best under pretty much all game related situations, at least for us.

maybe this can help:
http://www.codefortress.com/modules.php?name=Articles&op=ReadStory&sid=26&pgNum=1