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

Question

Hello

I want to write a program for simulating a motion of high number (N = 1000 - 10^5 and more) of bodies (circles) on 2D plane. All bodies have equal size and the only force 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).

Answer 1

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.

Answer 2

This first step in physics simulation is the broad-phase collision detection. There are several approaches outlined here http://http.developer.nvidia.com/GPUGems3/gpugems3_ch32.html but the two basics ones are spatial partitioning, dividing the objects into a grid, or sort-and-sweep, which consists of sorting all the objects along two axis.