PolyDepth: Real-time Penetration Depth Computation using Iterative Contact-Space Projection
This addresses the need for efficient collision resolution in robotics and simulation, though it is incremental as it builds on existing optimization and detection techniques.
The paper tackles the problem of computing Penetration Depth (PD) between polygonal models in real-time by using iterative contact-space projection and a Linear Complementarity Problem (LCP) solver, achieving interactive rates for models with tens of thousands of triangles.
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.