Real-Time Fractal Tree Mesh and Foliage Generation

LSystem Fractal Tree Mesh - Description

This project is still in progress


This is a C++ project written to use fractals to generate 3D meshes for trees and other types of objects suitable for fractal representations. The current version of the program is capable of generating any type of fractal mesh incrementally in real-time based on any desired parameters, and each segment of the LSystem is capable of executing an arbitrary duplication function. The latest version was originally designed to be used with touch screens on tablets allowing the user to generate the mesh by "painting" the screen.

Procedurally Generated Trees

3D Fractal Procedural Tree and Forest

Procedural Forest Simulation - April 2016

The goal of this portion of the project is to procedurally generate forests that cover the entire game world. The forests are to be able to grow densely and realistically, taking into account the available soil resources and available light striking the vegetation's leaves.

This system combines the procedural tree generation with a global system to estimate available resources for vegetation growth at each point in space. The trees increase in length, branch count, and width each update, as well as drop seeds. Each increase in any variable requires accumulated levels of resources before it can increase. A piece of a plant or tree's current resource allocation is increased each update based on how much sunlight is estimated to be striking it.

Voxelization is used to estimate growth collisions, as well as to estimate the amount of sunlight striking a particular area of the world. A voxelized representation of all trees and plants is maintained each frame. The number of occupied voxels in the column above a point in space is taken into account to estimate the amount of available light at that point. When a tree attempts to grow bigger, the nearby voxels are checked for emptiness before allowing the tree to increase in size. This allows dense growth of windy branches through each other. If a branch grows to a location which it cannot pass through, it attempts each update to change directions to grow around obstacles.

Plants also have the ability to drop seeds each update.

All growth parameters are configurable

Estimating the available light allows for results that realistically allow smaller numbers of large trees to have large canopies with hundreds of smaller, thinner plants underneath.

The voxels are stored in a map with a key based on the combination of the coordinates of the voxel so that the voxels can be arbitrarily far apart in the world without allocating large blocks of memory.

Ideally, this system will organically cause every available piece of space in the world to be optimally used by plants, and the forest will converge. Cutting down plants allows space for more to grow in their place.

The following video shows a sample of this system running. It is using debug graphics and there are no leaves.

Procedural Forest Generation

This video shows the growth simulation of a procedural forest using parameters that exaggerate growth speed.

The image on the left shows a dense generated dead forest with exaggerated parameters. The image on the right shows the generated voxels used for light estimation and growth collision avoidance.

3D Fractal Procedural Tree and Forest 3D Fractal Procedural Tree and Forest

Kinect-Guided Fractal Tree Generation - August 2013

This was a fun side project. It was a submission for a small hackathon. The project allows the user to use hand gestures to generate the trees. The trunk of the tree follows the arm movements of the user.

To create a tree, the user claps their hands together -- doing so will generate a stump. Keeping the hands together, moving the arms left or right will steer the direction the trunk grows. Subsequently moving the arms back apart creates the leaves and tree canopy using the fractal generation. Kicking either leg will fire a missile.

Kinect Tree Generation

This video shows my project partner demoing the kinect generation.

Screenshots of trees generated by other employees using our kinect application.

3D Fractal Procedural Tree and Forest 3D Fractal Procedural Tree and Forest

Leaves - August 2013

The trees now have leaves. The following video shows the trees being generated with leaves as well as exploding.

Trees With Leaves

Tree Generation Overview (In Development)

The current version was started Summer 2012, and rewritten completely from scratch in C++. It uses Direct3D 11 and pixel shaders. It began originally as an entry for a hackathon contest. The submission was to be a tablet application that allows the user to create the tree by swiping along the screen. The direction of the tree's growth follows the movement of the user's finger.

This version is still in development, but fixes most of the original's problems. It is currently implemented as a component of my Direct3D11 Game Engine, and will eventually be used to generate full-scale forests and other geological features for my open-world FPS.

Real-Time Generation

The meshes in this version can be generated incrementally and in real-time. The engine is optmized using DirectX intrinsics to take advantage of floating point vector operations. When new segments are added to an existing mesh, only vertices or normals which have changed are recomputed, so the cost of creating an entire tree is amortized over many frames. This allows for real-time animations in-game showing trees growing, or mesh generation based on user input. Each frame, the leaf nodes of the LSystem recursively replicate to a depth of one, up to a global maximum depth for the entire system.

Vertex Connections and Curve Generation

To generate the mesh for the tree, a number of issues must be overcome. The trees are generated as a sequence of transforms. These transforms are strung together to form a skeleton. Lastly, a circle of vertices is generated around the end point of each segment as it is created. This circle of vertices is perpendicular to the axis of the segment.

There are a number of issues with this method. The following video and section describe these issues and how to compensate.

Curve Generation

This video describes the different methods for curve generation.


Fractal tree wireframe.

Left: No shear compensation; Middle: Wedge curves; Right: Interpolated segment connections.

As demonstrated in the video and the wireframe image, merely adding perpendicular circles of vertices to the end of each segment causes the segment to be sheared and not preserve the segment's radius, nor derivative continuity between segments. The problem arises from the fact that adding an additional segment to the tree changes the normal of the curve. The normal is no longer perpendicular to the axis of either segment, but instead is an average of both.

To fix this, I determined two methods. The first, the wedge method, is to keep all segments straight so that their circle of vertices is always perpendicular to their axis. To allow the mesh to curve, a wedge is inserted between straight segments. This method produces the smoothest results, and was originally the method I chose to go with. The complications arose from the fact that the size of the wedge is dependent on both the angle of the curve, as well as the radius of the segments the wedge is placed between. Because the size of the wedge is dependent on the segment's radius, the width of segments in the tree cannot be changed after the tree has been created without invalidating the wedge. For trees that do not change once built, this is fine. But for my growth simulation which relies on both adding segments to the tree and increasing the width of the tree over time, this method is unsuitable. Even if the tree could be recalculated with the new radius, doing so changes the length of intermediate segments, which invalidates science and biology.

The second method is to interpolate the connective vertices when connecting a new segment. Initially, the circle of vertices is generated perpendicular to the axis of the segment. However, when a new segment is connected to said segment, the connecting vertices are changed so that they remain normal to the overall curve of the mesh, not just to a single segment. In other words, the mesh maintains derivative continuity at segment connections. This method also appears to maintain continuity when modifying the radius of segments, so this method is optimal. While it is not as beautiful as inserting a wedge, it can be made more beautiful by interpolating the connection of the curve multiple times so that it is smoother.

There is a major issue with the interpolation method. This method works perfectly for connecting single string of segments. However, connecting multiple segments to a single segment (for example, when a tree branches at the trunk into two or more branches) is complicated. In order to correctly connect the segments, the vertices must be normal to the curve created by all three (or more) segments. I have not yet figured out how to do this.

Arbitrary Branching Functions

Using an object-oriented branching system, child iterations of the LSystem can execute any script desired by the user, allowing for any type of object to be generated. Branch parameters are based on functions given by the user.

Crystal Tree

Fractal crystal tree with face lighting.

Crystal structure generated with fractal LSystem.

More-Correct Lighting, Texturing, and Bump Mapping

The lighting for meshes in this version appears to be probably correct. Normals are interpolated mostly correctly across all neighboring segments and vertices, so subtle specular highlights show up mostly. Bump mapping is also supported (as shown in the image), as well as texturing. Either per-vertex averaged normals or per-face normals (for crystalized look) can be used.

Decent Lighting and Bump Mapping

Smooth phong shading. Face phong shading with bump mapping.

Both smooth shading and face shading can be seen. The image on the right shows bump mapping (click the image to see the fullsized version).

Original Version

The original version of this project is my submission for a computer-graphics class in 2010. The assignment was to write a program that can generate a flat-shaded symmetric tree in 2D with rectangles and circles. I made mine 3D, randomized, and phong-shaded for extra credit. This version uses C++ and OpenGL (fixed-function pipeline).

Fractal Tree Rendered from 2010 Version

3D Fractal tree with low-quality phong shading in OpenGL.

3D Fractal tree with low-quality phong shading in OpenGL. 3D Fractal tree with low-quality phong shading in OpenGL.

Trees generated from the original program with various parameters.

The original version had some problems. The mesh could not be built incrementally -- it could only be displayed once it was completely generated, and was then immutable.

As well, the normals generated for the mesh assume every segment is a cylindar, and do not take into account neighboring segments. That is why there are clear discontinuities in the meshes in the images above.

Lastly, the segments for the trees do not share vertices. Instead, each segment duplicates the vertices it should connect to.