{'fraction_non_alphanumeric': 0.018930041152263374, 'fraction_numerical': 0.0, 'mean_word_length': 5.110552763819095, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exact distance computation for deformable objects

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.