Problem with Mandelbrot Distance Estimator

[Levi]

Hi all,

So this is my first time implementing a distance estimator and I have an issue. In the image below, my color scheme is 'mod(dist, 1.0)' where dist is the result of the distance estimator, so each ring should be 1.0 farther than the previous ring. But instead the rings actually become progressively smaller as you get farther from the center, indicating that my distance estimator is not returning a consistent estimate. Increasing the escape radius and iteration count does not fix this. Is this a bug in my implementation, or does the distance estimate normally have this problem?




GLSL code:

Code:

uniform int Iteration;
uniform float Radius;

varying vec2 Pos;

void main ()  
{
    int i;
    float x, y, x0, y0, x_temp; 
    float dx, dy, dx_temp;
    float r, dr, dist;
    float escape;
    
    //Initialize iteration variables
    escape = Radius*Radius;
    x0 = Pos.x; y0 = Pos.y;
    x = 0.0; y = 0.0;
    dx = 1.0; dy = 0.0;
    
    //Run iterations
    for (i = 0; i < Iteration; i++)
    {
        //Update z'
        dx_temp = 2.0*(x*dx - y*dy) + 1.0;
        dy = 2.0*(x*dy + y*dx);
        dx = dx_temp;
        
        //Update z
        x_temp = x*x - y*y + x0;
        y = 2.0*x*y + y0;
        x = x_temp;
        
        //If escaped, quit early
        if (x*x + y*y > escape) break;
        
        //If in a periodic orbit, assume it is trapped
        if (x == 0.0 && y == 0.0) i = Iteration;
    }
    
    //Calculate distance
    r = sqrt(x*x + y*y);
    dr = sqrt(dx*dx + dy*dy);
    dist = 0.5*r*log(r)/dr;
    
    //Color
    if (i < Iteration) gl_FragColor = vec4(1.0 - mod(dist, 1.0), mod(dist, 1.0), 0.0, 1.0);
    else gl_FragColor = vec4(0.0);
}

[cKleinhuis]

just regarding the images, it looks perfectly fine !!!
i think you confuse what mod(distance,1) should do
for my eyes the behaviour is just correct, give us some more zoomed in shots to check if it behaves correctly

[David Makin]

Not sure if there's a problem - what's the bailout used ? The larger the bailout value the better the results will be.

Also check this out (wait for your browser to finish on IQ's post):

http://www.fractalforums.com/3d-fractal-generation/true-3d-mandlebrot-type-fractal/msg8505/#msg8505

[xenodreambuie]

Yes, there is a problem. The distance estimator is wrong. For the Mandelbrot, dz should be initialized to 0. (It is only the Julia set that has dz initialized to 1; the other difference being that the Julia uses dz = z'dz, while the Mandelbrot has dz=z'dz+1).

This mistake seems to have spread over time, including the websites of some forum members; contacting them is on my to-do list 

[Levi]

Thanks xenodreambule, but that didn't fix the problem.

It is hard to tell with the naked eye, but if you use a ruler (or some small object that you can check the distance with), you can verify that the rings get thinner as they get further from the center. If you look at the second picture, the outermost ring is about half the width of the innermost (excluding the one that actually contains the mandelbrot of course). 

[xenodreambuie]

I didn't expect it to fix the 'problem' with the ring width, but it should fix problems with the accuracy of the set boundary.

I think the reason the ring width varies with distance is that it is only an estimate, and accuracy improves as iterations tend to infinity. The further out you get, the less accurate the DE is, but it's a consistent error. So you should not expect equal ring widths, but you can use various functions to change the curve.

[hobold]

The "standard" distance estimate is not exact. It is based on analytically derived bounds (i.e. mathematically proven guarantees) for the exact distance. That means, those formulas tell you that the actual distance of a specific point is guaranteed to be between a resulting lower limit and upper limit. You get no further information which value exactly it is within that interval.

Worse yet, in applying aforementioned theory to the Mandelbrot formula, a few simplifications had to be made to keep the math tractable. Strictly speaking, the commonly used formula is merely an approximation. But the simplifying assumption that was made is that the point in question is "near" the Mandelbrot set. In other words, for all the interesting points, the mathematical guarantees still hold (with a probability bordering on certainty). Further away from the Mandelbrot set, the "standard" distance estimate formula becomes more and more inexact.

[Syntopia]

Hobold is right, the distance estimate is only valid near the boundary.

There is a DE-based 2D Mandelbrot in Fragmentarium ("Mandelbrot-DE.frag") - I get similar results (see attached).

Yes, there is a problem. The distance estimator is wrong. For the Mandelbrot, dz should be initialized to 0. (It is only the Julia set that has dz initialized to 1; the other difference being that the Julia uses dz = z'dz, while the Mandelbrot has dz=z'dz+1).

Looking at the code, I think it is correct: notice, that the initial values (set in the line "dx = 1.0; dy = 0.0;") are not used at all, since x and y are both zero in the first iteration. So after the first iteration, (dx,dy)=(1,0), and (x,y)=(x0,y0), which seems to match the definitions on Wikipedia: http://en.wikipedia.org/wiki/Mandelbrot_set#Exterior_distance_estimation

[xenodreambuie]

Looking at the code, I think it is correct: notice, that the initial values (set in the line "dx = 1.0; dy = 0.0;") are not used at all, since x and y are both zero in the first iteration.

Oops, you are right that it doesn't matter here. But it is not correct as a matter of principle; it is just getting away with the special case of starting from the critical point (0,0) and will cause problems if starting from a different critical point, as should happen for some formulas other than z^2+c.

[Levi]

Thank you guys! So it is an issue with this method of distance approximation. That is unfortunate, since it means ray marching will be slower in implementation than theory. But at least I can rest assured that I've done it correctly!

Now on to ray marching. Wish me luck!

[jdebord]

But it is not correct as a matter of principle; it is just getting away with the special case of starting from the critical point (0,0) and will cause problems if starting from a different critical point, as should happen for some formulas other than z^2+c.

How do you initialize the derivative when the critical point is not zero ?

[xenodreambuie]

How do you initialize the derivative when the critical point is not zero ?

It should be initialized to 0 for the Mandelbrot and 1 for Julia. Actually z' is 0 whenever starting from a critical point, so the Mandelbrot initialization shouldn't matter unless you start from a noncritical point, which is not ideal anyway.

[jdebord]

OK. Thanks.

[frostfern]

Because the method uses the slope of the potential function log(|z_n|)/2^n, which is concave down rather than a straight line, the estimated "distance" will increasingly overestimate the real distance as you move away from the boundary of the set.  It's only a valid distance measure in the asymptotic sense, i.e. when zoomed in close to the boundary.  For deeper zooms it's pretty much exact distance.

[Adam Majewski]

See :

https://commons.wikimedia.org/wiki/File:Part_of_Mandelbrot_set_-_Smily_Kaleidoscope.png

Here

if (distance < (DistanceMax)) color = iBoundary ;

then you only use dem near boundary

HTH