Wednesday, December 17, 2008

Book notes: the algorithimic beauty of plants

The Algorithimic Beauty of Plants (Prusinkiewicz, Lindenmayer) (pdf, 40mb)

The highlight of this book for me was the picture of Lindenmayer opposite the title page. But the doodles that some pillock has drawn thought Glasgow Uni's copy came a close second, on the plus side he gave up after 40 pages. Sorry about the constant diversions in what follows, there where some interesting ideas sketched out.

Rewriting mechanisms can work on continuous geometry elements (lines, points, hyperplanes etc), discrete arrays of values (matrices, Conway's game of life) or String (Chomsky-esque grammars). Each of these have variations of the rewriting procedures specified.

The difference between Chomsky grammars and the of Lindenmayer(L)-Systems outlined in the book are expressed as "In Chomsky grammars productions are applied sequentially, whereas in L-systems they are applied in parallel" Thus making L-systems a limed form of context-free grammars if there is one symbol on the LHS of a rule, or context-sensitive if there there are more non-terminals on the LHS of thr grammar.

These examples show some nice properties, such as lack-of intersections. These aren't properties of the system, but reather properties of the nicely throughout grammars. Small changes create intersecting systems.

It is easier to construct non-intersecting curve if a recursive mechanism is used. If we allow the parameterization of terminals (eg. giving them a recursion count) we can define a minimal grammar that is non-intersecting, and as long each sub-section guarantees non-intersection and each combinator also guarantees non-intersection for a given maximum size of sub-section (example on page 17?). It is even possible to enumerate the entire set of these non-intersecting tilings for a grid of a given size.

These ideas extend to three dimensions.

We continue onto using bracketed L-systems to represent trees. In these the [bracket] symbol represent pushing or popping the turtle's state. This means that a sub-section of the tree can be evaluated, then the context popped and another subsection ("branch") of the tree, that starts from the same physical coordinates, can be evaluated.

I wrote a crude context sensitive L system library in java, it can export to svg format when linked against the correct libs. Here's some of the output from the demo library - the example 1.31b) over 40-ish iterations:


Because the entire tree is rewritten each time I guess we're evaluating the tree at different points in it's life. Eg: by rewriting the trunk or the tree at each iteration we can broaden it.

The next bastardization of the Lyndenmere system is adding in a stochastic element. He really means random L-systems (but computers can't do random - right?) - perhaps this should be implemented using a real random number generator and submitted to a journal that no one reads...

So we have a non-deterministic L-system (multiple possible rules for each replacement) except that for each replacement, the avilable rules have some probobailty function (the sum of which should be 1). This creates some nice "natural" variations of grammars.

Context sensitive L-Systems are, as you'd expect, systems where the replacement made can be context sensitive (as in context-sensitive-grammar).

We're building a hierarchy of L-systems, very closely related to the hierarchy of grammars/complexity. Jumping to context-sensitive L-system climbs us one step further up the hierarchy. Given that most programming languages are definable by Regular Languages, we must be missing some trick to call apon almost Semi-Thue/RE languages to create a solution to the problem.

However I digress, context sensitive L-systems allow some neat tricks like signal propagation:

w : baaaaa
p1: b <> b
p2: b -> a

Which is a neat trick.It adds a fair bit to the computation of these systems because by the time we've considered the "branch" stack-system the notion of context is taken to mean physical-context (rather than closeness of symblos in the evaluation) so for each rule and each we need to consider the previous context as the parent-branch and the following contexts asall the possible child-branches.

Hogeweg and Hesper's A model study on biomorphological description (science direct | pdf | doi) analyses of the complete (3 thousand odd) evaluations of a binary context sysitive L-system. (w00?) and generate some nice earily biological, but-not-quite results (because of physical limitations etc...) The above image is an evaluation of one of their models. I spent a bit of time playing with random inputs for each of the possible binary rules 0 <> 0, 0 <> 1 etc... and the various inputs and came to the conclusion that most of the rule and input space was very dull - either creating long stringy repetitive trees, or not evaluating to anything at all. Even using longer random string as the axiom/input string didn't make it more likely that interesting output was achieved. This falls back to the old evolutionist line: life on the edge of chaos. Most the universe is dull, some of it is chaotic, and so messy as to be uninteresting. The bit between the two extremes is where my sandwich is. Problem is - most of the L-system input space produces nothing (or so tedius to be close to nothing). Just picking a random set of rules and starting point as in the given paper is very dull. Random walks from interesting patterns become dull quickly. I guess this is a dull, flat domain with sparse interesting peaks.

A typical random ruleset and staritng point will often just get bogged down -

random ruleset produces

Simple L-systems seem to give great insight into the structure of plants. But they themselves have to be designed by an intelligence - most of the rule-space is uninteresting. I wonder how hard it is to analyze a set of rules and a starting condition and find out if the output is interesting or uninteresting? Given that even finding out if the system halts is difficult, I guess interestingnesss of patterns would be an even harder problem to solve...?

Like Thompson and the book Growth-and-Form (my bible). TABOP moves into looking at section elongation or growth. He shows how Thompson's growth s-curves can be generated using the L-system (page 38)

w : a0
pi : ai → ai+1b0 for i < k
pk+j : bj → bj+1F for j < l

If you evaluate this and count the number of F's the growth curve is sinusoidal and segmented in the manner that is described in that biology text book. Defn. an area for investigation - is the structure robust like the grass-hopper's leg that reorganizes itself when you chop the middle out and turn it around?

However the book goes on to note that "it is often difficult, if not impossible to find L-systems with their required growth functions". And a quote from Vitanyi that "The slowest increasing growth we can obtain by allowing cell interaction is logarithmic". I guess the default state for L-systems is cancerous growth :(

But to compensate for this growth-control problem, another generalization (spotting a pattern yet?) of L-systems is introduced - Parametric L-systems. Here each symbol is given a set of parameters, and a replacement can only take place if a logical statement associated with the parameters is true. The replacement produces more symbols that can have a mathematically altered version of the parameter embedded within them. Once this system is dragged into the context-sensitive model, it starts to look a bit of a mess.

Of course, with the addition of parameters, the terminal symbols can be defined wrt the parameter, allowing much more complex and geometrical shapes.

The second chapter discusses the modeling of trees. Starting with a statement that self-sensitive L-systems have been avoided to date because of their complexity, then goes on to review the literature on tree generation. I've moved these to a following blog post. This chapter of TABOP ends with the best example of not-letting-computer-scientists-decide-the-colour-scheme imaginable:

Chapter three "Developmental models of herbaceous plants" then returns to trying to ensure that each parallel step in the evaluation of an L-system corresponds to a step in time.

The phrase database amplification is used here and defined as "the generations of complex looking objects from very concise descriptions". The phrase is a little under specified and over abused in the literature.

Another variation of the L-system is defined, the tabled L-system. This uses a different table of production rules to simulate changes in the environment, for example one for winter (non flowering) and summer (flowering). Seems a little dubious to be using discrete-evaluation steps to model continuous time, and with tables as well we aren't doing a very good job at developing the goal - a continuous time model of a growing plant. I guess it's possible (with enough) rules to smooth this out. But as we've already established, we've got a Turing complete system in our L-systems, so we can do anything that is computable with enough rules.

The rest of the chapter bores on through some trivial L-systems that represent common flowering patterns in plants. I cut down L-system ("partial L-system") is used here for teaching clarity.

Chapter 4 deals with the phenomenon of Phyllotaxis in a dull generative way. You can see these patterns in the seeds on a pine cone, or centre of a sunfower etc... These kinda cool patters where discussed in more detail in How the Leopard. They refer to the way that several reoccurring features of plants occur in similar spiral patterns.

The basic generative algorithm takes the observation (spirals of points with 137.5 degrees between consecutive points) and converts it to an L-system using the model:

for incrementing n for each point
phi = n * angle ("correct" angle is 137.5)
radius = c * sqrt(n)

Starting from the observed results, a mathematic system is deduced that can construct Phyllotaxis patterns. Using TABOP generative model and varying the angle the following animations where made (java src code):

Changing the angle over the range 135 -> 140 degrees:

Changing the angle over the range 137.25 -> 137.75

There are lots of ideas as to why Phyllotaxis patterns are so common in nature, but no one seems to know for sure. Looking at my videos above it's possible to see the different phases that the form goes through. The angles chosen by nature are where two patterns collide lie (life between the gutter and the stars). Is this coincidence? Is it the best point to give continuous coverage to all areas (look at the following from the other side of the room - one pattern stands out as being the most homegenous) Interesting experiment would be to draw Voronoi cells around each point to discover if the magic angle is just high-coverage local maxima (easy for evolution to reach) .


The chapter also discusses the derivations for simulating Phyllotaxis on a cylinder, again without any insight as to why the patterns would be as they are.

Chapter 5 discusses how to model plant ogans. So that'll be leaves, staymen (plant porn!), petals etc...

First approach is to used artist modeled surfaces. These can be scaled and stretched by the parameters of the underlying L-system, but not changed too much. An attempt is made to define the normal L-Systems (driving a turtle) to trace closed boundaries of a leaf, but it isn't very successful, and the leaves are all the same shape. A modification is proposed that uses a series of point to define a leaf's boundary. These points are defined by the turtle's location at t given time. It produces a more robust system.

Another method presented is to use additional operators and a stack of polygons - you add vertices to the current polygon until you reach the push symbol, then you start adding to a new polygon. When you reach a pop symbol you draw the current polygon and go back to the previous example. More interesting than either of these two variations in interpreting an L-system is the idea that there must be a huge class of algorithms out there that can operate on a subset of the output of an L-system (time, location, points, edges etc...)

These techniques, when used with careful grammars can create realistic leaves that can grow through time. However I'm left with the impression that there are easier ways of defining the same shapes.

Map L-Systems are introduced later in the book. These are remarkably similar to Stiny's Shape Grammars (all the journals containing the papers on these are missing from the Glasgow library...). You start with a labeled graph and perform parallel substitutions on given edges.


These replacements can include adding stubs of additional lines, magic occurs (orange line above) to match one pair of stubs with the same label and performing a replacement. This is a non-deterministic step. Still it is a nice way of working with graphs and produces some remarkably varied textures. A further modification over the above is to match directed line segments.

Eventually the book decides to get self-sensitive (in a way) and uses the map-L-Systems(ish) to continually divide a map of springs. This system simulates the pressures inside a cell, and provides some interesting techniques for modeling cellular growth. This feedback mechanism has an effect on the layout (if not the topology) of the cells. Basically it's using a these L-systems as a crude approximation of Induction (the biological growth term for cells differentiating based on surroundings) -

cell induction

i) two adjacent regions of cells
ii) new cell type induced by adjacency
iii) strata of cells via induction

Sub-goal: investigate the results of modeling cellular machines continuously compared to L-Systems.

The last chapter of the book deals with the fractal nature of nature and L-Systems. An introduction to Iterated Function Systems is given. These give true self-similarity (as do the class of L-systems without terminal symbols) by endlessly transforming the input set of points by a series of (linear) functions. The input points are continuous in a given bound. This leads to several predictable methods of rendering IFS'. Finally a technique is given for converting a one line L-system to an IFS, with very pretty results. Can't think of a reason I'd want to do it tho!

In summary:

Mainly a list of variations on the theme of Lindenmayer(L)-Systems:
  • stochastic
  • self-sensative
  • context sensative
  • 3D
  • stack-operations [brackets]
  • parametric L-systems
  • table L-systems
  • map L-systems

I have a bit of a problem with this as it seems to be largely botched model, each bastadization attempts to make up for some short coming of the previous models. Perhaps this shows L systems provide a valid framework, because it is so easily extended, but I'm not convinced. When you see a model overloaded like this in the software engineering world it should ring alarm bells. But it is also horribly open to abuse by authors who extend L-systems to the point of any-other language. When (as Chomsky points out in Three Models for the Description of a Language) a grammar should reveal some insight into the structure being examined. Wheras these extended L-systems in practice are a mess of concepts and corrections, showing little more insight than if if the same structures where specified in any other programming language.

From an engineering point of view simple L-systems work well because there is little growth, just structure. As you start to try and simulate growth and structure using the same technique, it become painfully clear from the mess of L-systems in the book and other literature that the system. I can't help feeling that you need to model the two systems individually; L-systems seem to work well for structure but are clumsy at best for simulating growth. This is a view shared by Hart et al in the introduction to the paper Structural simulation of tree growth and response.

An annoying thing about procedural modeling is the quantity of domain specific knowledge you have to pick up to discuss features. Plants have a lot of parts I didn't realize needed names.

No comments:

Post a Comment