Rendering Complete Multibranch Multibrot Sets

This post tackles the problems faced when trying to generate full images of the multibrot fractal, taking into account all the possible branches when the exponent is a rational number.

Multibrot set of order 2.5

Multibrot set of order 2.5


The Mandelbrot

To understand the challenges faced when trying to compute non-integer multibrot sets you must first be aware of the most famous example of a multibrot, the mandelbrot.

The mandelbrot set is defined as all the points in the complex plane that are bounded when this iterative operation is applied:

z_{n+1}=z_n^2+c

where z_0=0 and c is the complex number (x + iy) of the scaled pixels coordinates you are calculating.

When this operation is applied to the complex number c, the point either stays bounded (converges to the origin, another attracting region or a cycle) or the point diverges away to infinity.

Therefore, this is relatively simple to calculate. Simply loop through all the points in the region of -2 to 2 and -2i to 2i on the complex plane. If after a set number of iterations (let’s say 100) the point is still within another set region, the escape boundary (normally a circle of radius 16), then the point is bounded and so belongs to the mandelbrot set and is coloured white. If it is outside this region it is unbounded and coloured black (or sometimes coloured depending on its escape time, the number of iterations required for it to leave the escape boundary).

The formula of the mandelbrot can be extended to other integers such as 3,4,5…e.g. z_{n+1}=z_n^4+c.  As this number increases the mandelbrot (now called multibrot) changes shape, although the basic features still remain. You can see that as the exponent (x) approaches infinity the shape of the mandebrot tends towards the unit circle. Because \lim_{x \to \infty} z^x=\left\{\begin{matrix}  0 & if |z| <1\\  \infty & if |z| >1  \end{matrix}\right.

Creating these multibrots is simple, the problem arises when trying to generate the fractals of order 2.5 or 2.2 or any other non-integer number.


 Multibrots and Nth Roots

This problem arises due to the multivalued functions of the nth root.

For example the square root function can return 2 possible values, + or -. This can be visualised using a complex reimann surface.

Riemann_sqrt.svg

Surface of \sqrt{x}

To calculate what z^{2.5} is you can break it down into z^2z^{1/2} , in fact the general formula for it is z^{p/q} = z^{p}\sqrt[q]{z} , however the \sqrt[q]{z} has q possible distinct values. These means that for each point you iterate it is able to ‘move’ to q possible points instead of just one, and some of these points and branches lead to convergence while some of the branches lead to divergence.

The n distinct roots of a nth root can be given by De Moivre’s formula

\sqrt[n]{re^{ix}}=r^{1/n} \left[ \cos \left( \frac{x+k\cdot 2\pi}{n} \right) + i\sin \left( \frac{x+k \cdot 2\pi}{n} \right) \right]

These images illustrate this feature, the red dot represents the starting point (0.3 + 0.6i), each new point is connected by a white line and shown by a green dot.

It can easily be seen how chaotic the different branches related with the square root are. In the image of the 6th iteration of order 2.5 you can clearly see how some points end within the boundary while some have diverged away. This presents a problem because it means that the fractal doesn’t always converge, depending on which value of the square root you take. Furthermore, calculating if a point is inside these multibrots is far more computationally difficult than normal. Calculating one point in the mandelbrot accurate to 50 iterations requires about 50 calculations, however in the multibrot of order 2.5 the same point and iterations would require 2^1+2^2+2^3+2^4 \cdots 2^{50} = 2^{51}-2 \approx 2000000000000000 calculations. Therefore it is only viable to render multibrots to 6 or 7 iterations.

Normal renderings of these multibrots would only use the principal value of the root function and so would ignore all other branches. Instead of taking into account all the paths that the point can take they only use the first one, however to generate the true image of the multibrot you must use all the branches because a point can converge and diverge on separate branches. This proves to be much faster, however, the image created bears little resemblance to the true multibrot as shown later on.

Coding the Multibrot

I used recursive functions in java to generate the image of the multibrots. Starting with a 2D array of integers called image we scale each point so it lies within the range of the multibrots (-2 to 2) and then use this function to evaluate each point.

   private static int evaluatePoint2(double x, double y, int currentDepth, int maxDepth,int total,double c,double ci,int basenumber,int basenumerinumber, int baserecinumber) {

        double magnitude = (x * x + y * y);

        if(magnitude>64)
        {
            return 0;
        }else
        if(currentDepth==maxDepth)
        {
            return 1;
        }else
        {
            magnitude = Math.sqrt(magnitude);
            
            double angle = Math.atan2(y, x);
            double xSquared = Math.pow(magnitude,basenumber)*(Math.cos((angle*(double)(basenumber))));
            double ySquared = Math.pow(magnitude,basenumber)*(Math.sin((angle*(double)(basenumber))));

            double newx = Math.pow(magnitude,basenumerinumber)*(Math.cos((angle*(double)(basenumerinumber))));
            double newy = Math.pow(magnitude,basenumerinumber)*(Math.sin((angle*(double)(basenumerinumber))));

            angle = Math.atan2(newy, newx);

            double magnituderoot = nthroot2(baserecinumber,Math.sqrt(newx*newx+newy*newy));

            for(int i = 0 ; i < ((baserecinumber));i++)
            {
                double rootx = magnituderoot*(Math.cos((angle+i*2f*Math.PI)/(double)(baserecinumber)));
                double rooty = magnituderoot*(Math.sin((angle+i*2f*Math.PI)/(double)(baserecinumber)));

                double x1=(xSquared*rootx-ySquared*rooty) + c;
                double y1=(xSquared*rooty+rootx*ySquared) + ci;
              
                total += evaluatePoint2(x1,y1,currentDepth+1,maxDepth,0,c,ci,basenumber,basenumerinumber,baserecinumber);
            }
            return total;
        }
    }

This function takes a point at x,y (start it a 0,0 with current depth 0) with the complex constants c,ci (the point you are iterating through from -2 to 2) and calculates all the branches of the multibrot of z^{basenumber}z^{basenumerinumber/baserecinumber}. It calculates all the branch points up to the max. depth number of iterations and then returns the total number of branches that are still bounded within the multibrot (here the escape region is a circle of radius 8). The function nthroot2 returns the simple principle root, I just used a modified version to generate more accurate roots but the normal java function Math.pow(x,1/n) is good enough.

After the entire plane has been calculated and the 2D array of numbers completed then your program can draw the fractal. For mine I used the colour scheme:

 if(image[x][y]==0)
{
g.setColor(Color.BLACK);
}else {
g.setColor(new Color(
Math.min(1, Math.max(0, ((image[x][y]/biggestfinalWeight) * 2.5f + 0.4f))),
Math.min(1, Math.max(0,(image[x][y]/biggestfinalWeight))),
 Math.min(1, Math.max(0, ((((image[x][y]))/biggestfinalWeight))*2f -0.5f))));
}

This colours the points inside the fractal on a scale from white->pink->orange->red (depending on the number of branches that converge) and the points outside as black.

Combining these gives accurate images of the fractal and increasing the max. iterations (max. depth) gives more accurate but slower-to-generate images.

The different colours therefore show how the different branches intersect and cut each other and how the red fringes of the fractal only converge on a few branches while the white centre converges for all the branches.

On the original 2D array you can run a simple edge detect to highlight the boundaries between the different branches.

We can then re-run the fractal generation using the conventional method (only taking the principle value, the simplest root) and overlay that incomplete fractal over our complete fractal to see how much of the fractal is cut out when not using all the branches.

I ran these algorithms over night to generate lots of fractals, here are just a few:

It can be seen that when the order contains a square root (2.5,3.5…17.5) the conventional method is missing half of the heads (because it only takes the positive square root).


What Next?

I will be extending the function to render the complete set of julia fractals of order 2.5 from (-2 to 2) on the complex plane. A julia fractal is similar to the multibrot, except instead of varying the constant c, the c stays completely constant and the starting point of z is changed instead. It may also be possible to plot the separate layers of the fractals (the separate branch-cuts) and render them in 3D to see how they intersect and overlay to give the true image of the fractal.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s