## Tracing a fractal outline

Improvements to and a release of my simple fractal program.

I’ve been working on the Mandelbrot fractal program that I made in April.  At the time it drew the fractal by allocating every n‘th pixel to a separate thread.  I’ve added a drawing mode that instead traces the outline of the fractal:

The algorithm is pretty simple.  A priority queue of waiting pixel coordinates is kept.  The drawing mode will pop the best (x, y) pair off this, draw that pixel, and push its neighbouring coordinates on the queue with a priority determined from the value of the recently drawn pixel.  The queue is seeded by a number of random pixel coordinates, and the algorithm finishes when all pixels are drawn.

Pixel priorities correspond to the number of iterations the pixel takes before escaping from the set; the closer an outside pixel is to the set, the better its score.  The effect is that, starting from a random point, the algorithm will quickly draw its way to the edge of the set (essentially by hill climbing).  It will then trace along the edge of the set, then gradually extend that edge outwards.

A performance enhancement is to break the algorithm into several states:

1. SEEDING – We’re still processing seed pixels and waiting to find one with a non-zero value (usually very short unless you zoomed on a big empty black bit!).
2. TRACING – We’re processing interesting pixels (though we’ve possibly completed the edge and are now filling in the outside).
3. EDGING – We’ve run out of interesting pixels.  Now we process any remaining edge pixels.  The Mandelbrot is connected, which means all interesting areas (i.e. outside the set) in the drawing will either be in one contiguous piece, or along the edge.
4. FILLING – We’re pretty sure we’ve done all the interesting pixels, and will assume everything left is in the set and can be painted black (which is much quicker than actually testing each remaining pixel).
5. WAITING – We’ve painted the whole picture.  (And we should stop hogging the CPU.)

There’s a couple of bugs.  Pixel priorities are randomised a bit (to make the drawing process more artistic).  Sometimes, low value but non-black pixels are miscoloured because the EDGING process begins while these marginally interesting pixels remain.  It’s only a problem when a zoomed-out drawing is done.

There is also an unexpected artefact!  When FILLING, the algorithm will paint the remaining area down in segments.  The way that subpixels are averaged into pixels means a bright line can be seen between the painted and unpainted bits.  It can be mesmerising:

It still uses SDL and OpenMP (though the parallel mode is currently disabled).  I’ve ported it to Linux, too.  The code to the program can be found at http://code.google.com/p/ejrh/source/browse/trunk/fractal/.  I’ve also tried packaging the binaries for Windows but it may or may not work.

Controls:

• Left click to zoom in (zoom factor is 2).
• Right click to zoom out.
• F12 to save a screenshot (as a BMP file).
• 1 to toggle depth (between 256 and 65536).
• ESC to “make like an exterior point” and escape.

As is traditional, I’ll end with a few hypothetical next steps.

Fix the colouring!  Pixels have values between 0 and MAX_ITERATIONS; colours are mapped monotonically from pixel values to a curve in RGB space (AKA a palette).  Lacking artistic talent, I’ve arbitrarily picked a reddish-whitish curve (for hi-depth mode).  And lacking mathematical ability, I’ve arbitrarily picked a mapping functions based on the square root and logarithm of the pixel value.

The thing is that high value pixels are much rarer than low value ones, and there’s no point wasting 90% of the palette on 10% of the pixels.  My plan is to assign colour in equal quantities.  Say we have 100 colours we can assign.  Sort the pixel values, then assign a colour to each percentile of the results.  This mapping depends on the particular area drawn; it could be updated several times during drawing as the pixel values are calculated.

Another idea is to have a few options for adjusting the colours.  This could consist of predefined palettes, or a mechanism for defining the curve.  The other aspect is a function for mapping values onto that curve.

It could be made into a screensaver — and CPU waster — if it had a method of automatically picking a point to zoom in on.  This is fairly easy: just pick the highest value point seen.

Commands for changing the window size and switch to the parallel drawing mode could help.  There are other drawing modes that could be implemented, too.  (And maybe the tracing mode could be made multithreaded.)

Finally, I still need to track down that part of it where I got those awesome wallpapers a long time ago…