Browse Prior Art Database

Senile Depth First Search Applied to Iterated Function Systems

IP.com Disclosure Number: IPCOM000107131D
Original Publication Date: 1992-Jan-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 3 page(s) / 88K

Publishing Venue

IBM

Related People

Greer, TD: AUTHOR

Abstract

Disclosed is a deterministic, terminating method to mark the points in a quantized space, such as an array of pixels, according to whether or not a given iterated function system "hits" each quantized region. The method is based on depth first search, but avoids unproductive exploring of many branches by acting senile -- the algorithm forgets upper portions of the search tree. One use is to speed up the display of images of fractals, and to eliminate the need for stochastic algorithms.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Senile Depth First Search Applied to Iterated Function Systems

       Disclosed is a deterministic, terminating method to mark
the points in a quantized space, such as an array of pixels,
according to whether or not a given iterated function system "hits"
each quantized region.  The method is based on depth first search,
but avoids unproductive exploring of many branches by acting senile
-- the algorithm forgets upper portions of the search tree.  One use
is to speed up the display of images of fractals, and to eliminate
the need for stochastic algorithms.

      This description refers to (X, Y) coordinates as if the
iterated function system is a subset of the two-dimensional plane.
This is for convenience and clarity only.  The system can be a subset
of higher dimensions as well, or one-dimensional too.  Likewise,
"plotting" a point here may be taken to mean marking the memory
location (X,Y, Z,...).  Marking a two-dimensional memory location is
equivalent to lighting a pixel on a digital display.

      In the flowchart, the current and previous values of the
coordinates for plotting are kept in the arrays X(*) and Y(*).  The
function used to get from one (X,Y) pair to the next is identified by
the array MAP(*).  The function "Plot (X,Y)" marks a pixel.  X and Y
are floating point numbers, whereas the Plot function can plot only
integer values, so the values of X and Y are rounded to the nearest
integer within the plotting routine.  Likewise, rounding occurs when
checking to see if a point has already been plotted.

      The flowchart acts as an ordinary depth first search, except
that after the depth of MAX + 1 is reached, the oldest points begin
to be written over.  The amount of overwriting is unlimited.  Since
each...