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

[Kirby Urner]

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[2] 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.

More information on Lsystems:

http://www.csu.edu.au/complex_systems/tutorial2.html
http://shakti.trincoll.edu/~cschneid/lsystems.html
http://www.xs4all.nl/~cvdmark/tutor.html