title: Best algorithm for efficient collision detection between objects
body: <p>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.  </p>
  
  <p>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).</p>
  
  <p>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).</p>
  
  <p>So, in my research I can use one of:</p>
  
  <p>(1) Octree
  (2) Loose Octree
  (3) Linear Octree (+ loose)
  (4) KD Tree
  (5) BSP Tree
  (6) Hashing</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Thanks</p>
  
  <p>EDIT: Ok, thanks to Floris, I found more information about AABB Trees.  There's an old discussion on GameDev here: <a href="http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/">http://www.gamedev.net/topic/308665-aabb-tree---wheres-the-poly-o_o/</a>.  Looks like a good compromise.</p>
  
  <p>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).</p>