Growth - Incremental Additions
Growth in life is mesmerizing with the intricacies of the structures that are created. This programming poem series is an exploration of what happens with small incremental additions. The first installment features the dynamic growth of a 3d tree structure.
Video of interaction
The creation process
The coding process
I knew I wanted to start a growth series, but the topic seemed pretty difficult to even begin, so I started with what was comfortable, trees. I explored the idea of recursive tree functions with my previous Recursivity series. With this new code I took a much more functional approach, which really lends itself towards a recursive tree structure. For me it was a big experiment in abandoning some object oriented approaches that I was really comfortable with. Ultimately I was happy with this more functional direction, but I would change some of the approach now if I were to refactor the code.
Avoiding the geometry problem
The hard problem to solve with growth is how to create new geometry on the fly in a realtime simulation. How do you actually grow a limb on a tree and add these new structures to it in real time? Rather than solve this problem I decided to generate all of the geometry at the beginning. In fact, the tree geometry by itself has no X or Y variation. It’s a tube the shoots straight up in the Z axis. This tube has branching, but each branch shares the same vertical space. This code breaks down into a few simple steps. First create some tube geometry that starts at some value, and then moves up in space a certain length. Then at the end of that tube create 1, 2, 3 or more tubes that all share the same space, and then keep on recursing through these steps until some arbitrary depth is reached.
The base un-branched geometry structure:
Real-time movement
The next trick is to get these tubes to move in real-time. The solution for this problem is bones. The CPU is relatively slow at performing a very large amount of matrix multiplications, but the GPU is quite fast at it due to its parallel architecture. The vertices in each tube segment are associated with different bones. These bones themselves are essentially transform matrices. All of the geometry and bones are calculated in JavaScript on the CPU. This data is then uploaded to the GPU (with the help of three.js’s skinning system) and used in the shader program on the graphics card to manipulate the individual vertices.
Finally the bone matrices are all packed into a texture and reconstructed in the shader. Each vertex has attribute data that consists of bone indices (to look up which bone to use) and bone weights (to decide how much of that transformation affects that vertex.) During the geometry generation phase it’s necessary to generate these additional values to associate each tube with the appropriate bones within the system. The shader then combines all of these components together in a really fast manner.
The split of the first branch:
Detail of the split:
Note in that last detail shot that the bone weighting and positioning is only “good enough” and could have been done more “correctly”. Notice how at the base the shares the same vertices.
Making it move and grow
With this system in place I looped over a growing function that used three.js’s built-in scene hierarchy to dynamically “grow” the tree. The scales and rotations of the root bones affected the transformations of each branch down the line. Scaling down by even a modest amount quickly magnified down the branches of the trees. Additionally I ran the elapsed time value through sin functions with a random time scaling value and random rotation amount to make the tree sway in space. This randomness took the tree from a straight pole of geometry all sharing the same vertical space, to the creepy and dynamic tree structure that is displayed on the screen.
Probably the hardest part of this exercise was figuring out the skinning system within three.js. Luckily I got it all figured out and sent in a pull request with some documentation on how everything works.
