Dans son jardin, un homme fait pousser des plants de tomates et vient de semer les premières graines. Est-il capable de prédire leur croissance? Peut-il deviner le nombre de branches, les angles entre elles, leur longueurs? Aristid Lindenmayer, un mathématicien du XXe siècle, a répondu à cette question: nous pouvons le faire et ce, avec une étonnante précision et un niveau de réalisme insoupçonné. Sa méthode? Les L-systèmes.
Lindenmayer et ses plantes
Quelque part, caché dans les cellules des plantes, un brin d’ADN décrit leur développement au fil des semaines ou des années. Au lieu d’analyser le code génétique des plantes, Aristid Lindenmayer a tenté de deviner par lui-même leurs règles de croissance, puis de les vérifier. Bien qu’il ait été biologiste, il est principalement reconnu pour son travail mathématique: les L-Systèmes. Cette grammaire formelle permet de modéliser la croissance des végétaux (aussi appelée morphogenèse en biologie) par un système de règles simples en nombre fini. Les résultats du chercheur, très concluants, se démarquent surtout par leur grande simplicité: il ne suffit que d’une ou deux règles simples pour décrire la croissance d’une plante complexe et élégante. Le fonctionnement des L-Systèmes que Lindenmayer utilise pour représenter la croissance des plantes est semblable à ce qui se passe en réalité dans la nature. De la même manière qu’une plante doit pousser, branche par branche, pour atteindre un âge mature, son équation mathématique doit elle aussi croître selon des règles très précises. Ainsi, Lindenmayer a modélisé de nombreuses plantes en trouvant leurs règles de croissance, ce qui lui a permis de générer leurs équations. Par exemple, la figure ci-contre représente une plante rudimentaire à ses premières étapes de croissance. Lindenmayer a inventé une grammaire pour représenter mathématiquement l’état des plantes et les règles qui régissent leur croissance. La description de la plante rudimentaire est donnée en milieu de page à gauche.
Mais comment lire ces équations pour faire le dessin de la plante? Il suffit d’utiliser l’interprétation à pas de tortue!
Une tortue bien spéciale est munie d’une craie qui trace une ligne au fur et à mesure que la tortue avance. En lui donnant des consignes simples (avancer, tourner, etc.), il est possible de tracer des images très complexes et très détaillées.
À l’étape 1 de l’exemple, nous pouvons lire la règle S[-F][+F], qui comporte six types d’instructions pour la tortue.
La tige principale est représentée par le premier « S » dans l’équation. Ensuite, « [-F] » est la branche de droite. Les crochets « [» et «] » servent donc à encadrer le contenu d’une branche et le « – » sert à lui donner un angle par rapport à la tige. Il en va de même pour « [+F] » qui représente la branche de gauche. Nous pouvons voir que seules les branches à l’extrémité de la plante sont fertiles et pourront donner naissance à d’autres branches.
Ayant les outils pour tracer une plante en L-systèmes, il ne reste plus qu’à la faire croître.
Pour faire pousser une plante, il faut appliquer ses règles de croissance récursivement.
Pour ce faire, il faut avoir un état initial (souvent une simple tige) sur lequel appliquer les règles de croissance. La plante vue plus tôt avait les règles suivantes ci-contre. À chaque étape de croissance, les règles sont appliquées à la plante, ce qui la fait croitre. Pour que la tortue puisse comprendre comment dessiner la plante, il faut exprimer les règles avec des symboles qu’elle comprend tel que sur la figure à droite.
De manière procédurale, il faudra replacer tous les « F » de l’étape n-1 par la chaîne « S[-F][+F] » pour obtenir l’étape n. Il sera laissé en exercice de vérifier la construction des étapes 2 et 3 de la plante vue plus tôt.
Dans la plupart des cas, une règle de croissance ne suffit pas et il faut plutôt un ensemble de règles pour construire une plante plus complexe.
Maintenant, nous pouvons nous amuser à faire pousser la plante simple en appliquant les règles de manière récursive. Nous dirons qu’après avoir appliqué les règles n fois, nous sommes à la ne itération de la plante.
On voit bien qu’à partir de l’étape 3 la notation devient très lourde. Il est presque impossible de s’en faire une représentation mentale. Par contre, géométriquement, ajouter deux branches sur chaque segment de manière itérative se conçoit assez aisément. Un ordinateur a justement le pouvoir (et la patience!) d’interpréter notre suite de caractères comme une figure géométrique. Pour se convaincre de la longueur de la tâche, la figure à droite montre la quantité d’instructions qu’un ordinateur doit interpréter pour dessiner les étapes suivantes de la plante1.
Dans l’ère de l’information où des millions de calculs peuvent s’effectuer en une fraction de seconde, Lindenmayer ne s’est pas arrêté là dans sa modélisation de plantes. Qu’en est-il s’il veut faire « pousser » des feuilles ou des fleurs?
C’est là que les L-Systèmes prennent toute leur puissance: l’utilisateur peut inventer des consignes pour la tortue et laisser libre cours à son imagination!
Par exemple, nous pouvons introduire « { » et « } » qui définissent une surface pleine limitée par ses côtés, plus fréquemment une feuille ou un pétale. Une feuille simple pourrait ressembler à la figure à gauche.
Dans les instructions, les deux premiers « FF » tracent la tige qui supporte la feuille. Ensuite, « { » commence à tracer un polygone en définissant ses côtés. « [-F+F+F] » détermine le côté droit de la feuille de la même manière que « [+F-F-F] » détermine le côté gauche. Finalement, « } » indique la fin du polygone qui représente la feuille.
Les accolades «{» et «}» peuvent aussi indiquer à la tortue de changer la couleur de sa craie. « { » fait passer la couleur au vert pour les feuilles alors que « } » la fait revenir au brun pour la tige, tel qu’illustré sur l’image plus haut. Nous reviendrons plus bas au traçage d’une plante avec des feuilles.
Pour certains modèles, il peut être pratique de tenir compte des bourgeons, représentés par des petits carrés bleus sur les figures. Ceux-ci vont agir comme points d’ancrage pour faire pousser de nouvelles branches. Définissons «B» comme un bourgeon. Nous avons mentionné plus tôt qu’il faut souvent plus d’une règle de croissance pour obtenir une plante réaliste. Voici les règles d’une plante où chaque segment double de longueur (règle 1) et chaque bourgeon « B » donne naissance à d’autres branches « F » qui contiennent elles-mêmes quatre bourgeons (règle 2).
Or, il semble n’y avoir que trois bourgeons dans la représentation de la règle 2. En réalité, les deux bourgeons du bas sont superposés et pousseront avec une orientation différente. On peut voir la plante à ses premières étapes de croissance. Dans cette illustration, on voit que l’état de départ, soit l’itération 0 ne contient qu’un seul bourgeon. Celui-ci va ensuite se développer et donner naissance à d’autres bourgeons. Les segments doublent de longueur à chaque itération, mais le changement d’échelle à chaque image semble annuler cet effet.
Et comment faire pour que les plantes ne soient pas toutes identiques?
Il est aussi possible de rajouter de la variation dans les plantes pour rehausser le réalisme. Certaines règles de croissance peuvent avoir deux possibilités que l’on tire au hasard chaque fois. Dans l’exemple ci-contre, un bourgeon peut se transformer en deux structures différentes, chacune ayant 50% de chances de survenir.
La figure ci-dessous montre deux exemplaires de la plante à sa quatrième itération. Le choix de la règle survient à chaque bourgeon, donc le nombre de plantes différentes à l’étape n est 2n où n est le nombre de bourgeons s’étant développés.
Dans les règles de croissance, il est intéressant de spécifier l’angle avec lequel la tortue tourne lorsqu’elle reçoit une instruction « + » ou « – ». Dans les exemples précédents, l’angle était de 25°, mais certains végétaux ont des angles plus petits (ex.: graminées) et d’autres ont des angles plus grands (ex.: sapins).
Utilisons maintenant les instructions que nous avons définies pour la tortue et construisons une plante élégante. Commençons par la dernière plante et rajoutons-lui du contenu en incluant une transformation en deux possibilités: l’éclosion d’un bourgeon. Comme dans le dernier exemple, la première possibilité (50% de chance d’occurrence) est
« B→F[[-B][+B]]F[+FB]-B »
et la deuxième est
« B→F[-B]F[-FB]+B ».
Nous pouvons ajouter de la variabilité dans les angles de rotation. Toujours tourner vers la gauche ou vers la droite d’un angle \(\delta\) peut créer un nombre anormal de tiges parallèles et diminuer le niveau de réalisme. Pour résoudre ce problème, nous pouvons laisser le choix de l’angle à la tortue, en lui donnant une borne minimale et une borne maximale. Dans ’exemple qui suit, nous avons choisi l’intervalle de 15° à 25° et une loi de probabilité uniforme sur cet intervalle.
Rajoutons aussi une feuille à chaque bourgeon qui pousse vers la droite
« -F{[-F+F+F][+F-F-F]} »
ou vers la gauche
« +F{[-F+F+F][+F-F-F]} ».
Ce sont presque les mêmes feuilles que celles vues plus tôt, mais avec l’instruction « + » ou « – » qui les précède pour leur donner un angle par rapport à la plante.
La règle « F→FF » est importante parce qu’elle fait doubler la longueur de chaque branche à chaque itération de la plante. Par contre, les feuilles seraient affectées aussi par cette règle (elles contiennent des « F ») et deviendraient de tailles démesurées. Il faudra alors définir une autre instruction pour la tortue: « f », qui est identique à « F », mais qui n’est pas affectée par la règle « F→FF ». Les feuilles deviendront:
« -f{[-f+f+f][+f-f-f]} »
et
« +f{[-f+f+f][+f-f-f]} »,
et cela complète les règles de croissance de notre plante (figure à gauche).
Le texte en vert représente la portion des instructions qui dicte la construction des feuilles. Les images à la page suivante montrent trois états possibles pour la plante à la quatrième itération. En choisissant un nombre réel comme angle entre 15° et 25°, il existe une infinité de plantes différentes construites avec ces règles.
Aristid Lindenmayer a créé un outil de modélisation puissant. Que ce soit pour mieux comprendre la croissance des végétaux, pour prédire le développement cellulaire d’un individu ou pour faire un rendu esthétique pour un montage vidéo, les L-Systèmes sont simples d’utilisation et offrent un rendu exceptionnel, complexe et de très grande envergure avec un minimum de règles et de difficulté.
Aristid Lindenmayer (1925 – 1989)
Biologiste hongrois, Lindenmayer a d’abord étudié la croissance de levures, de champignons et d’algues au niveau cellulaire. Au centre de recherche de l’université l’Utrecht, il a travaillé en collaboration avec Przemyslaw Prusinkiewicz qui se spécialisait en informatique. Ensemble ils ont développé une grammaire formelle (L-Systèmes) pour représenter la croissance de plantes, mais uniquement au niveau cellulaire. C’est seulement plus tard que l’idée leur est venue d’améliorer leur outil mathématique pour qu’il puisse modéliser les végétaux à grande échelle.
Dans leur livre The Algorithmic Beauty of Plants, ils expliquent précisément comment s’y prendre pour modéliser des végétaux allant de petites plantes à de grands arbres. Des notions de biologie et de botanique enrichissent leurs modèles de plantes et permettent de générer de très belles images.
Très peu avant la publication de leur livre, en 1989, Lindenmayer décède, laissant à Prusinkiewicz la tâche de compléter le livre et de le publier en 1990. Ce dernier travaille maintenant comme professeur d’informatique à l’Université de Calgary.
Vingt-trois ans après la publication du livre, les L-Systèmes de Lindenmayer continuent d’inspirer étudiants et chercheurs dans la création de végétaux plus réalistes.
L-systèmes en 3D
Les L-Systèmes permettent aussi de modéliser des plantes et des arbres en trois dimensions. Pour ce faire, il faut de nouvelles consignes à donner à la tortue pour qu’elle puisse se diriger et s’orienter dans l’espace. En plus des consignes utilisées en 2D, il faut rajouter les consignes ci-contre.
Avec ces instructions, les possibilités sont beaucoup plus nombreuses. Par exemple, une plante où chaque branche donne naissance à quatre autres branches aurait les règles de l’encadré ci-contre.
Ici, la tortue trace la tige mère « S », puis elle se penche vers le bas d’un angle de 30° pour tracer la première branche « [&F] ». De retour à l’extrémité de la tige principale, la tortue roule autour de celle-ci d’un angle de 90° « <<< », puis s’incline vers le bas pour tracer la deuxième branche « [&F] ». Le processus continue jusqu’à en avoir tracé quatre. Après trois itérations, nous obtenons la plante ci-dessous, vue de deux angles différents.
Pour en s\(\alpha\)voir plus!
http://algorithmicbotany.org/papers/abop/abop.pdf
Images utilisées:
http://www.visoflora.com/images/original/visoterra-branche-de-sapin-pectine-65.jpg
http://i44.servimg.com/u/f44/16/14/96/09/00615.jpg
- Voir page Problèmes. ↩
