Procedurally Generated Forests

Back in college I took a graduate level computer graphics course called global illumination. Instead of a final exam, we each did a term project and presented it on the last week. We, the students, were to decide on the topic for our term projects. This was pretty exciting for me -getting to choose what to work on- and so I immediately started fantasizing about nearly impossible and mostly pointless tasks. After a week or two I decided on procedurally generating trees because it's something I had daydreamed about in my youth.

Trees are pretty but they are difficult to model and render because they have a lot of geometry. What's more, no one actually cares about the geometry of the plants, as long as they look right. Therefore, artists use a type of computer algorithm called procedural generation to grow virtual trees.

Most of the computer programs that are actually being used by artists are based on regular grammars with substitutions. This class of methods works by building lists of instructions, where each instruction describes how to build a part of the tree. Each instruction is represented by a symbol from an abstract alphabet, and the list of instructions is a string of symbols. A finite state machine reads and executes the string to build the tree.

New trees are created by substituting sections of the string. Starting from a simple seed string, new strings containing tree-like structures are generated by repeatedly applying the substitution rules. A set of substitution rules determine which symbol motifs are replaced and with which new symbols. Stochastic rules yields more natural looking trees. By carefully controlling the substitution rules, we can control the shape of the final tree.

But in my literature review I also found an exciting and, at the time, new approach. This method models trees as organisms living in their environment. By modeling trees as they actual are, we can easily and intuitively understand and alter the model. The method is:

Interactive Procedural Modelling of Trees and Landscapes
By Steven Longay (2014)
http://algorithmicbotany.org/papers/longay.th2014.small.pdf

Fascinated, I spent the semester hacking together a proof of concept.
Here are a few pictures:

This method simulates the biological process of tree growth. Trees sprout from seeds and grow branches and leaves. Trees have internal logic that decides which branches should grow based on how much sunlight each branch collects. Leaves capture sunlight, but only if they are not in a shadow. Trees shed branches that don't capture enough sunlight. By simulating these effects, trees grow into a realistic forest canopy, where the tree tops cover the entire sky but do not overlap.

Calculating the shadows cast by every leaf in the forest seems like a major computational cost. The original paper recommends using a voxel approach. Each voxel contains an amount of sunlight. We sweep from the sky down to the ground and cast a shadow for each leaf in each voxel by subtracting sunlight. Shadows spread out as they propagates downwards. Use a convolutional filter on each layer of voxels to spread out the shadows while conserving the total amount to sunlight. The original paper says to use a mean-filter, but that has several shortcomings. For my implementation I used a Gaussian blur filter instead. The Gaussian filter has several special properties: it is rotationally symmetric, and it is linearly separable which means that it is very fast to compute. The Gaussian kernel is in fact the only kernel with both of these properties.

Left: schematic diagram of the shadow propagation algorithm, showing how leaves cast shadows into voxels, which then project downward. Top right: the original blur kernel. Bottom right: my new Gaussian blur kernel.

Discussion

As computer hardware improves, computer graphics are slowly moving from heuristic methods to more physically realistic methods. This trend is currently playing out with ray tracing. Physically-based rendering is a bit further along as a technology and it's what gives modern video games that extra sheen of photo-realism. Botanical models have not yet displaced the older heuristics, and although research and development continues, this nascent technology remain obscure.