Growing Trees with Space Colonisation in 2D

Yesterday, I quickly hacked up an implementation of the Space Colonisation algorithm, for growing trees. By trees, I don't mean the binary trees – the living sort, just represented by segments and forks.

My inspiration was from Procedural World and this article. The idea of Space Colonisation is to colonise/fill a limited area. A tree like this would grow from the bottom up (as they usually do), gradually taking up all the available space. Trees generated by this algorithm (as far as I know) rarely have intersecting branches, and look organic.

I started coding from the top (as usual I didn't plan much beforehand, but it didn't turn out too bad) – a Main class that creates a Point Cloud in a spherical shape, grows a tree in that cloud, and renders the tree out to an image. Later I added a GUI for faster feedback.

After some work, I got this:

A basic tree

The green points are the Point Cloud, and the black dots with the yellow lines are the generated tree (segments).

When I constructed the GUI, I added the option of scaling the point cloud horizontally, which can give me trees like:

A tree that has been scaled horizontally by 0.6

Here's a quick shot of the GUI:


I've still got more work to do, things like

  • Add different point cloud shapes
    • Generate from an image?
  • Support for multiple trees growing in the same space
  • Biases
    • Bias upwards
  • Rendering more tree-like
    • Trunk should be thicker than topmost twigs
    • Very close branches could be merged

The code is available on Github.