An Efficient Collision Detection Algorithm
for Polytopes in Virtual Environments


by Chung Tat Leung, Kelvin
for the degree of Master of Philosophy
at the Department of Computer Science,
University of Hong Kong
in September, 1996.

Abstract

The problem of collision detection is fundamental to interactive applications such as computer animation and virtual environments. In these fields, prompt recognition of possible impacts and the closest pair of points between two polytopes in collision are important for computing real-time response. We present a simple exact collision detection algorithm for convex polytopes. The algorithm finds quickly a separating plane between two polytopes if they are non-colliding. The validity of this separating plane is verified in constant time instead of linear time as in previous methods \cite{RichRabbitz}. Besides, our algorithm continues to find another separating plane if the current one is not a valid separating plane until collision is detected. Our algorithm guarantees to find a separating plane in a finite number of steps if there is no collision between the two polytopes. In the case of collision, the algorithm reports the closest pair of points between them since the contact points are useful for computing response. In the case of non-collision, the separating plane found for one time frame is cached as a witness for the next time frame. This use of time coherence further speeds up the algorithm in dynamic applications. Both temporal and geometric coherences are exploited to make this algorithm run in expected constant time empirically. In practice, our algorithm is significantly faster than existing methods.

Main Contributions

A new simple and efficient algorithm, called separating vector algorithm, for collision detection of polytopes in virtual environments.
An improved Gilbert's algorithm to compute the closest pair of points more robustly and efficiently by exploiting geometric and temporal coherences.
A new O(log n) algorithm to find a supporting vertex of a polytope with O(n) preprocessing where n is the total number of vertices in polytopes.
A technique that makes use of the hierarchical representation of polytopes to find a supporting vertex by local search.
An implementation of a collision detection library, called Q_COLLIDE (Quick collision detection library), based on our algorithm.
Experiments show that our collision detection library Q_COLLIDE is more efficient than the currently fastest collision detection library I_COLLIDE in all situations, especially when the rotational/translational velocity of polytopes in the environment is high or the complexity of polytopes is high. In particular, Q_COLLIDE is at least one order of magnitude faster then I_COLLIDE when the number of vertices of each polytope exceeds 200.

Overview of the Thesis

This thesis is organized in a way that each chapter is based on the foundation provided by the preceding chapters. We begin in Chapter 2 to describe basic concepts used in the development of the algorithms presented later. The computational geometry and modeling concepts we describe are convex polyhedra, hyperplanes, Minkowski sum and boundary representation.

Chapter 3 presents the main idea of our separating vector algorithm, which is a simple and practical algorithm for collision detection between two polytopes. In this chapter, we describe how the algorithm can be used to detect non-interference polytopes efficiently - by exploiting geometric and temporal coherences to find a separating plane between two polytopes in expected constant time. The algorithm is particularly suitable for dynamic collision detection. Experiments show that it can eliminate about 99% of non-interference polytopes with at most four iterations of the algorithm, nearly independent of polytopes' shape and complexity, before a usually more time-consuming exact collision detection algorithm must be invoked.

Chapter 4 extends the separating vector algorithm to detect collision between two polytopes by enforcing a termination condition so that the algorithm can detect if a collision occurs. Then we prove that the algorithm is guaranteed to find a separating plane if it exists. The later parts of this chapter deal with the complexity of the algorithm and its possible improvements.

Chapter 5 describes how to extend the separating vector algorithm so that the closest pair of points is also reported when there is a collision, which is useful in computing responses when collision. We first review the idea of Gilbert's algorithm and Johnson's algorithm. Then we describe how to improve Gilbert's algorithm so that it is more robust and supporting vertices can be found in O(log n) time instead of O(n) time. Afterwards, we describe how to use local search to further improve the complexity of Gilbert's algorithm when both geometric and temporal coherences are exploited. Finally, we describe how to integrate our separating vector algorithm with the improved Gilbert's algorithm seamlessly so that the whole algorithm can run in expected constant time empirically.

In Chapter 6, we will discuss the implementation details of our separating vector algorithm and the improved Gilbert's algorithm. We implemented our algorithm as a collision detection library, called Q_COLLIDE. Experiments have been carried out to verify the nice properties of our algorithm. To test the efficiency and effectiveness of our algorithm, we compare it with I_COLLIDE - an implementation of the closest feature tracking algorithm, which is the fastest collision detection library for polytopes so far. Our results show that Q_COLLIDE is more efficient in all cases, especially when the rotational/translational velocity of polytopes in the environment is high or the complexity of polytopes is high.

The thesis is concluded in Chapter 7.

Collision Library

Q_COLLIDE library

Complete Thesis

thesis.ps.gz (87 pages, 506K gzip Postscript)

thesis.pdf
Jump to My Unofficial Web page
Please send any comment and suggestions to [email protected].

Hosted by www.Geocities.ws

1