• February 25, 2021, 05:09:15 PM

Login with username, password and session length

Author Topic: (Question) Uni-colored artefacts in deeper zoom levels  (Read 498 times)

0 Members and 1 Guest are viewing this topic.

Offline sedi

  • Fractal Freshman
  • *
  • Posts: 5
(Question) Uni-colored artefacts in deeper zoom levels
« on: December 21, 2019, 12:45:16 AM »
Hi,
calculating Mandelbrot sets in c++ (double precision) I have noticed strange artefacts when I zoom down quite deeply. I have no explanation for them. It seems as if the correctly rendered structures are being overlapped by large chunks with non-fractal borders.

I have attached a screenshot for better understanding.
It was calculated with these parameters:
x: -0.743747
y: 0.110228   
height: 2.56114e-10 
calculated with 5350  iterations

My code is:
Code: [Select]
int MandelbrotIterator::mandelbrotPlusTest(Complex &c, int maxIter)
{
    double r = c.vectorSquaredLength();
    double s = qSqrt(r-0.5 * c.x() + 0.0625);
    // test for head (circle) or body (cycloid)
    if ((16 * r * s > 5 * s - 4 * c.x() + 1) && ((c.x()+1)*(c.x()+1))+(c.iy()*c.iy())>0.0625) {
        Complex x = m_startX;
        int i = 0;
        do {
            i++;
            x.squareAndAdd(c);
        } while (x.vectorSquaredLength() <= 2 && i <= maxIter);
        if (i > maxIter) {
            i = -1;
        }
        return i;
    }
    return -1;
}

I would expect to see the beautiful structures from the bottom left corner to cover the whole area. The big flat one-color sections are clearly wrong - but I don't get, how!

Any ideas / similar experiences?

Linkback: https://fractalforums.org/programming/11/uni-colored-artefacts-in-deeper-zoom-levels/3238/

Offline lycium

  • Fractal Fruit Salad
  • *****
  • Posts: 72
    • deviantArt profile
Re: Uni-colored artefacts in deeper zoom levels
« Reply #1 on: December 21, 2019, 09:30:35 AM »
You simply reached the (finite) precision of double precision IEEE 754 arithmetic.

To go further you need more bits of precision, usually via some arbitrary precision arithmetic library, which will be a lot slower of course.

Some "good" news though: you don't really see anything new from deeper zooming.

Online claude

  • 3f
  • ******
  • Posts: 1781
    • mathr.co.uk
Re: Uni-colored artefacts in deeper zoom levels
« Reply #2 on: December 21, 2019, 04:14:59 PM »
Code: [Select]
x.vectorSquaredLength() <= 2should be 4 (minimum) not 2

Online claude

  • 3f
  • ******
  • Posts: 1781
    • mathr.co.uk
Re: Uni-colored artefacts in deeper zoom levels
« Reply #3 on: December 21, 2019, 05:00:16 PM »
You simply reached the (finite) precision of double precision IEEE 754 arithmetic.
Precision loss artifacts are different - the whole image gets a grainy rectangle grid.  1e-10 is well within the range of double at screen-sized images.

Online claude

  • 3f
  • ******
  • Posts: 1781
    • mathr.co.uk
Re: Uni-colored artefacts in deeper zoom levels
« Reply #4 on: December 21, 2019, 05:16:51 PM »
It was calculated with these parameters:
x: -0.743747
y: 0.110228   
height: 2.56114e-10 
calculated with 5350  iterations
I tried to reproduce but you don't have enough precision in your coordinates so I end up with a blank image (100% exterior).  You need at least 13 digits after the point for 1e-13 pixel spacing (corresponding to 1e-10 radius at 1e3 image size).

Online claude

  • 3f
  • ******
  • Posts: 1781
    • mathr.co.uk
Re: Uni-colored artefacts in deeper zoom levels
« Reply #5 on: December 21, 2019, 05:44:17 PM »
Here's a complete reproducing example (not intended to be the best M-set rendering code):
Code: [Select]
#include <stdio.h>

int main(int argc, char **argv)
{
  const int bug = argc > 1;
  const double er2 = bug ? 2 : 4;
  const int maxiters = 53500;
  const int w = 1600;
  const int h =  800;
  const double cx0 = -0.74374706715361277261972712114815146;
  const double cy0 =  0.11022795357094870673438971108872898;
  const double cr0 =  2.56114e-10;
  printf("P5\n%d %d\n255\n", w, h);
  for (int j = 0; j < h; ++j)
  {
    const double cy = (0.5 - (j + 0.5) / h) * 2 * cr0 + cy0;
    for (int i = 0; i < w; ++i)
    {
      const double cx = ((i + 0.5) / w - 0.5) * 2 * cr0 * w / (double) h + cx0;
      double zx = 0;
      double zy = 0;
      int k;
      for (k = 0; k < maxiters; ++k)
      {
        const double zx2 = zx * zx;
        const double zy2 = zy * zy;
        if (zx2 + zy2 > er2) break;
        zy = 2.0 * zx * zy + cy;
        zx = zx2 - zy2 + cx;
      }
      putchar(k & 0xFF);
    }
  }
  return 0;
}

Usage:
Code: [Select]
gcc bug.c
./a.out > ok.pgm
./a.out bug > bad.pgm
and notice that the edges of the shapes are chopped off in the bad output.

Offline sedi

  • Fractal Freshman
  • *
  • Posts: 5
Re: Uni-colored artefacts in deeper zoom levels
« Reply #6 on: December 21, 2019, 11:39:03 PM »
Many thanks to both of you! Claude identified the problem right away (well, he knows - he's even written a proof for it): for performance reasons I had omitted the Pythagoras square root for the distance check without squaring the other side. That was rather stupid of me, sorry!

I was assuming that precision artefacts should look different, but I lack real experience in the field. Without being able to find words for it, I even have a feeling of a slight understanding about the reasons the artefacts appear when falsely checking against 2 instead of 4.

I am currently experimenting on sonification of the Mandelbrot set. Yes, I know I am not the first to try/do that. But I wanted to make fractals sound since I first got to know them as an 11th grader in the early 90ies. Neither computers nor I were ready for that task then. Ok, computers definitely more than I was :-D

Offline lycium

  • Fractal Fruit Salad
  • *****
  • Posts: 72
    • deviantArt profile
Re: Uni-colored artefacts in deeper zoom levels
« Reply #7 on: December 21, 2019, 11:43:54 PM »
Sorry for the red herring about precision, should have looked closer at the image :-[

Offline sedi

  • Fractal Freshman
  • *
  • Posts: 5
Re: Uni-colored artefacts in deeper zoom levels
« Reply #8 on: December 23, 2019, 12:57:37 AM »
No apologies needed - thank you very much for your input!
I have a first YT video of my experimental program:

I have noticed that I still have some overlapping spots (not visible in this video) and arbitrarily raised the limit from 4 to 5. Is there any number that is proven to be sufficient? I could just take a 10, it should not make a big performance difference (one or two iterations each) I guess. But on the other hand it would be possible to have more "false positives" at the end of the iterations….

Online claude

  • 3f
  • ******
  • Posts: 1781
    • mathr.co.uk

Offline marcm200

  • 3c
  • ***
  • Posts: 925
Re: Uni-colored artefacts in deeper zoom levels
« Reply #10 on: December 23, 2019, 05:01:32 PM »
Is there any number that is proven to be sufficient? I could just take a 10, it should not make a big performance difference (one or two iterations each) I guess. But on the other hand it would be possible to have more "false positives" at the end of the iterations….
I use the Douady estimate for polynomial Julia sets that is sufficient in the mathematical sense:
(1 + sum over all coefficient's magnitude)
divided by the highest degree coefficient (Figueireo et al, Images of Julia sets that you can trust, chapter 7).

As the c-value is the degree-0 coefficient, escape radii can be chosen quite differently for different parts of the set, which might speed things up - and if fewer iterations are sufficient for a (theoretically) correct result, the chance for numerical error to overpower the correct answer goes down (useful for degree >= 3).

There are sharper bounds mentioned in the text I've not used.

If by sufficient you mean sufficient for the used numerical type not producing any false escaping/bounded results, that'd be a very interesting question - but I have no answer.

I've currently started using Robert Munafo's f107 double-double implementation, which is about the speed of long double. This might be an option to try instead of arbitrary precision.
« Last Edit: December 23, 2019, 05:38:05 PM by marcm200, Reason: removed bad idea »

Offline marcm200

  • 3c
  • ***
  • Posts: 925
Re: Uni-colored artefacts in deeper zoom levels
« Reply #11 on: December 23, 2019, 05:36:20 PM »
Another possibility I just thought of:

Suppose your zoom regions has c-values of [c1 .. c2] (being a complex interval).
If you compute a Julia set with said interval using the cell mapping/IA algorithm of the above mentioned paper, you get a shape of the union Julia set with a guaranteed exterior region (white). Take the largest coordinate of the non-white region (this is usually smaller than 2) and use that as a bailout value.

Below is an example of the basilica region: c value's real part:-1 +- 1/128 and imaginary part of 0 +- 1/128 * i.
The leftmost gray pixel is around ~-1.8, the rightmost around ~1.8 , so a bailout of that exact number will be mathematically sufficient.


Offline sedi

  • Fractal Freshman
  • *
  • Posts: 5
Re: Uni-colored artefacts in deeper zoom levels
« Reply #12 on: December 24, 2019, 05:43:35 PM »
Wow, thats a lot of stuff to learn from, thank you very much! I will yet have to understand parts of it, but I probably will :-)
For the time being I've set the value to 4 (magnitude ==2).

When I wrote, that'd not be sufficient, I had mended a wrong (mostly unused) method. As it's not very expensive, I don't need smaller values - the impact would be marginal.

Offline sedi

  • Fractal Freshman
  • *
  • Posts: 5
Re: Uni-colored artefacts in deeper zoom levels
« Reply #13 on: December 24, 2019, 05:47:56 PM »
I have just released my code on GitLab, just in case anyone is interested:
https://gitlab.com/sedipublicstuff/mandelbrotsound/

Comments and ideas are always welcome!


xx
"Time Span"

Started by cricke49 on Fractal Image Gallery

0 Replies
802 Views
Last post August 02, 2018, 07:05:21 AM
by cricke49
xx
Neural Style Transfer enhanced Mandelbrot zoom

Started by schizo on Fractal movie gallery

6 Replies
725 Views
Last post December 22, 2020, 09:31:14 PM
by schizo
clip
A new style of fractal imagery using fractal neural style transfer

Started by iRyanBell on Fractal Image Gallery

3 Replies
696 Views
Last post October 03, 2020, 10:50:39 PM
by Jimw338
xx
Birdie Style

Started by gannjondal on Fractal Image Gallery

1 Replies
811 Views
Last post May 08, 2018, 02:39:37 PM
by who8mypnuts
clip
Neural Style Transfer with Fractal Art

Started by reallybigname on Other Artforms

1 Replies
665 Views
Last post July 20, 2019, 04:25:41 PM
by reallybigname