Proximity queries between convex objects: An interior point approach for implicit surfaces

In this paper, we present an interior point approach to exact distance computation between convex objects represented as intersections of implicit surfaces. The implicit surfaces considered include planes (polyhedra), quadrics, and generalizations of quadrics including superquadrics and hyperquadrics, as well as intersections of these surfaces. Exact distance computation algorithms are particularly important for applications involving objects that make contact, such as in dynamic simulations and in contact point prediction for dextrous manipulation. They can also be used in the narrow phase of hierarchical collision detection. In contrast to geometric approaches developed for polyhedral objects, we formulate the distance computation problem as a convex optimization problem; this optimization formulation has been previously described for polyhedral objects. We demonstrate that for general convex objects represented as implicit surfaces, interior point approaches are reasonably fast and in some cases, owing to their global convergence properties, are the only provably good choice for solving proximity query problems. We use an interior point algorithm that solves the KKT conditions obtained from the convex programming formulation. We present implementation results for example implicit surface objects and demonstrate that distance computation rates of about 1 kHz can be achieved.