Great question.
You basically have a complex trade-off between:
- Speed of a complete collision detection phase
- Overhead of updating / maintaining the data structure as objects move around
The bad news is that there is no “perfect” answer because of this – it will genuinely depend on lots of different factors unique to your situation. BSPs for example are blisteringly fast for 1. when they are pre-computed with a lot of static planar geometry, which explains why they were so prevalent in early FPS games.
My personal guess is that a loose AABB (Axis Aligned Bounding Box) tree with a reasonable number of objects (5-10?) in each bottom level bounding box will probably work best in your case. Reasons:
- You have quite a large / sparse space with clusters of objects. AABB trees tend to be good for this, as you can cut out a lot of levels that you would otherwise need.
- You are assuming perfect spheres. Sphere to sphere collision tests are very cheap so you can easily afford to do 10-45 tests for each bottom level-node. Basically N^2 is fine for small values of N 🙂
- Axis alignment makes updating the tree much simpler and intersection tests much cheaper than most alternatives. Since you are assuming roughly spherical objects, I don’t think you would gain much from oriented bounding boxes (which only really give you an advantage if you have lots of long/thin shapes at funny angles).
- By allowing the bounding boxes to be loose and contain a reasonable number of objects, you reduce the chance that the motion of any individual object will take it outside the AABB bounds. Unless this happens, you don’t need to update the tree. This will save you a lot of tree-updating time. When it does happen, extend the bound with a bit of margin so that you don’t immediately have to re-extend again next frame – remember that most motion tends to continue in the same direction for a few frames!
Sorry for the slightly woolly answer but I hope this gives you some useful ideas / things to consider!