“Plants, fractals, and formal languages” by Smith

Although fractal models of natural phenomena have received much attention recently, there are other models of complex natural objects which have been around longer in Computer Imagery but are not widely known. These are procedural models of plants and trees. An interesting class of these models is presented here which handles plant growth, sports an efficient data representation, and has a high “database amplification” factor. It is based on an extension of the well-known formal languages of symbol strings to the lesser-known formal languages of labeled graphs. It is so tempting to describe these plant models as “fractal” that the similarities of this class of models with fractal models are explored in an attempt at rapprochement. The models are not fractal so the common parts of fractal theory and plant theory are abstracted to form a class of objects, the graftals. This class may prove to be of great interest to the future of Computer Imagery. Determinism is shown to provide adequate complexity, whereas randomness is only convenient and often inefficient. Finally, a nonfractal, nongraftal family of trees by Bill Reeves is introduced to emphasize some of the paper’s nongrammatical themes.

1. Claus, Volker, Hartmut Ehrig, and Grzegorz Rozenberg (E ditors), Lecture Notes in Computer Science No. 73: Graph-Grammars and Their Application to Computer Science and Biology, Springer-Verlag, Berlin/Heidelberg/New York (1979). Proceedings of the conference held at Bad Honnef, West Germany, October 30-November 3, 1978.
2. Cook, Rob, Loren Carpenter, Thomas Porter, William Reeves, David Salesin, and Alvy Ray Smith, Road to Point Reyes, By the Lucasfilm Computer Graphics Project. Title page picture for SIGGRAPH ’83 Proceedings. July 1983.
3. Ehrig, Harmut, M. Pfender, and H. J. Schneider, “Graph-Grammars: An Algebraic Approach,” pp. 167-180 in Proceedings of 14th Annual Symposium on Switching & Automata Theory (October 1973). Now known as the Symposium on the Foundations of Computer Science.
4. Ehrig, Harmut and H.-J. Kreowski, “Parallel Graph Grammars,” pp. 425-442 in Automata, Languages, Development, ed. Aristid Lindenmayer and Grzegorz Rozenberg, North-Holland Publishing Company, Amsterdam/New York/Oxford (1976).
5. Ehrig, Harmut and Grzegorz Rozenberg, “Some Definitional Suggestions for Parallel Graph Grammars,” pp. 443-468 in Automata, Languages, Development, ed. Aristid Lindenmayer and Grzegorz Rozenberg, North-Holland Publishing Company, Amsterdam/New York/Oxford (1976).
6. Ehrig, Hartmut, “Introduction to the Algebraic Theory of Graph Grammars (A Survey),” pp. 1-69 in Lecture Notes in Computer Science No. 73: Graph-Grammars and Their Application to Computer Science and Biology, ed. Volker Claus, Hartmut Ehrig, and Grzegorz Rozenberg, Springer-Verlag, Berlin/Heidelberg/New York (1979).
7. Fournier, Alain, Don Fussel, and Loren C. Carpenter, “Computer Rendering of Stochastic Models,” Communications of the ACM 25(6), pp. 371-384 (June 1982).
8. Herman, Gabor T. and Grzegorz Rozenberg, Developmental Systems and Languages, North-Holland Publishing Company, Amsterdam/New York/Oxford (1975).
9. Hogeweg, Pauline and B. Hesper, “A Model Study on Biomorphological Description,” Pattern Recognition 6, pp. 165-179, Pergamon Press (1974).
10. Hopcroft, John E. and Jeffrey D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley Publishing Company, Menlo Park, California (1969). The latest edition of this book is entitled Introduction to Automata Theory, Languages, and Computation, 1979, and includes a small section on L-systems.
11. Kawaguchi, Yoichiro, “A Morphological Study of the Form of Nature,” Computer Graphics16(3), pp. 223-232 (July 1982). SIGGRAPH ’82 Proceedings.
12. Lindenmayer, Aristid, “Mathematical Models for Cellular Interactions in Development, Parts I and II,” Journal of Theoretical Biology18, pp. 280-315 (1968).
13. Lindenmayer, Aristid and Grzegorz Rozenberg (Editors), Automata, Languages, Development, North-Holland Publishing Company, Amsterdam/New York/Oxford (1976). Proceedings of the conference held at Noordwijkerhout, The Netherlands, March 31-April 6, 1975.
14. Mandelbrot, Benoit, The Fractal Geometry of Nature, W. H. Freeman and Company, San Francisco (1983). The 1983 printing differs from the 1982 printing by the addition of a small section at the end.
15. Mayoh, Brian H., “Another Model for the Development of Multidimensional Organisms,” pp. 469-485 in Automata, Languages, Development, ed. Aristid Lindenmayer and Grzegorz Rozenberg, North-Holland Publishing Company, Amsterdam/New York/Oxford (1976).
16. Nagl, Manfred, “On a Generalization of Lindenmayer-Systems to Labelled Graphs,” pp. 487-508 in Automata, Languages, Development, ed. Aristid Lindenmayer and Grzegorz Rozenberg, North-Holland Publishing Company, Amsterdam/New York/Oxford (1976).
17. Nagl, Manfred, “A Tutorial and Bibliographical Survey on Graph Grammars,” pp. 70-126 in Lecture Notes in Computer Science No. 73: Graph-Grammars and Their Application to Computer Science and Biology,, ed. Volker Claus, Hartmut Ehrig, and Grzegorz Rozenberg, Springer-Verlag, Berlin/Heidelberg/New York (1979).
18. Paz, Azaria, “Multidimensional Parallel Rewriting Systems,” pp. 509-515 in Automata, Languages, Development, ed. Aristid Lindenmayer and Grzegorz Rozenberg, North-Holland Publishing Company, Amsterdam/New York/Oxford (1976).
19. Reeves, William T., “Particle Systems – A Technique for Modeling a Class of Fuzzy Objects,” ACM Transactions on Graphics2 (2), pp. 91-108 (April 1983).
20. Smith, Alvy Ray, Loren Carpenter, Pat Cole, Tom Duff, Chris Evans, Thomas Porter, and William Reeves, “Genesis Demo,” in Star Trek II: The Wrath of Khan, Paramount (June 1982). Created by the Lucasfilm Computer Graphics Project for Industrial Light and Magic.
21. Smith, Alvy Ray, Loren Carpenter, Ed Catmull, Rob Cook, Tom Duff, Craig Good, John Lasseter, Eben Ostby, William Reeves, and David Salesin, Andre and Wally B., Created by the Lucasfilm Computer Graphics Project. July 1984.
22. Stevens, Peter S., Patterns in Nature, Little, Brown and Company, Boston (1974).
23. Voss, Richard F., Fractal Lunar Mist, Cover picture for SIGGRAPH ’83 Proceedings. July 1983.