Fast penetration depth computation for physically-based animation

Young J. Kim, Miguel A. Otaduy, Ming C. Lin, Dinesh Manocha

Research output: Contribution to conferencePaperpeer-review

71 Scopus citations


We present a novel and fast algorithm to compute penetration depth (PD) between two polyhedral models for physically-based animation. Given two overlapping polyhedra, it computes the minimal translation distance to separate them using a combination of object-space and image-space techniques. The algorithm computes pair-wise Minkowski sums of decomposed convex pieces and performs a closest point query using rasterization hardware. It uses bounding volume hierarchies, object-space and image-space culling algorithms to further accelerate the computation and refines the estimated PD in a hierarchical manner. We demonstrate its application to contact response computation and a time-stepping method for dynamic simulation.

Original languageEnglish
Number of pages9
StatePublished - 2002
EventASM SIGGRAPH Symposium on Computer Animation - San Antonio, TX, United States
Duration: 21 Jul 200222 Jul 2002


ConferenceASM SIGGRAPH Symposium on Computer Animation
Country/TerritoryUnited States
CitySan Antonio, TX


  • Collision detection
  • Dynamics simulation
  • Geometric modeling
  • Graphics hardware
  • Image-space computations
  • Robotics


Dive into the research topics of 'Fast penetration depth computation for physically-based animation'. Together they form a unique fingerprint.

Cite this