Using GD is straightforward: all that's necessary to create a GIF suitable for displaying on a Web page is a GD::Image object, some colors, and a few drawing commands. It takes only six lines of code to produce a lone brown dot on a white background, a work surely worth millions to a sufficiently avant-garde patron of the arts:
#!/usr/bin/perl use GD; $im=new GD::Image(100,100); $white=$im->colorAllocate(255,255,255); $brown=$im->colorAllocate(128,0,0); $im->setPixel(42, 17, $brown); open (OUT, ">masterpiece.gif") or die $!; print OUT $im->gif();
Here we create an image 100 pixels square and allocate two colors. GIFs use color tables (in particular, a 256-color palette) so it's necessary to specify in advance which colors are to be used. The colors themselves are specified by their red, green, and blue components, which range from 0 to 255.
The dot is then drawn with setPixel(), 42 pixels to the right of the edge and 17 pixels below the top left corner. Finally, the contents of the GIF itself, obtained through the GD::Image::gif() method, is printed to the file masterpiece.gif.
GD provides other drawing commands, special brushes and patterns, and the ability to load existing GIFs from files. But we already have everything we need. The rest of this article is devoted to using GD to build and use code that implements L-systems, a task that proves quite comfortable in Perl because it requires both graphical output and text manipulation.
For our purposes, an L-system is simply a very abstract way of modeling cell-scale growth within a plant. Bear in mind that the level of abstraction is quite high - an L-system won't tell you much about how real plants grow. Real plant growth depends on cytoplasm structure, cell membranes, mitosis rates, and plenty of other hard-to-model phenomena. However, L-systems are quite good at generating realistic images of plants.
Originally developed by Astrid Lindenmayer (hence the 'L') in the late 1960's, L-systems have undergone a number of generalizations and improvements in the decades since, including the addition of randomness, multiple transition tables, and non-discrete evolution. The core of the idea is quite simple: Take a string, called the axiom, and apply a series of rules to each character of the string. For example, suppose your axiom (commonly designated w) is A and you have two production rules,
(1) Every A is translated to BA, and
(2) Every B is translated to AB.
This system would be written in L-system notation as:
w: A p1: A --> BA p2: B --> AB
These rules are applied simultaneously to the axiom, producing BA, since we start with A and change according to rule p1. The rules are then applied to that result, yielding ABBA (no relation to the band). Then the rules are applied again, generating BAABABBA.
When does the process stop? It doesn't. In principle, the combination of axiom and rules describes an infinite sequence of words:
A BA ABBA BAABABBA ABBABAABBAABABBA BAABABBAABBABAABABBABAABBAABABBA
and so on.
This might seem to have little relevance to plant development. However, the output of an L-system can be interpreted as the shape of the plant at various ages. Finding the appropriate time to stop, then, is equivalent to deciding how big or old a tree (or fern, or flower, or blue-green algae colony) you want.
How could an L-system resemble a tree, then? To get branches we can use a bracketed L-system. That just means that we add [ and ] to our L-system's alphabet. Any string enclosed in brackets is interpreted as separate branch, protruding from the string it would otherwise be part of. Brackets can also be nested. For example, A[B][CD[E[F]G]H] can be loosely interpreted as this:
Typically, objects modeled with L-systems are rendered with turtle graphics. Turtle graphics were invented for the LOGO programming language; they're used to give children a simple metaphor for expressing graphics algorithmically. Implementations of LOGO have virtual turtles that turn, move, and leave trails across the screen. Older versions sometimes had an actual robot controlled by the program. The robot moved a pen around on paper, and was sometimes fashioned to look like a small, plastic-shelled turtle.
The Turtle class (in the Turtle.pm module on the TPJ web site) implements simple turtle graphics. The humble turtle can produce some striking graphics if carefully controlled, but itself knows little more than its position, orientation, how to turn, and how to move forward at an angle. The most important method of the Turtle class is forward():
sub forward {
my $self = shift;
my ($r, $what)=@_;
my ($newx, $newy)=($self->{x}+$r* sin($self->{theta}),
$self->{y}+$r*-cos($self->{theta}));
if ($what) {
# Do something related to motion according to
# the coderef passed in
&$what($self->{x}, $self->{y}, $newx, $newy);
}
#... and change the old coordinates
($self->{x}, $self->{y}) = ($newx, $newy);
}
forward() first uses a bit of trigonometry to calculate the (x, y) position given the distance r and angle 
. (All angles are measured in radians, with zero being directly up and angles increasing as you move clockwise.). Then it does something with the old and new coordinates, but exactly what it does is up to $what. Whoever calls Turtle::forward() passes in a code reference; that coderef gets the turtle's old and new coordinates as parameters, and can do whatever it wants with them. For now, all we want the turtle to do while moving forward is draw a line, but this flexibility will prove quite handy later. Another method worth examining is turn():
sub turn {
my $self=shift;
my $dtheta=shift;
$self->{theta} += $dtheta * $self->{mirror};
}
Our turtle will occasionally need to turn left into right and right into left; this is accomplished by calling the turtle's mirror() method. That toggles the mirror attribute between 1 and -1, and has the effect of changing clockwise rotations into counterclockwise rotations.
A turtle can't do much by itself. Starting with a subroutine in lsys.pl, we'll make it more useful. To get an L-system rule to tell the turtle what to do, we create a turtle, an image, and a hash to translate characters into behavior:
sub lsys_init {
# S => Step Forward
# - => Turn Counter-clockwise
# + => Turn Clockwise
# M => Mirror
# [ => Begin Branch
# ] => End Branch
%translate=(
'S' => sub{$turtle->forward($changes->{"distance"},
$changes->{"motionsub"})},
'-' => sub{$turtle->turn(-$changes->{"dtheta"})},
'+' => sub{$turtle->turn($changes->{"dtheta"})},
'M' => sub{$turtle->mirror()},
'[' => sub{push(@statestack, [$turtle->state()])},
']' => sub{$turtle->setstate(@{pop(@statestack)})},
);
my ($imagesize)=@_;
# Create the main image
$im = new GD::Image($imagesize, $imagesize);
# Allocate some colors for it
$white = $im->colorAllocate(255,255,255);
$dark_green = $im->colorAllocate(0,128,0);
$light_green = $im->colorAllocate(0,255,0);
# Create the turtle, at the midpoint of the bottom
# edge of the image, pointing up.
$turtle = new Turtle($imagesize/2, $imagesize, 0, 1);
}
To have the turtle perform the action identified by the character $chr, we just say &{$translate{$chr}}(), which calls the appropriate anonymous subroutine.
$changes, the hash reference inside %translate, holds information specific to a given L-system rule. It'll go in a separate file, tree.pl, whose beginning is shown below.
#!/usr/bin/perl
require "lsys.pl";
# Set some parameters
$changes={ distance => 40,
dtheta => .2,
motionsub => sub{$im->line(@_, $dark_green)}}
};
The first two keys of the hash referred to by $changes are straightforward: distance is how far the turtle moves every instance of S, and dtheta is how much the turtle's angle changes for every + or -. The last key, motionsub, identifies the anonymous subroutine passed to Turtle::forward(). Recall that Turtle::forward() passes the old position and the new position of the turtle. sub{$im->line(@_, $dark_green); merely takes that argument list, tacks on $dark_green, and hands everything off to GD::Image's line() method. That draws the line.
Now we have a turtle that can turn, flip, go forward, and trace a line. Only the left and right bracket characters remain - they'll help the turtle remember a position and later recall where it was. The [ character pushes the turtle's current state (x, y, q, and mirror) onto a stack, @statestack. The ] character, conversely, pops an element off @statestack and forces the turtle back into that state.
To create an honest-to-goodness L-system inside all this mess, we just need one more hash table to describe the production rules, and a scalar initialized with the axiom. Let's start with a small system:
w: A p1: A --> S[-A][+A]
This system has every A go forward (S) and produce two branches, each with an A: one to the left ([-A]), and one to the right ([+A]). On every iteration, the tree will split in half, yielding a binary tree growing upward from the turtle's initial location.
This L-system is expressed in Perl as follows:
%rule = ( A => 'S[-A][+A]' ); $axiom = "A";
%rule contains the single rule of our L-system; $axiom is our start string. The lsys_execute() subroutine, in lsys.pl on the TPJ Web site, applies the rules to the axiom $repetitions times:
sub lsys_execute {
my ($string, $repetitions, $filename, %rule) = @_;
# Apply the %rule to $string, $repetitions times,
# and print the result to $filename
for (1..$repetitions) {
$string =~ s/./defined ($rule{$&}) ? $rule{$&} : $&/eg;
}
...and calls the appropriate subroutines held in %translate...
foreach $cmd (split(//, $string)) {
if ($translate{$cmd}) {&{$translate{$cmd}}();}
}
...and finally prints out the GIF itself:
open(OUT, ">tree.gif") or die $!;
print OUT $im->gif;
close(OUT);
}
This program creates the GIF below:
#!/usr/bin/perl
require "lsys.pl";
%rule = ( 'A' => 'S[-A][+A]', );
$axiom = "A";
$changes={distance => 40,
dtheta => .2,
motionsub => sub{$im->line(@_, $dark_green)}};
$repetitions=8;
$imagesize=400;
$filename = "tree1.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
)
Not exactly breathtaking, but moderately tree-like. Its most glaring flaw is that all the branches are the same length. Younger branches should be shorter because they've had less time to grow. Changing the system to
w: A p1: A --> GS[-A][+A] p2: G --> GS
makes every G produce an S at every step. Coding the rule in Perl and shortening the distance a bit:
#!/usr/bin/perl
require "lsys.pl";
%rule = ( 'A' => 'GS[-A][+A]', 'G' => 'GS' );
$axiom = "A";
$changes={distance => 10,
dtheta => .2,
motionsub => sub{$im->line(@_, $dark_green)}};
$repetitions = 8;
$imagesize = 400;
$filename = "tree2.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
This produces:
)
A definite improvement. However, most plants aren't perfectly symmetrical. Let's try forcing the right branch to wait before splitting. Specifically, we'll use this L-system:
w: A
p1: A --> GS[-A][+B]
p2: G --> GS
p3: B --> C
p4: C --> A
Now every right branch spends less time splitting and growing. Here's the program that implements this system:
#!/usr/bin/perl
require "lsys.pl";
%rule = ('A' => 'GS[-A][+B]',
'G' => 'GS',
'B' => 'C',
'C' => 'A');
$axiom = "A";
$changes={distance => 2.8,
dtheta => .2,
motionsub => sub{$im->line(@_, $dark_green)}};
$repetitions = 15;
$imagesize = 400;
$filename = "tree3.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
)
Interesting, but kind of lopsided. Remember Turtle's mirror() method? Now's a good time to take advantage of it. Let's try changing the first rule of the L-system to
p1: A --> GS[---A][++MB]
and decreasing dtheta a bit:
#!/usr/bin/perl
require "lsys.pl";
%rule = ('A' => 'GS[---A][++MB]',
'G' => 'GS',
'B' => 'C',
'C' => 'A');
$axiom = "A";
$changes={distance => 2.8,
dtheta => .06,
motionsub => sub{$im->line(@_, $dark_green)}};
$repetitions = 15;
$imagesize = 400;
$filename = "tree4.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
)
Now the second branch of every subtree is flipped, and the tree looks less like the victim of gale-force winds.
Merely drawing branches may be good enough for trees in winter, but around this time of year, plants acquire things that are harder to draw: leaves and flowers. Fortunately, GD can draw and fill polygons, and import other GIFs.
Our leaves will be polygons oriented in some direction relative to the branch they're on. We'll use the already-existing turtle code and create a 'polygon mode,' using the traditional L-system notation of curly braces. The turtle will trace out the polygon and then fill it. Turtle::forward() can perform any sort of movement as long as we pass it the appropriate coderef - we just need to construct one that tells GD to convert part of the turtle's path into polygon vertices.
It would be convenient to modify distance and dtheta in polygon mode independently of their values in 'stem mode'. Since these two values are stored in %$changes, we'll create two hashes: %stemchanges for stem mode, and %polychanges for polygon mode. $changes will always be current whatever the mode, so it'll initially refer to %stemchanges. The most important difference between them is their motionsub; %stemchanges has the familiar sub {$im->line(@_, $dark_green)}, but %polychanges has sub {$poly->addPt(@_[0..1])}.
Skipping what that means for the moment, let's handle curly braces with two more entries to %translate:
%translate=(
...
'{' => sub { $poly = new GD::Polygon;
$changes = \%polychanges;
},
'}' => sub {$im->filledPolygon($poly,$light_green);
undef $poly;
$changes = \%stemchanges;
}
);
What's going on? The GD module defines the GD::Polygon class, an instance of which, $poly, gets created whenever we encounter a {. Every time the turtle moves in polygon mode, $polychanges{motionsub} is called, so we call GD::Polygon::addPt() to add a point to the list of vertices in $poly. Once the polygon is drawn, a } is processed, filling the polygon with $light_green. Then $poly is thrown away and stem mode is restored.
#!/usr/bin/perl
require "lsys.pl";
%rule=( 'A' => 'SLMA', 'L' => '[{S+S+S+S+S+S}]');
$axiom = "A";
%stemchanges = (distance => 24,
dtheta => .15,
motionsub => sub{$im->line(@_, $dark_green)});
%polychanges = (distance => 6,
dtheta => .4,
motionsub => sub{$poly->addPt(@_[0..1])});
$changes = \%stemchanges;
$repetitions = 15;
$imagesize = 400;
$filename = "tree5.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions,
$filename, %rule);
The result is something resembling a vine.
){kind=small}
This system is pretty easy to follow - it merely leaves commands for moving forward, drawing a leaf, and flipping the turtle, repeated an arbitrary number of times. The M character once again proves useful, this time allowing easy alternating placement of leaves. Also note that GD automatically closes polygons if they're not closed already.
Let's use some GIFs of flowers: flower.gif, flower2.gif, and flower3.gif, all available on the TPJ Web site. Creating a GD::Image from an existing file is easy - the newFromGif() method does exactly that. All you need to add to lsys_init() is the following:
open(IN, "flower.gif") or die $!;
$flower = newFromGif GD::Image(IN);
close(IN);
open(IN, "flower2.gif") or die $!;
$flower2 = newFromGif GD::Image(IN);
close(IN);
open(IN, "flower3.gif") or die $!;
$flower3 = newFromGif GD::Image(IN);
close(IN);
Once all the flowers are loaded, we need to copy them onto the main image. We'll delegate that to a small subroutine in lsys.pl that centers the image at the turtle's current coordinates. It uses GD::Image's getBounds() method.
sub flower {
my $flower=shift;
my ($width, $height) = $flower->getBounds();
my ($x,$y) = $turtle->state();
$im->copy($flower, $x-$width/2, $y-$height/2,
0, 0, $width, $height);
}
GD::Image::copy() does the dirty work here, even copying the flowers' color tables if necessary. We'll add a few more entries to %translate.
%translate = (
...
'f' => sub { flower($flower) },
'g' => sub { flower($flower2) },
'h' => sub { flower($flower3) },
);
We can test the new features with this program:
#!/usr/bin/perl
require "lsys.pl";
%rule = ( 'A' => 'GS[-fA][+fA]', 'G' => 'GS');
$axiom = "A";
%stemchanges=(distance => 9,
dtheta => .25,
motionsub => sub{$im->line(@_, $dark_green)});
%polychanges=(distance => 6,
dtheta => .4,
motionsub => sub{$poly->addPt(@_[0..1])});
$changes = \%stemchanges;
$repetitions = 8;
$imagesize = 400;
$filename = "tree6.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
)
It looks odd with flowers growing out of every branch. One way to avoid this result is forcing flowers to die every step, leaving live flowers only at the very tips. The program then becomes:
#!/usr/bin/perl
require "lsys.pl";
%rule = ('A'=>'GS[-fA][+fA]', 'G'=>'GS', 'f'=>'');
$axiom = "A";
%stemchanges=(distance => 9,
dtheta => .25,
motionsub => sub{$im->line(@_, $dark_green)});
%polychanges=(distance => 6,
dtheta => .4,
motionsub => sub{$poly->addPt(@_[0..1])});
$changes=\%stemchanges;
$repetitions = 8;
$imagesize = 400;
$filename = "tree7.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
)
Alternately, you can have the flowers change before they die:
#!/usr/bin/perl
require "lsys.pl";
%rule = ( 'A' => 'GS[-fA][+fA]', 'G' => 'GS',
'f' => 'g', 'g' => 'h', 'h' => '' );
$axiom = "A";
%stemchanges=(distance => 9,
dtheta => .25,
motionsub => sub{$im->line(@_, $dark_green)});
%polychanges=(distance => 6,
dtheta => .4,
motionsub => sub{$poly->addPt(@_[0..1])});
$changes = \%stemchanges;
$repetitions = 8;
$imagesize = 400;
$filename = "tree8.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
)
The L-system itself is an incredible source of variety; even the primitive system I've presented is still capable of making appealing pictures. For a few final examples we'll experiment with some additional rules.
Using just one type of flower:
#!/usr/bin/perl
require "lsys.pl";
%rule = (
'A' => 'GS[---fMA][++++B]',
'B' => 'C',
'C' => 'GS[-fB][++A][++++A]',
'f' => '',
'G' => 'HS',
'H' => 'HSS'
);
$axiom = "A";
%stemchanges = (distance => 4, dtheta => .12,
motionsub => sub{$im->line(@_, $dark_green)});
%polychanges = (distance => 6, dtheta => .4,
motionsub => sub{$poly->addPt(@_[0..1])});
$changes = \%stemchanges;
$repetitions = 10;
$imagesize = 400;
$filename = "tree9.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
)
With leaves and a different flower,
#!/usr/bin/perl
require "lsys.pl";
%rule=(
'A' => 'S[---LMA][++++B]',
'B' => 'S[++LBg][--Cg]',
'C' => 'S[-----LB]GS[+MC]',
'g' => '',
'L' => '[{S+S+S+S+S+S}]'
);
$axiom = "A";
%stemchanges=(distance => 18.5, dtheta => .1,
motionsub => sub{$im->line(@_, $dark_green)});
%polychanges=(distance => 3, dtheta => .4,
motionsub => sub{$poly->addPt(@_[0..1])});
$changes = \%stemchanges;
$repetitions = 10;
$imagesize = 400;
$filename = "tree10.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
)
With all three flower types, leaves, and slightly weird axial growth:
#!/usr/bin/perl
require "lsys.pl";
%rule=(
'A' => 'GS[---fA][++MB]',
'B' => 'C',
'C' => 'A',
'f' => 'g',
'g' => 'h',
'h' => '',
'G' => 'HS',
'H' => 'IS',
'I' => 'GLMS',
'L' => '[{S+S+S+S+S+S}]'
);
$axiom = "A";
%stemchanges=(distance => 2.8, dtheta => .06,
motionsub => sub{$im->line(@_, $dark_green)});
%polychanges=(distance => 3, dtheta => .4,
motionsub => sub{$poly->addPt(@_[0..1]);});
$changes = \%stemchanges;
$repetitions = 17;
$imagesize = 400;
$filename = "tree11.gif";
lsys_init($imagesize);
lsys_execute($axiom, $repetitions, $filename, %rule);
)
You can find several L-systems programs for Unix, Macintoshes, and DOS at http://www.cpsc.ucalgary.ca/projects/bmv/software.html. If you don't mind peeling your eyes off of the CRT, the definitive text on L-systems is The Algorithmic Beauty of Plants, by Lindenmayer and Prusinkiewicz (1990, Springer-Verlag).
_ _END_ _