Abstract | ||
---|---|---|
Collision detection is critical for applications that demand a great deal of spatial interaction among objects. In such applications the trajectory of an object is often not known in advance either since a user is allowed to move an object at his/her will, or since an object moves under the rules that are hard to describe by exact mathematical formulas. In this paper we present a new algorithm that efficiently detects the collisions among moving spheres with unknown trajectories. We assume that the current position and velocity of every sphere can be probed at any time although its trajectory is unknown. We also assume that the magnitude of the acceleration of each sphere is bounded. Under these assumptions, we represent the bounding volume of the sphere as a moving sphere of variable radius, called a time-varying bound. Whenever the time-varying bounds of two spheres collide with each other, they are checked for actual collision. Exploiting these bounds, the previous event-driven approach for detecting the collisions among multiple moving spheres with ballistic trajectories is generalized for those with unknown trajectories. The proposed algorithm shows an interactive performance for thousands of moving spheres with unknown trajectories without any hardware help. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1007/s00453-005-1153-2 | Algorithmica |
Keywords | Field | DocType |
object move,current position,unknown trajectory,spheres collide,ballistic trajectory,computational geometry.,event-driven approach,actual collision,new algorithm,proposed algorithm,Unknown Trajectories,time-varying bound,computer animation,interactive applications,Efficient Collision Detection,collision detection | Discrete mathematics,Mathematical optimization,Bounding volume,Collision detection,Computational geometry,Algorithm,Collision,SPHERES,Acceleration,Mathematics,Trajectory,Bounded function | Journal |
Volume | Issue | ISSN |
43 | 3 | 0178-4617 |
Citations | PageRank | References |
9 | 0.71 | 24 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ho Kyung Kim | 1 | 9 | 1.38 |
Leo J. Guibas | 2 | 5202 | 536.33 |
Sung Yong Shin | 3 | 1904 | 168.33 |