Modeling organic branching structures with the space colonization algorithm and JavaScript
The shapes, patterns, and forms that are found throughout the natural world, and the processes that produce them, endlessly fascinate me. At first glance, these real-world systems can feel impossible to understand — the sheer quantity of matter, the overwhelmingly small or large time scales, and the complex interplay of dynamic forces (including those coming from other systems) are all just too much us to fully comprehend as-is.
However, we can methodically deconstruct our observations of these natural phenomena into elegant, modular conceptual models to develop new ways of looking at and appreciating the world around us — you know … science!
Usually these conceptual models describe processes that occur over time, which another field of study (computer science) has a great synonym for — algorithms. In this article, we’ll take a look at one such natural algorithm, called space colonization, which can be used to model the growth of branching networks like those found in leaves, trees, sea fans, circulatory systems, and more (like in the images below)!
Despite the sci-fi-sounding name, the space colonization algorithm actually describes a method for iteratively growing networks of branching lines based on the placement of organic materials. Think 🍃 and 🌳, not 🚀!
Quick links
Before we dive into the theory and implementation side of things, let’s take a look at the end result so we know what we’re going for! Over on Github I created a repository with my source code along with a small documentation site that gets served up via Github Pages. If you’re not so into the coding side of things, the documentation site is a good place to start:
All of the source code for these experiments, along with a comprehensive list of features and references (academic, creative, and technical) is available in this repository:
Understanding the algorithm
Originally described (PDF) in 2005, then expanded on (PDF) in 2007, by Adam Runions and collaborators at the Algorithmic Botany group at the University of Calgary, this algorithm models the iterative growth of organic branching structures using two fundamental elements: attractors and nodes.
- Attractors are focal points of natural resources that promote growth. Exactly which resources these represent will depend on the specific branching system you want to model — auxin for leaves, sunlight for tree branches, nutrient concentrations for sea fans and corals, etc.
- Nodes are the points through which lines are drawn to render branches. More nodes mean more fidelity, but poorer performance.
The core steps of the algorithm are described visually by this diagram provided in the 2007 paper, in which attractors are shown as blue dots and nodes as black dots:
- (a) place a set of attractors.
- (b) figure out which attractors are influencing which nodes (see the note below on open vs. closed venation for details).
- (c) for each node, calculate the average direction towards all of the attractors influencing it.
- (d) calculate the positions of new nodes by normalizing this average direction to a unit vector, then scaling it by a pre-defined segment length.
- (e) place nodes at the calculated positions.
- (f) check if any nodes are inside any attractors’ kill zones.
- (g) remove attractors that fit the criteria for the type of growth you want (open or closed, see below).
- (h) begin the process over again from step (b)
Personally, I like to think of this process in simpler terms like so:
- Place attractors using some pattern or formula.
- Associate attractors with nearby nodes.
- Grow the network by adding nodes to branches, reaching towards nearby attractors.
- Prune attractors when branches get too close.
- Go to #2.
Key parameters
You may have noticed three important “constants” in the process above, which we can turn into configurable parameters to achieve different effects:
- Attraction distance = only nodes within this distance around an attractor can be associated with that attractor. Large attraction distances mean smoother and more subtle branch curves, but at a performance cost.
- Kill distance = an attractor may be removed if one or more nodes are within this distance around it.
- Segment length = the distance between nodes as the network grows. Larger values mean better performance, but choppier and sharper branch curves.
Open versus closed venation
Most implementations I’ve seen of this algorithm use only one of two different types of growth described in the original papers. These two types are called open and closed venation, referring to whether or not adjacent branches connect together to form loops, as shown in the animations below.
Open venation is the easiest to implement and the least computationally demanding, which is probably why so many prior projects have used it. But closed venation can produce some really awesome and realistic effects too! 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.
For open venation …
Associate each attractor with the single closest node within the pre-defined attraction distance.
Attractors are pruned as soon as any node enters its kill distance.
For closed venation …
Associate each attractor with all nodes in its relative neighborhood (also limited by the pre-defined attraction distance).
Only remove attractors when all of their associated nodes are within the kill distance. This is what causes branches to connect together into closed loops.
Figuring out how to calculate an attractor’s relative neighborhood turned out to be pretty difficult. If you can explain it in simple terms, please let me know!
Getting vein loops to actually connect together is a little tricky, and I didn’t end up working on a solution for it. Instead, I just use a very small kill distance so that converging veins are terminated very close to each other so they seem connected. To get loops to actually connect together I’m thinking you’ll need to work out a way to determine when a given branch has been “terminated”. Once a branch is terminated, draw a line from it’s last node to the closest attractor position. If you figure this out, I’d love to see it!
Implementation tips
At the core of any implementation of the space colonization algorithm are three main components: a data structure for representing individual attractors, another for representing individual nodes, and a management module to track them all and run the rules of the algorithm.
In my implementation, I created three core classes stored in separate files which can be pulled in to lightweight “sketches” (like this one) using standard ES6 module syntax:
Attractor.js- representation of a concentration or source of a chemical or environmental factor that promotes growth. This stores a position along with references to each of the nodes it is influencing.Node.js- a single point in a branch. This stores a position along with references to the attractors influencing the node, it’s parent node, and any child nodes (the ingredients of a doubly linked list).Network.js- manages the growth of branches (made of nodes) based on attractors and any bounding shapes or obstacles.
Just for funsies, I chose not to use any creative coding frameworks (like p5.js) and instead rely on native Canvas API methods and focused standalone packages. For me this was the right choice, but you can use whatever frameworks you like!
Use a spatial index for better performance!
In practice, the management module (Network.js) needs to be able to keep track of hundreds or thousands of attractors and many thousands of nodes. In each time step of the simulation it’ll need to find which nodes are close to each attractor, which gets computationally expensive way too fast if you were to just loop over every attractor and node and perform distance checks.
The key to making this work is to use something called a spatial index — a sort of living, breathing database of points in space arranged into a tree-like data structure that makes it ridiculously easy (and fast) to find which points are near other points. Daniel Shiffman has a great introduction to this topic in his Coding Train series — definitely check it out!
Each frame, all of the nodes are put into the spatial index, which we then query using something called a k-NN search (k-nearest neighbors) to find the nodes that are within some distance of an attractor. This method gives us a massive performance boost for the attractor-node association step and the attractor pruning step.
In my implementation, I used the kdbush package, and you can see how I used it over in the source repository on Github (look in Network.js).
Vein thickening
In addition to the core growth algorithm, the original papers also describe a way to vary the thickness of a branch at each node based on how many descendant nodes it has. Basically, the longer a branch gets (including descendant branches), the thicker it becomes.
This effect is achieved by adding each node’s thickness to it’s parent node’s thickness, which more or less follows a generalized principle of fluid transport systems called Murray’s law.
Starting at each “tip” node (that is, nodes without any descendants), recursively traverse up through all of it’s parent nodes, accumulating their thicknesses as you go. The pseudo-code below outlines how this is done in my implementation.
For this to work correctly, you’ll want to initialize every node with a default thickness parameter that effectively becomes the minimum branch width.
for(let node in nodes) {
if(node.children.length == 0) {
let currentNode = node;
while(node.parent != null) {
if(current.parent.thickness < MaximumThickness) {
currentNode.parent.thickness += currentNode.thickness;
currentNode = currentNode.parent;
}
}
}
}Here is what the effect looks like in action (without the effect on the left, and with the effect on the right):
Opacity blending
In my tinkering, I also found another nice rendering effect that involves varying the opacity of branch segments based on it’s thickness. This is especially effective when combined with the variable vein thickness technique above, since it causes veins to become more opaque as they grow is size.
I really like this effect because it gives an illusion that the branches are extending into 3D space, when really they are all just 2D!
if(this.settings.EnableOpacityBlending) {
this.ctx.globalAlpha = this.thickness / 3 + .2;
}Here is what the effect looks like in action (without the effect on the left, and with the effect on the right):
Basic space colonization
Once all the fundamental data structures and modules are in place, its time to start experimenting! I recommend starting off simple — just a few thousand attractors and a half dozen or so nodes, all scattered randomly around the canvas.
Focus more on getting the core algorithm running smoothly, and less on the visual effects. Don’t over-complicate things too early with unnecessary colors, branch thicknesses, opacity, or other post-processing effects. If everything is built correctly, you should get a result like the one below.
Bounding shapes
Next let’s work on constraining growth using arbitrary polygons so we can start creating more interesting (and useful) shapes. We’ll need a data structure of some kind to represent a polygon and a way to easily test whether an attractor or node is inside or outside of it.
In my implementation, I created a class file called Path.js which stores an array of coordinates representing whatever shape you’d like. To test whether an arbitrary point is inside or outside of the shape, I used the point-in-polygon package and exposed an abstracted public method called contains(x,y).
The point-in-polygon package wraps a really tiny, but really clever ray-based algorithm called the PNPoly test created by W. Randolph Franklin. Definitely worth a quick read!
One way to constrain branch growth to these shapes is with a conditional check before new nodes are added to the network — if the new node would be inside of the bounding shape, add it.
A better way to constrain growth to a path is by removing every attractor that is outside of the bounding shape at the beginning of the program. That way the branches will actually bend to conform to the shape of the bounding path!
During this experiment I also implemented a way to create Paths from external SVG files. Its a bit finicky, but it works (with extremely simplified SVG files)! See
SVGLoader.jsto learn more.
Obstacle avoidance
Once there is a way of representing shapes and checking whether arbitrary points are inside or outside of them, it’s pretty easy to implement the logical inverse of bounding shapes: obstacles.
Whereas bounding shapes are polygons that attractors are not allowed to be placed outside of, obstacles are polygons that attractors are not allowed to be placed inside of.
Marginal growth
The original paper describes a method of simulating the dynamic shapes of real leaves as they grow, which sometimes can be pretty significant. For example, some leaves develop pronounced lobes or serrations as they mature, but start off as very smooth ovals or circles when they emerge from their buds.
In real leaves, a growth hormone called auxin is produced in higher concentrations around the edge of the leaf, which we can model by placing attractors only along the bounding path itself rather than inside of it.
As the bounding path is scaled (grows), our attractors will naturally get farther and farther apart, whereas in real leaves the auxin hormone will continue being produced and more or less fill in any gaps that are created. To simulate this effect we need to inject new attractors whenever the existing attractors get too far apart. A fancy technical name for this is “adaptive subdivision”.
In the animations below, notice how branches split at more or less regular intervals. That’s because those are the points at which attractors on the bounding shape edge get too far apart and new ones are injected!
Instead of just scaling a static bounding shape to simulate the growth of the leaf, see if you can find a way to interpolate the path between different shapes and sizes!
Interactivity
At this point we have all of the important features of a space colonization implementation: the algorithm logic, attractors, nodes, bounding shapes, obstacles, and marginal growth. Now let’s see what we can do to have a little fun with it!
Adding interactivity to any project can add a new dimension of engagement and understanding, so let’s add some mouse controls to our implementation. In my experiment, I implemented the following controls:
Left clickto place a “cloud” of attractors randomly inside a circle around the mouse.Right clickto place a single root node at the mouse cursor to kick off growth.- Use your
scroll wheelto adjust the diameter of the circle around the mouse, which effectively lets you vary the density of attractors.
What would it be like if you could draw or import and place bounding shapes and obstacles? Or change the colors of branches using a color picker? Maybe you can think of a way of turning this into a game somehow? Whatever you come up with, I’d love to see it!
Growth from images
Just for a bit of extra fun and challenge, I got curious about whether it would be possible to “grow” images using veins. I thought about this wonderful series by Robert Hodgin of generative stippling images and wondered, “what if each of these points were an attractor in a space colonization system?”
Robert used a custom physics-based particle system along with variable dot opacity and size, so I needed to figure out an approximation that wouldn’t become a big project in itself.
After researching a few different stippling and dithering algorithms and pre-made apps, I ended up choosing Evil Mad Scientist Laboratories’ (EMSL) StippleGen software which allows you to create a stippling effect from any imported image using the weighted Voronoi stippling technique (PDF) described by Adrian Secord, then export the result as an SVG file.
I started by prepping an image by converting it to grayscale and bumping up the contrast to create a sharp difference between highlights and shadows (the dots will cluster in the highlights). It was then brought into StippleGen and given some time to get processed — its a bit of a quirky interface built with Processing (the Java-based version), so it takes a bit of fiddling of the controls to kick off the stippling process.
After a few iterations StippleGen will show a bunch of clustered points that resemble the original image. Normally you would then use StippleGen to generate a efficient single-line path (using the TSP algorithm) through all of these points for use with plotters, but all I was interested in was the points.
StippleGen lets you export the geometry as an SVG file containing (IIRC) <circle> elements with [x,y] coordinates. I used VSCode’s find-and-replace to strip out everything but those raw coordinate pairs to transform them into the format shown in the AttractorPatterns.js module. The live experiment and video below shows the result of all this hackery!
Going further
I hope this article has given you more than enough guidance and inspiration to explore the space colonization algorithm on your own! If you find itching to take things further, here are a few ideas for things to try:
- Find a way to actually connect converging paths in closed venation, not just faking it with a small kill distance.
- Find a way to implement vein thickening in a way that can be exported to an SVG file for pen plotters and CNC machines. This may involve creating variable width “ribbons” using the node chains as splines.
- Try storing and querying only the tip nodes in the spatial index and seeing if that gives a performance boost. If none of the attractors are moving around, new nodes won’t be added to “older” parts of a branch (I think?).
- Implement the algorithm in 3D using something like ThreeJS, Unity, Unreal, or Houdini. Spoiler alert: I’ve been working on a 3D version in Unity recently, and here what I’ve been able to produce so far:
