We''ve all seen the silly demo which has a bunch of balls bouncing around in 3D space...I hope so anyway. It''s a fairly simple/common demo.
What I want is a good algorithm to do collision detection between the balls that are bouncing. Since all the balls are well...balls, I''m saying each one is a particle defined by a sphere of radius R.
When the number of balls is small, it''s fairly simple to check if any of the spheres overlap;
For each x, y, z, get a minimum (coordinate - radius) and a maximum (coordinate + radius). For every other ball, check if the spheres overlap. The order of this is shocking however. N*N*(Number of operations to see if a ball is overlapping another ball).
So I want a more efficient algorithm to achieve this. I''ve had quite a look around and the only real collision detection I can find is based on trying to do collision detection on a polymesh, using cubes or sphere (elipsoids) to approximate the polygons.
Can anyone suggest some reading on this matter?
So far the very best I''ve come up with sorting the balls into a series of trees by x, y, z and then using the binary tree to throw away any balls which are outside the target area. This can reduce the calculations in the best case situation, but on the worst case it''s more calculations and the average case is only something like 2% more efficient. When I actually implement it and use random starting positions and velocities on the balls, I get a comparable time taken for collision detection (1000 balls).
Any thoughts on the matter most welcome. I''m getting quite frustrated by things which say: "Particle Collision Detection Algorithm!" and then spent 30 pages on generating BSPTrees from polymeshs and collision caching and about 1/2 a page on actually doing collision detection.
Thanks!