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

Question

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 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).

Answer 1

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