Publication
Exact Distance Computation for Deformable Objects
M. Gissler; Udo Frese; M. Teschner
In: Proceedings of the Computer Animation and Social Agents 2008 Conference. Annual Conference on Computer Animation and Social Agents (CASA-2008), September 1-3, Seoul, Korea, Republic of, 2008.
Abstract
We present a novel approach for the computation
of the minimum distance between
arbitrarily shaped, triangulated objects. The
approach proceeds in two stages. In the first
stage, the Gilbert-Johnson-Keerthi algorithm
(GJK) is performed. We show how to employ
characteristics of the algorithm to efficiently
compute lower and upper bounds of the minimum
distance between non-convex objects. We
further show how to use these bounds to set up
a spatial subdivision scheme that computes the
exact minimum distance in the second stage of
the algorithm. The knowledge of a lower and
an upper bound allows for a twofold culling
in the second stage. First, only a small part
of the simulation domain is considered in the
spatial subdivision. Thus, large object parts
are culled. Second, the intrinsic properties of
the spatial subdivision scheme are employed
to further accelerate the computation of the
minimum distance for the remaining object
parts. The proposed algorithm does not rely
on precomputed data structures. Therefore,
it is particularly appropriate for deformable
objects. Experiments indicate the efficiency of
the approach compared to existing algorithms.