Incremental Penetration Depth Estimation between Convex Polytopes Using Dual-Space Expansion

Young J. Kim, Ming C. Lin, Dinesh Manocha

Research output: Contribution to journalArticlepeer-review

43 Scopus citations


We present a fast algorithm to estimate the penetration depth between convex polytopes in 3D. The algorithm incrementally seeks a "locally optimal solution" by walking on the surface of the Minkowski sums. The surface of the Minkowski sums is computed implicitly by constructing a local dual mapping on the Gauss map. We also present three heuristic techniques that are used to estimate the initial features used by the walking algorithm. We have implemented the algorithm and compared its performance with earlier approaches. In our experiments, the algorithm is able to estimate the penetration depth in about a milli-second on an 1 GHz Pentium PC. Moreover, its performance is almost independent of model complexity in environments with high coherence between successive instances.

Original languageEnglish
Pages (from-to)152-163
Number of pages12
JournalIEEE Transactions on Visualization and Computer Graphics
Issue number2
StatePublished - Mar 2004

Bibliographical note

Funding Information:
This research is supported in part by US Army Research Offoce Contract DAAG55-98-1-0322, US Department of Energy ASCII Grant, US National Science Foundation Grants NSG-9876914, NSF DMI-9900157, and NSF IIS-982167, US Office of Naval Research Contracts N00014-01-1-0067 and N00014-01-1-0496, and Intel.


  • Gauss map
  • Haptic rendering
  • Incremental algorithm
  • Minkowski sums
  • Penetration depth


Dive into the research topics of 'Incremental Penetration Depth Estimation between Convex Polytopes Using Dual-Space Expansion'. Together they form a unique fingerprint.

Cite this