How would you continuously improve the mandelbrot fractal?

Question

I've seen many mandelbrot image generator drawing a low resolution fractal of the mandelbrot and then continuously improve the fractal. Is this a tiling algorithm? Here is an example: http://neave.com/fractal/

Update: I've found this about recursively subdivide and calculate the mandelbrot: http://www.metabit.org/~rfigura/figura-fractal/math.html. Maybe it's possible to use a kd-tree to subdivide the image?

Update 2: http://randomascii.wordpress.com/2011/08/13/faster-fractals-through-algebra/ Update 3: http://www.fractalforums.com/programming/mandelbrot-exterior-optimization/15/

Answer 1

I think that site is not as clever as you give it credit for. I think what happens on a zoom is this:

• Take the previous image, scale it up using a standard interpolation method. This gives you the 'blurry' zoomed in image. Click the zoom in button several times to see this best
• Then, in concentric circles starting from the central point, recalculate squares of the image in full resolution for the new zoom level. This 'sharpens' the image progressively from the centre outwards. Because you're probably looking at the centre, you see the improvement straight away.

You can more clearly see what it's doing by zooming far in, then dragging the image in a diagonal direction, so that almost all the screen is undrawn. When you release the drag, you will see the image rendered progressively in squares, in concentric circles from the new centre.

I haven't checked, but I don't think it's doing anything clever to treat in-set points differently - it's just that because an entirely-in-set square will be black both before and after rerendering, you can't see a difference.

Answer 2

Author of Fractal eXtreme and the randomascii blog post linked in the question here.

Fractal eXtreme does a few things to give a gradually improving fractal image:

1. Start from the middle, not from the top. This is a trivial change that many early fractal programs ignored. The center should be the area the user cares the most about. This can either be starting with a center line, or spiraling out. Spiraling out has more overhead so I only use it on computationally intense images.
2. Do an initial low-res pass with 8x8 blocks (calculating one pixel out of 64). This gives a coarse initial view that is gradually refined at 4x4, 2x2, then 1x1 resolutions. Note that each pass does three times as many pixels as all previous passes -- don't recalculate the original points. Subsequent passes also start at the center, because that is more important.
3. A multi-pass method lends itself well to guessing. If four pixels in two rows have the same value then the pixels in-between probably have the same value, so don't calculate them. This works extremely well on some images. A cleanup pass at the end to look for pixels that were miscalculated is necessary and usually finds a few errors, but I've never seen visible errors after the cleanup pass, and this can give a 10x+ speedup. This feature can be disabled. The success of this feature (guess percentage) can be viewed in the status window.
4. When zooming in (double-click to double the magnification) the previously calculated pixels can be used as a starting point so that only three quarters of the pixels need calculating. This doesn't work when the required precision increases but these discontinuities are rare.

More sophisticated algorithms are definitely possible. Curve following, for instances.

Having fast math also helps. The high-precision routines in FX are fully unwound assembly language (generated by C# code) that uses 64-bit multiplies.

FX also has a couple of checks for points within the two biggest bulbs, to avoid calculating them at all. It also watches for cycles in calculations -- if the exact same point shows up then the calculations will repeat.

To see this in action visit http://www.cygnus-software.com/

Answer 3

The oldschool Mandelbrot rendering algorithm is the one that begins calculating pixels at the top-left position, goes right until it reaches the end of the screen then moves to the beginning of next line, like an ordinary typewriter machine (visually).

The linked algorithm is just calculating pixels in a different order, and when it calculates one, it quickly makes assumption about certain neighboring pixels and later goes back to properly redraw them. That's when you see improvement, think of it as displaying a progressive JPEG. If you zoom into the set, certain pixel values will remain the same (they don't need to be recalculated) the interim pixels will be guessed, quickly drawn and later recalculated.

A continuously improving Mandelbrot is just for your eyes, it will never finish earlier than a properly calculating per-pixel algorithm which can detect "islands".