L-systems, anyone?


I’ve been tinkering with parametric L-systems, the simpler 0L flavor, and I was wondering if anyone has hit on a particularly good parsing strategy for them or any suggestions in general.

What I’ve done is more or less a recursive macro-like string replacement, and it works pretty well, but maybe there’s a better approach or one that’s just different and interesting. That’s really no biggie though, since it’s not a very time consuming process and it only needs to be done once for each tree.

If anyone has any ideas on generating a continuous mesh, that’d be sweet :slight_smile:

Also I’d be very interested in any rules that create some nice trees and bushes. I may need to go to a 1L or 2L system to get the most convincing results, but I’ll resist that path as long as I can, in the interest of keeping things as simple as possible.

If you haven’t heard of these creatures, everything you need to know and more can be found in this book and website:

You can also read about them in Texturing & Modeling, A Procedural Approach, 3rd Ed.

Here’s a quick rub, if you’re interested.

A L-system is basically a grammar, like you would use to define a language in flex/bison for example. It’s a set of production rules for an input string, or axiom in L-system parlance. An example might look like this:

axiom: AB
rule A: B
rule B: BC
rule C: CA

Starting with the input string AB, we apply the production rules, one at a time, rewriting the original string at each step.

AB <- start string, apply rule A then rule B 
BBC <- apply rule B, rule B, then rule C
BCBCCA <- and so on
BCCABCCACAB <- and so on ...

and so on. Lots and lots of data from a little input.

The difference with parametric L-systems is that the rules themselves can take parameters. So you could do something like this instead

axiom: A(5,6)
rule A(x,y): B(x,y)
rule B(x,y): B(x,y)C(y)
rule C(y): C(y)A(1,y)

Not that you’d want to. You can get even fancier by adding predicates (conditions) to the rules, so that they only kick in if certain patterns are matched. Like, match rule A, but only if preceded by B and followed by C, otherwise use another version of rule A. You can really go nuts with this stuff.

Anyways, the idea with L-systems is that you use turtle graphics commands instead of As, Bs and Cs in your input string, so you are left with a long string that represents the geometric and graphical structure of the trees. What I’m trying to come up with a cool way to turn these commands into a nice, smooth, continuous mesh (or meshes).

Preliminary results are encouraging. You can create some really nice looking trees, but my end-to-end cylinders, which I use to represent the trunk and branches, have got to go :slight_smile: The trees look like they’re suffering from some strange tropical disease.

This stuff is way too fun to play with, so be warned!


Wow, it looks really great! I will shurely play with it one day.

An idea: for generating small plants you should attach a lief to the end of each outer branch (could be just a triangle with about 70 degrees angle).
As for trees, I really don’t know :frowning: I’ll go for a walk today and will observe how the leafs are growing there :slight_smile:

very nice algorithm, indeed.

while i was googling for L-systems, i found the pythagoras tree (sorry, german site…left/right click on the tree to make it grow/shrink)

the advantage, in my opinion, is that the branch diameter decreases as the tree grows.

There are companies based on tree rendering.
Check this out: http://www.speedtree.com/
I’d bet the beginning was also just an L-system to play with. :slight_smile:

Thanks a bunch for the interest guys!

Good idea about the leafs Zengar :slight_smile: I’ve been doing a lot of walking around and looking at trees too. The tricky part for me is turning my ideas of what a tree should look like into input strings and rules. There’s some rhyme and reason to it to be sure, but it’s not all that intuitive, even less so for an artist I imagine. But I can worry about a good interface later :slight_smile: There are some good systems given in the book that produce some really nice trees, so I’ve been tweaking them like crazy hoping I’ll end up with more than variations on a theme. Sadly, I think that’s all I’m going to get, unless I really branch out :slight_smile:

Thanks for the link RigidBody. Yes, decreasing the diameter helps a lot, and there are graphics commands solely for that purpose. That’s what I’ve been doing with my cylinders, but somehow I feel it would look better with a nice mesh as opposed to cylinders, perhaps with a little noise added in to simulate knots and general imperfections. I guess the cylinders just look to “straight” :slight_smile: I could just subdivide cylindrical meshes and displace some vertices with noise, and I may go with that unless there’s something cooler around the corner.

Thank you Relic. That’s inspirational :slight_smile: I’ll bet many tree modelers have L-systems lurking inside, but I haven’t really looked at many. MojoWorld, mentioned in Texturing & Modeling, supposedly uses them as a basis for their trees. I really can’t think of anything cooler. I suppose a really skilled artist could work some magic in a good modeler, but I’m really big on programmer art. Go programmers! You can do it! :slight_smile: Alas on my shoe-string budget, it would seem that I have little choice. But that’s OK with me :smiley:


As I played Oblivion just now, I carefully studied the trees there (Oblivion uses the Speedtree engine, actually). They seem to display the leafs with billboarding. I guess they render a pseudo-transparent textured quad with the liafs image at the end of each branch. The thickness of the branch is reduced with each generation.

Jeez, Oblivion. I’ve been meaning to get a copy but I really need to get some work done this year. I haven’t been right since Arena and Morrowind :wink:

But yeah, some quads should do very nicely for the leaves I would think, with a good variety of nice leaf textures. I’d like to have a stab at generating those as well. I think some procedural texture generation would go a long way for trees, leaf and bark alike.

On the mesh thing, I’m thinking more and more this is the way to go, with some LOD thrown in for good measure. I think it’d be pretty easy to control if certain levels where meshed serparately. Hey, maybe subdivision surfaces would come in handy here. Hmmm…

Just a very rough idea: The ugly things with a cylinder-based rendering strategy are the branches. Now what about a metaball-like approach, like so: determine all the sticks going out from the branch and assign a cylindric potential to each of them based on the radius. Draw the branch with one of the standard iso-potential renderers (the one in Blender works with iterative cube division, as far as i know).

Great idea Dolf. I’m looking into this now, but I confess my blobs are a bit rusty :slight_smile:

I’ve found some good material on them and it looks like this could work, with a cylinder/capsule-like potential field, as you suggested. I’ll hand wave a bit more once my blobs are gellin’ :smiley:

Thanks for the reference to Blender too. It would certainly be worth looking into the source. I’m looking at one volume method spin off of the marching cubes algorithm, the so called “marching pyramids algorithm,” and it looks promising (read: simple).

Many thanks!