Efficient Penetration Depth Computation Between Rigid Models Using Contact Space Propagation Sampling

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations


  • Liang He
  • Jia Pan
  • Danwei Li
  • Dinesh Manocha


Original languageEnglish
Article number7342933
Pages (from-to)10-17
Journal / PublicationIEEE Robotics and Automation Letters
Issue number1
Online published1 Dec 2015
Publication statusPublished - Jan 2016


—We present a novel method to compute the approximate global penetration depth (PD) between two nonconvex geometric models. Our approach consists of two phases: offline precomputation and run-time queries. In the first phase, our formulation uses a novel sampling algorithm to precompute an approximation of the high-dimensional contact space
between the pair of models. As compared with prior random sampling algorithms for contact space approximation, our propagation sampling considerably speeds up the precomputation and yields a high quality approximation. At run-time, we perform a nearest-neighbor query and local projection to efficiently compute the translational or generalized PD. We demonstrate the performance of our approach on complex 3-D benchmarks with tens or hundreds or thousands of triangles, and we observe significant
improvement over previous methods in terms of accuracy, with a modest improvement in the run-time performance

Research Area(s)

  • Contact Modelling, Simulation and Animation