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 Access content directly
Journal Articles Computer-Aided Design Year : 2017

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

Samuel Hornus

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.
Fichier principal
Vignette du fichier
inter-spm.pdf (641.15 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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 View
2071 Download

Altmetric

Share

Gmail Facebook X LinkedIn More