Optimization in collision detection

3
votes

I'm searching for information about optimization for collision detection.

There is an object (circle) which is moving from point a to point b. This object has radius r, and there are many obstacles (circle) in field too.

enter image description here

I have an algorithm (function) that checks collision between a circle and a capsule, and I currently call this function for every obstacle:

for-each (o : obstacles)
  if collide(o, Capsule(a,b,r))
    return true;

return false;

Many obstacles are very far away from the moving object and they can be ignored from checking with the collision detection function.

My question is:

Is there a solution to ignore checking all obstacles with collision detection function? Something like Nearest neighbor search or KD trees?


EDIT : All obstacles have same radius.

6
algorithmoptimizationcollision-detection
How many obstacles do you have? How dense are they? Do collisions happen often or rarely? - Björn Pollex
Think about 100 obstacles, and they are sparsely distributed. Algorithm calls every 10ms. - masoud
And I think the battle-neck of my program is this issue. - masoud
You should try profiling your program to make sure you have found the bottle-neck. Also, A kd-tree seems suitable for your problem, have you tried if it helps? - Björn Pollex
I used kd-tree for find nearest point to a given point before. But in this case do not know how can I use kd-tree! - masoud

6 Answers

4
votes

As a first step, you can ignore all obstacles not beeing in a certain frame/box.

E.g. all obstacles with y - coordinate (the y- lowest point of the shape of the obstacle) bigger then the maximum y coordinate of a and b + same distance for the radius of the moving object can be ignored. Similar for lower y-border and the x borders. Instead of one box, you could further branch similar into two (ore more) boxes. For example buy splitting the distance of a-b into two distances and doing the above procedure for each of (a, (b-a)/2), /(b-a)/2, b).

But it all depends on how efficient you can compare these values in comparison to you collision procedure.

3
votes

You can simply use a grid, where each cell holds all the obstacles touching that cell. Now only check the cells for collision that your capsule touches. Also you could use a quadtree as well, but from my experience a grid suffices usually and also has the advantage of being easily and quickly updatable in case your obstacles move.

2
votes

A comment on Martin's answer:

I made a box like Box(a.x-R, a.y-R, b.x+R, b.y+R) where R is ObjectRadius + ObstacleRadius, then drop every obstacle which is not inside this box. In the figure, only obstacles with yellow dot will be checked:

enter image description here

1
votes

I can recommend a monster curve, for example a hilbert curve. It's a quadtree or kd tree like data structure and it reduces the 2d complexity to a 1d problem. At each frame you can just build the monster curve from start and such spare the deleting or inserting in a quadtree or kd tree. It has also some better 2d tiling properties but that may be unwanted in your case.

0
votes
  1. Put centres of obstacles into KD-tree.
  2. Find the nearest centre.
  3. Check if it's closer than ObstacleRadius.
0
votes

You can try implementing spatial partitioning in your code. By partitioning each object/obstacle into each boxes covering the entire space or map. By doing so you are grouping the obstacle into sections. So you can reduce the collision check by a huge amount by just checking for collision within a small section. If your obstacle are not moving you only need to do this partitioning only once for each obstacle. If they are moving, you have to update the partitioning [Regrouping] for each obstacle every time.

Spatial Partitioning techniques have been around for quite some time, here is a link to help you out with the implementation.

http://gameprogrammingpatterns.com/spatial-partition.html