Diffusion-limited aggregation creates branched and coral like structures by the process of randomly moving particles that touch and stick to existing stationary particles.
All of the images and movies in this post were created with Visions of Chaos.
Real Life Experiments
If you put an electrodeposition cell into a copper sulfate solution you can get results like the following images.
2D Diffusion-limited Aggregation
DLA is a simple process to simulate in the computer and was one of my first simulations that I ever coded. For the simplest example we can consider a 2D scenario that follows the following rules;
1. Take a grid of pixels and clear all pixels to white.
2. Make the center pixel black.
3. Pick a random edge point on any of the 4 edges.
4. Create a particle at that edge point.
5. Move the particle randomly 1 pixel in any of the 8 directions (N,S,E,W,NE,NW,SE,SW). This is the “diffusion”.
6. If the particle goes off the screen kill it and go to step 4 to create a new particle.
7. If the particle moves next to the center pixel it gets stuck to it and stays there. This is the “aggregation”. A new particle is then started.
Repeat this process as long as necessary (usually until the DLA structure grows enough to touch the edge of the screen).
When I asked some of my “non-nerd” aquaintances what pattern would result from this they all said a random blob like pattern. In reality though the pattern produced is far from a blob and more of a coral like branched dendritic structure. When you think about it for a minute it does make perfect sense. Because the moving particles are all coming from outside the fixed structure they have less of a chance of randomly walking between branches and getting to the inner parts of the DLA structure.
All of the following sample images can be clicked to see them at full 4K resolution.
Here is an image created by using the steps listed above. Starting from a single centered black pixel, random moving pixels are launched from the edge of the screen and randomly move around until they either stick to the existing structure or move off the screen.
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: when they move next to a single stuck particle
The change in this next example is that neighbouring pixels are only checked in the N, S, E and W directions. This leads to horizonal and vertical shaped branching.
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W
Particles stick condition: when they move next to a single stuck particle
There are many alternate ways to tweak the rules when the DLA simulation is running.
Paul Bourke’s DLA page introduces a “stickiness” probability. For this you select a probability of a particle sticking to the existing DLA structure when it touches it.
Decreasing probability of a particle sticking leads to more clumpy or hairy structures.
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: 0.5 chance of sticking when they move next to a single stuck particle
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: 0.1 chance of sticking when they move next to a single stuck particle
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: 0.01 chance of sticking when they move next to a single stuck particle
Another method is to have a set count of hits before a particle sticks. This gives similar results to using a probability.
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has hit stuck particles 15 times
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has hit stuck particles 30 times
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has hit stuck particles 100 times
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has hit stuck particles 1000 times
Another change to experiment with is having a threshold neighbour count random particles have to have before sticking. For example in this next image all 8 neighbours were checked and only 1 hit was required to stick, but the moving particles needed to have at least 2 fixed neighbour particles before they stuck to the existing structure.
The first 50 hits only need 1 neighbour. This build a small starting structure which all the following hits stick to with 2 or more neighbours.
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has 2 or more stuck neighbours
That gives a more clumpy effect without the extra “hairyness” of just adding more hit counts before sticking.
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has 3 or more stuck neighbours
This seems a happy balance to get thick branches yet not too fuzzy ones.
Start configuration: Single centered black pixel
Random pixels launched from: rectangle surrounding existing structure
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has 3 or more stuck neighbours and has hit 3 times
The next two examples launch particles from the middle of the screen with the screen edges set as stationary particles.
Start configuration: Edges of screen set to black pixels
Random pixels launched from: middle of the screen
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has 1 or more stuck neighbours
Start configuration: Edges of screen set to black pixels
Random pixels launched from: middle of the screen
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has 3 or more stuck neighbours
These next three use a circle as the target area. Particles are launched from the center of the screen.
Start configuration: Circle of black pixels
Random pixels launched from: middle of the screen
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has 1 or more stuck neighbours
Start configuration: Circle of black pixels
Random pixels launched from: middle of the screen
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has 2 or more stuck neighbours
Start configuration: Circle of black pixels
Random pixels launched from: middle of the screen
Neighbours checked for an existing pixel: N, S, E, W, NE, NW, SE, SW
Particles stick condition: once a moving particle has 3 or more stuck neighbours
This next image is a vertical 2D DLA. Particles drop from the top of the screen and attach to existing seed particles along the bottom of the screen. Color of sticking particles uses the color of the particle they stick to.
Start configuration: Bottom of screen is fixed particles
Random pixels launched from: top of the screen
Neighbours checked for an existing pixel: S, SE, SW
Particles stick condition: once a moving particle has 1 or more stuck neighbours
Dendron Diffusion-limited Aggregation
Another DLA method is Golan Levin’s Dendron DLA. He kindly provided java source code so I could experiment with Dendron myself. Here are a few sample images.
Hopefully all of the above examples shows the wide variety of 2D DLA possible and the various methods that can produce them. This post was mainly going to be about 3D DLA, but I got carried away trying all the 2D possibilities above.
3D Diffusion-limited Aggregation
DLA can be extended into 3 dimensions. Launch the random particles from a sphere rather than a surroundiong circle. Check for a hit against the 27 possible neighbours for each 3D grid cell.
For these movies I used default software based OpenGL spheres. Nothing fancy. Slow, but still managable with some overnight renders.
In this first sample movie particles stuck once they had 6 neighbours. In the end their are approximately 4 million total spheres making up the DLA structure.
This second example needed 25 hits before a particle stuck and a particle needed 5 neighbours to be considered stuck. This results in a much more dense coral like structure.
Note: see here for my latest much improved 3D DLA results.
A Quick Note About Ambient Occlusion
Ambient occlusion is when areas inside nooks and crannies are shaded darker because light would have more trouble reaching them. Normally to get accurate ambient occlusion you raytrace a hemisphere of rays from the surface point seeing how many objects the rays intersect. The more hits, the darker the shading. This is a slow process. For the previous 3D DLA movies I cheated and used a method of counting how many neighbour particles the current sphere has. The more neighbours the darker the sphere was shaded. This gives a good enough fake AO.
Programming Tip
A speedup some people do not realise is when launching random particles. Use a circle or rectangle just slightly larger than the current DLA structure. No need to start random points far from the structure.
Other Diffusion-limited Aggregation Links
For many years now the ultimate inspiration in DLA for me has been Andy Lomas.
http://www.andylomas.com/aggregationImages.html
His images like this next one are very nice.
Another change Andy uses is to launch the random walker particles in patterns that influence the structure shape as in this next image.
Future Changes
1. More particles. The above 2 movies have between 4 and 5 million particle spheres at the end of the movies. Even more particles would give more natural looking structures like the Andy Lomas examples.
2. Better rendering. Using software (non-GPU) OpenGL works but it is slow. Getting a real ray traced result supporting real ambient occlusion and global illumination would be more impressive.
3. Controlled launching of particles to create different structure shapes other than a growing sphere.
Jason.
