Continuous Penetration Depth Computation for Rigid Models using Dynamic Minkowski Sums

 

Youngeun Lee1, Evan Behar2, Jyh-Ming Lien2 and Young J. Kim1

1Department of Computer Science & Engineering

Ewha Womans University, Seoul, Korea

youngeunlee@ewhain.net, kimy@ewha.ac.kr

2Department of Computer Science

George Mason University, VA, USA

behare@gmail.com, jmlien@cs.gmu.edu

 

Computer-Aided Design [Paper]

(Presented at the Symposium on Solid and Physical Modeling 2016)

 

 

   

 

    Abstract

   We present a novel, real-time algorithm for computing the continuous penetration depth (CPD) between two interpen-etrating rigid models bounded by triangle meshes. Our algorithm guarantees gradient continuity for the penetration depth (PD) results, unlike conventional penetration depth (PD) algorithms that may have directional discontinuity due to the Euclidean projection operator involved with PD computation. Moreover, unlike prior CPD algorithms, our algorithm is able to handle an orientation change in the underlying model and deal with a topologically-complicated model with holes. Given two intersecting models, we interpolate tangent planes continuously on the boundary of the Minkowski sums between the models and nd the closest point on the boundary using Phong projection. Given the high complexity of computing the Minkowski sums for polygonal models in 3D, our algorithm estimates a solution subspace for CPD and dynamically constructs and updates the Minkowski sums only locally in the subspace. We implemented our algorithm on a standard PC platform and tested its performance in terms of speed and continuity using various benchmarks of complicated rigid models, and demonstrated that our algorithm can compute CPD for general polygonal models consisting of tens of thousands of triangles with a hole in a few milli-seconds while guaranteeing the continuity of PD gradient. Moreover, our algorithm can compute more optimal PD values than a state-of-the-art PD algorithm due to the dynamic Minkowski sum computation.

 

    Benchmarking Scenarios

  1. Cone & Axes

 The red cone moves along the blue arrow while penetrating into the yellow axes.

                           

PD magnitudes and directions of our CPD and PD by PolyDepth

 

  2. Spoon & Cup

 The red spoon moves along the blue arrow while penetrating into the yellow cup.

                           

PD magnitudes and directions of our CPD and PD by PolyDepth

 

  3. Fish & Torus

 The red fish moves along the blue arrow while penetrating into the yellow torus.

                           

PD magnitudes and directions of our CPD and PD by PolyDepth

 

  4. Torus & Torus

 The red torus moves along the blue arrow while penetrating into the yellow torus.

                           

PD magnitudes and directions of our CPD and PD by PolyDepth

 

   Related Links

 

   PhongPD:

   http://graphcs.ewha.ac.kr/PhongPD

 

   Weighted Averages on Surfaces Library:

   http://igl.ethz.ch/projects/wa/

 

  m+3d Library:

   http://masc.cs.gmu.edu/wiki/SimpleMsum

 

 

Copyright 2015 Computer Graphics Laboratory

Dept of Computer Science & Engineering

Ewha Womans University, Seoul, Korea

Last update: 2015-06-05

[°³ÀÎÁ¤º¸º¸È£¹æħ]