C-DIST: Efficient distance computation for rigid and articulated models in configuration space

Liangjun Zhang, Young J. Kim, Dinesh Manocha

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

18 Scopus citations

Abstract

The problem of distance computation arises in many applications including motion planning, CAD/CAM, dynamic simulation and virtual environments. Most prior work in this area has been restricted to separation or penetration distance computation between two objects. In this paper, we address the problem of computing a measure of distance between two configurations of a rigid or articulated model. The underlying distance metric is defined as the length of the longest displacement vector over the corresponding vertices of the model between two configurations. Our algorithm is based on Chasles theorem in Screw theory, and we show that the maximum distance can be realized only by a vertex of the convex hull of a rigid object. We use this formulation to compute the distance, and present two acceleration techniques to speed up the computation: 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 describe its application to proximity queries and motion planning.

Original languageEnglish
Title of host publicationProceedings - SPM 2007
Subtitle of host publicationACM Symposium on Solid and Physical Modeling
Pages159-169
Number of pages11
DOIs
StatePublished - 2007
EventSPM 2007: ACM Symposium on Solid and Physical Modeling - Beijing, China
Duration: 4 Jun 20076 Jun 2007

Publication series

NameProceedings - SPM 2007: ACM Symposium on Solid and Physical Modeling

Conference

ConferenceSPM 2007: ACM Symposium on Solid and Physical Modeling
Country/TerritoryChina
CityBeijing
Period4/06/076/06/07

Keywords

  • Configuration space
  • Distance metric

Fingerprint

Dive into the research topics of 'C-DIST: Efficient distance computation for rigid and articulated models in configuration space'. Together they form a unique fingerprint.

Cite this