Procedural Tree Generator

This project is done in collaboration with Kelly Cho.

I. Overview

Trees and other organic vegetation usually appear in abundance and in a wide variation, are therefore very difficult to model individually. Instead, it would be much more efficient to be able to describe a species or type of tree and be able to create many unique plants with that specification. Our goal with this project is to procedurally generate natural looking trees.

In 1968, Aristid Lindenmayer developed a method to simulate the development of multicellular organims called L-Systems that is particularly useful in modeling plants. This method considers a plant to be modular, consisting several branching units or modules, that as a whole emerge as a plant shape. The paper L-systems: from the Theory to Visual Models of Plants (Prusinkiewicz, 1996) uses the L-System in combination with a turtle interpretor to render plants. We use the turtle interpretation of L-Systems described in this paper to create procedurally generated trees.

II. Live Demo - Coming soon!

III. Implementation

This project can be separated into two parts: tree generation using L-Systems that produces a string, and tree rending that reads and visualizes this string.

Tree Generation

L-System

An L-System is a parallel rewriting system that consists of a vocabulary, an axiom, a set of rules, number of iteration steps, and results in a sentence.

• Vocabulary - the collection of symbols that are the building blocks of this L-System
• Axiom - the initial state or seed of the tree
• Generation - the number of iterations the tree has gone through
• Rule - consists of two strings that are the predecessor and the successor; there can be multiple rules
• Sentence - the resulting string after n generations that describes a tree

With each generation, we sweep through the current sentence and replace all predecessors with their respective successors in accordance to the rules. Below is an example of this process, along with a visualization using a turtle interpretor as described in the next section.

Tree Rendering

Turtle Interpreter

The strings that are produced by our L-Systems can be efficiently visualized through a turtle interpeter. The turtle draws lines given a series of three commands: location, orientation, and pen on/off. This is percisely what our vocabularly describes.

The vocabulary and their definitions are listed below:

The turtle begins at the base and draws as it steps through the sentence, following each instruction, to generate the tree. A transformation matrix is used to keep track of all the operations performed on the turtle.

The [ and ] operations are used to create branches in the tree. Processing is capable of keeping track of a stack of transformation matrices. At each [, we simply push the current matrix onto the stack. At each ], we pop a matrix from our stack. This allows the turtle to return to any position and orientation on the tree and continue drawing from there.

Extra Shaping

• Angle Noise - Allow some noise when assigning angles to each rotating operation to create unique trees
• Branch Length Reduction - With each generation, shorten the branch length by some amount

Realism

While these branching visualizations are reminiscent of real-life trees, the realism can be greatly improved.

IV. Results