<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 1 : Etat de l'art en synthse d'images de paysages naturels</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="149"><p align="center">&nbsp;<a     href="Default.htm"><img src="Fleche.gif" width="41" height="28"> <font size="3"><strong>RETOUR</strong></font></a></td>     <td align="right" valign="top" width="530" height="149"><p align="center"><font size="5"><strong>Chapitre     1</strong></font></p>     <p align="center"><font size="4">Etat de l'art en synthse d'images<br>     de paysages naturels</font></p>     <p align="center">&nbsp;</td>   </tr>   <tr>     <td valign="top" width="100%" colspan="2"><b>1.1 Introduction</b><p>Dans le cadre de la     synthse d'image, actuellement en plein dveloppement, la modlisation de scnes     naturelles et en particulier de paysages reprsente un challenge particulier en raison de     la complexit importante des scnes  synthtiser. Un arbre simple tant compos de     plusieurs milliers de branches et de plusieurs dizaines de milliers de feuilles, il sera     difficile de grer en temps rel une animation comportant plus de quelques arbres sur     les stations de travail graphiques actuelles (qui peuvent grer quelques millions de     facettes par seconde). Cet aspect du problme en sus de l'intrt du sujet par lui     mme, explique probablement les dveloppements constants de la recherche dans ce     domaine. Les mthodes dveloppes sont varies et de nombreuses classifications ont     t proposes comme par exemple dans Fournier [Fo87]. L'objet de cette introduction est     de prsenter une telle classification dans les deux domaines qui font l'objet de cette     thse: la modlisation des vgtaux et la modlisation de terrain.</p>     <p><img src="Chapitre1/1erePhoto.gif" width="680" height="540"></p>     <p>Photographie 1A : Exemple de paysage</p>     <p><b>1.2 Synthse d'images de vgtaux</b></p>     <p>La littrature comporte un nombre important de travaux ayant pour objet la     modlisation et la synthse d'images d'arbres botaniques par des mthodes     informatiques. Ils se caractrisent par la trs grande diversit des approches     proposes qui peuvent tre classifies en les catgories suivantes :</p>     <p><b>1.2.1 Les pionniers</b></p>     <p><b>1.2.1.1 </b>L'un des tout premiers  s'intresser  la forme des arbres d'un     point de vue informatique graphique fut le Japonais Honda [Hon71] qui ds le dbut des     annes 70 s'intressa aux diverses formes adoptes par un arbre en fonction d'un     certain nombre de paramtres  caractre gomtrique. Pour rendre la comparaison     possible entre les diverses formes, la structure topologique sous-jacente  tous les     arbres dessins est un arbre binaire parfait. Le modle gomtrique dfinit:</p>     <p>- des rapports de diminution des longueurs des branches : chaque branche fille droite     (respectivement gauche) est un segment de droite dont la longueur est raccourcie par     rapport  la longueur de sa branche mre d'un rapport R1 (respectivement R2),</p>     <p>- des angles d'embranchement aux diffrents n&#156;uds : une branche mre non     verticale (direction de la gravit) se ramifie en deux branches filles dans le plan qui     la contient et qui est perpendiculaire au plan qu'elle forme avec la verticale (Figure     1A). Les angles de dviation q1 et q2 entre les branches filles droite et gauche et leur     mre sont fixs. Dans le cas d'une branche mre verticale, le branchement a lieu dans     le plan xOz avec les angles q1 et q2 avec la verticale, si les deux angles de dviation     (q1 et q2) sont non nuls. Si l'un des deux est nul un traitement particulier a lieu car     l'une des branches filles reste verticale, un angle de dviation a en projection dans le     plan xOy est alors introduit de proche en proche pour rpartir les branches dans l'espace     (Figure 1A').</p>     <p><img SRC="Chapitre1/Image070.gif" width="322" height="301"></p>     <p>Figure 1A : Gomtrie selon Honda (cas gnral)</p>     <p>&nbsp;<img SRC="Chapitre1/Image071.gif" width="355" height="416"></p>     <p>Figure 1A' : Gomtrie selon Honda (cas particulier)</p>     <p>Les structures ainsi obtenues sont reprsentes en fil de fer par Honda de manire      pouvoir analyser facilement leurs formes.</p>     <p><b>1.2.1.2 </b>Les travaux de Honda furent repris et poursuivis par Aono et Kunii     [AK84] qui dans le cadre d'un logiciel appel A-system, formalisrent la dmarche de     Honda  partir de L-systmes (voir dfinition des L-systmes ci-aprs) trs     particuliers permettant de gnrer des arbres binaires ou ternaires parfaits. Pour Aono     et Kunii les L-systmes mme s'ils peuvent tre amliors, ne sont pas assez     puissants pour modliser des arbres botaniques car les formes de ces arbres sont trop     complexes.</p>     <p>Au niveau gomtrique, ils introduisent des variations dans le modle de Honda pour     pouvoir simuler :</p>     <p>- le vent par une dviation uniforme de tous les n&#156;uds ou un tropisme par     simulation d'attracteurs ou d'inhibiteurs d'action proportionnelle  leur distance au     n&#156;ud trait,</p>     <p>- des arbres ternaires,</p>     <p>- une relation entre le niveau des n&#156;uds dans l'arbre et les angles de branchement     en ces n&#156;uds.</p>     <p>Enfin ils amliorrent le rendu des images en attribuant une paisseur aux branches     fonction de leur niveau dans l'arbre et en munissant leurs arbres d'ombres et de feuilles     modlises semble-t-il  partir de nuages de points.</p>     <p><b>1.2.1.3 </b>Un autre pionnier, Kawaguchi [Ka82], modlise rcursivement des formes     gomtriques du type coraux, cornes, ...,  partir de primitives gomtriques simples     et de rgles de collage de ces primitives. L'lment de base de la construction est un     prisme constitu de deux bases (suprieure et infrieure) ayant des formes     homothtiques  une forme donne (souvent une ellipse) (Figure 1B).</p>     <p><img SRC="Chapitre1/Image072.gif" HSPACE="7" VSPACE="7" width="322" height="686"> </p>     <p>Figure 1B : Gomtrie selon Kawaguchi</p>     <p>La position et la taille relative de la base suprieure par rapport  la base     infrieure est donne par (Figure 1B) :</p>     <p>-&nbsp;un rapport appel taux de croissance,</p>     <p>-&nbsp;un vecteur d'inclinaison (qx,qy,qz) donnant en projection dans les plans     orthogonaux aux axes, les trois angles entre les deux plans des bases infrieure et     suprieure,</p>     <p>-&nbsp;un vecteur (Tx,Ty,Tz) de translation dfinissant le dplacement de la base     suprieure par rapport  la base infrieure.</p>     <p>L'accumulation rcursive de ces prismes permet d'obtenir des cornes telles que celles     prsentes dans [Ka82].</p>     <p><img SRC="Chapitre1/Image073.gif" hspace="7" vspace="7" width="512" height="405"> </p>     <p>Figure 1B' : Branchement selon Kawaguchi</p>     <p>Pour gnrer des structures arborescentes, une notion de ramification est introduite,     constitue par un prisme ayant une base ellipsodale infrieure et deux bases     ellipsodales suprieures dont les grands-axes sont orthogonaux (figure 1B'). Des     cylindres  section ellipsodale sont alors lis selon la figure 1B' aux bases de ce     prisme. Pour que le modle soit entirement dfini le rapport hauteur sur base de tous     les cylindres intermdiaires est le mme. La gnration rcursive de l'arborescence     est stoppe lorsqu'une condition gomtrique est vrifie (par exemple l'paisseur     des cylindres devient infrieure  une valeur limite).</p>     <p>Cette modlisation gomtrique est en fait la base d'une srie de travaux :</p>     <p><b>1.2.2 Modlisations issues de la gomtrie classique</b></p>     <p><b>1.2.2.1</b> Le modle de Bloomenthal [Bl85], part d'un arbre topologique     pralablement dfini appel <i>squelette</i>. Une caractristique de ce modle est de     dfinir pour toute branche mre une branche fille dominante (habituellement celle de     plus grande paisseur). Ce squelette est construit en interpolant chaque suite de n     artes (n+1 n&#156;uds d'embranchement) commenant par une branche fille non dominante     ou par la racine et se poursuivant par la succession des branches filles dominantes      chaque n&#156;ud, par une <i>B-spline C2 cubique</i>, c'est  dire n courbes splines     conscutives, de faon  obtenir le prolongement par continuit des drives     premire et seconde aux n-1 n&#156;uds d'embranchement intermdiaires. Une telle suite     de branches sera reprsente par les coefficients des n polynmes cubiques qui la     dfinissent. Ces coefficients sont dtermins par les positions et les tangentes aux     n+1 n&#156;uds. Cette mthode des B-Splines permet de fixer arbitrairement la tangente     initiale pour la premire branche (non dominante), tangente choisie d'autant plus     loigne de la direction de la branche mre que la branche fille est petite.</p>     <p><img SRC="Chapitre1/Image074.gif" HSPACE="7" VSPACE="7" width="224" height="366"> </p>     <p>Figure 1C : Reprsentation d'une arte par un cylindre gnralis</p>     <p><img SRC="Chapitre1/Image076.gif" width="296" height="285"></p>     <p>Figure 1C' : Modlisation d'un embranchement</p>     <p>La modlisation volumique de l'arbre est ralise en considrant chaque arte     comme un cylindre gnralis dont l'axe est la courbe B-spline prcite et dont la     section est un cercle de rayon variable (Figure 1C). La modlisation des embranchements     est ralise par des surfaces du type &quot;selle&quot; obtenues en considrant les     trois disques reprsentant les sections circulaires des branches (la mre et ses deux     filles), en les reliant par des courbes splines, et enfin en polygonalisant  partir de     ces courbes (Figure 1C').</p>     <p>Les angles de branchement entre artes, leurs longueurs et paisseurs sont choisies     alatoirement dans des champs dfinis en fonction du dveloppement de l'arbre.</p>     <p>Dans cette approche le rendu est tout particulirement tudi. Par exemple les     veines de l'corce sont obtenues par une technique de modulation de la normale (&quot;<i>Bump     Mapping</i>&quot;) guide par l'image aux rayons X du moulage en pltre d'un morceau     d'corce rel. On cre ainsi un carreau de texture d'corce qui est ensuite plaqu     sur le tronc. Le problme du recollement des bords de deux carreaux de texture connexes     est rsolu par &quot;mlange&quot; des deux carreaux sur une bande frontire. Les     feuilles, elles, sont obtenues par digitalisation de feuilles d'rable relles et par     plaquage de cette image digitalise sur des surfaces polydriques. Le nombre de feuilles     dessines sur une branche est fonction de l'paisseur de cette branche. Le     positionnement d'une feuille dans l'espace est fonction de la direction de la branche qui     la porte. La gestion des feuilles et d'une texture permet ainsi l'obtention d'images en     gros plan trs ralistes.</p>     <p>On voit un bel exemple de branches gnres par Greene [Gr84] au moyen du modle de     Bloomenthal  la page de couverture des actes de SIGGRAPH'84. Cette image, extraite du     film d'animation &quot;Inside a Quark&quot;, montre trs bien la qualit de texture     obtenue par &quot;Bump Mapping&quot;.</p>     <p><b>1.2.2.2</b> Les travaux d'Oppenheimer [Op86] rentrent galement dans le cadre des     mthodes issues de la gomtrie classique, faisant le lien entre les travaux de     Kawaguchi et les mthodes fractales. La structure topologique sous-jacente est     constitue d'arbres binaires ou ternaires rsultant d'un processus de gnration     alatoire assez lmentaire faisant intervenir le nombre de branchements sur chaque     segment de branche principal et permettant d'obtenir des arbres auto-similaires et donc     fractals (Figure 1D). Oppenheimer reprend les travaux de Kawaguchi en ce sens qu' partir     de quatre primitives gomtriques simples : cylindre, spirale, hlice et tortillon, de     rgles de rduction et de collage faisant intervenir les paramtres suivants :</p>     <p><img src="Chapitre1/Image077.gif" width="242" height="416"></p>     <p>Figure 1D : Topologie selon Oppenheimer</p>     <p>- l'angle entre un segment principal et les artes qui s'y connectent,</p>     <p>- le rapport de longueur entre les artes principales d'un branchement et les branches     qui s'y connectent,</p>     <p>- le rapport de dcroissance des artes sur un segment,</p>     <p>- la valeur de la rotation hlicodale sur les branches,</p>     <p>il construit rcursivement les solides 3D en formes de cornes ou spirales qui sont      l'origine de ses branches.</p>     <p>Pour le rendu, Oppenheimer utilise des vecteurs &quot;<i>anti-aliass</i>&quot; pour     les branches les plus fines, et des prismes polygonaux pour les autres. Les ombrages des     facettes sont grs. Comme chez Bloomenthal, les veines de l'corce sont ralises     par modulation de la normale, modulation guide par un mouvement Brownien fractal en     forme de vague. Par ailleurs les feuilles qu'il modlise sont obtenues comme limite de     l'arborescence fractale des nervures qui les composent.</p>     <b><p>1.2.3 Modlisations fractales de paysages</p>     <p>1.2.3.1 Systmes de fonctions itres</b></p>     <p>Une mthode importante de compression et de restitution d'images est celle fonde sur     les systmes de fonctions itres (Iterated Function Systems, IFS) dveloppe par     Demko, Hodges et Naylor [DH85] ou Barnsley, Jacquin, Malassenet, Reuter et Sloan [BJ88].     Cette technique totalement trangre  toute analyse de la structure d'un paysage est     purement mathmatique et est fonde sur des thormes ergodiques.</p>     <p><i>IFS en noir et blanc</i> : A tout ensemble fini de fonctions affines strictement     contractantes {wn, 1=n=N} du plan, appel <i>systme de fonctions itres</i> (<i>IFS</i>     pour Iterated Function System), on associe la transformation W qui  B compact du plan     associe : W(B)=<img src="Chapitre1/Image078.gif" align="middle" width="59" height="44">.</p>     <p><i>L'attracteur</i> de l'IFS est alors l'unique point fixe A de W sur l'espace complet     des parties compactes du plan muni de la distance de Hausdorff (&nbsp;A=W(A)=<img     src="Chapitre1/Image079.gif" align="middle" width="58" height="39">), ensemble limite des points itrs z<font     size="1">n </font>obtenus  partir d'un point z<font size="1">0</font> arbitraire du     plan, en appliquant de faon itre avec quiprobabilit les applications w<font     size="1">i</font> (z<font size="1">n+1</font> = w<font size="1">i</font>(z<font size="1">n</font>)).</p>     <p>On remarquera la trs forte amplification de ces donnes qui contrle la forme d'une     image A  partir de 6*N rels dfinissant les N transformations affines de l'IFS.</p>     <p>Le problme inverse de la dtermination d'un IFS ayant pour attracteur une image noir     et blanc P donne, est rsolu par Demko et al. en introduisant la notion d'auto-pavage,     o l'on recouvre au mieux l'objet A avec un nombre minimum N de copies rduites de     lui-mme appeles sous-objets. Barnsley et al. proposent un algorithme visuel interactif     o l'on ralise  la main sur un cran un pavage du modle A dont on veut calculer un     IFS au moyen de N sous-objets de A. Les N w<font size="1">i</font> correspondant  ces N     sous-objets sont automatiquement calculs. Le <i>thorme de collage</i> permet alors     de dterminer l'erreur obtenue par rapport  l'image originale en fonction de la     prcision de l'ajustement obtenu dans le &quot;collage&quot; (Figure 1E).</p>     <p><img SRC="Chapitre1/Image080.gif" HSPACE="7" VSPACE="7" width="283" height="449"><img     SRC="Chapitre1/Image081.gif" width="287" height="449"></p>     <p>Figure 1E: Thorme du collage</p>     <p>Si l'on munit d'une probabilit p<font size="1">i </font>(autre que 1/N) la     transformation w<font size="1">i</font>, 1=i=N, l'IFS<i> </i>est dit<i> probabilis. </i>Il     y a deux consquences  l'introduction des probabilits dans les IFS. L'acclration     de la vitesse de rendu obtenue en choisissant p<font size="1">i</font> proportionnelle      l'aire w<font size="1">i</font>(P) de l'image produite par w<font size="1">i</font> (Ce     qui permet de gnrer par w<font size="1">i</font> un nombre de points proportionnel      l'aire de w<font size="1">i</font>(P) pour dessiner w<font size="1">i</font>(P)). Dans     l'exemple de la figure 1E' de recouvrement de l'attracteur carr, la seconde image     obtenue ainsi est meilleure ( nombre de points gal) que la premire obtenue par     quiprobabilit, puisqu'elle fournit l'image finale du carr  6 pixels prs. On a     donc obtenu une vitesse de convergence suprieure par ce choix de probabilits.</p>     <div align="center"><center><table BORDER="1" CELLSPACING="1" WIDTH="604"     bordercolordark="#006633" bordercolorlight="#339966">       <tr>         <td WIDTH="26%" VALIGN="TOP"><p ALIGN="CENTER"><img SRC="Chapitre1/Image082.gif" width="135" height="135"></td>         <td WIDTH="11%" VALIGN="TOP"><p ALIGN="JUSTIFY">p1=0.25</p>         <p ALIGN="JUSTIFY">p2=0.25</p>         <p ALIGN="JUSTIFY">p3=0.25</p>         <p ALIGN="JUSTIFY">p4=0.25</td>         <td WIDTH="26%" VALIGN="TOP"><p ALIGN="CENTER"><img SRC="Chapitre1/Image083.gif" width="104" height="101"></td>         <td WIDTH="11%" VALIGN="TOP"><p ALIGN="JUSTIFY">p1=0.25</p>         <p ALIGN="JUSTIFY">p2=0.25</p>         <p ALIGN="JUSTIFY">p3=0.10</p>         <p ALIGN="JUSTIFY">p4=0.40</td>         <td WIDTH="26%" VALIGN="TOP"><p ALIGN="CENTER"><img SRC="Chapitre1/Image084.gif" width="104" height="101"></td>       </tr>     </table>     </center></div><p>Figure 1E' : Exemple de recouvrement de l'attracteur carr avec 100 000     points calculs</p>     <p>La seconde consquence est l'introduction de la couleur que l'on constate sous forme     de tramage dans l'exemple d'un carr recouvert par quatre copies identiques de lui-mme     (colonne a = (0.5,0.5,0.5,0.5) dans l'exemple prcdent). Si l'on gnre 10 000 points     avec diffrents choix de probabilits, on obtient :<font size="1"></p>     </font><div align="center"><center><table BORDER="1" CELLSPACING="1" WIDTH="612"     bordercolordark="#006633" bordercolorlight="#339966">       <tr>         <td WIDTH="26%" VALIGN="TOP"><p ALIGN="CENTER"><img SRC="Chapitre1/Image085.gif" width="135" height="135"></td>         <td WIDTH="10%" VALIGN="TOP"><p ALIGN="CENTER">p1=0.10</p>         <p ALIGN="CENTER">p2=0.40</p>         <p ALIGN="CENTER">p3=0.10</p>         <p ALIGN="JUSTIFY">p4=0.40</td>         <td WIDTH="27%" VALIGN="TOP"><p ALIGN="CENTER"><img SRC="Chapitre1/Image086.gif" width="120" height="120"></td>         <td WIDTH="10%" VALIGN="TOP"><p ALIGN="CENTER">p1=0.10</p>         <p ALIGN="CENTER">p2=0.20</p>         <p ALIGN="CENTER">p3=0.30</p>         <p ALIGN="JUSTIFY">p4=0.40</td>         <td WIDTH="27%" VALIGN="TOP"><p ALIGN="CENTER"><img SRC="Chapitre1/Image087.gif" width="120" height="120"></td>       </tr>     </table>     </center></div><p>Dans ces deux situations, les points &quot;tombent&quot; avec     diffrentes frquences suivant les diffrents endroits donnant dans les images     ci-dessus un &quot;effet de trame&quot; ou de couleur. Les rgions les plus sombres sont     celles dans lesquelles un plus grand nombre de points sont tombs. Le nombre de points     tombant dans une rgion peut tre considr comme une densit sur cette rgion. On     associe ainsi  un IFS probabilis, une unique densit porte par l'attracteur A de     cet IFS (densit qui est l'unique mesure invariante d'un oprateur contractant dfini     sur un certain espace mtrique complet de mesures borliennes). Cette mesure assigne      tout pixel de A un nombre positif qui est interprt comme sa couleur: cette mesure est     donc une unique faon de colorier A.</p>     <p>Le problme inverse de dtermination des probabilits de l'IFS probabilis     permettant de reconstruire une image couleur donne est complexe et n'est pas trait     ici.</p>     <p><img SRC="Chapitre1/Image088.gif" WIDTH="268" HEIGHT="358"></p>     <p>Figure 1E'' : Feuille extraite de [Hu91] (2 IFS pour le limbe et le ptiole, N = 10 )</p>     <p>Une nouvelle transformation C<font size="1">B</font> peut tre ajoute  un IFS et     permet d'obliger l'attracteur de l'IFS  contenir un ensemble donn appel <i>ensemble     de condensation</i> B. Une <i>hirarchie d'IFS</i> est alors dfinie comme tant une     suite ordonne d'IFS avec ensemble de condensation, chaque ensemble de condensation     tant l'attracteur de l'IFS prcdent. L'intrt des hirarchies d'IFS avec     ensembles de condensation est qu'elles permettent de rduire le nombre de fonctions     affines ncessaires au rendu d'un paysage complexe, en rendant compte des hirarchies     topologiques entre lments vgtaux (branche -&gt; arbre -&gt; fort).</p>     <p>Un autre aspect intressant de la gnration d'images par IFS est que le caractre     fractal des images obtenues permet d'obtenir des agrandissements  toute chelle de     l'objet modlis tout en gardant le mme code en mmoire et la mme prcision de     rendu. Le calcul itratif de l'image se poursuit jusqu' l'obtention d'une image     suffisamment consistante. Les couleurs sont obtenues en rglant les probabilits P<font     size="1">i</font> et par un choix convenable de la fonction liant les caractristiques     chromatiques avec la frquence d'apparition en un pixel des points de l'attracteur dans     le procd itratif.</p>     <p>Les images obtenues reprsentent souvent des objets  forte caractristique     auto-similaire (feuilles d'rable, fougres). Dans les exemples donns (images de la     cte de Monterey, de la fort noire, d'un champ de tournesols,... (cf [BJ88]), le nombre     d'applications affines des IFS est de 160  180. Ces nombres sont rduits  environ 100     par l'utilisation de la notion de hirarchie d'IFS avec ensemble de condensation,     correspondant  la hirarchie des lments vgtaux.</p>     <b><p>1.2.3.2 Systmes de particules</b></p>     <p>Un second modle entrant dans la catgorie des mthodes fractales, permettant     d'obtenir des rsultats de type impressionniste, a t dvelopp par Reeves [Re83] et     Reeves et Blau [RB85] : il s'agit des <i>systmes de particules</i>. Par cette approche,     l'objet modlis est considr comme un flot de particules voluant dans R<font     size="1">3</font>. Une image reprsentera les trajectoires de ces particules. Si l'on     modlise le feu, les particules issues d'un foyer commun seront toutes indpendantes et     seront essentiellement des points lumineux caractriss par leur forme, couleur,     trajectoire (position et vitesse  tout instant), date de naissance et de mort .</p>     <p>Trois raisons expliquent l'intrt de ce type de modlisation :</p>     <p>- Une particule ponctuelle est la plus simple des primitives graphiques imaginable. Un     trs grand nombre pourra en tre dessin dans le mme laps de temps, des objets avec     plus de dtails pourront donc tre obtenus.</p>     <p>- Les systmes de particules sont procduraux et stochastiques : on peut minimiser le     temps pass  la modlisation car un faible nombre de paramtres initiaux permettent     d'obtenir des images trs fouilles, on dit qu'il y a un grand taux d'amplification des     donnes.</p>     <p>- Ils permettent de modliser des scnes dynamiques (feu, vent dans de l'herbe).</p>     <p><img SRC="Chapitre1/Image090.gif" HSPACE="7" VSPACE="7" width="333" height="386"></p>     <p>Figure 1F : Gomtrie selon Reeves et Blau</p>     <p>Les systmes de particules qui permettent de gnrer des images d'arbres botaniques     ou d'herbe sont structurs et donc composs de particules non indpendantes. Chaque     arbre est reprsent comme un ensemble d'artes pour les branches et de petits cercles     pour les feuilles. Les feuillus auront la forme d'ellipsodes tandis que les arbres      feuillage persistant ressembleront  des cnes (Figure 1F). De nombreuses relations     existent entre les particules modlisant un arbre car elles doivent constituer un objet     3D cohrent. Chaque type d'arbre possde son propre modle dans une base de donnes.     Ce modle est dfini par un ensemble de contraintes sur les paramtres le     caractrisant, contraintes qui dfinissent les intervalles autour d'une valeur moyenne     dans lesquels les paramtres sont choisis avec quiprobabilit et qui lient les     paramtres entre eux. Un algorithme rcursif gnre les branches  partir de     paramtres et de relations permettant de dfinir le type de branchement, la distance     entre deux sous-branches conscutives, l'angle de la branche au tronc, sa longueur et son     paisseur. Chaque branche hrite d'une grande partie des paramtres de ses parentes     (ventuellement remis  l'chelle). La rcursion est arrte quand l'paisseur de     la branche atteint une valeur minimale limite ou quand un certain niveau de profondeur est     atteint.</p>     <p>Les problmes de rendu qui se posent  Reeves et Blau sont d'un tout autre ordre que     pour les autres auteurs. En raison du caractre &quot;impressionniste&quot; du modle,     un trs grand nombre de particules devront tre gnres pour obtenir un objet     consistant.</p>     <p>Les algorithmes classiques de reprsentation en faces caches utiliss pour la     visualisation sont inoprants en raison du trop grand nombre de primitives graphiques      grer. La mthode propose est celle du peintre aprs un tri de paquets de particules     ainsi ralis (1) trier en z les arbres constituant le paysage, (2) appliquer     l'algorithme suivant sur chacun des arbres indpendamment de tous les autres. Chaque     arbre est dcompos en tranches en fonction de la distance en z, lorsqu'une particule     est gnre, elle est insre dans la tranche (paquet) correspondant  sa distance     en z moyenne. 2000 tranches sont habituellement utilises pour un arbre.</p>     <p>Par ailleurs, pour rendre les ombres portes il n'est pas non plus possible d'utiliser     un algorithme classique. Reeves et Blau proposent une mthode statistique. La lumire     illuminant chaque particule est forme de trois composantes (Figure 1F'):</p>     <p><img SRC="Chapitre1/Image091.gif" WIDTH="202" HEIGHT="149"></p>     <p>Figure 1F'' : Ombres portes</p>     <p><img SRC="Chapitre1/Image092.gif" width="296" height="312"></p>     <p>Figure 1F' : Distances dans un arbre</p>     <p>- une composante D de lumire diffuse exponentiellement dcroissante de la distance d<font     size="1">d</font> dans l'arbre  la source lumineuse (D = e<font size="1">-add</font>),</p>     <p>- une composante A de lumire ambiante exponentiellement croissante de la distance     horizontale d<font size="1">a</font> de la particule au bord extrieur de l'arbre et     minore par une valeur minimale d'clairage ambiant A<font size="1">min</font> (A =     max(e<font size="1">-bda</font>,A<font size="1">min</font>)),</p>     <p>- une composante S de lumire spculaire pour les particules de distance d<font     size="1">d</font> faible et dont la branche associe est perpendiculaire  la direction     d'incidence des rayons lumineux.</p>     <p>Enfin l'ombre porte d'un arbre sur un autre arbre est gre en considrant que les     composantes diffuse et spculaire n'existent qu'au dessus du plan figur sur la figure     1F''. En dessous de ce plan, elles sont de moins en moins prises en compte jusqu' tre     totalement ignores. Les rsultats obtenus sont tout  fait ralistes avec un luxe de     dtails ponctuels propres aux systmes de particules. La ralisation de clairires est     un exemple frappant de la qualit des rsultats obtenus par gestion statistique de     l'clairage et des ombres portes. Les temps de calcul et d'affichage annoncs sont en     contrepartie de plusieurs heures en raison de l'importance des calculs.</p>     <p>Cette technique se caractrise enfin par une aptitude particulire  modliser des     squences animes, en particulier les systmes de particules ont t utiliss pour     la ralisation d'une spectaculaire squence d'effets spciaux du film de cinma     &quot;Star Trek II, la colre de Kahn&quot; o l'on voit un mur de feu recouvrir une     plante. L'aspect dynamique de la modlisation par des particules mobiles rend     intrinsque le mouvement dans des scnes changeantes au cours du temps.</p>     <b><p>1.2.4 Modles combinatoires</b> </p>     <p><b>1.2.4.1</b> De tels modles sont prsents dans Eyrolles, Franon et Viennot     [EF86], Eyrolles [Ey86] et Viennot, Eyrolles, Janey et Arqus [VE89a] [VE89b] [VJ90], qui     seront dcrit dans le chapitre 3 (non dtaill ici). Il permet la gnration     d'arborescences ressemblant  des arbres botaniques  partir d'un processus utilisant     des paramtres  caractre purement combinatoire.</p>     <p><b>1.2.4.2</b> La modlisation des feuilles vgtales a t aborde par Lienhardt     [Li87] et Lienhardt et Franon [LF87] par une approche combinatoire. Ils se basent sur     l'utilisation de connaissances botaniques appliques  un modle o la topologie prime     sur la gomtrie pour simuler une volution des feuilles au cours du temps.</p>     <p><img SRC="Chapitre1/Image094.gif" width="318" height="233"></p>     <p>Figure 1G : Une feuille</p>     <p>Le modle est bas sur la constatation que le <i>limbe</i> d'une feuille forme une     surface s'appuyant sur des <i>nervures</i> constituant elles-mme un <i>arbre enracin </i>(Figure     1G). Le dveloppement de l'architecture des nervures au cours du temps est assez proche     de celui des axes d'un arbre. Les notions propres aux axes des arbres (ramification,     mortalit, rythme, ... voir plus loin) peuvent tre tendues aux nervures d'une     feuille.</p>     <p>Le modle topologique d'une feuille est un <i>graphe modulaire</i> comprenant :</p>     <p>-&nbsp;deux types d'artes : des <i>artes de</i> <i>croissance</i> et des <i>artes     de</i> <i>rsistance</i>,</p>     <p>-&nbsp;deux types de sommets : des <i>sommets de croissance</i> (incidents  au moins     une arte de croissance) et des <i>sommets de</i> <i>rsistance</i> (incidents  aucune     arte de croissance),</p>     <p>-&nbsp;deux types de faces : des <i>faces</i> d'<i>activit</i> (incidentes  au     moins une arte de croissance) et des <i>faces</i> <i>frontires </i>(incidentes      aucune arte de croissance).</p>     <p>Les sommets et artes de croissance symbolisent la nervation de la feuille. Le     sous-graphe modulaire restreint  ces seuls sommets et artes est un arbre appel <i>arbre     de croissance</i> (Figure 1G'). A ce titre les artes de croissance sont donc orientes.</p>     <p><img SRC="Chapitre1/Image095.gif" WIDTH="206" HEIGHT="142"></p>     <p>Figure 1G' : Arbre de croissance</p>     <p><img SRC="Chapitre1/Image096.gif" WIDTH="257" HEIGHT="145"></p>     <p>Figure 1G'' : Deux types de modules lmentaires</p>     <p>Un graphe modulaire est planaire. Il est construit  partir des deux modules     lmentaires (Figure 1G'') existants dfinis par deux faces triangulaires ayant une     arte de croissance en commun, les autres artes et sommets tant de rsistance.</p>     <p><img SRC="Chapitre1/Image097.gif" WIDTH="219" HEIGHT="105"></p>     <p>Figure 1H : ramification</p>     <p><img SRC="Chapitre1/Image098.gif" WIDTH="269" HEIGHT="74"></p>     <p>Figure 1H' : Cration de face frontire par fusion</p>     <p>Une feuille est obtenue par simulation discrte de son dveloppement au moyen     d'oprations topologiques appliques au seuls lments de croissance. Deux des     principales oprations sont (Figures 1H et 1H'):</p>     <p>- la <i>ramification</i>, o l'on voit la cration  partir d'un sommet de     croissance, d'une nouvelle arte de croissance et du module lmentaire correspondant     (plusieurs rsultats possibles),</p>     <p>- la <i>fusion</i> ou la <i>disjonction</i> qui entranent la cration ou la     suppression de faces frontires, l'allongement ou le raccourcissement de faces     frontires.</p>     <p>L'enchanement des oprations topologiques de gnration d'une feuille est     ralise au moyen de <i>fonctions de dveloppement</i> qui permettent de dfinir,     squencer et caractriser les oprations applicables  une feuille. Ces fonctions,     appliques  tout lment de croissance au cours de la gnration, font intervenir     l'horloge t, la date de cration de l'lment de croissance sur lequel porte la     fonction, l'<i>intensit</i> de l'lment de croissance (ordre entier associ  tout     arte de croissance), les distances entre cet lment et ses lments ascendants     (paramtres voisins des notions d'ge, d'ordre, de dimension du modle botanique de de     Reffye).</p>     <p>Pour le calcul de la gomtrie et le rendu, un certain nombre de fonctions de     complment dfinissent les aspects non topologiques de la feuille tels que les longueur,     diamtre et angles 3D entre les artes de croissance filles d'un sommet, ou les     caractristiques chromatiques.</p>     <p>Ce modle permet de gnrer des feuilles d'une grande diversit de formes. Un     aspect intressant est que, par non remplissage des faces frontires, on peut obtenir     des feuilles &quot;troues&quot;. Le temps de calcul d'une feuille varie de quelques     secondes  plusieurs minutes, pour obtenir des graphes de quelques centaines  plusieurs     milliers de facettes triangulaires.</p>     <b><p>1.2.5 Modles  base de rcriture</p>     <p>1.2.5.1 L-Systmes</b></p>     <p>Les mthodes bases sur les <i>L-Systmes</i> (grammaires de rcriture     parallle) permettent de simuler au niveau topologique la croissance botanique des     arbres, voir par exemple Smith [Sm84], Prusinkiewicz [Pr86], Prusinkiewicz, Lindenmayer et     Hanan [PL88], Prusinkiewicz et Hanan [PH89] et Prusinkiewicz et Lindenmayer [PL90].</p>     <p><img SRC="Chapitre1/Image104.gif" width="440" height="440"></p>     <p>Figure 1I : Arbre axial selon Prusinkiewicz</p>     <p>Cette modlisation topologique est fonde sur la notion d'<i>arbre axial </i>(Figure     1I):</p>     <p>- A chaque n&#156;ud on distingue au plus une arte fille appele <i>arte     principale</i>, les autres artes issues de ce n&#156;ud tant appeles <i>artes     latrales</i>.</p>     <p>- Un <i>axe</i> est une sous-suite maximale d'artes commenant par l'arte issue de     la racine ou bien par une arte latrale, et continuant par une sous-suite maximale     d'artes principales .</p>     <p>-&nbsp;Le sommet terminal de l'axe issu de la racine est appel <i>sommet de l'arbre</i>.</p>     <p>- Une <i>branche</i> est l'ensemble constitu d'un axe et de tous ses axes descendants     dans l'arbre. Une branche est elle-mme un arbre axial .</p>     <p>Des ordres  valeurs numriques sont attribus aux axes et par la mme aux artes     :</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image105.gif" width="484" height="708"></font></p>     <font FACE="HELVETICA"><p></font>Figure 1I' : Codage d'un arbre</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image101.gif" width="527" height="231"></font></p>     <font FACE="HELVETICA"><p></font>Figure 1J : Rgle de production et application de cette     rgle  l'arte tiquete S d'un arbre axial</p>     <p>- L'axe dont l'arte racine est la racine de l'arbre a l'ordre 0.</p>     <p>- Les axes d'ordre i commencent par une premire arte latrale issue d'un axe     d'ordre i-1.</p>     <p>Une mthode simple de reprsentation d'un arbre axial dont les artes sont     tiquetes par les lettres d'un alphabet V consiste  le coder au moyen d'un mot sur     l'alphabet V&nbsp;U {[,]}, o les crochets [ et ] codent les branches, selon l'exemple de     la figure 1I&#146; qui dcrit la construction du codage d&#146;un arbre.</p>     <p>La croissance topologique dans ce modle est alors guide par la <i>rcriture     parallle</i> de toutes les artes tiquetes de l'arbre axial courant selon le <i>systme     de rcriture</i> appel <i>arbre-0L-System</i> dfini comme le triplet (V,w,P) o :</p>     <p>- V est un alphabet,</p>     <p>- w est un mot de V appel axiome reprsentant un arbre axial,</p>     <p>- P est un ensemble de rgles de production associant  chaque lettre de l'alphabet V     un arbre axial, selon l'exemple de la figure 1J.</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image065.gif" width="680" height="314"></font></p>     <font FACE="HELVETICA" SIZE="2"><p></font>Figure 1J' : Evolution d'un arbre selon un     arbre-0L-systme</p>     <font FACE="HELVETICA"><p></font>La gnration de l'arbre s'effectue par un processus     itratif dbutant par l'axiome w, et remplaant  chaque itration simultanment     chaque arte tiquete de l'arbre par l'arbre axial correspondant  la <i>rgle de     production</i> trouve dans P associe  son tiquette, les deux sommets de l'arte     tant remplacs par les deux sommets extrmits (racine et sommet de l'arbre) de l'axe     d'ordre 0 de l'arbre axial que l'on substitue  l'arte (Figure 1J').</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image103.gif" width="674" height="608"></font></p>     <font FACE="HELVETICA"><p></font>Figure 1J'' : Contexte BC &lt; S &gt; G[H]M et exemple     d'apparition dans un arbre axial</p>     <font FACE="HELVETICA"><p></font>Une grande influence est donne  la topologie par     paramtrage des rgles de rcriture. Dans les exemples prcdents, celles     prsentes sont <i>indpendantes du contexte</i>, constitu par les artes situes     en amont (contexte  gauche) et en aval (contexte  droite) de l'arte tudie.     Prcisment, on appelle <i>contexte gauche</i> CG d'une arte S de l'arbre toute suite     d'artes anctres de S dans l'arbre et aboutissant en S, et on appelle <i>contexte droit</i>     CD de S, tout arbre axial issu en aval de l'extrmit finale de S (Figure 1J''). On note     alors CG&lt;S&gt;CD ----&gt; T une rgle de production s'appliquant  l'arte     tiquete S et remplaant S par l'arbre axial T dans le contexte considr.     L'utilisation de rgles dpendant du contexte permet la simulation de phnomnes tels     que la propagation temporelle d'informations de la racine de l'arbre vers les feuilles (<i>propagation     acroptale</i>) ou des feuilles vers la racine (<i>propagation basiptale</i>) (Figure     1K) ou l'volution du type des n&#156;uds (un n&#156;ud peut d'abord donner des feuilles     puis ensuite des fleurs).</p>     <p><font FACE="HELVETICA"><img SRC="Chapitre1/Image102.gif" width="680" height="243"></font></p>     <font FACE="HELVETICA" SIZE="2"><p ALIGN="JUSTIFY"></font>Figure 1K : Signal de     propagation acroptale et basiptale</p>     <font FACE="HELVETICA"><p></font>La modlisation gomtrique est effectue au cours     d'une seconde passe appele &quot;<i>interprtation</i>&quot;, aprs la cration du     mot dcrivant la topologie de l'arbre.</p>     <p>Chez Smith, les branches et les feuilles sont modlises par des lignes et des     disques en 2D et par des cylindres et des sphres en 3D. Smith ne dcrit pas     prcisment les lois gomtriques employes, en particulier pour le calcul des angles     d'orientation. Il signale seulement la possibilit offerte par le logiciel Gene de     dfinir un ensemble d'angles, en soulignant que l'utilisation de variables alatoires     n'est pas ncessaire pour obtenir de beaux rsultats.</p>     <p><img SRC="Chapitre1/Image106.gif" width="228" height="357"></p>     <p>Nombre de gnrations = 4, d = 22.5, V = {F}, F -&gt; FF-[-F+F+F]+[+F-F-F]</p>     <p>Figure 1L : Arbre gnr par arbre-0L-systme avec une gomtrie 2D</p>     <p>En revanche, Prusinkiewicz et al. abordent le problme du calcul d'une gomtrie     applique  un mot gnr par un L-system beaucoup plus finement que Smith. La     gomtrie est construite au moyen d'une tortue de type LOGO qui interprte le mot     cr par le L-Systme sous forme d'instructions  caractre gomtrique. En 2D,     certaines lettres du langage (+, -) indiquent des dviations positives ou ngatives d'un     angle d par rapport  l'axe de la tortue (Figure 1L). Les tiquettes associes aux     artes de l'arbre codent le dplacement de la tortue sur une longueur d. En 3D un     repre </p>     <p>Les symboles [ et ] permettent la gestion d'une pile d'tats de la tortue pour les     retours d'interprtation de branches aux n&#156;uds d'embranchement. D'autres symboles     peuvent encore tre ajouts pour contrler la couleur, le diamtre et la longueur des     segments, pour incorporer et remplir des surfaces (feuilles),...</p>     <p>En ce qui concerne le rendu, Prusinkiewicz et al. franchissent un grand pas vers le     ralisme. L'utilisation des feuilles modlises directement par L-systme     gomtrique et d'une modlisation volumique des branches rend les dessins beaucoup plus     ralistes. L'utilisation de L-Systmes stochastiques permet d'introduire de la varit     dans les vgtaux dessins.</p>     <b><p>1.2.5.2 Grammaires d'arbres</b></p>     <p>Une autre approche, dveloppe par Shao [Sh92], consiste  gnrer des <i>arbres     enracins</i> par utilisation de systmes de rgles de rcriture parallles     (remplaant les sommets par des arbres) appels <i>grammaires d'arbres</i>. Ces travaux     se distinguent de ceux de Prusinkiewicz sur le point particulier que la rcriture est     effectue par remplacement par des arbres de sommets et non pas seulement d'artes. Des     extensions sont proposes par introduction de contexte de suppression d'arbre et de choix     stochastique des rgles employes.</p>     <p>Les paramtres gomtriques mis en &#156;uvre sont classiques. Ils font intervenir     des longueurs d'artes et des angles de branchement fonction des ordres. L'arbre est     modlis par des segments pour les artes et des sphres pour les sommets. Une forme     3D est considre comme limite d'une arborescence voluant en 3D justifiant ainsi     l'emploi de sphres pour les sommets. Cette ide gnralise en 3D celle dveloppe     par Oppenheimer, faisant apparatre une feuille comme la limite fractale de     l'arborescence de ses nervures. Le rendu est ralis au moyen d'algorithmes classiques     (Z-Buffer, illumination calcule au moyen de la normale) amliors pour le rendu de     surfaces modlises par des sphres.</p>     <p>Ces travaux sont prsents par dcomposition en trois noyaux logiciels de manire      bien faire apparatre la disjonction entre les aspects topologiques, gomtriques et     infographiques. Le paramtrage des lois permet d'obtenir des objets fractals, mais aussi     des objets ressemblant  des arbres botaniques (brocoli, choux fleur par exemple).</p>     <b><p>1.2.6 Modles botaniques</b></p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image107.gif" width="434" height="924"></font></p>     <font FACE="HELVETICA"><p></font>Figure 1M : Dfinitions</p>     <font FACE="HELVETICA"><p></font>Le modle botanique de de Reffye, Edelin, Franon,     Jaeger, Puech [RE88], Jaeger [Ja87] simule la croissance de vgtaux au moyen de rgles     purement botaniques extraites d'analyses empiriques ralises sur le terrain. Ils     permettent ainsi l'obtention thorique de toute espce existant dans la nature.</p>     <p>L'lment fondamental de l'architecture d'un arbre est l'<i>axe</i>. La <i>croissance</i>     de tout axe rsulte de l'activit du bourgeon situ  son extrmit, bourgeon     appel <i>bourgeon apical.</i> Un axe est constitu d'un ensemble d'<i>intern&#156;uds </i>crs     les uns aprs les autres. Entre deux intern&#156;uds existe un n&#156;ud qui donne     naissance  des feuilles et  des <i>bourgeons latraux</i>. La naissance d'un axe      partir d'un bourgeon latral est appele <i>ramification</i>. A une unit prs, on     dfinit sur les arbres botaniques la mme notion d'ordre attribu au axes et aux     n&#156;uds que sur les arbres gnrs par arbres-L-systmes par Prusinkiewicz et al.     (voir ci-dessus). L'<i>axe d'ordre 1</i> est l'axe associ au n&#156;ud racine. Un <i>axe     d'ordre k</i> prend naissance sur un bourgeon latral d'un axe d'ordre k-1 (Figure 1M).</p>     <p>La <i>ramification</i> au niveau des bourgeons latraux s'effectue selon plusieurs     modes :</p>     <p>- <i>ramification continue</i> : tout bourgeon latral d'un axe donne naissance  un     nouvel axe,</p>     <p>- <i>ramification rythmique</i> : seuls certains bourgeons latraux rpartis     rgulirement donnent naissance  un nouvel axe,</p>     <p>- <i>ramification diffuse</i> : seuls certains bourgeons latraux rpartis     alatoirement donnent naissance  un nouvel axe.</p>     <p>Le modes de ramification latrale et de croissance apicale de chaque axe sont     fonctions de l'ordre de l'axe considr suivant les espces modlises.</p>     <p><img SRC="Chapitre1/Image108.gif" width="74" height="342"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img     SRC="Chapitre1/Image109.gif" width="242" height="333"></p>     <p>Orthotropie &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Plagiotropie</p>     <p>Figure 1M' : Tendances de croissance</p>     <p>Au niveau gomtrique les axes adoptent gnralement une tendance <i>orthotropique</i>     (croissance des axes en direction verticale) ou <i>plagiotropique</i> (croissance des axes     en direction horizontale) (Figure 1M').</p>     <p>Un arbre <i>monopodial d'ordre k</i> est un arbre possdant un seul axe d'ordre 1 et     un nombre fini d'axes d'ordre compris entre 1 et k. La croissance des axes peut ne pas     tre uniquement monopodiale, en particulier si un bourgeon apical meurt (mort naturelle     ou taille de l'axe), il peut y avoir <i>ritration</i> et cration  partir de     bourgeons latraux de nouveaux axes  la place de ce n&#156;ud. On dit qu'on a alors une     croissance <i>sympodiale.</i></p>     <p>Croissance sympodiale orthotropique</p>     <p>Ramification continue</p>     <p>Figure 1N: Modle de Leeuwenberg</p>     <p>Croissance monopodiale orthotropique sur l'axe d'ordre 1 et plagiotropique sur les     autres</p>     <p>Ramification rythmique</p>     <p>Figure 1N' : Modle de Massart</p>     <font FACE="HELVETICA"><p></font>Hall, Oldeman et Tomlinson [HO78] ont recens 23     modles architecturaux pour les arbres des forts tropicales (exemples aux figures 1N et     1N'). Leur classification est principalement bases sur :</p>     <p>- la prsence ou l'absence de croissance sympodiale,</p>     <p>- le type de ramification,</p>     <p>- la croissance continue ou non,</p>     <p>- la tendance plagiotropique ou orthotropique.</p>     <p>De Reffye et al. modlisent l'volution d'un arbre par un processus de croissance     discret bas sur l'activit des bourgeons et faisant intervenir la croissance, la     ramification et la mort de ces bourgeons.</p>     <p>La croissance de l'arbre est rythme par les tops d'une horloge. Chaque axe de l'arbre     croit d'une <i>unit de croissance</i> (squence d'intern&#156;uds) entre chaque top     d'horloge. La dure entre deux tops d'horloge est suppose constante pour tous les axes     de mme ordre, ce qui implique que la croissance peut tre plus ou moins rapide suivant     les axes.</p>     <p>Deux probabilits sont attribues  chaque bourgeon (Figure 1O) :</p>     <p>- une <i>probabilit de mort</i> (pour un bourgeon latral cette probabilit est la     probabilit de non ramification),</p>     <p>- une <i>probabilit de pause</i>.</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image110.gif" width="672" height="240"></font></p>     <font FACE="HELVETICA" SIZE="1"><p></font>Pmort = Ppause = 0</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image111.gif" width="624" height="290"></font></p>     <font FACE="HELVETICA" SIZE="1"><p></font>Pmort = 0</p>     <p>Ppause = 0 sur l'axe 1, sinon Ppause grande</p>     <font FACE="HELVETICA"><p></font>Figure 1O : Croissances topologiques</p>     <font FACE="HELVETICA"><p></font>Pour une espce particulire, des probabilits ne sont     fonction que de l'<i>ge</i> (date de naissance suivant l'horloge), la <i>dimension</i>     (dure entre la naissance d'un bourgeon et la naissance de l'axe qui le porte) et l'ordre     du bourgeon considr.</p>     <p>La gnration d'un arbre demande la connaissance d'un certain nombre d'autres     paramtres : l'ge de l'arbre que l'on veut gnrer, les <i>vitesses de croissance</i>     des axes (en fonction de l'ordre), le nombre de bourgeons  chaque n&#156;ud (en fonction     de l'ordre), la probabilit de ritration sur un bourgeon (fonction des mmes     paramtres que les probabilits prcdentes).</p>     <p>L'algorithme suivant dcrit de manire trs simplifie la gnration de l'arbre :</p>     <pre><font face="Courier">Pour chaque bourgeon b  chaque top horloge faire 	Si b ne meurt pas alors 		Si b n'entre pas en pause alors 			cration d'un intern&#156;ud 			cration d'un bourgeon apical 			Si b se ramifie alors 				cration de bourgeons latraux 			Finsi 		Finsi 	Finsi Finpour</font>          </pre>     <p>Dans la pratique, pour des raisons d'implantation mmoire, l'arbre est gnr      partir de l'utilisation d'une pile de bourgeons, sans conservation globale de la     structure. La gnration d'arbres de plusieurs centaines de milliers de n&#156;uds est     ainsi possible, mais la simulation de la croissance est rendue plus difficile car un arbre     entier doit tre gnr pour chaque tape de l'volution.</p>     <p>Au niveau gomtrique, la portion de branche correspondant  un intern&#156;ud est     modlise par un cylindre ou un cne. Les longueurs et diamtres des intern&#156;uds     sont des fonctions de l'ordre, de l'ge et de la dimension. Les angles d'insertion (a sur     la figure 1M') et de phyllotaxie (angle d'une feuille ou d'une branche dans le plan     perpendiculaire  l'axe de la branche la portant) sur les axes sont des variables     alatoires fonctions de ces mmes paramtres. Il peut aussi tre tenu compte de la     pesanteur et de la flexibilit des branches (calcul de rsistance des matriaux).</p>     <p>Le rsultat de l'excution du gnrateur de plantes est un fichier de composantes     botaniques qui peuvent tre des intern&#156;uds, des feuilles, des fleurs, des fruits,...     ainsi que les informations gomtriques ncessaires  leur placement dans l'espace. A     chacun de ces lments correspond une primitive graphique dans une bibliothque de     formes, par exemple un cylindre hexagonal ou un cne tronqu pour un intern&#156;ud ou     bien des polygones pour les feuilles. Cette librairie peut tre paramtre en fonction     de l'ge de l'arbre. La qualit de la visualisation (qui est trs bonne) ne semble pas     tributaire de l'utilisation de formes complexes (prismes  6 faces latrales, feuilles     composes de 4 facettes), ni de techniques infographiques complexes (facettes     monochromes, Z-buffer pour l'affichage, pas d'anti-aliasing, ni de plaquage de texture).</p>     <p>Du point de vue de l'utilisateur, le nombre de paramtres  fournir pour gnrer un     arbre crot rapidement avec la complexit de l'arbre  modliser (quelques dizaines     pour un petit arbre, plusieurs centaines pour un arbre important). Les temps de calcul et     d'affichage suivent le mme processus (de quelques minutes  plusieurs dizaines de     minutes).</p>     <b><p>1.2.7 Modles environnementaux</p>     <p>1.2.7.1 Modle volutionniste</b></p>     <p>Le modle environnemental de Niklas [Ni86] analyse en fonction de paramtres     gomtriques, la forme des arborescences selon des critres tels que l'adaptation  la     captation de la lumire ou  la rsistance  la pesanteur, de manire      caractriser l'volution de la forme des arbres au cours des quelques dizaines de     millions d'annes ayant suivis leur apparition sur Terre. Son raisonnement se base sur     l'affirmation que les arbres sont des solutions structurelles au problme biochimique de     la photosynthse. C'est  dire que les plantes dont la forme leur permet le mieux de     capter la lumire auront plus de chances de survie que les autres. En consquence     l'volution d'une espce aura tendance  renforcer ce caractre par slection     naturelle. Une hypothse  caractre structurelle doit aussi tre vrifie, pour     supporter des contraintes mcaniques et donc ne pas s'crouler sur elle-mme, une     plante doit pousser verticalement.</p>     <p>La modlisation de Niklas repose sur l'utilisation d'arbres binaires engendrs par un     processus itratif o  chaque tape une certaine proportion de n&#156;uds terminaux     se ramifient.</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image112.gif" width="364" height="442"></font></p>     <font FACE="HELVETICA"><p></font>Fig 1P : Gomtrie selon Niklas</p>     <p>La gomtrie de l'arbre est calcule  partir de deux angles, l'angle de     branchement constant qui dtermine l'angle entre les deux artes filles d'un n&#156;ud,     et l'angle de rotation qui dtermine la valeur de la rotation entre le plan form par     les artes filles d'un n&#156;ud n et le plan form par l'arte mre de n et son     arte s&#156;ur, angle calcul alatoirement dans un intervalle donn (Figure 1P). La     manire avec laquelle l'angle de branchement est rparti entre les deux artes filles     n'est pas indique, les images proposes laissent supposer qu'il peut tre allou soit     quitablement, soit entirement  l'une des deux branches filles. La longueur des     artes semble tre constante dans l'ensemble de l'arborescence. Ces arbres sont     simplement dessins en fil de fer, le but de Niklas n'tant pas l'obtention d'images     photoralistes.</p>     <b><p>1.2.7.2 Modlisation dans l'espace des voxels</b></p>     <p>Le modle de Greene [Gr89] ralise la croissance d'une l'arborescence botanique dans     un espace subdivis en un ensemble de cubes identiques appels <i>voxel</i> (<i>Voxel     Space</i>) en fonction de contraintes environnementales telles que l'ensoleillement ou la     prsence d'obstacles physiques.</p>     <p>Greene utilise des arbres binaires engendrs par un processus stochastique dont l'un     des moyens de contrle est un retour de la gomtrie sur la topologie avec pour     consquence une limitation de leur volution. Cet arbre ne semble pas cod     explicitement au cours de la modlisation. Le modle gomtrique conu par Greene est     grandement influenc par les particularits de l'espace de travail utilis: un espace     Voxel est l'quivalent en trois dimensions d'une image bitmap en deux dimensions. Un     objet (ligne, polygone, polydre) sera reprsent comme un ensemble de voxels occups.     L'environnement proche d'un objet tant alors form des couches successives de voxels     voisins de ceux occups par l'objet.</p>     <p>L'intrt de l'utilisation d'un espace discret dans le cadre de la modlisation 3D,     est que certaines manipulations sont grandement facilites par rapport  des espaces     plus classiques (euclidiens). On citera le test d'intersection (par test d'occupation de     tous les voxels), le test de proximit ( l'aide des couches successives de voxels     voisins) ou la mesure de la distance entre deux objets complexes. Les oprations     effectues dans un espace voxel sont forcment approximes en raison du caractre     discret inhrent  l'espace, mais les avantages en vitesse et en facilit de travail     peuvent tre dterminants. Ceci est le cas pour la ralisation d'automates de     croissance sensitifs  l'environnement (les obstacles doivent tre vits, la     proximit de certains objets peut inhiber ou favoriser la croissance, l'volution est     module par la lumire).</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image113.gif" width="377" height="547"></font></p>     <p><font FACE="HELVETICA"><img SRC="Chapitre1/Image114.gif" width="377" height="547"></font></p>     <font FACE="HELVETICA"><p></font>Figure 1Q : Retour de la gomtrie sur la topologie     pour la croissance</p>     <font FACE="HELVETICA"><p></font>L'algorithme de croissance utilis par Greene consiste     dans un premier temps,  initialiser l'espace voxel,  dfinir ensuite des points     sources, et enfin,  partir de ces points  gnrer des lments gomtriques (des     branches) selon un ensemble de contraintes. Ces contraintes sont de deux types, soit     gomtriques pures comme la longueur et l'paisseur des artes ou les valeurs des     angles de branchement (utilisation de variables alatoires), soit environnementales qui     sont de deux types :</p>     <p>-&nbsp;non intersection et non proximit avec les objets dj existants,</p>     <p>-&nbsp;illumination suffisante pour qu'un n&#156;ud puisse voluer.</p>     <p>Des tentatives de gnration sont effectues jusqu' trouver une position     acceptable dans la limite d'un nombre d'essais maximum donn (voir la figure 1Q gauche     o les essais infructueux (ventails) marquent les arrts dans les ramifications).</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image133.gif" width="480" height="328"></font></p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image134.gif" width="472" height="333"></font></p>     <font FACE="HELVETICA"><p></font>Figure 1Q': Calcul de l'illumination du soleil et de     l'illumination ambiante</p>     <font FACE="HELVETICA"><p></font>Le calcul de l'illumination tire partie des     spcificits de l'espace voxel. L'illumination d'un voxel est la somme de deux valeurs,     une illumination venant du ciel entier et une illumination venant du soleil tout au long     de sa course quotidienne. Il est simple de vrifier si un rayon (un segment de droite)     coupe l'un des objets prsents dans l'espace voxel. L'illumination du ciel sera la     proportion de rayons non intercepts par un voxel dj occup venant de la     demi-sphre cleste et allant vers le voxel test (test sur 100 rayons rpartis avec     homognit sur la sphre cleste), l'illumination du soleil sera la proportion de     rayons non intercepts venant du soleil (test sur 100 rayons rpartis sur l'arc     semi-circulaire matrialisant la course du soleil dans le ciel) (Figure 1Q').</p>     <p>Les images prsentes par Greene ont t obtenues par des techniques classiques de     rendu par facettes. La gestion des couleurs attribues  ces facettes s'effectue par     codage direct au niveau des voxels. La taille de l'espace voxel est comprise entre     150x150x150 et 300x300x300, il y a donc entre 3 et 27 millions de voxels. Logiquement, le     temps de construction des arborescences crot proportionnellement avec le nombre de     voxels dans l'espace, les temps signals sont d'environ 30 heures de calcul.</p>     <p>Le dessin d'une image peut reprsenter la gestion de plusieurs centaines de milliers     de facettes, mais les rsultats obtenus sont trs ralistes. La gnration de     l'arborescence s'accompagne de la gnration de feuilles polygonales. La gestion des     btiments  la base mme de la mthode apporte un grand avantage par rapport  toutes     les autres techniques pour la ralisation de paysages composites. Un problme reste     toutefois les exigences matrielles lies  la gestion d'un espace Voxel.</p>     <p>Un autre travail utilisant une modlisation dans un espace Voxel est celui de Blaise     [Bl91] qui  partir du modle de croissance de de Reffye et Jaeger ([RE88], [Ja87])     permet la simulation de contraintes d&#146;ensoleillement ou de contraintes gomtriques     (lors de l&#146;volution d&#146;une branche, la prsence de btiments, d&#146;autres     arbres ou d&#146;autres branches du mme arbre peut inhiber la croissance).</p>     <b><p>1.2.8 Classification croise</b></p>     <p>Un grand nombre de ces travaux sous-tendent la dcomposition de l'arbre en deux     structures complmentaires. La structure topologique matrialisera l'organisation     interne des branches d'un arbre  l'exclusion de toute considration gomtrique. La     structure gomtrique inclura toutes les informations gomtriques concernant l'arbre     (positions des n&#156;uds, paisseur des branches,...).</p>     <p>Dans les paragraphes suivants nous prsentons ces travaux selon une classification     transversale en fonction des trois aspects :</p>     <p>- <i>Topologie</i> : La structure topologique d'un arbre reprsente son architecture     interne et exclut tout caractre gomtrique. Quand elle existe, elle est reprsente     par un objet mathmatique (mot,&#133;).</p>     <p>- <i>Gomtrie</i> : Elle consiste en le plongement de l'arbre topologique dans le     plan ou dans l'espace.</p>     <p>- <i>Rendu</i> : Il traite du type de rendu obtenu et donc de toutes les techniques     infographiques utilises pour arriver  ce rendu (limination des parties caches,     plaquage de texture).</p>     <p>Cette dcomposition est classique en modlisation et en informatique graphique, elle     est employe dans les travaux prsents dans les chapitres suivants pour la     modlisation et le dessin d'arbres botaniques et de reliefs montagneux.</p>     <b><p>1.2.8.1 La topologie</b></p>     <p>La topologie va tre ici vue sous deux aspects :</p>     <p>-&nbsp;Est-elle ou n'est-elle pas prsente dans le modle?</p>     <p>-&nbsp;Est-elle ou n'est-elle pas utilise pour paramtrer la forme finale de l'arbre     obtenue par ce modle?</p>     <table BORDER="1" CELLSPACING="1" WIDTH="673" bordercolordark="#006633"     bordercolorlight="#339966">       <tr>         <td WIDTH="402" VALIGN="TOP">&nbsp;</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Type de topologie</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Influence</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Honda [Hon71]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Non dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Aono &amp; Kunii [AK84]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Non dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Kawaguchi [Ka82]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Implicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Non dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Bloomenthal [BL85]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Non dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Oppenheimer [Op86]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Non dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Demko, Hodges &amp; Naylor [DH85]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Inexistante</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">-</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Barnsley, Jacquin, Malassenet, Reuter &amp;         Sloan [BJ88]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Inexistante</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">-</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Reeves et Blau [RB85]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Embryonnaire</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">-</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Arqus, Janey, Viennot &amp; Eyrolles         [VE89] [AJ90] [AJ91]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Lienhardt &amp; Franon [Li87] [LF87]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Smith [Sm84]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Prusinkiewicz, Lindenmayer &amp; Hanan         [PL88]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">de Reffye, Edelin, Franon, Jaeger &amp;         Puech [RE88]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Niklas [Ni86]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Explicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Non dominante</td>       </tr>       <tr>         <td WIDTH="402" VALIGN="TOP"><p ALIGN="CENTER">Greene [Gr89]</td>         <td WIDTH="138" VALIGN="TOP"><p ALIGN="CENTER">Implicite</td>         <td WIDTH="115" VALIGN="TOP"><p ALIGN="CENTER">Non dominante</td>       </tr>     </table>     <b><font FACE="HELVETICA"><p></font>1.2.8.2 La gomtrie</b></p>     <p>Le classement des mthodes gomtriques va tre effectu en fonction du type de     modlisation, c'est  dire, &quot;quel espace de travail a t employ?&quot; et     &quot;dans cet espace quelles sont les primitives utilises?&quot;. On trouve en effet     des mthodes relativement classiques modlisant les objets dans un espace euclidien      partir d'angles d'embranchement, de longueurs et d'paisseurs attribus aux artes, au     moyen de primitives comme des lignes, des cylindres,..., mais aussi des mthodes beaucoup     moins classiques tant pour l'espace de travail que pour les primitives utilises sur cet     espace.</p>     <table BORDER="1" CELLSPACING="1" WIDTH="679" bordercolordark="#006633"     bordercolorlight="#339966">       <tr>         <td WIDTH="257" VALIGN="TOP">&nbsp;</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Type de gomtrie</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Modlisation des objets</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Fractal</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Honda [Hon71]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Segments</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Aono &amp; Kunii [AK84]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Segments avec paisseur</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Kawaguchi [Ka82]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Cylindres</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Oui</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Bloomenthal [BL85]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Cylindres gnraliss d'axes des         B-Splines et polygones</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Oppenheimer [Op86]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Cylindres, spirales, hlices et tortillons</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Oui</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Demko, Hodges &amp; Naylor [DH85]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Espace mtrique 2D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Points</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Oui</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Barnsley, Jacquin, Malassenet, Reuter &amp;         Sloan [BJ88]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Espace mtrique 2D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Points</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Oui</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Reeves et Blau [RB85]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Espace mtrique 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Points et Segments</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Arqus, Janey, Viennot &amp; Eyrolles         [VE89] [AJ90] [AJ91]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 2D ou 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Polygones en 2D ou cnes courbe en 3D</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Lienhardt &amp; Franon [Li87] [LF87]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Polygones</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Possible</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Smith [Sm84]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 2D ou 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Segments et disques en 2D ou cylindres et         sphres en 3D</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Prusinkiewicz, Lindenmayer &amp; Hanan         [PL88]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Cylindres et polygones</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">de Reffye, Edelin, Franon, Jaeger &amp;         Puech [RE88]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Cylindres et polygones</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Niklas [Ni86]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Euclidienne 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Segments</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>       <tr>         <td WIDTH="257" VALIGN="TOP"><p ALIGN="CENTER">Greene [Gr89]</td>         <td WIDTH="142" VALIGN="TOP"><p ALIGN="CENTER">Discrte 3D</td>         <td WIDTH="191" VALIGN="TOP"><p ALIGN="CENTER">Segments discrets et polygones discrets</td>         <td WIDTH="65" VALIGN="TOP"><p ALIGN="CENTER">Non</td>       </tr>     </table>     <b><font FACE="HELVETICA"><p></font>1.2.8.3 Le rendu</b></p>     <p>Les mthodes de modlisation dcrites dans les paragraphes prcdents gnrent     des structures qu'il reste maintenant  dessiner. Les particularits de ces structures     (type, nombre d'lments les composant) ont une influence sur les algorithmes qu'il est     possible ou qu'il n'est pas possible d'employer. Dans certain cas de nouveaux algorithmes     ont mme d tre dfinis.</p>     <table BORDER="1" CELLSPACING="1" WIDTH="676" bordercolordark="#006633"     bordercolorlight="#339966">       <tr>         <td WIDTH="197" VALIGN="TOP">&nbsp;</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Elimination des parties caches</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Plaquage de texture</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Type de rendu</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Honda [Hon71]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Fil de fer</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Aono &amp; Kunii [AK84]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Fil de fer</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Kawaguchi [Ka82]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Oui<br>         Mthode non prcise mais trs probablement classique</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Non raliste</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Bloomenthal [BL85]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Oui<br>         Mthode non prcise mais trs probablement classique</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Oui</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Trs raliste<br>         gros plans possibles</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Oppenheimer [Op86]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Oui<br>         Mthode non prcise mais trs probablement classique</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Oui</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Trs raliste<br>         gros plans possibles</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Demko, Hodges &amp; Naylor [DH85]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Impressionniste</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Barnsley, Jacquin, Malassenet, Reuter &amp;         Sloan [BJ88]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Impressionniste</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Reeves et Blau [RB85]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Oui</p>         <p ALIGN="CENTER">Spcifique</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Impressionniste</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Arqus, Janey, Viennot &amp; Eyrolles         [VE89] [AJ90] [AJ91]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Oui<br>         Classique adapte</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Oui</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Raliste</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Lienhardt &amp; Franon [Li87] [LF87]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Oui, classique</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Trs raliste</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Smith [Sm84]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Raliste</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Prusinkiewicz, Lindenmayer &amp; Hanan         [PL88]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Raliste</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">de Reffye, Edelin, Franon, Jaeger &amp;         Puech [RE88]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Oui<br>         Z-Buffer</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Trs raliste</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Niklas [Ni86]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Fil de fer</td>       </tr>       <tr>         <td WIDTH="197" VALIGN="TOP"><p ALIGN="CENTER">Greene [Gr89]</td>         <td WIDTH="190" VALIGN="TOP"><p ALIGN="CENTER">Oui, Z-Buffer</td>         <td WIDTH="131" VALIGN="TOP"><p ALIGN="CENTER">Non</td>         <td WIDTH="134" VALIGN="TOP"><p ALIGN="CENTER">Raliste</td>       </tr>     </table>     <b><font FACE="HELVETICA"><p></font>1.3 Les reliefs</b></p>     <p>La simulation raliste de scnes naturelles est l'un des domaines de l'infographie     o se posent les problmes les plus difficiles en raison de la complexit des scnes     et des phnomnes  modliser. Un paysage est compos d'un ensemble d'objets naturels     et artificiels de natures diffrentes dont la modlisation individuelle est difficile.     Parmi ces objets on trouve bien sr les arbres, mais aussi les nuages, les btiments et     surtout le relief qui les supporte. La composition de ces objets au sein d'une scne est     aussi un problme compliqu.</p>     <p>Les mthodes imagines pour la gnration de reliefs sont beaucoup moins varies     que celle traitant de la modlisation des arbres.</p>     <p>Les domaines d'application de la modlisation de relief sont nombreux (simulateurs de     vols, animation, images de synthse, ...) et imposent deux objectifs antinomiques : le     ralisme et l'efficacit. Peu de modles concilient ces deux contraintes : ceux     utiliss dans les applications &quot;temps rel&quot; (comme les simulateurs de vol)     sacrifient le ralisme  l'efficacit, les modles au rendu plus raliste peuvent     demander des temps de calcul trs importants (plusieurs heures).</p>     <p>Les techniques dveloppes en modlisation et rendu de terrain peuvent tre     classes en un certain nombre de catgories.</p>     <b><p>1.3.1 Les techniques  base de plaquage de texture</b></p>     <p>Historiquement les plus vieilles techniques de modlisation de relief sont celles     bases sur le plaquage de texture sur des primitives graphiques simples.</p>     <p>Dungan, Stenser, Sutty [DS78] produisent des images 2D de terrains par plaquage de     texture sur des zones de l'image.</p>     <p>&nbsp;Marshall, Wilson et Carlson [MW80] utilisent des <i>modles procduraux</i> de     manire  dcrire les hirarchies prsentes  l'intrieur d'une scne (arbre -&gt;     fort d'arbres, montagne -&gt; chane de montagnes, fort d'arbres + chane de     montagnes -&gt; paysage, ...) et  rendre ainsi plus facile le travail de conception et     de dessin d'une telle scne. Chacun des lments de base (arbre, colline, ...) est     entirement dcris par un ensemble de paramtres permettant la modlisation de     l'objet. Typiquement ces valeurs seront les paramtres de la procdure (au sens     informatique) permettant la conception et le dessin de cet objet. Dans le cas particulier     de la gnration de collines, un logiciel interactif  t crit pour la conception     d'un maillage topographique. Des oprations gomtriques lmentaires permettent la     paramtrisation de ce relief.</p>     <p>Gardner [Ga84] modlise un terrain et plus gnralement un paysage compos (relief,     arbres, nuages) par un ensemble de <i>surfaces quadriques 3D</i> (quation cartsienne     gnrale de cette famille de surfaces: Q<font size="1">1</font>x<font size="1">2</font>+Q<font     size="1">2</font>y<font size="1">2</font>+Q<font size="1">3</font>y<font size="1">2</font>+Q<font     size="1">4</font>xy+Q<font size="1">5</font>yz+ Q<font size="1">6</font>zx+Q<font size="1">7</font>x+Q<font     size="1">8</font>y+Q<font size="1">9</font>z+Q<font size="1">0</font> = 0). Dans la     pratique Gardner utilise surtout des hyperbolodes et des ellipsodes. Pour obtenir une     plus grande varit topographique et viter des problmes de recoupement entre     surfaces qui pourraient tre coteux en temps de calcul, chacune de ces surfaces     quadriques peut tre limite par un ou plusieurs plans. Pour raliser l'affichage d'une     scne, Gardner gre un clairage et plaque sur ces surfaces une texture calcule     mathmatiquement. L'utilisation d'une texture mathmatique a pour buts :</p>     <p>- l'obtention d'un rendu raliste (le plaquage de texture est ncessaire pour le     terrain et impratif pour les nuages et les arbres),</p>     <p>- la ralisation de gros plans,</p>     <p>- la ralisation d'une animation.</p>     <p>Kaneda, Kato, Nakamae, Nishita, Tanaka, Noguchi [KK89] utilisent aussi une mthode par     plaquage de texture, mais dans un but diffrent : la synthse d'images artificielles de     zones gographiques existantes et dont on dispose de relevs topographiques et de     photographies ariennes. Ils oprent en six tapes.</p>     <p>a)&nbsp;Saisie des lignes de niveau d'une carte topographique.</p>     <p>b)&nbsp;Gnration d'une carte 3D par maillage  partir des lignes de niveau. Il ne     s'agit pas ici d'un maillage classique triangulaire ou carr mais d'un maillage radial     dpendant de la position de l'observateur. Du point de vue de l'observateur, le maillage     ainsi obtenu possde des facettes quadrangulaires ayant deux cots verticaux.</p>     <p>c)&nbsp;Ajustement de la teinte de photographies ariennes de la zone  reprsenter.</p>     <p>d)&nbsp;Plaquage de ces photographies en tant que texture sur les facettes.</p>     <p>e)&nbsp;Pour tenir compte des arbres, modification du modle, par rehaussement des     facettes contenant des arbres et ajout de nouvelles facettes verticales  la limite des     zones forestires. Une texture spciale est plaque sur les facettes ajoutes.</p>     <p>f)&nbsp;Introduction des constructions et gestion des ombres portes.</p>     <p>L'inconvnient conceptuel principal de ces mthodes est qu'elles n'incluent pas un     rel mcanisme de gnration automatique de relief.</p>     <b><p>1.3.2 Les mthodes fractales</b></p>     <p>La seconde catgorie de mthodes de gnration de reliefs est base sur la     thorie mathmatique des fractales de Mandelbrot [Ma82].</p>     <p>Une approche intuitive et trs connue consiste  considrer qu'une <i>fractale</i>     est la transformation rcursive d'un objet par n copies de lui mme  l'chelle r.     C'est ce que l'on appelle l'<i>autosimilarit</i>. La figure 1R prsente des exemples de     transformations en dimension 1. Il est bien entendu possible d'oprer dans un espace de     dimension quelconque et, en particulier pour les reliefs, en dimension 2. On a coutume de     caractriser un objet fractal  partir d'un paramtre numrique gnralement not D     appel <i>dimension fractale</i>. D est gal  <img src="Chapitre1/Image117.gif"     align="middle" width="41" height="47"> et caractrise la manire selon laquelle une fractale volue dans     l'espace o elle est dessine.</p>     <p>Les <i>fractales stochastiques</i>, par opposition aux <i>fractales dterministes</i>,     permettent de gnrer des dessins non rguliers. On obtient de bons rsultats avec D     voisin de 1,2 pour gnrer des rivages ocaniques (lignes) et avec D voisin de 2,2 pour     la gnration de montagnes (surfaces), plus D croit plus la ligne ou la surface devient     chaotique et irraliste.</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image132.gif" width="176" height="550">&nbsp;&nbsp;&nbsp; <img     SRC="Chapitre1/Image120.gif" WIDTH="278" HEIGHT="545"></font></p>     <font FACE="HELVETICA"><p></font>Figure 1R : Fractales dterministes</p>     <font FACE="HELVETICA"><p></font><img src="Chapitre1/Image121.gif" width="375" height="343"></p>     <font FACE="HELVETICA"><p></font>Figure 1R' : Mouvement Brownien fractionnaire avec des     valeurs de H gales  0.2, 0.3, 0.4, 0.6 et 0.8 de haut en bas correspondant  des     valeurs de D gales  1.8, 1.6, 1.4, 1.3 et 1.2.<font FACE="HELVETICA"></p>     <p></font>La thorie des fractales est issue de travaux de Mandelbrot et van Ness [MV68]     o est introduit la notion de <i>mouvement Brownien fractionnaire</i> (fractional     Brownian motion, fBm) pour caractriser une famille de processus stochastiques Gaussiens     unidimensionnels V<font size="1">H</font>(t) (H reprsente un paramtre numrique     compris entre 0 et 1 et t reprsente le temps) tels que plus H est proche de 0 plus la     courbe est bruite (Figure 1R'). Une valeur de H gale  0,5 quantifie une <i>mouvement     Brownien normal</i>. L'une des proprits de ces processus temporels est l'<i>autoaffinit</i>,     c'est  dire que deux morceaux quelconques de la courbe reprsentative du processus se     ressembleront, mais surtout, si l'on effectue une mise  l'chelle d'un facteur r sur le     temps et d'un facteur r<font size="1">H</font> sur V<font size="1">H</font>(t), la courbe     garde toujours le mme aspect.</p>     <p>L'extension multidimensionnelle des fBm permet de modliser un large ventail de     phnomnes naturels dont, en particulier, les reliefs. Le paramtre temps t est alors     transform en un couple (x,y) indiquant une position dans le plan d'un point P, V<font     size="1">H</font>(x,y) donne l'altitude du point P (Figure 1R''). Un objet fractal de     dimension fractale D peut apparatre comme un fBm de coefficient H tel que D = E + 1 - H     o E est le nombre de variables de la fonction fBm, c'est  dire la <i>dimension     euclidienne</i> de l'objet construit. Cet objet n'est videmment pas strictement     autosimilaire mais seulement autoaffine.</p>     <p><img src="Chapitre1/Image122.gif" width="442" height="299"></p>     <p>Figure 1F'' : Un relief fractal gnr par fBm reprsent par facettes</p>     <font FACE="HELVETICA"><p></font>Les mthodes fractales sont prsentes sous un certain     nombre d'aspects (mathmatique, programmation, applications) par Barnsley, Devaney,     Mandelbrot, Peitgen, Saupe et Voss dans [BD88] et dans bien d'autres ouvrages ([Ba88],     [Fa90],...). La proprit d'autosimilarit peut tre traduite au moyen d'un grand     nombre de formalisations mathmatiques. la plus connue est probablement celle permettant     de gnrer les ensembles de Julia-Fatou et de Mandelbrot : x -&gt; x<font size="1">2</font>     + c, o x est une variable complexe et c est une constante complexe.</p>     <p>De trs nombreux travaux ont t effectus avec pour but une implantation efficace     des fractales stochastiques. En effet, la programmation exacte des lois mathmatiques     mises en &#156;uvre requiert une quantit de calcul trs importante. Ces implantations     sont essentiellement des approximations du mouvement Brownien fractionnaire soit par des <i>techniques     spatiales</i> (subdivision rcursive), soit par des <i>techniques spectrales</i> (par     filtrage de Fourier).</p>     <font FACE="HELVETICA"><p><img SRC="Chapitre1/Image125.gif" width="564" height="183"></font></p>     <font FACE="HELVETICA"><p></font>Figure 1S : Une tape de fractalisation d'un triangle</p>     <font FACE="HELVETICA"><p></font>Fournier, Fussel et Carpenter [FF82] prsentent des     techniques de <i>subdivision rcursive</i> qui peuvent tre utilises pour construire     des lignes polygonales fractales (approximation de la forme de l'Australie  partir d'un     octogone), des pavages polygonaux fractaux ou des surfaces paramtriques stochastiques     indpendants du repre cartsien de l'espace de travail (Figure 1S). Smith [Sm84]     prsente les techniques de subdivision de Fournier et al. en terme de <i>grammaire et de     rgles de rcriture</i> (Graftals) appliqus  des cartes topologiques. Miller     [Mi86] aborde le problme du choix du motif de subdivision rcursive en soulignant que     ce choix influe sur l'aspect final du dessin (on peut reconnatre le motif  partir de     l'image obtenue). Deux exemples de subdivision sont dcrit (en triangle et en diamant)     qui peuvent poser problme, et une meilleure solution est propose par dcomposition en     carrs. Enfin, il donne une solution au problme du rendu d'un paysage fractal par un     algorithme parallle de ray tracing.</p>     <p><img src="Chapitre1/Image124.gif" width="476" height="333"></p>     <font FACE="HELVETICA"><p></font>Figure 1S' : Un nuage fractal</p>     <font FACE="HELVETICA"><p></font>Les mthodes fractales sont trs souvent considres     comme les plus efficaces pour la cration d'images ralistes d'objets naturels (images     de Voss [Vo83] et de Cook, Carpenter, Porter, Reeves, Salesin, Smith [CC83]). Les     qualits de l'approche fractale s'expriment en termes de ralisme remarquable, de trs     importante <i>amplification des donnes</i> (un trs petit nombre de paramtres suffit      dcrire un nuage ou une montagne fractale simple) et de niveau de dtail aussi fin     que voulu (un nuage est donn Figure 1S', une montagne fractale peut tre trouve page     249 de [BD88]). Certains inconvnients ont toutefois t signals. Par exemple, <i>l'effet     de plissement</i> ou &quot;<i>creasing effect</i>&quot; est li  l'indpendance du     contexte des grammaires prcites. Benoit Mandelbrot dans [BD88] (Annexe A) cite un     autre problme qui dfinit assez bien les questions qui sont abordes par une approche     non fractale dans la deuxime partie de cette thse :</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. De plus, les fractales ne sont pas     capables de modliser directement un rseau fluvial dans sa totalit. Il serait     illusoire de penser qu'un seul modle global puisse rendre compte de la trs grande     diversit des processus mis en &#156;uvre au cours de la gnration d'un relief     (soulvements dus  la tectonique, rosion par les rivires, les glaciers, le vent, le     gel, ..., prsence de strates gologiques, formation de bassins sdimentaires par     accumulation de matriaux dtritiques dans les valles,...). Mandelbrot bauche  ce     problme un type de solution (voir [BD88]) qui consiste dans un premier temps,      construire rcursivement, simultanment deux fractales 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'altitude (maxima pour     les sources, diminution de l'altitude le long des fleuves,...).</p>     <b><p>1.3.3 Les techniques bases sur un modle d'rosion</b></p>     <p>La dmarche qui consiste  gnrer un relief par simulation de l'rosion (<i>modle     dynamique</i>) ou par utilisation de lois rendant compte des consquences de l'rosion     sur un bassin de drainage (<i>modle statique</i>) caractrise la troisime catgorie     de techniques de modlisation de terrain.</p>     <b><p>1.3.3.1 Mthodes statiques</b></p>     <p>Outre la solution sus-mentionne de Mandelbrot, les travaux de Kelley, Malin et     Nielson [KM88] sont caractristiques de cette approche. La description du bassin fluvial     (fleuve et bassin de drainage) est fonde sur des modles empiriques d'coulement     utiliss en gomorphologie (voir Abrahams [Ab80], Howard [How71], Shreve [Sh66]) mettant     en &#156;uvre un arbre binaire recouvrant une carte modlisant le rseau hydrographique     et le bassin de drainage associ. Cet arbre est gnr par ajouts rcursifs     d'affluents  partir d'une arte racine unique concurremment  l'ajout de facettes      la carte sous-tendue.</p>     <p><img src="Chapitre1/Image126.gif" width="514" height="622"></p>     <p>Figure 1T: Systme de drainage initial</p>     <p><img src="Chapitre1/Image127.gif" width="454" height="438"></p>     <p>Figure 1T' : Maillage modlisant un relief</p>     <font FACE="HELVETICA"><p></font>L'arte racine est initialement place  l'intrieur     d'un <i>systme de drainage initial</i> dfini par l'arte initiale et les deux     polygones  droite et  gauche de cette arte (Figure 1T), ces trois composants tant     positionns dans R<font size="1">3</font>. La cration d'un affluent sur un segment de     rivire intervient si le rapport :</p>     <p>r=<img src="Chapitre1/Image128.gif" align="middle" width="258" height="36"> est suprieur  une limite     donne. Il y a alors cration de deux nouveaux n&#156;uds : un n&#156;ud de jonction sur     l'ancien segment et un n&#156;ud  l'extrmit du segment nouvellement cr. La carte     est elle-mme modifie par cration de nouvelles facettes. Le placement gomtrique     des deux nouveaux n&#156;uds est effectu en fonction de contraintes gomorphologiques     qui vont permettre de dcider du cot d'insertion du segment (le cot o le rapport r     est le maximum) et de calculer les positions des n&#156;uds en x en y et en z (Figure     1T').</p>     <p>Les modlisations topologiques et gomtriques (plongement dans R<font size="1">3</font>)     sont ici effectues simultanment avec une influence de la gomtrie sur la topologie.</p>     <p>Le maillage polygonal obtenu est alors interpol par une surface analogue  une <i>surface     spline sous tension</i> pour permettre d'attribuer une altitude  n'importe quel point du     relief et ainsi gnrer un nouveau maillage triangulaire rgulier en projection sur xOy     de la surface modlise (Figure 1T'').</p>     <p><img src="Chapitre1/Image129.gif" width="462" height="318"></p>     <p>Figure 1T'' : Un relief par modle d'rosion (Illustration extraite de [KM88], p 267     ,  ACM.)</p>     <font FACE="HELVETICA"><p></font>Les images finales sont obtenues en attribuant une     couleur  chaque facette. Cette couleur est fonction de paramtres tels que la position,     l'altitude ou la pente de la facette. L'image de relief montre  la figure I. compte     environ 40000 triangles pour un temps de modlisation de 8 minutes (sur SUN 3) et un     temps d'affichage de 4 minutes sur VAX 11/750.</p>     <p>Cette mthode matrialise un modle de gnration statique, 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.</p>     <b><p>1.3.3.2 Modles dynamiques</b></p>     <p>Les modles dynamiques 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>Roudier [Ro91], partant d'un maillage rgulier initial carr ou hexagonal dont chaque     sommet est affect d'une altitude constante bruite fractalement, simule l'volution     dans le temps de ce relief en faisant subir  chaque itration temporelle  chaque     point du maillage une rosion exprime par une baisse de son altitude (dans certains cas     particulier de points situs dans une cuvette, il peut y avoir accroissement de     l'altitude par sdimentation). Cette variation d'altitude est calcule  partir d'un     certain nombre de lois simulant un dplacement de matire traduisant l'action de l'eau :</p>     <p>- <i>Loi gravitaire</i> : Elle traduit le dplacement lent des terrains dans le sens     de la pente sous l'action de la gravitation et entrane une diminution d'altitude Z<font     size="1">g</font> (valeur ngative).</p>     <p>- <i>Loi mcanique</i> : Elle rend compte de l'usure des sols avec production de <i>matriaux     dtritiques</i> (sdiments) sous l'action des eaux de ruissellement provenant des     prcipitations. Les eaux de ruissellement passant sur chaque n&#156;ud du maillage sont     la somme des prcipitations sur ce n&#156;ud et des eaux de ruissellement provenant des     sommets adjacents de plus haute altitude, diminue des quantits d'eau infiltre et     vapore. Les matriaux dtritiques sont dplacs vers le n&#156;ud adjacent     d'altitude la moins leve. La loi mcanique entrane une diminution d'altitude Z<font     size="1">w</font> (valeur ngative).</p>     <p>- <i>Loi chimique</i> : Elle permet de calculer la fraction des matriaux rocheux mis     en solution par les eaux d'infiltration et qui disparaissent de la simulation. Elle se     traduit par une diminution d'altitude Z<font size="1">c</font> (valeur ngative).</p>     <p>- <i>Loi sdimentaire</i> : Quand l'rosion mcanique amne des matriaux     dtritiques dans une cuvette ou que la concentration de ces matriaux dans les eaux de     ruissellement devient trop importante vis  vis de la pente, il y a sdimentation,     phnomne qui entrane une prise d'altitude Z<font size="1">d</font> (valeur positive).</p>     <p>La diffrence d'altitude Z  chaque itration t de la simulation pour chaque     n&#156;ud n du maillage et donc Z(t,n) = Z<font size="1">g</font>(t,n) + Z<font size="1">w     </font>(t,n)+ Z<font size="1">c</font>(t,n) + Z<font size="1">d</font>(t,n).</p>     <p><img src="Chapitre1/Image130.gif" width="606" height="255"></p>     <p><img src="Chapitre1/Image131.gif" width="606" height="255"></p>     <font FACE="HELVETICA" SIZE="2"><p></font>Figure 1U : Evolution d'un relief (Images     extraites de [Ro91]).</p>     <font FACE="HELVETICA"><p></font>Ces quatre lois sont fonctions des prcipitations et de     paramtres gologiques attribus aux n&#156;uds :</p>     <p>- un coefficient K<font size="1">d</font> de duret de la roche,</p>     <p>- un coefficient K<font size="1">f</font> d'infiltration,</p>     <p>- un coefficient K<font size="1">v</font> de vgtation,</p>     <p>- un coefficient K<font size="1">c</font> de dissolution chimique,</p>     <p>- un rapport entre les sdiments<font size="1"> </font>dposs et les sdiments     restant en suspension.</p>     <p>Le calcul de l'coulement de l'eau est effectu de manire simplifie en     considrant que les eaux de ruissellement provenant d'un sommet du maillage quelconque se     dirigent toujours vers le sommet d'altitude minimum qui lui est adjacent. Il faut bien     entendu que ce point ait une altitude infrieure  celle du point source sinon il y     cration d'un lac. Ce processus d'coulement permet de tracer les cours d'eau prsents      l'intrieur du relief.</p>     <p>La simulation est assez pousse dans le sens o une vritable modlisation     gologique du sous-sol du terrain initial est dfinie avec le calcul possible pour tout     point du maillage polygonal, quels que soient sa position et surtout son altitude, d'un     ensemble complet de paramtres gologiques (modlisation du sol et du sous-sol par     modlisation pralable de phnomnes gologiques tels que les plissements ou     l'apparition de failles). En fonction de ces caractristiques l'rosion est diffrente     suivant la position des n&#156;uds du maillage. On voit ainsi ressortir les     caractristiques du sous-sol (rsistance plus ou moins grande  l'rosion, lignes de     failles) au fil des itrations rythmant l'coulement du temps (Figure 1U).</p>     <p>Musgrave, Kolb et Mace [KMK89] rsolvent le problme de la symtrie des valles et     des montagnes dans un paysage gnr par une mthode fractale en effectuant une     modlisation en deux tapes conscutives :</p>     <p>- une gnration fractale adapte  la gnration de reliefs,</p>     <p>- une phase d'rosion du relief fractal obtenu.</p>     <p>La gnration fractale est effectue en faisant varier les paramtres     caractristiques suivants :</p>     <p>- la dimension fractale,</p>     <font FACE="HELVETICA"><p></font>- &quot;<i>l'chelle de croisement</i>&quot; (<i>crossover     scale</i>) qui reprsente la valeur d maximale telle qu&#146;un dplacement d&#146;une     distance d dans le plan horizontal puisse tre accompagn d&#146;une diffrence     d&#146;altitude de mme valeur d.</p>     <p>Ces deux paramtres varient en fonction de la position considre dans le plan et de     l'altitude :</p>     <p>- On se servira de la dimension fractale de manire  rendre les reliefs gnrs     moins chaotiques dans les zones basses. La figure 1V montre un exemple de relief o la     dimension fractale augmente de 2  3 de la gauche vers la droite</p>     <p><img src="Chapitre1/Image135.gif" width="433" height="300"></p>     <p>Figure 1V : Influence de la dimension fractale (Illustration extraite de [KMK89], p 48,      ACM.)</p>     <p>- Le paramtrage de l'chelle de croisement permet de dfinir des zones o     l'amplitude du relief est plus ou moins importante La figure 1V' montre une ligne de     crte o l'chelle de croisement varie en fonction de l'altitude et de la position     horizontale.</p>     <p><img src="Chapitre1/Image136.gif" width="432" height="299"></p>     <p>Figure 1V' : Influence de l'chelle de croisement (Illustration extraite de [KMK89], p     48,  ACM.)</p>     <p>L'utilisation de ces deux paramtres est ncessaire car la dimension fractale ne     suffit pas  caractriser correctement un terrain. Par exemple une piste d'atterrissage     d'un aroport et la chane himalayenne possdent la mme dimension fractale et     pourtant ne se ressemblent pas car leurs chelles de croisement sont respectivement de     l'ordre du millimtre et de l'ordre du kilomtre (voir [Ma82]).</p>     <p>Aprs la gnration fractale on obtient un relief modlis par facettes pouvant     tre vu comme une carte plonge dans R<font size="1">3</font>. Pour rsoudre le     problme de l'absence de modlisation relle des rseaux fluviaux, une phase     d'rosion hydraulique est ajoute  la suite de la gnration fractale, de manire      simuler des dplacements de matire. Pour cela,  chaque itration du processus     discret d'rosion, chaque facette du relief va tre traite pour valuer la quantit     de sdiments qui prcipite ou qui est rode. Cette quantit est fonction d'un     certain nombre de valeurs :</p>     <p>- la quantit d'eau provenant des prcipitations et des facettes adjacentes  cette     facette (fonction des altitudes relatives de ces facettes par rapport  la facette     teste),</p>     <p>- la quantit de sdiment arrivant avec l'eau de ruissellement provenant des facettes     adjacentes,</p>     <p>- la constante K<font size="1">c</font> dfinissant la quantit maximale de sdiment     pouvant tre en suspension dans un volume d'eau, la constante K<font size="1">s</font>     dfinissant la solubilit du sol de cette facette, la constante K<font size="1">d</font>     dfinissant la vitesse de sdimentation.</p>     <p>Du point de vue de la simulation du processus d'rosion hydraulique, les travaux de     Musgrave et al. semblent une version simplifie de ceux de Roudier. De plus il n'y a pas     de modlisation gologique du sous-sol. La modlisation fractale initiale permet     d'apporter des dtails aux reliefs qui n'apparatraient pas sans, cela semble tre une     bonne mthode pour calculer le relief de dpart.</p>     <p><img src="Chapitre1/Image137.gif" width="434" height="356"></p>     <p><img src="Chapitre1/Image138.gif" width="433" height="361"></p>     <p>Figure 1W : Une valle sans et aprs une trs longue rosion ([KMK89], p 48 et 49,      ACM).</p>     <p>Les travaux de Musgrave et al. sont axs sur un troisime aspect : le rendu au moyen     d'un algorithme spcifique de lanc de rayons qui ne sera pas dcris ici.</p>     <b><p>1.4 Conclusion</b></p>     <p>La conclusion de cette tude comparative est la trs grande diversit des     modlisations proposes dans le cadre de la synthse d'images de vgtaux et de     terrains. Il serait intressant de rechercher un modle qui gnralise et unifie, en     particulier pour les vgtaux, ces diffrentes approches.</td>   </tr> </table> </body> </html> 
