Skip to content
Diffusion-limited aggregation, fast.
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
LICENSE.md
Makefile
README.md
dlaf.cpp

README.md

dlaf

Diffusion-limited aggregation, fast. Diffusion-limited as f*ck.

Features

  • 2D or 3D diffusion-limited aggregation
  • Super fast? 35 seconds to compute one million points on a single core.

Dependencies

  • boost (used for its spatial index)

Usage

git clone https://github.com/fogleman/dlaf.git
cd dlaf
make
./dlaf > output.csv

Output Format

The parent_id tells you which particle was joined to. It is -1 for initial seed positions. When 2D is used, Z will be zero for all points.

# columns are: id, parent_id, x, y, z
$ head output.csv
0,-1,0,0,0
1,0,0.934937,0.354814,0
2,0,0.0525095,-0.99862,0
3,1,0.989836,1.35331,0
4,3,1.92472,1.70826,0
5,3,0.65572,2.29584,0
6,4,2.90818,1.88937,0
7,0,-0.989205,0.146538,0
8,2,0.917631,-1.50018,0
9,5,0.832028,3.28017,0

Hooks & Parameters

The code implements a standard diffusion-limited aggregation algorithm. But there are several parameters and code hooks that let you tweak its behavior.

The following parameters can be set on a Model instance.

Parameter Description
AttractionDistance Defines how close together particles must be in order to join together.
ParticleSpacing Defines the distance between particles when they become joined together.
MinMoveDistance Defines the minimum distance that a particle will move in an iteration during its random walk.
Stubbornness Defines how many join attempts must occur before a particle will allow another particle to join to it.
Stickiness Defines the probability that a particle will allow another particle to join to it.

The following hooks allow you to define the algorithm behavior in small, well-defined functions.

Hook Description
RandomStartingPosition() Returns a starting position for a new particle to begin its random walk.
ShouldReset(p) Returns true if the particle has gone too far away and should be reset to a new random starting position.
ShouldJoin(p, parent) Returns true if the point should attach to the specified parent particle. This is only called when the point is already within the required attraction distance. If false is returned, the particle will continue its random walk instead of joining to the other particle.
PlaceParticle(p, parent) Returns the final placement position of the particle.
MotionVector(p) Returns a vector specifying the direction that the particle should move for one iteration. The distance that it will move is determined by the algorithm.

Rendering

Rendering is left to you. This code just gives you the location of the points and their hierarchy. But here is an example rendering in 2D with one million particles:

Example

And here is a 3D example with 10 million particles. This image was ray traced in about 10 hours at 4096x4096px with 2048 samples per pixel. Full resolution here.

Example

You can’t perform that action at this time.