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

Samuel Hornus 1
1 ALICE - Geometry and Lighting
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Article dans une revue
Computer-Aided Design, Elsevier, 2017, 〈10.1016/j.cad.2017.05.009〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Samuel Hornus <>
Soumis le : lundi 15 mai 2017 - 17:00:04
Dernière modification le : jeudi 11 janvier 2018 - 06:20:18
Document(s) archivé(s) le : jeudi 17 août 2017 - 00:47:11


Fichiers produits par l'(les) auteur(s)




Samuel Hornus. Detecting the intersection of two convex shapes by searching on the 2-sphere. Computer-Aided Design, Elsevier, 2017, 〈10.1016/j.cad.2017.05.009〉. 〈hal-01522903〉



Consultations de la notice


Téléchargements de fichiers