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 xaxis.
 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.
 Resulting string:
FFFF+FFF  Resulting string:
FFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFF+FFFF+FFFFFFF+FFFFFFF+FFF  Resulting string:
FFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFF+FFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFF+FFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFF+FFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFF+FFFF+FFFFFFF+FFFFFFF+FFF+FFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFF+FFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFF+FFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFFFFFF+FFF+FFFF+FFFFFFF+FFFFFFF+FFF
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 byFF
G
is replaced byF[+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 Ftype line, each green branch a Gtype 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 3space which is defined by three othonormal 3vectors:
 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 endThe 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 da = deg2rad(delta) ; %convert to radians %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
 The 2D program described above.
 A 3D program which renders the plant as both
lines and tubes, as shown below.