Collision detection using spherical voronoi diagrams

Abstract

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...