TY - GEN

T1 - Generalized penetration depth computation

AU - Zhang, Liangjun

AU - Kim, Young J.

AU - Varadhan, Gokul

AU - Manocha, Dinesh

PY - 2006

Y1 - 2006

N2 - Penetration depth (PD) is a distance metric that is used to describe the extent of overlap between two intersecting objects. Most of the prior work in PD computation has been restricted to translational PD, which is defined as the minimal translational motion that one of the overlapping objects must undergo in order to make the two objects disjoint. In this paper, we extend the notion of PD to take into account both translational and rotational motion to separate the intersecting objects, namely generalized PD. When an object undergoes rigid transformation, some point on the object traces the longest trajectory. The generalized PD between two overlapping objects is defined as the minimum of the longest trajectories of one object under all possible rigid transformations to separate the overlapping objects. We present three new results to compute generalized PD between polyhedral models. First, we show that for two overlapping convex polytopes, the generalized PD is same as the translational PD. Second, when the complement of one of the objects is convex, we pose the generalized PD computation as a variant of the convex containment problem and compute an upper bound using optimization techniques. Finally, when both the objects are non-convex, we treat them as a combination of the above two cases, and present an algorithm that computes a lower and an upper bound on generalized PD. We highlight the performance of our algorithms on different models that undergo rigid motion in the 6-dimensional configuration space. Moreover, we utilize our algorithm for complete motion planning of polygonal robots undergoing translational and rotational motion in a plane. In particular, we use generalized PD computation for checking path non-existence.

AB - Penetration depth (PD) is a distance metric that is used to describe the extent of overlap between two intersecting objects. Most of the prior work in PD computation has been restricted to translational PD, which is defined as the minimal translational motion that one of the overlapping objects must undergo in order to make the two objects disjoint. In this paper, we extend the notion of PD to take into account both translational and rotational motion to separate the intersecting objects, namely generalized PD. When an object undergoes rigid transformation, some point on the object traces the longest trajectory. The generalized PD between two overlapping objects is defined as the minimum of the longest trajectories of one object under all possible rigid transformations to separate the overlapping objects. We present three new results to compute generalized PD between polyhedral models. First, we show that for two overlapping convex polytopes, the generalized PD is same as the translational PD. Second, when the complement of one of the objects is convex, we pose the generalized PD computation as a variant of the convex containment problem and compute an upper bound using optimization techniques. Finally, when both the objects are non-convex, we treat them as a combination of the above two cases, and present an algorithm that computes a lower and an upper bound on generalized PD. We highlight the performance of our algorithms on different models that undergo rigid motion in the 6-dimensional configuration space. Moreover, we utilize our algorithm for complete motion planning of polygonal robots undergoing translational and rotational motion in a plane. In particular, we use generalized PD computation for checking path non-existence.

KW - Penetration depth

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

U2 - 10.1145/1128888.1128914

DO - 10.1145/1128888.1128914

M3 - Conference contribution

AN - SCOPUS:33745965450

SN - 1595933581

SN - 9781595933584

T3 - Proceedings SPM 2006 - ACM Symposium on Solid and Physical Modeling

SP - 173

EP - 184

BT - Proceedings SPM 2006 - ACM Symposium on Solid and Physical Modeling

PB - Association for Computing Machinery (ACM)

Y2 - 6 June 2005 through 8 June 2005

ER -