A Fractal Generator in C# for .Net 3.5
Fractals are interesting creatures. They are the visual representation of complex mathematical functions. Writing a fractal generator was something I always wanted to do, and recently found the time. My initial motivation was to discover if fractals were able to be generated using parallel processing, which they most certainly are, so I set off with a clear goal in mind: a multi-threaded fractal generator. This post is the result of that work.
I’ll start by linking to Snagy.Fractals.zip. This zip file contains 3 projects: a core fractal library, a console app, and a WPF app. The 2 apps use the fractal library to generate fractals in both single and multi-threaded scenarios.
One of the most common functions is the set of numbers defined by Benoit Mandelbrot in the Mandelbrot Set. This function relates to the concept of Complex Numbers and the plotting of co-ordinates on the Complex Plane. This particular branch of mathematics is complex and I’m not going to talk about it here (mostly because I still don’t know how it all works!). Suffice to say that the fractals generated from the Mandelbrot set are the most common and well documented. I selected the Mandelbrot algorithm for my fractal generator.
Before I started this work I thought it more worth while to use an existing generator if one was available. There were some, but one of the key problems I discovered was that they were badly written and difficult to understand. Having said that, some might find the same problems with mine, and if that is the case, please let me know!
Another problem I discovered was that some of these generators were written by mathematicians. This meant that the language and terminology used presumed an understanding of the maths (which I only have part of) and that made the code difficult to read. So my goal was to lose the jargon and stick to programming terms.
After spending some time on the mathematics, I followed some online guides to programming the fractal, as well as munging in some concepts from some example applications I found. Snagy.Fractals namespace is the end result, and here is an overview of the important classes within.
FractalSettings – Contains just properties representing the required settings for a fractal
MandelbrotBase – An abstract class that provides helpers for settings, timing, and pixel creation
MandelbrotSingleThreaded – A derived class that creates fractals in a single thread
MandelbrotMultiThreaded – A derived class that creates fractals in multiple threads
Fractory – A factory class for generating the derived class based on settings
ColourMap – Static class that creates arrays of colours used in the fractal
How It Works
This won’t be a math lecture so we’ll just cover some simple concepts. First, fractals are generated on a pixel by pixel basis. This makes them excellent candidates for parallelism: 2 pixels can be generated at the same time because there is no relationship between pixels.
The work we do is broken up into ‘Strips’. Imagine we want a fractal that is 900×900 pixels in size. We can break this up into 200×900 strips, with the 5th strip only being 100×900 pixels. These strips allow us to break our work up into logical units. These strips are what get distributed amongst multiple threads.
Think about a 900×900 fractal image again. If we just run the standard co-ordinates through the functions (x = 1 to 900, y = 1 to 900) then the Mandelbrot fractal is quite small (a couple pixels). This doesn’t let us see anything interesting! So we need to simulate “zoom”. To do this we take a scale modifier and multiple the numbers against that. The best top level zoom starts at scale 0.01. This means we are supplying the algorithm with the numbers x = 0.01 to 9.00 and y = 0.01 to 9.00. But the most amazing art occurs much deeper still!
Because Mandelbrot is based on quadratic equations (eg. y = ax^2 + bx + c ) then everything happens around the ‘Origin’. This means we need to introduce negative X and Y values, with the centre of our image being co-ordinate 0:0. To achieve this we need to offset calculations based on how big our image is (Height/2, Width/2) and also based on our zoom level. This moves the fractal to the centre of our screen (in this case, the centre of our bitmap that we are creating).
When we start zooming in, we don’t actually want to look at the exact centre of the image. If you look at pictures of Mandelbrot, you’ll see the very centre is empty! Nothing exciting happening there, so we actually need to zoom in at specific x/y locations. These locations have to take into account the offsets mentioned above, and of course the scale factor.
The colour of any pixel is decided by the number of iterations of the Mandelbrot function that can occur. What we mean by this is that the function : f(n) can be called on itself recursively “i” number of times while satisfying the core equation (see complex quadratic equations for details). So if the deepest we can go at a particular point is f(f(f(f(f(n))))) then this means we reached 5 iterations.
Forget the math though; the MandelbrotBase class will calculate the iteration for you based on the x/y co-ordinate. However this x/y co-ordinate is actually relative to the centre mentioned above, so is in fact quite a small number pair, rather than the actual X/Y of the bitmap we are calculating.
To Infinity – And Beyond!
If you zoom in on an ‘edge’ of a fractal, you will see that you can keep zooming.. forever and ever. Well this isn’t technically true: the app is hardcoded to 1000 iterations max, which means that there are defined edges between the fractal and space. But theoretically.. .there is no such edge!
All the fractal work is done in the class library, so its really very easy to consume and use in your own application. The console application is a perfect example of this. All the code in this app is around getting command line parameters and turning them into a FractalSettings instance, and then saving the resulting fractal image. Use this application as a guide to using the fractal classes.
This is a simple harness that will show you the fractal based on your settings on the left. Enter a scale and centre point, then click create.
I did attempt to put some navigation into it, but its very flaky. There is this tendency for UI events to “queue” while the fractal is being generated. As a result the experience is rather poor, but the framework is there if someone wants to work on it and make it work better.
This is open to anyone to use. Since its unusual to embed a fractal generator in a commercial app, I’m not too concerned about what you use it for. But if you do republish an app with my code, I’d appreciate a mention and a link through. =)
I have to thank Buddhike for his help around the threading. Bud helped me get the locking sorted along with the right threading classes. So thanks Bud! I’d also like to thank Paul Stovell for making me ditch my original Win Forms harness and use WPF instead, which resulted in more work to convert bitmaps, recreate my flashy UX, and fight against dispatchers.
The WPF navigation (pan and zoom) was based on this article on the topic.