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.

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

MARIS, Bogdan Mihai;BOTTURI, Debora;FIORINI, Paolo
2011-01-01

Abstract

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.
2011
9780889868656
Collision detection; Algorithms and techniques; Convex polyhedra; Proximity queries
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/413543
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact