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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01522903
Contributor : Samuel Hornus <>
Submitted on : Monday, May 15, 2017 - 5:00:04 PM
Last modification on : Thursday, January 11, 2018 - 6:20:18 AM
Document(s) archivé(s) le : Thursday, August 17, 2017 - 12:47:11 AM

File

inter-spm.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

322

Files downloads

441