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 computation and the collision detection algorithm attests their promise for real-time dynamic simulations as well as applications in a computer generated virtual environment.
본 논문에서는 구면 보로노이 다이아그램과 구면 근점 다이아그램을 이용하여 움직이는 다면체와 평면과의 충돌을 정확하고 빠르게 찾는 알고리즘을 제시하였다. 대부분의 충돌 파악 알고리즘들은 애니매이션할 시간을 등간격으로 나누어 각 시점에서의 충돌 여부를 알기 위하여 두 물체간의 거리를 계산한다. 이러한 알고리즘들은 움직이는 물체의 속도가 빠르지 않다는 가정하에서 충돌 여부를 파악했는데, 이는 등간격의 크기를 제한하는 단점을 가지고 있다. 따라서, 임의의 속도를 가지면서 움직이는 물체들간의 충돌을 탐지하기에는 올바른 방법이 아니고 이에 대한 완전한 해법을 필요로 하게 되었다. 본 논문은 이에 대한 해결책을 제시하고자 기본적인 모델인 움직이는 다면체와 평면간의 충돌 문제를 다루었고, 이 모델에 대한 해결책이 보다 복잡한 모델에 응용될 수 있음을 알 수 있다. 이때, 두 물체간의 거리 계산은 매우 중요한 요소로 작용한다. 본 논문은 두 물체간의 거리를 시간에 대한 함수로 표현하였고, 이에 따라 움직이는 물체의 충돌 여부를 정확하고 신속하게 파악할 수 있었다. 우선, 볼록 다면체의 기본 성질과 그와 연관되는 자료구조에 대한 연구를 하였다. Brown은 구면 상의 점들의 집합이 주어졌을때, 이들에 대한 구면 보로노이 다이아그램을 $O(n \log n)$에 만드는 알고리즘을 제시하였다. 볼록 $n$-면체에 있는 면의 단위 법선 벡터를 Gauss map에 의하여 구면에 $n$ 개의 점을 대응시킬 수 있다. 우리는 이 구면 집합에 대한 구면 보로노이 다이아그램을 $O(n)$에 구하는 알고리즘을 제시하였다. 그리고, 보로노이 다이아그램의 dual인 디로노이 삼각분할에 대해서도 구면으로 확장 가능한지를 조사하였다. 평면 상의 디로노이 삼각분할은 중첩되는 삼각형이 없는 반면, 구면 상에 정의되는 디로노이 삼각분할은 주어진 점들의 상관관계에 따라 중첩할 수도 있다는 사실을 알게 되었고, 중첩하는 조건을 제시하였다. 평면 디로노이 삼각분할은 중첩성을 제외하면 구면 디로노이 삼각분할로 모두 확장가능하다. 볼록 다면체에 의해서 생성되는 구면 상의 점들에 대한 구면 디로노이 삼각분할은 중첩하지 않음을 알 수 있었다. 볼록다면체의 기본 성질을 이용하여 움직이는 다면체의 근점 문제를 해결하였다. 즉, 음직임에 따라 다면체의 근점은 변하게 되는데, 이러한 근점들의 나열과 그 변하는 시점을 구하는 알고리즘을 제시하였다. 볼록 다면체에 dual-변환을 적용하여 원점을 포함하는 볼록헐을 구하고, 이를 다시 Gauss 구면에 투영시켜 새로운 구면 근점 다이아그램을 만들었다. 근점 다이아그램의 영역은 다면체의 꼭지점 하나를 대응하게 되는데, 질의점이 속하는 영역을 알면 그 영역에 대응되는 꼭지점이 그 시점에서 근점이 된다는 사실을 알 수 있었다. 따라서, 질의점이 움직이는 궤적을 알게되면 변하는 근점들을 알게된다. 또한 변하는 시점을 알 수 있어, 애니매이션 시간동안의 두 물체의 거리 함수를 구하였고, 두 물체의 충돌 시점은 그 거리함수의 첫번째 근이므로, 그 근을 찾기 위하여, interval Newton 방법을 사용하였다. 이와 같은 방법에 의하면 충돌 시점을 찾는데 걸리는 시간이 매우 단축되고, 애니메이션 시간 등간격의 크기에 상관없이 주어진 오차안에 충돌시점을 찾을 수 있다.
