*Continued* SuperFractalThing: Arbitrary precision mandelbrot set rendering in Java.

[knighty]

I've tried the per pixel test AAAaaannnddd... It works!  
Here, for each pixel we compute:
error(delta) = R*|delta|^m+1/(|SA'(delta)| * dt)
The error is given in 0.5 pixel units.

This is the location "Adventurous forest" at zoom factor 4E47 (in kalles units). I used m=8. The first picture shows the result with 7745 SA iterations. The second with 7746 SA iterations. The red shades encode the error in delta space pixel units. At the center, that is at the reference point, it is 0. The first full red color from the center means 0.5 pixel error then 1 then 1.5... as we go further.


link In case there is no picture shown.
Notice the red shades at the upper left and lower right corners... and around the red blobs.


link
Notice that:
   - the error jumps while we added only one iteration.
   - the error is maximal where there was a blob.
   - because the estimation of the truncation error is conservative. The fractal is not deformed too much (but it is).

Here is a little gif animation shoing what happens between 7100 and 8000 SA iteration. In the last picture of the sequence there are no red shades, not because the errors were not detected but because the estimation of the truncation error overflowed.

[urlhttps://goo.gl/photos/QkXCjVoBaMEYhocT9]link[/url]

Finally, sequence for the same location at 8E40 (kalles zoom factor) with SA iteration going from 5630 to 6470.


link

And finally the source code attached.

[Kalles Fraktaler]

Seems that you are on to something

Here is a little test I made on KF for this location at 4E47 (640x360 pixels):

Terms	Skipped	Time
0	0	5.928
3	6756	1.802
5	7156	1.309
10	7551	1.079
30	7764	0.942
50	7891	1.889
100	7943	2.713
1000	7950	2:41.400

So, for this location it is possible to skip 7950 iterations and still get an identical image as if no iterations are skipped.
No deformation occurs on KF...

Addition
For the second location, at 8E40, KF is not able to skip more than 6451 iterations even if 1000 terms are used. So that is about the limit of how much that can be skipped. And again, no deformation occurs

[knighty]

Seems that you are on to something

Here is a little test I made on KF for this location at 4E47 (640x360 pixels):

Terms	Skipped	Time
0	0	5.928
3	6756	1.802
5	7156	1.309
10	7551	1.079
30	7764	0.942
50	7891	1.889
100	7943	2.713
1000	7950	2:41.400

So, for this location it is possible to skip 7950 iterations and still get an identical image as if no iterations are skipped.
No deformation occurs on KF...

Addition
For the second location, at 8E40, KF is not able to skip more than 6451 iterations even if 1000 terms are used. So that is about the limit of how much that can be skipped. And again, no deformation occurs

I couldn't go beyond 50 terms because of overflows in the computation of R. It occurs when R reaches 1e2466 . Then when computing the absolute value there is a squaring which causes the overflow. R*tmax^(m+1) is still very small though.

The first picture attached is with 7940 skipped iteration and the second with 7950. Both use 50 terms. The one with 7950 terms is extremely deformed at the edges. Maybe round off errors?

[claude]

I've tried the per pixel test AAAaaannnddd... It works!  
Here, for each pixel we compute:
error(delta) = R*|delta|/(|SA'(delta)| * dt)
The error is given in 0.5 pixel units.

Interesting.  But as far as I can tell this doesn't help.  We want a cheap way of determining for a whole region whether the series approximation is still valid, as the per-pixel test above is more expensive than simply doing a perturbed iteration.

The interval arithmetic SA' lower bound estimate is messed up because of the zero at the minibrot reference after one period, maybe it would be possible to do some maths to cancel out that zero?  Or minimize over an annulus instead of a disc?  Something like tmin = max(dt, minibrot size) and consider the annulus with radius tmin<=r<=tmax - I don't know enough interval voodoo to figure out if it's possible...

[knighty]

Interesting.  But as far as I can tell this doesn't help.  We want a cheap way of determining for a whole region whether the series approximation is still valid, as the per-pixel test above is more expensive than simply doing a perturbed iteration.

It a WIP, many things still have to be done. 

From the beginning, this test was meant for testing and debugging purposes. But it shows so far, that kalles fractaler's method, by checking at some points (mainly on the border), is good. It is even possible to take it further by using the proposed formula:

  error(delta) = R*|delta^(m+1)|/(|SA'(delta)| * dt), I did a mistake in the previous post

R*|delta^(m+1)| can be estimated as the the absolute value of the difference between test and SA computed points.
SA'(delta) being the derivative of the SA polynomial is easy to compute
For dt and by security  , just take a small fraction of the pixels' width... say 0.01 pixel_width
... Then just take the max.

It is not bullet proof though.

The interval arithmetic SA' lower bound estimate is messed up because of the zero at the minibrot reference after one period, maybe it would be possible to do some maths to cancel out that zero?  Or minimize over an annulus instead of a disc?  Something like tmin = max(dt, minibrot size) and consider the annulus with radius tmin<=r<=tmax - I don't know enough interval voodoo to figure out if it's possible...

I doubt an annulus IA would be effective because of the addition... It is more or less a minkowski addition. But who knows! Thank you for the idea.
There is another way that involves subdivision. The advantage is that it may give the regions where the SA is safe. The disadvantage is that it is maybe costly.

Anyway, the test doesn't have to be done each iteration. At 10000 max possible skipped iterations we can do it each 100 iterations. If we stop at 9900 we won't loose a lot of speed. There must be a good compromise.

I forget each time to mention that the estimation of R is related to interval taylor forms. See for example link.

[stardust4ever]

Very fascinating, watching the images break down. I guess one can assume then at any level, skipping iterations result in slight perturbations of pixels laying outside the centroid. Below some threshold, however, these perturbations are infinitesimally small and do not affect pixel accuracy of the image. Above some threshold, the image becomes visibly distorted and completely trashed.

Also on occasion it is possible to create fun images with glitches, such as this two frame animation I made with MM by limiting the precision of the perturbation float terms.
http://stardust4ever.deviantart.com/art/XX-Fun-with-Glitches-Animated-598140911

[Kalles Fraktaler]

KF is comparing the result from SA with 8 pixels around the edge of the view.
From the begining the threashold was 1e-3.
However I found one location where this threashold was too high.
Even though I have only found location one so far, after playing with this for a couple of years, I changed the default threashold to 1e-5 (so that is mabye why I don't find them anymore)

This location is the location:

Code:

Re: -1.74974151205442298522942858901997753983231934503
Im: 0.000000724622003515946711698189333384986416781569
Zoom: 7.5E22

I know that more iterations can be skipped closer to the reference point than on the edge of a view.
So I had an idea of making more SA start values as you closer to the reference point you get.
However, this particular location contradicts my assumptions, since it reveals than less iterations can be skipped in an area inside the view.
So one would need to be able to go up and down in the number of skipp-able iterations as you go closer to the reference point...

[stardust4ever]

KF, I am curious what the difference in render time between your two images was? It also seems similar to MM where selecting a point of origin not in the centroid causes the glitch to occur.

[Kalles Fraktaler]

KF, I am curious what the difference in render time between your two images was? It also seems similar to MM where selecting a point of origin not in the centroid causes the glitch to occur.

Low tolerance and correct render with 702 skipped iterations (for the first reference) in 640x360 is 0.698 seconds.
High tolerance and incorrect render with 705 skipped iterations is 0.687 seconds, so it is about the same.

[TheRedshiftRider]

I have found that especially with my 16k renders in kf that they sometimes have these kind of glitches. Do I simply have to decrease the number of terms to render a correct image? (This seems to work but takes more time due to the increase of iterations that needs to be calculated.)

[Kalles Fraktaler]

I have found that especially with my 16k renders in kf that they sometimes have these kind of glitches. Do I simply have to decrease the number of terms to render a correct image? (This seems to work but takes more time due to the increase of iterations that needs to be calculated.)

Can you provide an example, because with "Low tolerance" active I haven't encountered any locations with glitches due to SA...?

[TheRedshiftRider]

Can you provide an example, because with "Low tolerance" active I haven't encountered any locations with glitches due to SA...?

http://www.fractalforums.com/ultra-deep-mandelbrot/lightyears-away/
I have tried to render one of my contest images in 16000x9000. I had low tolerance active. I do not have an image of the glitch.

[hapf]

I spent quite some time with this "how much can I skip" problem and in the end actual testing turned out to be the safest and reasonably efficient way (testing = compare skipped and not skipped values at a number of pixels). Analysing the behaviour of the series itself did not work out in the end because as the terms go up (and we usually want them to go up a lot due to the reference period rule) the contributions are spread around more and more in waves and it was unclear when to stop safely looking at contributions. The abrupt changes from ok to corrupted occur around period boundaries. They depend on pixel location and the reference used. And here is some probably new insight: Relevant period boundaries are not just the multiples of the period of the current reference, it's also all the other periods a pixel location is affected by, e.g. the partials. As far as I could see the boundaries from good to bad are always at a sum of multiples of the partials of the pixel. As one flies by a local minibrot the periods there become relevant and possible skipping goes down (when using a deeper down minibrot as reference). As one zooms further the local minibrot becomes less relevant again and only what one inherits from it in the partials can be relevant further down. Embedded Julia sets can further complicate this by adding corruption due to rounding errors independent of overskipping.

[quaz0r]

in the end actual testing turned out to be the safest and reasonably efficient way (testing = compare skipped and not skipped values at a number of pixels). Analysing the behaviour of the series itself did not work out in the end because as the terms go up the contributions are spread around more and more in waves and it was unclear when to stop safely looking at contributions.

this reiterates that the stop conditions which have been experimented with thus far are not truly proper methodologies, which is further evidenced by the fact that MM and KF can still be shown to produce glitches, the fact that KF even supplies a means to manually adjust the sensitivity of the stop condition, and the fact that this guy resorted to brute-force comparison of SA versus no SA to try to safely divine the right stop point.  if we can really nail down something akin to what knighty has proposed, it would be absolutely huge and would elevate this whole endeavor out of the muck of perpetual experimental status.  (and even if hapf's current approach is relatively better than other current approaches, it is still brute-force testing a handful of points in order to divine a course of action for the whole image.)

[stardust4ever]

I spent quite some time with this "how much can I skip" problem and in the end actual testing turned out to be the safest and reasonably efficient way (testing = compare skipped and not skipped values at a number of pixels). Analysing the behaviour of the series itself did not work out in the end because as the terms go up (and we usually want them to go up a lot due to the reference period rule) the contributions are spread around more and more in waves and it was unclear when to stop safely looking at contributions. The abrupt changes from ok to corrupted occur around period boundaries. They depend on pixel location and the reference used. And here is some probably new insight: Relevant period boundaries are not just the multiples of the period of the current reference, it's also all the other periods a pixel location is affected by, e.g. the partials. As far as I could see the boundaries from good to bad are always at a sum of multiples of the partials of the pixel. As one flies by a local minibrot the periods there become relevant and possible skipping goes down (when using a deeper down minibrot as reference). As one zooms further the local minibrot becomes less relevant again and only what one inherits from it in the partials can be relevant further down. Embedded Julia sets can further complicate this by adding corruption due to rounding errors independent of overskipping.

Your description reminds me of my "Simply Awesome II" rework of my first deep Mandelbrot Zoom. Kalles Fractaller produced glitch frames precisely in two locations where the render path deviated from the centroid. I imagine the periodicity of the alternate render paths was very different from that of the central minibrot.

http://sta.sh/01aqqf7kg83r


http://sta.sh/017skb4ouloa

Ultimately I left the glitch frames in the video because I did not know how to fix them without potentially corrupting the iteration data. Here is the final result:
<a href="https://www.youtube.com/v/vnUjXAIIcq0&rel=1&fs=1&hd=1" target="_blank">https://www.youtube.com/v/vnUjXAIIcq0&rel=1&fs=1&hd=1</a>