Shop Forum More Submit  Join Login

Perturbation for the Mandelbrot set


Perturbation for rendering the Mandelbrot set has been around for a while. I would have written a journal before because it's very awesome, but right from the start there was a fundamental problem: reliability. A recent discovery by Pauldelbrot on fractalforums.com indicates that perturbation can now be used to render the Mandelbrot set reliably. Is the project approaching completion? "Correctness" now appears to be achieved.

Discovery

Roughly a year ago, Kevin Martin published a relatively short document about the Mandelbrot set, containing some equations that staggered everyone. His idea was to apply the principle of perturbation to rendering the Mandelbrot set, and combining that with something he called series approximation. Perturbation allows the iteration count of a pixel to be derived from a different, fully calculated pixel "nearby" (to be called a reference pixel). In practice this means that it's possible to calculate just one single pixel in an image, and derive the rest using perturbation. At great depths with millions of iterations, this saves an enormous amount of render time, which is the main result.

Series approximation allows large number of iterations of pixels to be skipped entirely, good for another enormous speed-up, but it doesn't stop there. In addition, no arbitrary precision calculations are required to do the "deriving" work. Floating point calculations, which are much faster to perform, are sufficient. Martin concludes his document with the following statement:
Using [the equations] means that the time taken rendering Mandelbrot images is largely independent of depth and iteration count, and mainly depends on the complexity of the image being created.
The implications of this are enormous and such a theory is of course yelling to be implemented. Along with the mathematics, Martin also published a simple software implementation of the theory dubbed SuperFractalThing, so that everyone could see that it works. Since then, more software developers have started working on their own implementations.

The simple equation of the Mandelbrot set has long been famous of being so computationally intensive that it can bring any supercomputer to it's knees, as long as you zoom in deep enough. Although that is still the case even with perturbation, the barrier has been shifted significantly. To get an idea of the speed-up we're talking about, consider the following deviation:
SSSSSurvival of the fittest - Evolution #3 by DinkydauSet
Fractal extreme has been the fastest software to calculate the Mandelbrot set for a long time, using traditional optimizations. If the deviation above were to be rendered in Fractal extreme, the render would take roughly 6 months. The actual image was rendered in 6 hours using an implementation of perturbation by Botond Kosa. What you're looking at right there is something that, without perturbation, would have been totally out of reach for many years, no matter how optimized the software is. As Bruce Dawson, the man behind Fractal extreme, commented on fractalforums.com: good algorithms beat optimized code.

Glitches

Although there is no doubt that perturbation is a "good algorithm", it came with severe problems right from the start, that Kevin Martin couldn't solve himself. If you have been paying attention, you may have noticed the requirement of a reference pixel to be "nearby". More specifically, usage of floating point numbers to do the calculations requires some numbers in the perturbation equation to be "small". Mathematically, this is completely useless, because there's no exact definition of what "small" is. Indeed, the results of the calculations were shown to be unreliable in many cases. It turned out that the results were correct "most of the time", but sometimes not. Incorrect parts of renders have since been called glitches.

An example of such a glitch can be seen in the image below.
rare_glitch.png (1024×533)
Look closely at the largest spirals. The render on the left contains glitches; the render on the right is correct.

Several attempts have been done to get rid of these inaccuracies. There have been made workarounds where the computer was taught what glitches usually look like, so that they can be automatically recognized and solved. A way to do it is to calculate a second reference point inside the glitched area and do the perturbation calculations again. Having a new reference point more "nearby" solves the glitch. Karl Runmo made notable contributions to this automated glitch solving in his software implementation called Kalles Fraktaler.

As you may understand, it is very difficult to teach a computer to distinguish between correct and incorrect renders visually, especially because glitches can occur in such an enormous variety of types. Even fractal structures can sometimes appear as glitches, which is interesting on its own, but very, very difficult to auto-recognize. As such, manually solving glitches appeared to be a necessity: a very time-consuming process.

It might seem reasonable to spend some time to solve the glitches. Considering how many months of render time (and hundreds of euros worth of electricity) can be saved, spending a day solving glitches doesn't seem so bad. This idea slowly started to change as more difficult types of glitches were found where the "extra-reference-trick" didn't even work. Where does it stop? How many more types of glitches are there and can there ever be made workarounds for all of them? What was needed was more insight in where the inaccuracies come from, so that they can be avoided instead of worked around.

Correctness: now achieved?

Recently, Pauldelbrot on fractalforums.com published an algorithm to find reliably which pixels of a render are correct and which aren't. This information can then be used to reliably solve the glitches as well. This was somewhat unexpected, because the algorithm doesn't help in preventing glitches, instead, it helps to detect them afterwards. This is somewhat similar to the approach of Karl Runmo, except Pauldelbrot detects glitches in a non-visual way. The algorithm has shown to be reliable. It automatically solves all the hard-to-detect glitches and no counterexample that slips trough has been found so far. That is great news!

This doesn't mean the project is really finished. There may still be a better way to get rid of glitches still to be discovered and many of the programs that currently use perturbation are still under development. It may even be possible to extend the method of perturbation to be used with different fractals. A good first candidate would be the Mandelbrot set with a power of 3 (instead of 2), but applications in 3d fractal rendering cannot be excluded in the future. The search continues. Mathematics never ends.

Applications in art

I haven't been sitting idle as the developments went on. As such I can now present to you a new video. I once remarked on YouTube that I could do so many more interesting things if just my computer was 1000 times faster. Here you have it. This is one of the things I was thinking of at the time.


More is coming "soon".
Add a Comment:
 
:iconleconservateur:
LeConservateur Featured By Owner Oct 9, 2014  Professional Digital Artist
What software would you recommend for taking advantage of this, DinkydauSet?

As best I can tell, Kalles Fraktaler 2 requires manual correction of certain classes of glitches... contrary to your suggestion herein that PauldelBrot's solution is a full proof method for automatic glitch detection and correction.  Am I misunderstanding something?

MandelMachine I cannot tell whether it is the same way... but even if it automatically resolves all glitches to end up with a correct image, it seems to refuse to use more than 2 GB of memory for renders... which is a real shame, because I have 64 GB of memory on this desktop system.

I'd be grateful for any suggestions you may have!

I thank you in advance!

- Sebestyén
Reply
:icondinkydauset:
DinkydauSet Featured By Owner Oct 16, 2014  Hobbyist Digital Artist
Mandel Machine is much faster than kalles fraktaler, but both programs have interesting features. Mandel machine has only the mandelbrot set at the moment and it can only render images. Kalles fraktaler can render videos. Mandel machine is much faster at what it does, and kalles fraktaler can go deeper.
Reply
:iconleconservateur:
LeConservateur Featured By Owner Oct 16, 2014  Professional Digital Artist
Your 7+ GB video is without doubt the most incredible Mandelbrot zoom I have seen to date.  It's been making me want to do some calculations of with regards to your video?

e.g.: How many seconds of zooming into your video would the full mandelbrot set be the "size" of Germany?  Europe?  All terrestrial landmasses combined?  Our solar system?  Our galaxy?  The observable universe?

Maybe I'll get around to figuring it out before long... unless you have a pretty good idea already.

And am I correct in my understanding that the end-point of your zoom is so deep that a complete mandelbrot rendered at that magnification would be some absolutely ludicrously large number of times larger than the observable universe?

- Sebestyén
Reply
:icondinkydauset:
DinkydauSet Featured By Owner Oct 17, 2014  Hobbyist Digital Artist
Every "zoom" stands for a factor 2 increase in size, so the final size of the fractal is 2^zooms, which is something like 2^1450 in this case. But: 2^1450 what? meters? In any case, even if you take it to be millimeters, you will very soon surpass sizes like those of countries.
Reply
:iconleconservateur:
LeConservateur Featured By Owner Oct 17, 2014  Professional Digital Artist
I have a bit of an odd and only semi-related question, DinkydauSet...

Are there mathematical proofs that no matter how deeply you zoom into the mandelbrot set, it will always be self-similar (or, I suppose, featureless, depending on where you zoom)?  If not, is that even something that is the sort of thing that could be mathematically proven?

Obviously it's hard to define what I mean by self-similar... but I assume both of us would be skeptical to believe that something that looked like random noise or a series of perfectly straight vertical stripes of alternating matte colour were features within the mandelbrot set.

Is that just our intuition combined with pre-existing knowledge talking though?  Or is there a conclusive way to know that no matter how deeply we zoom, we'll never find anything that looks (based on current expectations) improbably different?
Reply
:icondinkydauset:
DinkydauSet Featured By Owner Oct 17, 2014  Hobbyist Digital Artist
As far as I know: no, there is no such proof! I have raised this question on fractalforums.com before and there was no one who knew of any kind of proof that the mandelbrot set is the fractal such as we understand it at all. It's interesting to think about it and it would be nice if there was a proof.
Reply
:iconleconservateur:
LeConservateur Featured By Owner Oct 17, 2014  Professional Digital Artist
Great minds think alike, I guess! ;-)

Though despite my curiosity, I may be happier not having such a proof... it keeps possibilities more tantalizing.
Reply
:iconleconservateur:
LeConservateur Featured By Owner Oct 17, 2014  Professional Digital Artist
Well, I was going by a rough guesstimate of 10 cm being the original unzoomed size (on my computer screen, at least).

So, going by Wolfram Alpha:

Your final zoom is 3.5 * 10^408 times the diameter of the observable universe.

Congrats! ;-)

And, just out of curiousity, I played around a bit more... after 23 zoom levels, the full area would be approximately twice the size of Germany.
Reply
:icondinkydauset:
DinkydauSet Featured By Owner Oct 16, 2014  Hobbyist Digital Artist
I think Pauldelbrot's method hasn't been shown yet not to work. However, a "tolerance" for error is required. The default tolerance in kalles fraktaler is not always enough, but there is a setting to decrease it, which increases render time but should solve any remaining glitches. Of course there may still be a location where the decreased tolerance is not even good enough. It may take more time to get a good understanding of what kind of tolerances are required for a good balance between correctness and speed, but that's not something I have investigated, so I know little about it.

64 GB? That's nice. I think mandel machine can use your RAM. Botond Kosa has recently made it possible to use more RAM. You may have to start the program with a BAT file to enable that. See here:
www.fractalforums.com/mandel-m…
Reply
:iconleconservateur:
LeConservateur Featured By Owner Oct 16, 2014  Professional Digital Artist
Thank you for the explanation and the link.  I will definitely explore a bit more.

I will also approach Botond to see if he might be willing to add console-based functionality... that is greatly my preference.

- Sebestyén
Reply
:icondinkydauset:
DinkydauSet Featured By Owner Oct 17, 2014  Hobbyist Digital Artist
Nice to meet another person interested in console-functionality. I would like that as well, especially interesting combined with the exporting of raw iteration data.
Reply
:iconleconservateur:
LeConservateur Featured By Owner Oct 17, 2014  Professional Digital Artist
Hopefully Botond can be persuaded.  I am Hungarian too... so who knows, perhaps our fraternity shall aid my case. ;-)
Reply
:iconfractalmonster:
FractalMonster Featured By Owner Sep 30, 2014
:clap: :clap: :clap:

.. and maybe the best zoom animation I ever seen (patterns, High quality, the music, and all) :omg: :wow:
Reply
:icondinkydauset:
DinkydauSet Featured By Owner Oct 1, 2014  Hobbyist Digital Artist
Thank you very much
Reply
:icontimemit:
timemit Featured By Owner Jul 28, 2014  Student Digital Artist
epic zoom, what a journey thanks for sharing... . i like that when it stops the last brot seems to bounce back and shrink in size :) 
Reply
:icondinkydauset:
DinkydauSet Featured By Owner Aug 17, 2014  Hobbyist Digital Artist
thank you very much!
Reply
:iconcatelee2u:
catelee2u Featured By Owner May 13, 2014  Hobbyist General Artist
Awesome and many thanks for writing this. Anything that speeds this up will aid in the creative process as ideas get lost in wait time. I love saving electric too!
Reply
:icondinkydauset:
DinkydauSet Featured By Owner May 13, 2014  Hobbyist Digital Artist
Yes, absolutely! The Mandelbrot set used to be very difficult to navigate around. Now it's much easier and it will probably get better in the future, as the techniques get more refined and optimized.
Reply
:iconseryzone:
SeryZone Featured By Owner Apr 29, 2014  Hobbyist Photographer
THANK YOU very much!!! Maybe, once, I wake up and will see rendered hard video 10^30000... Thanks for perturbation)))
Reply
:iconmario837:
mario837 Featured By Owner Apr 29, 2014
Excellent article and unbelievable zooming! :clap:
Reply
:icondinkydauset:
DinkydauSet Featured By Owner May 13, 2014  Hobbyist Digital Artist
Thank you very much!
Reply
Add a Comment:
 
×

Featured in Collections


More from DeviantArt



Details

Submitted on
April 28, 2014
Link
Thumb

Stats

Views
12,477
Favourites
10 (who?)
Comments
21