Cyclic Diffusion-Limited Aggregation: real-time natural pattern generation

Cyclic Diffusion-Limited Aggregation

In this article, I will propose an approach to generate natural 2D patterns, like chemical reactions or smoke using a variation of Diffusion-Limited Aggregation (DLA). With this technique, the aggregation of particles does not remain static over time thus opening the way for evolving patterns. A part of the implementation will be done within Processing for educational purposes.

1. Diffusion-Limited Aggregation, a quick overview

The DLA is a process where particles move randomly because of a Brownian motion and cluster together to form aggregates of such particles. A possible algorithm to simulate such phenomena in 2D can be described as following:

  • a grid will be used to store the aggregation: it is initialized with zeros and a small area is fed with 1. This area will be the first aggregate
  • the particles are distributed in the space, usually at a long distance from the aggregate to prevent weird growth
  • at each new iterations, each particle is moved to one of its 8 neighbors. If at least one of its neighbors is an aggregate, we set the aggregation map to 1 under the particle position. In other words, if a particle hits the aggregate, it gets added to it
  • if a particle was added to the aggregate, it gets removed

This is a simple algorithm. The following illustration shows a possible outcome of this algorithm from the beginning of the generation to the end.

Figure 1. (x2 speed) DLA with line seed at the center, grid size 128×128, 400 particles

Notice that the initial aggregate is a line in the middle, and particles are introduced at the top and the bottom to create a nicely distributed growth.

2. Introducing the generation of cyclic patterns

The algorithm described in part 1 can only simulate the growth of a finite structure. There are a few things that we can do to allow for a more dynamic behavior, with a dynamic aggregate that can change over time.

First thing, decay of the aggregation can be introduced. At each iteration, every value of the aggregation grid gets multiplied by the decay. Because of the decay, we need to change the distribution of the particles. If they are far away from the first aggregate, they will never be able to hit it before it fades out. So let’s have the particle positions randomized within the whole grid. Also, after a particle hits the aggregate, we will write 1 to the aggregation map at the particles position and reassign a random position to the particle.

Figure 2. Introduction of the decay of the aggregate

We can already observe an interesting behavior: structures keep evolving. We can also observe that over time, the aggregate gets smaller and smaller until it fades out. This is due to the fact that we add a particle to the aggregate if the sum of the neighbors  S_n around the particle is equal or greater than 1. But because of the decay, cases where this condition is true are rarer. This can be solved by introducing an Aggregation threshold  T_a. If  S_n > T_a, then we add the particle to the aggregate.

Figure 3. Setting Ta to 0.1

A last issue remains: what happens if a particle should be added to the aggregate given the sum of its neighbors, but already stands on some aggregate ? It still gets added to it. That’s why the aggregation map gets filled over and over in this case. By preventing aggregation from happening if the value in the aggregation map at a given particle position is higher than a Limitation threshold  T_l, we ensure that the aggregate at this position needs to first decay before it can become 1 again.

Figure 4. Ta 0.05 Tl 0.04

Because of this new addition, we can now observe a cycle in the aggregation. This is the very basis of this algorithm. By tweaking the rules of DLA this way, it opens the way some sort of cyclic reaction to happen, a backbone for the generation of even more interesting effects !

The implementation of this system on Processing up to this point is available on Github, you will find the link at the end of the article.

3. Scaling this system up

Due to some limitations of Processing, using Compute shaders isn’t yet supported in the environment (at least not from my research), so I implemented this algorithm at a bigger scale in TouchDesigner. I also think this software is better suited when you work on visuals with precision, I’ve implemented the Processing version just to have something that would appeal to more people. Compute shaders are a way to utilize the graphic card for computations, and I often use them to scale systems up. By having all the particles update done in parallel, you can have millions of them running in real time.

The following illustration demonstrates how the same algorithm performs with this settings:

Grid sizeParticles NbDecay  T_a  T_l
900×9002304000.950.80.001
Figure 5. Scaling the system up

With a larger grid, more interesting patterns can emerge, and we truly can see how cyclic this system is.

Grid sizeParticles NbDecay  T_a  T_l
900×9003600000.91.20.001
Figure 6. Scaling the system up again – nice patterns starts to emerge

With this set of values, the emerging patterns reminds me of the Belousov-Zhabotinsky reaction [3].

On a side note, I would like to point out the fact that as the ratio particles / grid cells gets closer to 1, basically any cell of the grid can be subject to aggregation. Therefore, it is possible to simulate the same effect without particles, just by considering that a cell has a certain chance to “aggregate” at each iteration. I wrote this on ShaderToy if you are interested by a possible implementation of this idea:

We will stick with particles though, we will later see that this system can be manipulated by playing with the motion of the particles.

4. Applying spatial distortions to the aggregate

Right now, the aggregate is dynamic but it remains static. The motion in the patterns comes from a sweet balance between all the parameters, but we could totally introduce some other distortions and see what happens. Let’s start with a blur. After each iteration, we will apply a 5×5 gaussian blur to the grid of the aggregate.

Grid sizeParticles NbDecay  T_a  T_l
900×9001936000.980.0850.01
Figure 7. 5×5 gaussian blur is applied to the aggregate after each iteration

Unfortunately with this system, I couldn’t find a way to have perfect values that works fine under every condition. It usually requires a bit of trial and error to find something that works well when you introduce a new idea to the system.

Another possibility is to add displacement. Displacement is a way to move individual pixels of a texture to a different position on another texture. A 2D vector field can be used to tell where should the pixels of a texture be picked from another texture. When using GLSL and working with textures, it is not mandatory to use discrete coordinates, for instance it is possible that the output pixel of a texture gets its value grabbed and interpolated from 4 different pixels of an input, if the displacement vector of such pixel isn’t an integer (assuming we are in pixel coordinates).

Figure 8. Interpolation due to a non-discrete displacement vector

By using this, we can create a tiny blur which in my opinion can make the effect more organic over time. I will be using some Perlin Noise as a displacement field and make it evolve over time. In the following illustration, I layered the noise used for the displacement on top. Red and Green are used to encode the value of the vector of the displacement field.

Grid sizeParticles NbDecay  T_a  T_l
900×9001936000.980.210.01
Figure 9. Displacement on the aggregate

We can observe how the displacement influences the reaction. By moving the aggregate, it is more likely that such aggregate will encounter some particles. Thus, the Aggregation Threshold  T_a can be increased to prevent a chaotic reaction.

We can think of many other transformations and effects to add at this step. For instance, I tried to add some translation (there is only translation):

Grid sizeParticles NbDecay  T_a  T_l
900×9001936000.970.30.005
Figure 10. Aggregate translated

Scaling down (0.991):

Grid sizeParticles NbDecay  T_a  T_l
900×9001936000.970.10.04
Figure 11. Aggregate scaled down

Rotation:

Grid sizeParticles NbDecay  T_a  T_l
900×9001936000.970.20.01
Figure 12. Aggregate rotated

Be creative and combine what you know to get your own results đź‘˝

5. Local control of the aggregation rules

Among the 5 parameters affecting the reaction, one of them plays a crucial role: the Aggregation threshold. By itself, it can control… if reaction is happening or not. The other settings are also important, but by tweaking solely the  T_a, we can control the whole reaction.

What if we were using a 2D grid, aka a texture, in which we would encode the value of  T_a at a particular location ? We would know if aggregation can happen by sampling this texture. In the following illustration, I layered the threshold map, in red, with the reaction. The red component encodes  T_a, keep in mind that I lowered the opacity so that the red value does not represent the actual value of  T_a, however it gives us an understanding of the variations of  T_a between different areas.

Figure 13. Ta is driven by a texture

We can even have a threshold map that changes over time:

Figure 14. The threshold map evolves over time

And use the edges of a texture to guide the reaction and the patterns:

Figure 15. Using a butterfly to guide the reaction

Again, this new layer opens many possibilities for interesting ideas and explorations of this system. The other parameters could also be encoded in the texture in the same manner. Feel free to try it out.

6. Moving the particles

By tweaking how the particles move, it is also possible to manipulate the reaction. By having them flow in one direction only, we can force the reaction to happen in the opposite direction. In the next illustration, particles are forced to move to the right only, thus the reaction goes to the left.

Figure 16. Particles only move to the right

Many more things can be done, but I think this is enough for the scope of this article. I really hope you will enjoy playing with this system. You will find a Processing implementation at the end of the article. Comment if you would like the .toe file, I don’t know if it can be useful in such a case.

7. Some more exploration with the system

Follow me on instagram for more content

8. Processing implementation

The source code of the implementation of part 1 and 2 is available on github:

References

  1. Diffusion-Limited Aggregation, Wikipédia
  2. Diffusion-Limited Aggregation, Softology’s blog
  3. Compute Shader, Knonos
  4. Recreating one of the weirdest reactions (Belousov Zhabotinsky), Tim Kench

4 thoughts on “Cyclic Diffusion-Limited Aggregation: real-time natural pattern generation

  1. Hi Baptiste,

    This has been a very interesting read, well put together and easy to understand.

    Would it be possible to grab a .toe file please? I’m interested in trying this effect to audio.

    Many thanks,

    Daniel

    1. Hi Daniel, thanks for the feedback. I will clean the project in the following week and add it to the article. I’ll send it to you via mail (the one available on your website).
      Regards

  2. Awesome work! I recently made a simple DLA implementation in TouchDesigner and this is a great resource I’ll be looking at to take it further. The cyclical aspect especially!

    I’d also love to take a look at the .toe as well if you’re interested in sharing!

Leave a Reply

Your email address will not be published. Required fields are marked *