Efficient distance computation in configuration space

Liangjun Zhang; Young J. Kim; Dinesh Manocha

doi:10.1016/j.cagd.2008.04.005

Efficient distance computation in configuration space

Liangjun Zhang, Young J. Kim, Dinesh Manocha

Department of Computer Science & Engineering

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

2 Scopus citations

Abstract

We address the problem of computing a measure of the distance between two configurations of a rigid or an articulated model. The underlying distance metric is defined as the maximum length of the displacement vectors over the vertices of the model between two configurations. Our algorithm is based on Chasles theorem from Screw theory, and we show that for a rigid model the maximum distance is realized by one of the vertices on the convex hull of the model. We use this formulation to compute the distance, and present two acceleration techniques: incremental walking on the dual space of the convex hull and culling vertices on the convex hull using a bounding volume hierarchy (BVH). Our algorithm can be easily extended to articulated models by maximizing the distance over its each link and we also present culling techniques to accelerate the computation. We highlight the performance of our algorithm on many complex models and demonstrate its applications to generalized penetration depth computation and motion planning.

Original language	English
Pages (from-to)	489-502
Number of pages	14
Journal	Computer Aided Geometric Design
Volume	25
Issue number	7
DOIs	https://doi.org/10.1016/j.cagd.2008.04.005
State	Published - Oct 2008

Bibliographical note

Funding Information:
We would like to thank Frank Chongwoo Park, Steven M. LaValle, Jean-Claude Latombe and Bert Jütler for useful discussions. We would also like to thank the anonymous reviewers for their valuable comments. This research was supported in part by ARO Contracts DAAD19-02-1-0390 and W911NF-04-1-0088, NSF awards 0400134 and 0118743, ONR Contract N00014-01-1-0496, DARPA/RDECOM Contract N61339-04-C-0043 and Intel. Young J. Kim was supported in part by the Korea Research Foundation Grant funded by the Korean Government (KRF-2007-331-D00400) and the IT R&D program of MKE/IITA (2008-F-033-01, Development of Real-time Physics Simulation Engine for e-Entertainment).

Keywords

Configuration space
Distance metric

Access to Document

10.1016/j.cagd.2008.04.005

Cite this

@article{b4f7e9d029df494b8dcb9c040e3ef1f0,

title = "Efficient distance computation in configuration space",

abstract = "We address the problem of computing a measure of the distance between two configurations of a rigid or an articulated model. The underlying distance metric is defined as the maximum length of the displacement vectors over the vertices of the model between two configurations. Our algorithm is based on Chasles theorem from Screw theory, and we show that for a rigid model the maximum distance is realized by one of the vertices on the convex hull of the model. We use this formulation to compute the distance, and present two acceleration techniques: incremental walking on the dual space of the convex hull and culling vertices on the convex hull using a bounding volume hierarchy (BVH). Our algorithm can be easily extended to articulated models by maximizing the distance over its each link and we also present culling techniques to accelerate the computation. We highlight the performance of our algorithm on many complex models and demonstrate its applications to generalized penetration depth computation and motion planning.",

keywords = "Configuration space, Distance metric",

author = "Liangjun Zhang and Kim, {Young J.} and Dinesh Manocha",

note = "Funding Information: We would like to thank Frank Chongwoo Park, Steven M. LaValle, Jean-Claude Latombe and Bert J{\"u}tler for useful discussions. We would also like to thank the anonymous reviewers for their valuable comments. This research was supported in part by ARO Contracts DAAD19-02-1-0390 and W911NF-04-1-0088, NSF awards 0400134 and 0118743, ONR Contract N00014-01-1-0496, DARPA/RDECOM Contract N61339-04-C-0043 and Intel. Young J. Kim was supported in part by the Korea Research Foundation Grant funded by the Korean Government (KRF-2007-331-D00400) and the IT R&D program of MKE/IITA (2008-F-033-01, Development of Real-time Physics Simulation Engine for e-Entertainment).",

year = "2008",

month = oct,

doi = "10.1016/j.cagd.2008.04.005",

language = "English",

volume = "25",

pages = "489--502",

journal = "Computer Aided Geometric Design",

issn = "0167-8396",

publisher = "Elsevier B.V.",

number = "7",

}

TY - JOUR

T1 - Efficient distance computation in configuration space

AU - Zhang, Liangjun

AU - Kim, Young J.

AU - Manocha, Dinesh

N1 - Funding Information: We would like to thank Frank Chongwoo Park, Steven M. LaValle, Jean-Claude Latombe and Bert Jütler for useful discussions. We would also like to thank the anonymous reviewers for their valuable comments. This research was supported in part by ARO Contracts DAAD19-02-1-0390 and W911NF-04-1-0088, NSF awards 0400134 and 0118743, ONR Contract N00014-01-1-0496, DARPA/RDECOM Contract N61339-04-C-0043 and Intel. Young J. Kim was supported in part by the Korea Research Foundation Grant funded by the Korean Government (KRF-2007-331-D00400) and the IT R&D program of MKE/IITA (2008-F-033-01, Development of Real-time Physics Simulation Engine for e-Entertainment).

PY - 2008/10

Y1 - 2008/10

N2 - We address the problem of computing a measure of the distance between two configurations of a rigid or an articulated model. The underlying distance metric is defined as the maximum length of the displacement vectors over the vertices of the model between two configurations. Our algorithm is based on Chasles theorem from Screw theory, and we show that for a rigid model the maximum distance is realized by one of the vertices on the convex hull of the model. We use this formulation to compute the distance, and present two acceleration techniques: incremental walking on the dual space of the convex hull and culling vertices on the convex hull using a bounding volume hierarchy (BVH). Our algorithm can be easily extended to articulated models by maximizing the distance over its each link and we also present culling techniques to accelerate the computation. We highlight the performance of our algorithm on many complex models and demonstrate its applications to generalized penetration depth computation and motion planning.

AB - We address the problem of computing a measure of the distance between two configurations of a rigid or an articulated model. The underlying distance metric is defined as the maximum length of the displacement vectors over the vertices of the model between two configurations. Our algorithm is based on Chasles theorem from Screw theory, and we show that for a rigid model the maximum distance is realized by one of the vertices on the convex hull of the model. We use this formulation to compute the distance, and present two acceleration techniques: incremental walking on the dual space of the convex hull and culling vertices on the convex hull using a bounding volume hierarchy (BVH). Our algorithm can be easily extended to articulated models by maximizing the distance over its each link and we also present culling techniques to accelerate the computation. We highlight the performance of our algorithm on many complex models and demonstrate its applications to generalized penetration depth computation and motion planning.

KW - Configuration space

KW - Distance metric

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

U2 - 10.1016/j.cagd.2008.04.005

DO - 10.1016/j.cagd.2008.04.005

M3 - Article

AN - SCOPUS:49949093125

SN - 0167-8396

VL - 25

SP - 489

EP - 502

JO - Computer Aided Geometric Design

JF - Computer Aided Geometric Design

IS - 7

ER -

Efficient distance computation in configuration space

Abstract

Bibliographical note

Keywords

Access to Document

Fingerprint

Cite this