Fast collision detection among multiple moving spheres

The paper presents an event driven approach that efficiently detects collisions among multiple moving spheres of uniform radius. We divide the space containing the spheres into uniform subspaces of cell structure. Each sphere intersecting a subspace is tested against the others intersecting the same subspace for possible collisions. We identify three types of events to detect the sequence of all collisions during our simulation: collision, entering, and leaving. The first type of events is due to actual collisions, and the other two types occur when spheres move from subspace to subspace. By tracing all such events in the order of their occurring times, we are able to simulate n moving spheres with proper collision response in O(n_c log n+n_e log n) time with O(n) space after O(n log n) time preprocessing, where n_c and n_e are the number of actual collisions and that of entering and leaving events during the simulation, respectively. Since n_e depends on the size of subspaces, we adopt the collision model from kinetic theory for molecular gas (Feynmann et al., 1963) to determine the subspace size that minimizes simulation time. Experimental results show that collision detection can be done in linear time in n over a large range