Today I read a paper titled “PolyDepth: Real-time Penetration Depth Computation using Iterative Contact-Space Projection”
The abstract is:
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.