Collision detection using spherical voronoi diagrams = 구면 보로노이 다이아그램을 이용한 충돌 탐지

Collision detection is an important issue in many fields such as robot control, computer animation and virtual reality. Although it has been extensively investigated, the issue remains as an unsolved problem. The recently popular algorithms for collision detection problems are the incremental ones which utilize convexity and local coherence to verify the closest points. However, the incremental algorithms have such critical drawbacks like failure to detect high-speed collisions and dependence of collision times on the time step size of animation. In this thesis, in order to find out a new method which can resolve the drawbacks we are concerned with a more restricted but non-trivial version of the problem: Given a fixed infinite plane and a moving convex polyhedron, compute their collision time. This problem is an abstraction of a real-world problem, which arises in an environment with a moving object bouncing off the ground. The problem inherently requires distance evaluation between them. We present an efficient collision detection algorithm which constructs a distance function of time between them. Hence, we are able to resolve the drawbacks of the incremental algorithms. We employ the notion of the Gauss sphere to construct spherical extreme vertex diagrams for solving an extreme vertex problem and its generalized extreme vertex problem efficiently. Using the spherical extreme vertex diagram, we give an efficient algorithm for computing the Euclidean distance from a polyhedron and a plane at a given time in $O(\log n)$ time. With this algorithm as a tool, we are able to construct a distance function of time between them. The polyhedron collides with the plane where the distance function first vanishes. The interval Newton``s method is employed to obtain the collision time within a given tolerance. Hence, the collision time of our algorithm is independent of time step size whereas those of other algorithms are not. The performance of the distance computatio...
Kim, Hong-OhresearcherShin, Sung-Yongresearcher김홍오researcher신성용researcher
Issue Date
135099/325007 / 000925097

학위논문(박사) - 한국과학기술원 : 수학과, 1998.2, [ iv, 89 p. ]


Spherical extreme vertex diagrams; Point-plane duality; 충돌 탐지; 구면 보로노이 다이아그램; 구면 근점 다이아그램; 점-평면 이중성; Collision detection; Spherical voronoi diagrams

Appears in Collection
Files in This Item
There are no files associated with this item.
  • Hit : 55
  • Download : 0
  • Cited 0 times in thomson ci


  • mendeley


rss_1.0 rss_2.0 atom_1.0