Combinatorial analiz of ramified patterns and computer imagery of treesAuthor: Viennot E.
Other authors: Janey A.
Publishers: Computer graphics
Year of publication: 1989
Number of pages: 10
Read: 1 2 3 4 5 6 7 8 9 10
Computer Graphics, Volume 23, Number 3, July 1989
Combinatorial Analysis of Ramified Patterns and Computer Imagery of Trees
Xavier GerardViennot 1, Georges Eyrolles 1, Nicolas Janey 2, Didier Arques 2
1. LABRI, Departement d'Informatique, Universite de Bordeaux I, FRANCE
(U.A. CNRS 0726)
2. LIB, Departement d'Informatique, Universite de Franche-Comte, FRANCE
(U.A CNRS 0822)
Herein is presented a new procedural method for generating images of trees. Many other algorithms have already been proposed in the last few years focusing on particle systems, fractals, graftals and L-systems or realistic botanical models. Usually the final visual aspect of the tree depends on the development process leading to this form. Our approach differs from all the previous ones. We begin by defining a certain "measure" of the form of a tree or a branching pattern. This is done by introducing the new concept of ramification matrix of a tree. Then we give an algorithm for generating a random tree having as ramification matrix a given arbitrary stochastic triangular matrix. The geometry of the tree is defined from the combinatorial parameters implied in the analysis of the forms of trees. We obtain a method with powerful control of the final form, simple enough to produce quick designs of trees without loosing in the variety and rendering of the images. We also introduce a new rapid drawing of the leaves. The underlying combinatorics constitute a refinment of some work introduced in hydrogeology in the morphological study of river networks. The concept of ramification matrix has been used very recently in physics in the study of fractal ramified patterns.
CR Categories and Subject Descriptors : 1.3.5 [Computer Graphics]: Computational Geometry and Object Modeling. 1.3.7.[Computer Graphics]: Three-Dimensional Graphics and Realisms. J.3 [Life and Medical Sciences]: Biology. J.5 [Arts and Humanities]: Arts, fine and performing.
General terms: Trees, plants, algorithms, realistic image synthesis, figurative image synthesis
Additional keywords and phrases: branching patterns in physics, stochastic modeling, analysis of form, fractals, self-similarity, combinatorics, ramification matrix
1. Introduction Computer Image Synthesis generation of trees and plants has been the subject of many papers in the past few years. Let us mention for example : Marshall, Wilson, Carlson , Kawaguchi , Reeves, Blau , Gardner , Aono, Kunii , Smith , Bloomenthal , Niklas , Demko,
1. LABRI, Departement d'Informatique, Universite de Bordeaux I, 33405 Talence, FRANCE - Tel.: (33) 56 84 60 85
2. LIB, departement d'Informatique, Universite de Franche-comte, 25030 Besan5on, FRANCE - Tel.: (33) 81 66 64 63
Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.
Hodges, Naylor , Oppenheimer , Prusinkiewicz , Beyer et Friedel , Prusinkiewicz, Lindenmayer et Hanan , De Reffye, Edelin, Fran?on, Jaeger, Puech .
In these works, tree generation was mainly made at two levels. The first one is the generation of the topological (combinatorial) tree underlying the real tree. In general, this topological tree is binary or ternary. The second level is the generation of the geometrical tree. Each method applies a more or less sophisticated geometrical model to the topological tree. The minimum geometry consists in a 2D-drawing of trees, with width and length choices for each branch and angle choices for each branching node. A more sophisticated geometry consists in a 3D visualization to which are added vegetal elements (leaves, flowers), bark texture on branches and outside constraints such as light, wind or gravity.
In all previous mentioned works, these two topological and geometrical levels are more or less separated during the generation. These methods can be roughly classified as follows :
- Fixed topology methods, like the ones of Kawaguchi , Aono & Kunii  which only generate perfect trees. Due to the lack of variation of topology, geometry is of great importance in order to create a large diversity of forms.
- Generation methods by development models which include a real growth strategy of trees. For example : generation by fractals of Mandelbrot, Oppenheimer , or by stochastic and recursive growth of branching nodes, Niklas ; generation by rewriting rules using L-systems theory developed by Lindenmayer, Smith , Prusinkiewicz , Prusinkiewicz, Lindenmayer, Hanan ; generation by a botanical development model De Reffye, Edelin, Franfon, Jaeger, Puech .
Papers ,,,,  essentially focus on geometry, while papers , , , ,  are mainly interested in the development of topology.