Detecting the intersection of two convex shapes by searching on the 2-sphere. (September 2017)

• Record Type: Journal Article
• Authors: Hornus, Samuel
• Is Part Of: Computer aided design. Volume 90(2017)
• Page Start: 71
• Page End: 83
• Publication Date: 2017-09
• Subjects: Intersection detection -- GJK -- Numerical robustness -- Collision detection -- Minkowski sum -- Gauss map; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2017.05.009
• Languages: English
• ISSNs: 0010-4485

Abstract

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. Highlights: An algorithm similar in spirit to GJK for detecting when 2 shapes touch each other. Numerically more robust and a little faster. Graphical abstract: