in black and white
Main menu
Share a book About us Home
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

Combinatorial analiz of ramified patterns and computer imagery of trees - Viennot E.

Viennot E., Janey A. Combinatorial analiz of ramified patterns and computer imagery of trees - Computer graphics, 1989. - 10 p.
Download (direct link): combinatorialoframifled1989.djvu
Previous << 1 < 2 > 3 4 5 6 7 8 .. 10 >> Next

These various methods use geometry in order to obtain the final shape (or form) of the tree. The aim is to realize realistic drawings of plants and trees. All above mentioned methods focus mostly on the parameters involved in the development process, rather than on the direct control of the final shape. The fact that the shape is implicitly contained in its history, is a well known concept : D'Arcy Thompson [6], Halle, Oldeman and Tomlinson [13]. In this paper a new approach, different from previous ones, is proposed, separating shape from development. In order to obtain better control of the final shape, we first stress on the necessity of defining numerical parameters which allow a certain measure of shape of the tree, i.e. allowing the numerical evaluation of features as thorny, dense, slender, well built or bushy.

Herein, the shape of tree is measured by introducing the new notion of ramification matrix. This matrix is a triangular




31 SIGGRAPH '89, Boston, 31 July-4 August, 1989

stochastic one, associated with each tree or ramified structure. Depending only on the underlying topological tree, this matrix is defined from the combinatorial notions of branch order and branching node biorder. These notions constitute a refinement of some concepts introduced by the hydrogeolo-gists Horton [15] and Strahler [41] in the morphological study of river networks. Our study shows that many visual characteristics connected with the shape of the tree, are reflected in the associated matrix. Very recently, this notion has been used in physical study of fractal ramified structures, Vannimenus, Viennot [43], [44].

Our method consists in the choice of a ramification matrix and then random generation of a combinatorial tree whose ramification matrix is the one chosen (or very similar). At last an elementary 2D geometry is defined. The main idea is to control the width and length of branches, the angles of branching nodes by linear, polynomial or exponential laws in terms of the order and biorder parameters. The advantage is in a better control of the shape. The method is simple and fast while keeping a great variety of possible forms. Although this theoretical model moves away from the botanical ones, a realistic rendering can be obtained. For this purpose, we introduce a fast leaf drawing algorithm. Our method also seems well adapted for obtaining figurative trees as could be painted by artists.

2. Horton-Strahler analysis for binary trees

2.1. Binary trees and botanical trees

In order to avoid confusion between botanical tree, topological tree or geometrical tree, we recall a few concepts from theoretical computer science, see for example Knuth [18]. A binary tree is defined by a set of vertices or nodes, joined by edges. There are two kinds of vertices : the internal nodes (or branching nodes) and the external nodes (or terminal nodes). Each internal node has two sons : a left and a right son, the external nodes having no sons. An internal node is called the father of its sons. The edges join a father with each of its sons. The root of the tree is the unique node with no father. It will be convenient to add an extra edge from this root, called the root edge (see Figure 1).

To each natural branching pattern, one can associate an underlying topological tree. Generally, this tree can be considered as a binary tree. In botany, the binary tree edges are referred to as branch segments.

2.2. Order and segments

The vertices of a binary tree are labeled by the following recursive procedure. The terminal nodes are labeled 1. If the two sons of a node v are labeled and j, then the label of the node v is ord(v) =max(i,j) ifwtj ; = i+1 ifi=j.

The label ord(e) of an edge e going from the vertex v to one of its sons is the label of y. The label of a node (resp. edge) is called the order of this node (resp. edge) (Figure 1).

Figure 1. Order and Strahler number in a binary tree.

The order of the root edge (that is the order of the root) is called the Strahler number of the tree. A segment of order is a maximal sequence of consecutive edges having order k. The notions of order and segment have been introduced in hydro-geology by Horton [15] (in a slightly different form), and by Strahler [41]. Observe that this concept of order is different from the one usually introduced in the botanical study of trees. In [8] the notion of order is defined from the development history of the tree. When this history is unknown, for each 32

node the distinction between the so-called "straight edge" and "lateral edge", as in [36], is arbitrary. Herein neither development history nor arbitrary convention are required.

2.3. Horton-Strahler analysis in hydrogeology and other sciences.

A river network is supposed to be without islands and triple (or multiple) junction points. Thus, the underlying topological tree is a binary tree. Many studies have been carried out in hydrogeology in order to examine river network morphology. In particular, the concept of bifurcation ratio Bk of order has been introduced. If bk is the number of order segments, then Bk is the ratio IjtlZbk. For example, the binary tree in Figure 1 has bifurcation ratios ?2=8Z2=4, ?3=2Zl=2. These ratios give certain information about the "shape" of the binary tree. For example the trees in Figures 2, 3 are two extreme cases. The perfect tree of height 3 (each terminal node has the same height. Fig. 2) has all segments reduced to the edges: each bifurcation ratio is equal to 2 (this is the minimum possible value). For the very thin tree (Fig. 3) there is one segment of order 2, each terminal edge is a segment of order 1, the bifurcation ratio of order 2 is equal to the number of terminal
Previous << 1 < 2 > 3 4 5 6 7 8 .. 10 >> Next