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

An fast realtime interactive fractal zoomer

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

3.4.1 Saving Previous Pixels

Ideally, all precalculated points should be saved and used for building successive frames. I could not figure out a practical way to implement this. To save all frames for half an hour would require 24 Mb of memory, and searching the saved frames would be more computationally expensive than recalculating an entirely new frame.

One way was later used by program Frang. It remembers all pixels as x,y and value fields and when it builds new image, it draws all pixels to it and then browses image and fills it by new pixels. Possibly some rle cache should be used for calculated pixels. Frang actually uses algorithm, that takes away pixels out of screen, so it behaves exactly in same way as algorihm described here. At the other hand, this method seems to require much more memory than XaoS algorithm and drawing pixels/browsing image cost quite a lot, so algorithm descibed here seems to be faster. Since it never requires examining of whole image and new image is constructed using block move operations.

For this reason only the last generated frame is used as reference. This way the memory requirements are proportional to xsize * ysize. It can be shown that this method is only about 2-5% slower during zooming. Of course unzooming back to once browsed areas is much slower. Because only the previous frame is used, another optimization can be performed: Imaginary and real parts of the calculated image are not precise since they are the result of successive iterations of same algorithm. In order to prevent errors from being distributed to the following frames their exact coordinates need to be known. Fortunately, it isn't neccassary to save their values since it is known that all real components in a row and all imaginary components in a column are equal. Thus, the only things that must be saved are the real components for every row and the imaginary components for every column. This allows for a substantial speed-up in approximation because the calculation requires less data. Of course, some rows and columns fall out of the threshold and new ones need to be calculate to fill in the gaps in the frame. Obviously, much less work is done. There are only xsize + ysize calculations instead of xsize * ysize. So the main loop in XaoS looks like this:

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

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