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

Authors:

Nilanjan Chakraborty
Department of Computer Science
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
chakrn2 at cs.rpi.edu

Jufeng Peng
Progressive Insurance Company
jamespjf at gmail.com

Srinivas Akella
Department of Computer Science
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
sakella at cs.rpi.edu

John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj at rpi.edu

IEEE Transactions on Robotics 24(1), 2008, pages 211-220.

An earlier version of this paper appeared in the Proceedings of ICRA2006, the 2006 IEEE International Conference on Robotics and Automation. The proceedings are for sale here.

Abstract:

This paper presents an interior point approach to exact distance computation between convex objects represented as intersections of implicit surfaces. Exact distance computation algorithms are particularly important for applications involving objects that make contact, such as in multibody 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 sufficiently fast, and owing to their global convergence properties, are the only provably good choice for solving proximity query problems for some object classes. We use a primal-dual interior point algorithm that solves the KKT conditions obtained from the convex programming formulation. For the case of polyhedra and quadrics, we establish a theoretical time complexity of O(n^1.5), where n is the number of constraints. We present implementation results for example implicit surface objects, including polyhedra, quadrics, and generalizations of quadrics such as superquadrics and hyperquadrics, as well as intersections of these surfaces. We demonstrate that in practice, the algorithm takes time linear in the number of constraints, and that distance computation rates of about 1 kHz can be achieved. We also extend the approach to proximity queries between deforming convex objects. Finally, we show that continuous collision detection for linearly translating objects can be performed by solving two related convex optimization problems. For polyhedra and quadrics, we establish that the computational complexity of this problem is O(n^1.5).
Index Terms: Proximity query, closest points, smooth objects, interior point algorithms, collision detection, multibody dynamic simulation.

Download the paper.

Return to my list of papers.