Procedural Modelling of Plant Scenes

Short Paper Draft

Computer Science Honours Project

Author: Kim Randleff-Rasmussen

00R1008

Supervisors: Shaun Bangay

Adele Lobb

This paper describes the development of a procedural model for the creation of complex plant scenes such as forests and jungles. The aim is to use the widespread technique of L-Systems to model the plants as this will mean that any aspect of the plant growth can be rendered without intensive modelling work by the animator.

The aim is to model realistic complex organic environments by modelling not only the inhabitants of these environments but also the interactions between same. These interactions are modelled using a domination algorithm which stunts the growth of plants which are encroaching on the space of others. This same algorithm allows for the dynamic addition and removal of plants to and from the population.

Previous work in the fields of plant modelling in general, L-Systems in particular and procedural modelling is described in Section 2. The specific approaches chosen, as well as the reasons for these choices, are explained in Section 3, where the coding environment is also introduced. Section 4 looks at results that have been achieved thus far, and Section 5 looks at possible extensions to the final project.

Many techniques have developed over the years to model plant structure and growth, such as the mathematical model developed by de Reffye et al. [1988] which formalises known botanical rules. Other models focus on specific geometric phenomena such as [Borchert and Honda 1984] which models the tendency of a tree to increase the vigour of growth after the loss of a branch.

[Meyerowitz 1994], [Janssen and Lindenmayer 1987] and [Borchert and Slade 1981] use specific species to create their models. A comprehensive study of various species can be found in [Hallé et al. 1978]. This book asserts that the thousands of plant species in the world can be modelled using a mere twenty-three models.

Environmental influences obviously have a tremendous effect on plant growth and shape. [Prusinkiewicz et al. 2000] looks at the effect of gravity on the branching behaviour of certain trees while [Prusinkiewicz et al. 1994] looks at pruning – forced and self-imposed – and how this affects branch growth. [Prusinkiewicz et al. 2001] uses positional information to model the growth and survival of a plant. This model uses such techniques as self-thinning and competition for space to model how tree growth is affected by environmental factors. [Honda et al. 1981] focuses on how interaction between individuals affects branching and [Sorrensen-Cothern et al. 1993] looks at interaction between modules of a single individual. [Weber and Penn 1995] introduces a number of rules which ease the creation of models of various species of plants.

L-Systems (Lindenmayer Systems, named for Hungarian biologist Aristid Lindenmayer) were developed in 1968 as a method for representing biological growth [Lindenmayer 1968]. They are replacement languages which use defined production rules to supplant symbols within a string. Each symbol in the strings represents an addition or change to the graphical representation of the organism the string describes.

The most common interpretation of L-System symbols (or modules) is through Turtle graphics. In this case, a basic L-System alphabet consists primarily of:

F(s) Move forward a step of length s and draw a line segment from the original to the new position of the turtle

[ Push the current state of the turtle (position, orientation and drawing attributes) onto a pushdown stack

] Pop a state from the stack and make it the current state of the turtle. No line is drawn although in general the position and orientation of the turtle are changed

Other letters and symbols may also be used to delineate areas for string replacement.

Another important element of L-Systems is the production rules which specify what symbols are to be replaced by which strings at each iteration step. Due to this recursive process, L-Systems are a succinct language for describing the growth of organic material such as plants. The production rules have the following structure:

where lc is the left-hand context, rc the right-hand context, pred the predecessor (the symbol to be replaced), cond a condition and succ the successor (the string to replace the predecessor). The rule is only run (i.e. the symbol replaced by the successor) if the condition evaluates to true. prob is a number which defines the probability of the rule being chosen. This is only found in stochastic L-Systems where more than one rule can exist for each symbol. Only the predecessor and the successor are compulsory.

For example, an L-System may comprise an axiom F and a replacement rule F à F[>F][<F]F. A first pass of the L-System will yield a new string F[>F][<F]F where the original F has been replaced. A second pass will yield F[>F][<F]F [>F[>F][<F]F][< F[>F][<F]F] F[>F][<F]F where each F in the second string is replaced by the successor of the rule.

Many extensions to basic L-Systems have also been developed to add greater functionality to the basic technique. Table L-Systems were developed by Rosenberg [1973] to allow different production rules to be chosen according to certain environmental factors. Prusinkiewicz et al. [1994] developed another type of L-System – environmentally sensitive L-Systems – which uses query symbols (?E(parameters)) to provide environmental information to the plants. In [Prusinkiewicz and Mĕch 1996], bilateral communication was added which allows the plant to return information to the environment.

Other extensions allow for more than one individual plant to be modelled from the same L-System. The introduction of parametric L-Systems [Prusinkiewicz et al. 1995] allows certain aspects of the model to be changed dynamically, such as angle size and segment length. Differential L-Systems (or dL-Systems) [Prusinkiewicz et al. 1993] extend these parametric L-Systems by incorporating continuous time flow which allows for smooth animation of plant development.

Stochastic L-Systems [Eichhorst and Savitch 1980] use multiple productions for each symbol, the specific rule being chosen according to assigned probabilities. This functionality allows a single L-System to create a number of individual plants with the same basic shape but different to one another – the L-System would describe the species and the many incarnations represent the individual members of that species. Erasing productions [Herman and Rozenberg 1975] also allows individual variation within a single model.

The addition of genetic algorithms [McCormack 1993], mutation [Mock 1998] and evolution [Rodkaew et al. 2002] into L-Systems has allowed for realistic modelling of plant development over long periods of time. Extrusion in space-time [Hammel and Prusinkiewicz 1996] extends a two-dimensional structure’s development into a three-dimensional line or curve which represents the progress of time.

L-Systems have also been used to model entire plant populations. An example of this use can be found in [Prusinkiewicz and Lane 2002] which introduces multi-set L-Systems which allow for production rules to be applied to a set of strings instead of to a single string.

Procedural modelling is a computer graphics technique designed to decrease the computational power required to render a geometrically complex scene. It does so by improving on two areas of scene rendering, Firstly, objects that are not within the view spectrum of the camera are not rendered [Foley 1996]. Secondly, elements of the model are rendered according to the level of detail required. For example, a knot on a tree trunk would only be visible from a metre or less away from the tree and not from a distant shot.

[Amburn et al. 1986] suggests a number of ways in which traditional procedural models might be improved. One of these techniques is communication between models which may affect one another that models may adjust their behaviour according to messages from another model. The second improvement is subdivision of labour and the sharing of some subdivided activities between procedures.

Procedural modelling has long been in use in programs which model geometrically complex scenes such as forests, cities and crowds. Large cities, for example, have been procedurally modelled in [Birch et al. 2003], [Greuter et al. 2003], [Parish and Müller 2001] and [Wonka et al. 2003]. In terms of forest or landscape generation, some prominent projects can be found in [Guerraz et al. 2003] and [Deussen et al. 1998].

The basis of procedural modelling is to have all of the complex geometry needed in a scene generated by a procedure. In this procedural model, the entire forest is modelled by a single procedure (forest). Within this procedure, only the placement and size of the plants is calculated. The actual geometry generation is delegated to another procedure (lsystem) which, in turn, delegates the generation to another (segment). This technique means that large scenes can be developed and modelled quickly and efficiently as the geometry generation is only tackled after the other calculations.

Each procedure is supplied with the Transformation matrix from the calling procedure. Along with this, the procedure is also supplied with a long integer random key which can be used to seed a pseudo-random number sequence. It is useful to use the same number to seed the sequence so that the exact same forest can be generated provided the key is known.

A R p replacement rule (A is the symbol to replace, R the string to replace it with and p is a double value which signifies the probability of the rule).

[, ] Push and pop the current state as in the alphabet seen above (Section 2.2).

L-System strings are stored in a defined LSystem data structure which allows for easy access to any of the modules within the string and its parameters.

[Prusinkiewicz and Lane 2002] introduces a number of methods by which the placement of plants in a forest can be determined. These methods can be considered to be local-to-global or global-to-local. The latter category contains methods which place individuals according to pre-defined and constantly updated density functions. As each plant is placed, the probability function is updated according to this new placement and the placement of the next plant will be affected.

Local-to-global plant placement methods simulate eco-system interaction by focussing on each individual. Multi-set L-Systems are an example of this type of placement methodology. These L-Systems apply a set of production rules to a set of L-Systems strings (or a plant population). This allows for the dynamic addition and removal of individual plants and the dynamic upkeep of the population as a whole.

[Deussen et al. 1998] mentions two methods for placing plants within a modelled forest. The first of these involves inputting a density map to which an error diffusion algorithm is then applied. The specific algorithm implemented in this paper is one introduced by Floyd and Steinberg. The second method places plants randomly and then iteratively grows or kills individuals based on domination. It is this second method which is used in this project.

[Maierhofer 2002] introduces generalised subdivision meshes. This technique allows for the smoothing of meshes using a combination of a number of common subdivision methods. It also uses procedural modelling to model small scale surface detail. The focal point of the thesis is rule-based mesh growing which applies L-Systems to mesh faces as opposed to symbols.

In the creation of the forest, the plant placements are randomly calculated. These random placements are seeded by the long integer key which is passed to the procedural model (see Section 3.1). This key then seeds the x and z coordinates of the plant to be placed. The same key seeds a random number which determines the L-System to be used in the determined place, and hence, the plant to be planted in the position. Figure 2 shows an example of the random placement of plants that can be generated.

A final random number determines the starting iteration for the plant to be modelled. Later, this number will be increased according to the frame being rendered.

Once the plant placement has been determined, an LSystem must be created and sent to the lsystem procedure for parsing and translation. The creation occurs when a .sys file is read and the full L-System string generated according to the number of iterations. The lsystem procedure then parses this string, changing the Transformation matrix according to the <, >, &, @, %, # and | symbols and calling the segment procedure in response to an F symbol. Figure 1 shows an example of an L-System image and the originating string.

Generalised mesh techniques are implemented in this project in order to create more realistic looking smooth trees. In order to achieve this, a segment is repeatedly smoothed from its original square shape. Figure 3a shows a section of an L-System tree before application of these techniques and Figure 3b shows the same section after smoothing.

Figure 1: The L-System tree generated by the string “F[>F][<F]F[>F[>F][<F]F][<F[>F][<F]F]F[>F][<F]F[>F[>F][<F]F[>F[>F][<F]F][<F[>F][<F]F]F[>F][<F]F][<F[>F][<F]F[>F[>F][<F]F][<F[>F][<F]F]F[>F][<F]F]F[>F][<F]F[>F[>F][<F]F][<F[>F][<F]F]F[>F][<F]F”.

Figure 3: Two versions of the same joint showing the difference between the generated cube (a) and the cube after smoothing (b).

In [Tobler et al. 2002], a method is explained by which texture coordinates from a generated complex mesh are used to displace the vertices. This method allows for grooves and ridges to be added to such complex meshes as trees, thus increasing the realism of the final image. This is a possible extension to the project described above.

Another possible extension is the definition of the L-System files using a grammar definition language such as COCO/R. This would be relatively easy to implement and would streamline the process of parameter finding and symbol replacement.

1. Amburn, P., Grant, E. and Whitted, T. 1986. Managing Geometric Complexity with Enhanced Procedural Models. SIGGRAPH 1986 Conference Proceedings, pp. 189-195

2. Birch, P., Browne, S., Jennings, V., Day, A. and Arnold, D. 2003. Rapid Procedural Modelling of Architectural Structures. SIGGRAPH 2003 Conference Proceedings

3. Borchert, R. and Honda, H. 1984. Control of development in the bifurcating branch system of Tabebuia rosea: A computer simulation. Botanical Gazette 145(2), pp. 184–195

4. Borchert, R. and Slade, N. 1981. Bifurcation ratios and the adaptive geometry of trees. Botanical Gazette 142(3), pp. 394–401

5. de Reffye, P., Edelin, C., Françon, J., Jaeger, M. and Puech, C. 1988. Plant Models Faithful to Botanical Structure and Development. Computer Graphics 22(4), pp. 151-158

6. Deussen, O., Hanrahan, P., Lintermann, B., Mĕch, R., Pharr, M. and Prusinkiewicz, P. 1998. Realistic Modeling and Rendering of Plant Ecosystems. SIGGRAPH 1998 Conference Proceedings

7. Eichhorst, W. and Savitch, J. 1980 Growth Functions of Stochastic Lindenmayer Systems. Information and Control 45(3), pp. 217-228

8. Foley, D. 1996. Computer Graphics Principles and Practice Second Edition. Addison-Wesley: Reading, Massachusetts

9. Greuter, S., Parker, J., Stewart, N. and Leach, G. 2003. Undiscovered Worlds. melbourneDAC - 5th International Digital Arts and Culture Conference

10. Guerraz, S., Perbet, F., Raulo, D., Faure, F. and Cani, M. 2003. A Procedural Approach to Animate Interactive Natural Sceneries. CASA03

11. Hallé, F., Oldeman, R. and Tomlinson, P. 1978. Tropical trees and forests. Springer-Verlag: Heidelberg, New York.

12. Hammel, M. and Prusinkiewicz, P. 1996. Visualization of developmental processes by extrusion in space time. Proceeding of Graphics Interface '96, pp. 246-258

13. Hanan, J. 1992. Parametric L-systems and their application to the modelling and visualization of plants. PhD thesis, University of Regina, Canada

14. Herman, G. and Rozenberg, G. 1975 Developmental systems and languages. North-Holland: Amsterdam

15. Honda, H., Tomlinson, P. and Fisher, J. 1981. Computer simulation of branch interaction and regulation by unequal flow rates in botanical trees. American Journal of Botany 68, pp. 569–585

16. Janssen, J. and Lindenmayer, A. 1987. Models for the Control of Branch Positions and Flowering Sequences of Capitula in Mycelis muralis (L.) Dumont (Compositae). New Phytologist 105(2), pp. 191-220

17. Lindenmayer, A. 1968. Mathematical Models for Cellular Interaction in Development. Journal of Theoretical Biology

18. Macri, D. and Pallister, K. 2004. Procedural 3D Content Generation. Technical report. Intel Developer Service

19. Maierhofer, S. 2002. Rule-Based Mesh Growing and Generalised Subdivision Meshes. Doctoral Thesis Dissertation. Vienna University of Technology, Austria

20. McCormack, J. 1993. Interactive Evolution of L-System Grammars for Computer Graphics Modelling. In: Green, D. and Bossomaier, T. (Eds.): Complex Systems: from Biology to Computation, ISO Press: Amsterdam, pp. 118-130

21. Meyerowitz, E. 1994. The genetics of flower development. Scientific American 271(5), pp. 56–65

22. Mock, K. 1998. Wildwood. International Conference on Evolutionary Computing (ICEC '98)

23. Parish, Y. and Müller, P. 2001. Procedural Modeling of Cities. SIGGRAPH 2001 Conference Proceedings, pp. 301-308

24. Prusinkiewicz, P. and Lane, B. 2002. Generating spatial distributions for multilevel models of plant communities. Proceedings of Graphics Interface, pp. 69-80.

25. Prusinkiewicz, P. and Mĕch, R. 1996. Visual Models of Plants Interacting with Their Environment. SIGGRAPH 1996 Conference Proceedings, pp. 397-410

26. Prusinkiewicz, P., Hammel, M. and Mĕch, R. 1995. The Artificial Life of Plants. Artificial Life for Graphics, Animation, and Virtual Reality, v7 of SIGGRAPH 1995 Course Notes, pp 1-1 – 1-38, ACM Press 95

27. Prusinkiewicz, P., Hammel, M. and Mjolsness, E. 1993. Animation of Plant Development. SIGGRAPH 1993 Conference Proceedings

28. Prusinkiewicz, P., Hammel, M., Hanan, J. and Mĕch, R. 1996. Visual models of plant development. In: Rozenberg, G. and Salomaa, A. (Eds.): Handbook of formal languages. Springer-Verlag: Berlin, pp. 535-597

29. Prusinkiewicz, P., James, M. and Mĕch, R. 1994. Synthetic Topiary. SIGGRAPH 1994 Conference Proceedings

30. Prusinkiewicz, P., Jirasek, C. and Moulia, B. 2000. Integrating biomechanics into developmental plant models expressed using L-systems. In: Spatz, H. and Speck, T. (Eds.): Plant biomechanics 2000. Georg Thieme Verlag: Stuttgart, pp. 615-624

31. Prusinkiewicz, P., Lane, B., Muendermann, L. and Karwowski, R. 2001. The use of positional information in the modeling of plants. SIGGRAPH 2001 Conference Proceedings, pp. 289-300

32. Rodkaew, Y., Lursinsap, C., Fujimoto, T., Suripant, S., Chongstitvatana, P. and Chiba, N. 2002. Modelling Leaf Shapes Using L-Systems and Genetic Algorithms. International Conference NICOGRAPH. April, Japan

33. Rozenberg, G. 1973. T0L systems and languages. Information and Control 23(4), pp. 357-381

34. Sorrensen-Cothern, K., Ford, E. and Sprugel, D. 1993. A model of competition incorporating plasticity through modular foliage and crown development. Ecological Monographs 63(3), pp. 277-304

35. Tobler, R., Maierhofer, S. and Wilkie, A. 2002. A Multiresolution Mesh Generation Approach to Procedural Definition of Complex Geometry. International Conference on Shape Modeling and Applications 2002 (SMI'02). Banff, Canada, pp. 35-42

36. Weber, J. and Penn, J. 1995. Creation and rendering of realistic trees. SIGGRAPH 1995 Conference Proceedings, pp. 119-128

37. Wonka, P., Wimmer, M., Sillion, F. and Ribarsky, W. 2003. Instant Architecture. SIGGRAPH 2003 Conference Proceedings, pp. 669-67