[Edu-sig] Implementing an Lsystem (edu-sig Python project)

Kirby Urner pdx4d@teleport.com
Thu, 06 Jul 2000 14:38:56 -0700

```I was exploring in ActiveWorlds Education Universe today
(http://edu.activeworlds.com/top.html), and went again to=20
Bonnie DeVarco's Virtual High School (VHS), a fave location=20
in TheU, one of 133 worlds in Education Universe.

At 21N 54W facing North, you have this amazing wall of bioforms,=20
with a link to the Lsystems website by Lauren Lapr=E9.  This guy=20
has done some trully amazing ray tracings.  For example, check=20
out:=20

http://www.xs4all.nl/~ljlapre/tdd.jpg

Anyway, the Lsystem is the formal language that grew up in the=20
space between fractal and turtle geometries, and is used to develop=20
fairly realistic bioforms on the computer.  This seems a useful=20
and rich area in which to anchor some educational "math through
programming" Python projects.

First, for an example of what Lsystems can do, check out some=20
of these images:

http://www.xs4all.nl/~ljlapre/lp07.jpg
http://www.xs4all.nl/~ljlapre/lp06.jpg

Where to find more background on Lsystems?  Everyone refers to=20
a groundbreaking text: 'The Algorithmic Beauty of Plants' by=20
P. Prusinkiewicz and A. Lindenmayer (the Lindenmayer's name=20
providing the L in Lsystems).

Prusinkiewicz and colleagues, based in Canada, have put quite a=20
bit of material on the web, starting at:

http://www.cpsc.ucalgary.ca/projects/bmv/vmm/title.html

http://www.cpsc.ucalgary.ca/projects/bmv/vmm/JPEG/production.jpg

would make a good PowerPoint slide, and starts to explain the=20
notation.

Especially useful is Hung-Wen Chen's explanation of his 1995=20
master project in computer graphics at:=20

http://www.tc.cornell.edu/Visualization/contrib/cs490-94to95/hwchen/

Here we find the turtle language spelled out, along with ideas=20
about how to implement in code, including the rotation matrices. =20
Excerpt:

=3D=3D=3D=3D=3D=3D=3D=3D  =20

The basic idea of turtle interpretation described by=20
Prusinkiewicz is given below. A state of the turtle is=20
defined as a triplet state (X,Y,Alfa), where the Cartesian=20
coorfinates(x,y) represent the turtle's position , and the=20
angle Alfa, called the heading, is interpreted as the=20
direction in which the turtle is facing. Given the step size=20
N and the angle increment angle Delta, the turtle can respond=20
to commands represented by the symbols : F , + , and -.=20

However, the three symbols can only generate 2 dimensional graphic=20
trees. If we want to generate 3 dimensional graphics, these two=20
operators are not enough. Therefore, for 3D graphics, we have=20
to change the turtle's state to (X,Y,Z,Angle_U,Angle_L,Angle_H).=20

In addition, there are seven operators to deal with the freedom=20
of the 3 dimensions graphics space, such as turn left or right,=20
pitch down or up, and roll left or right, and turn around. All=20
these operators are used to generate the graphics not only in=20
a flat plane but also in 3D space.=20

"F" : Move forward a step of length d. A line segment between=20
points (X,Y,Z) and (X',Y',Z') is drawn.=20
"["=20
and=20
"]" : bracket - push and pop the current state, in this project=20
it is used to generate the tree branches.
"+" : Turn left by angle Delta, Using rotation matrix R_U(Delta).=20
"-" : Turn right by angle Delta, Using rotation matrix R_U(-Delta).=20
"&" : Pitch down by angle Delta, Using rotation matrix R_L(Delta).=20
"+" : Pitch up by angle Delta, Using rotation matrix R_L(-Delta).=20
"<" : Roll left by angle Delta, Using rotation matrix R_H(Delta).=20
">" : Roll right by angle Delta, Using rotation matrix R_H(-Delta).=20
"|" : Turn around, Using rotation matrix R_H(180).=20

=3D=3D=3D=3D=3D=3D=3D=3D

The above information is giving us the outlines of a Python Lturtle=20
class. We'd need a current state list, saved state, and rotation=20
methods.  The heading, up and left members of the state tuple are=20
unit vectors. So we need a vector class -- something like this:

from coords import Vector  # coords.py is something I wrote earlier

class Lturtle:

state      =3D []    # current state=20
stackstate =3D []    # remembers saved state
delta      =3D 0     # angle of rotation
length     =3D 0.5   # full length of turtle move
thickness  =3D 0.02  # default thickness of cylinder

def __init__(vPos =3DVector((0,0,0))
vH   =3DVector((1,0,0)),
vL   =3DVector((0,1,0)),
vU   =3DVector((0,0,1))
):
=20
self.state =3D [x,y,z,vH,vL,vU]

def forward(self,d):
"""F by self.count"""

def turnleft(self,delta):
"""+ angle by self.delta"""

def turnright(self,delta):
"""- angle by self.delta"""

def pushstate(self):
""" [ save current state """

def popstate(self):
""" ] load saved state """

... (etc.)

We also need a way to parse Lsystem files, meaning we iterate=20
through a set of rules (e.g. substitions) a specified number=20
of times, and feed the resulting string to the Lturtle as a=20
series of commands e.g. [+F+F+F+F][-F-F-F-F].  We should=20
probably read these in as text files (.ls) in order to be=20
compatible with a lot of the work already done.