Improved Method for Generating Fractal Images
Timothy D. Greer

"Senile Depth First Search applied to Iterated Function Systems" is a relatively fast and efficient method of rendering fractals using their iterated function system definition. Because it is guaranteed to terminate, it is highly desirable for use in applications involving automation. (See for example "Auto-Generating Fractal Movie".) But it is known to deliver sparse renderings in some cases. For example [Rendering by original SDFS]

Compare with the output of the random iteration method [Rendering of same fractal by random iteration]

and that of this disclosure [Rendering by augmented SDFS] A competing method, the random iteration method can also be shown to suffer this problem. For example [Another fractal by random iteration]

Compare this with the same fractal rendered by the method about to be described. [2nd fractal rendered by augmented SDFS] The improved method given, retaining essential elements required for guaranteed termination, substantially eliminates this problem. This is done by following up Senile Depth First Search with limited random searches. Each random search terminates as soon as it encounters an unmarked pixel, where SDFS is restarted. This process is repeated until the random search finds no unmarked pixel within the iteration limit.

Another method to attempt to fix sparse-rendering problem of SDFS is to run the same algorithm using higher resolution, and then decrease the resolution. While this helps slightly, experiments using 2x resolution (4x number of pixels) demonstrate that this method fails. Results for the first fractal shown above, for example, were visually indistinguishable from the original sparsely-rendered version.

This display method combines Senile Depth First Search (SDFS) with limited random iteration. The improved method given, retaining essential elements required to guarantee termination, has been found experimentally to run almost as fast as SDFS. A reason to expect this will be offered later.

First, SDFS is run as described in the reference. SDFS colors pixels known to be on the fractal. When SDFS terminates, a random iteration is initiated for some fixed number of steps N, e.g. 10000. If the random iteration makes it through all N steps without encountering an unmarked pixel, the entire algorithm terminates. If the random iteration encounters an unmarked pixel, random iteration terminates, the pixel is colored appropriately, and SDFS is started from that pixel. When SDFS then terminates, the algorithm returns to the random iteration step.

Because there are a finite number of pixels, this algorithm must terminate. In practice, if SDFS has produced a sparse image, then random iteration generally hits an unmarked pixel within a few steps (e.g. < 100), so that the algorithm quickly returns to SDFS. Given the fresh starting point, SDFS fills in all paths (up to its senility limit) from this previously unmarked pixel, and so is able to fill in most or all of the remaining pixels needed to properly render the fractal. So it is likely that there will be only a few such hand-offs between the two methods before there are no more unmarked pixels to find. Note that none of these methods is guaranteed to correctly light all the pixels that would appropriately render the fractal image, but as long as the fraction missed is tiny, such error will not be noticeable.

Related Articles

A modified version of this article is also available.


The information provided, and views expressed on this site are my own and do not represent the IBM Corporation.



 

Return to the author's home page.