Procedural tree generation

Introduction

Procedural content generation is a field that is very useful in certain projects. In particular, big, open world games can find procedurally generated content extremely useful. Instead of having artists model hundreds of variations of an asset, those variations can be generated by a program.

This project is a proof of concept for generating realistic looking foliage - trees in particular. The aim of the project is to generate a realistic looking topology of a tree. The crown or roots of the tree are not considered. This is done using the space colonization algorithm. The algorithm treats competition for space as the main factor determining branching and the structure of the tree.

The space colonization algorithm

The algorithm is initialized with a number of attraction points. These points, as the name suggests, attract the new nodes generated in the tree structure. Once the attraction points are defined, an iterative process of adding nodes to the tree structure is started:

  1. The closest node is found for all attraction points within predefined range
  2. Each of the nodes found as closest in previous step determine the average direction to all points that found it the closest node. This is used as the direction for the growth of the next node
  3. A new node is added at a predefined distance along the direction found in step II, for each node that was deemed closest by at least one attraction point
  4. All attraction points that are within a predefined kill distance to any node are removed
  5. If there are no nodes remaining or none of the remaining ones are within the radius of influence, the algorithm is considered completed and is stopped
If this algorithm is followed as is, a small issue arises, where some two attraction points in mirroring directions would affect the same node and cause the placement of the next nodes on that branch to loop infinitely. When this bug was found during the development it was trivial to detect and fix.

Application work-flow

The first thing the algorithm requires is the attraction points. To this end the area of the crown of the tree is defined by the user. This is done by drawing an outline of the crown on the Y-X plane by the user. The application then generates the attraction points within the volume defined by the rotated outline.

Once the crown of the tree is defined the algorithm generates the tree. This process can be seen as it is happening. Once it is done, the topology of the tree is rendered using lines to represent branches. The user can then choose to apply some post-processing of the tree structure to reduce the node count and generate a simple representation of the body of the tree.

Defining the area of the crown.
Attraction points generated in the defined area.
Tree shown in debug mode while being generated. Blue lines represent attraction vectors, red - vector for the placement of the next node.
Generated topology of the tree.
Representation of the tree using cylinders with a calculated thickness.
Results

The resulting application can generate some convincing tree topology. The space colonization algorithm is definitely a viable algorithm for producing realistic looking trees. A wide range of different tree structures can be generated by changing the control parameters.

Here are some trees generated using different parameters:

Git repository | Back to homepage