L-Systems

L-Systems is a shorthand for Lindenmayer Systems. Astrid Lindenmayer developed L-Systems in 1968 as a means to describe the development of simple multi-celled organisms and later, in plants. The self similiarity of parts of the plant as they grow and the patterns they form is the basis of L-Systems. Later, geometric structures were incorporated into L-Systems which allowed the patterns produced by an L-System to be described graphically.

For our purposes, we will describe an L-System as being made up of an initial string that can be modified using a series of production rules that will expand the initial string along with a way to translate the string into a geometric structure. The geometric structure produced is encoded by a string. That is the string dictates what to draw and where to draw it.

L-Systems can generate complex geometric structures by applying production rules over and over again to a string that alters what the string is.

This image shows 3D models that was created using L-Systems.

This chapter will look at how lindenmayer systems work.

The Grammar

L-Systems can be used to create complex geometric structures. We do this by essentially starting out with with a simple string and allowing the L-system's grammar rules alter and change the string to a more complex form. The drawing is then done to this more complex shape.

Turtle Graphics

One way to interpret the encoded string is to use turtle graphics. Turtle graphics draw images based on the position of and orientation of a "turtle" in 3D space.

The code encodes instruction to the turtle such as turn in a certain direction, draw a line to a position or move to a new position without drawing.

Note that what is drawn for each symbol, how the turtle may move is entirely up to the L-system. It is important therefore to state what each symbol means.

Here is a grammar found on wikipedia:

    variables : A B
    constants : + −
    start  : A
    rules  : (A → B−A−B), (B → A+B+A)
    angle  : 60°

So, if you see a string A and B, it means draw a "line" forward. The + and - indicates a turn to left and right of the turtle but does not show anything in the drawing drawing itself.

There are two rules. which describe how A and B change.

(A → B−A−B), (B → A+B+A)

So, if we apply the rules once to an initial string "A", string becomes: "B-A-B"

if we apply it again (this time to "B-A-B") we get: A+B+A-B-A-B+A+B+A

The above grammar will produce the following depending on how many times we apply our substitution:

Writing an L-System in 3DS Max

You can take the concept of turtle graphics and translate it into an L-system in 3DS Max. To do so, you will need create "turtle" object. The turtle is essentially a cursor that keeps track of where to draw and which direction to draw in.

For example you can create the following struct:

struct Turtle (
  position,
  heading
)

position should be a vector. As for heading, it depends on what method you want to use to represent your rotation and whether you are working with a 2D or 3D L-system. For 2D, you can simply pick an axis of rotation and use a single number to represent the amount of spin around that one axis. For 3D, a quaternion is much more useful (quats can be used in 2D systems also)

The drawing command for the turtle typically involves drawing a line, This can be represented in 3D space with shapes like cylinders, boxes and cones or essentially any geometric shape that are "line" like.

When you draw the shape, you will want to draw it at the specified position and then rotate it around your axis by the amount specified by your heading.

Once you have done, this, you will then need to reposition your turtle to the "tip" of the line you just drew.

2D - Trig method

If you are using just a single angle to represent your rotation, you can use trignometry to determine your position.

after drawing your "line" object, simply apply a rotation to it to spin it around the axis of rotation.

To reposition your turtle, make the calculation as follows:

• determine the 2 axis for your "plane" and which axis is x and y. For example.. if you drew it so that your geometric shape is drawn on a flat vertical surface along the x axis, then you are using the x-z plane in 3DS max. You would want your "y" to be z.
• You know the length of your "line", so knowing its starting position and its rotation, you can find its tip by simply calculating:
  • x = height * cos $\theta$
  • y = height * sin $\theta$ then map those to the appropriate coordinate system for your plane.

3D - Quaternion method.

Maxscript has some quirks when it comes to working with quaternions. This section will help you overcome some of these quirks.

A quaternion is very useful for calculating a series of rotations applied one after the other. This is essentially what you are doing when you are drawing with L-systems. Each time, you apply a "turn" command, you are applying a rotation from the current position.

To create a quaternion, you simply need to supply an angle and an axis of rotation:

q = quat 90 [0,1,0]  -- q is a quaternion now

In Max, a right handed system is used in quaternion calculations. To visualize what this means stick out your thumb and make the thumb your axis of rotation, thumb points to the positive axis. Now, curve your fingers. That is positive spin around the axis. opposite direction is negative.

if you take any vector and multiply it by a quat you will end up with the vector rotated by the angle.

Thus:

v = [0,0,1]    -- (vector pointing up)
q = quat 90 [0,1,0]  -- rotation around y (in-out of screen axis)
u = v * q   -- u would be [-1,0,0]

When you multiply two quaternions together you essentially apply the two rotations in the order you state:

q = quat 90 [0,1,0]
q2 = quat 90 [0,0,1]
q3 = q * q2

v = [0,0,1]
v = v * q
v = v * q2

u = [0,0,1]
u = u * q3

in above, q3 would be a quaternion representing rotation around y axis then the z axis by 90 each time. If we apply the rotations separately (like we do to v) or we apply their product to a vector (like we do to u), the results would be the same. This makes quaternions very convenient for storing a series of rotations which is exactly what we need.

In 3D L-systems other than having just + and - (roll), you will also find symbols to spin and yaw. (in other words, symbols that represent spinning in eahc of the 3 axis.

Our turtle can then be defined as follows:

struct Turtle(
 position,
 heading, --a unit vector pointing foward
 rotq, --a quat representing our cumulative rotation
)

Now, set the intial position and heading. for rotation, you can initialize it to any rotation with a 0 angle.

After you draw a straight line, you can calculate a new position by simply multiplying the length of your "line" by the heading vector and adding it to the old position to get your new position:

newposition = oldposition + (length of line * heading)

Every single time you have to do some sort of rotation, simply build a quat for that rotation and multiply your heading and rotational quaternion by that quat:

   q = some quat that represents your rotation
   new heading = old heading * q
   new rotq = old rotq * q

Now, here is the wierd tricky bit that has to do with drawing your lines. After some experimentation it seems that while the calculations for your quaterions spins a vector in some direction, the rotate function seems to spin it in the other. so if you build a quat, and you use it to calculate the position and you use it to rotate, you will find that your object is opposite to where you want it to be.

However, if you use the inverse of the quat for rotation that seems to make it rotate your objects correctly. So... the short of it is this... when you actually use the rotq to spin your "line", make sure you do this:

c = cone()
rotate c (inverse rotq)

instead of using just the quaterion.