Introduction, présentation des résultats
et de leur contexte

La synthèse d'images réalistes comporte deux aspects relativement (bien que non totalement) disjoints :

1) le développement d'un modèle sous-jacent aux objets que l'on désire représenter,

2) le développement de techniques permettant de réaliser le "rendu" de la scène ainsi modélisée.

Une bonne introduction à ces deux domaines peut être trouvée dans [FV90].

Dans cette thèse nous nous intéresserons à ces deux aspects dans le cadre exclusif de la synthèse d'images de paysages, à partir de la modélisation de végétaux et de reliefs montagneux.

 La troisième partie, chapitre 7 à 9, aborde enfin les problèmes liés au rendu réaliste des scènes modélisées (cf [JA89], [AJ90b], [AJ90c], Planches 12, 16 à 21).

0.1 Contexte de ce travail dans le cadre de la synthèse d'images de paysages

Il sera présenté en détail dans le chapitre 1. Nous décrivons ici dans une brève revue bibliographique, comment les résultats présentés aux chapitres 3, 4, 6, 7 et 8 se situent dans le domaine de la synthèse d'images (voir [AJ90c] dans son entier pour une revue des images présentées ces 10 dernières années à IMAGINA)..

0.1.1 Première partie : synthèse d'images de végétaux

Celle-ci a fait l'objet d'un grand nombre d'études ces dernières années: Kawaguchi [Ka82], Reeves, Blau [RB85], Gardner [Ga84], Aono, Kunii [AK84], Smith [Sm84], Bloomenthal [Bl85], Niklas, [Ni86], Demko, Hodges, Naylor [DH85], Oppenheimer [Op86], Prusinkiewicz [Pr86], Prusinkiewicz, Lindenmayer et Hanan [PL88], De Reffye, Edelin, Françon, Jaeger, Puech [RE88], Viennot, Eyrolles, Janey, Arquès [VE89] [AJ90] [AJ91a], Greene [Gr89].

Dans ces travaux, la génération d'un végétal est principalement opérée à deux niveaux. Dans un premier temps, est généré l'arbre topologique (combinatoire) sous-jacent à l'arbre réel. Généralement cet arbre est binaire ou ternaire. Le second niveau consiste en la génération de l'arbre géométrique associé. Toutes ces méthodes appliquent des modèles géométriques plus ou moins sophistiqués à l'arbre topologique. La géométrie minimale consiste en une modélisation en deux dimensions, avec l'épaisseur et la longueur choisies pour chaque arête et un angle à droite et à gauche pour chaque nœud d'embranchement. Une géométrie plus sophistiquée doit être utilisée pour une visualisation en trois dimensions à laquelle pourront être ajoutés des éléments végétaux (feuilles, fleurs), une texture sur le tronc et les branches et des contraintes extérieures telles que le vent, la lumière ou la gravité,… .

Dans tous ces travaux, les aspects topologiques et géométriques sont plus ou moins liés. Ces méthodes peuvent être classées comme suit :

- Les méthodes géométriques : La topologie est ici secondaire et la géométrie acquiert dès lors une grande importance pour obtenir une grande diversité de formes Kawaguchi [Ka82], Aono et Kunii [AK84], Honda [Hon71] et Bloomenthal [Bl85].

- Les méthodes axées sur la visualisation : La technique des systèmes de particules Reeves et Blau [RB85], les techniques fractales de Mandelbrot, Oppenheimer [Op86], les systèmes de fonctions itérées de Barnsley, Jacquin, Malassenet, Reuter, Sloan [BJ88], Demko, Hodges et Naylor [DH85].

- Les méthodes environnementales s'intéressent à l'importance de l'environnement dans le développement d'une plante. Citons le modèle de croissance stochastique et récursive de Niklas [Ni86] ou le modèle de développement de lierre sur une surface par croissance stochastique guidée par un automate sur un espace de voxels, tenant compte de contraintes d'intersection ou d'illumination, Greene [Gr89].

- Les méthodes topologiques qui mettent l'accent sur le développement de l'arbre topologique sous-jacent à l'arbre réel. Dans ce cadre, on peut distinguer :

° L'approche botanique : le modèle topologique est directement issu de l'étude botanique de l'arbre que l'on désire modéliser. Les principaux travaux dans ce domaine sont ceux de De Reffye, Edelin, Françon, Jaeger, Puech [RE88].

° L'approche L-systèmes : La technique de génération par règles de réécritures utilisant la théorie des L-systèmes développée par Lindenmayer, Smith [Sm84], Prusinkiewicz [Pr86], Prusinkiewicz, Lindenmayer, Hanan [PL88], permet de modéliser le développement d'arbustes ou de cellules par codage (mot ou graphe).

° L'approche combinatoire que nous avons développée dans Viennot, Eyrolles, Janey, Arquès [VE89a], [VE89b]. L'introduction du concept de matrice de ramification permet de séparer la forme de l'arbre de son histoire, beaucoup d'aspects visuels (aspect touffu, effilé, bien équilibré) étant présents dans la matrice. Cette matrice dépend uniquement de l'arbre topologique sous-jacent et est définie à partir des notions combinatoires d'ordre et de biordre d'un noeud (Horton [Ho45], Strahler [St52]). La forme de l'arbre est directement contrôlée par la matrice de ramification, mais n'est en revanche pas issue d'un processus de croissance au sens botanique. L'utilisation de l'analyse d'Horton-Strahler pour la synthèse d'images d'arbres a été auparavant suggérée mais non développée dans [EF86], article dans lequel la croissance des ramifications est déterminée par une extension de la "méthode de Rémy" utilisant un jeu de probabilités (Deux cas extrêmes y sont présentés conduisant à la génération des arbres binaires aléatoires et des arbres binaires croissants aléatoires).

La classification des modélisations de végétaux que nous présenterons au chapitre 1 "Etat de l'art en synthèse d'images de paysages naturels", est ainsi fonction de la caractéristique principale de chaque modèle. Elle distinguera les grandes catégories suivantes:

- les pionniers,

- les modélisations issues de la géométrie classique,

- les modélisations fractales de paysages,

- les modèles combinatoires,

- les modèles à base de réécriture,

- les modèles botaniques,

- les modèles environnementaux.

Ces travaux sont ensuite présentés selon une classification transversale en fonction des trois aspects :Topologie, Géométrie et Rendu.

0.1.2 Deuxième partie : synthèse d'images de terrains et reliefs montagneux

Les domaines d'application de la synthèse d'images de reliefs sont nombreux (simulateurs de vols, animation, images de synthèse, CADCAM, ...) et imposent deux objectifs opposés : le réalisme et l'efficacité. Peu de modèles concilient aujourd'hui ces deux contraintes : ceux utilisés dans les applications "temps réel" (comme les simulateurs de vol) sacrifient le réalisme à l'efficacité, en revanche les modèles les plus réalistes peuvent demander un temps important pour calculer une unique scène.

Les techniques développées en modélisation de terrain peuvent être classées en trois catégories :

- La première catégorie, parfois qualifiée de procédurale, consiste à plaquer une texture sur des primitives simples classiques comme proposé par Dungan, Stenser, Sutty [DS78], par Kaneda, Kato, Nakamae, Nishita, Tanaka, Noguchi, [KK89] qui utilisent des textures hiérarchisées pour tenir compte de la distance à l'observateur, par Marshall, Wilson, et Carlson [MW80] qui utilisent une base de donnée de primitives linéaires et par Gardner [Ga84] dont les surfaces primitives sont des quadriques. Ces techniques, historiquement parmi les premières, conduisent à des reliefs aux lignes douces et ont souvent l'inconvénient de présenter des discontinuités dans le gradient de la texture aux intersections des surfaces.

- La seconde catégorie très souvent considérée comme la plus efficace pour la création d'images réalistes (Voss [Vo83], Cook, Carpenter, Porter, Reeves, Salesin, Smith [CC83]) est celle des techniques fractales (Mandelbrot [Ma82]). Elle est présentée sous ses différents aspects dans Barnsley, Devaney, Mandelbrot, Peitgen, Saupe, Voss [BD88] et a fait l'objet de très nombreux travaux pour l'implantation efficace des fractals stochastiques (par opposition aux fractals déterministes : courbe de Koch, cf [Fo87]), implantations qui sont essentiellement des approximations du mouvement Brownien fractionnaire : Fournier, Fussel, Carpenter [FF82], Miller [Mi86], Smith [Sm84] (qui présente les techniques de subdivision récursive de [FF82] en termes de grammaires et de règles de réécriture).

Les qualités des techniques fractales s'expriment en termes de réalisme remarquable, de très importante amplification des données et du niveau de détail. Certains inconvénients (comme l'effet de plissement, "creasing effect", lié à l'indépendance du contexte des grammaires précitées) ont été exprimés, entre autres, par Mandelbrot dans [BD88] (Annexe A) :

"The most basic defect of past fractal forgeries of landscape is that every one of them fails to include river networks. This is one reason why these forgeries look best when viewed from a low angle above the horizon, and are worst when examined from the zenith. This is also why achieving a fully random combined model of rivers and of mountains will be a major advance for computer graphics (and also perhaps for the science of geomorphology)."

Une autre façon d'exprimer ce problème est de constater que dans les images fractales de montagnes, vallées et montagnes sont symétriques, ceci étant dû à la symétrie de la loi gaussienne utilisée, alors que dans la réalité la montagne et son fleuve présentent une totale dissymétrie due à l'érosion. Mandelbrot ébauche à ce problème un type de solution (cf [BD88]) qui consiste dans un premier temps, à construire récursivement, simultanément deux fractals déterministes représentant le réseau fluvial et le réseau des lignes de partage des eaux, puis dans un deuxième temps, à relever le relief le long des lignes de partage des eaux, par une technique de subdivision récursive modifiée pour tenir compte des problèmes d'itude (maxima pour les sources, diminution de l'itude le long des fleuves, ...).

- Cette démarche qui consiste à modéliser un relief à partir d'un modèle d'érosion caractérise la troisième catégorie de techniques de modélisation de terrain. Outre la solution sus-mentionnée de Mandelbrot, les travaux de Kelley, Malin, Nielson [KM88], sont caractéristiques de cette approche. Dans cet article, la description du bassin fluvial (fleuve et bassin de drainage) est fondée sur des modèles empiriques d'érosion utilisés en géomorphologie (cf [Ab80], [How71], [Sh66]). Le maillage polygonal ainsi obtenu est alors interpolé par une surface analogue à une surface spline sous tension. Cette méthode matérialise un modèle de génération statique, c'est à dire qu'il n'y a pas simulation de l'érosion par déplacement de matière, mais génération d'un relief à partir des conséquences d'un phénomène d'érosion présentées sous forme de lois topologiques et géométriques. Les modèles dynamiques de génération de reliefs de Roudier [Ro91] et Musgrave, Kolb et Mace [KMK89] modélisent en revanche l'évolution d'un relief au moyen de processus mettant en œuvre des déplacements de matière.

C'est dans cette troisième catégorie (modèle statique d'érosion) que se situe le modèle de bassin fluvial que nous avons développé. L'idée de base de ce modèle est de générer un bassin montagneux à partir de la modélisation planaire de son bassin fluvial. Ce bassin fluvial est ainsi considéré comme un arbre binaire planaire, le terrain étant alors considéré comme une carte planaire admettant cet arbre binaire comme arbre recouvrant. La modélisation finale du bassin montagneux consiste alors à remonter les points de cette carte planaire, en tenant compte de paramètres issus de l'analyse des bassins fluviaux.

La classification des modélisations de terrains et bassins montagneux que nous présenterons au chapitre 1 distinguera ainsi les grandes catégories suivantes:

- les techniques à base de plaquage de texture,

- les méthodes fractales,

- les techniques basées sur un modèle d'érosion.

0.2 Contexte de ce travail dans le cadre du dessin automatique d'arbres et de cartes planaires

Si l'on modélise un terrain, un relief en projection sur le plan de l'horizontale par une carte planaire, si l'on modélise un réseau fluvial en projection dans le plan de l'horizontale par un arbre binaire, on constate que la modélisation d'un relief montagneux et de son réseau fluvial sous-jacent est directement liée au plongement automatique dans le plan d'un arbre binaire et d'une carte planaire recouverte (au moins partiellement) par cet arbre binaire. Par ailleurs les algorithmes et structures de données sous-jacent au dessin d'arbres planaires sont identiques à ceux du dessin de végétaux, même si les contraintes graphiques sont fort différentes. Aussi les chapitres 2 et 5, premiers chapitres des parties 1 et 2, étudient respectivement les deux domaines du dessin par plongement automatique dans le plan des arbres binaires d'une part et des cartes planaires d'autre part. La présentation choisie, sans prétendre à l'exhaustivité, a pour but de décrire certains des principaux algorithmes de plongement (ceux de Wetherell, Shannon [WS79], Reingold, Tilford [RT81], pour les arbres et de Laumond [La84], Chiba, Onoguchi, Nishizeki [CO85] pour les cartes) dans une approche graduelle, partant des algorithmes les plus simples satisfaisant peu de contraintes, en allant vers les plus sophistiquées satisfaisant des contraintes graphiques complexes, et ceci en parallèle pour les arbres au chapitre 2 et pour les cartes au chapitre 5. L'étude comparée de ces deux démarches algorithmiques, relativement achevée dans le cas des arbres et encore inachevée dans le cadre plus complexe des cartes, est très intéressante et conduit à de nouvelles idées pour le développement d'un algorithme de plongement automatique dans le plan de cartes planaires (fin du chapitre 5). Par ailleurs un nouvel algorithme de plongement automatique d'une carte planaire munie d'un arbre binaire partiellement recouvrant, algorithme préliminaire à la modélisation de bassins fluviaux montagneux, est présentée au chapitre 6.

Plus précisément :

Le chapitre 2 présente les définitions de base sur les cartes planaires et arbres planaires qui serviront dans la suite de la thèse. Il détaille les liens entre les notions de cartes planaires topologiques et cartes planaires combinatoires et décrit les structures de données qui ont servi à l'implantation des algorithmes décrits dans la suite de la thèse. Dans une seconde partie, ce chapitre s'intéresse au dessin d'arborescences planaires (essentiellement binaires) et décrit quelques algorithmes caractéristiques de ce domaine (cf [WS79], [RT81]). Les contraintes qui président au dessin d'arborescences planaires (contraintes esthétiques : centrage d'un père par rapport à ses deux fils, nœuds de même niveau situés sur une même horizontale, respect des symétries, sous-arbres identiques représentés de façon identique, …; contraintes de planarité …) sont fort différentes de celles que l'on rencontre dans la synthèse d'image de végétaux, même si les objets de base sont les mêmes : des arbres binaires. En effet dans le cas de la synthèse de végétaux, le dessin se fait dans R3. Ainsi la contrainte de planarité qui est essentielle et complexe à rendre dans le cas du dessin d'arborescences planaires n'existe plus. Au contraire, dans le cas de végétaux, les contraintes sont de nature "rendu" (modélisation 3D, modélisation d'embranchements, modèles d'illumination, … cf partie 3). Malgré cette importante différence, les algorithmes de dessin de ces deux catégories d'arborescences planaires sont fondés sur les mêmes algorithmes de parcours prioritairement en profondeur de la structure arbre binaire sous-jacente.

Le fait qu'un réseau fluvial n'est autre, si on le projette sur le plan de "l'horizontale", qu'une arborescence binaire planaire explique le deuxième intérêt de l'étude de ces algorithmes de dessins d'arborescences planaires binaires. L'un des algorithmes présentés (celui de Knuth) conduira (cf chapitre 6, partie 2), après adaptation à une modélisation nouvelle d'un réseau fluvial, liant aire des régions drainées et nombre de nœuds du réseau les drainant. Cette modélisation d'un réseau fluvial ne peut pas être réalisée indépendamment de la modélisation du terrain drainé (bassin fluvial). Si l'on modélise le terrain drainé par une carte (encore une fois planaire, si projetée dans le plan de l'horizontale), cela revient à dire que l'on est amené à modéliser topologiquement simultanément une carte planaire est une arborescence planaire la recouvrant (au moins partiellement), puis à plonger automatiquement dans le plan les deux objets (arbre et carte planaire). Le problème du dessin automatique d'une carte topologique planaire est reconnu difficile si l'on impose des contraintes fines (comme des contraintes de densité de points de la carte en fonction de l'aire par exemple). Il sera abordé dans la deuxième partie. Le chapitre 5, analogue dans sa démarche au chapitre 2 sur le dessin d'arbres planaires, présente quelques algorithmes de dessin automatique de cartes planaires respectant des propriétés "esthétiques" de plus en plus contraignantes (cf [La84], [CO85]). Les résultats obtenus dans le dessin de cartes planaires sont moins élaborés que dans le cadre des arborescences planaires, ceci étant dû à la beaucoup plus grande complexité structurelle des cartes comparées aux arbres planaires. Cependant, la comparaison des fondements des algorithmes de dessin d'arbres planaires d'une part et de dessin de cartes planaires d'autre part, présentés aux chapitres 2 et 5, est très intéressante et conduit à une nouvelle idée d'algorithme de dessin de cartes planaires, présentée en fin de chapitre 5. On constate dans la suite d'algorithmes de dessin d'arborescences planaires présentés au chapitre 2, une double évolution :

- Le passage du préordre en postordre, permettant au moment du traitement d'un nœud (affectation de ses coordonnées) de disposer de plus en plus d'information sur les autres nœuds qui lui sont liés. On constatera en particulier que la prise en compte de contraintes esthétiques de plus en plus sophistiquées dans le dessin d'une arborescence planaire est obtenue naturellement lors du parcours en profondeur, par le passage d'un traitement en préordre à un traitement en ordre puis en postordre des nœuds de l'arbre. Ceci s'explique très bien par le fait que l'information disponible lors du traitement en postordre d'un nœud est beaucoup plus grande que lors du traitement en préordre, puisque en postordre, on a déjà traité (positionné dans le plan) tous les nœuds du sous-arbre du nœud courant.

- L'abandon progressif de la fixation a priori de la "marge gauche" du support d'affichage du dessin (feuille, écran) dans l'algorithme d'affectation d'une "future place libre" au nœud courant sur l'horizontale de son niveau. Cette marge gauche fausse dans l'affectation des coordonnées les symétries, ne permettant pas de les respecter lors du dessin de l'arbre.

Cette double progression peut être analysée dans le cas des cartes planaires. On constate ainsi que tous les algorithmes présentés travaillent en "préordre" (c'est à dire en déterminant les coordonnées d'un nœud quand on le rencontre pour la première fois) et que l'analogue de la marge gauche fixée a priori, c'est à dire la fixation a priori du polygone extérieur de la carte planaire est toujours présente dans les algorithmes de dessin de cartes planaires. Cette analyse conduit, en fin de chapitre 5, à la proposition de bases pour un nouvel algorithme de dessin de cartes planaires, travaillant en "postordre", et sans fixation a priori du polygone extérieur (cf [AJ92b]).

0.3 Résultats présentés dans les parties 1, 2 et 3

Les chapitres 3, 4 de la partie 1, 6 de la partie 2 et 7 et 8 de la partie 3 présentent les résultats de cette thèse. Ils ont été publiés dans [VE89a], [VE89b], [VJ90], [AJ90a], [AJ90b], [AJ91a], [AJ91b], [AJ92a], cf également [JA89], [AJ90c].

Dans la partie 1, le chapitre 3 présente une modélisation de la forme des végétaux par l'approche combinatoire que nous avons développée dans Viennot, Eyrolles, Janey, Arquès [VE89a], [VE89b]. Cette approche est fondée sur le concept de matrice de ramification. Cette matrice dépend uniquement de l'arbre topologique sous-jacent et est définie à partir des notions combinatoires d'ordre et de biordre d'un noeud (Horton [Ho45], Strahler [St52]). La forme de l'arbre et nombre d'aspects visuels (aspect touffu, effilé, bien équilibré) sont directement contrôlés par la matrice de ramification, mais ne sont en revanche pas issus d'un processus de croissance au sens botanique. Cet aspect est pris en compte au chapitre 4 dans lequel est présentée une modélisation dite "par matrice d'évolution", qui permet la représentation d'un arbre à différentes étapes de sa croissance (cf [AJ91a]). Cette matrice d'évolution est stochastique, triangulaire supérieure, infinie dans les deux directions. Elle permet de quantifier la forme et l'aspect visuel de l'arbre, mais pilote de plus la croissance de l'arbre génération après génération, permettant de contrôler l'aspect visuel de cet arbre à chacune de ces générations. On pourra ainsi voir un arbre être bien équilibré pendant les premières étapes de sa croissance, puis devenir chevelu avec de longs segments dans les étapes suivantes de son évolution et enfin achever sa croissance par l'apparition de petits arbres parfaits. Cette notion de matrice d'évolution permet de piloter la croissance des branches de l'arbre binaire topologique. Dans cette méthode l'arbre topologique sous-jacent joue un rôle essentiel, en particulier pour quantifier la forme de l'arbre finalement représenté.

Dans la partie 2, le chapitre 6 décrit un modèle de synthèse d'image d'un relief montagneux à partir de son bassin fluvial (cf [AJ91b], [AJ92a]). Ce modèle sépare clairement les aspects topologiques et géométriques dans la conception du bassin fluvial :

La première partie est purement topologique et est décomposée en trois étapes. Après avoir modélisé un réseau fluvial quelconque par un arbre binaire topologique, un algorithme de construction d'une carte topologique planaire quasi-triangulaire admettant cette arborescence planaire comme arborescence recouvrante, est proposé. Un raffinement de cette carte planaire quasi-triangulaire permet alors de définir des lignes de crête.

La seconde partie est le plongement géométrique 3D des trois étapes de ce modèle topologique. Un algorithme de plongement de l'arbre binaire dans le plan, respectant des conditions de répartition de densité de nœuds, est d'abord proposé. On montre alors que la triangularisation topologique admettant cet arbre comme arbre recouvrant peut être réalisée par segments de droite. On obtient ainsi un algorithme de dessin automatique dans le plan par segments de droites d'une carte planaire quasi-triangulaire admettant une arborescence recouvrante donnée. Le raffinement final de cette carte planaire (pour l'adjonction de lignes de crêtes, dans un but de réalisme des images obtenues) peut alors être également réalisé par segments de droites sans difficulté.

Ce modèle topologique plongé dans le plan permet, par remontée des sommets de la carte, d'obtenir la modélisation géométrique simultanée du relief montagneux et de son bassin fluvial. Les sommets de l'arborescence sont remontés en fonction des ordres combinatoires de Strahler de ses nœuds. Les sommets surajoutés des lignes de crête sont munis d'ordonnées compatibles avec l'écoulement des eaux, ce qui conduit à la résolution de systèmes d'inéquations linéaires. Ces travaux se distinguent des précédents dans leurs aspects topologiques :

- L'algorithme de construction automatique d'une carte planaire quasi-triangulaire par segments de droite admettant une arborescence planaire donnée comme arborescence recouvrante est nouveau.

- Le problème du dessin d'arborescences planaires et de cartes planaires respectant des contraintes de densité de points est reconnu comme difficile est a été abordé dans Wetherell, Shannon [WS79], Reingold, Tilford [RT81], Laumond [La84], Chiba, Onoguchi, Nishizeki [CO85], de Fraissex, Rosenstiehl [FR83,84]. Nous proposons ici dans le cas d'une carte planaire quasi-triangulaire munie d'une arborescence binaire recouvrante, un nouvel algorithme, particulièrement bien adapté au problème infographique posé et permettant de respecter de tels types de contraintes.

Dans leurs aspects géométriques, les lois utilisées pour la définition du relief sont nouvelles.

La partie 3 présente enfin les méthodes utilisées pour le dessin et le rendu réaliste d'arbres et de bassins montagneux (cf [AJ90a,b,c], [JA89]). Les techniques permettant de réaliser des scènes associant ces deux modélisations (bassin montagneux couvert de végétation) sont présentées. Tous les travaux présentés aux parties 1 et 2 ont été développés sur micro-ordinateur IBM PS/2 8580, ce qui a nécessité de trouver les moyens d'obtenir une vitesse de calcul et de dessin compatible avec la puissance limitée d'un micro-ordinateur. L'adaptation des algorithmes classiques à cette situation y est détaillée comme par exemple, le problème de l'affichage des milliers de facettes constituant un arbre 3D.

En conclusion une caractéristique de ce travail est de réaliser une grande unité dans les algorithmes de synthèse de paysages naturels : ce sont en effet les mêmes algorithmes qui sont utilisés dans les images présentées pour construire l'arborescence sous-jacente au bassin fluvial et aux arbres botaniques portés par le bassin fluvial.