2D colliding n-body simulation (fast Collision Detection for large number of balls)

I want to write a program for simulating a motion of high number (N = 1000 - 10^5 and more) o开发者_如何学Gof bodies (circles) on 2D plane. All bodies have equal size and the only interaction between them is elastic collision.

I want to get something like

but in larger scale, with more balls and more dense filling of the plane (not a gas model as here, but smth like boiling water model).

So I want a fast method of detection that ball number i does have any other ball on its path within 2*radius+V*delta_t distance. I don't want to do a full search of collision with N balls for each of i ball. (This search will be N^2.)

PS Sorry for loop-animated GIF. Just press Esc to stop it. (Will not work in Chrome).

---

This first step in physics simulation is the broad-phase collision detection. There are several approaches outlined here Broad-Phase Collision Detection with CUDA but the two basics ones are:

• spatial partitioning: dividing the objects into a grid
• sort-and-sweep: sorting all the objects along two axes

---

Obviously you want to avoid (N1-)*N checks for collisions with each iterations. A simple approach would be to divide the area into a 2D grid of cells and then make a single pass to work out which cells each ball passes through in the current iteration. Each ball then only checks for collisions with balls passing through the cells it passes through.

I am sure there are more sophisticated approaches, but this might be a good start.

---

Grid width/length should be greater than or equal to the radius of them and search should be on the 1st neighbours(8+center=9 grids). With minimal grid size, it is ten to fifteen times the number of particles calculations.