(Question) Changing permutation reference point during calculation

  • 3 Replies
  • 167 Views

0 Members and 1 Guest are viewing this topic.

Offline jjrv

  • *
  • Fractal Freshman
  • *
  • Posts: 2
« on: October 26, 2018, 05:28:12 PM »
I'm working on a realtime WebGL Mandelbrot zoomer so the CPU / GPU time budget per frame is tight. It uses perturbation with the reference point calculated like this:

1. Find the next lowest period in the view using Robert Munafo's Jordan curve based algorithm.
2. Look for a minibrot with the period from the previous step using Newton-Raphson and an epsilon of one pixel.
3. If Newton-Raphson failed to converge at all, go to step 1.
4. If a minibrot was found inside the view, we're done.
5. If 3 minibrots outside the view have already been found, use the closest one as reference. Otherwise go to step 1.

This seems to converge near a minibrot pretty reliably, but with one pixel epsilon may be still be outside the set.

The full reference orbit is calculated in chunks sent to the GPU, which keeps the last low precision orbit coordinates for every pixel from the previous chunk of iterations.

However only after iterating past period length I can detect that the reference orbit actually escapes, epsilon needs to be smaller and the precision increased. Then the reference orbit needs to be re-calculated, which takes too long, and the pixels rendered on GPU so far are thrown away.

Sometimes this happens several times before epsilon is small enough for the particular minibrot - it may need to be smaller by a factor of 2^32 or even more.

I can see two possible solutions:

1. Can I use some size estimation algorithm like this...
https://code.mathr.co.uk/mandelbrot-numerics/blob_plain/HEAD:/c/lib/m_d_size.c
...even if the "nucleus" is actually outside the set due to insufficient precision?
Knowing the size would help choose a sufficiently small epsilon, and that algorithm only needs to iterate for one period.

2. Can I "rebase" the previous low precision orbit coordinates (without knowing their full history) on the GPU to a new, more precise reference orbit?
All the GPU could see is some previous coordinates from the old and new reference orbits in single precision, and the latest perturbed coordinates using the old reference.
The epsilon is divided by 65536 and precision increased by 16 bits at a time, so the reference orbit itself could probably be perturbed on the CPU using only double precision.
The CPU sees the full history of both reference orbits and could also calculate a moderate number of parameters for some arbitrary function (series approximation?) to send to the GPU for application to every pixel there.

In case you're wondering, this is aimed for zooming up to 2^128. Really deep zooms are obviously never going to be real-time.
« Last Edit: October 26, 2018, 06:18:13 PM by jjrv »

Offline claude

  • *
  • 3e
  • *****
  • Posts: 1063
    • mathr.co.uk
« Reply #1 on: October 26, 2018, 07:13:25 PM »
https://mathr.co.uk/blog/2017-05-22_on_the_precision_required_for_size_estimates.html

yes you can rebase, you just have to be careful to do the subtraction in the right order (as zr_1, zr_2 should be very close together):
Z_true = zr_1 + zd_1 = zr_2 + zd_2 -> zd_2 = (zr_1 - zr_2) + zd_1
bets may be off if one of the reference is on the way to escape,if (zr_1 - zr_2) is much bigger than zd_1 you loose precision in the addition

Offline jjrv

  • *
  • Fractal Freshman
  • *
  • Posts: 2
« Reply #2 on: October 26, 2018, 08:10:28 PM »
Thanks claude! That link clarifies the worst case epsilon for a given period (proportional to 16^-p). Since it's also the precision needed for a 100% reliable size estimate, it sounds like the size estimate won't save much time here.

Still not sure if the size estimate works if the nucleus given to the algorithm is outside the set and/or the atom domain. However the perturbation rebase sounds like a better solution. Wonder how I didn't realise the math was so simple all along. Will try it next!

Offline claude

  • *
  • 3e
  • *****
  • Posts: 1063
    • mathr.co.uk
« Reply #3 on: October 27, 2018, 01:49:45 PM »
My result in that page is that if the bits of precision needed to be inside the atom is 4p, and you have something known to 2p, you can find an ok size estimate (at least for that sequence atoms in the antenna).  If you know something to 2p bits, the chances it is inside an epsilon of 4p bits is tiny, so it does work outside the atom (and set).  Nice idea about relating it to the atom domain size, that needs to be investigated I think.

However, even 2p bits is probably vast overkill for most atoms, it is a very-worst-case estimate... if I recall correctly KF's Newton zooming uses 3N bits, where N is the number of bits at the current zoom level (which is something like "lambda-log2(pixel_spacing)" where lambda is a small buffer, around 10 perhaps...


xx
"Time Span"

Started by cricke49 on Fractal Image Gallery

0 Replies
209 Views
Last post August 02, 2018, 07:05:21 AM
by cricke49
xx
Reference Point for Reference Orbit

Started by mrmath on Fractal Mathematics And New Theories

2 Replies
281 Views
Last post December 10, 2017, 05:14:03 PM
by mrmath
xx
Original Point Color

Started by mclarekin on Color Snippets

0 Replies
11 Views
Last post March 21, 2019, 08:12:34 AM
by mclarekin
xx
Gallery Upload limit time interval calculation?

Started by Anon on Forum Help And Support

0 Replies
105 Views
Last post March 12, 2018, 02:35:49 PM
by Anon
xx
"The Changing Beggar"

Started by cricke49 on Fractal Image Gallery

0 Replies
72 Views
Last post January 31, 2018, 05:30:46 AM
by cricke49