An fast realtime interactive fractal zoomer
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:
- Make approximations for rows
- Make approximations for columns
- Move old pixels to their new positions
- Calculate pixels for which there is no good approximation for
their row
- Calculate pixels for which ther is not good approcimation for
their column but there is one for their row
