Adaptive surface decomposition for the distance computation of arbitrarily shaped objects

摘要

We propose an adaptive decomposition algorithm to compute separation distances between arbitrarily shaped objects. Using the Gilbert-Johnson-Keerthi algorithm (GJK), we search for sub-mesh pairs whose convex hulls do not intersect. We show how to employ characteristics of GJK to guide a recursive decomposition of the objects in the case of intersections. We further show how to employ GJK to derive lower and upper distance bounds in non-intersecting cases. The bounds are used in a spatial subdivision scheme to enforce a twofold culling of the domain. Experiments show the applicability of the algorithm in dynamic scenarios with dynamically moving rigid and deformable objects.