Lindenmeyer and Przemyslaw noticed that you could treat the long text strings resulting from multiple replacements as commands to build objects. In two dimensions, the interpertation is:

• Start at x=0, y=0, facing along the x-axis.
• Capital F means "draw a line of length=1 in the direction you are now facing".
• + means turn left.
• - means turn right.

Let's look at the result of applying the rule in the first paragraph 3 times. The string length grows fast. The three output strings are shown below, followed by the resulting geometric interpertation, assuming that left and right turns are each 90 degrees.

1. Resulting string: ``` F-F-FF+F-F-F```
2. Resulting string: ``` F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-FF-F-FF+F-F-F+F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F```
3. Resulting string: ``` F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-FF-F-FF+F-F-F+F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-FF-F-FF+F-F-F+F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-FF-F-FF+F-F-F+F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-FF-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-FF-F-FF+F-F-F+F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F+F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-FF-F-FF+F-F-F+F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-FF-F-FF+F-F-F+F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-FF-F-FF+F-F-F+F-F-FF+F-F-F-F-F-FF+F-F-F-F-F-FF+F-F-F```

Here are the images resulting from following the geometric instructions for each string. Repititions 4 and 5 have been included. The strings would have filled pages. you can see that the application of this simple rule makes very complex structures which are constructed of repeated, modular units, much like a plant or animal.

As you can guess by the drawing rules given above, without some further commands, all structures will be a single (very twisted) line. We need to be able to make branches, so we are going to add two new commands to the strings, `[` and `]`. These two commands are interperted as:

• [ means "store the current drawing position and orientation". This storage is done on a stack so that several drawing states may be saved (in order) without losing any of them.
• ] means "retrieve the last drawing position and orientation stored on the stack and make it your current configuration"

As an example, start with the string `G`. The geometry used will be that G means "draw a line of length 0.5 in the direction you are facing, and color it green". There are two replacement rules:

• `F` is replaced by `FF`
• `G` is replaced by `F[+G][-G]F[+G][-G]FG`

Note that each bracket`, [ `or` ]` will cause a branch. After 3 repetitions, with a turning angle of 25 degrees, you get the following image. Each brown branch is an F-type line, each green branch a G-type line.

Obviously it would be nice to have a fully 3D geometric interpertation so that we can construct 3D plants and animals. To go to 3D we need to define 7 different turning commands. We need to turn left/right, pitch up/down, roll left/right. It is very handy to also have a "turn around and go back" command. The symbols we will use are:

• + means turn left by angle Delta, Using rotation matrix R_U(Delta).
• - means turn right by angle Delta, Using rotation matrix R_U(-Delta).
• & menas pitch down by angle Delta, Using rotation matrix R_L(Delta).
• ^ means pitch up by angle Delta, Using rotation matrix R_L(-Delta).
• \ means roll left by angle Delta, Using rotation matrix R_H(Delta).
• / means roll right by angle Delta, Using rotation matrix R_H(-Delta).
• | means turn around, Using rotation matrix R_H(180).

The rotation matrices refered to above are a mathematical way of keeping track the order of rotation operations and will be explained further below. The state of the drawing entity now has an orientation in 3-space which is defined by three othonormal 3-vectors:

• The direction it is heading (drawing) which is called the H vector.
• The direction which is up, called the U vector.
• The direction to the left, called the L vector.

At any given time, turning right/left means rotating around the U vector. Pitching up/down means rotating around the L vector and rolling means rotating around the H vector. To rotate, each of the 3 vectors is multiplied by the same matrix to form the updated orientation of the drawing entity. The three matrices are given below for a rotation angle delta. The process will be further described in the next section

```                    |  cos(delta)   sin(delta)     0     |
R_U (delta ) = | -sin(delta)   cos(delta)     0     |
|     0           0            1     |

|  cos(delta)      0      -sin(delta)|
R_L (delta ) = |     0            1         0       |
|  sin(delta)      0       cos(delta)|

|     1           0          0       |
R_H (delta ) = |     0        cos(delta) -sin(delta)|
|     0        sin(delta)  cos(delta)|

```

The three H vector components can be directly added to the current drawing position to make a 3D line segment.

Matlab code considerations

The Matlab code separates into two parts. The first computes the string substitutions. The second performs the geometric interpertation. We will look at the 2D code here.

The scheme I used for the string substitutions was to distribute each character of the input string into an element of a cell array. This allows each character to be modified independently of the others. Then the original string was searched once for each substitution rule to find all the symbols that needed replacement. These symbols are then replaced in the cell array with new strings and the cell array packed back into a single string. The following code details the algorithm.

```
%Rules -- structure element rule(x).before is string to be replaced for the xth rule.
%      -- structure element rule(x).after is the replacement string for the xth rule.

rule(1).before = 'F';
rule(1).after = 'FF';

rule(2).before = 'G';
rule(2).after = 'F[+G][-G]F[+G][-G]FG';%

%get the number of rules
nRules = length(rule);

%angle: +operator means turn left; -operator means turn right
delta = 25; %degrees

%length of the line segments corresponding to the symbols F and G
lenF = 1;
lenG = 1;

%starting seed
axiom = 'G';

%number of repititions
nReps = 4;

for i=1:nReps

%one character/cell, with indexes the same as original axiom string
axiomINcells = cellstr(axiom');

for j=1:nRules
%Find the vector of indexes of each 'before' string for each rule
hit = strfind(axiom, rule(j).before);
if (length(hit)>=1)
%set all of the hits to the new string
%This does not vectorize
for k=hit
axiomINcells{k} = rule(j).after;
end
end
end
%now convert individual cells back to a string for the next repetition
axiom=[];
for j=1:length(axiomINcells)
axiom = [axiom, axiomINcells{j}];
end
end
```
The next step is to convert the final string into geometry. The code refers to a "turtle" because of a similar scheme taught to elementary school students a few years ago. The turtle can go forward (drawing or not drawing), or it can turn left or right. The state of the turtle is given by xT,yT and aT, the x,y position and angle respectively. For each character in the string (either ```F,G,+,-,[, ```or` ]`) , there is a case clause to handle the operation. The bracket commands store/recall the state of the turtle so that the most recent state stored is the next one recalled. When a state is recalled, it is discarded from the stack and exposes the previous state stored so that the previous state may be recalled next. The computer science name for the structure is a stack.
```% Now draw the string as turtle graphics
%Upper case (e.g. F or G) causes a line to be drawn in the current direction of the turtle
%angle +operator means turn left; -operator means turn right

%Init the turtle
xT = 0;
yT = 0;
aT = 0; %facing the x axis

%init the turtle stack
stkPtr = 1;

hold on

for i=1:length(axiom)
cmdT = axiom(i);
switch cmdT
case 'F'
newxT = xT + lenF*cos(aT);
newyT = yT + lenF*sin(aT);
%line([xT newxT], [yT newyT]);
line([yT newyT], [xT newxT],'color',[.3 .3 0], 'linewidth',2);
xT = newxT;
yT = newyT;
case 'G'
newxT = xT + lenG*cos(aT);
newyT = yT + lenG*sin(aT);
%line([xT newxT], [yT newyT]);
line([yT newyT], [xT newxT],'color','g', 'linewidth',2);
xT = newxT;
yT = newyT;
case '+'
aT = aT + da;
case '-'
aT = aT - da;
case '[' %push the stack
stack(stkPtr).xT = xT ;
stack(stkPtr).yT = yT ;
stack(stkPtr).aT = aT ;
stkPtr = stkPtr +1 ;
case ']' %pop the stack
stkPtr = stkPtr -1 ;
xT = stack(stkPtr).xT ;
yT = stack(stkPtr).yT ;
aT = stack(stkPtr).aT ;
otherwise
disp('error')
return
end
%drawnow
end

daspect([1,1,1])
```

Examples

1. The 2D program described above.
2. A 3D program which renders the plant as both lines and tubes, as shown below.