I have a 3D scene with a lot of Mobiles (basically world objects that move all the time) and I'm trying to figure out the best way to organise them so as to speed up collision detection.

I'm leaning towards using a kd tree to divide my game world up into a binary tree of nodes, and then adding each mobile to a node.
- If there is an overlap between the mobile's bounding sphere and multiple nodes, then they go in a parent node.
- Every time a mobile moves, a check is required to see if it is still in its current node, and moved to a new node if required.
- A collision detection test with a mobile (mobA), would require a check between mobA and all the mobiles that are in the same node as mobA and all the mobiles that are in parent nodes.


This is as about as good as I can think of, but am really keen to get some advice before I pour some hours into this.

Alternatively I was thinking about using
- Quad trees
- Perhaps not using the kd-tree nodes as 'buckets' of mobiles but instead making each mobile a kd-tree node, so that mobiles have child mobiles. I figured this would get crazy complex when mobiles moved and the kd-tree would have to get entire branches re-added to the tree.

I see there are lots of good articles on collisions between two objects, but I can't find much in the way of better organising a world of moving objects.
I did find:
http://www.gamedev.net/community/forums/topic.asp?topic_id=434610

Cheers for any tips.

I'd recommend a Spatial Hash.

It's efficient enough for dynamic and deformable bodies, thus it works well with normal rigid bodies as well.

For mobile objects, you'd have to first clear the spatial hash. Then update each objects bounding volume (like an AABB). Then rehash each object into the Spatial Hash. That may sound kind of bad but it handles the problem of updating the structure positions for fast moving objects and has an algorithm cost of O(N), which is doable. Once everything is in place, asking the game engine "What is by this point," "What is in this volume of space," or "What other objects may collide with this game object?" becomes an easy and efficient thing to answer.

I did an implementation for convex shapes with AABB for bounding volumes and it's been working well for my broad phase collision detection.

Read the paper and if you're interested in discussing implementation details, let me know.

Thanks for the feedback guys. Those two ideas look a lot more promising than what I was going to use.