So I have a very simple problem : how do you prevent combinatorial explosion when you start having to do collision detection for a large number of items ? Let''s say Boids. In 2D, I can think of a nice way of solving this by, I think, discretizing the world in tiles, then simply marking each tile each item is in, then only doing actual collision detection when there is more than one item per cell (and to prevent the same collision being done several time, simply have a list of collisions to do this frame, or something like that). But in 3d ? Is there an elegant way to simplify things when discretization isnt possible ? Actually, I think I can answer that one by saying you can always find a way to simplify the world down to a point where you can discretize it, but I just want to see if there is a nice method out there... any thoughts ? Sancte Isidore ora pro nobis !

divide your space into cubes: if 1st object is present in cube, write 1 into it, and then write 2 into all cubes containing 2st object. and if you see both 1 and 2 object in the same cube, it means that your objects may intersect in this cube (but they may not intersect: for example

 |            |----------------- |111/        | |11/        /| |1/        /2| |/        /22| |        /222| |       /2222|----------------- |            |

both objects are present in one cube, but they don't intersect, so you have to divide this cube into smaller cubes to look the intersection).

this algorithm has linear complexity! if you don't understand why or don't understand my russian english, say!

excuse me for my russian english

[edited by - wormball on October 22, 2003 11:38:24 AM]

[edited by - wormball on October 22, 2003 11:38:52 AM]

cheers guys !
Well, I kinda had that one figured out already to be honest, since it''s just an extension of what I described in 3D. I was just hoping to see if there was any other approach to the problem I had overlooked, but I guess this *is* the best solution, is it ?


Sancte Isidore ora pro nobis !