Growing Trees in Your Computer

Plants and flowers are beautiful. That’s the main reason we keep them around our houses. Supposedly, if you want to have any chance with girls, at one time or another you’re going to have to give them flowers of some kind (although I personally prefer to give potatoes). Greenery is life. A house full of plants, means a healthy, vibrant house, a place you can call home.
Unfortunately, while flowers and decorative vegetation are nice and all, they have their problems. You have to water them, they can get infections and parasites, and are doomed to eventually wither and rot. So while many people grow spices, ferns, or orchids in the living room, I prefer to grow a different kind of tree: the digital kind.

Ever since high school I have been interested in computer graphics algorithms, especially those relating to fractals, which are one of nature’s ways of blowing our minds. About a year and a half ago I came across a wonderful book called “The Algorithmic Beauty of Plants” (available here, in addition to other lovely articles). The book describes many ways and considerations of creating artificial botanical objects, like trees and flowers. I decided to tackle the simplest of these methods – generating plants using L-Systems.
L-Systems are a type of “rewriting systems”, which are a part of mathematics and computer science. We start with a series of symbols, and then go through an iterative process: during each iteration, we do a “find-replace” on each symbol, replacing it with a series of others. The replacement for each symbol is known as a “production rule”. For example, suppose we have the following system:
Initial Symbols: AB
Production Rules: (A → AA), (B → BAB)
So during each round, we simultaneously replace all A’s with AA’s, and all B’s with BAB’s. When generating, we get:

Zero iteration     : AB
First iteration     : AABAB
Second iteration : AAAABABAABAB
Third iteration    : AAAAAAAABABAABABAAAABABAABAB

And so on.

There are many variations to this model, but this is the most basic form of L-Systems, called a “Deterministic Context-Free System”. Deterministic means that each symbol can only be replaced by one string. Context-Free means that when we replace the symbols, we do not look at their surroundings, but only at the symbols themselves. Seemingly, this is just a rather simple and not-so-helpful way of creating strings. Why would we want to create strings in the first place, and how does it help us generate computer based imagery? L-System’s true power comes when we attach a graphical meaning to each of the symbols used.
Suppose that we have a sort of “pen” that we can draw with. We then treat the string of symbols that we got from the L-System as instructions on how to draw using that pen. One symbol might mean “draw a straight line”, another might mean “the next line will be drawn at 45 degrees to the left of the previous one”, still another “start drawing thicker lines”.
By forming the right production rules and symbol interpretation, we can reach all sorts of neat graphics-related objects. For example, the Sierpinski Gasket, a commonly known fractal, can be generated with the following system:
Initial symbols: A
Production Rules: (A → B−A−B), (B → A+B+A)
A and B both mean “go forward”. The symbols – and + mean “turn left 60 degrees” and “turn right 60 degrees”, respectively. Here is what we get after 7 iterations:

Wow! L-Systems are cool, you must be thinking. Well, I think so too. So I decided to have a go at creating plants, and wrote a simple L-System drawing program in C++ (I used it to generate the picture above).

And here is a simple plant, with production rules taken from The Algorithmic Beauty of Plants. Plants are created using branches: We start drawing from the trunk upwards, and we have a symbol in our L-System that tells us “start branching” and “stop branching”.

Well, my plant is very nice, but I will have to do something better. Sure, it looks like a plant, but I can’t recognize what kind. Maybe some sort of wheat, or a type of fern. In any case, I certainly didn’t intend to create wheat or fern. Can I get my L-System to generate a lifelike item? More specifically – can I write a set of production rules and parameters so that I will be able to model a specific tree or plant?
I surely did hope so, and decided to try and recreate the trees in the park beneath my apartment.

There are several factors to consider when trying to generate trees:

  1. The general shape of the tree – how its branches curve, whether they are straight or leaning;
  2. How thick its trunk and branches are in relation to each other;
  3. How its leaves look like and are how they are distributed.

Armed with my notebook, a pencil, and a tape measure, I set out to the garden below to get some answers.

  1. I sketched some pictures of the trees, so that I would get a general feel of how they look like.
  2. I climbed on some trees and measured the thickness of the branches as far as I could. Unfortunately, these trees are rather thin, and were not at all comfortable for climbing. I could get really good measurements from only one tree. I take it to be representative.
  3. I mostly ignored the leaves. Since they appear only at the end of the smallest branches, they can be treated as separate from the general topology of the tree.

Here are some of the results in raw form:

First, we need to think of a way to treat different branch thickness. Obviously, the trunk is the thickest part of the tree, and as we go up, the branches get smaller and smaller. The mainstream solution is to decrease the drawing size every time you branch. Meaning, the L-System will have a special symbol that tells it “You are now starting a branch; from now on, draw thinner lines”. The question is, in what way should we make the branches thinner?
In order to answer it, I plotted the circumference of each branch as a function of its index. The higher the index, the smaller the branch. Here is a graph taking the average of all the trees I measured, along with a best-fit for an exponential curve.

We see that an exponential curve fits the data very nicely. This implies that each branch is smaller by a constant factor than its father – the one that it branched out from. I do not know if this is true for all trees or just for this type of tree, nor do I know the exact biological reason that causes this phenomenon (although I suspect that it has to do with physics, stability, and load bearing) – this is just empirical evidence. However, empirical data suit us just fine, since we only want to model the appearance of the tree. In any case, the branch-shrinking factor can be extracted from the graph.
That solves the branching problem. As to the shape problem – as you can see from the pictures, the trees do not grow upwards in a straight line, they protrude at weird angles. I took this into account by sometimes changing the direction in which a branch grows.
Finally, the leaves. Leaves can also be described by L-Systems just as well as an entire tree, and are just as fractal-like. However, for the sake of simplicity, I chose to draw just small circles at the end of the final branches.
I put the data in, played around with the equations a bit, and finally got to a good resemblance. Along the way, I also tweaked up the model to make it stochastic – when choosing how to create the tree, there is a little bit of randomness involved, so that the trees generated by the program tend to be different, despite being built out of the same parameters.
Here is a sequence of trees, built up from 0 to 6 iterations:

And here are some more realistic-looking trees:


I love this type of generated imagery. Look at how complex those shapes are – they really do look like trees. But very little information was required to generate them. We do not have to store a lot of graphical data in order to recreate them or to keep them in memory – there’s not a trace of thousands of polygons to remember. All we need are just the parameters (in this case: thickness, crookedness, branch angle, and six production rules); from them we can derive the entire image. And that is the real power of L-Systems (and other similar iterated systems): to be able to generate lifelike images, using simple algorithms and without human intervention, from very little data.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s