Proximity Queries between Convex Objects: An Interior Point Approach for Implicit Surfaces

  • Published 2005 in

Abstract

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 dynamics 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 a primal-dual interior point algorithm that solves the KKT conditions resulting from the convex programming formulation. We present preliminary implementation results, including distance computation between deforming superquadrics, to demonstrate the merit of the interior point approach.

Topics

3 Figures and Tables

Download Full PDF Version (Non-Commercial Use)