  We present a real-time algorithm that finds the Penetration Depth (PD)
between general polygonal models based on iterative and local optimization
techniques. Given an in-collision configuration of an object in configuration
space, we find an initial collision-free configuration using several methods
such as centroid difference, maximally clear configuration, motion coherence,
random configuration, and sampling-based search. We project this configuration
on to a local contact space using a variant of continuous collision detection
algorithm and construct a linear convex cone around the projected
configuration. We then formulate a new projection of the in-collision
configuration onto the convex cone as a Linear Complementarity Problem (LCP),
which we solve using a type of Gauss-Seidel iterative algorithm. We repeat this
procedure until a locally optimal PD is obtained. Our algorithm can process
complicated models consisting of tens of thousands triangles at interactive
rates.

Graphics;Computational Geometry;Robotics