Hello world ! Today we're going to go more in depth about a subject I've explored in a previous article : Differential Line Growth, except this time, we're taking it 3D.

**Differential Growth (DG)** is an algorithm part of the digital morphogenesis family of generative arts as it simulates growth patterns that exist in nature. Biologically, it is defined as a natural mechanism in which growing tissues grow at different rates within the same structure, which, often solves itself by self-folding in a waving pattern.

With a plane, the motifs closely resemble the undulating phenomenons of flower petals, self-folding leaves and even whatever these lettuce sea slugs think they are doing in the evolutionary tree.

Just like differential lines, differential planes also grow with a space-filling behavior, which gives living beings the opportunity to occupy a maximum surface in a minimum space. This can be very advantageous for some species, especially in plants, as more surface in tight spaces will facilitate photosynthesis. Here are two relevant pictures, one of a salad, and the other one of a lettuce sea slug, they are not to be confused.

## the differential plane growth algorithm

The principle of the algorithm doesn't differ much from its 2D counterpart, the two main functions that will be repeated over and over again are still the **adaptive subdivision function**, and the** repulsion between nodes function**, except, we will be applying these to points on a plane, rather than points on a line.

Working with a plane is fun ! It opens up a lot of possibilities. Let's say for instance that we want the repulsion forces to be stronger on the edges of the plane than in its center. In this case, the undulating phenomenon would happen mostly on the edges of the shape (see drawing above).

Aside from the new possibilities it proposes, I believe the separation forces involved in the the 2D variation are still completely valid for our use case. What's really changed the game is that subvisions on a plane are a little more complex than subdivisions on a line. So for practicity and readability, I decided to use a half edge data structure which I'm going to develop on next.

## the half edge data structure

A **half edge data structure** is a way of thinking about geometry. For example you could think of a mesh as a list of triangles that each have three points, classic. Well, in a half edge data structure, we think of geometry as a list of triangles that each have 3 half-edges and 3 points.

*But what the hell is a half edge ?* Well, as you can see in the drawing above, each half edge is represented by an arrow. Look at the red arrow called **[ he1 ]**, you'll notice that the edge it goes along is occupied by a second arrow, a green one called **[ flipped he1 ]. **Together, these two arrows make a complete edge, hence why we call them half edges.

What's useful about half edges is that in implementation, you can get them to store references to their next neighbour, their flipped neighbour, as well as any other data you'd need. Which will let you parcour that geometry really fast ! For notice, here's a list of variables contained inside my Half Edge class :

```
export class HE_halfEdge {
constructor(){
this.nextHalfEdge = undefined; // next halfedge
this.flipHalfEdge = undefined; // opposite halfedge
this.vertex = undefined; // vertex at tail of halfedge
this.face = undefined; // face
}
```

And now just to give you an idea of application, let's say I want to calculate the area of a triangle to see if it needs to be subdivided. Using only one half edge, I can reconstruct the whole triangle and calculate its area like so :

```
let a = halfedge.getVertex(); // get a point
let b = halfedge.getNextHalfEdge().getVertex(); // get b point
let c = halfedge.getNextHalfEdge().getNextHalfEdge().getVertex(); // get c point
let ab = b - a; // calculate ab vector
let ac = c - a; // calculate ac vector
// the area of a triangle is half the magnitude
// of the cross vector product of ab and ac
let cross = cross(ab,ac);
let area = cross.length() / 2;
```

## Subdivision Patterns

For the subdivision pattern I chose the most naive way to divide a plane. Which is to check all half edges lengths, and if one is above a certain threshold, I then divide it at its center.

Here's a quick drawing of how it works :

This method is known as **triangular splitting** and is very common all around, but if you're into morphogenesis and interested in subdivision patterns, I really suggest you read Andy Lomas's paper : Cellular Forms in which he talks about subdivision in terms of cell division. This is definitely something I'll try to implement in the future.

## final results and external rendering

And voilĂ , now that we have a data structure to handle our subdivisions. All we need to do is apply exactly the same exponential repulsion forces that I explained in the 2D variation. Below is what my draw function looks like, and below that, a minimal interactive wireframe simulation that you can click to restart.

```
if(vertices.length < MAX_VERTEX){
subdivide(); // go through all half edges and subdivide the big ones
separationExp(); // calculate separation forces for every vertex
move(); // apply these forces to each vertex
update(); // update the mesh geometry
}
```

Unfortunately 3D differential growth is very computationally heavy, even when using octrees as spatial indexers to cut the calculations. Hence why I can't really include simulations with thousands of nodes in this article. Though I've had a lot of fun generating some at home using my GPU, I can't figure out how to have them work on mobile and also don't feel like it is environmental worthy to harvest this much power from my visitors graphics card every time.

What I did do though, is export an obj from one of my biggest simulations, and rendered it in Blender just to give you an idea of what it looks like :)

That's it ! Thanks for reading. I'll see you next time, luckily, maybe for an article about **Differential Mesh Growth**, which will explore the same algorithm but applied on a closed geometry (i.e. a sphere), giving not unsuprisingly, very different and intricate patterns.

**kaspar.ravel @ gmail dot com**.

This code was developped in javascript using p5.js, three.js and <3.

All is licensed as

**CC BY-SA 4.0**(Attribution-ShareAlike) meaning you are allowed to copy, share, remix, build upon, as long as you give appropriate credit and reshare with the same license.