Help : looking for a (fast) rotation symmetric CA diffusion.
Hello, let's say that you have a floating point cellular state (or a few bit wide one, as you prefer), and you start from a uniformly blank world state, except a small local neighbourhood, what CA would you use, for it to diffuse acceptably FAST. The slow solution, is to use a simple blur on the von neuman neighborhood, however it is indeed very slow. I also tried various ways of reinforcing it, accepting small losses of symmetry, but so far it's mostly been disappointing.
Hence my calling to you, CA community, who might already have solved this issue either willingly or by random luck. Any help appreciated, thanx in advance.
Posted Apr 10, 2019, 11:02 AM UTC
34
If computational speed is what you're looking for: almost any simple convolution, if repeated many times, approaches an ideal Gaussian blur. So one solution I've used is computationally very simple: compute a weighted average of each value with its immediate neighbors. At its simplest, just replace each value with the average of it and its four neighbors. This can be done very efficiently with loops if you can access the memory directly.
Using such a simple convolution you would expect the anisotropy to be pretty bad, but with repeated iteration, the expanding boundary becomes nearly circular. If the goal is a high framerate, it's a good way to go.
I have used this technique successfully to implement interactive reaction-diffusion and similar algorithms. Works well in fragment shaders, too.
it's more like diffusion speed that i'd like to obtain. Basically the distance that the symetric signal goes to relative to the number of convolution step. Speediest would be a simple floodfill, but that's far from rotation symetric. Slowest would probably be the blur, but that's far from "fast", i don't know if it's quadratic or even slower, and then it also tend to rapidly degrade to some form of sand castle as you go farthest from he origin, maybe that's why it get so slow. Or maybe i missed something ?
I see. Well, you could repeat the simple neighbor average you're using many times per frame.
Or, you could switch to a Gaussian convolution. This would multiply all values by a square matrix, the blur kernel. There are some good fast implementations. A larger kernel would give you faster diffusion but slower computation.
This is a common operation, so most decent graphics/math libraries would have a relatively fast implementation that would compute the Gaussian matrix for you. For example, opencv's GaussianBlur
I mostly use opengl. On shadertoy there are some implementations also, especially this one : https://www.shadertoy.com/view/4dcGW2 Maybe i should investigate further. For the time being, i mostly use a simple polygonal diffusion mecanism, that enable for example to build the distance map at high diffusion speed. here is one of my prototype implementation : https://www.shadertoy.com/view/wdSXzy You can use the mouse to click in and drag on one of the diffusion point.