www.delorie.com/gnu/docs/xaos/xaos_33.html   search  
Buy GNU books!

An fast realtime interactive fractal zoomer

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

3.4.4 Calculating New Pixels

The above optimizations make XaoS very fast, but another 30% increase in speed is aquired by using a clever method for calculating the new pixels. Many methods are known for saving calculations during the generation of fractal images. The most powerful is boundary detection. It relies on the fact that the Mandelbrot Set is connected with lakes. You need only one pixel at the boundary, then traverse the whole set and then fill the solid area inside. This method saves many calculations but is too complex for adding just one line. Many claim that it does not introduce any errors, but this is not true. It is possible for a connected part of the lake to be so small that it is not visible in smaller resolutions. In this case, boundary detection misses the whole area. This algorithm is acutually used just for calculating of new images (i.e. at the startup).

XaoS uses modification of method known as solid guessing. The pixels at the boundaries of a rectangle are calculated. If they are all the same you may assume that this rectangle does not does not contain anything and fill it.

This algorithm is further modified to operate on added lines. For this it is at least as good as boundary detection and produces more tangible errors. When adding a single line, the upper and lower line may be examined for the nearest three pixels. If they are all the same then it is assumed that 9x9 pixels are the same. This disables all calculations inside solid areas and calculates as many points as boundary detection. The only possibility of creating a larger error with this method as opposed to boundary detection is in the instance that the shape of the set is so sharp that it does not set any of the tested points but comes from the right (i.e., uncalculated) location. This situation is not very common.

Later, rules were added for new rows and columns that crossed each other. In this instance you can test only four pixels. This situation is very rare. It is hoped that it does not introduce many errors.

If multiple blocks of new lines need to be calculated there are not reference pixels to use for solid guessing. Interlacing does the trick. By calculating the odd lines without any guessing, the guessing algorithm is now possible for the remaining uncalculated lines. This simple trick saves about 30% of the calculation of the main Mandelbrot image.

A similar approximation can also be done for the X coordinate. This makes it possible to improve solid guessing at even pixels because all surrounding pixels are available, further reducing errors.

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003