Wednesday, May 24, 2017

diamond square fractals

I have previously worked on fractal automata which produce animating patterns in 2D and 3D. A special case of this is where only the larger scale affects the smaller scales, giving static images. One shortcoming with these automata and images is that they have square or cubic symmetry, so features are just at right angles, which gets a bit dull, this was one reason I made this cubic modification for 2D images, giving a hexagonal symmetry.

A tweet by someone called R4_Unit showed a different way to achieve a similar goal. Use the diamond-square algorithm which is used for plasma fractals and hilly height fields, but use automata rules rather than random offsets. R4_Unit applied this in 3D, and has since submitted his code here, and a user called Softology has added his own implementation to his Visions of Chaos software. In 2D the diamond-square algorithm gives a pseudo octagonal symmetry, quite similar to automata rule type 7 that I made in the 2nd link above which gave nice results:
But with a rule that is more complicated than diamond-square. The 3D diamond-square is actually cube-irregular_octahedron-octahedron and doesn't have nearly the simple symmetry of diamond-square, so here I investigate what the results look like in 2D.

For 4 parent points there are 2^4 parent combinations and the central point is either black or white for each, giving 2^16 rule sets. However, once you constrain it to square symmetry, this drops down to only 64 rule sets, which I draw using a 4x4 start grid:
0001
0010
0011
1111

And for the symmetric start grid:
0000
0110
0110
0000
five along one up seems like the 'nicest' in both cases.

For more than two colours the number of combinations explodes. One way to contain that is to demand 'bit symmetry' which in the two-colour case means the rule sets acts the same if black and white are swapped. Unfortunately it is not possible to have a two-colour bit symmetric rule with this diamond-square approach, because there are an even number of identical parents. If two parents are white and two are black then there is no child colour that acts the same if black and white are reversed.

The generalised 'bit symmetry' for n colours means the rules are the same if the n colours are permuted in any way. Then for three colours it is possible to have bit symmetric rules, and there are only three of them:
Overall the rule is to choose the most popular colour of the parent. If this is a tie, then choose the least popular. The choice occurs when there are three parent corners of a single colour. Do you choose the colour there is none of, one of or three of among the parents? The above shows each respectively.

The third is the simpler rule (as it is subsumed by the first criteria), and gives more solid results. Here is a close up of the only complex feature it seems to generate:
These teardrop shapes are all identical. While they are polygonal, each protrusion seems to have an infinite number of edges, in fact it is a tree. So each teardrop is a tree.

In fact, these are the only three bit-symmetric rule sets possible for the diamond-square algorithm for any number of colours, and none exist in 3D at all (assuming cubic symmetry), so they are quite unique.

However, a square lattice is not the only scalable lattice, the only other I know is the triangular lattice. And in this lattice bit-symmetric automata occur only with four colours, and there are only two of them:
The rule is the same as for the square lattice case, but the choice is when two of your parents are the same colour, do you choose the colour there is one of or two of? Again, the more solid results come from the latter case. It is quite a wonderful shape, with almost rounded looking blobs that belie its triangular lattice frame. These used a randomised 4x4(ish) start pattern, and here is higher resolution with an 8x8(ish) start pattern:
The rule for this and the teardrop above are incredibly simple, pick the most popular parent colour, if it is a tie then pick the least popular.

Here are three simplest cases:
The apparent fifth colour is a nowhere-dense mix of the four colours and primarily takes the shape of a modified Koch snowflake, by contrast the dense colours are all finite sided polygons.