Fast Penetration Depth Computation Using Rasterization Hardware and Hierarchical Refinement
Young J. Kim youngkim@cs.unc.edu
Miguel A. Otaduy otaduy@cs.unc.edu
Ming C. Lin lin@cs.unc.edu
Dinesh Manocha dm@cs.umd.edu

Abstract: We present a novel and fast algorithm to compute penetration depth (PD) between two polyhedral models. Given two overlapping polyhedra, it computes the minimal translation distance to separate them using a combination of object-space and image-space techniques. The algorithm computes pairwise Minkowski sums of decomposed convex pieces, performs closest-point query using rasterization hardware and refines the estimated PD by object-space walking. It uses bounding volume hierarchies, model simplification, object-space and image-space culling algorithms to further accelerate the computation and refines the estimated PD in a hierarchical manner. We highlight its performance on complex models and demonstrate its application to dynamic simulation and tolerance verification. 
PUBLICATION
Fast Penetration Depth Computation for Physically-based Animation

Young J. Kim, Miguel A. Otaduy, Ming C. Lin, and Dinesh Manocha, ACM Symposium on Computer Animation, July 21-22, 2002.

Acrobat (1.8 Mb)

Powerpoint (911 KB)  

 

Closest Point Query Among the Union of Convex Polytopes Using Rasterization Hardware

Young J. Kim,  Kenneth Hoff, Ming C. Lin, and Dinesh Manocha, Journal  of Graphics Tools, 2003 (to appear).

Acrobat (169 KB)

 

Fast Penetration Depth Estimation Using Rasterization Hardware and Hierarchical Refinement

Young J. Kim,  Ming C. Lin,  and  Dinesh Manocha, Workshop on Algorithmic Foundations of Robotics (WAFR), Dec. 2002.

Acrobat (315 KB)  

 

Fast Penetration Depth Computation Using Rasterization Hardware and Hierarchical Refinement

Young J. Kim,  Miguel A. Otaduy, Ming C. Lin, and Dinesh Manocha, UNC-CH Tech. Rep. TR02-014, 2002.

Acrobat (2.0 Mb)

VIDEO

Mpeg (180 Mb)

Application Only (23.9 Mb)

RELATED LINKS

DEEP

youngkim@cs.unc.edu

last updated: 04/15/2003