Tag Archives: fractals

Mandelbrot explorer

This project estimates the Mandelbrot set using the HTML5 canvas. It’s one of my longest running projects that has been implemented in PHP, SVG, HTML5 canvas, HTML tables, and even in ROOT.

Links

Live page
GitHub repository

Overview

This projects presents a wide range of different challenges. The aim is to create a fractal browser that pushes the operating environment to the limit in terms of performance, while still being user friendly and responsive. In its current iteration the user clicks on the region of the fractal they wish to explore and the project zooms in to that region. The user can change the way the fractal is coloured by changing the palette its properties. They can also move from the Mandelbrot set to the corresponding Julia set. There is also the option to explore the cubic Mandelbrot set. Past iterations have included even more fractals, including Newton iterations and generalised Julia sets. However these have been removed in this iteration as they should be refactored into a separate fractal class rather than inserted by hand.

Challenges

Challenge: The algorithm must be responsive and make reasonable use of memory.
Solution: The iterations used in the algorithm can be expensive when the image approaches several hundred thousand pixels. Currently the algorithm uses a pixel object to manage the colour at a given point, and for arbitrarily large images a single pixel object is used in order to reduce the cost of creating and storing large numbers of these objects. The current iteration uses Javascript in the user’s browser, and most modern browsers deal with excessive memory usage sensibly, killing particularly bad cases. It is not desirable to cap a user’s capabulities when it comes to image size, so instead the algorithm forces the browser to fail relatively safely and without major inconvenience. Previously this project ran on PHP on a shared server, so memory use had to be monitored and was formally enforced on the server, making failure modes potentially dangerous. Once the canvas became available I switched to using it very quickly. Even so, running PHP locally overnight to generate very large images is still a sensible use of resounces. There are probably other areas where savings could be made. (Resolved, to be revisited)
Challenge: The algorithm must make reasonable use of CPU.
Solution: In many cases the fractals take several tens of thousands of iterations per pixel for several thousand pixels, leading to large CPU usage. In the context of Javascript this can cause serious performance issues for the user, affecting their whole computing experience and not just that associated with the browser session. To mitigate this the iterations are interrupted every \(100 ms\) and forced to wait for \(10 ms\) before continuing. In addition when several small canvases are populated they are pushed into a queue which is processed serially with interruptions. This reduces the impact on the user’s CPU significantly leading to much smoother performance and better response to user input. Even so, this should be revisited to make further savings and be more responsive to the user’s inputs. (Resolved, to be revisited)
Challenge: The user interface must be intuitive.
Solution: In some senses it will never be possible ot make the user interface entirely transparent, given the technical nature of the fractal’s inner workings. In spite of this the way the user navigates is relativelt straightforward, but more improvments can and should be made. (Resolved, to be revisited)
Challenge: The palettes should be easy to edit.
Solution: The asethetic properties of the fractals often depend on the choice of palette. The palette scales can be manipulated, using slders on the log scale. This solution borrows from another project being developed in parallel, and leads to an easier interpretation of the scaling and distorting of the palette scale. This method should be tested in a “focus group” style environment. The user should be able to create and store a palette from scratch with their own choice of colours stops. (Resolved, to be revisited)
Challenge: The user should be able to store fractals.
Solution: The user can currently choose to save a fractal to the server, storing the \((x,y)\) coordinates, zoom, and other factors. This uses AJAX requests with a PHP and MySQL backend, which has become fairly standard in my projects by now. This comes with the usual MySQL injection overheads and PHP safety issues. In the future, as the number of fractals in the gallery increases, the gallery should be orgainsed in some manner to reduce bandwidth and CPU usage. (Resolved, to be revisited)
Challenge: The project should support arbitrary fractals for future expansion.
Solution: At the moment the fractal algorithms are hard coded into the project. This needs to be more object oriented in the future so that other developers can contribute their own fractals. (Partially resolved, to be revisited)

Sample output

Mandelbrot explorer output
Mandelbrot explorer output

Apollonian gasket

One of my hobbies is creating fractals and one of the most interesting is the Apollonian gasket. An area defined by some arcs and straight lines is recursively filled with circles and in all cases (except the trivial case of a single circle) this process recurses infinitely, making counting circles challenging.

Links

Live page 1
Live page 2
GitHub repository

Overview

Circles and lines are defined in much the same way (with lines having an infinite radius, and vanishing inverse radius) and from this point lines will be referred to as circles. There is then a relatively straightforward relationship between the position of a circle and the three circles/lines which enclose it. For three circles \([c_1,c_2,c_3]\) that enclose a circle \(c_4\), the radii are related by:

\[
r_4 = \frac{r_1r_2r_3}{r_1r_2+r_2r_3+r_3r_1+2\sqrt{r_1r_2r_3(r_1+r_2+r_3)}}
\]

where \(r_i\) is the radius of the \(i\)th circle. The centres of the circles, \((x_i,y_i)\) for the \(i\)th circle, are related by:

\begin{eqnarray*}
A_{12} & = & x_1^2 – x_2^2 + y_1^2 – y_2^2 + (r_2+r_4)(r_2+r_4) – (r_1+r_4)(r_1+r_4) \\
A_{13} & = & x_1^2 – x_3^2 + y_1^2 – y_3^2 + (r_3+r_4)(r_3+r_4) – (r_1+r_4)(r_1+r_4) \\
B_{12} & = & 2(x_2-x_1) \\
B_{13} & = & 2(x_3-x_1) \\
C_{12} & = & 2(y_2-y_1) \\
C_{13} & = & 2(y_3-y_1) \\
x_4 & = & \frac{A_{12}C_{13}-A_{13}C_{12}}{B_{13}C_{12}-B_{12}C_{13}} \\
y_4 & = & -\frac{A_{12}B_{13}-A_{13}B_{12}}{B_{13}C_{12}-B_{12}C_{13}}
\end{eqnarray*}

Three circles used to create a new circle are known as a triplet. Each time a new circle is created from a triplet this introduces three new “holes” in which additional circles can be added. The three new triplets associated with these holes are then \([c_1,c_2,c_4],[c_2,c_3,c_4],[c_3,c_1,c_4]\).

Challenges

Challenge: The first challenge faced was to correctly reconstruct a new circle from a given triplet. There is a degenerate case where the centres of the circles in a triplet are collinear and none of the circles contains another circle. A degenerate collinear triplet can never emerge if the first triplet is not a degenerate collinear triplet.
Solution: The equations given above always find a new circle for a given triplet. Degenerate collinear triplets are ignored. (Resolved)
Challenge: As triplets are processed this introduces new triplets. These can lead to a few problems, including runaway memory and CPU usage, as well as the algorithm never completing one part of the gasket before moving on to another.
Solution: There is a limit on the number of circles that can be produced. There is a stack of triplets and new triplets are added to this. As triplets are processed, they get removed from the stack. In this way the gasket can be filled uniformly, removing triplets keeps memory usage low, and the limit on the number of circles stops the algorithms before CPU use becomes an issue. The result is an image where some areas may look sparsely populated. This algorithm should be revisited to make it more robust. (Resolved, to be revisited.)

Sample output

A initial triplet of circles:

Apollonian gasket version 1
Apollonian gasket version 1

An initial triplet of lines:

Apollonian gasket version 2
Apollonian gasket version 2