Procedurally Generated 3D Trees

A while ago I saw this blog post and it's associated Reddit post. The algorithm described there is used to generate a tree in 2D by first generating a bunch of leaves, and then "growing" the tree towards them. I liked the results that were obtained, and tried to recreate them. I then expanded the algorithm to work in 3D, and output to 3D object files.

The algorithm will add a bunch of branch segments, each contributing to the entire branch. The algorithm works as follows (at least as far as I understand it):

1. Start by generating a bunch of points.

   This can be done using whatever distribution type you like, but they will eventually be leaves, so place them at the correct height.

2. Generate the initial branch segment from the ground up to the start of the leaves.

3. For every leaf, calculate the closest branch segment.

   Following these rules: - Ignore every branch outside of a certain radius. - Every leaf can only influence one branch at a time. - If a leaf is closer than a certain distance, mark it as reached, and remove it from computation.

   For example, the image shows a few branch segments, and a few leaves surrounding them. The lines are drawn to the closest branch segment, and show the "pull" of the leaves on the segments. There is one leaf that is too far away, and one that is close enough, that has already been reached.

   

4. Add a branch segment towards the pull from the leaves.

   For every branch, get the positions of all the leaves influencing it. Then append another branch towards the average of that direction. I have found that the direction should be weighted with the direction of the parent branch. Otherwise the new segments jut out at weird angles.

   

5. Repeat from step 3

   Repeat these steps until all the leaves have been reached, or until there are no more changes to the tree.

In practice, I have found that there should be a few additions to the algorithm.

• Weighting the new branches with the original branch direction produces better results. However it is possible for the new branch to grow "past" the leaves. The new branch will then not be the closest branch. In the next iteration the same branch will be added again. My quick solution to this problem was to check if a similar branch segment already exists in a list of branch segments. This check is done with some tolerance, to allow for floating point errors.
• Maintain a thickness variable for each segment. When a segment is added, traverse back through the tree, adding to each segment's thickness.

2D Output

Here are a few results from running this in 2d, using a few different settings. Both the height of the initial points and the weight for new branches are varied. Click the images for a slightly larger view.

There are still a few issues, such as thick branches suddenly becoming thin branches.

Adjusting for 3D

But 2D is boring, lets add another dimension! In order to generate tress in 3D the leaf and branch generation is extended to include the third dimension. Rather than export to png, the data is exported to obj files. Initially only points with lines were exported. The export was then changed to generate a circle of points around every branch segment's start and end position. The circle was simply rotated to face in the direction of the branch. Calculating the rotation turned out to be much harder than I thought.

To connect the faces, one circle's vertices are simply connected to the next. When two branches split up the vertices are simply connected, no fancy maths is performed to find the line of intersection.

Additionally, the ends of the branches are merged into a single point. The trees are also rendered in 2D from the top, as the side view is a mess.

This image shows a basic result. There are still quite a few errors here. The biggest and most obvious one is the "twist" that certain segments have. This always occurs on the main stem, and is mainly a result of bad rotation code. The second problem is small stubs that just out from branches. This occurs when a branch grows just a little bit to be closer to leaves, before its parent segment grows in another direction. Viewing the 3D model reveals many of these types of issues.

The first problem is easily fixed by using correct rotation code. And by "easily" I mean easy in concept. The second problem is fixed by checking the distance length of a segment chain. If it is smaller than 3, it is removed.

After these fixes are implemented, the tree looks like this.

After some tweaking in blender, with nice lights and shadows:

Running the script

The source for the program is hosted on github, and published as a python package here. To run the program you will need python>3.5, as well as the following libraries:

• numpy
• scipy
• PIL

The runner.py file contains samples of how to generate and save some trees.

Future work

I'd like to add some leaves as well, as currently the trees look very empty. Initially this can be done with simple square planes, but I'd like to add generation of leaves as well. After that I'd like to add some textures to the generated objects, or maybe even generate some textures.