loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Computer Animation 1997
Fast Collision Detection among Multiple Moving Spheres
Geneva, SWITZERLAND
June 04-June 07
ISBN: 0-8186-7984-0
Dong-Jin Kim, Korea Advanced Institute of Science and Technology
Sung-Yong Shin, Korea Advanced Institute of Science and Technology
Leonidas J. Guibas, Stanford University
This 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 occuring 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 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.
Index Terms:
Collision Detection, Event-Driven Approach, Physical Simulation, Computer Animation, Computational Geometry
Citation:
Dong-Jin Kim, Sung-Yong Shin, Leonidas J. Guibas, "Fast Collision Detection among Multiple Moving Spheres," ca, pp.1, Computer Animation 1997, 1997
Usage of this product signifies your acceptance of the Terms of Use.