Download an exciting AlmondBread technology demo for DOS that gives you a preview of what speed you can expect from the upcoming AlmondBread 0.3 which will include support for Windows95/NT. Here's the README.
AlmondBread is a program for the X Window System that generates images of the Mandelbrot set. Here are some of its features:
.MAP
files).
News in version 0.22 include:
AlmondBread is known to work on Linux using XFree86, Solaris, and IRIX. It requires X11 and the aforementioned Tcl/Tk (at least version 7.4/4.0), plus the jstools-package by Jay Sekora.
View a screenshot of AlmondBread in
action, then download AlmondBread
(400k gzipped tar-file from Berlin, Germany).
Outside of Europe, you
might want to use the Canadian
mirror instead.
By popular demand, it is also available as a zip file.
The remainder of this page is an adapted version of the AlmondBread help file.
The Mandelbrot set - or M - was discovered in 1980 by mathematician Benoit B. Mandelbrot. It is considered to be the most complex object mathematics has ever seen [1].
In [2] M is defined as follows: "The Mandelbrot set is the set of all complex numbers c such that iterating z->z²+c does not go to infinity (starting with z=0)".
It can be shown that the sequence diverges if the magnitude of z exceeds 2.
N is the maximum number of iterations you allow (smaller values mean faster execution, larger ones better accuracy). If the iteration loop terminates because n>=N, there is a good chance c lies in M, so you can color p accordingly. If, however, |z|>=2 then p lies outside of M and you can color p according to the number of iterations when z "bailed out", i.e. according to n.
scan.c
that comes with AlmondBread.
The idea is the following: For each i consecutive pixels, compute only one. If its color matches that of the previous computed pixel, assume all i are of same color and go on. If not, go back one pixel at a time until it matches the "saved" color (plotting each of those different colored pixels along the way, of course). Now, plot the whole line of unique color defined by the first point of "saved" color and the last.
Obviously, this is very fast for images containing
large areas of a single color, but may err in images with fine
filaments extending through areas of few colors. Thus, it follows the
same policy as Fractint's solid-guessing logic. Its complexity is
O(c·n²), with 1/i<=c<=1. For further details, check out
interleave.c
.
It makes use of the Mandelbrot set's connectedness property, which has as a consequence that there cannot be a region of one color inside a rectangle of another color, i.e. once you find that the sides of a rectangular region are of a single color, it is safe to assume the whole rectangle to be of said color (with some margin of error, of course, since strictly speaking one pixel defines a region, not just one point). The procedure used to generate the image is this:
There are some details I think are worth elaborating on. First,
AlmondBread's algorithm subdivides at least once to avoid "blitting"
in the initial image. Secondly, it skips computing those edges of the
image that were already done in the previous stage (which is either 3
or all 4 using the "DIN" approach). Thirdly, AlmondBread uses the
"DIN" approach to subdividing the image (I call it that because of the
way paper sizes in the DIN system are related, e.g. DIN A5 is half the
size of DIN A4), which is also known as hv-splitting. This means
simply that subdividing in horizontal or
vertical direction is done in alternating fashion, which has proven to
be very efficient over other methods like 4-way splitting. The
complexity of the Tesseral algorithm is in O(n·log(n)). The code can
be found in tesseral.c
.
We scan the whole screen pixel by pixel, keeping an offscreen map of iteration values for each pixel (initially set to all -1s to signal "not done"). If we hit a pixel not done, we start tracing its border going right and keeping the "wall" to our left until we get back to the starting point. For each pixel, the next pixel visited will be computed thus:
When we're back at the starting point we trace the boundary once more. Now, whenever we move up, we plot pixels to the right of the current one until we hit the wall.
This method was inspired by a post on sci.fractals by Maarten Egmond (cp@stack.urc.tue.nl).
The complexity of the
Boundary Tracing algorithm is in O(n2). The code can be
found in
boundary.c
.
As you may recall from section The Mandelbrot Set, calculating M involves an iterative process, which means on successive iterations one point is mapped onto another one. Now, if we look at not only one point but a whole set of points, say a rectangle, these points get mapped onto a different set of points in the complex plane. If this (iterated) set of points is still a rectangle, we can make the reasonable assumption that in order to obtain the iterated value for a point inside the original rectangle all we have to do is a linear interpolation, i.e. determine where the point in the original rectangle would be in the new, iterated rectangle if we had merely "resized" it and moved it to the new location (which in effect is what we have done by iterating). To put it in other words, if point x is in the middle of the rectangle before iterating it will be in the middle of the iterated rectangle also.
The problem is that for a given rectangle the iterated point set is very rarely a perfect rectangle. The approach used by AlmondBread involves a polynomial interpolation of 2nd degree (using Newton interpolation). For every rectangle we have 9 key points plus four test points. All points are iterated and the test points are interpolated. If the ratio of iterated to interpolated test points is greater than an allowed margin, we subdivide, proceeding in a fashion similar to the Tesseral algorithm (using a 4-way split, though). Otherwise, we do the iterating and interpolating over until we have to split or maxiter is reached, in which case we simply fill the rectangle and exit. This may sound trivial at first, but the whole interpolating stuff can get pretty confusing after a while, particularly when you have to interpolate certain points and don't know which key points to use (just take a look at the subdividing part in the code), but this is mainly due to my quick'n'dirty implementation tactics.
SOI does a very good job on images that have a high number of average iterations, typically very deep zooms that take a long time using other algorithms such as Interleave. The following image is a very deep zoom that took over 2 hours using Fractint under DOS on a 486DX-33. It took about 4 minutes using AlmondBread under Linux on the same machine.
Load the image into Fractint and check out yourself how long this image takes to calculate (Download the Parameter file if you just want to calculate the image).
SOI does not do as good a job on low-magnification images, because unlike Interleave, for example, SOI has a large organizational overhead. There are a few tricks, however, which can make SOI as fast or even faster on low-magnificaction images. The main problem with low-magnification images is that the number of simultaneous iterations is very small and you have to subdivide after very few iterations. Therefore, AlmondBread has a minprogress variable, which controls the minimum number of iterations required to allow subdividing. If this number is not reached, Interleave scanning is employed.
A word of warning is necessary at this
point. The SOI in AlmondBread is far from perfect. With certain images
you may notice severe distortions caused by a failure of the tolerance
code. You can then lower the value of the variable
tolerance (possibly
from 0.1 to 0.05). Of course, this is not acceptable, but up till now,
I have not found a fool-proof way of detecting distortion (I would
greatly appreciate any input you might have on this or any other
aspect of SOI. Plus, let me know if you have implemented SOI or a
similar method yourself). The complexity of SOI cannot be easily
compared to previous methods, since it does not depend on the side
length of the image. The code for SOI can be found in soi.c
.
conventional.h
.
optimized.h
.
do
{
im=(im+im)*re+cim;
re=rq-iq+cre;
rq=re*re;
iq=im*im;
/* maybe some periodicity checking here */
} while (i++<=maxiter && rq+iq<bailout);
As you can see, this process involves 3 floating point multiplies. We
would be able to eliminate one of them if we didn't have to check for
bailout on each iteration. And that's exactly what we do: We unroll
the loop and check for the bound only every n-th time.
do
{
/* do this n times */
i1 = (im+im)*re+cim;
r1 = (re+im)*(re-im)+cre;
/* now check the bound once */
rq = rn*rn;
iq = in*in;
if(rq+iq>bailout) { /* determine correct iter and return */ }
i+=n;
} while (i<maxiter);
In addition to saving one multiplication (which in fact isn't such a big savings on modern processors such as the Pentium) the comparison and looping overhead can be avoided. This turns out to be an even greater advantage, especially for Intel processors where floating point comparisons are very costly.
There are a couple of problems, though. First of all, we are running the risk of doing too many iterations if we don't check the bound each time, but if maxiter is large compared to the number of unrolled iterations the time-savings outweigh the overhead.
Secondly, the magnitude of z can get very large after it surpasses bailout, generating a floating-point exception. Therefore, AlmondBread unrolls only to a depth of eight, which seems to be safe for IEEE 754 doubles.
Thirdly, it has to be determined when exactly the
bailout value was exceeded in order to color the corresponding pixel
correctly. Nick Haines (nickh@cmu.edu) suggested doing an "exponent
correction hack", which uses the exponent of the magnitude of
z to determine the correct iteration number. It is based on the
observation that after |z| surpasses
bailout, its exponent is doubled on each consecutive iteration. However,
this works only for
bailout values larger than 4.
The code is in
unroll.h
.
pot:=maxcolor-slope*log(|zn|)/2n
,
where maxcolor
is the maximum value for pot
. The variable
slope
affects
the width of the color bands. zn is the value of z
at the end of iteration, i.e. the value it holds when bailout is
reached, after n iterations. Values less than 1 are "truncated" to
1.
angle:=(atan2(i,r)/(2*pi)+0.5)*arity
.
This will yield a value in the range 0-arity
.
The arity
parameter determines how many
segments the circle of possible angle values is divided into, i.e. if
arity
is 2, p will be colored according to whether the
imaginary part
of zn is positive or negative. Again, try [1] or [3] for an
in-depth
explanation. arity
256 and a nicely shaded colormap gives beautiful pictures.