Fast collision detection among multiple moving spheres

摘要

This paper presents an event-driven approach that efficientlyndetects collisions among multiple ballistic spheres moving in the 3Dnspace. Adopting a hierarchical uniform space subdivision scheme, we arenable to trace the trajectories of spheres and their time-varying spatialndistribution. We identify three types of events to detect the sequencenof all collisions during our simulation: collision, entering, andnleaving. The first type of event is due to actual collisions, and thenother two types occur when spheres move from subspace to subspace in thenspace. Tracing all such events in the order of their occurring times, wenare able to avoid fixed time step simulation. When the size of thenlargest sphere is bounded by a constant multiple of that of thensmallest, it takes O(n¯c log n+n¯e lognn) time with O(n) space after O(n log n) time preprocessing to simulatenn moving spheres, where n¯c and n¯e arenthe number of actual collisions and that of entering and leaving eventsnduring the simulation, respectively. Since n¯e, dependsnon the size of subspaces, we modify the collision model from kineticntheory for molecular gas to determine the subspace sizes for the spacensubdivision scheme, that minimize simulation time. Experimental resultsnshow that collision detection can be done in linear time in n over anlarge range