“Combinatorial analysis of ramified patterns and computer imagery of trees” by Viennot, Eyrolles, Janey and Arqués

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.

1. Aono M., and Kunii T.L. Botanical tree image generation, IEEE Computer Graphics & Apphcations 4,5 (1984),I0-34.
2. Ball, R.C. DLA in the real world, in On growth and form: fractal and non-fractal patterns in Physics, Stanley, H.E., and Ostrowski, N., eds., Martinus Nijhoff, Boston (1986) 69-78.
3. Beyer, T., and Friedel. M. Generative scene modelling. Proceeding of EUROGRAPHICS ’87 (1987),151-158 & 571.
4. BloomenthaI, J. Modeling the Mighty Maple. Proceedings of SIGGRAPH ’85 (San Francisco, CA, July 22-26, 1985). In Computer Graphics 19, 3 (1985), 305-311,
5. Cole, V,C. The artistic anatomy of trees. Dover Publication, N-Y (1965) (orginally Seely Servi & Co., Load., 19 I5).
6. D’Arcy Thompson, W. On growth and form. University Press, Cambridge, 2rid ed., (1952).
7. Demko, S., Hodges, L., and Naylor, B. Construction offractal objects with iterated function systems. Proceedings of SIGGRAPH ’85 (San Francisco, CA, July 22-26, 1985). In Computer Graphics 19, 3 (I985), 271-278.
8. De Reffye, P., Edelin, C., Franqon, J., Jaeger, M., Puech, C. Plant Models Faithful to Botanical Structure and Development. Proceedings SIGGRAPH ’88 (Atlanta, August 1-15, 1988). Computer Graphics 22, 4(1988),151-158,
9. Eyrolles G. Synth~se d’images figuratives d’arbres par des rndthodes combinatoires. Ph.D. Thesis, Un. Bordeaux I 1986
10. Flajolet, P., Raoult, J.C., and Vuillemin, J. The number of registers required for evaluating arithmetic expressions. Theor. Computer Science 9 (1979) 99-125.
11. Gardner, G., Simulation of natural scenes using textured quadric surfaces. Computer Graphics 18, 3 (1984).
12. Green, M., and Sun, H. A 1engage and system for procedural modeling and motion. IEEE Comp. Graph. & Ap. , (1988) 52-64.
13. Hail6 F., Oldeman R., and Tomlinson P. Tropical trees and forests: an architectural analysis. Springer Berlin 1978,
14. Honda, H. Description of the form of trees by the parameters of the tree-like body: effects of the branching angle and the branch length of the shape of the tree-like body, J. Theor. Biol. 31 (1971), 331-338.
15. Horton, R.E. Erosioned development of systems and their drainage basins, hydrophysical approach to quantitative morphology. Bull. Geol. Soc. America 56 (1945), 275-370.
16. Kawaguchi, Y. A morphological study of the form of nature. Proceedings of SIGGRAPH ’82 (July 1982). In Computer Graphics 16, 3 (1982), 223-232.
17. Kemp, R. The average number of registers needed to evaluate a binary tree optimally. Acta Infor. 11 (1979), 363-372.
18. Knuth, D.E. The Art of Computer Programming. col. 3, Addison-Wesley, Reading (1973).
19. Leopold, L.B. Trees and streams: the efficency of branching patterns, J. Theor. Biol. 31 (1971), 339-354.
20. Lienhardt, P. Moddlisation et gvolution de surfaces libres. Ph.D. Thesis, Univ. Louis Pasteur, Strasbourg (1987).
21. Lienhardt P. & Franqon J.Vegetal leaves synthesis. Proc. COGNITIVA’87 (Paris La Villette,May 18-22,1987)212-18.
22. MacMahon, T.A. The mechanical design of trees. Scientific American 233 (1975), 92-102.
23. Mandelbrot, B, The fractal geometry of nature. Freeman & Co., San Francisco (1982).
24. Marshall, R., Wilson, R., and Carlson, W. Procedure models for generating three-dimensional terrain. SIGGRAPH ’80, Computer Graphics 14, 3 (July 1980), 154-162.
25. Meier A., Moon J.W. & Pounder J.R. On the order of random channel networks. SIAM J. Alg. Disc. Mat. 1 (I 980) 25-33.
26. Mendes-France M., De l’arbre de Leonardo da Vinci d la thdorie de la dimension. Rev. du Palais de la D6couverte, Paris, 10 (1981), 52-60.
27. Naudin, J.J., and Prud’homme, R, Mdthodes d’analyse morphologiques et morphostructurales d’interprdtation des topogra.phies et des bathymdtries dans les domaines continentaux matins. Bull. de l’Inst, de Gdologie du Bassin D’Aquitaine 10 (1971) 111-114
28. Niemeyer, L., Pietronero, L., and Wiesmann, A.J. Fractal structure of dielectric breakdown patterns. Phys. Rev. Letters 52 (1984) 1033.
29. Nittmann, J,, Daccord, G., and Stanley, H.E. Fractal growth of viscous fingers. Nature 314 (1985) 141-144.
30. Niklas, K.J,, Computer-simulated plant evolution. Scientific American (1986) 78-86.
31. Oppenheimer, P. Real time design and animation of-f rectal plants and trees. Proceedings of SIGGRAPH ’86 (Dallas, Texas, August 18-22, 1985). In Computer Graph. 20, 4 (1986), 55-64.
32. Penaud, J.G. The ramification matrix of random binary trees. Research report, LABRI n~ 8832 , D6partement d’Informatique, Universit6 de Bordeaux I (1988).
33. Percheron, G., Principles and methods of the graph theoretical analysis of natural binary arborescences. J. Theor. Biology 99 (1982) 509-552.
34. Prud’homme, R., and Vigneaux, M. Mdthodes rnorphologiques et morphostructurales appliquies d l’dtude des rdseau.x hydrographiques du Bordelais. Revue gfographique des Pyr~n6es du Sud-Ouest 41 (t970), 5-14.
35. Prusinkiewicz P.Graphical applications of L-systems. Proc. of Graphics Interface ’86-Vision Interface’86 (1986),247-53
36. Prusinkiewicz, P., Lindenmayer, A., and Hanan, J. Developmental models of herbaceous plants for computer imagery purposes. Proceedings of SIGGRAPH ’88 (Atlanta, August 1-15, 1988).In Computer Graph. 22, 4(1988), 141-150.
37. Reeves, W.T. & Blau, R.Approximate and probabilistic algorithms for shading and rendering structured particle systems Proceedings of SIGGRAPH ’85 (San Francisco, CA, july 22-26, 1985).In Computer Graphics 19, 3 (1985), 313-322.
38. Sawada, Y., Dougherty, A., and Gollub, J.P. Dentritic and fractal patterns in electrolytic metal deposits. Phys. Review Letters 56 (I 986) 1260-t263.
39. Smith, A.R., Plants, fractals, and formal languages. Proceedings of SIGGRAPH ’84 (Minneapolis, Minnesota, July 23-27, 1984). Computer Graphics 18, 3 (1984), 1-10.
40. Stevens, P.S. Patterns in Nature. Little, Brown & Co., Boston (1974).
41. Strahler, A.N.Hypsometric (area-altitude) analysis of erosional topology. Bull. Geol. Soc. Amer. 63 (1952) 1117-42.
42. VanDamme, H., Obrecht, F., Levitz, P., Gatineau, L., Laroche, C. Nature 320 (1986), 73 I.
43. Vannimenus, J., On the shape of trees: tools to describe ramified patterns. Proc. sum. school in Theor. Physics, Les Houches (1987).
44. Vannimenus, J., and Viennot, X.G. Combinatorial Tools for the Analysis of Ramified Patterns. J. Star. Physics, 54 (I989) 1529-1538.
45. Vauchaussade de Chaumortt, M., artd Viennot X.G. Enumeration of RNAs secondary structures by complexity, in Mathematics in Medecine and Biology, Lecture Notes in Biomathematies n~57, Capasgo, V., Grosso, E., and Paven- Fontana, S.L., eds., Springer-Verlag, Berlin (1985), 360-365.
46. Witten, T.A., and Sanders, L.M. Phys. Rev. 47 (1981) 1400.
47. Woldenberg, M.J. A structural taxonomy of spatial hierarchies, in Colston papers,v. 22,Butterworth Sci. Publ., London (1970) 147-175.