Skip to Main content Skip to Navigation

Intersection detection via Gauss maps; a review and new techniques

Samuel Hornus 1 
1 ALICE - Geometry and Lighting
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : This paper delves into the problem of detecting the intersection of two convex polyhedra. It does so through the lens of Minkowski sums and Gauss maps, and with a bias towards applications in computer graphics and robotics. In the first part, we show how Minkowski sums and Gauss maps come into play, give a brief survey of techniques for pairs of simple shapes and describe a low-level optimization of a naive algorithm for convex polyhedra, which is applied to tetrahedra. Novel applications to the ray casting problem are also given. In the second part, we take a more abstract approach to the problem and describe a new and very efficient and robust algorithm for detecting the intersection of two convex shapes. The new technique works directly on the unit sphere, interpreted as the sphere of directions. In particular, it is compared favourably to the ubiquitous algorithm of Gilbert, Johnson and Keerthi.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Samuel Hornus Connect in order to contact the contributor
Submitted on : Friday, June 12, 2015 - 2:18:04 PM
Last modification on : Wednesday, February 2, 2022 - 5:00:57 PM


Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License


  • HAL Id : hal-01157239, version 2


Samuel Hornus. Intersection detection via Gauss maps; a review and new techniques. [Research Report] RR-8730, Inria Nancy - Grand Est (Villers-lès-Nancy, France); INRIA. 2015, pp.39. ⟨hal-01157239v2⟩



Record views


Files downloads