A Geometric Approach to Improve Performance of a Collision Detection Algorithm Derived from GJK and LC Algorithms

We present a fast algorithm for collision detection and for distance computation between two convex objects in 3D. The algorithm is an optimization of Gilbert, Johnson and Keerthi algorithm (GJK) and uses a geometrical approach through the Voronoi regions to detect the closest features, as described in Lin and Canny algorithm (LC). The main contributions of this work are the simplification of each iteration of the GJK algorithm by substituting the computation of the closest point with the identification of the closest feature to the origin and a clear geometric representation and implementation of every iteration. By using the Voronoi regions, together with the above simplification of the calculus, we increase the robustness of the algorithm and we give a deeper understanding of the inner steps.The paper presents a complete description of the proposed procedure showing the approach quality.