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

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

doi:10.1109/TVCG.2004.1260767

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

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

Department of Computer Science & Engineering

Research output: Contribution to journal › Article › peer-review

44 Scopus citations

Abstract

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 language	English
Pages (from-to)	152-163
Number of pages	12
Journal	IEEE Transactions on Visualization and Computer Graphics
Volume	10
Issue number	2
DOIs	https://doi.org/10.1109/TVCG.2004.1260767
State	Published - 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.

Keywords

Gauss map
Haptic rendering
Incremental algorithm
Minkowski sums
Penetration depth

Access to Document

10.1109/TVCG.2004.1260767

Cite this

@article{c861d6e32cbf48c78ae6ae4514b22e55,

title = "Incremental Penetration Depth Estimation between Convex Polytopes Using Dual-Space Expansion",

abstract = "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.",

keywords = "Gauss map, Haptic rendering, Incremental algorithm, Minkowski sums, Penetration depth",

author = "Kim, {Young J.} and Lin, {Ming C.} and Dinesh Manocha",

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.",

year = "2004",

month = mar,

doi = "10.1109/TVCG.2004.1260767",

language = "English",

volume = "10",

pages = "152--163",

journal = "IEEE Transactions on Visualization and Computer Graphics",

issn = "1077-2626",

publisher = "IEEE Computer Society",

number = "2",

}

TY - JOUR

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

AU - Kim, Young J.

AU - Lin, Ming C.

AU - Manocha, Dinesh

N1 - 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.

PY - 2004/3

Y1 - 2004/3

N2 - 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.

AB - 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.

KW - Gauss map

KW - Haptic rendering

KW - Incremental algorithm

KW - Minkowski sums

KW - Penetration depth

UR - http://www.scopus.com/inward/record.url?scp=1342282179&partnerID=8YFLogxK

U2 - 10.1109/TVCG.2004.1260767

DO - 10.1109/TVCG.2004.1260767

M3 - Article

C2 - 15384640

AN - SCOPUS:1342282179

SN - 1077-2626

VL - 10

SP - 152

EP - 163

JO - IEEE Transactions on Visualization and Computer Graphics

JF - IEEE Transactions on Visualization and Computer Graphics

IS - 2

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this