efficient algorithms for drawing mandelbrot or julia set

[sddsmhr]

I just want to know, which of the many known algorithms for drawing the mandelbrot and/or julia set are most efficient.

Furthermore does anybody know the algorithm of Peitgen, which he offered in earlier editions of his book "Chaos and Fractals - New Frontiers of Science"? There he was using a technique to triangulate the complex plane and approximating the mandelbrot set by following the equipotential lines... He gave a BASIC-Code for that algorithm, but that doesn't work for me.

[cKleinhuis]

i like the algorithm that traces the equipotential lines as well, i saw it in peitgens video, in my eyes the easiest to implement, and most speed gaining algorithm is the
successive refinment found on mu encys excellent fractal coding website:
http://mrob.com/pub/muency/successiverefinement.html

[cKleinhuis]

problem with that method is it hardly applies to sophisticated coloring algorithms, one other solution is to track for orbits, wich means that you track if a position in the iteration loop has been visited before, and break instantly at that point ... but this method hardly really gains anny speed increase, and due to float/double limitiations and rounding effects it is hardly a real efficent method ....

for the julia set a point-cloud rendering via ifs (iterated function systems ) is viable, as seen by many winamp visualisations and aphophysis....

lets wait what others say ,9

[sddsmhr]

Thanks for fast response at first. I know the technique of "Successive Refinement" from the Ultra Fractal Explorer and really like it...

But I guess that technique still bases on the "Espace Time Algorithm" which should be the the lowest of all algorithms.

What about "Distance Estimation Method" or "Boundary Scanning Method"...? Is there any algorithm which is able to rival the "ETM"...?

And for Julia Sets I actually only implemented "Inverse Iteration Method (IIM)" and the Modified "Inverse Iteration Method (MIIM)". Are there some "better" ones...?

I had some problems with my computer (damaged power supply) the last weeks and now I just have only some days to finish and showcase my program (which should compare some algorithms and show their strengths and weakness). I just would like to have a top list of the most popular algorithms (and techniques), so I can decide, which algorithm I try to implement now...

PS: Now I simply included some 'scanlines' which wasn't much effort and also at least halves the calculation time...

[cKleinhuis]

you know, the mandelbrot is mirrored ad the x axis, thus you can re-use the upper calculation for the lower at least for viewings near the x axis

dude, it is nice that you want to create such an detailed list, i am not aware of any other methods, when you put your list online i am mostly interested in checking out the algorithms presented
but as a side note, when you start making such a list, please keep in mind that many of the optimizations can not be used on nowadays graphics hardware, because the modern gpu graphics cards do not allow to share calculation results - at least not in one step - so, your algorithm list should include a check box for: "viable for gpu" and the other one "viable for cpu"

[David Makin]

*If* you know for certain that your set is 100% connected i.e. the original Mandelbrot (or similar) or Julias where the central point is "inside" then obviously the optimum method if you simply want a visual approximation of the boundary is a simple boundary trace, either simply to the required display resolution or to a sub-pixel level to allow some form of AA.

Other than that, if you want some form of varied colouring "outside" and possibly "inside" and you want to render any formula rather than just z^p+c including disconnected Sets then *there is no better method* than the escape-time one *and* any optimisations that actually speed things up, however good, will reduce the quality of the result (e.g. periodicity checking).

Of course I'm ignoring specific optimisation here such as mirroring and rotational symmetry as they are restricted to relatively few fractals in practice - if you really only want to render z^p+c then optimisations based on these apply whatever the basic rendering algorithm happens to be, even using the convergent methods. But of course taking advantage of symmetry is only relevant really when rendering the entire object, not usually when rendering zooms with the window only showing sections of the fractal.

[Syntopia]

The quality might also play a role: though standard escape-time is probably the fastest, you need to do a lot of oversampling - otherwise you get aliasing and loose detail. The DE based methods don't suffer from this - you can evaluate one pixel and check whether the boundary is completely outside this pixel (check out some of Pauldelbrot's DE Mandelbrots for some good examples)

[Adam Majewski]

cgi.di.uoa.gr/~vasilios/DRA02.pdf

Drakopoulos V., Comparing sequential visualization methods for the Mandelbrot set, International Conference of Computational Methods in Sciences and Engineering 2003 (ICCMSE 2003), Kastoria, Greece, Sep.12–16, 2003.

Generaly algorithm is related with dynamic type.
http://en.wikibooks.org/wiki/Fractals

HTH

[therror]

In well-known benchmarksgame.alioth.debian.org the best  speed gives this program: http://benchmarksgame.alioth.debian.org/u64q/program.php?test=mandelbrot&lang=gcc&id=9
I have implemented similar algorithm, but with poisson disk distribution(Dunbar and Humfrey's boundary sampling algorithm). Speed increases by 43%.
Also border tracing is very useful.

[Adam Majewski]

IMHO  benchmarksgame.alioth.debian.org  compares the same algorithm in different programs/programming languages.

[therror]

Yes. But in the same language different implementations has different efficiencies. Implementation in the link above twice faster than simplest implementation in the same language (data from benchmarksgame).