On Generative Algorithms

Differential Mesh Github

When I had gotten Differential Line working the obvious next step was to try to create something similar in three dimensions; and one alternative is to make the line itself move in three dimensions. However, that did not really seem all that appealing. Instead I chose to go for a combination of the attraction/rejection behaviour of Differential Line, and the growing behaviour of Hyphae. Essentially I wanted to make a (triangular) mesh that grew outward without self-intersecting or colliding. Doing this directly in three dimensions seemed a little daunting, so I started with a two dimensional version.

differential mesh triangles

In the animation above you can see that new triangles are added to the outside if the existing mesh. They are added in such a way that they don't collide with existing parts of the mesh. I use a very naive collision detection where I check if a potential new vertex is too close to any existing vertices before adding it. In addition all vertices still behave similarly to the vertices in Differential Line; that is, they try to get as much space around themselves as possible, whilst remaining close enough to their neighbors.

The key thing to get this to work is to have the mesh do various self-balancing operations as it grows. There are a few things you can try:

  • Split edges that are too long.
  • Avoid inserting new vertices where the vertex density is too high.
  • Flip edges to reduce the length of the edge.
  • Add a force that makes the triangles attempt to be roughly equilateral.

The animation above employs a combination of all of these.

Now we scale down the triangle size and add some structure.

  mesh mesh uniform

The hope was that this set of rules would resemble the growth of slime mold or, more likely, lichen. It turns out the basic version of this is quite similar to certain types of lichens. And it seems to match the growth of liverworts as well, as was pointed out to me on twitter.

The way I initially controlled the growth was to choose random edges, check if they were on the outside if the structure, and see if I could attach a new triangle to that edge. The problem with this strategy is that eventually most edges are going to be on the "inside" of the structure. This means that you are going to spend a lot of resources checking edges that you can't do anything with.

There is a pretty obvious solution to this problem. (And, as usual, when I say obvious, I mean that it took me a few months to realize) Instead of picking random edges and testing if you can grow a new triangle from it, you can use food sources. First you randomly position food sources in the domain. Then you have something happen each time an edge in the structure hits one of these food sources. For instance if you let the growth of the mesh spike when a food source is hit you get something like this.

differential mesh sources

If you let this simulation run for a while you can get a number of interesting results. Here is a version where the color of each triangle gradually changes according to when it was created. The color changes gradually from white to black, then flips instantly back to white again. The first time I did this it was an accident, but as you can see it gives it a nice three dimensional illusion.

differential mesh rose