We present a new measure for computing continuous penetration depth between two intersecting rigid objects. We generate a set of samples in the configuration space, precompute an approximation of the contact space for two intersecting objects using binary classification techniques, and construct a bijective mapping between the spherical space and the precomputed contact space. For a given in-collision configuration, we search the spherical space for the nearest neighbor and find the corresponding image in the contact space based on the predefined spherical parameterization. The resulting image is a witness equivalent to the nearest configuration and is used to formulate the penetration depth direction based on our measure. Unlike prior algorithms, our algorithm guarantees that both the penetration depth magnitude and direction are continuous with respect to the motion parameters. Our algorithm is approximate in a sense that we approximate the exact contact space, and we have applied our algorithm to complex rigid models composed of tens or hundreds of thousands of triangles and the runtime query takes only around 0.01 milliseconds.

Keywords—Penetration Depth, Discontinuity, Spherical Parameterization


SIAM Conference on Geometric and Physics Modeling, November 11-14, 2013, Denver Colorado, USA

(Journal of Computer-Aided Design) [paper] [bibtex]

Related Work