Saturday, March 08, 2014

L-System Garden: Max implementation of Lindenmeyer



Iteration is the act of repeating a task in order to approach a desired goal. This process is at work in many natural phenomena, notably plant growth. Aristid Lindenmayer, a Hungarian biologist), first modelled cell formation using a simple iterative process. He later discovered that the same principles could be extended to larger plant forms: stems, leaves, petals, and so forth. He introduced the L-system (Lindenmayer System) in 1968 and subsequently proposed various geometric interpretations in order to create 2D and 3D renderings of this data. The best source for information is the book he co-authored and in 1990 (shortly after his death). The Algorithmic Beauty of Plants is available as a free PDF download.

L-System process explained

An L-system can be represented by a simple string of characters. All we need is a seed (or axiom) to start with, a set of substitution rules, and a way of interpreting the resulting string as a graphic. A common way to do this is with Turtle graphics, a system so simple it is taught to children. The following minimal command set is all you need:
F = draw forward
- = turn left
+ = turn right
[ = save current position
] = restore saved position

We can specify a different angle for each implementation. Turtle graphics includes a few other commands, but they are rarely used in practice. Any additional symbols in our string are used as place-holders for the iteration, and are not interpreted in any special way.

Let's try an example. Start with the following:
angle: 25°
seed: X
rules: X => F-[[X]+X]+F[+FX]-X and F => FF

Now, we iterate.

Generation 1: X
Generation 2: F-[[X]+X]+F[+FX]-X
Generation 3: FF-[[F-[[X]+X]+F[+FX]-X]+F-[[X]+X]+F[+FX]-X]+FF[+FFF-[[X]+X]+F[+FX]-X]-F-
[[X]+X]+F[+FX]-X

As you can see, the string rapidly gets bigger, so just as well we have powerful computers to plot the results.

After six iterations we end up with a lovely fern, according to the Wikipedia entry.



Implementation in Max 6

As part of its Jitter component, Max 6 includes the jit.linden object, which works on data stored in a one-dimensional single-plane matrix. To discover more, I read the Max Help Reference. That entry shows how the iterative process is established, and how to convert from Max symbols before populating the matrix. It also demonstrates the somewhat obscure format for the rules; we write the previous example as * X * F-[[X]+X]+F[+FX]-X * F * FF (spaces matter).

I didn't think much of the actual graphical output in the Reference example, but thankfully Jitter implements Turtle graphics by way of the jit.turtle object. The example in the Reference is trivial, demonstrating only that one needs to use spell to work through the symbols. The results can then be displayed using jit.lcd.

Unfortunately I couldn't find a robust example of a Lindenmayer System, so I set out to create one. L-System Garden allows you to choose from various preset shapes or specify the parameters individually. Then, almost too late, I discovered a patcher by David Cummings that performs similar tasks but without the direct interface implemented here.

After squashing a few strange bugs I thought it worthwhile to share the results with you here. I am hesitant to do so because the resulting shapes do not in fact correspond to the canonical examples. In most cases they look similar, and it is possible to find plant-like objects and surface tesselations. All well and good! But when it comes to Koch curves and Sierpinski triangles, they come out as strange distortions of the expected patterns. Maybe someone with more Jitter smarts than myself can help tend the Lindenmeyer Garden. I look forward to your comments and suggestions.

If you own Max 6 you can download the patch.

RELATED POSTS

4 comments:

robin said...

Two years on... can no-one help me improve this patch?

Anonymous said...

Nice work, I will try (fyi: newbie, i.e. step by step) ... (Might be too late, though).? Thanks anyway...

robin said...

It will be a challenge if nothing else!

Anonymous said...

Hey! Thank you for yout patch, it helps me a lot getting started with L-systems and turtle graphics in Max.

Post a Comment