Efficient collision detection using fast distance-calculation algorithms for convex and non-convex objects

Abstract

This paper describes a practical and efficient collision detection algorithm for non-convex objects in R/sup 3/. The algorithm is based on two other distance calculation algorithms: one is for convex polyhedra and the other is for non-convex polyhedra. The applied algorithm is switched between convex and non-convex, according to the distance between the objects. The closest points between the objects are followed continuously in time and can be calculated by searching for the nearest neighbors of the previous closest points. This feature greatly improves the distance calculation speed and makes it possible, for instance, to pick and move an object with a mouse, interactively getting the distance between the object and other objects. The algorithm is implemented in C++, and embedded in a series of C++ class libraries for a graphic simulation system-which the authors have named ContactScope.