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 metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01157239
Contributor : Samuel Hornus <>
Submitted on : Friday, June 12, 2015 - 2:18:04 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:25 PM

Licence


Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License

Identifiers

  • HAL Id : hal-01157239, version 2

Citation

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⟩

Share

Metrics

Record views

523

Files downloads

615