Paper Info
Title
Detecting the intersection of two convex shapes by searching on the 2-sphere.
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 favorably 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.
Year
DOI
Venue
2017
10.1016/j.cad.2017.05.009
Computer-Aided Design
Keywords
Field
DocType
Intersection detection,GJK,Numerical robustness,Collision detection,Minkowski sum,Gauss map
Gilbert–Johnson–Keerthi distance algorithm,Mathematical optimization,Collision detection,Minkowski space,Regular polygon,Computer graphics,Gauss map,Minkowski addition,Mathematics,Unit sphere
Journal
Volume
ISSN
Citations 
90
0010-4485
0
PageRank 
References 
Authors
0.34
11
1
Name
Order
Citations
PageRank
Samuel Hornus116612.52