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 9 .. 10 >> Next

We also have chosen analog aesthetic effects and a certain amount of realism for the choice of the angle laws Q1 and 02. The principal idea is that the main branches should have a smaller deviation with respect to their rrtother branches than the less important branches of the tree. In our model, the importance of a branch is measured by its order. We have thus used the following laws :

For a branching node with biorder (k-l,k-l), that is a fork, the two resulting branches have the same importance, and we set O1=O2=Ot, a real constant.

For a branching node with biorder (k,i), i<k, then the respective deviation angles Gm and Gj of the main and secon-dary branches with their mother branch (see Figure 8) are given by

9m(k,i) = cm*i/(k-l), 0,(k,i) = c,*(k-i) /(k-1) where cm and c, are some numerical constants.

biorder (k-1,k-1) biorder (k,i), k<i

Figure 8. Angles Gr 9m, Qj as functions of the biorder.

Good visual effects can be obtained with Cj and 9t equal 30 and cm equal 10. Of course it is possible to adopt any other kind of parameterization, depending on the final visual effects one desires.

For 2D drawing, these definitions are sufficient for defining the (elementary) geometry of the tree. The coordinates of each node of the tree can be computed using length and angle parameterizations. As most of our pictures are given in 2D, we do not insist in the choice of the phyllotaxy angle 93. There are no natural reasons to make this angle depend on the order of the mother branch. 4.4. 2D-drawing

For the purpose of quicker drawing, and also for a better understanding of the influence of the choice of the ramification matrix, we have simplified the drawing algorithm.

Once the coordinates of each node have been computed, each edge of the underlying binary tree is represented by a line segment. This edge is visualized on the screen by a rectangle. The junction between the rectangles corresponding to a branching node is organized as shown in Fig 9.

First filling triangle left edge

Second filling triangle right edge

Figure 9. Jonction between branches represented by rectangles.

In the drawing of Figure 10 (end of the paper), some rectangles have not been filled up. This is to show that, when the length or width of some edges is very small (a few pixels or under the size of a pixel) the tree may have many more branching nodes than those visualized on the screen (more than 1000 for the binary tree related to this figure). Figures 10, 20 give examples of two different geometric laws for the width of the branches: exponential and polynomial.

5. Relationship between form and ramification matrix

The ramification matrix is relative to the topological binary tree underlying the geometrical tree. The "shape" or "form" of

34 Computer Graphics, Volume 23, Number 3, July 1989

this topological tree, without any geometrical consideration, is obviously a purely abstract concept. The study of the relationship between the ramification matrices and the tree shape can only be made with geometrical trees. It is one of the reasons for which a very simplified geometry (2D geometry, each edge being visualized by a rectangle) has been defined, in order to avoid a too important influence from this geometry upon the relationship study between shapes and matrices. The parameters and geometrical laws chosen for the photos of the trees in this section, are always the same.

5.1. Self-similar matrices

Two typical matrices leading to very different visual results are those given by above given Tables 3 & 4, i.e. the ramification matrices of random binary trees and of random increasing binary trees. In the first case (Figure 11) we obtain rather airy trees with a slender or bushy shape, with a few long segments where many thorns are settled, i.e. branching nodes of biorder (k,l) (these thorns are too small to be seen in the photo in Fig. 11). The thorns and the small subtrees associated to the biorder (k,2) concentrate 75% of the biorder probabi-lities. The second matrix gives rise to a family of trees which contains many more important branches and are more well balanced (Fig. 12). In this matrix, 60% to 70% of biorder probabilities are concentrated on the 2 last values (diagonal and sub-diagonal).The "well-balanced" aspect is due to the high probability of the biorder (k-1,k-1) giving rise to many forks (however without reaching the totally well-balanced aspect of the perfect tree). Very few thorns or small subtrees appear on high order branches.

The matrix of Table 6 is similar to the one of random increasing binary trees, except for the biorders (k-1,k-1) whose probability has mainly been reduced, while maintaining a high probability for the biorders (k,k-l). This matrix looks like a self-similar one (at least for the orders > 4). This leads to quite well-balanced trees (Fig. 13), with few forks and then long segments of constant order (and then of constant thickness). These long segments appear at all levels of the tree (for all the orders).
Previous << 1 .. 2 3 4 < 5 > 6 7 8 9 .. 10 >> Next