Best algorithm for efficient collision detection between objects

Question

I'm confused. Well not confused, so much as not wanting to do 6 test programs to see which algorithm is the best. So I thought I'd ask my expert friends here at SO to give me the benefit of their experience.

The scenario is a 3d scene with potentially quite a large area compared to the sizes of the objects inside it. There are potentially thousands of objects in the scene. Objects vary in size from tenths of a unit to up to around 10 units, but no bigger (or smaller). The objects tend to be clustered together, but those clusters can potentially appear anywhere in the scene. All objects are dynamic and moving. Clusters tend to move together, but when they do their velocities might not be the same all the time. There's also static geometry to consider. Although there are large numbers of dynamic objects, there's also some static objects in the scene (the static objects tend to be one or two orders of magnitude larger than the dynamic objects).

Now, what I want is a spatial data structure for efficiently performing collision detection for all items in the scene. It would be great if the algorithm also supported visibility query too, for the rendering pipeline. For the sake of simplicity, assume that collision detection here is broad-phase (i.e. all dynamic objects are just perfect spheres).

So, in my research I can use one of:

(1) Octree (2) Loose Octree (3) Linear Octree (+ loose) (4) KD Tree (5) BSP Tree (6) Hashing

So far (6) is the only one I've tried. It's actually totally superb in terms of speed (8192 items collision checked in under 1ms on my system) if objects in the scene are on average evenly spread out. It's not such a good algorithm if all objects get couped up into a smaller area, which I suppose is possible.

Does anyone have some insight as to which one to use, or any tricks I can employ to speed things up? I'm thinking that whatever happens I can just use a separate BSP tree for the static geometry. I suppose the dynamic "spheres" are what concern me most here. Note: no CUDA, this is CPU only :p.

Thanks

EDIT: Ok, thanks to Floris, I found more information about AABB Trees. There's an old discussion on GameDev here: http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/. Looks like a good compromise.

Final EDIT: Decided not to reinvent the wheel. It's possible the bullet physics library will do all of this for me (it has AABB tree in it, probably very well optimised too).

Answer 1

Great question.

You basically have a complex trade-off between:

1. Speed of a complete collision detection phase
2. 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!