Fast penetration depth estimation using rasterization hardware and hierarchical refinement

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

doi:10.1007/978-3-540-45058-0_30

Fast penetration depth estimation using rasterization hardware and hierarchical refinement

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

Department of Computer Science & Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

We present a novel and fast algorithm to estimate penetration depth (PD) between two polyhedral models. Given two overlapping polyhedra, it computes the minimal translational distance to separate them using a combination of discretized computations and hierarchical refinement. The algorithm computes pairwise Minkowski sums of decomposed convex pieces, performs closest point query using rasterization hardware, and refines the estimated PD by incremental walking. It uses bounding volume hierarchies, model simplification, and culling algorithms to further accelerate the computation and refines the estimated PD in a hierarchical manner. We highlight its performance on complex models.

Original language	English
Title of host publication	Algorithmic Foundations of Robotics V
Pages	505-521
Number of pages	17
DOIs	https://doi.org/10.1007/978-3-540-45058-0_30
State	Published - 2004
Event	5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002 - Nice, France Duration: 15 Dec 2002 → 17 Dec 2002

Publication series

Name	Springer Tracts in Advanced Robotics
Volume	7 STAR
ISSN (Print)	1610-7438
ISSN (Electronic)	1610-742X

Conference

Conference	5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002
Country/Territory	France
City	Nice
Period	15/12/02 → 17/12/02

Access to Document

10.1007/978-3-540-45058-0_30

Cite this

@inproceedings{7e5f1459de6c4af7bd2216cc488ce7ae,

title = "Fast penetration depth estimation using rasterization hardware and hierarchical refinement",

abstract = "We present a novel and fast algorithm to estimate penetration depth (PD) between two polyhedral models. Given two overlapping polyhedra, it computes the minimal translational distance to separate them using a combination of discretized computations and hierarchical refinement. The algorithm computes pairwise Minkowski sums of decomposed convex pieces, performs closest point query using rasterization hardware, and refines the estimated PD by incremental walking. It uses bounding volume hierarchies, model simplification, and culling algorithms to further accelerate the computation and refines the estimated PD in a hierarchical manner. We highlight its performance on complex models.",

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

year = "2004",

doi = "10.1007/978-3-540-45058-0_30",

language = "English",

isbn = "3540404767",

series = "Springer Tracts in Advanced Robotics",

pages = "505--521",

booktitle = "Algorithmic Foundations of Robotics V",

note = "5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002 ; Conference date: 15-12-2002 Through 17-12-2002",

}

Kim, YJ, Lin, MC & Manocha, D 2004, Fast penetration depth estimation using rasterization hardware and hierarchical refinement. in Algorithmic Foundations of Robotics V. Springer Tracts in Advanced Robotics, vol. 7 STAR, pp. 505-521, 5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002, Nice, France, 15/12/02. https://doi.org/10.1007/978-3-540-45058-0_30

TY - GEN

T1 - Fast penetration depth estimation using rasterization hardware and hierarchical refinement

AU - Kim, Young J.

AU - Lin, Ming C.

AU - Manocha, Dinesh

PY - 2004

Y1 - 2004

N2 - We present a novel and fast algorithm to estimate penetration depth (PD) between two polyhedral models. Given two overlapping polyhedra, it computes the minimal translational distance to separate them using a combination of discretized computations and hierarchical refinement. The algorithm computes pairwise Minkowski sums of decomposed convex pieces, performs closest point query using rasterization hardware, and refines the estimated PD by incremental walking. It uses bounding volume hierarchies, model simplification, and culling algorithms to further accelerate the computation and refines the estimated PD in a hierarchical manner. We highlight its performance on complex models.

AB - We present a novel and fast algorithm to estimate penetration depth (PD) between two polyhedral models. Given two overlapping polyhedra, it computes the minimal translational distance to separate them using a combination of discretized computations and hierarchical refinement. The algorithm computes pairwise Minkowski sums of decomposed convex pieces, performs closest point query using rasterization hardware, and refines the estimated PD by incremental walking. It uses bounding volume hierarchies, model simplification, and culling algorithms to further accelerate the computation and refines the estimated PD in a hierarchical manner. We highlight its performance on complex models.

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

U2 - 10.1007/978-3-540-45058-0_30

DO - 10.1007/978-3-540-45058-0_30

M3 - Conference contribution

AN - SCOPUS:84863277679

SN - 3540404767

SN - 9783540404767

T3 - Springer Tracts in Advanced Robotics

SP - 505

EP - 521

BT - Algorithmic Foundations of Robotics V

T2 - 5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002

Y2 - 15 December 2002 through 17 December 2002

ER -

Fast penetration depth estimation using rasterization hardware and hierarchical refinement

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this