Collision detection of huge number of circles

What is the best way to check collision of huge number of circles?
It's very easy to detect collision between two circles, but if we check every combination then it is O(n²) which definitely not an optimal solution.

We can assume that circle object has following properties:

• Coordinates
• Radius
• Velocity
• Direction

Velocity is constant, but direction can change.

I've come up with two solutions, but maybe there are some better solutions.

Solution 1
Divide whole space into overlapping squares and check for collision only with circles that are in the same square. Squares need to overlap so there won't be a problem when a circle moves from one square to another.

Solution 2
At the beginning distances between every pair of circles need to be calculated.
If the distance is small then these pair is stored in some list, and we need to check for collision in every update.
If the distance is big then we store after which update there can be a collision (it can be calculated because we know the distance and velocitites). It needs to be stored in some kind of priority queue. After previously calculated number of updates distance needs to be checked again and then we do the same procedure - put it on the list or again in the priority queue.

Answers to Mark Byers questions

1. Is it for a game?
   It's for simulation, but it can be treated also as a game
2. Do you want to recalculate the new position every n milliseconds, and also check for collisions at this time?
   Yes, time between update is constant.
3. Do you want to find the time at which the first/every collision occurs?
   No, I want to find every collision and do 'something' when it occures.
4. How important is accuracy?
   It depends on what do you mean by accuracy. I need to detect all collisions.
5. Is it a big problem if very small fast moving circles can pass through each other occasionally?
   It can be assumed that speed is so small that it won't happen.

Solution 1:

There are "spatial index" data-structures for storing your circles for quick comparison later; Quadtree, r-tree and kd-tree are examples.

Solution 1 seems to be a spatial index, and solution 2 would benefit from a spatial index every time you recalculate your pairs.

To complicate matters, your objects are moving - they have velocity.

It is normal to use spatial indexes for objects in games and simulations, but mostly for stationary objects, and typically objects that don't react to a collision by moving.

It is normal in games and such that you compute everything at set time intervals (discrete), so it might be that two objects pass through each other but you fail to notice because they moved so fast. Many games actually don't even evaluate collisions in strict chronological order. They have a spatial index for stationary objects e.g. walls, and lists for all the moving objects that they check exhaustively (although with relaxed discrete checks as I outlined).

Accurate continuous collision detection and where the objects react to collisions in simulations is usually much more demanding.

The pairs approach you outlined sounds promising. You might keep the pairs sorted by next collision, and reinsert them when they have collided in the appropriate new positions. You only have to sort the new generated collision list (O(n lg n)) for the two objects and then to merge two lists (the new collisions for each object, and the existing list of collisions; inserting the new collisions, removing those stale collisions that listed the two objects that collided) which is O(n).

Another solution to this is to adapt your spatial index to store the objects not strictly in one sector but in each that it has passed through since the last calculation, and do things discretely. This means storing fast moving objects in your spatial structure, and you'd need to optimise it for this case.

Remember that linked lists or lists of pointers are very bad for caching on modern processors. I'd advocate that you store copies of your circles - their important properties for collision detection at any rate - in an array (sequential memory) in each sector of any spatial index, or in the pairs you outlined above.

As Mark says in the comments, it could be quite simple to parallelise the calculations.

Solution 2:

I assume you are doing simple hard-sphere molecular dynamic simulation, right? I came accros the same problem many times in Monte Carlo and molecular dynamic simulations. Both of your solutions are very often mentioned in literature about simulations. Personaly I prefer solution 1, but slightly modified.

Solution 1
Divide your space into rectangular cells that don't overlap. So when you check one circle for collision you look for all circles inside a cell that your first circle is, and look X cells in each direction around. I've tried many values of X and found that X=1 is the fastest solution. So you have to divide space into cells size in each direction equal to:

Divisor = SimulationBoxSize / MaximumCircleDiameter;
CellSize = SimulationBoxSize / Divisor;

Divisor should be bigger than 3, otherwise it will cause errors (if it is too small, you should enlarge your simulation box).
Then your algorithm will look like this:

1. Put all circles inside the box
2. Create cell structure and store indexes or pointers to circles inside a cell (on array or on a list)
3. Make a step in time (move everything) and update circles positions inside on cells
4. Look around every circle for collision. You should check one cell around in every direction
5. If there is a collision - do something
6. Go to 3.

If you will write it correctly then you would have something about O(N) complexity, because maximum number of circles inside 9 cells (in 2D) or 27 cells (in 3D) is constant for any total number of circles.

Solution 2
Ususaly this is done like this:

1. For each circle create a list of circles that are in distance R < R_max, calculate time after which we should update lists (something about T_update = R_max / V_max; where V_max is maximum current velocity)
2. Make a step in time
3. Check distance of each circle with circles on its list
4. If there is a collision - do something
5. If current time is bigger then T_update, go to 1.
6. Else go to 2.

This solution with lists is very often improved by adding another list with R_max_2 > R_max and with its own T_2 expiration time. In this solution this second list is used to update the first list. Of course after T_2 you have to update all lists which is O(N^2). Also be carefull with this T and T_2 times, because if collision can change velocity then those times would change. Also if you introduce some foreces to your system, then it will also cause velocity change.

Solution 1+2 You can use lists for collision detection and cells for updating lists. In one book it was written that this is the best solution, but I think that if you create small cells (like in my example) then solution 1 is better. But it is my opinion.

Other stuff
You can also do other things to improve speed of simulation:

1. When you calculate distance r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...) you don't have to do square root operation. You can compare r^2 to some value - it's ok. Also you don't have to do all (x1-x2)*(x1-x2) operations (I mean, for all dimentions), because if x*x is bigger than some r_collision^2 then all other y*y and so on, summed up, would be bigger.
2. Molecular dynamics method is very easy to parallelise. You can do it with threads or even on GPU. You can calculate each distance in different thread. On GPU you can easly create thousends of threads almost costless.

For hard-spheres there is also effective algorithm that doesn't do steps in time, but instead it looks for nearest collision in time and jumps to this time and updates all positions. It can be good for not dense systems where collisions are not very probable.

Solution 3:

one possible technique is to use the Delaunay triangulation on the center of your circles.

consider the center of each circle and apply the delaunay triangulation. this will tesselate your surface into triangles. this allows you to build a graph where each node stores the center of a triangle, and each edge connects to the center of a neighbour circle. the tesselation operated above will limit the number of neighbours to a reasonable value (6 neighbours on average)

now, when a circle moves, you have a limited set of circles to consider for collision. you then have to apply the tesselation again to the set of circles which are impacted by the move, but this operation involves only a very small subset of circles (the neighbours of the moving circle, and some neighbours of the neighbours)

the critical part is the first tesselation, which will take some time to perform, later tesselations are not a problem. and of course you need an efficient implementation of a graph in term of time and space...

Solution 4:

Sub-divide your space up into regions and maintain a list of which circles are centred in each region.

Even if you use a very simple scheme, such as placing all the circles in a list, sorted by centre.x, then you can speed things up massively. To test a given circle, you only need to test it against the circles on either side of it in the list, going out until you reach one that has an x coordinate more than radius away.