   Partioning the scene for Collision detection
  hi,I am currently working on rigid body collision detection and response. I made it to work fine for 30 objects(spheres)in the world. I have around 30,000 objects in the scene. The force is applied in a particular region of the scene, so that collision detection happens only around that area.My question is how to split the scene(objects are dynamic and are uniformly arranged in a plane, initially)to check for collision detection.Is it better to go for Quad tree or standard grid based approach.Because the region of influence can be moved anywhere in the plane.[Edited by - JAIHANUMAN on April 9, 2010 9:29:02 AM]
  If you start with a quad tree and you optimize it for speed(preallocate the nodes, make it loose, put it in an array), you basically end up with a grid.So in a general sense...QuadTree slower/less memory.Grid faster/more memory.   ;  a hash-map is kinda in the middle. It's basically a grid, but saves on the storage of empty grid cells. It's worth considering is the grid is too costly. As for quad-tree versus grid, for me the grid is straight-forward to code, and pretty efficient already. The dynamic quad-tree is trickier to implement and balance. In a kind of middle ground, you have the sweep-and-prune, but I'd stick with a grid / hashmap if you are comfortable with that. It's good at keeping track of small areas of effect as well.   