Last edited 11dec11 by lnghmmr2@illinois.edu


LindFern

Creating a 3-dimensional visualization of a fractal fern using an L-system in VPython

Abstract

My project is a 3-dimensional representation of a plant-like Lindenmayer system created in VPython for MATH 198 Hypergraphics, taught by Professor George Francis. Prior to the course, I had no background in visual programming, let alone computer programming. With guidance and assistance from Professor Francis and classmates, I was able to learn python and create the program. 


Background

An L-system is a method of modeling plant development, as introduced by biologist Aristid Lindenmayer in 1968.1 L-systems focus on recursively replacing parts of a string in accordance to a set of general instructions. Lindenmayer, along with Frijters, Hogeweg, and Hosper, first published graphical representations of L-systems in 1974. Besides modeling plants, L-systems can be used to generate fractal curves and space-filling curves. 


For example, we will start with the simple string A. The rules will be that A becomes AB, and B becomes A. Following these rules, each iteration results in a new string, as shown here. The results are as follows: The first iteration results in AB, the next ABA, then ABAAB, then ABAABABA.  


Today, L-systems are commonly drawn using 2D turtle geometry.2 The state is a triplet, (x,y,a), x and y being Cartesian coordinates and a being the angle the turtle faces from the horizontal axis. Generally, step sizes are denoted by d and angle increments by b. Furthermore, general commands exist, and they are as follows:


F moves the turtle forward length d, changing the state to (x’,y’,a). x’ is x+dcos(a) and y’ is y+dsin(a). A line segment is drawn.


f moves forward d, but does not draw a line segment. The state changes as it does with F.


+ turns the turtle left by b. The state becomes (x,y,a+b).


- turns the turtle right by b. The state becomes (x,y,a-b). 


Aristid Lindenmayer added the stack to create branching patterns, using [ and ]. 


[ puts the current position and direction on top of a stack.


] moves the current position and direction to the top and removes that entry.


The initial position and string are defined by the axiom, and the recursive replacement instructions are called the production rules. 


Here is an example of a two-dimensional L-system generated using a stack to allow you to picture what I am constructing. The axiom is F and the production rules are F becomes F[-F]F[+F][F].  The first four iterations are shown. 

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][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[+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]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[-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][+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][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[+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]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[-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]]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][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[+F][F][+F[-F]F[+F][F]][F[-F]F[+F][F]]]] 


My Project

My goal is to study and explore the mechanics behind Lindenmayer systems and fractal plant growth. Instead of creating a fractal plant in two-dimensional turtle graphics, I will be using VPython and adding a third dimension. Turtle graphics will also be utilized in VPython. The plant will begin with one main branch and then split, following production rules for each iteration. 


Each component that branches from the initial stem mirrors the overall plant in a way. There is similarity between each iteration of the branches, and an ideal construct of a fern would have infinite iterations. Due to technological and visual constraints, my version of the fern in VPython will not have an infinite amount of iterations. I have found that 2 or 3 iterations work best in my program.


Currently, my code declares how branches will be created and constructs them in VPython. It uses iterations and production rules to generate branches. I can provide an axiom and rules, as well as the number of iterations I want, and see the resulting string. Then, a branch is constructed from a cylinder as follows:



Note that the position is stored in the triple (aa,bb,cc) and the axis is (dd,3,ff). aa,bb,cc,dd, and ff are all arrays with one initial item, 0, stored. This is because the plant will start at the position (0,0,0) and each branch will have a length of 3. dd controls whether the branch leans left or right, and ff controls whether it leans forward or backward.

 

Because +  - as well as [ and ] are already used in python, I had to create new variables. In my program, the variables are as follows:


R changes the dd value in the axis. It appends dd so that the next item in its list is ‘1,’ which makes the next branch constructed tilt to the right.


L changes the dd value in the axis. It appends dd so that the next item in its list is ‘-1,’ which makes the next branch constructed tilt to the left.


T changes the ff value in the axis. It appends ff so that the next item in its list is ‘1,’ which makes the next branch constructed tilt forward.


B changes the ff value in the axis. It appends ff so that the next item in its list is ‘-1,’ which makes the next branch constructed tilt backwards.


P pops the current state and returns to the position and axis that existed before the previous branch was constructed. It appends all the arrays so that the next item listed was the item that was listed before the previous branch was constructed.


F constructs a branch using the current items in each array to designate position and axis. It then appends those arrays to create the new position and reset the axis.


Here is a screenshot of the production and iteration codes3: 


The produce command takes the axiom and applies the rules to each F, replacing the axiom. The iterate command then prints these results for each iteration.


When I run the module, iterate(n, axiom, rules) runs, letting n be the number of iterations I desire. For example, when iterate(2,axiom,rules) is at the end of the code, this is the result using the axiom and rules in the above screenshot:


Then, the line “axiomarray=[c for c in axiom]” takes the above string and turns it into an array. The result is below:


Next, the construct function, which is called at the iteration function, creates the cylinders then adjusts the position and axis vectors by appending the respective arrays. It examines the current items in dd and ff and sees where the new position should be. If both are 0, then 3 is simply added to bb. If either of them are positive, the new item appended to bb is 3*sin(45). The following table shows what is appended for each value of dd and ff. If an array is not listed, then the new item appended to it is its current item in the list. 


dd=0

dd<0

dd>0

ff=0

bb=bb+3

aa=aa-cos(44.5)

bb=bb+3sin(45)

aa=aa+cos(44.5)

bb=bb+3sin(45)

ff<0

bb=bb+3sin(45)

cc=cc-cos(44.5)

aa=aa+cos(22.5)

bb=bb+3sin(45)

cc=cc+cos(22.5)

aa=aa-cos(22.5)

bb=bb+3sin(45)

cc=cc+cos(22.5)

ff>0

bb=bb+3sin(45)

cc=cc+cos(44.5)

aa=aa+cos(22.5)

bb=bb+3sin(45)

cc=cc-cos(22.5)

aa=aa-cos(22.5)

bb=bb+3sin(45)

cc=cc-cos(22.5)

As you can see, I use cos(44.5) instead of cos(45) because the radius is .25, allowing correct alignment so that the branches do not appear jagged.


Note that it only constructs a branch if the item in the array is ‘F’. If it is not ‘F,’ it skips to an else loop inside the construct function. The else loop looks at if the item in the array is ‘L,’ ‘R,’ ‘T,’ ‘B,’ or ‘P’ and makes the aforementioned changes to the respective arrays. 


At the very end of the code, as I said before, the iteration function is called. Before running the module the user must change n in the iterate function and make their own axiom and rules. Using the previously mentioned axiom and rules, here is what is constructed when n=2 and the module is run:



Using the right mouse, the user can move the constructed plant and examine it from all angles.

You may have noticed that this plant only moves left and right, not forward or backward. Here are some other screenshots of constructed plants that go in various directions.

n=3, Axiom=FLF, Rules=FPRFPBFPTFB

n=2, Axiom=F, Rules=FLFPBFPTF


Using the Program

Before running the module, users can edit the axiom and rules line. Also, at the very bottom of the program, where iterate is called, they can change the number, n, to choose how many times they want it to iterate. In the construct function, the line time.sleep(1) delays production of each branch to slow down the program. If desired, the user can change that number to make it run different speeds. Here is my program: lindfern.pyIf that does not work, here is my program in a .txt file:lindfern.txtAlso, here are directions to use the program and a link to my powerpoint for a more in-depth walkthrough of the program.Directions Powerpoint

Future Changes

There are plenty of ways to enhance this program in the future. A few ideas involve randomizing the axiom and rules, allowing branches to extend more than 45 degrees, and varying the lengths and radii of the branches.

Reflection

Looking back at my progress throughout the semester, I would have to say that I am happy with my development. Prior to this class, I had no programming experience. Now, I have a program that I was able to construct by myself with guidance and assistance from Professor Francis. The produce and iterate function were adapted from Kirby Urner's project (see below) to accommodate the construction of branches in VPython. I am proud that I was able to debug my own program and fix all problems that arose.

Sources

References