GPU Diffusion Limited Aggregation
I have explored this algorithm before, in a limited capacity. The algorithm that the html5 demo uses is horrendous, slowing down linearly as more points become anchored. That's a bad implementation, with a lot of redundant calculation - I have wanted to explore doing this on the GPU. Some posts by Mattias Malmer I saw a few years ago related this method to crystal growth, and got some interesting results - I would really like to explore this. He gave me some information about the relation between atoms in different forms of crystal lattice. I am looking more closely now at some of his renders, and the grid size is quite large relative to the overall block... This gives me some ideas on how I might implement the crystal lattice constraints.
Moving to the GPU implementation, I got away from keeping a list of anchored particles at all. That was a very naive approach, and it was where my old js implementation completely fell down. Iterating through the list of anchored particles to find a candidate to bond to was O(N), and it became the vast majority of the sim time as the number of anchored particles, N, grew larger. By putting this information on a constant access time grid, you can take one sample to see if the cell you are inside has an anchored cell. I think this will extend to keeping more information on the grid, and keeping an index or maybe indices of any contained particle(s). This indirection seems like it will make it easy to keep 4x4 matrix orientation and position, for the anchored particle. I think this will be most of what I need to implement something based on Mattais' suggestions.
One of the key things I see here is that the process requires this particle orientation. It's an important part of the parameterization of the crystal growth. This might be in a complementary SSBO that is indexed into with something based on the grid values. This matrix is important because it allows you to orient the lattice structure of the crystal itself. These are the geometric bonds between neighboring particles. A given free particle would potentially form a bond with a nearby anchored particle, and then anchor itself to be subsequently bonded to. There are some open questions here as to how this process actually takes place. One of Mattias' more interesting suggestions was this idea of introducing a small chance to randomly apply small errors into this grid orientation term, so that you get more organic and random crystal growth.
This implementation models unoriented random walkers bonding to anchored cells, in a very simple way. If the grid has a nonzero value, it's a neighbor that can be bonded to. Each new bond formed simply increments the corresponding texel in that grid texture. It's actually a little too fast to play with, and needs some performance knobs to adjust the simulation rate. The volume fills too quickly, and you don't really have much time to watch it do its thing. I think there's potential there if you introduced a random chance to bond, rather than just bonding in all cases. Alternatively, the entire process could be managed on the CPU, where this kind of oriented particle system is maybe easier to work with, and then keep a list of newly formed bonds as updates to a 3D texture per update and upload in time to do volumetric lighting and present the next image