XaoS - Hubička Algorithm

Hubička Algorithm

XaoS was originally just a "poorly written" Mandelbrot viewer until Jan Hubička added efficient zooming, using a technique sometimes called the XaoS algorithm or Hubička algorithm.

At the time fractal zoom movies were produced by completely recalculating each frame, even though they naturally had much of their area in common with each other. This made interactive zooming impossible without very powerful computers. Furthermore, unless even more processing is used in order to do antialiasing, recalculating every frame produces a 'twinkle' effect as small bright areas hit and then disappear between pixels.

Yet allowing the user to zoom, rather than jump as in Fractint, seemed like the most natural way to interact with fractals. In order to create an interactive zoom, Hubička needed to find a way to save the calculations which were already made. It would take up too much memory to save every pixel ever calculated, so the Hubička algorithm only saves the previous frame, and rather than remembering the location of each pixel it can keep them aligned in rows and columns and remember those instead.

The most difficult part of the XaoS algorithm was choosing which saved rows and columns to draw where. Doing this wrong results in distorted images, yet it must be done quickly to be useful. After several different heuristics were tried, eventually the problem was treated as an optimization problem.

The remaining rows and columns are colored in the same as the closest row/column, and are freshly calculated as the CPU gets time to do so. This is a careful balance between keeping the zoom going and increasing the level of detail. Calculating areas where the image is being zoomed to is put at a higher priority since these will be on the screen the longest and this is likely where the user is looking anyway. Zooming out, the reverse occurs and the priority is on the edges.

The Hubička algorithm can also be applied to zooming in on other images where the pixels are calculated, and has been used in other software such as the rtzme complex function graphing program, and other fractal zoomers.

Read more about this topic:  XaoS