<html>  <head> <style type="text/css">   body { font-family: "Comic Sans MS";          font-size: 10pt;}   table { font-family: "Comic Sans MS";          font-size: 10pt;}   p { font-family: "Comic Sans MS";          align = left;          font-size: 10pt;}   tr { font-family: "Comic Sans MS";          font-size: 10pt;}   td { font-family: "Comic Sans MS";          font-size: 10pt;}   dl { font-family: "Comic Sans MS";          font-size: 10pt;}   dt { font-family: "Comic Sans MS";          font-size: 10pt;} </style> <title>Chapitre 0 : Introduction, prsentation des rsultats et de leur contexte</title> </head>  <body background="bg.jpg" bgcolor="#FFFF99" text="#333399" link="#990033" vlink="#009966" alink="#FF6600">  <table border="0" cellpadding="0" cellspacing="0" width="100%">   <tr>     <td align="right" valign="top" width="150" height="70">&nbsp;<a href="Default.htm"><img     src="Fleche.gif" width="41" height="28"> <font size="3"><strong>RETOUR</strong></font></a></td>     <td align="center" valign="top" width="530" height="70"><font size="5"><strong>Chapitre 0</strong></font><p     align="center"><font size="4">Introduction, prsentation des rsultats<br>     et de leur contexte</font></p>     <p align="center">&nbsp;</td>   </tr>   <tr>     <td valign="top" width="100%" colspan="2">La synthse d&#146;images est  la fois un     moyen et un but dans la recherche scientifique actuelle : un moyen de comprendre des     phnomnes en les modlisant numriquement, en les visualisant lorsqu'ils sont     invisibles ou complexes et un but par la beaut des images gnres. Ceci est tout     particulirement vrai dans le domaine particulier de la synthse d&#146;images de     paysages o l&#146;on peut tout aussi bien vouloir comprendre ce qui conduit  la     cration de valles, de montagnes, d&#146;arbres, de nuages,..., que simplement crer     les images les plus ralistes possibles de la manire la plus simple possible.<p>La     synthse d'images ralistes comporte deux aspects relativement (bien que non totalement)     disjoints :</p>     <p>1) le dveloppement d'un modle sous-jacent aux objets que l'on dsire reprsenter,</p>     <p>2) le dveloppement de techniques permettant de raliser le &quot;rendu&quot; de la     scne ainsi modlise.</p>     <p>Une bonne introduction  ces deux domaines peut tre trouve dans [FV90].</p>     <p>Dans cette thse nous nous intresserons  ces deux aspects dans le cadre exclusif     de la synthse d'images de paysages,  partir de la modlisation de vgtaux et de     reliefs montagneux.</p>     <i><p>A la suite du chapitre 1 prsentant l'tat de l'art, cette thse se dcompose en     trois parties :</p>     <p>-&nbsp;La premire partie, chapitres 2  4, est consacre  la modlisation de la     forme et de la croissance de vgtaux par des mthodes combinatoires (cf [VE89a],     [VE89b], [VJ90], [AJ90a], [AJ91a]).</p>     <p>-&nbsp;La seconde partie, chapitres 5 et 6, prsente une nouvelle modlisation d'un     relief montagneux au travers de son bassin fluvial (cf [AJ91b], [AJ92a]).</p>     <p>&nbsp;La troisime partie, chapitre 7  9, aborde enfin les problmes lis au rendu     raliste des scnes modlises (cf [JA89], [AJ90b], [AJ90c], Planches 12, 16  21).</i><b></p>     <p>0.1 Contexte de ce travail dans le cadre de la synthse d'images de paysages</b></p>     <p>Il sera prsent en dtail dans le chapitre 1. Nous dcrivons ici dans une brve     revue bibliographique, comment les rsultats prsents aux chapitres 3, 4, 6, 7 et 8 se     situent dans le domaine de la synthse d'images (voir [AJ90c] dans son entier pour une     revue des images prsentes ces 10 dernires annes  IMAGINA)..</p>     <p><b>0.1.1 Premire partie : synthse d'images de vgtaux</b></p>     <p>Celle-ci a fait l'objet d'un grand nombre d'tudes ces dernires annes: 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, Franon, Jaeger,     Puech [RE88], Viennot, Eyrolles, Janey, Arqus [VE89] [AJ90] [AJ91a], Greene [Gr89].</p>     <p>Dans ces travaux, la gnration d'un vgtal est principalement opre  deux     niveaux. Dans un premier temps, est gnr l'arbre topologique (combinatoire)     sous-jacent  l'arbre rel. Gnralement cet arbre est binaire ou ternaire. Le second     niveau consiste en la gnration de l'arbre gomtrique associ. Toutes ces mthodes     appliquent des modles gomtriques plus ou moins sophistiqus  l'arbre topologique.     La gomtrie minimale consiste en une modlisation en deux dimensions, avec     l'paisseur et la longueur choisies pour chaque arte et un angle  droite et  gauche     pour chaque n&#156;ud d'embranchement. Une gomtrie plus sophistique doit tre     utilise pour une visualisation en trois dimensions  laquelle pourront tre ajouts     des lments vgtaux (feuilles, fleurs), une texture sur le tronc et les branches et     des contraintes extrieures telles que le vent, la lumire ou la gravit,&#133; .</p>     <p>Dans tous ces travaux, les aspects topologiques et gomtriques sont plus ou moins     lis. Ces mthodes peuvent tre classes comme suit :</p>     <p>- Les mthodes gomtriques : La topologie est ici secondaire et la gomtrie     acquiert ds lors une grande importance pour obtenir une grande diversit de formes     Kawaguchi [Ka82], Aono et Kunii [AK84], Honda [Hon71] et Bloomenthal [Bl85].</p>     <p>- Les mthodes axes sur la visualisation : La technique des systmes de particules     Reeves et Blau [RB85], les techniques fractales de Mandelbrot, Oppenheimer [Op86], les     systmes de fonctions itres de Barnsley, Jacquin, Malassenet, Reuter, Sloan [BJ88],     Demko, Hodges et Naylor [DH85].</p>     <p>- Les mthodes environnementales s'intressent  l'importance de l'environnement     dans le dveloppement d'une plante. Citons le modle de croissance stochastique et     rcursive de Niklas [Ni86] ou le modle de dveloppement de lierre sur une surface par     croissance stochastique guide par un automate sur un espace de voxels, tenant compte de     contraintes d'intersection ou d'illumination, Greene [Gr89].</p>     <p>- Les mthodes topologiques qui mettent l'accent sur le dveloppement de l'arbre     topologique sous-jacent  l'arbre rel. Dans ce cadre, on peut distinguer :</p>     <p> L'approche botanique : le modle topologique est directement issu de l'tude     botanique de l'arbre que l'on dsire modliser. Les principaux travaux dans ce domaine     sont ceux de De Reffye, Edelin, Franon, Jaeger, Puech [RE88].</p>     <p>&nbsp;L'approche L-systmes : La technique de gnration par rgles de     rcritures utilisant la thorie des L-systmes dveloppe par Lindenmayer, Smith     [Sm84], Prusinkiewicz [Pr86], Prusinkiewicz, Lindenmayer, Hanan [PL88], permet de     modliser le dveloppement d'arbustes ou de cellules par codage (mot ou graphe).</p>     <p> L'approche combinatoire que nous avons dveloppe dans Viennot, Eyrolles, Janey,     Arqus [VE89a], [VE89b]. L'introduction du concept de matrice de ramification permet de     sparer la forme de l'arbre de son histoire, beaucoup d'aspects visuels (aspect touffu,     effil, bien quilibr) tant prsents dans la matrice. Cette matrice dpend     uniquement de l'arbre topologique sous-jacent et est dfinie  partir des notions     combinatoires d'ordre et de biordre d'un noeud (Horton [Ho45], Strahler [St52]). La forme     de l'arbre est directement contrle 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 synthse d'images d'arbres a t auparavant     suggre mais non dveloppe dans [EF86], article dans lequel la croissance des     ramifications est dtermine par une extension de la &quot;mthode de Rmy&quot;     utilisant un jeu de probabilits (Deux cas extrmes y sont prsents conduisant  la     gnration des arbres binaires alatoires et des arbres binaires croissants     alatoires).</p>     <p>La classification des modlisations de vgtaux que nous prsenterons au chapitre 1     &quot;Etat de l'art en synthse d'images de paysages naturels&quot;, est ainsi fonction     de la caractristique principale de chaque modle. Elle distinguera les grandes     catgories suivantes:</p>     <p>- les pionniers,</p>     <p>- les modlisations issues de la gomtrie classique, </p>     <p>- les modlisations fractales de paysages,</p>     <p>- les&nbsp;modles combinatoires,</p>     <p>- les modles  base de rcriture,</p>     <p>- les&nbsp;modles botaniques,</p>     <p>- les modles environnementaux.</p>     <p>Ces travaux sont ensuite prsents selon une classification transversale en fonction     des trois aspects :Topologie, Gomtrie et Rendu.</p>     <b><p>0.1.2 Deuxime partie : synthse d'images de terrains et reliefs montagneux</b></p>     <p>Les domaines d'application de la synthse d'images de reliefs sont nombreux     (simulateurs de vols, animation, images de synthse, CADCAM, ...) et imposent deux     objectifs opposs : le ralisme et l'efficacit. Peu de modles concilient aujourd'hui     ces deux contraintes : ceux utiliss dans les applications &quot;temps rel&quot; (comme     les simulateurs de vol) sacrifient le ralisme  l'efficacit, en revanche les modles     les plus ralistes peuvent demander un temps important pour calculer une unique scne.</p>     <p>Les techniques dveloppes en modlisation de terrain peuvent tre classes en     trois catgories :</p>     <p>- La premire catgorie, parfois qualifie de procdurale, 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 hirarchises pour tenir compte de la distance  l'observateur, par Marshall,     Wilson, et Carlson [MW80] qui utilisent une base de donne de primitives linaires et     par Gardner [Ga84] dont les surfaces primitives sont des quadriques. Ces techniques,     historiquement parmi les premires, conduisent  des reliefs aux lignes douces et ont     souvent l'inconvnient de prsenter des discontinuits dans le gradient de la texture     aux intersections des surfaces.</p>     <p>- La seconde catgorie trs souvent considre comme la plus efficace pour la     cration d'images ralistes (Voss [Vo83], Cook, Carpenter, Porter, Reeves, Salesin,     Smith [CC83]) est celle des techniques fractales (Mandelbrot [Ma82]). Elle est prsente     sous ses diffrents aspects dans Barnsley, Devaney, Mandelbrot, Peitgen, Saupe, Voss     [BD88] et a fait l'objet de trs nombreux travaux pour l'implantation efficace des     fractals stochastiques (par opposition aux fractals dterministes : courbe de Koch, cf     [Fo87]), implantations qui sont essentiellement des approximations du mouvement Brownien     fractionnaire : Fournier, Fussel, Carpenter [FF82], Miller [Mi86], Smith [Sm84] (qui     prsente les techniques de subdivision rcursive de [FF82] en termes de grammaires et de     rgles de rcriture).</p>     <p>Les qualits des techniques fractales s'expriment en termes de ralisme remarquable,     de trs importante amplification des donnes et du niveau de dtail. Certains     inconvnients (comme l'effet de plissement, &quot;creasing effect&quot;, li      l'indpendance du contexte des grammaires prcites) ont t exprims, entre autres,     par Mandelbrot dans [BD88] (Annexe A) :</p>     <i><p>&quot;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).&quot;</i></p>     <p>Une autre faon d'exprimer ce problme est de constater que dans les images fractales     de montagnes, valles et montagnes sont symtriques, ceci tant d  la symtrie de     la loi gaussienne utilise, alors que dans la ralit la montagne et son fleuve     prsentent une totale dissymtrie due  l'rosion. Mandelbrot bauche  ce problme     un type de solution (cf [BD88]) qui consiste dans un premier temps,  construire     rcursivement, simultanment deux fractals dterministes reprsentant le rseau     fluvial et le rseau des lignes de partage des eaux, puis dans un deuxime temps,      relever le relief le long des lignes de partage des eaux, par une technique de subdivision     rcursive modifie pour tenir compte des problmes d'itude (maxima pour les sources,     diminution de l'itude le long des fleuves, ...).</p>     <p>- Cette dmarche qui consiste  modliser un relief  partir d'un modle     d'rosion caractrise la troisime catgorie de techniques de modlisation de     terrain. Outre la solution sus-mentionne de Mandelbrot, les travaux de Kelley, Malin,     Nielson [KM88], sont caractristiques de cette approche. Dans cet article, la description     du bassin fluvial (fleuve et bassin de drainage) est fonde sur des modles empiriques     d'rosion utiliss en gomorphologie (cf [Ab80], [How71], [Sh66]). Le maillage     polygonal ainsi obtenu est alors interpol par une surface analogue  une surface spline     sous tension. Cette mthode matrialise un modle de gnration <i>statique</i>,     c'est  dire qu'il n'y a pas simulation de l'rosion par dplacement de matire, mais     gnration d'un relief  partir des consquences d'un phnomne d'rosion     prsentes sous forme de lois topologiques et gomtriques. Les modles <i>dynamiques</i>     de gnration de reliefs de Roudier [Ro91] et Musgrave, Kolb et Mace [KMK89] modlisent     en revanche l'volution d'un relief au moyen de processus mettant en &#156;uvre des     dplacements de matire.</p>     <p>C'est dans cette troisime catgorie (modle statique d'rosion) que se situe le     modle de bassin fluvial que nous avons dvelopp. L'ide de base de ce modle est de     gnrer un bassin montagneux  partir de la modlisation planaire de son bassin     fluvial. Ce bassin fluvial est ainsi considr comme un arbre binaire planaire, le     terrain tant alors considr comme une carte planaire admettant cet arbre binaire     comme arbre recouvrant. La modlisation finale du bassin montagneux consiste alors      remonter les points de cette carte planaire, en tenant compte de paramtres issus de     l'analyse des bassins fluviaux.</p>     <p>La classification des modlisations de terrains et bassins montagneux que nous     prsenterons au chapitre 1 distinguera ainsi les grandes catgories suivantes:</p>     <p>- les techniques  base de plaquage de texture,</p>     <p>- les mthodes fractales,</p>     <p>- les techniques bases sur un modle d'rosion.</p>     <b><p>0.2 Contexte de ce travail dans le cadre du dessin automatique d'arbres et de cartes     planaires</b></p>     <p>Si l'on modlise un terrain, un relief en projection sur le plan de l'horizontale par     une carte planaire, si l'on modlise un rseau fluvial en projection dans le plan de     l'horizontale par un arbre binaire, on constate que la modlisation d'un relief     montagneux et de son rseau fluvial sous-jacent est directement lie 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     donnes sous-jacent au dessin d'arbres planaires sont identiques  ceux du dessin de     vgtaux, mme si les contraintes graphiques sont fort diffrentes. 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 prsentation choisie, sans prtendre      l'exhaustivit, a pour but de dcrire 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 sophistiques satisfaisant des contraintes graphiques complexes, et     ceci en parallle pour les arbres au chapitre 2 et pour les cartes au chapitre 5.     L'tude compare de ces deux dmarches algorithmiques, relativement acheve dans le     cas des arbres et encore inacheve dans le cadre plus complexe des cartes, est trs     intressante et conduit  de nouvelles ides pour le dveloppement 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 prliminaire  la modlisation de bassins     fluviaux montagneux, est prsente au chapitre 6.</p>     <p>Plus prcisment :</p>     <p>Le chapitre 2 prsente les dfinitions de base sur les cartes planaires et arbres     planaires qui serviront dans la suite de la thse. Il dtaille les liens entre les     notions de cartes planaires topologiques et cartes planaires combinatoires et dcrit les     structures de donnes qui ont servi  l'implantation des algorithmes dcrits dans la     suite de la thse. Dans une seconde partie, ce chapitre s'intresse au dessin     d'arborescences planaires (essentiellement binaires) et dcrit quelques algorithmes     caractristiques de ce domaine (cf [WS79], [RT81]). Les contraintes qui prsident au     dessin d'arborescences planaires (contraintes esthtiques : centrage d'un pre par     rapport  ses deux fils, n&#156;uds de mme niveau situs sur une mme horizontale,     respect des symtries, sous-arbres identiques reprsents de faon identique, &#133;;     contraintes de planarit &#133;) sont fort diffrentes de celles que l'on rencontre dans     la synthse d'image de vgtaux, mme si les objets de base sont les mmes : des     arbres binaires. En effet dans le cas de la synthse de vgtaux, le dessin se fait     dans R<font size="1">3</font>. 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 vgtaux, les contraintes sont de nature &quot;rendu&quot;     (modlisation 3D, modlisation d'embranchements, modles d'illumination, &#133; cf     partie 3). Malgr cette importante diffrence, les algorithmes de dessin de ces deux     catgories d'arborescences planaires sont fonds sur les mmes algorithmes de parcours     prioritairement en profondeur de la structure arbre binaire sous-jacente.</p>     <p>Le fait qu'un rseau fluvial n'est autre, si on le projette sur le plan de     &quot;l'horizontale&quot;, qu'une arborescence binaire planaire explique le deuxime     intrt de l'tude de ces algorithmes de dessins d'arborescences planaires binaires.     L'un des algorithmes prsents (celui de Knuth) conduira (cf chapitre 6, partie 2),     aprs adaptation  une modlisation nouvelle d'un rseau fluvial, liant aire des     rgions draines et nombre de n&#156;uds du rseau les drainant. Cette modlisation     d'un rseau fluvial ne peut pas tre ralise indpendamment de la modlisation du     terrain drain (bassin fluvial). Si l'on modlise le terrain drain par une carte     (encore une fois planaire, si projete dans le plan de l'horizontale), cela revient      dire que l'on est amen  modliser topologiquement simultanment 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 problme 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 deuxime partie. Le chapitre 5, analogue     dans sa dmarche au chapitre 2 sur le dessin d'arbres planaires, prsente quelques     algorithmes de dessin automatique de cartes planaires respectant des proprits     &quot;esthtiques&quot; de plus en plus contraignantes (cf [La84], [CO85]). Les     rsultats obtenus dans le dessin de cartes planaires sont moins labors que dans le     cadre des arborescences planaires, ceci tant d  la beaucoup plus grande complexit     structurelle des cartes compares 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, prsents aux chapitres 2 et 5, est trs intressante et     conduit  une nouvelle ide d'algorithme de dessin de cartes planaires, prsente en     fin de chapitre 5. On constate dans la suite d'algorithmes de dessin d'arborescences     planaires prsents au chapitre 2, une double volution :</p>     <p>- Le passage du prordre en postordre, permettant au moment du traitement d'un     n&#156;ud (affectation de ses coordonnes) de disposer de plus en plus d'information sur     les autres n&#156;uds qui lui sont lis. On constatera en particulier que la prise en     compte de contraintes esthtiques de plus en plus sophistiques dans le dessin d'une     arborescence planaire est obtenue naturellement lors du parcours en profondeur, par le     passage d'un traitement en prordre  un traitement en ordre puis en postordre des     n&#156;uds de l'arbre. Ceci s'explique trs bien par le fait que l'information disponible     lors du traitement en postordre d'un n&#156;ud est beaucoup plus grande que lors du     traitement en prordre, puisque en postordre, on a dj trait (positionn dans le     plan) tous les n&#156;uds du sous-arbre du n&#156;ud courant.</p>     <p>- L'abandon progressif de la fixation a priori de la &quot;marge gauche&quot; du     support d'affichage du dessin (feuille, cran) dans l'algorithme d'affectation d'une     &quot;future place libre&quot; au n&#156;ud courant sur l'horizontale de son niveau. Cette     marge gauche fausse dans l'affectation des coordonnes les symtries, ne permettant pas     de les respecter lors du dessin de l'arbre.</p>     <p>Cette double progression peut tre analyse dans le cas des cartes planaires. On     constate ainsi que tous les algorithmes prsents travaillent en &quot;prordre&quot;     (c'est  dire en dterminant les coordonnes d'un n&#156;ud quand on le rencontre pour     la premire fois) et que l'analogue de la marge gauche fixe a priori, c'est  dire la     fixation a priori du polygone extrieur de la carte planaire est toujours prsente 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 &quot;postordre&quot;, et sans fixation a priori du polygone extrieur (cf     [AJ92b]).</p>     <b><p>0.3 Rsultats prsents dans les parties 1, 2 et 3</b></p>     <p>Les chapitres 3, 4 de la partie 1, 6 de la partie 2 et 7 et 8 de la partie 3     prsentent les rsultats de cette thse. Ils ont t publis dans [VE89a], [VE89b],     [VJ90], [AJ90a], [AJ90b], [AJ91a], [AJ91b], [AJ92a], cf galement [JA89], [AJ90c].</p>     <p>Dans la partie 1, le chapitre 3 prsente une modlisation de la forme des vgtaux     par l'approche combinatoire que nous avons dveloppe dans Viennot, Eyrolles, Janey,     Arqus [VE89a], [VE89b]. Cette approche est fonde sur le concept de matrice de     ramification. Cette matrice dpend uniquement de l'arbre topologique sous-jacent et est     dfinie  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 contrls 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 prsente une modlisation dite     &quot;par matrice d'volution&quot;, qui permet la reprsentation d'un arbre      diffrentes tapes de sa croissance (cf [AJ91a]). Cette matrice d'volution est     stochastique, triangulaire suprieure, 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 gnration aprs gnration, permettant de contrler l'aspect visuel de cet     arbre  chacune de ces gnrations. On pourra ainsi voir un arbre tre bien     quilibr pendant les premires 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 mthode     l'arbre topologique sous-jacent joue un rle essentiel, en particulier pour quantifier la     forme de l'arbre finalement reprsent.</p>     <p>Dans la partie 2, le chapitre 6 dcrit un modle de synthse d'image d'un relief     montagneux  partir de son bassin fluvial (cf [AJ91b], [AJ92a]). Ce modle spare     clairement les aspects topologiques et gomtriques dans la conception du bassin fluvial     :</p>     <p>La premire partie est purement topologique et est dcompose en trois tapes.     Aprs avoir modlis un rseau 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 dfinir des lignes de crte.</p>     <p>La seconde partie est le plongement gomtrique 3D des trois tapes de ce modle     topologique. Un algorithme de plongement de l'arbre binaire dans le plan, respectant des     conditions de rpartition de densit de n&#156;uds, est d'abord propos. On montre     alors que la triangularisation topologique admettant cet arbre comme arbre recouvrant peut     tre ralise 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 donne. Le raffinement final de cette carte     planaire (pour l'adjonction de lignes de crtes, dans un but de ralisme des images     obtenues) peut alors tre galement ralis par segments de droites sans difficult.</p>     <p>Ce modle topologique plong dans le plan permet, par remonte des sommets de la     carte, d'obtenir la modlisation gomtrique simultane du relief montagneux et de son     bassin fluvial. Les sommets de l'arborescence sont remonts en fonction des ordres     combinatoires de Strahler de ses n&#156;uds. Les sommets surajouts des lignes de crte     sont munis d'ordonnes compatibles avec l'coulement des eaux, ce qui conduit  la     rsolution de systmes d'inquations linaires. Ces travaux se distinguent des     prcdents dans leurs aspects topologiques : </p>     <p>- L'algorithme de construction automatique d'une carte planaire quasi-triangulaire par     segments de droite admettant une arborescence planaire donne comme arborescence     recouvrante est nouveau.</p>     <p>- Le problme 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, particulirement bien adapt au problme infographique pos et permettant     de respecter de tels types de contraintes.</p>     <p>Dans leurs aspects gomtriques, les lois utilises pour la dfinition du relief     sont nouvelles.</p>     <p>La partie 3 prsente enfin les mthodes utilises pour le dessin et le rendu     raliste d'arbres et de bassins montagneux (cf [AJ90a,b,c], [JA89]). Les techniques     permettant de raliser des scnes associant ces deux modlisations (bassin montagneux     couvert de vgtation) sont prsentes. Tous les travaux prsents aux parties 1 et     2&nbsp;ont t dvelopps sur micro-ordinateur IBM PS/2 8580, ce qui a ncessit de     trouver les moyens d'obtenir une vitesse de calcul et de dessin compatible avec la     puissance limite d'un micro-ordinateur. L'adaptation des algorithmes classiques  cette     situation y est dtaille comme par exemple, le problme de l'affichage des milliers de     facettes constituant un arbre 3D.</p>     <p>En conclusion une caractristique de ce travail est de raliser une grande unit     dans les algorithmes de synthse de paysages naturels : ce sont en effet les mmes     algorithmes qui sont utiliss dans les images prsentes pour construire l'arborescence     sous-jacente au bassin fluvial et aux arbres botaniques ports par le bassin fluvial.</td>   </tr> </table> </body> </html> 
