Sphere Cluster

We can generate 3D clusters in a similar way to the previous post, but using a hyperbolic regular polyhedron tiling instead of a hyperbolic regular polygon tiling. We can continue to use this 2D diagram as a guide:

We define the outer green circle as radius 1, and the offset green circle l2 has its centre at a distance L=sqrt(1+R^2) where R is the solution to:

 R/theta = sqrt(1+R^2)/sin(pi/2 + pi/m)

where theta is the angle from the polyhedron centre to the nearest face edge and m is the number of polyhedrons that meet at each edge. There are two good polyhedrons to use here, the dodecahedron and the icosahedron, their values and resulting formula are: 

 Dodecahedron: 

• theta = atan2(phi+2, 2phi + 2 + 1/phi)
• m      = 4
• R      = sqrt(2)/sqrt(-2 + cosec^2(theta))

Icosahedron:

• theta = atan2(phi, 1+2phi)
• m      = 3
• R      = 2/sqrt(-4 + cosec^2(theta))

Where phi is the golden ratio, and the inner red circle has radius r=L-R.

To render in 3D we want to do something better than just an inside-outside test, we want to approximate the distance to the nearest surface. It goes roughly like this... invert each query point p around the red radius r sphere then:

1. rotate the point to a be radially in one single polyhedron face*
2. if it is inside l2 you invert it around l2
3. if its magnitude is less than rk (plus a skin width) then divide by rk and then invert around l4 = sqrt(r), sending the red sphere to the outer green unit sphere
4. once you are out of iterations return the distance to the centre sphere rk, multiplier by a scale factor that is initialised to 1 and grows in proportion to all transformations of p in the above steps

* this is a bit harder in 3D than 2D. The simplest I can think of is to fold the point around the planes defined by the origin and each edge of the chosen face. For the dodecahedron the chosen face has vertices in order: (1/phi,0,phi), (1,-1,1), (phi, -1/phi,0), (phi,1/phi,0), (1,1,1). For the icosahedron the three vertices are (0,1,phi), (0,1,-phi), (phi,0,1). The planes can be generated using the cross product of adjacent vertices. I found that for the dodecahedron you just need to fold around each edge twice to guarantee the point ends up radially in the specified face, and for the icosahedron you need to do it three times. 

The direction to the l2 sphere centre is then the direction to this face centre, which is the mean of the above vertices.

The resulting approximate signed distance function to the shape's surface is sampled in Fragmentarium in order to generate a rendering of the shape with lighting and shadows. 

Here is the result for the dodecahedral cluster, with k values from 0.7 up to 1:

Here against a black background, a close up of k=0.7:

and k=0.8:

and k=0.1:

For the icosahedral cluster, here are k values of 0.7 up to 1:

Both the decahedral and the icosahedral become cluster-sponges at k=1, and are very spikey and visually less rough. We can make the shape less spikey at higher k by alternating between the dodecahedral and the icosahedral clusters. Since they are duals of each other, we should expect that to do the opposite of lining up subclusters. 

There are two versions depending on which shape you start with. Here starting with the dodecahedral with k from 0.8 up to 1:

a close up at k=1:

Here we start with the icosahedral shape, k = 0.7 to 1:

It is a bit hard to render this fractal for k>=1, but if you replace the final distance calculation with a slightly smaller sphere distance then it makes no difference to the limit set, and avoids some rendering artifacts for k>1, which is when the shape changes from a cluster to a sponge.

So here is the icosahedral fractal for k=1 and k=1.3:

and the dodecahedral from k=1 up to k=1.6:

If you toggle between icosahedral and dodecahedral, it is a bit more organic looking:

k=1.1 starting dodecahedral:

k=1.2

Starting icosahedral, k=1.1:

k=1.16

k=1.17

Disk Cluster 2

 In a previous post I was making cluster fractals because these are quite rarely found in fractal examples. Moreover, I was making clusters that are nowhere differentiable (from the outside), which is the purest sort of fractal boundary because everywhere has the same fractal property, with no smooth regions. 

The only problem with these clusters is that they were a little too heavily constructed, and so don't transfer to 3D in any obvious or simple way. 

This post however constructs the cluster based on a very small number of symmetries. It uses two different sphere inversions, octagonal symmetry and a single scale factor k. As such, it makes a proper Kleinian group limit set. To describe it I borrow from figure 6 of this Kajino paper:

We define the outer green circle as radius 1, and the offset green circle l2 is at a distance L=sqrt(1+R^2) where R is its radius: R=2/sqrt(-4 + cosec^2(pi/n)), and n is the polygon number of sides, here it is n=8. The inner red circle has radius r=L-R.

To test if a point is inside or outside the cluster, first you invert the point around the purple circle then:

1. rotate the point to the first octant (in line with the circle l2)
2. if it is inside l2 you invert it around l2
3. if its magnitude is less than rk then divide by rk and then invert around l4 = sqrt(r), sending the red circle to the outer green unit circle

repeat until its magnitude is > 1 (black) or you run out of repetitions (white).

For k=0.9 we get:

For k=1 we get:

and for k=1.1 we get:

Actually this last picture uses slightly less than 1.1 as we need to tweak the value for circles to match properly. I don't have the exact analytic value for k here, but it is very close to k=1.0985.

In terms of fractal classes these are a cluster, a cluster-sponge and a cluster-foam respectively. The first differs from the previous cluster in that the subclusters closer to the centre don't form a uniform pattern, and because it is a proper Kleinian group it generalises cleanly to the two other structures pictured above.

The value of n doesn't have to be 8 but it needs to be more than 6, so here are clusters for n=7 and n=9, both for k=0.8:

Here are the cluster-sponge versions (k=1):

One thing to note about these cluster-sponges it that they are very spikey. That is because the sub-cluster orientation lines up with its parent, causing a cascade of disks all in a row. 

We can avoid that by rotating each point by pi/n in step 3, here for n=8 for comparison with the first three images:

This latter image is again slightly away from k=1.1, at approximately k=1.096. Here's a high resolution close up:

Notice that these are all less spikey, and the k=1 case is no longer a cluster-sponge, so can have larger sub-clusters before touching. In the n=7 case the touch point happens around k=1.064:

For fun here's the prior n=8 image coloured by iteration depth:

The next step is to bring this formulation across to three dimensions. I cover this in the next post, but as a quick preview:

There are basically two ways to do this, we can use a hyperbolic tiling of an icosahedron or a dodecahedron. Here I'm using an icosahedron, which give 20 subclusters (one for each face).

The above image is a sphere at each icosahedron in a hyperbolic tiling, only the tiling has been sphere inverted, sending all radii r to 1/r. We use a value of k of roughly 0.5 above.

We then need to recurse inside each sphere, like so:

For larger k, around 0.8:

and k=1

Here's close up around k=0.8:

Mean Clusters

Imagine you dropped some pebbles on the ground or threw several darts at a bullseye, what shape do they form on average?

If we model this 'cluster' of pebbles or darts as a Gaussian distribution then we can estimate the average shape of the cluster. 

I run it as a tournament, so each set of 2D points is averaged with one other, all the way down to one mean cluster.

In order to get the average of two clusters we have to match them up. Not only does this mean translating and rotating one cluster to be as close as possible to the other cluster, but it also means considering all permutations of the cluster order, in order to find the mapping that produces the closest Euclidean transformation between the two point sets. 

If we do this then we get shapes emerging. Obviously for 2 darts they just form a point pair. For 3 darts we get this:

For 4 darts we get this shape:

And for 5 points, we get:

For 6 we get:

Putting them in a line with 1 and 2 for completion we get:

Or rendered a bit bigger:

You might imagine a 'mean dice' using these patterns as its spots for 1 to 6, since they are the most average shape that a cluster of that size would be found in. 

 

In each case the result has to have bilateral symmetry, but if we allow reflections when comparing shapes then we get asymmetric results:

and for 4:

and for 5:

I have rotated them so the closest points are horizontal, this makes it look like the result is a spiral that grows. Does the pattern continue for 6 points?:

It looks like the pattern breaks at 6, though it is a bit hard to see because it could be this or its mirror image.

A different definition of a cluster is a set of points that are closer to each other than to any other points. Such clusters can be generated from any uniformly randomly placed set of points. It would be interesting to see whether this produces a different set of shapes. I doubt they would be very different as the distribution of such a cluster is surely fairly close to a radial Gaussian. 

Mean Islands

 What does the average island look like?

To answer that, we need a very general model for generating islands. The model I am using is the Gaussian Free Field. This is the 2D equivalent of Brownian noise, and it has the property that it is conformal / scale symmetric. In other words, it is a fractal height field very similar to the old plasma fractals used to make fractal landscapes:

In fact the Gaussian Free Field is the mathematically simplest and most invariant such landscape.

All we need to do is set a water level and the result is a set of islands. So what does the average such island look like?

It wouldn't be circular because it is a shape, and shapes are invariant to Euclidean transforms, in other words you need to rotate and pair of islands to best fit, before taking the average of the height field. This is therefore part of my series on mean shapes under symmetries. The first attempt at a mean island looks like this:

The greyscale is the island, with height shown from 50% grey up to white, and the blue is water, showing the depth. It looks like an inverted ellipsoidal paraboloid, i.e. oval shapes, with a length to width ratio of something close to 2  (1.97 above, which merges 2^16 islands).

In order to generate the mean island, I generate a large number of Gaussian Free Fields (2^18) in a fixed square region, then for each pair of fields I find their peak and lower the water level until I get an island of specified area (I'm using 1/20 the area of the GFF). It doesn't matter that I use the highest peak, or what area I choose because the GFF is conformal and all peaks have the same statistical properties. I just can't make the area too large compared to the GFF region. 

Examples of GFF islands. Brightness is height, blue is below water, yellow is the floodfilled island from the highest peak in the map. Red is the centroid and dark red is the centroid plus the eigenvector corresponding to the smallest eigenvalue of the island's covariance matrix.

I then must align the two islands. A smart way would be to use the Fourier-Mellin transform to find the closest transformation between the two islands. However this is complex and slow and didn't work after several attempts including using a 3rd party library, so I use a simpler method: I take the centroid of each island, and find the covariance around each one, then I use the eigenvectors of this covariance to align the two islands, so that the smallest eigenvectors are either parallel or anti-parallel. I test both transformations by looking at the sum of the product of all the heights above water.

It is a bit surprising that the result is such a uniform ellipse, which has 180 degree rotational symmetry. I thought that the ability to rotate would allow more of an egg-like shape with 360 degree rotational symmetry. I think the reason why is that aligning the centres of mass is not the same as finding the cross-correlation peak. 

So instead, I cross correlate the translations by using the 'FFT->multiply by conjugate->IFFT->find peak real part' technique, and I check the value of the peak for both 180 degree rotations, making sure to interpolate the peak using a quadratic interpolation with the two neighbours along each axis. The result is what I expected, the mean island is an egg-like shape:

If I allow reflection symmetry when finding the closest correlation then the result is (surprisingly) unaffected:

This is a bit suspicious. It could be that reflective symmetry is where a full Fourier-Mellin cross-correlation is required, to see the asymmetry in the island, or the asymmetry maybe just be subtle. 

Anyway, here is another run at twice the resolution, just to show that it is repeatable and smooth: 

Mean Repeating Continuous Function

It a previous post I looked at the mean path of Brownian motion in 2D. Here I look at something similar in 1D: for a repeated continuous function. 

Again, the question arises as to what the space of all continuous repeating functions are. I think the answer that makes the least assumptions is a Brownian bridge from 0 to 0. It is therefore repeated Brownian motion. 

If we took the mean function of all such Brownian bridges, the result would be y=0, which is rather boring. 

However, this series of 'mean things' is including symmetries, or rather, making certain parameters non-absolute. In this case we make the x position of the function non-absolute, and we give it scale symmetry in its range, so we look at the mean function only relative to its own variance in y, and without any absolute x values. 

We can make a Brownian bridge from 0 to 0 by noting that the power spectrum of Brownian noise is 1/f^2 where f is the spatial frequency. We can therefore generate this spectrum with random phase values per wavelength, and take the inverse Fourier transform to get the resulting Brownian bridge.

The algorithm is as follows:

For each pair of repeating functions, cross correlate (Fourier transform, element-wise multiply, inverse Fourier transform) to get the x offset where they are closest, then average the two using this x offset.

The resulting function looks like this:

In other words a sine wave. At least it appears to be a sine wave, and it probably is exactly that. 

We can also give the range vertical symmetry, so we pick the closest correlation between the two functions from either the two positive functions, or with the second function negated. This removes the symmetry in the repeating function, giving a slightly leaning sine wave:

Noting that it is this function, and its negative, which are the mean repeating functions.

It is probably not right for our samples to have an exact 1/f magnitude for each wave frequency f, a better sample would have its magnitude taken from a normal distribution with standard deviation f. This takes longer to converge but seems to give the same results. Without reflection symmetry:

With reflection symmetry:

We could extend this idea to 2D, for example finding the mean Brownian drum (0 in a unit circle) under rotation symmetry, but I think it is likely to be a simple smooth Bessel function. We could also make a Brownian surface on a sphere (using spherical harmonics presumably) under spherical rotation symmetry, but I also imagine that the result would be very smooth and simple.