Method of Early Checking Whether a Point Is In the Set

  • 12 Replies
  • 724 Views

0 Members and 1 Guest are viewing this topic.

Offline Byte11

  • *
  • Fractal Fanatic
  • ***
  • Posts: 39
    • Fractal To Desktop
« on: December 04, 2017, 02:50:15 AM »
NOTE: This does NOT apply to perturbation theory. I'm talking in terms of just normal rendering.

We know that most points that we calculate keep oscillating between a few points (roughly) and tend towards infinity or tend towards 0. What I've found is that points that tend towards 0 (points that are in the set) just get into loops where the oscillate through a few exact points. It becomes an infinite loop. If we increase the precision of our numbers, that point may not tend towards 0, but at the precision we are rendering at, the points will always stay within the set. The program will keep calculating the same thing over and over again until it finally reaches the maximum iteration mark and the program will color the point accordingly. A much better way of doing this would be to check whether points are in a loop. Then we know with certainty that the point is in the set. The problem is that we don't know how many points the program will loop through. It could be 2 points, 4 points, 10 points, 1 point. We just don't know. We could always compare a new point calculated to all the previous points to determine whether it's the same, but that would cost a lot of memory, and it would be slow.

Instead, we can just randomly select a point, see if another point in the future equals it EXACTLY and break. Here is the code:

Code: [Select]
                        int randNum = 0;
random_device rand_dev;
mt19937 generator(rand_dev());
uniform_int_distribution<int> distribution(0, 6);
randNum = distribution(generator);

if (randNum == 4) {
if (mpfr_cmp(ZCoordinateReal, lastZCoordinateReal) == 0 && mpfr_cmp(ZCoordinateImaginary, lastZCoordinateImaginary) == 0) {
break;
}
mpfr_set(lastZCoordinateReal, ZCoordinateReal, MPFR_RNDN);
mpfr_set(lastZCoordinateImaginary, ZCoordinateImaginary, MPFR_RNDN);
}

This works because we know that if the exact same point is calculated twice, it must result in a loop because in Z^2+C, only Z is changing between iterations.

The reason this doesn't work with Perturbation Theory is that XSubN will change based on the iteration, so just because DeltaSubN at an iteration equal the DeltaSubN at another iteration, that doesn't mean that YSubN is the same. (Maybe you could check YSubN?)

Linkback: https://fractalforums.org/fractal-mathematics-and-new-theories/28/method-of-early-checking-whether-a-point-is-in-the-set/572/
Fractal To Desktop - Live Render Fractals To Your Desktop!
http://fractaltodesktop.com/

Offline Byte11

  • *
  • Fractal Fanatic
  • ***
  • Posts: 39
    • Fractal To Desktop
« Reply #1 on: December 04, 2017, 02:58:38 AM »
Update: checking the squared magnitude inside Perturbation Theory in a similar fashion works, but the speed at which random numbers are generated is WAY longer than the speedup this provides.

Offline FractalStefan

  • *
  • Fractal Fanatic
  • ***
  • Posts: 20
    • JavaScript Mandelbrot Generator & More (in German)
« Reply #2 on: December 04, 2017, 01:10:29 PM »
Hi,

I assume you are talking about the Mandelbrot set...? :)

Have you already tested your approach in practice?

If I'm looking at the Z points for a given C starting point (see this little JavaScript app), I can see that the points are indeed oscillating, but they don't always hit the exactly same positions (see 1st attached image). But I do see that they are approaching a center point if C is in the set (see the other attached images), so IMO an algorithm should detect if a point is circulating around such a center point while approaching it.

Stefan

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1329
    • mathr.co.uk
« Reply #3 on: December 04, 2017, 05:21:12 PM »
I like my interior checking method, it does need some Newton's method iterations so it is a bit fiddly:
https://mathr.co.uk/blog/2014-11-02_practical_interior_distance_rendering.html

It can be extended to perturbation rendering, if you use the nucleus of the visible minibrot as primary reference.  But most of the time when deep zooming there are no minibrots visible, so better to skip those calculations entirely unless it is known that some interior pixels will be visible (which can be achieved with size estimate formulas).

Offline Adam Majewski

  • *
  • Fractal Furball
  • ***
  • Posts: 207

Offline Byte11

  • *
  • Fractal Fanatic
  • ***
  • Posts: 39
    • Fractal To Desktop
« Reply #5 on: December 05, 2017, 03:39:03 AM »
Few things I should note:

1. I have tried this in practice and it does catch points that are in an infinite loop. That's what I'm going to use it for.
2. It does not work for all points, it mainly works for ones that are fairly deep within the set.
3. Many points that get stuck in an infinite loop don't do so immediately, you have to calculate for a little while for them to start looping.

Stefan, super cool Javascript tool. My method will catch points that spiral inwards because they'll get into loops at their center. It also catches the perfect shapes that you're seeing. What it doesn't catch are those messy figures similar to the first image you attached that happen near the edge. Increasing the iterations, however, makes these far less messy and converge on a point. I'm fairly confident that at a certain (possibly EXTREMELY deep (>e308) point) these go out, or they converge in a manner this detects since I noticed this behavior happening at the edge of the set. The further you go move from the edge of the set, the longer it takes to go out, and once you move more than 0.1 from the edge, the iterations to escape the set (if I'm correct) get to be ridiculously large. Atleast that's my theory about these points.

This isn't deterministic in that it isn't going to catch everything, but it won't have any false-positives (that's assuming your precision doesn't change midway through calculating the frame) and it catches the vast majority of points. This could definitely be used in conjunction with the methods that claude and Adam put up here, but honestly this doesn't really provide a speedup in calculations unless you're doing classic rendering. 

I do have a use case for this as part of a larger algorithm to automatically determine the optimal max iteration at a given point and magnification (do we have some other algorithms to do this on the forums because I couldn't find any) and so far it works better than UltraFractal's.  I just need to test its robustness.

Offline Byte11

  • *
  • Fractal Fanatic
  • ***
  • Posts: 39
    • Fractal To Desktop
« Reply #6 on: December 23, 2017, 03:02:42 AM »
I tried implementing Adam's method with perturbation theory, but D is EXTREMELY small for every point, and it's marking every single point as being in the set. It's also fairly expensive. I used gerrit's math that he posted here: https://fractalforums.org/fractal-mathematics-and-new-theories/28/perturbation-theory/487/msg2556#msg2556.

Adam, what value were you using for AttractionRadius in the code you posted?

The reason I need this is because every single point that should be colored as being in the set is being marked as being outside the set if I specify my own iteration value. If you look at antelbrot or newman on github, they both check for the point where the reference tends towards infinity, then they break. Antelbrot simply uses this point as the maximum iteration value, which worked well for me in the past, but now I want to set a maximum iteration that is higher than that point. If I just raise the maximum iteration value, none of the points inside the set get colored properly, but everything outside the set works fine.

My theory is that when the point that you're calculating is using the reference after it tends towards infinity, the reference is so high that when it gets plugged into the perturbation equation, it's over the bailout and it immediately breaks.

Is there a way to avoid this problem without interior detection altogether? Have any of you experienced this problem?

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1329
    • mathr.co.uk
« Reply #7 on: December 23, 2017, 06:02:27 AM »
typically you test for glitches and add new (better) references for glitched pixels.  glitch detection formulae should signal that there is a glitch when the reference escapes before the pixel.

for regions with visible interior, better have the reference in the interior (see here: http://www.fractalforums.com/mandelbrot-and-julia-set/strange-deep-zoom-glitch-(help!)/ )
« Last Edit: December 23, 2017, 06:22:03 AM by claude »

Offline Byte11

  • *
  • Fractal Fanatic
  • ***
  • Posts: 39
    • Fractal To Desktop
« Reply #8 on: December 23, 2017, 07:40:02 AM »
Turning on glitch correction only fixes a few points. Making the initial reference in the set fixes the problem!

I think the problem is that I simply log the point that was marked glitched and recalculate those. This works with all points outside the set, but it doesn't seem to always be working with points inside the set. The good thing is: all the points that should be inside the set have the same iteration including the ones that the glitch detection catches. This means that if I change my algorithm to recalculate all points with the glitch iteration, it'll work. I believe this is how Kalles Fraktaler and other renderers work, and it would explain why glitch correction fixes the problem for you and not for me.

Thanks!

Offline Adam Majewski

  • *
  • Fractal Furball
  • ***
  • Posts: 207
« Reply #9 on: December 23, 2017, 12:01:08 PM »
I tried implementing Adam's method with perturbation theory, but D is EXTREMELY small for every point, and it's marking every single point as being in the set. It's also fairly expensive. I used gerrit's math that he posted here: https://fractalforums.org/fractal-mathematics-and-new-theories/28/perturbation-theory/487/msg2556#msg2556.

Adam, what value were you using for AttractionRadius in the code you posted?


const double AttractionRadius=0.001;

from
https://gitlab.com/adammajewski/mandelbrot_wiki_ACh/blob/master/m_int.c

c fila has the same name as  the image


Offline claude

  • *
  • 3f
  • ******
  • Posts: 1329
    • mathr.co.uk
« Reply #10 on: December 23, 2017, 12:43:04 PM »
I tried implementing Adam's method with perturbation theory, but D is EXTREMELY small for every point, and it's marking every single point as being in the set. It's also fairly expensive. I used gerrit's math that he posted here: https://fractalforums.org/fractal-mathematics-and-new-theories/28/perturbation-theory/487/msg2556#msg2556.

gerrit's math is for d/dC, not d/dZ as needed.  Moreover, the derivative isn't "small" in relation to addition with larger values, so you don't need to use perturbation.  It should work something like this, adapt to the case of lots of pixels as you like:

Code: [Select]
N = iteration limit
R = escape radius (eg 10000)
r = convergence radius (eg 0.001)
G = Pauldelbrot glitch threshold (eg 0.001)
C = reference C
Z = reference C
z = pixel delta c
c = pixel delta c
dz = 1
dc = 1
n = 1
while (n < N)
    dz = 2 * (Z + z) * dz
    dc = 2 * (Z + z) * dc + 1
    z = (2 * Z + z) * z + c
    Z = Z * Z + C
    n = n + 1
    if (|Z + z|^2 < G * |Z|^2)
        glitched, try another reference
    if (|Z + z|^2 > R^2)
        escaped, use Z+z and dc for distance estimation
    if (|dz|^2 < r^2)
        converged, probably interior

Offline Byte11

  • *
  • Fractal Fanatic
  • ***
  • Posts: 39
    • Fractal To Desktop
« Reply #11 on: December 24, 2017, 12:21:06 AM »
It works! Kinda.

I've attached a picture with the attraction radius at 0.59 and another with the attraction radius at 0.001. You can see that they approximate the set, but it isn't quite there. This works as a basic speedup, but Claude was talking about setting an arbitrarily high max iteration, using an interior checking method for checking if it's inside, and iterating the rest of the points until they completely escape. As far as I can tell, this interior checking method wouldn't work for that because it would result in an infinite loop. I also tried using the method I described above, but due to minor differences in the deltas, the point doesn't get into an exact loop like it should and the method above doesn't work.


Offline Byte11

  • *
  • Fractal Fanatic
  • ***
  • Posts: 39
    • Fractal To Desktop
« Reply #12 on: December 24, 2017, 12:33:10 AM »
Implementing the algorithm as described above didn't really work...

What I had to do is get the glitched points and continue iterating them until they bailed out (even though they shouldn't have). Then I'd mark that iteration, calculate the rest of the points in the same manner, mark all the points with that iteration as glitched (not the same iteration as the glitch was detected) and recalculate. The problem is that marks a bunch of points that shouldn't be glitched as glitched. This turns into a runaway process where more and more of the image gets marked as glitch IF the reference is outside the set, so when I tried rendering DinkyDau's flake, it didn't work.

The solution to this was using the interior detection method that I originally posted on the reference and if the reference was inside the set, use the algorithm I just described, if not, solve glitches like normal.

Technically, this works, but it's inelegant. I really don't know why Paul's glitch detection isn't catching all the points that are bailing out. It works brilliantly on every location that doesn't have points inside the set. >:(


xx
Early Ultra Fractal

Started by Anon on Image Threads

6 Replies
730 Views
Last post February 21, 2018, 04:22:27 PM
by Anon
xx
Ancient (Another point of view)

Started by kohlenstoff on Fractal Image Gallery

0 Replies
84 Views
Last post October 27, 2018, 03:40:29 PM
by kohlenstoff
xx
Fractals and the vanishing point

Started by Nintendokater on Fractal movie gallery

2 Replies
105 Views
Last post January 23, 2019, 12:57:07 PM
by Nintendokater
clip
Point Cloud export

Started by Arnold3456 on Mandelbulb3d

2 Replies
298 Views
Last post February 15, 2018, 05:53:51 PM
by spain2points
xx
Original Point Color

Started by mclarekin on Color Snippets

0 Replies
35 Views
Last post March 21, 2019, 08:12:34 AM
by mclarekin