Introduction
In this article, I'm going to be showing the result of the work of approximately 2 months. I set out with an interest in fractals, and finished with a program capable of generating the Mandelbrot set in around 2 seconds. This project has greatly helped me in learning to code, especially in optimization and efficiency.
Background
Firstly, we need to use complex numbers, Z, each of which has a "real" and "imaginary" part. This can be written as
Z = x + i * y
where x is the real part and y is the imaginary part. The i corresponds to the “i” in imaginary.
Since complex numbers have two parts (x, y) we can plot them on an x-y graph. In our case we are going to plot them on an image. Each row of pixels corresponds to a set of complex numbers, Z, that all have the same y value and every increment in x-pixel represents a step in the x value.
Now, we are going to calculate the set over some range of x, y values. A pixel will then be assigned to each x, y coordinate, for example x = 0.3, y = 0.2. The colour of this pixel will be calculated using the Mandelbrot equation.
The equation is:
c is the coordinate at which a given pixel will be drawn, with coordinate c = x + i * y.
n is an iteration number, we start at n = 0 and also with Z0=0+i0. So at n = 0,
Zn+1 = Z1 = Z02+c = c. So Z1 = c.
Now we can put this Z value into the equation to get Z2. At n = 1,
Zn+1 = Z2= Z12+c
We keep on iterating like this, generating Zn+1 at each iteration. But when should we stop iterating?
Every time we get a new Zn+1 value we also calculate something called the complex modulus, which is written:
| Zn+1 |
and it is calculated using Pythagoras’ Theorem for the length of the hypotenuse of a triangle:
| Zn+1 | = √(x2 + y2)
Mandelbrot tells us to stop iterating if | Zn+1 | is ≤ 2, otherwise keep iterating.
We count the number of iterations, n, that are done before the equation converges (stop iterating). The n value is used to represent the colour of our pixel at c = x + i * y.
There are some parts of the set where n appears to be infinite, or at least it becomes so large that it is impossible to keep iterating. We set a maximum number of iterations, nMax and always stop iterating if n reaches nMax.
It turns out that nMax is quite important! A large nMax takes longer to calculate, but can show very fine detail close to the boundary between the places where the Mandelbrot equation converges (colourful parts) and diverges (white). However a low nMax can also produce nice images since the colour scale can work well.
Please note: in the program, k is used as the iteration count and kMax is used for the maximum number of iterations.
Features
I decided it would be better for my program to be able to do more than just generate the main Mandelbrot set, so it has some other features.
I added a zoom feature in which you can set how much you want to zoom in by, click the mouse and it renders the new image. Of course, the further you zoom in, the more iterations you need in order to support the high detail.
You are able to save an area of the Mandelbrot set in the "Favourites" feature. This saves all the parameters of your image to a text file which can be read from in order to load the favourite.
Each time a new image is rendered, it saves the parameters used to create the image to a text file. In this way, you can use the "Undo" feature to go back through your images.
Apart from a timer to show how long the last render took, I thought the ability to save your images would be a nice feature to have. The images are saved as PNG's and you can choose a file name for it.
All of the files saved to are stored at C:\Users\%username%\mandelbrot_config.
Using the code
The program is a Windows Form application. It can be launched from within the Micrsoft Visual Studio environment. Alternatively the executable can be run as a normal Windows application.
The user interface is self-explanatory with controls allowing the range of x, y coordinates to plot, the maximum allowed number of iterations, resolution (pixel step size) and zoom controls. Additionally there are other controls which are mentioned in the "Features" section of this article.
There are four C# classes, which are used as follows:
ComplexPoint.cs
Used to encapsulate a single complex point (Z = x + i * y), where x and y are the real and imaginary parts respectively. A number of complex arithmetic functions are included in the class to carry out the maths behind the Mandelbrot equation.
ScreenPixelManage.cs
Handles the conversions between mathematical and physical screen coordinates (pixel coordinates). The underlying mathematical coordinates are independent of screen resolution and size, whereas pixel coordinates are applicable to run-time screen dimensions.
Prompt.cs
Custom prompt, which in this case, is used for the user to input the name of their new favourite (see "Features")
Mandelbrot.cs
This is the main class in the project and extends the .NET Form class. It is used to render the Mandelbrot set, with controls allowing the user to modify the section of the Mandelbrot set to plot, pixel step (resolution), and a few other things which are mentioned in the "Features" sections of this article.
The main block of code used for drawing the Mandelbrot set can be seen below:
for (double y = yMin; y < yMax; y += xyStep.y) {
int xPix = 0;
for (double x = xMin; x < xMax; x += xyStep.x) {
ComplexPoint c = new ComplexPoint(x, y);
ComplexPoint zk = new ComplexPoint(0, 0);
int k = 0;
do {
zk = zk.doCmplxSqPlusConst(c);
modulusSquared = zk.doMoulusSq();
k++;
} while ((modulusSquared <= 4.0) && (k < kMax));
if (k < kMax) {
if (k == kLast) {
color = colorLast;
} else {
color = colourTable.GetColour(k);
colorLast = color;
}
if (xyPixelStep == 1) {
if ((xPix < myBitmap.Width) && (yPix >= 0)) {
myBitmap.SetPixel(xPix, yPix, color);
}
} else {
for (int pX = 0; pX < xyPixelStep; pX++) {
for (int pY = 0; pY < xyPixelStep; pY++) {
if (((xPix + pX) < myBitmap.Width) && ((yPix - pY) >= 0)) {
myBitmap.SetPixel(xPix + pX, yPix - pY, color);
}
}
}
}
}
xPix += xyPixelStep;
}
yPix -= xyPixelStep;
}
The final if...else... statement is used to deal with resolutions. If the pixel step is greater than 1, the resolution will be decreased so that there is no white space when the final image is drawn. If the pixel step is 1 then the image will be drawn as normal, i.e. at the highest resolution possible.
Notice that the y pixel count is decremented in the loop above, whilst x is incremented. This is because the origin of the drawing area (x, y = 0, 0) is at the top left of the screen. We want to draw the image starting at lower left and working towards upper right. This means that y starts at its maximum value.
Points of Interest
Performance Optimisation
As mentioned in the introduction, I learnt how to optimise code. Prior to writing this article, rendering the Mandelbrot set with my program would take you quite a long time: 10 minutes. The version I have uploaded here does it in around 2 seconds (AMD A8), and a fast PC can do it in just under 1 second (AMD FX-8350).
A key performance improvement came from the way the image is rendered. In the first version of this program, I used the System.Drawing with each pixel in the Mandelbrot set being draw as an ellipse. This was very CPU intensive. Additionally, when drawing at high resolution (small pixel steps) each ellipse drawn using System.Drawing was overlapping adjacent pixels, resulting in a slightly blurred image. The version of the program uploaded here uses instead a bitmap which overcomes these problems and also allows the image to be retained when the form is hidden or minimised.
Colour Map
The colour map is used to translate our iteration values, n, into pixel colours. A lot of people have invested time in working on different colour maps, mostly using some type of lookup table and often also using some type of interpolation algorithm.
My solution is very simple but also very effective - the resulting images, in my opinion, are as good as any. It works like this:
for iterationCountN, calculate:
hue = (n/nMax)α
Where α is a small number, currently set at 0.2. The hue is easily converted to a standard RGB using fixed values for saturation (s) and lightness (l), i.e. we convert:
n → hsl colour → rgb colour.
Realtime calculation of (n/nMax)α would be very CPU-intensive, so I generate a lookup table of RGB colours when the Mandelbrot calculation begins.
File I/O
I also learnt to do file I/O, which could be useful for other projects in the future. As mentioned in the features, I used file I/O to save the parameters used to draw the images in a text file. This text file was also used to be read from in order to retrieve those parameters.
References
Mandelbrot set on Wikipedia
HSL and RGB colours explained
Easy introduction to complex numbers
