Detecting the intersection of two convex shapes by searching on the 2-sphere - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Computer-Aided Design Année : 2017

Detecting the intersection of two convex shapes by searching on the 2-sphere

Samuel Hornus

Résumé

We take a look at the problem of deciding whether two convex shapes intersect or not. We do so through the well known lens of Minkowski sums and with a bias towards applications in computer graphics and robotics. We describe a new technique that works explicitly on the unit sphere, interpreted as the sphere of directions. In extensive benchmarks against various well-known techniques, ours is found to be slightly more efficient, much more robust and comparatively easy to implement. In particular, our technique is compared favourably to the ubiquitous algorithm of Gilbert, Johnson and Keerthi (GJK), and its decision variant by Gilbert and Foo. We provide an in-depth geometrical understanding of the differences between GJK and our technique and conclude that our technique is probably a good drop-in replacement when one is not interested in the actual distance between two non-intersecting shapes.
Fichier principal
Vignette du fichier
inter-spm.pdf (641.15 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01522903 , version 1 (15-05-2017)

Identifiants

Citer

Samuel Hornus. Detecting the intersection of two convex shapes by searching on the 2-sphere. Computer-Aided Design, 2017, ⟨10.1016/j.cad.2017.05.009⟩. ⟨hal-01522903⟩
311 Consultations
2050 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More