Archived

This topic is now archived and is closed to further replies.

ahw

Collision detection scheme

Recommended Posts

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 !

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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 !

Share this post


Link to post
Share on other sites
well you should also try to perform some quick checks before launching into the CPU intensive stuff... like for example you can do a quick distance test or bounding box test, and if they fail you can skip the more complex things like checking colosion between individual triangles...

I don''t think there is just one solution that will make it run lighting fast, you just need to to try a combination of things and tweak it until u find what is the fastest...

Share this post


Link to post
Share on other sites
This post belongs in the Maths & Physics forum. I''ll leave it here for now, since it appears to have been answered. If there are any further queries along these lines, please post them in the M&P forum.

Thanks,

Timkin

Share this post


Link to post
Share on other sites