Cornell University
BioNB 441
L-Systems in Matlab
Introduction
An L-System (Lindenmayer System) is a scheme for simulated development
of biological structures. In biological terms, an L-System uses a small set
of rules to locally add details to a structure (e.g. at every end point on a
tree branch, add two branches). In computer science terms, an L-System is a
context-free, recursive, text substitution scheme, followed by geometric interpretation.
A simple L-System starts with a seed, let's say the letter F, and
has one rule to replace the existing seed. A simple replacement rule might be:
F-F-FF+F-F-F
This rule would be applied many times to produce a series of strings of increasing
complexity. Examples will be given below after we talk more about the meaning
of the text.
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:
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.
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-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-FHere 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:
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 FFG is replaced by F[+G][-G]F[+G][-G]FGNote 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:
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:
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
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
