Intersection detection via Gauss maps; a review and new techniques - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2015

Intersection detection via Gauss maps; a review and new techniques

Détection d’intersection via l’application de Gauss; revue et nouvelles techniques

Samuel Hornus

Résumé

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.
Cet article discute du problème (décisionnel) de la détection de l'intersection de deux polyèdres convexes. Il porte particulièrement sur les applications de ce problème en informatique graphique et en robotique. La discussion s'y fait du point de vue des sommes de Minkoswki et de l'application de Gauss. Dans la première partie, nous rappellons le rôle de ce point de vue dans la compréhension de la géométrie du problème. Nous donnons un bref aperçu des techniques conçues pour certaines paires de formes simples, et nous proposons un algorithme naïf mais optimisé, traitant des polyèdres convexes quelconques. Nous traitons en exemple une application aux paires de tétraèdres et une application au problème du lancer de rayons. En deuxième partie, nous approchons le problème de manière plus abstraite et décrivons un nouvel algorithme robuste et rapide pour la détection de l'intersection de deux objets convexes (non nécessairement polyédrique). Ce nouvel algorithme travaille directement sur la sphère unité que nous interprétons comme l'espace des directions. En particulier, notre nouvelle technique est comparée favorablement à celle, fort répandue, de Gilbert, Johnson et Keerthi.
Fichier principal
Vignette du fichier
RR-8730.pdf (1.27 Mo) Télécharger le fichier
RR-8730-code.zip (37.83 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01157239 , version 1 (03-06-2015)
hal-01157239 , version 2 (12-06-2015)

Licence

Paternité - Partage selon les Conditions Initiales

Identifiants

  • HAL Id : hal-01157239 , version 2

Citer

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⟩
306 Consultations
2343 Téléchargements

Partager

Gmail Facebook X LinkedIn More