Space colonization is a process for iteratively growing networks of organic branches based on the distribution of attractors to which the branches are attracted. Originally described (PDF) by Adam Runions and collaborators at the Algorithmic Botany group at the University of Calgary, this system can be used to simulate the growth of leaf venation patterns and tree-like structures, as well as many other vein-like systems like Gorgonian sea fans, circulatory systems, root systems, and more.
For those of you who would like to learn exactly how this process works and how I implemented it using code, I’ve published a full technical write-up available over on Medium:
Types of growth
The original paper describes two types of growth – open and closed venation, referring to whether or not adjacent branches connect together to form loops. Open venation is perfect for modeling trees, shrubs, and sea fans, but closed venation is the way to go for modeling leaf venation and slime molds.
In addition to the core growth algorithm there are a couple of nice visual effects that can be implemented to create more realistic and compelling images.
In this effect, branches become thicker the longer they get. Starting at the tips, each branch’s thickness is increased as the code recursively travels all the way up to the “root”. If there are multiple sub-branches, they all contribute to the “trunk” branch thickness. The paper references the term auxin flux canalization when talking about leaf venation, as well as Murray’s law from fluid transport network theory.
The illusion of depth can also be created by varying a branch’s opacity proportionally to it’s thickness at any point. Thinner, shorter branches are more transparent more thicker, longer ones.
Taking away all the visual effects, colors, and features shown below, this is what the raw output of the space colonization (with open venation) looks like:
Growth can be constrained to arbitrary bounding shapes to simulate the finite domain of a leaf or organism.
Growth can also be made to avoid obstacles to simulate areas of decay or space already taken up by competing systems. Its fascinating to see how veins will “find” paths of minimal energy automatically, like lightning seeking a path to the earth.
Real leaves grow over time, sometimes even evolving their boundary shapes to form features like lobes or serrations. In these examples, growth attractors are placed only along the edge (never inside the shape) and new attractors must be added to fill in gaps between older attractors as the shape gets bigger. Each time attractors are filled in, branches tend to be split.
This system comes really alive when a bit of interactivity is added! In this experiment the mouse is used to “paint” growth attractors and place “roots”. Use left click to paint, mouse wheel to increase/decrease the paintbrush radius, and right click to place a root node to kick off growth.
Growth from images
The branching networks that the space colonization algorithm produces are highly dependent on the arrangement of attractors through which the branches grow. In all of the experiments above, attractors were distributed randomly (taking into account any bounding shapes or obstacles), but really you can arrange them however you like.
In this experiment I started with a grayscale image and generated a pattern of circles using the weighted Voronoi stippling algorithm via EMSL’s StippleGen. I converted each circle’s position into a set of attractors and ended up with the following result.