Welcome to Fractal Forums

Hi everyone,
I am trying to write a little program to draw fractals in C, and I am using Ultra Fractal as an example.
I implemented triangle inequality average coloring (TIA), but my results differ a bit from UltraFractal. I understand that to obtain a good image with TIA, one has to chose a big bailout radius, (like 1E20), but with my program I get artifacts for such big values.

The weird thing is, my program uses double precision floats, like Ultra Fractal by default (I checked in the "statistics" panel that the type used is indeed double), so I just don't understand why Ultra Fractal doesn't show any artifacts.

To illustrate what I am talking about, below is what I obtain using TIA with my program, for a bailout value of 1E20 (this is the classic mandelbrot set).
First with no interpolation :
http://dl.free.fr/k4lvSLyZG (http://dl.free.fr/k4lvSLyZG)
With linear interpolation (like Ultra Fractal) :
http://dl.free.fr/nukvlbBle (http://dl.free.fr/nukvlbBle)
And here is the result with Ultra Fractal (gradients differ, but apart from that it should be the same) :
http://dl.free.fr/ntgp4MLS5 (http://dl.free.fr/ntgp4MLS5)
Note that the artifacts do also appear with Ultra Fractal for a bigger bailout radius, like 1E50 (unless you increase the precision, so that Ultra Fractal switches to Arbitrary precision floats) :
http://dl.free.fr/h3eWZMiAI (http://dl.free.fr/h3eWZMiAI)

Also, if I reduce the bailout value to something 1E7 in my program, the artifacts disappear.
First with no interpolation (see ? no artifacts) :
http://dl.free.fr/bXmTqM21V (http://dl.free.fr/bXmTqM21V)
Then with linear interpolation (like UltraFractal) :
http://dl.free.fr/rjSZElo1F (http://dl.free.fr/rjSZElo1F)

Now I can explain why MY program shows such artifacts, but I can't explain why Ultra Fractal does NOT. Here is the explanation :
At one point during the TIA computation, you have to compute something like ||z-c|-|c|| (where c is denoted as #pixel in Ultra Fractal scripts, for those who now). Now if |z| is much much bigger than |c|, then |z-c| ~= |z| : in particular, if your float is not precise enough, you will have |z-c|=|c| (which leads to those artifacts). You also experience the same thing when you compute z_{n+1} = z_n^2 + c : you may have z_n^2+c = z_n^2 because of lack of precision.

For example : In C, mantissa for double precision numbers is 52 bits, so about 14-15 decimal digits. So if |z|>1E16 (which happens when bailout radius is > 1E20), and 0<|c|<10 (which is the case for the given example), then double precision numbers are not precise enough to evaluate |z-c| (we will actually have |z-c|=|z|).
Try initializing a double with 2E20+3E-1, and print it, you will get 2E20 (because 2000000000000000000003 does not fit in 52 bits).

Anyone has any idea how Ultra Fractal can compute things like that with only double ? Because that just seems impossible..

Edit : found this in the Ultra Fractal 8 manual on triangle inequality average :
"Use very large bail-out values for good results. The default value 1e20 (a 1 with 20 zeroes) is a good
starting point. The Mandelbrot (Built-in) formula cannot handle such large values, so use the non-
built-in Mandelbrot instead."
I checked, and indeed, with the Mandelbrot (Built-in) formula, the artifacts appear at a bailout radius of 1e12 or something (and with less, the result is not even smooth, as though there was no linear interpolation), like for my program which uses doubles. So apparently, the problem does not come from my implementation, and the trick for Ultra Fractal is probably that for non builtin formulas it does not use double precision numbers (even if it says so), but something else, maybe double double or quad precision numbers :). What do you think ?

Do *not* go through the colouring loop calculation *after* bailout and the artifacts should go away.

i.e in UF in all main formulas *except* the in-built ones the loop: section of colouring formulas is only called after the main formula loop: section *if* bailout did not occur - so when bailout does occur the only part of the colouring formula processed after the main formula loop: section is the final: section of the colouring formula.

(if the above fixes your problem then I think the reason for your artifacts is actually overflow)

I don't get it : are you saying I should skip the coloring calculations if bailout occured ?
But bailout always occurs (except when maximum number of iterations is reached, that is to say inside the fractal. but anyway, only points outside the fractal are colored), doesn't it ? Isn't it the condition to exit the calculation loop (well, that and the maximum number of iterations) ?
i.e.
while (iteration_number <= max_iteration && |z| < bailout_value)
Could you clarify please ?

No.

If you look at the UF code there is some calculation in the loop: section that is performed per iteration and in the final; section there is the final section which is performed after bailout.
On the iteration when bailout occurs *the loop: code* is *not* executed in UF precisely because *after* z is found to be too large it could actually be :INF: or :NAN:

From the standard UF TIA formula:

loop:
  sum2 = sum
  IF (!first)
    az2 = cabs(#z - #pixel)
    lowbound = abs(az2 - ac)
    sum = sum + ((cabs(#z) - lowbound) / (az2+ac - lowbound))
  ELSE
    first = false
  ENDIF
final:
  sum = sum / (#numiter)
  sum2 = sum2 / (#numiter-1)
  f = il*lp - il*log(log(cabs(#z)))
  #index = sum2 + (sum-sum2) * (f+1)  


The loop: above is normally executed on each iteration after the main formula loop: code *but* if at the end of the main formula loop: code bailout occurs then the above colouring loop: code is not executed *on that final iteration* and program flow continues directly to the colouring final: section.

I hope that's now clear ;)


For a clearer description of UF's execution sequence see the UF help (in program or online) "Tips->Execution sequence".

Just to be sure In understood correctly :
You are saying that the last iteration (where bailout occurs) is ignored for TIA coloring.
If that's what you're saying, then it's exactly what I do in my program.

No, I'm quite convinced these artifacts come from loss of precision in floating point operations, because :
1) My calculations show so. If you have a bailout of 1e20 and your floating point precision is 14-15 decimal digit, you will experience loss of precision (even if you skip the last iteration for coloring).
2) Experience shows so : those artifacts appear both with my program and with Uf5 (with built-in mandelbrot) for a bailout of 1e20. They also appear with Uf5 with *non* built-in mandelbrot for a bigger bailout (like 1e50)

The only mystery is : why do those artifacts appear with Uf5 for a bailout of ~ 1e15 with built-in mandelbrot, but with *non* built-in mandelbrot for a bailout >= 1e50 ?

Edit :
Why do you say "if" ? Bailout *always *occurs at the last iteration (for points outside fractal) : it is the condition to break the loop.

I have no idea why it works in UF and not in your code - assuming you are using double and not float - I implemented it in my own software for 32-bit DOS in 2000 exactly as in UF and it performed/performs exactly as in UF.

Here's the main UF executon including both main formula and colouring:

for each transformation
  execute global section of transformation
execute global section of fractal formula
execute global section of inside coloring algorithm
execute global section of outside coloring algorithm

Then, for each pixel, the following calculations are performed:

for each transformation
  #solid = false
  execute transform section of transformation
  if #solid == true
    stop and give pixel the solid mapping color
endfor
execute init section of fractal formula
execute init section of inside coloring algorithm (if it exists)
execute init section of outside coloring algorithm (if it exists)
int iter = 0
repeat
  execute loop section of fractal formula
  bool b = the expression in the bailout section of the fractal formula
  if b == true
    ; not yet bailed out
    execute loop section of inside coloring algorithm (if it exists)
    execute loop section of outside coloring algorithm (if it exists)
  endif
  iter = iter + 1
until (b == false) || (iter == #maxiter)
#numiter = iter
if #numiter == #maxiter
  ; pixel is inside
  execute final section of the inside coloring algorithm
else
  ; pixel is outside
  execute final section of the outside coloring algorithm
endif
color the pixel

Because the built-in Mandelbrot (and Julia) are essentially historical redundancies going back to the early days of UF - and in fact Fractint for that matter - the z value is one iteration off as compared to the non-built-in version i.e. when executing the colouring code (loop or final or both) the z value is one iteration further on than normal.

But my program works just like Ultrafractal with built-in Mandelbrot. I get the same result (see the image files I gave in the first post), with the same bailout radius :).
The weird thing is that in Ultra fractal :
- with built-in mandelbrot, those artifacts appear for a quite small bailout radius (like my program)
- with *non* built-in mandelbrot, they appear *too* but for a much bigger bailout radius (try 1e50)

To me, a difference of one iteration does not justify such a difference on acceptable bailout values.
Do you think it is possible that for non built-in formulas, Uf5 uses something more precise that simple C doubles ?

No - because I can turn the "use extra precision" in the options/preferences to "never" and it makes no difference whatsoever.

Under further investigation (since I don't normally ever use the in-built formulas I found that for correct rendering using the built-in formulas if you use a bailout magnitude of m in the main formula then the correct bailout value to give the TIA colouring is m^2 e.g. in UF using the in-built formula try 1e17 for the formula and 1e34 for the TIA colouring.

You are probably correct that when using say 1e40 for both bailouts using the normal formula or 1e20 and 1e40 for the built-in and the TIA then the errors are due to lack of resolution in the mantissa rather than the exponent as I was theorising....

Also if you're used to:

|z| being used strictly to mean the magnitude of z as in formal maths then you need to be aware that UF (and most other fractal siftware) actually interpets |z| as x*x+y*y rather than sqrt(x*x+y*y) which would be an alternative explanation as to why your bailout values when errors begin do not match those in UF.

Of course x^2+y^2 (i.e, magnitude^2) is used for the bailout testing as getting the actual magnitude involves an unnecessary and slow sqrt function call.

Ah ! There it is ! You have the explanation :).
It seems that :
bailout(my program) <=> bailout^2(Ultra fractal built-in mandelbrot)
and
bailout(my program) <=> bailout^4(Ultra fractal *non* built-in mandelbrot)

This can be explained by the two following remarks you made :
I did not know that ! While ultra fractal does check that x*x+y*y<bailout, my program check x*x+y*y<bailout^2 (of course, I don't compute the square root at each iteration, I just pre-compute bailout^2 and then compare if with x*x+y*y).

Then, you were right about the last iteration : after re-reading my code, I found out that I was doing the TIA even for the last iteration. For TIA calculation, there is a difference of one iteration between my program and ultra fractal, and I was wrong saying that this would not make a big difference on bailout value. Indeed |z| doubles (approximately) after each iteration (for classic mandelbrot).

If I make these two modifications in my code (checking x*x+y*y<bailout and skipping calculation for last iteration), I obtain the same thing as Ultra Fractal : artifacts appear for bailout=1E31.
Anyway I prefer keeping my code as it is, I think it makes more sense :
bailout value is compared to |z| (mathematical definition), and I don't skip the last iteration for TIA calculation (why not use the informations of last iteration if I computed it ?).

:) actually the magntude *squares* - its exponent doubles ;)

One reason not use use z from *after* bailout in some calculations is as I said i.e. the fact that if the bailout is large than after the bailout iteration it's possible that the value may have overflowed or will overflow if used in colouring calculations (whereas we know the penultimate value is definitely of magnitude less than the associated bailout.
Other than that I'm not entirely sure ;)

In fact my class colourings such as Smooth Orbit Traps in mmf.ulb I do give users the option of having the colouring loop process the fina iteration after bailout - and of course this results in similar restriction changes to the max possible bailout as with using the TIA colouring.