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
Résumé : 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.
Type de document :
Rapport
[Research Report] RR-8730, Inria Nancy - Grand Est (Villers-lès-Nancy, France); INRIA. 2015, pp.39
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01157239
Contributeur : Samuel Hornus <>
Soumis le : vendredi 12 juin 2015 - 14:18:04
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23

Licence


Distributed under a Creative Commons Paternité - Partage selon les Conditions Initiales 4.0 International License

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

434

Téléchargements de fichiers

375