Lindenmayer (L-System) ApplicationSalome Navarrete, CPE 471 Fall 2012 |
A parallel rewriting system for plant growth modeling
Lindenmayer systems are a variant of a formal grammar used to model natural patterns such as the morphology of organisms or plant life. (self-similar fractals) Common patterns are Dragon Curves, Sierpinski triangles, Koch curves and Fractal plants. Any of these, being specified in the given formal language and with 'F', 'G' being the curve-controlling bases, can be drawn in the application. The following are a few images, and the rules used to generate them.
Rules: (figure 1) Free-Form equations with varying color/noise, 7 iterations
Rules: (figure 2) (F->G[+&F][-%F]G) (G->GG), 8 iterations
Rules: (figure 3) (F->FF+[+F-F-F]-[-F+F+F]) (G->GG), 6 iterations
The actual graphics geometry utilized is simple - namely, 1-unit length lines and small spheres. The interesting patterns, shapes, and colors generated are a series of translations, rotations, and scaling effects on the basic shapes according to the rules specified. The entire system is hierarchically modelled using a matrix stack. While the geometry is itself straightforward, the difficulty in the implementation came from trying to define a formal system and the simple geometry restrictions. There was a lot of initial research to understand formal languages and defining L-Systems (I followed several examples, see references). The provided framework (MStackHelp.h/.cpp) wasn't useful for my application, so I used it as a guide and wrote my own wrapper system around openGL calls for translating and storing everything in a stack, the easiest way to deal with extremely large numbers of transformations.
The system consists of a lexicon of symbols that are turned into strings based on two input rules (production rules). The rules consist of the initial axiom string to build from (F, in this case) and the replacement string. In the following example, F->FG&@FFG G->GG, everytime the initial F or G axioms are seen in the strings, they are replaced by the secondary strings. Patterns are created based on those initial set of rules, creating natural, organic forms. As an addition, a random seed adds a small bit of change to each transformation to increase the organic appearance. Each iteration, as many rules as possible (the string length) are added to the output string, resulting in increasingly very large systems as the number of iterations grows. The application is keyboard-controlled. w,a,s,d,r,f all have various rules pre-defined; those keys will render the stored system. To build your own system, use the 'e' key, and type your rules into the console as [from] [to] [from] [to] [number of iterations], ie F FG@[FGG|] G GG 8. The translation strings get large quickly, so if the rules are complicated and the iterations above 6, it may take several seconds and a decent amount of memory to render. My system uses the following symbol table and translations for its' reproduction grammar (1):
| Turn/Rotate 180*
+ Turn Right/Rotate specified degree
- Turn Left/Rotate specified degree
G, F Draw Forward (translate, for controlling the curve)
& Pitch Down/Rotate specified degree
% Pitch Up/Rotate specified degree
] Restore a saved angle
[ Save the current angle
@ Draw a sphere
X Translate/Rotate based on the iteration
The application is keyboard-controlled.
References:
(1) Oracle/ThinkQuest, Applications of Fractals http://library.thinkquest.org/26242/full/ap/ap15.html
(2) Wikipedia, L-systems http://en.wikipedia.org/wiki/L-system
(3) Wikipedia, Parallel Rewriting systems http://en.wikipedia.org/wiki/Rewriting_system
(4) MStackHelp.h/.cpp Lab provided in class
(5) OpenGL Tutorials http://www.opengl-tutorial.org/