MCED Chapter 11
Title
Grammar-Based Models and Fractals
Authors
Winfried Kurth and Dirk Lanwert
Abstract (from the book)
In ecological interactions the three-dimensional structure of organisms can play an important role. We will present an approach for modelling and simulation of the development of geometrical structures in space, which is particularly suitable for representing branching systems as they occur in plants. The related notions of self-similarity and fractality will be briefly discussed. The crucial idea for modelling is to describe the development of a modular structure by rules controlling the replacement of substructures by other substructures. Such replacement systems are also called “grammars”. When the structures are encoded as strings, we speak of L-systems. A more general case are graph grammars, where the transformed structures are networks consisting of nodes and arcs. Loosely following Kurth (2007), we will first show example grammars written down in the programming language XL, which simulate the branching structures of simple plants. The final example, also implemented in XL, is about competition and resulting spatial interaction between plants. All code examples can be tested with the free software GroIMP (“Growth-grammar related Interactive Modelling Platform”).
Additional material
- Detailed description and evaluation of the tree model outlined at the end of the chapter, including its possible usage in e-learning: See Dirk Lanwert’s PhD thesis (2007; in German)
- Homepage of the software GroIMP for rule-based 3-d modelling of organisms (including a gallery of examples), and GroIMP download site
- Course material from the International Summer School “Modelling and Simulation with GroIMP” (Göttingen, Sept. 27 – Oct. 1st, 2010)
- Course material from the M.Sc. (Forest science) lectures “Struktur-Funktions-Modelle von Pflanzen” (W. Kurth, University of Göttingen, semester term Summer 2010; in German)
- Detailed XL language description, mathematical background for graph-grammar based modelling, examples and GroIMP software description in Ole Kniemeyer’s PhD thesis (2008)
Further Reading
- Abelson H, diSessa A A (1982) Turtle Geometry. MIT Press, Cambridge
- Andrieu B (guest ed.) (1999) Architectural modelling of plants. Special issue of: Agronomie 19 (3-4):161-328
- Barnsley M F (1988) Fractals Everywhere. Associated Press, Boston
- Bouchon J, de Reffye Ph, Barthélémy D (eds.) (1997) Modélisation et simulation de l’architecture des végétaux. Science Update, INRA, Paris (435 pp.)
- Buck-Sorlin G, Kniemeyer O, Kurth W (2007) A grammar-based model of barley including virtual breeding, genetic control and a hormonal metabolic network. In: Vos et al. (2007), 243-252.
- Cournède P-H (2009) Système dynamique de croissance des plantes. HDR thesis, Université Montpellier II
- Edgar G A (1990) Measure, Topology, and Fractal Geometry. Springer, New York
- Fourcaud Th, Zhang X, Stokes A, Lambers H, Körner Ch. (guest eds.) (2008) Plant growth modelling. Special issue of: Annals of Botany 101 (8):1053-1293
- Frijters D, Lindenmayer A (1974) A model for the growth and flowering of Aster novae-angliae on the basis of table <1,0> L-systems. In: Rozenberg G, Salomaa A (eds) L-systems. Springer, Berlin, 24-52
- Godin Ch, Sinoquet H (guest eds.) (2005) Functional-structural plant modelling. Featured in: New Phytologist 166 (3):705-708 and 771-894
- Goel NS, Rozehnal I (1991) Some non-biological applications of L-systems. International Journal of General Systems 18 (4):321-405+color plates
- Guo Y, Ma Y, Zhan Z, Li B, Dingkuhn M, Luquet D, de Reffye P (2006) Parameter optimization and field validation of the functional-structural model GreenLab for maize. Ann. Bot. 97:217-230
- Hanan J, Prusinkiewicz P (guest eds.) (2008) Functional-structural plant modelling. Special issue of: Funct. Plant Biol. 35 (9/10):i-iii and 739-1090
- Harvey B (1997) Computer Science Logo Style, 2nd edn. 3 volumes. MIT Press, Cambridge, MA. Also available under http://www.cs.berkeley.edu/~bh/ (accessed Feb. 14, 2011)
- Hemmerling R, Smoleňová K, Kurth W (2010) A programming language tailored to the specification and solution of differential equations describing processes on networks. In: Dediu AH, Fernau H, Martín-Vide C (eds.): Language and Automata Theory and Applications. Proceedings of LATA 2010, Trier, Germany, May 24-28, 2010. Lecture Notes in Computer Science 6031, Springer, Berlin etc., pp. 297-308
- Herman GT, Schiff GL (1975) Simulation of multi-gradient models of organisms in the context of L-systems. J. Theor. Biol. 54:35-46
- Hogeweg P, Hesper B (1974) A model study on biomorphological description. Pattern Recognition 6:165-179
- Hu B-G, Jaeger M (eds.) (2003) Plant growth modeling and applications. Proceedings – PMA03. Tsinghua University Press, Beijing / Springer, Berlin (435 pp.)
- Karwowski R, Prusinkiewicz P (2003) Design and implementation of the L+C modeling language. Electronic Notes in Theoretical Computer Science 86 (2) 19 pp. http://algorithmicbotany.org/papers/l+c.tcs2003.pdf (accessed Feb. 14, 2011)
- Kastner-Maresch A, Kurth W, Sonntag M, Breckling B. (eds.) (1998) Individual-based structural and functional models in ecology. Bayreuther Forum Ökologie 52 (243 pp.)
- Kniemeyer O, Buck-Sorlin G, Kurth W. (2004) A graph-grammar approach to Artificial Life. Artificial Life 10 (4):413-431
- Kniemeyer O (2008) Design and implementation of a graph-grammar based language for functional-structural plant modelling. Doctoral dissertation, BTU Cottbus, 432 pp. http://nbn-resolving.de/urn/resolver.pl?urn=urn:nbn:de: kobv:co1-opus-5937
- Kurth W (2007) Specification of morphological models with L-systems and relational growth grammars. Image – Journal of Interdisciplinary Image Science 5 / Themenheft. http://www.uni-forst.gwdg.de/~wkurth/cb/html/ima_lsy.pdf (accessed Feb. 14, 2011)
- Kurth W, Sloboda B (2001) Sensitive growth grammars specifying models of forest structure, competition and plant-herbivore interaction. Proc. IUFRO 4.11 Congress, Greenwich, UK, June 25-29, 2001. http://www.uni-forst.gwdg.de/~wkurth/cb/html/gree_tx.pdf (accessed Feb. 14, 2011)
-
Lanwert D (2007) Funktions- / Strukturorientierte Pflanzenmodellierung in E-Learning-Szenarien. Doctoral dissertation, Universität Göttingen, 209 pp. http://webdoc.sub.gwdg.de/diss/2008/lanwert/ (accessed Feb. 14, 2011)
-
LeRoux X, Sinoquet H (guest eds.) (2000) 2nd international workshop on functional-structural tree models. Special issue of: Annals of Forest Science 57 (5/6):393-621
-
Li B, Jaeger M, Guo Y (eds.) (2010) Plant Growth Modeling, Simulation, Visualization and Applications. Proceedings – PMA09, Beijing (China) 9-13 Nov. 2009. IEEE, Los Alamitos (454 pp.)
-
Lindenmayer A (1968) Mathematical models for cellular interactions in development. J. Theor. Biol. 18:280-315
-
Mandelbrot B (1977) The Fractal Geometry of Nature. W. H. Freeman, N.Y.
-
Monsi M, Saeki T (1953) Über den Lichtfaktor in den Pflanzengesellschaften und seine Bedeutung für die Stoffproduktion. Japanese Journal of Botany 14: 205-234
-
NVIDIA Corp. (2006) DirectX 10: The next-generation graphics API. Technical brief. http://forum.greycomputer.de/download/handbuecher/nvidia/nvidia_ microsoft_directx-10_technical_brief.pdf (accessed Feb. 6, 2010)
-
Peitgen H-O, Richter PH (1986) The Beauty of Fractals. Springer, Berlin
-
Pfreundt J (1988) Modellierung der räumlichen Verteilung von Strahlung, Photosynthesekapazität und Produktion in einem Fichtenbestand und ihre Beziehung zur Bestandesstruktur. Doctoral dissertation, Universität Göttingen
-
Pfreundt J, Sloboda B (1996) The relation of local stand structure to photosynthetic capacity in a spruce stand: a model calculation. Lesnictví / Forestry 42:149-160
-
Prusinkiewicz P (1987) Applications of L-systems to computer imagery. Lecture Notes in Computer Science 291:534-548
- Prusinkiewicz P, Lindenmayer A (1990) The algorithmic beauty of plants. Springer, New York. http://algorithmicbotany.org/papers/abop/abop.pdf (accessed Feb. 14, 2011)
- Room PM, Hanan JS (1995) Virtual cotton: A new tool for research, management and training. In: Constable GA, Forrester NW (eds) Challenging the Future. CSRIO Australia, 40-44
- Rozenberg G (1973) T0L systems and languages. Information and Control 23:357-381
- Rozenberg G (1997) Handbook of Graph Grammars and Computing by Graph Transformations. Vol. 1: Foundations. World Scientific, Singapore
- Sievänen R, Mäkelä A, Nikinmaa E (guest eds.) (1997) Functional-structural tree models. Special issue of: Silva Fennica 31 (3):237-380
-
Sloboda B, Pfreundt J (1989) Baum- und Bestandeswachstumsprozess. Ein systemanalytischer Ansatz mit Versuchsplanungskonsequenzen für die Durchforstung und Einzelbaumentwicklung. Bericht der Jahrestagung der Sektion Ertragskunde im Deutschen Verband Forstlicher Forschungsanstalten, Attendorn 1989, pp. 17/1-17/25
-
Smith AR (1984) Plants, fractals, and formal languages. Computer Graphics (ACM/SIGGRAPH) 18 (3):1-10
-
Tunbridge A, Jones H (1995) An L-systems approach to the modelling of fungal growth. The Journal of Visualization and Computer Animation 6 (2):91-107
-
Vos J, Marcelis LFM, de Visser PHB, Struik PC, Evers JB (eds.) (2007) Functional-structural plant modelling in crop production. Springer, Dordrecht (269 pp.)
Links
Several software systems exist which can be used to explore the possibilities of fractals and L-systems and to create virtual plants. One of the oldest tools is
- Fractint (http://www.fractint.net).
It does not only include a simple L-system interpreter, but also other algorithms for generating fractal structures.
developed by Christoph Streit, was one of the first tools specializing on L-systems and was later used in an agronomical application. A more advanced tool,
was developed by Laurens Lapré.
- LStudio (http://algorithmicbotany.org/lstudio)
from P. Prusinkiewicz’s team is one of the most widely used L-system software tools, with numerous applications in functional-structural plant modelling.
contains not only an L-system interpreter, but also several tools for analysing branching systems of trees. Meanwhile, most of its functions are also available in the open-source system
- GroIMP (http://www.grogra.de),
developed by Ole Kniemeyer et al. (2004), which offers an advanced, interactive graphics display and an XL compiler.
by Christophe Pradal, is an open-source system designed to compose submodels and tools from different sources in order to create complex models of plants and ecosystems.
General Webpages on L-systems, fractals and functional-structural plant models
L-systems
- Wikipedia (en.): “L-system“
- Wikipedia (dt.): “Lindenmayer-System” (in German)
- interactive JavaView tool for L-systems
- An introduction to Lindenmayer systems (University of Hamburg)
- GroIMP homepage (software for interpreting extended L-systems)
Fractals
- Wikipedia (en.): “Fractal“
- Wikipedia (dt.): “Fraktal” (in German)
- Fractalizer graphics tool
- Wolfram MathWorld / Fractal
- FractalForge free software
Functional-structural plant models
- 6th International Workshop on Functional-Structural Plant Models (Davis, Cal., Sept. 12-17, 2010)
- Review paper by J. Vos et al. (2009) on FSPM
- J. Hanan, P. Prusinkiewicz: Studying plants with functional-structural models (2008).
Project web pages linked to functional-structural plant modelling
- UMR AMAP (Montpellier, France)
- Biological Modeling and Visualization Research Group (University of Calgary, Canada)
- LIGNUM tree model (METLA, Vantaa, Finland)