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:
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:
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
- 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.