Collision Detection

Simulating the interaction between a large number of moving spheres is a non-trivial problem that often occurs in simulations (hard-sphere simulation, molecular dynamics simulation, simulation of ideal gases) and computer games (collision detection between fast-moving entities that can be inscribed in bounding spheres). There are two major approaches to collision detection in this context:

Static collision detection: In this approach, all spheres are assumed to be non-overlapping at the beginning of a simulation time step, and are assumed to move linearly during the time step. The simulation moves all spheres by adding their current velocities, scaled by the length of the time step, to their current positions. After all spheres have been moved, all pairs of overlapping spheres are detected, and collisions are handled by changing the spheres' velocities and positions.
Dynamic collision detection: This approach follows the same assumptions as the first one, but instead of checking for collisions after the fact, all potential calculations between any pair of spheres are predicted at the beginning of the time step, and then handled in order of the time they occur. In other words, a single time step is split into many micro-time steps that lie between a collision event and the next collision event. This approach is also referred to as event-based collision detection.

The main drawback of the first approach is accuracy, or lack thereof. Since collisions are only detected at the end of time steps, spheres that neither overlap at the beginning or the end of a time step, but collide in the middle, are not found. Furthermore, once a collision has been detected, the exact time and position at which the collision happened are unknown, and backtracking is often difficult. If spheres are dense, backtracking to resolve one overlap might introduce another one that will be neither detected nor handled. As a result, static collision detection is unsuitable for applications in which accuracy matters - especially simulations.

Dynamic collision detection does not suffer from this drawback. All collisions are detected, and since collisions are handled before they happen, by conceptually advancing the simulation to the exact point where the next collision happens, at no point in time will two spheres ever overlap. This means that no spheres will have to be moved to remove overlap, which means there will be no new overlap when spheres are dense, and those situations will be handled correctly.

The drawbacks of dynamic collision detection are that it is only accurate to machine precision - collisions can be missed if round-off error moves colliding spheres so close that they overlap on the next check - and that they are more computationally expensive than static methods. Extra math is required to calculate the exact collision time between two moving spheres, and all potential collision events in a time step have to be stored and sorted in time order for correct processing. Furthermore, all spheres involved in collisions have to be moved several times in a single time step.

Nonetheless, dynamic collision detection can be implemented very efficiently, by combining a spatial data structure to quickly find spheres that can potentially collide and a heap data structure with lazy evaluation to quickly access the next collision event during a time step. The source code provided on the download page uses such data structures to simulate the movement of many spheres inside a 2D or 3D box, with an additional (larger) sphere that a user can drag with a mouse to interact with the other spheres.

Figure 1: Simulation of 8,123 particles of radius 1 in a square box of side length 150. The large grey disk can be dragged by the user and will push the smaller particles around. On a 2.4 GHz Athlon 64, this simulation runs at about 100 fps when idle, and drops down to about 2 fps when the large disk is quickly dragged through areas where particles are stacked very densely. In those cases, the simulation has to process upwards of 400,000 collisions per time step.

Project Details

The example program uses the following algorithms and data structures:

A cell grid data structure to reduce the time to find any pair of potentially colliding spheres from O(n²) to expected O(n).
A traversal algorithm that treats a sphere leaving its current grid cell and entering a new cell as a pseudo-collision to ensure that collisions between fast-moving spheres are never missed.
A priority queue implemented as a heap to store and sort all (potential) collision events detected during a time step.
Lazy removal of invalidated collision events from the priority queue. If two spheres collide, all future collision events involving either one of the two spheres need to be invalidated, because the spheres will change velocities. Lazy removal will not process the entire queue to explicitly remove those events, but will flag both spheres as updated, and then ignore any collision event that refers to at least one updated sphere. This allows a very simple implementation of the priority queue as a heap, without the need for removal operations.

Project Status

This is a one-shot project that grew out of a class project I wrote for the ECS 277 - Advanced Visualization class I took in spring quarter 2000. The final version (so far) of the project source code can be downloaded from the download page.

Pages in this Section

Download page: Contains the complete source code for the collision detection example program.