PolyDepth: Real-time penetration depth computation using iterative contact-space projection

Changsoo Je, Min Tang, Youngeun Lee, Minkyoung Lee, Young J. Kim

Research output: Contribution to journalArticlepeer-review

36 Scopus citations


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.

Original languageEnglish
Article number5
JournalACM Transactions on Graphics
Issue number1
StatePublished - Jan 2012


  • Animation
  • Collision detection
  • Dynamics
  • Penetration depth
  • Polygon-soups


Dive into the research topics of 'PolyDepth: Real-time penetration depth computation using iterative contact-space projection'. Together they form a unique fingerprint.

Cite this