Portfolio Piece

Tree Generator

In this project I set out to create an easy to use, light weight program for generating models of trees and similar plant life

The Finished Product

Features:

An easy to use interface for modifiying the input parameters of the tree, mostly featuring sliders.
The Tree is generated by making a skeleton, which is then surrounded by the mesh.
Pseudo random algorithms ensure that adjusting a setting doesn't change the look of the tree completely.
The tree can be viewed with cell shading, unshaded, wireframe or as a skeleton.

Generation Method

Pseudo-randomness

One of the first things I developed was my own pseudo random algorithm, something that produces a large variety of results in a controlled manner. To begin with I implemented a simple Xorshift function. Each time I call it I add together the seed of the tree, the amount of nodes previous to the current node, the child count of it's previous generations and a unique identifier for the function. This makes it so that each possible node will have it's own pseudo random numbers that are unaffected by previously randomly generated calls, while making each node unique. Most importantly, this allows the parameters of the tree to be changed without completely changing it's look and shape.

Skeleton Generation

The Tree's core is made with the principles of skeletal animation. The tree begins as a single node at it's base that then travels out to place more nodes. Each node has a transform which is slightly adjusted from the previous. Each of the directional vector's in the nodes transform is generated from the radiating vector from the previous node, and then the cross product of this vector and the previous nodes right vector, and then the last perpendicular. This ensures the the bone will have a similar orientation, meaning the stitching of the vertex patches will be significantly easier.

Branch Separation

Once the preliminary skeleton is generated, the thickness of each branch is applied, separating the branches out on a first come basis. This algorithm could be improved, but currently it produces acceptable results. In the majority of cases there will be no self intersection at a node because of this. This is also what causes the most chaos in the generation, making some branches rapidly move with small changes.

Placing Vertices

The vertices placed in two rings for every branch segment, one at the base and end. These are later joined in to a cylinder in the index buffer stage. There is also an edge case for end nodes to place some joining vertices to close up the end.

Building the Index Buffer

Each branch has a total amount of vertices equal to two times the amount generated per ring. Each branches orientation is align to to make make the creating of the connecting cylinder's easy by simply iterating over the rings. Then each node with multiple branches runs a special algorithm to generate it's geometry.

Branch Geometry

At each node with multiple branches a convex hull is generated using the quickhull algorithm. As it's input it takes the vertices of the circular faces connecting to the node. This generates an initial geometry from which internal geometry can be culled by checking if all the vertices of a triangle face are connected to the same circular face or not.

Future Developments

There are a couple of possible improvements:

The branch separation algorithm being changed to something balanced, rather than first come, to provide less chaotic results
Currently there is still some internal geometry remaining that could be removed.
The quick hull algorithm could be run on the centers of the circles to figure out a branches neighbor, then generate geometry from there. This would save on time since quickhull is a time consuming algorithm.