Skip to Main content Skip to Navigation
Journal articles

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

Samuel Hornus 1 
1 ALICE - Geometry and Lighting
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Samuel Hornus Connect in order to contact the contributor
Submitted on : Monday, May 15, 2017 - 5:00:04 PM
Last modification on : Friday, July 8, 2022 - 10:06:56 AM
Long-term archiving on: : Thursday, August 17, 2017 - 12:47:11 AM


Files produced by the author(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⟩



Record views


Files downloads