Soutenance mémoire
La visibilité en tant que preuve
Dans cette section, sont définis différents termes et notions inhérents à notre contexte. Nous nous plaçons dans le cadre de scènes composées de polygones convexes. Les objets auxquels nous faisons référence sont des points, des segments, des polygones convexes, ou des polyèdres convexes. D’une manière générale, un problème de visibilité est souvent ramené à la question : “Est-ce que c’est visible ?”. Si l’on considère uniquement deux objets, l’ensemble de leur visibilité s’assimile à l’ensemble des droites qui les intersectent. Dans notre contexte, on parle alors souvent de droites poignardantes (stabbing lines). La définition 1 précise cette notion.
Définition 1 Relativement à un ensemble d’objets {Ai, 1 ≤ i ≤ n}, une droite est dite poignardante si elle intersecte tous les objets de cet ensemble (en incluant les cas de tangence). On notera stab(A1, …, An) l’ensemble des droites poignardant tous les Ai. Plus généralement, la visibilité de deux objets se pose relativement à un ensemble d’obstacles que nous désignerons par bloqueurs. Dans notre contexte, un bloqueur satisfait à la définition suivante :
Définition 2 Un objet O est un bloqueur pour deux objets A et B s’il possède une intersection non vide avec l’enveloppe convexe de A et de B. Trouver une visibilité entre deux objets revient à déterminer une droite qui les intersecte, sans intersecter un seul de leurs bloqueurs. On parle souvent de droite poignardant (stabbing line) ces objets. Sur la base de ces définitions, la preuve de la visibilité mutuelle de deux objets s’interprête géométriquement comme suit :
Définition 3 Etant donnés deux objets A et B ainsi que l’ensemble de leurs bloqueurs {Oi, 1 ≤ i ≤ n}, A et B sont visibles si, et seulement si, il existe au moins une droite l ∈ stab(A, B) telle que l ∈/ Sn i=1 stab(Oi). Toute droite satisfaisant à la définition 3 est la preuve que deux objets sont visibles. La figure 1.1 donne deux exemples. La majeure partie des travaux existants ont pour objet de prouver l’existence ou l’absence de visibilité. Cette information binaire est suffisante pour répondre à des problématiques, aujourd’hui classiques. Par exemple, quel est le premier objet rencontré par un rayon ? Quels sont les objets visibles depuis un point de vue ? Le classique lancer de rayons est à la base des solutions pratiques à ces problèmes, et à tous ceux qui s’y ramènent. Populaire et robuste, cette approche ne permet cependant pas de mieux comprendre les phénomènes visuels. Une simple information binaire de visibilité revient à explorer un monde obscur avec un pointeur laser. L’image souvent reprise est celle de l’étude de la visibilité en tant que fonction ou équation. La visibilité selon un rayon procure un ensemble de points satisfaisant à la fonction de visibilité. Mais elle ne procure pas d’information globale sur la fonction en elle-même. La seule preuve de la visibilité est insuffisante pour approfondir la compréhension globale du phénomène. Or, cette compréhension est nécessaire pour appréhender des questions plus complexes.
Positionnement
En matière de visibilité, la littérature est des plus vastes. Nous résumons dans cette section les différents critères qui ont pu être proposés pour différencier les problématiques, et permettre leur positionnement dans la littérature. Enfin nous nous appuyons sur ces critères pour situer les travaux présentés dans ce mémoire. Durand [Dur99] propose un état de l’art multidisciplinaire où les problèmes de visibilité abordés sont classés en fonction de l’espace dans lequel ils sont résolus. Il distingue :
• L’espace image, qui regroupe toutes les méthodes opérant dans un plan projectif 2D. C’est le cas par exemple des approches qui exploitent la carte graphique d’un ordinateur.
• L’espace objet, autrement dit l’environnement 2D ou 3D considéré. En l’occurrence, le classique lancer de rayons entre dans cette catégorie, étant basé sur la recherche de la première intersection rayon/objet.
• L’espace des points de vue, c’est-à-dire l’ensemble de tous les points d’observations possibles dans un environnement donné. Il peut s’agir d’approches liées à la vision par ordinateur, mais cela concerne également les applications type “promenade dans un environnement virtuel”.
• L’espace de droites, qui comprend l’ensemble des méthodes analytiques utilisant une paramétrisation des droites. Les travaux en visibilité globale entrent dans cette catégorie. Nirenstein [NBG02] distingue les différentes méthodes en fonction de la précision avec laquelle elles résolvent un problème de visibilité :
• Les méthodes agressives, qui sous-estiment l’ensemble des visibilités à calculer. Autrement dit, des objets visibles peuvent être manquant, mais il n’existe pas de fausse visibilité.
• Les méthodes conservatrices, qui surestiment l’ensemble des visibilités à calculer. Certaines visibilités rapportées peuvent ne pas exister, mais il est certain que toutes les visibilités existantes sont trouvées.
• Les méthodes exactes, qui trouvent tous les objets visibles, ni plus, ni moins. La capacité d’une méthode agressive ou conservatrice à tendre vers la solution exacte détermine son efficacité. Il est aussi parfois question de méthode approximative lorsque l’approche suivie ne permet pas de garantir un comportement conservatif ou agressif. Ces critères s’appliquent davantage à des applications dont l’objet est de prouver la visibilité. Ils sont souvent utilisés dans un contexte de calcul de PVS (Potentially Visible Set), i.e. de calcul des objets visibles depuis une région de l’espace de vue. Concernant la visibilité globale, un comportement conservatif ou agressif n’a pas de sens
Arrangement d’hyperplans
La résolution du problème présenté au paragraphe 1.2 est soumis à une complexité théorique temps et mémoire en O(n^4 log n) où n est le nombre de bloqueurs considérés. Ce résultat est lié aux classes d’isotopie induites par un ensemble de droites. Le problème se décrit usuellement comme suit [Pel93] : on considère un ensemble de droites bleues et deux droites rouges. Ces dernières appartiennent à la même classe d’isotopie si la première peut être déplacée et confondue avec la seconde sans jamais croiser ou devenir parallèle à une droite bleue. Dans l’espace de Plücker, les hyperplans associés aux droites bleues forment un arrangement dont les cellules (de dimension 5) correspondent aux classes d’isotopie. Plus exactement, il s’agit des cellules qui intersectent la quadrique de Plücker. D’une manière générale, un arrangement de n hyperplans dans R d induit un nombre maximum de cellules O(n d ) [EOS86]. Restreint à la zone d’une surface algébrique de dimension (d − 1) (i.e. les cellules qui intersectent cette surface), le nombre maximum de cellules devient O(n d−1 log n) [APS93]. D’où une complexité en O(n^4 log n) pour les classes d’isotopie induites par un ensemble de droites réelles dans l’espace de Plücker. Si les droites considérées sont supports des arêtes d’un ensemble de polygones convexes et orientés, les droites intersectant un même sous-ensemble de ces polygones appartiennent à la même classe d’isotopie. La visibilité depuis un polygone a pour complexité O(n^4 log n) puisque le complexe de polytopes calculé est, dans le pire des cas, l’arrangement d’hyperplans associés aux arêtes des bloqueurs dans la zone de la quadrique de Plücker. On peut noter que Pellegrini propose une complexité équivalente en O(n 4+ ) [Pel90, Pel91] Le problème des classes d’isotopie est connexe à d’autres problématiques liées aux droites dans R^3. Par exemple, étant supposé construit un arrangement d’hyperplans dans l’espace de Plücker, Pellegrini montre que l’on peut répondre au problème du lancer de rayons en O(log n) [Pel93]. Un tour d’horizon plus complet de ces problématiques peut être trouvé dans [Pel97].
|
Table des matières
Introduction
1 Introduction à la visibilité
1.1 Définitions et classification
1.1.1 La visibilité en tant que preuve
1.1.2 L’étude globale de la visibilité
1.1.3 Positionnement
1.2 Prérequis mathématiques
1.2.1 Géométrie projective
1.2.2 Paramétrisation de Plücker
1.2.3 Polyèdres et polytopes
1.3 Visibilité et espace de Plücker
1.3.1 Visibilité à travers une séquence de polygones
1.3.2 Prise en compte de l’occultation
1.3.3 Événements visuels étendus
1.4 Précédents travaux
1.4.1 Arrangement d’hyperplans
1.4.2 Le graphe d’aspect
1.4.3 L’Asp
1.4.4 Portails et antipénombre
1.4.5 Le complexe de visibilité 2D
1.4.6 Le complexe de visibilité 3D
1.4.7 Le squelette de visibilité
1.4.8 Arbre PSP
1.4.9 Cellule de vue exacte
1.4.10 Arbre d’occultation
1.4.11 Preuve de visibilité
1.5 Conclusion
2 Visibilité polygone à polygone
2.1 Problématique
2.1.1 Objectifs
2.1.2 Effet de fragmentation
2.2 Approche proposée
2.2.1 Test d’intersection renforcé
2.2.2 Arbre VBSP
2.2.3 Valider et rentabiliser
2.3 Implantation et évaluation
2.3.1 Éléments d’implantation
2.3.2 Évaluation de la méthode
2.3.3 Discussion
2.4 Conclusion
3 Ombres douces en synthèse d’images
3.1 Calcul d’ombres douces
3.1.1 Subdivision de surfaces
3.1.2 Volumes d’ombre
3.1.3 Approches stochastiques
3.1.4 Faisceaux de rayons
3.1.5 Volumes d’ombre et de pénombre
3.1.6 Silhouette étendue et volume d’ombre douce
3.1.7 Maillage de discontinuités et événements visuels
3.2 Approche proposée
3.2.1 Vue d’ensemble
3.2.2 Visibilité point-polygone
3.2.3 Résultats
3.3 Discussion et perspectives
3.3.1 Extensions et optimisations
3.3.2 Limitations actuelles
3.3.3 Perspectives
4 Prédiction sans perte de la propagation des ondes électromagnétiques
4.1 Préambule
4.1.1 Les enjeux
4.1.2 Caractéristiques du canal de propagation
4.1.3 Les modèles basés rayons
4.2 Approche proposée
4.2.1 Requête de visibilité unifiée
4.2.2 Graphe de visibilité : calcul hiérarchique mixte
4.2.3 Résultats
4.3 Conclusions
4.3.1 Discussion
4.3.2 Perspectives
Conclusion
Bibliographie
Télécharger le rapport complet
