Combinatorial analysis of ramified patterns and computer imagery of trees

ABSTRACT

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.

REFERENCES

• 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: Jules Bloomenthal, Modeling the mighty maple, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.305-311, Jul. 1985
• 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: Stephen Demko , Laurie Hodges , Bruce Naylor, Construction of fractal objects with iterated function systems, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.271-278, Jul. 1985
• 8: Phillippe de Reffye , Claude Edelin , Jean Françon , Marc Jaeger , Claude Puech, Plant models faithful to botanical structure and developmentr, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.151-158, June 1988
• 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: Geoffrey Y. Gardner, Simulation of natural scenes using textured quadric surfaces, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.11-20, July 1984
• 12: Mark Green , Hanqiu Sun, Interactive Animation: A Language and System for Procedural Modeling and Motion, IEEE Computer Graphics and Applications, v.8 n.6, p.52-64, November 1988 [doi>10.1109/38.20318]
• 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: Yoichiro Kawaguchi, A morphological study of the form of nature, Proceedings of the 9th annual conference on Computer graphics and interactive techniques, p.223-232, July 26-30, 1982, Boston, Massachusetts, United States
• 17: Kemp, R. The average number of registers needed to evaluate a binary tree optimally. Acta Infor. 11 (1979), 363-372.
• 18: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 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: Robert Marshall , Rodger Wilson , Wayne Carlson, Procedure models for generating three-dimensional terrain, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.154-162, July 14-18, 1980, Seattle, Washington, United States
• 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: Karl J Niklas, Computer-simulated plant evolution, Scientific American, v.254 n.3, p.78-86, March 1986
• 31: Peter E. Oppenheimer, Real time design and animation of fractal plants and trees, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.55-64, August 1986
• 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: P Prusinkiewicz, Graphical applications of L-systems, Proceedings on Graphics Interface '86/Vision Interface '86, p.247-253, August 1986, Vancouver, British Columbia, Canada
• 36: Przemyslaw Prusinkiewicz , Aristid Lindenmayer , James Hanan, Development models of herbaceous plants for computer imagery purposes, Proceedings of the 15th annual conference on Computer graphics and interactive techniques, p.141-150, June 1988
• 37: William T. Reeves , Ricki Blau, Approximate and probabilistic algorithms for shading and rendering structured particle systems, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.313-322, Jul. 1985
• 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: Alvy Ray Smith, Plants, fractals, and formal languages, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.1-10, January 1984
• 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.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.5 ARTS AND HUMANITIES
      Subjects: Arts, fine and performing**

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms