For this years Wheel Reinvention Jam I attempted to implement a procedural plant generator where the method of generation is to simulate actual plant growth.
I love plants and trees and I've been toying with the idea of making something like this for quite some time.
For the jam I limited the scope to trees with a particular growth pattern. Even then it turned out more difficult than expected and at the end I had to resort to ad-hoc solutions in order to get results that where somewhat tree like.
Still, I now have a foundation to work from and this post will cover the general approach that I took.
The segments that make up the tree body are called stems.
Stems are subdivided into internodes and in between them are the nodes from which anything lateral grows, such as leaves, flowers and branches.
Leaves grow in a pattern particular to the spieces. Branches may occur later but will do so on a need basis.
Growth is categorized into primary and secondary.
Primary growth occurs at the tip of branches, giving rise to new nodes and internodes. At the time of writing I'm not sure whether this category includes any other lengthwise growth as well.
Secondary growth is the increase in thickness, with new cells forming around the walls of the stem.
A tree data structure to represent a real tree seems like a given, but there is some nuance.
Since branches are chains of nodes, having each node be a parent to the next didn't make much sense since we wouldn't be able to represent the branch itself.
Instead, the nodes of a given branch are the children of the node from which the branch originates. This calls for transformations to be handled a bit differently. Nodes will be defined relative to their previous sibling or their parent if they are the first in the chain.
This won't work well for nodes with multiple branches, although I'm not sure how common that is.
Each data node defines a stem node and a proceeding internode. The next node in the chain will be attached to the end of the internode.
Transformation is primarily defined relative to "previous". Locally we only store rotation Rl and world space position Pw and rotation Rw is updated during simulation.
struct StemNode { StemNode* parent = 0; StemNode* first = 0; StemNode* last = 0; StemNode* prev = 0; StemNode* next = 0; v4 Rl = ROTOR_IDENTITY; v3 Pw = {0}; v4 Rw = ROTOR_IDENTITY; u32 state = 0; f32 age = 0.0f; f32 length = 0.0f; f32 radius = 0.0f; f32 randID = 0.0f; };
Data structure visualization. "First nodes" are offset by the radius of the parent.
Nodes are iterated in waves ("wave iteration" I like to call it).
This way we process the tree one level at a time. I tend to favor this approach for the aformentioned property. The benefits for this particular case remains to be seen.
// Psuedo code for wave iterations // Wave buffers curWave []; nextWave[]; // Start with the root entry Add(curWave, {root->first}); // Process wave while (curWave.num) { // Process each current entry for (entry in curWave) { at = entry.first; Query_At_: // Simulate node // Add branch to next wave if (at->first) { Add(nextWave, {at->first}); } if (at->next) { at = at->next; goto Query_At_; } } // Swap wave buffers Swap(curWave, nextWave); nextWave.num = 0; }
The current rendering is only placeholder. For each node we instance a unit sized cylinder which is scaled and tapered in the vertex shader.
Leaves are also instances of a mesh generated during program initialization. Nodes that carry leaves will have a bit set in state and so instances will be generated accordingly.
During the jam I managed to implement Rotors for the first time. Rotors are the geometric algebra equivalent to quaternions.
At the start of the jam I was using matrices to store rotations which take up a lot of extra space and are harder to manipulate.
Before adopting Rotors to the simulation I wrote a test widget in another project dedicated for that purpose.
Testing vector-vector and axis-angle based rotation.
Til next time!