This was an individual project from 2017.

The original aim was to simply build a tree, as a procedurally generated level structure for an exploration game. This developed into a game concept, with a custom controller, and will likely further develop into a full game prototype and robust Unity editor tool.

 

The idea for the game is to use a tree - or a forest - as the world, which you can explore from the perspective of a small insect clinging to the branches.​ This creates an interesting 3D maze-like structure, with plenty of room for interesting additions and things to discover/interact with. Primarily, this project focused on the world generation itself, and connecting to a customised controller, rather than on any gameplay elements.

The challenges:

  1. Procedurally generate the structure of a tree. This needs to be highly customisable to produce distinct structures.

  2. Generate the tree mesh and leaves (and potentially other objects) using the structure.

  3. Create a custom first-person character controller to stick to the mesh at all times. Unexpectedly, this was the most challenging part.

Overview

To begin, I investigated and rapidly prototyped three methods for procedurally generating trees, in order to decide how to proceed.

1a: Selecting a method

Option 1: Simple fractals

This was my first instinct (and first prototype), but have several downsides:

  • Often display too much symmetry

  • Very difficult to fine-tune (difficult to visualise effects of small input value changes)

  • Composed of straight sections, which looks unnatural and are expensive to reduce

  • Prone to overlapping branches, especially in 3D

Option 2: L-Systems

Another recursive algorithm (a type of fractal), these produce much more natural-looking trees than fractals alone. The user defines a set of "rules", which repeat to produce the overall structure.

However, again, this does not seem to fit the project, since trees produced in this manner:

  • Often produce a large number of overlapping branches, which need to be trimmed

  • Are very difficult to customise (i.e. they tend to end up looking relatively similar)

  • Comprise of straight edges, which are expensive to reduce

  • Produce repetitive structures

This last point is important for the game prototype. L-System trees tend to sprawl out in a generally predictable manner. What I wanted was something a bit more interesting.

Option 3: Space Colonisation

This is a completely distinct method, where branches compete to fill a space. It offers the most by far for this project:

  • Extremely tune-able (even through visual means, by changing the envelope space)

  • Will never produce overlapping branches (unless, it seems, the branch width > step size)

  • Very natural-looking structures - or deliberately alien / unnatural, depending on input

  • Can change "resolution" (length of straight sections of branch) without changing the algorithm or parameters, to tune the algorithm cost for different generations

  • Can produce very complex and sprawling structures, with no repetition of segments (perfect for exploring!)

This was the method for the project. The next step: make it do.

Image from: A. Runions, B. Lane, P. Prusinkiewicz. Modeling Trees with a Space Colonization Algorithm. Eurographics Workshop on Natural Phenomena. 2007. Pages 63-70

Procedural generation:

Trees using Space Colonisation
and Mesh-Clinging Controller

Experiment and Game Prototype (Unity3D)

 

Individual project

Code available: https://github.com/micklethwaitem/SpaceColonisationTrees

March 2017

For this, I followed the algorithm described in: A. Runions, B. Lane, P. Prusinkiewicz. Modeling Trees with a Space Colonization Algorithm. Eurographics Workshop on Natural Phenomena. 2007. Pages 63-70.

1b: Generating the Structure

The algorithm makes use of attraction points, which represent the space you wish the tree to fill. To start with, I generated these points randomly within a sphere. These each have a radius within which they are able to influence a "growing" tree, and a radius within which a node is said to have "reached" it (removing the attraction point from the rest of the algorithm). The tree itself is a graph of nodes and edges - similar to its corresponding data type, and this is how I decided to store it within Unity. Once placing the first node on the floor, the algorithm goes through several stages:

  1. Force the tree to ascend towards the envelope of space. Continue until an attraction point can find a node within range to influence.

  2. For each attraction point, "pull" the closest node (if there is one within influence range). Its new direction will be an interpolation of its previous direction and the vector towards this attraction point, and can be a result of several attraction point influences.

  3. Every node influenced in the above way will then produce a child, in its updated direction.

  4. If a new node is within "kill" range of an attraction point, delete the attraction point.

  5. Repeat steps 2-4 until all attraction points have been removed ("reached"). To prevent infinite loops, other edge cases are required.

[Refer to the github repository for the project & code]

The LineRenderer (tree structure) and sphere primitives (attraction points and envelope) are for demonstration/debugging only.

This implementation uses:

  • An "Envelope" of randomly positioned attraction points.

  • A "TreeSkeleton", including a linked list of "TreeNodes" and methods for generating/editing it.

  • A "MyTree" object responsible for planting and growing the tree, directing both the "TreeSkeleton" and "Envelope".

  • "MeshGenerator" and "QuadGenerator", to be implemented later.

As more nodes are added, the algorithm becomes significantly burdened. Some optimisations can be used, but unfortunately it is at best of Mlog(M) x N complexity (M the number of iterations of the algorithm you decide on, N the number of attraction points). As the procedure continues, it becomes slower and slower as the number of nodes greatly increases. I did attempt mid-algorithm cleanups of the structure after intervals (removing nodes in the middle of almost-straight sections, etc.), but found that this produced artifacts for only a modest increase in speed.

I used several edge cases to ensure that no more calculations were performed than absolutely necessary, and no infinite loops. Once in the main loop (past stage 1), the algorithm exits if:

  1. The number of nodes does not increase in one iteration,

  2. No "unreached" (active) attraction points remain, or

  3. A defined maximum number of loops has been exceeded (a last resort for potential infinite loops from unreachable attraction points).

Additionally, if a branch exceeds a specified height during stage 1, the algorithm exits - it has passed all attraction points in their expected range, and would otherwise proceed indefinitely.​

[Time to generate this example: ~2 seconds - part of which is devoted to updating the linerenderer]

1c: Optimising the structures

(2) Remove superfluous nodes in straight sections.

 

If the angle between nodes 1-2-3 is within θ (a small value), then the centre node can be removed without visual differences.

Since you cannot consider removal of nodes which form branching points, this is best done after optimisation 1, which will remove plenty of superfluous branching points.

In addition, care must be taken, however, not to simply proceed through the tree structure node by node with this:

If nodes A-B-C-D are connected, A-B-C may well be under θ, as may B-C-D. However, A-B-D or A-C-D might not be, so you cannot remove both B and C. In fact, to avoid any possibility of creating an undesired artefact, you can only ever check/remove every other node, without doing many more validations (checking every combination of nodes between two points). While this can be cumbersome, it greatly reduces the node count without affecting the resulting structure.

The structure shape is good, but if I were to generate a mesh around it as it is, it would be horrendously expensive. The "Step Length" - the length between one node and its next (which you can consider to be the "resolution" of the structure) needs to be very small in order for the branches to appear curved. However, this produces a vast number of nodes, rendering further calculations very wasteful. Two methods I used for rectifying this are:

In the high resolution (small step length) example from the images above, and, this optimisation reduced the node count from 6918 to 5254 (24% reduction), using an angle threshold of only 2 degrees, and with no visible differences.

(1) Remove very short branches.

 

In many cases, the penultimate node before "reaching" an attraction point gives a branch, resulting in a tiny branch of just 1 step length in size. This should clearly be removed - it is so small that it can barely be noticed in the linerenderer debug view. With a mesh added - giving the branching point a finite width (a much larger value than the step length ever should be), this branch will be entirely hidden beneath the mesh of its parent.

 

Not only does this make the branch a waste of calculations and rendering, I later found that trimming it is actually necessary for the player controller to work. In the final version of the controller, these would cause miscalculations and glitches while trying to find the nearest nodes and directions from the skeleton.

I added the option to remove any branch length of <n nodes, where n is an adjustable parameter.

In the high resolution (small step length) example from the images above, and, this optimisation reduced the node count from 7912 to 6918 (13% reduction), using a minimum branch length of 2 nodes.

1d: Customising the structures

The next step was to produce distinct and interesting results, by changing only the parameters of the functions. With the above algorithm robust, I set to work on exposing parameters to the user, and experimenting with values. The most useful ones, with the most clear changes, are:

  • Pull ratio - The amount an attraction point can influence a node's current direction; between 0 [no influence] and 1 [overwriting direction entirely]

  • Envelope shape - The shape of the container of attraction points, and the overall shape of the tree. For the sake of extensibility, and removing the dependency on unique meshes and expensive generations of random points within custom volumes, multiple envelopes (with distinct settings) can be used on the same tree.

  • Envelope type - Whether the envelope provides a volume to fill, or a surface to cover (using vertices as potential attraction points)

  • Attraction point Kill radius - The distance at which attraction points can influence a node, and at which they are killed by a node. Lower values produce more branches at higher cost, and with greater chance of artefacts (must keep step length low to avoid these).

  • Step length - Distance between nodes; lower values produce smoother curves at greater cost. [Important note: if the step length, the kill radius must be increased similarly to avoid artefacts with orbiting branches]

Low kill radius

High kill radius

Low step length

High step length

Very high pull ratio

Very low pull ratio (Before and after "Short Tip" optimisation)

Medium pull ratio

Envelope shape

Envelope groups (varying settings)

Mesh covers

2a: Mesh (Branch) Generation

The meshes, shown in some of the examples in the previous section, are generated once the structure has finished optimising. Again, tuneability was prioritised, with editable parameters such as start/end thickness, thickness falloff, number of edges ("roundness" of the branches), etc.

Optimising the structure was very important for this stage to be possible. At each node, a new cross-section of vertices is created, and so the tree node count is directly proportional to the mesh triangle count. At present, this is still generated using the CPU, but a compute shader would be excellent with the huge number of vector calculations.

[Small note: while the algorithm will never allow 2 branches to cross, making the mesh very large compared with the step size does allow an overlap. Specifically, when branch radius > step size, this becomes a possibility.]

At each node (except the tips & start), the cross section direction is taken as the average of the incoming branch and the outgoing branch. Vertices are then elevated across this plane to the desired width, calculated as a function of the node's distance from each end. Cross sections are lined up, and the triangles assigned from the vertices, assuming a model close to a polygonal prism. Normals are taken as the direction of the offset of a vertex from the node. Branching nodes create new meshes, which are later added to the entire structure, allowing them to be calculated simply and concisely.

 

See the GitHub code for the maths behind this section.

2b: Quad (Leaf) Generation

The leaves, as simple particles, are generated on nodes. All aspects are tuneable, such as the branch width at which they start spawning, the angle at which they are offset, the number that appear on the very tip, the colours and sizes, and the probabilities of different numbers spawning at a given point. the leaves are elevated by the mesh width to place them on the surface.

With user input, the leaves can also be placed ad non-node positions (between nodes on the skeleton). This is done by interpolating width, position, etc. between skeleton nodes. The advantage of this is that leaves don't need to cluster, and that otherwise the leaves appear clustered if the resolution of nodes on the skeleton is low (if the step size was high).

The leaves are also triggered to fall when clipped by the player - partly to remove them from obstructing the camera, but also to give a sense of gravity, and to show areas visited (the barren parts of the tree). The player controller will be expanded on later.

3: Player Controller

As it turns out, this was the most complex task, and the one I had to iterate on the most. The solution is rather brilliant. Unfortunately you'll have to wait for me to write it up. Sorry.

©2017 by Martin Micklethwaite.