Procedurally Generated Trees

If you've ever played games like Minecraft or No Man's Sky, you've seen procedurally generated terrain. An infinite array of rivers, mountains, and trees can be generated from simple mathematical formulas.

If you're googling the word procedural right now, we aren't talking about in the sense of procedural law or whathaveyou. We're talking about Procedural Generation. In Minecraft for example, when you start a new game, all of the terrain is procedurally generated. No one sat down and modeled the mountains, lakes, and rivers etc. around you. They were generated algorithmically.

In this Instructable (my first one by the way) I'm going to teach you how to generate a fractal tree from a mathematical "seed" using OpenSCAD. OpenSCAD is a programming language that allows you to generate 3D models using code rather than sculpting or modeling them by hand.

Then I'm going to show you how to make the code customizable, and publish it to Thingiverse as a Customizer so that everyone can "grow" their own unique tree. Customizer is an app from Thingiverse that allows everyday users to plug in their own variables, such as the seed, and run your code to generate an object, directly through the website.

Last, you'll print out your tree so that you can use it in your next model car, train, architectural model, or diorama project.

What you will need:

• A good computer. Compiling OpenSCAD code is a very intense process that will take advantage of all of your available cores and memory and can take hours.
• Free OpenSCAD software. This is available for free from http://www.openscad.org/
• A free Thingiverse account. If you wish to publish your tree so that others can print it and share pictures of their own printed trees. http://www.thingiverse.com
• 3D Printer. This is needed to print your tree. If you don't have one, of you can order a print from your local Hub at 3D Hubs. You can visit my Hub here.
• Acrylic paint. If you want to paint your tree.

If you like my Instructable, please consider voting for it in the 3D Printing contest, using the vote link at the top right of your screen.

Step 1: Recursion

Introducing Recursion

Our fractal tree is going to use a concept called recursion. Recursion basically means a function calls itself, over and over again, until a stop condition is met. One common example of a recursive algorithm is calculating the Fibonacci sequence. The Fibonacci sequence goes 0, 1, 1, 2, 3, 5, 8, 13... The first two elements are 0 and 1, and then each element after that is the sum of the last two elements. So we can write a function Fib(n) where n is the index (using C/Java syntax) as:

<p>int Fib(n)<br>{
     return n < 2 ? n : Fib(n-1) + Fib(n-2);
}</p>

So lets say we want to find the fifth element, Fib(5) calls Fib(4) and Fib(3), and so on in that fashion until Fib(0) or Fib(1) get called. This is the "stop condition" in which it just returns 0 or 1 instead of calling Fib() again.

True recursion is not possible in OpenSCAD, because it's not a functional programming language. OpenSCAD uses Modules, which are similar to functions or methods, but are compiled in a different way. In traditional programming, the compiler turns your code into a set of instructions for the computer to execute. In OpenSCAD, the compiler turns your instructions into a 3D model.

When you write a C program, for example, that calculates the first few elements of the Fibonacci sequence, it compiles down to the same size as one that calculates the first million elements of the sequence. When you do something like this in OpenSCAD, your output is a million times bigger, and takes a million times as long to compile.

For this reason, you have to be very careful not to go through too many iterations!

In most versions of OpenSCAD, it won't let you compile a module that calls its self directly, so I use the following pattern to get around it:

• First create module A, and generate some geometry within it.
• Then inside of A, call module B.
• Now create module B.
• Within it, do nothing except call module A.
• A is now a de facto recursive module. (Make sure to have a stop condition to avoid an infinite loop.)

Step 2: Building the Trunk

Recursive algorithms are commonly used to generate fractals, or infinitely complex visual patterns that are self-similar. (https://en.wikipedia.org/wiki/Fractal) They are created by repeating simple processes over and over.

The Fibonacci sequence that I mentioned earlier, can be used to generate a common fractal called a Sierpinski Triangle, for example. (https://en.wikipedia.org/wiki/Sierpinski_triangle)

If you've never coded in OpenSCAD before, or never coded at all, don't worry. Its pretty straightforward and you can get a long way by copying from my examples and using the cheat sheet http://www.openscad.org/cheatsheet/

Lets say you want to make a sphere, you would use the sphere command, and give it a radius like this:

sphere(5);

now lets say you want the sphere to be over to the right, you would translate it along the x axis, like this:

translate([10,0,0])

{

sphere(5);

}

And so on in that fashion...

You're going to start off by building the "Trunk" module. This module generates a vertical cylinder, representing a segment if trunk. It caps it off with a sphere, which will serve as a "knuckle."

Next you're going to create module "branch_one". Create a cylinder to represent a single branch. Make the base radius greater than the top radius, so it will be tapered toward the end of the branch.

Next, this is where the magic happens. You're going to call module "Trunk" again. Pass in an initial depth of 5, and watch the trunk grow!!

As you can see, you'll decrement the depth with each call. This will create the stop condition, when the depth reaches 0. That way you can pass in the number of recursions. Also pass in a size. When you call the next module, you'll pass size * 0.9 as the new size, so that each successive branch will get smaller and smaller.

In case you have trouble downloading the example code from Instructables, I've thrown it up on GitHub as well https://github.com/steveweber314/ProceduralTrees

Step 3: Branches

So far you've created a stick in the ground, but not a tree. A tree needs branches. Within the "branch_one" module, edit the code so that it calls "trunk" twice, once with a small amount of rotation to the left, and once with a small amount of rotation to the right.

This means that with each iteration, the each branch will grow some, and then split off into slightly smaller branches to the left and right.

Then each of those branches will grow a little bit, and then split off to the left and right. At each iteration it will repeat the process, increasing the number of branches exponentially.

Now you've got something starting to resemble a tree.

Step 4: Before We Move On....

Within these last few steps, small alterations in the logic will produce vastly different end results. Once you complete this Instructable, you'll have the knowledge you need to create your own variations, or species, of tree.

Think about thew different types of plants you want to make, and the basic pattern that they follow as they grow. Most plants follow a fairly simple pattern.

Here, for example, I've made a "cactus", still using the same basic system of spheres and cylinders. What I did was follow a pattern of: most of the time, keep growing up. Some of the time, split off at a 90 degree elbow in a random direction, and occasionally, stop.

(You can customize it on Thingiverse at http://www.thingiverse.com/thing:1637232)

Now, you might be thinking to yourself, what if there was a way to express these patterns in a more general way. That's where Lindenmayer Systems come in.

L-systems, as they are called for short, use a code of letters, strikingly reminiscent of a DNA code. You might have one letter that indicates to keep going straight, one letter that indicates you to turn left, and so forth.

While I did not use L-systems in my examples, they are worth reading up on because they are often used in procedural generation http://mathworld.wolfram.com/LindenmayerSystem.htm...

Step 5: Leaves

A tree needs leaves, too. When we reach the stop condition, let's create a sphere to represent a bundle of leaves at the end of each branch.

In my example, I colored the leaves so you can see them better. You don't normally need to worry about colors in OpenSCAD because you're going to be exporting it to a colorless STL file. STL is the most common format for 3D printable models. Since most 3D printers only print one color at a time, the format isn't designed to handle more than that.

Step 6: Adding Entropy (Randomness)

At this point what you've created is a perfect example of a fractal. Fractals use a simple set of rules, implemented over and over again, to create something incredibly complex. Our fractal has a trunk, a set of branches, and some leaves, but it still looks more like some kind of fern than it does a tree.

Nature is full of fractals. From the longest coastline to the tiniest snowflake. Sometimes They are very orderly, as in the spiral of a sunflower's seeds. If you wanted to generate a pine tree, for example, each one would look the same as the next. Other times, nature's fractals are much less predictable, like a lightning strike, or an oak tree for example. That is the kind of tree you are going to generate here.

Add three new modules for different types of branches, where the tree splits into 2, 3, or 4 directions. Call them "branch_two", "branch_three", and "branch_four" (see my code sample for all the angles.) Add logic to the "Trunk" module to choose randomly between them. Copy the code from "branch_one" to the new modules, and then modify the modules so that "branch_one" does not split, and "branch_three" splits three ways, and so forth. You now have a much more randomized, much less predictable looking tree. Its almost finished.

Next we will add a degree of randomness to all of the angles where the branches separate from each other, and all the size scales of each branch. Please refer to the code listing as there are too many changes to screenshot them all there.

Now that is a realistic looking tree!

Step 7: The Seed

Before you can export your tree as an STL file for 3D printing and sharing on Thingiverse, you will need to render it. This will take a while, so be patient. It takes OpenSCAD longer to render than it does to preview because it calculates the geometry much more accurately.

Why did your rendered tree come out different than the preview? OpenSCAD uses a pseudo-random number generator, which means it produces a predictable sequence of numbers, given the same starting number, or seed. Since you aren't passing in a seed, its using a random one.

random_seed = 1138;
...

module trunk(size, depth, seed)
{
    //create an array of random numbers
    operation = rands(1,4,1, seed+1);
...
trunk(height, number_of_iterations, $fn=level_of_smoothness, random_seed);

By passing in the seed, you can produce predictable results each time. In a way, your tree "grows" from that seed. You have to pass the seed along through the modules, incrementing it each time, or else you would end up picking the same random values at each iteration, and end up with a symmetrical, unnatural looking, tree.

Step 8: Thingiverse and the Customizer App

Next, you're going to add a base, and include a text library that will allow you to add some text to it. The base is made of a cylinder on top of another cylinder. The top cylinder tapers down to match the radius of the bottom of the trunk.

use <write/write.scad> 

The text will wrap around the lower cylinder so that you can write your name, or anything else you want, on it.

I try to incorporate a line of customizable text like this into my customizers whenever I can. Its a nice way for people to be able to make something that is really customized specifically for them. Also, the write.scad file and the font files that go with it are automatically included so you don't have to upload them.

You want to publish your tree to Thingiverse as a Customizer, so that everyone can make their own tree using the Customizer App. To do that, we will need to add a couple of comments that will tell the Customizer App which variables are customizable and how.

// BEGIN CUSTOMIZER

This tells Customizer that the variables below here are customizable

/* [Tree Parameters] */

This creates a tab called Tree Parameters.

//height of the first branch
height = 45; //[1:100]

This tells Customizer to give the user a slider between 1 and 100 for the height variable, and it will label it "height of the first branch".

Now go to Thingiverse.com, log in. and click the "create" button to upload a new thing. Upload your STL file and OpenSCAD code, and check the "This is a Customizer" box. Make sure your thing name begins with the word "Customizable." and tag it with the word "customizable." Also, you now sometimes have to add the Customizer App explicitly under the Apps section at the bottom.

Fill out the fields for the Thing Name, Category, and so on. Click the publish button to publish your new Thing. It will take a few minutes for the customizer button to show up on your newly published thing.

You can see my customizable tree here.

Step 9: 3D Print and Paint

Your tree can now be printed on any home 3D printer. It will probably have a lot of overhangs, which will require support material to print well. In these pictures, you can see I didn't use as much support as I should have, and it adversely affected a few of the low hanging branches.

I printed this one in woodfill, which is a PLA filament with real sawdust embedded in it. It has the smell and feel of real wood. You can even sand it with some fine (200 grit or so) sandpaper! To get in between the branches and clean up some marks from the support, I used a sanding pen which you can get at auto and craft supply stores. You can use any brown filament that you want, of course. If the surface gets scratchy or hazy from sanding, you can give it a quick blast with a heat gun and it will shine it up again.

I painted the leaves green with Folk Art satin acrylic paint. Acrylic is generally recommended to be the best paint for painting PLA parts. You could also pause the print, and switch from a brown to a green filament, to achieve a similar effect.

If you don't have a 3D printer, you can order a print of your tree from your local Hub at 3D Hubs. Click here to go to my Hub.

Step 10: The End

That's it, now go forth and grow your own trees!

You can see mine here on Thingiverse, and run the Customizer app.

I hope you enjoyed my first Instructable. If you liked it, please consider voting for it in the 3D Printing Contest!

If you want to see more of the stuff I've modeled/coded/3D printed, check out my Thingiverse page.

In case you have trouble downloading the example code for this project from Instructables, I've thrown it up on GitHub. You can clone it at https://github.com/steveweber314/ProceduralTrees