« Back to Processing

Tutorial #2: Recursive trees

| No Comments | Published on April 10, 2008
The content that follows was originally published on the Don Havey website at http://donhavey.com/blog/tutorials/tutorial-2-recursive-trees/

Recursive tree previewToday’s tutorial is going to be shorter and sweeter than the last.

The problem we’ll address is how to structure a tree-like object in a way that’s similar to a real-life tree. It must contain a set of user-defined variables that affect the “species” of tree, but still allow some random variation within the tree’s growth.

I created something similar to this a couple years ago, but have reworked it to be simpler and more efficient. We’ll be using this Tree object in the “Lettertree” tutorial to come…

Here’s the finished product: Recursive tree

And here are the classes: Recursive tree classes

Let’s take a look at what we’ll be learning:

  • Transforming points in three dimensions
  • Randomizing variables
  • How to structure a recursive object

And now why would we want to learn it…

The use for a recursive tree

The most obvious reason to write a tree generating script is… to generate trees. It would be fairly simple to export the coordinates of this tree into any 3D modeling software. Texture mapping and such would be tricky, because as you’ll see, this script uses segments as branches, not three-dimensional shapes. But nevertheless, it would be a nice addition to your next architectural project: some non-generic, bare trees in the landscape.

Of course, branching structures are used in more than just trees. Let me know if you think of other uses. Maybe something like… plotting three-dimensional decision making graphs? Where the sum of a user’s choices is represented by a single point within a cloud of possible outcomes? That could be a nice way of comparing the results of a survey in three dimensions.

And now, let the games begin…

Without further ado…

What is recursion

In computer programming, recursion refers to a process that applies itself to its own output until a given condition is met. So in our case, the pseudocode illustrating recursion looks like this:

class Branch{
  Branch(level){
    if(level<max_tree_levels){
      for(int i=0;i<branch_children;i++){
        branches[i] = new Branch(level+1);
      }
    }
  }
}

So what we’re doing is creating branches that “hold” or “own” an array of more branches until we’ve reached a given level of recursion. The branches contained within a branch are typically referred to as “children” of that branch, and in turn, the word “parent” is used to refer to the branch that contains another.

The process is fractal in nature, but does not continue infinitely, thanks to our recursion limit… or our computers would explode in a fiery ball of doom.

Hopefully you can tell that the number of branches increases exponentially, with the exponent determined by the max_tree_levels variable above. The equation to determine the total number of branches in the example above would be something like this:
n = branch_children + branch_children^2 ... + branch_children^tree_max_levels
And the total number of one-way paths between the base of the tree and the tip of a branch would be:
n = branch_children^tree_max_levels
Not too bad, right?

The Branch class

We’ll be taking advantage of the fact that the first Branch of our Tree actually contains all the other branches, or rather, it contains the second level Branches, which contain the third level Branches, etc. etc. etc.. This will allow us to manipulate the entire tree by adding a similarly recursive structure to our Branch methods. Let’s look at the rotate() function as an example:

void rotate(float $rz,float $ry,float $x,float $y,float $z){
  for(int i=0;i<nbranches;i++){
    branches[i].rotate($rz,$ry,$x,$y,$z);
  }
  p2.rotate(cos($rz),sin($rz),"z",$x,$y,$z);
  p2.rotate(cos($ry),sin($ry),"y",$x,$y,$z);
}

Within that for() loop, we’re making sure that this Branch object’s children are rotated first. Let’s look at how that affects the order in which a method executes. In this example, we’ll assume that each Branch contains only one child Branch, up to a maximum of three levels:

  1. The rotate() method is called for the first Branch.
  2. The first level Branch calls the rotate() method for the second level Branch.
  3. The second level Branch calls the rotate() method for the third level Branch.
  4. The third level Branch has no children. It rotates itself.
  5. Third level rotation complete. The second level rotates itself.
  6. Second level rotation complete. The first level rotates itself.

This order of operations is a convenient way to rotate the Tree, but it will also play a crucial role in the Tree’s structure. Notice the code for the initialization object looks like this:

void init(Tree $t){
  if(nbranches>0){
    $t.branches[$t.nbranches] = this;
    $t.nbranches++;
    for(int i=0;i<nbranches;i++){
      branches[i].init($t);
    }
  }else{
    $t.buds[$t.nbuds] = this;
    $t.nbuds++;
  }
  rotate(rz,ry,p1.x,p1.y,p1.z);
}

Similar to how the rotate() method bubbles up to act on the top Branches first, the very top level is initialized first and rotated according to the y- and z-rotations defined in its constructor method. Then the second-to-top level rotates the top level again before rotating itself according to its own y- and z-rotations. By the time we reach the bottom level, the top branches have been rotated n times, where n is equal to the number of levels. The second-to-top level has been rotated n-1 times, etc. etc. etc.. See where I’m going here?

Thanks to this hierarchy, what we can do is pass each Branch an identical y- and z-rotation, which are compounded on top of the Branch’s parent’s rotations.

Why not just assign the correct rotation to begin with? Well because rotation in three dimensions is not a piece of cake, since we’re rotating about two axes. It’s not a matter of simply adding up the angles. Directly calculating the rotations might slightly lessen the number of trig calculations required to initiate the tree, but our method makes the code much much cleaner.

The Tree class

Tree before initializationBy now you’ve noticed that our Tree is initialized after the entire thing has been constructed, meaning that the Branches are not rotated until all of them have been defined. So what does the Tree look like before it’s initialized? Well, like a stick. All of the Points that define our Branches/Segments are aligned along the y-axis. Something like in the image on the left. Pretty boring.

Once we trigger their initialization via Branch #0 (the trunk of the Tree), each Branch will be rotated first around the z-axis (with the point of rotation at the base of the Branch being rotated), then around the y-axis according to its place amongst its siblings.

Apart from an array of Branches, the Tree object contains a list of “buds”: the final level of Branches. Their endpoints will be colored.

Randomizing variables

All of our Tree-related variables are contained within our Tree class file and are pretty thoroughly commented. They’ll be plugged into the Branch class’ constructor object. I’ve included an overall “randomness” variable that offers a quick way to affect the irregularity of the Tree. Here’s an example of the final results with all sorts of randomness vs. zero randomness.

In our tree.pde file there is a function that looks like this:

float randomize(float $n,float $r){
  return $n+random(-$r/2,$r/2);
}

What that will do is randomize a variable to within a given range. As an example, if we pass the “branch_length” variable (70), along with the “branch_length_r” variable (40), the function will return a random number within the range of “branch_length – branch_length_r/2″ to “branch_length + branch_length_r/2″ (50-90).

Wrapping up

The rest of the code in the included files is pretty self-explanatory. I give the Branches some thickness using the lineWeight() setting, with the width determined by a Branch’s level.

Here are the classes again: Recursive tree classes

And one more link to the finished product: Recursive tree

Coming up next… a tree made of letters… it’s a Lettertree!

Categories: Processing / Tutorials

Tags: / / / / /

Leave a Response

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>