Alvy Ray Smith
Abstract
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. Google Scholar
Digital Library
- 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.Google Scholar
- 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.Google Scholar
- 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).Google Scholar
- 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).Google Scholar
- 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). Google ScholarDigital Library
- 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). Google ScholarDigital Library
- 8 Herman, Gabor T. and Grzegorz Rozenberg, Developmental Systems and Languages, North-Holland Publishing Company, Amsterdam/New York/Oxford (1975). Google ScholarDigital Library
- 9 Hogeweg, Pauline and B. Hesper, "A Model Study on Biomorphological Description," Pattern Recognition 6, pp. 165-179, Pergamon Press (1974).Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 11 Kawaguchi, Yoichiro, "A Morphological Study of the Form of Nature," Computer Graphics16(3), pp. 223-232 (July 1982). SIGGRAPH '82 Proceedings. Google ScholarDigital Library
- 12 Lindenmayer, Aristid, "Mathematical Models for Cellular Interactions in Development, Parts I and II," Journal of Theoretical Biology18, pp. 280-315 (1968).Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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).Google Scholar
- 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).Google Scholar
- 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). Google ScholarDigital Library
- 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).Google Scholar
- 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). Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 22 Stevens, Peter S., Patterns in Nature, Little, Brown and Company, Boston (1974).Google Scholar
- 23 Voss, Richard F., Fractal Lunar Mist, Cover picture for SIGGRAPH '83 Proceedings. July 1983.Google Scholar
Index Terms
- Plants, fractals, and formal languages
Recommendations
Plants, fractals, and formal languages
SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniquesAlthough 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 ...
Plant models faithful to botanical structure and development
SIGGRAPH '88: Proceedings of the 15th annual conference on Computer graphics and interactive techniquesSome very impressive results have been obtained in the past few years in plants and trees image synthesis. Some algorithms are largely based on the irregularity and fuzziness of the objects, and use fractals, graftals or particle systems. Others focus ...
Plant models faithful to botanical structure and development
Some very impressive results have been obtained in the past few years in plants and trees image synthesis. Some algorithms are largely based on the irregularity and fuzziness of the objects, and use fractals, graftals or particle systems. Others focus ...
Comments