DEM/M
DEM/M =Distance Estimation Method for Mandelbrot set = Milnor algorithm
Idea:
In typical algorithms coordinate of pixel ( integer value = screen coordinate) is matched with one value of world coordinate ( real number),
but between 2 real values there are infinitely many other real values.
If narrow part of M-set ( dendrit or filaments) is between 2 values it is a little chance that it would be drawn by such typical algorithm.
So we can :
- check more real values in one pixel ( subpixel rendering )
- check what is the distance from that point to M-set ( it is DEM/M )
Programers point of view:
This algorithm is based on escape time algorithm:
Each pixel ( c ) is iterated ( Z0:=0 ) to compute Zn, DZn ( first derivative with respect to c) and last iteration.
If point is not in madelbrot set ( LastIteration < iterationMax) then compute distance from that point to M-set.
Distance = F ( Zn, DZn)
if distance< distanceMax then draw a pixel ( = border of M-set).
Theory:
the approximate distance between the point c and the nearest point in the Mandelbrot set
distance = 2 * |Zn| * log|Zn| / |dZn|
where:
Zn = F(n)(Z0) (complex number)
dZn is first derivative of the Mandelbrot map with respect to c ( complex number)
|Zn| = magnitude(Zn)
format of floating point numbers = extended
iterationMax:=1000;
excape_Radius:=2
distanceMax:= exp(-9)/100000
This image is made with delphi program, which is translation ( with modification) of Mandelbrot Dazibao program in QBasic
It is slow program, but works.
It draws only border of M-set.
It means points for which:
- iteration< IterationMax
- and distance < DistanceMax.
This image was drawn with MSExplorer
How to compute DistanceMax ?
This value is obtained empirically and is different than in Mandelbrot Dazibao program.
probably because of used type of floating point numbers( I use extended ).
DistanceMax is proportional to width of "border" of M-set;
distanceMax:= ePixelSize;
where ePixelSize:= (eCxMax-eCxMin)/(iXmax-iXmin);
This procedure is time consuming, because more computations in main loop ( derivatives).
What can we do to make it faster?
- 15 270 msec = initial procedure: 800x800 pixels using pixel property and extended type, iterationMax:integer=1000; BailOut2:double=4
- 7 649 msc = initial procedure with double numbers ( !!!!) extended numbers (4 bytes) are 2 times bigger then double ( 2 bytes)
- 7 700 msec = initial procedure with mirror symmetry.
If Cy=0 is in the middle then one can draw 2 times shorter then without symmetry.
Here is Delphi program using mirror symmetry.
- 2 310 msec = change acces to pixels from pixel property to ScanLine and cardioid checking without mirror symmetry
- 1 160 msec = change extended type to double type and iteration as procedure
- 978 msec = change extended type to double type and iteration as set of instructions
- 557 msec = ScanLine, mirror symmetry, cadioid checking, double numbers, iteration procedure
Is it worth trying ?
30 times faster !!!
There are a few versions/modifications of this algorithm:
- I use the simplified version of Mandelbrot Dazibao
For every pixel "c" one computes a distance
If distance < DistanceMax then Draw Pixel.
It draws only border of M-set.
You should clear the bitmap before drawing, because in my implementation of this algorithm only border points of are changed ( color) so previeous drawing may hide next image.
- Mandelbrot Dazibao version
- Peitgen version from page 196 of "The science of fractal images"
It is the most complicated version
For every pixel "c" one computes a label l(c) from {-1, 0, +1, 2}.
label=0 means that point is in M-set
Abs(label)=1 means that point is close to M-set
label=2 means that point is far from M-set
- Peitgen version from page 198 of The science of fractal images
R Munafo version is translation of this version.
- Evgeny Demidov version
where one can draw not only border of M-set but also colour the complement of M-set.
color is proportional to logarithm of distance.
In my implementation : Abs(Round(100*Log10(distance)) mod 500)
Questions :
What is the relation between distance (DEM) and distance between 2 points ?
" For distance estimate it has been proved that the computed value differs from the true distance at most by a factor of 4. " (Wolf Jung)
Links:
Main Page
Feel free to e-mail me!
Author: Adam Majewski
adammaj1-at-o2-dot-pl
About
http://republika.pl/fraktal/