I wrote two presentations for this project already - one was for a public presentation class, another was for the original class that I made the project for. They do an ok-ish job of explaining the project, but I'm going to repeat the process on this article to some degree. I'll post the screenshots again, and go over the basic concepts. One cool thing about this project is that it actually got shared in the MIT publication, MIT Spectrum, in a review of the class I built this project for. The class was 6.837 - Intro to Computer Graphics - and here is the article featuring my work. I ended up being a TA for this class later on in college.

The first thing I'll explain about this project is that I coded it in Processing, which is essentially a Java wrapper with some built in graphics functionality. At this point, my exposure to graphics was mostly from this class, from using Processing in high school classes, or from messing around in game engines - I decided to write it in Processing just since I had already written simple games and geometry in there, but honestly, Processing is good as a learning tool, but not for actual projects.

Ultimately, I did get some nice looking results. Here are some of the trees I came up with:

Some nicely generated trees. The last one used different settings I defined to make it look more like a willow tree.

So how are these trees generated? In short, the trees are recursive instructions to a "turtle" system of generation. They use what's called an L-system to define a tree structure over some number of iterations to determine how large the tree is, and with how many branches.

An L-system looks like a sequence of letters, with associated rules per letter. One simple L-system could look like this:

1. Start with "ABC"

2. A -> AB

3. B -> BC

4. C -> A

This definitely isn't a very useful system, but you can see how it changes each iteration. If we propagate the system forwards one iteration, A becomes AB, B becomes BC and so on, so the resulting string is "ABBCA". Another propagation, and it becomes "ABBCBCAAB". And the recursive behavior follows.

You can probably tell where this is going in terms of trees. Letters in L-systems can be used to represent parts of trees, or instructions on how to build the tree. For example, A might mean a branch/trunk of size 3. One iteration might turn A into two As - to naturally proportion "older" branches in the tree structure as larger.

A few extra instructions are needed to properly build a tree. The ability to branch is important - it is really the fundamental ability that makes the shape into a tree. So we need an instruction to branch - or change the angle we are building out the tree, and essentially adding on a small tree to our big tree, and then through propagations we will be recursively adding small trees to that small tree, until we reach the leaf nodes. Leaf nodes are another instruction we need - in an L-system, we can guarantee that they only appear at the "ends" of branches by having rules to always turn leaves into branches, or something else. When we add stochastic aspects to the algorithm we can keep some leaves on older branches.

We also need a way to store a location on the tree - I used brackets in the ruleset for the L-system to represent a saved position. The program essentially needs to keep a stack of positions for every open bracket, and each time it finds a closed bracket it pops that position and we can continue rendering from the saved position.

With these rules, we can start to build 2D plants/trees, or normal fractals.

2D example tree.

Rules:

X->F+[[X+]-X]-F[-FX]+X-[+X+[X+]]

F->FF

Start: X

F means move the "turtle" forward some amount. +/- change the angle of the turtle by some amount. Brackets save position and orientation.

Dragon curve fractal with L-Systems

X->X+YF+

Y->-FX-Y

Start: FX

Additional work is needed to port this into 3D, especially if we want it to look good. If you look into my original presentations, I included some examples of non-stochastic trees - they look horrible. More like geometric shapes. We can mostly keep the L-systems, but we need to change how the L-systems are computed and the actual generation of the trees. The most important change is randomness. Randomness can be introduced in a few areas.

1. Distance/amount of angle changed given a rule
2. Chances of rules being propagated - for example, chance of A becoming AA in the L-system generation
3. Random "mutation" chance - wrong propagations

In addition to randomness, some other aesthetic changes are needed. I implemented an "age" system to determine how thick branches/trunks should be in the final result, which makes a big difference. Leaves, too, were done on the rendering side - I was surprised when I first implemented it how quickly I could make them look good. Each is only around 6-8 vertices that I wrote out the positions for haphazardly.

There is additional expansion possible that I didn't fully get around to - namely, context-dependent generation. I did have chances vary based on factors like the "age" of the branch, but L-system rules and randomness factors can also be affected by surrounding letters in the L-system string, for even more realistic results.

I experimented a lot with L-systems and the stochastic parameters to get trees to consistently generate with interesting, unique, and realistic results. For good measure, I also generated some landscapes using Perlin noise and placed the trees on top:

Extra credit :)

I've been thinking about implementing another version of this project. It would be cool to generate some voxel trees. We'll see if I can get something like that working. I can imagine a turtle system for drawing it, but it would certainly be expensive. But it could be a cool web-based demo.