#### Archived

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

# Collision detection scheme

This topic is 5232 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
Octrees are often used to partition entities into smaller areas. Then you only need to check for collisions with entities that are in the same octree node as you...

http://www.gamasutra.com/features/19970801/octree.htm

botman

##### 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 on other sites
yeh check out the octree tutorials on http://www.gametutorials.com/ in the tutorial section -> opengl

##### 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 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 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