Saturday, December 14, 2013

Rolling fractals: Thistles and leaves

An interesting fractal construction comes from rolling circles inside a stack of larger circles. This has been considered here and here... however I don't think these designs are the correct maths for proper conformal rolling circles. The equation I uses gives a different result.

For a set of nested circles of power 2 diameters, rolling with a constant roll contact point speed, in alternating directions I get this:
It is part of a set of fractals which are defined by the curvature ratio from parent to child. Here we see the family for ratios -4,-3,-2,  2, 3, 4.  (-1,0 and 1 are not fractals).

None of these fractals appear to self intersect.

Tuesday, October 1, 2013

The golden egg

The value 0 is the set that is a distance 0 from its negative.
The unit diameter circle is the set that is a distance 1 from its negative.

The value 1 is the set that is a distance 0 from its inverse.
What is the set that is a distance 1 from its inverse?

One point in the set is the golden ratio (1.618..) since its inverse is 0.618... but it isn't the only point in the set, for instance 0.618 is also in the set. Also cos(30) + 0.5i is in the set since its inverse is cos(30) - 0.5i. The full set is drawn in blue:
The green curve is an ellipse, since the blue oval is 'fatter' at smaller real values and thinner at larger real values it is in egg shape; I'll call it the golden egg! In fact there are two of these, one being the negative of the other.

The left and right sides can be calculated iteratively and separately, for the left side (lesser real values):
a = 1/(c + a) where c is the unit radius circle.
For the right side:
a = 1/a - c

Does anyone know the analytic formula?

One could extend this idea to the quaternions (a golden orb? volume embedded in 4d) and presumably also to the octonions.

Wednesday, February 13, 2013

Relativistic automata continued II

In a previous blog I outlined roughly how you can add velocity symmetry neatly into fractal automata (from now on called Lorentz automata). Here are some implementation descriptions.

Minkowski lattice

The data structure for cellular automata is the (n dimensional) grid, for fractal automata it is a grid-tree, otherwise known as a quad-tree and oct-tree in two and three dimensions respectively. For Lorentz automata I use what I call a Minkowski lattice (or M lattice). Similar to a grid tree, but each grid has several children of different elongations, as such two parents can have the same child, which makes this structure a lattice:

The data structure is therefore the set of grids with resolutions (2^w, 2^h) for all w,h between 1 and the highest resolution depth. The non-square grids represent non-zero velocity frames.

Lattice update order

Assuming we have such grids available for accessing and setting the bit value at any point on the grid, the challenge is then to find the correct order at which each cell of each grid is updated. For the 1+1 Minkowski space-time the update order can be seen as follows:
The image shows the high resolution grid on the left and two lower resolution grids as examples. The red/green arrows indicate the local coordinate origin for each grid. If a single frame step is defined as one quarter the diagonal length of the highest resolution grid then the centre of the grid cells and all lower resolution grid cells always pass through one of these frame times (shown as blue line).
We want each cell to be updated when the frame time hits the centre of that cell, so the simplest algorithm is to iterate through all the grids and update all the cells that touch the line.

In 2+1 space-time the frame-time represents a plane which the 3d grid cell centres sit on. The direction of time is along the long-diagonal of the grid coordinates. To update the cells correctly you need to define a resolution for the plane, e.g. 256x256, then for each grid it must find cell centres that lie on and in this clipped plane:

for (i = 1; i<=resolution; i*=2)
  for (j = 1; j<=resolution; j*=2)
    for (k = 1; k<=resolution; k*=2)
      for (x = centre.x-resolution; x++)

        if ((x&(2*i-1)) != i)
        for (y = centre.y-resolution; y++)

          if ((y&(2*j-1)) != j)
          z = frame - x - y;
          if ((z&(2*k-1)) != k)
          updateCell(x/(2*i), y/(2*j), k/(2*k)); 

Interestingly the update of the lattice has an exactly constant number of updateCell calls per frame, which is useful for real-time use. The number of updateCell calls approaches 4 times the number of pixels, so the cost of adding velocity symmetry using these Lorentz transforms is finite and small, unlike with Galilean transforms.

Cell update 

With the fractal cellular automata the half-resolution parent cell is located at (frame - 1)>>1. For these Lorentz automata it is simply this for each axis, e.g. (x-1)>>1 on each axis that is half-resolution. This therefore applies to elongated grids too. The purpose of this is that you only retrieve data from neighbour cells that are prior in time.

Conversely, the double-resolution children cells are located at x << 1 and ( x << 1 ) - 1 again ensuring that these neighbours are prior in time so have already been set.


Due to the large search space, I start with a hand-built automata rule:
This diagram shows a very simple Lorentz automaton, there are just four points with zero velocity, each with scale twice the previous. The larger scale points (set in the larger voxel grid) are interpreted by the successively higher resolution grids such that the resulting shape is a high resolution hexagon in this case. A different rule could generate any shape like those seen in the static fractal automata.
Additionally there are seven clones of these 4 points which have successively larger upwards velocities (velocity 1), and also 7 clones with successively larger diagonal velocities (velocity 2 in the diagram).
The picture was taken after a few seconds, so the points have moved from their initial positions. You can see most clearly the tiny points in the bottom right area, notice that the points are not evenly spaced along the velocity, even though they each have the same difference in speed. This is because we are using a relativistic velocity. The points get closer together towards the top, this is the equivalent of approaching the speed of light.
Looking at the top left section of large hexagons, it looks a bit like a grid of points, this is because there are points for each non-uniform power of two scale, which give the different point directions, velocities and scales. The middle points seem flattened in the direction of movement, this is mainly because the three prime motion directions are elongated in this model and the three secondary motion directions are flattened. But additionally there is some flattening due to time dilation.
Notice that the decimation (from low res to high res) keeps smoothly shaped hexagons even when they are distorted by their velocity.

Base tiling

While most cellular automata use a square grid, these automata are a bit different. The long-diagonal projection of each cube through time gives a variable shape, but we can make the grid constant by viewing the last three frames rather than just the last frame. This gives us a base hexagonal tiling, which is nice since it has 6 rotational symmetries compared with 4 for a square, plus it is a 'stable' tiling in that it is the most efficient filling of the space. This also extends into 3d (where time is the long diagonal of a 4d 'hyper'cube)... the base tiling becomes a rhombic dodecahedron, with 12 rotational symmetries compared to 6 for the cube. Equally, the honeycomb of rhombic dodecahedrons are the most space efficient way to tile 3d space. 
This also makes the 'diagonal time axis' method an attractive method for normal fractal automata, not just for Lorentz automata.