Welcome to Fractal Forums

Okay, I've been perusing the forums while waiting for my latest deep zoom of the Mandelbrot to render, and I've found a lot of awesome stuff, but not what I was looking for: ideas on how to optimize calculation of the EXTERIOR of the M-Set. I've seen some brilliant stuff (thanks Pauldelbrot et al.) for eliminating chunks that are definitely inside the set, but what I'm rendering now has no points IN the set, but lots close to it. So, any ideas? I'm using C, with GMP for arbitrary precision arithmetic.

I've already implemented a couple of basic things (like saving Re(z)^2 and Im(z)^2 for bound calculations) and I have a couple ideas (like calculating two or four iterations in a row without stopping to check in between) but so far nothing that doesn't tend to cause unacceptable losses in accuracy.

Any ideas?

A while ago I tried to get something going with alternative bailout methods... sadly, it never really took off... I did end up having a couple of weird methods which worked, though... if used, say, once every 5 iterations, they might be of some help. Really, the idea is that anything outside of the anti-buddhabrot can be eliminated. The problem is that it is, well, fractal, so you can't really "cut off" everything around it without using excessive computation. You can always try epsilon-cross methods, I think they can do useful stuff... something like "if Re(z)<(1/(abs(Imag(z))-0.5)) then bailout" or something.

Yeah, I read that, I figured it would be a good idea to open a topic with a less specific title :D The bailout adjustments seem promising, but the inconvenient thing is that I would think that it would tend to mess with the iteration count and therefore the smooth coloring procedure.

Just a thought--are there any holes in the Buddhabrot itself? If there are, then we can simplify calculations by stopping the moment a point enters one of those regions. Or if there aren't, could there be conditional holes? Like, are there places that points with initially positive imaginary components never go?

And now I'm meandering a bit... I wonder if there's any way to adjust for modified bailout. Something like "If calculation terminated early due to reaching such-and-such a bailout condition, then add x to the iteration count."

Would a bog standard level set rendering suffice? For exteriors coloured with just the iteration number, it is possible to skip computation in the flat areas. This can be done either with boundary tracing methods, or with a quadtree (or Kd-tree). These methods are an approximation based on pixel resolution, but they are backed up by the theory. Rendering errors are extremely unlikely to ever affect more than a few pixels.

Yeah, those would be helpful for certain parts (though they'd be fairly likely to cut off fine threads) but the particular image I'm rendering has very little in the way of flat areas. I need to implement boundary tracing, though, that seems very very promising...

How would you implement boundary tracing? Are you talking about a Fractint-esque style, where it "carves out" the level sets of iteration? That way you also won't be able to use any sort of smoothed iteration...

I would also like to mention that, at deep zooms, any "weird" bailouts begin to blend in perfectly. This might indicate that they stop being useful, but in any case they stop messing with the coloring.

The boundary trace methods were popular in the 8 bit days, when floating point arithmetic was implemented in software, and pixel operations could be done purely with cheap integer arithmetic.

The quad/Kd-tree method requires less complex logic, and is probably more suitable with the faster arithmetic these days. The Kd version works like this:

1. Compute top and bottom rows, leftmost and rightmost columns.

2. If all pixels of that whole frame have the same identical number of iterations, fill the rectangle and return.

3. Otherwise split the rectangle in two and compute one single row/column of pixels at the border. Recurse into both halves. (e.g. split the longer edges at midpoint.)

This method fails only if the initial rectangle contains all of the Mandelbrot set. Or, more generally speaking, it fails only when the rectangle contains a disconnected part of the set, which cannot happen for any subset, because the Mandelbrot set is connected.

Theoretically, i.e. if you would not just sample the rectangle border on a pixel grid, but could compute the iteration of all the infinitely many points, then the method would be exact rather than an approximation. I like the method because it works automatically for the interior of the set, too, with no need for further special cases. And the "divide and conquer" type of algorithms can be parallelized naturally.

I have implemented this method in several simple Mandelbrot zoomers over the years, and have yet to encounter an image where it produced visible artifacts. It doesn't cut off antennas, because there is always a bit of a canyon around those infinitely thin structures. So even if no sample point can hit the actual line, there is usually a few pixels with different iteration counts to trigger a subdivision. Only when the rectangle gets very small, like 4x4 or 2x2 pixels, does the probability for errors increase to non-negligible values.

The biggest drawback of the method is that it only works in "boring" areas of the image. Thus experienced Mandelbrot explorers, who tend to zoom into richer collections of ornamental structures, will see less of a speedup.

I suppose that if you're using smoothed iterations, you could do something similar by measuring the difference in color between two successive pixels along the boundary. If this difference is too great, then it should be subdivided; if over the entire rectangle it's only a shallow slope, though, it would be filled in with some interpolation. This has mathematical theory to back it up, too: the slope is actually a pretty close estimate to the derivative of the function, so by just using this value you could get a fairly accurate DE.

Perhaps this would actually be the best way to do it: Calculate the DE at each of the corner points. If the DE is greater than the size of, say, 0.6*(diagonal of rectangle), then subdivide at the middle; otherwise, fill the rectangle with interpolation from the borders.

Has anyone ever tried this? I think it might give great speed-ups, even at relatively deep zooms.

Surely you mean LESS than 0.6 times the diagonal? I see the idea here... you'd get a lot of speedup unless, of course, everything's close to the set. Which would be basically whenever there's a lot of detail in the image. I like the idea, though... seems promising...

Yeah, less.  :embarrass: It's true that it won't work while you're still close to the set, but if you're rendering at a high resolution, it's almost certain that you will eventually subdivide at some point into a relatively open area. I've been thinking maybe a more efficient way would be checking just the center of the rectangle for being close to the set. It would be a lot more efficient when it come to eliminating areas. To double check, use directional estimation, take the center of the side that it points to, and check its Distance Estimate. Assuming it's far enough away, compute the border and extrapolate.

By the way, I think I've got a better idea of how to extrapolate the colors; I'm pretty sure that you can compute the direction of a level set of smoothed iteration - should be a fun exercise. Then maybe also compute the quadratic component, and you can get something like a Bezier curve. This is proving to be a very interesting idea, extrapolating from the borders... and it could give rise to very large speed boosts, I think...

Oooh, the center sounds good... also, for high-detail images, maybe start the subdivisions at smaller rectangles? So that you don't waste calculations on large parts. Also, bear in mind that it's very possible that the center happens to land on a minibrot well below the size of a pixel--so maybe several central pixels, very close together, so that details too small to see are ignored?

Hi guys,

I am new to this forum, but I have also been working on my own Mandelbrot generator for 5 years. I have implemented the interpolating method to speed up the calculation of monotonic areas. My algorithm works like this:
1. Check the bounds of the rectangle for monotonicity. If the parallel bounds are monotonic in the same direction, go to step 2. Else subdivide the rectangle.
2. For each monotonic bounding line, calculate the minimum and maximum of the differences of subsequent values. If abs(max)<abs(min)*threshold, got to step 3. Else subdivide the rectangle. (With lower thresholds the interpolation will be more accurate, but more subdivisions will be required. I use a threshold of 2)
3. For each inner pixel of the rectangle, compute the interpolated value of the four projected boundary pixels. For the interpolation use an average of the weighted boundary values. I experimented with several weights and averages.

Weights:
1. Use the reciprocal of the distance from the boundary
2. Use the distance to the opposite boundary

Averages:
1. Arithmetic mean
2. Geometric mean
3. Harmonic mean
4. Quadratic mean

For a specific calculated image, the difference between the different weights and averages is very subtle and hardly noticeable, assuming the monotonicity threshold is kept low. The best method I found to quantify the accuracy of the different interpolations is to compress the image, and compare the compressed sizes (in bytes). The method with the highest compression ratio will be the best.

A few words about the compression I use:
My program is written in Java. I store the calculated iteration values for the pixels in an array of 32-bit floats. I convert the float values to int using Java's Float.floatToIntBits() method, which creates an int that has the same bit pattern as the float. I then split the int into one 8-bit and one 24-bit chunk (roughly the float's exponent and mantissa), and filter each row's exponent and mantissa values using a differential filter. Then I split the 24-bit mantissa into 3 bytes, create an array of bytes with width*height*4 values, and copy the following values into it:
1. The filtered exponent values
2. The first bytes of the filtered mantissa values
3. The second bytes of the filtered mantissa values
4. The third bytes of the filtered mantissa values
Finally I compress the whole array with java.util.zip.

Based on my measurements, for the majority of images the best weighting method is #2 (by far) and the best averaging method is #3 harmonic mean.

Another benefit of the interpolating method is that it scales well when using oversampling, because monotonic areas will be larger. The effect is similar to adaptive anti-aliasing. One example created with my application:

Original image:
Size: 640x480
Total pixels: 307200
Computed pixels: 158101 (51.47%)

4x4 oversampled image:
Size: 2560x1920
Total pixels: 4915200
Computed pixels: 1710370 (34.80%)

So despite the total pixel count being 16 times higher, the calculated pixel count is only 10.8 times higher.

Greetings, and Welcome to this particular Forum !!!    :)

If you got any images to share, please upload or give a link.  And if you would like beta testers for your program, there are many here that would give it a whirl.    :D
 

@reesej: But DE still wouldn't be able to, very consistently, tell us the size of the object. (That might be interesting to try, though.) And if any part of the set is within the rectangle, the extrapolation from the sides could end up being very inaccurate. By the way, I think I got the formula for the angle of the level sets at any given point: It's the exact same calculations as DE to get the derivative, the only difference being the final result; in leiu of one would use (I think - need to check my maths again) or just if you want the field lines. I'm very excited about these formulas, and I think they might produce pleasing coloring alogrithms! Just to check that they work, would someone mind trying them for me? Just copy the code for the DE formula, and change the final: part to arg(z/zDeriv).  ;D

@kbotond: I would really like to see your program? What is it called? And, one question, did you try using log(abs(max))<log(abs(min))*threshold? Or, I suppose more efficiently, abs(max)<abs(min)^threshold? It sounds like a very interesting technique you're using...

Two more cents on algorithmic ideas ...

 - Skipping rectangular regions with distance estimates works best for squares. So a quadtree would probably win over a Kd-tree. Unless the Kd-tree is modified to prefer square cells.

 - Calculating a DE in the center makes it harder to re-use the result later. Values at corners stay at corners after subdivision. A possible solution would be to subdivide into 3x3 squares rather than 2x2, but that would be less adaptive, so not a clear win.

Here are some low resolution (320x240) examples illustrating the effect of pixel interpolation.
- left: fully computed image
- center: interpolated (partially computed) image
- right: interpolated image showing computed pixels only

As you can see, there is no visible difference between the fully computed and interpolated versions.

Wow, very impressive. What kind of time improvement does it allow? I can see that it would be a LOT faster than basic computation.

I like your method a lot, kbotond, because it doesn't require that all the boundary points have the same escape time, which always struck me as a very hard-to-meet condition.

The time savings come from skipping the computationally intensive z->z²+c iterations, so the higher escape values can be interpolated, the better. The savings depend on two major factors, as I learned:
1. The complexity of the image. The more plain (inside) or monotonic (outside) areas are on the image, the more pixels can be interpolated. Unfortunately, as you zoom in and more fine detail starts to appear, the savings in outside areas converge to zero. After reaching the resolution capability of 64-bit double numbers (at a magnification of ~ 2E-45), the savings become insignificant, especially in the area around minibrots. Inside the minibrots however, the savings can be huge, especially at high maximum count values.
2. The resolution of the image. The higher resolution the image is computed, the higher the ratio of interpolated pixels can be. See the attached images, which show the same area computed without, with 2x2, with 4x4, and with 8x8 oversampling. I got the following savings:
- no oversampling: 72.32% of pixels, 76.89 of iterations computed. Savings: ~23%
- 2x2 oversampling: 59.62% of pixels, 66.11 of iterations computed. Savings: ~34%
- 4x4 oversampling: 48.59% of pixels, 56.50 of iterations computed. Savings: ~43%
- 8x8 oversampling: 39.86% of pixels, 48.66 of iterations computed. Savings: ~51%

(These are the samples for 4x4 and 8x8 oversampling. I couldn't attach them to my previous post.)

That's some serious time savings. I take it the technique never becomes noticeably detrimental?

I have experienced no performance degradations so far. The costs of monotonicity checking and interpolation are lower than that of computing the actual pixel values, by orders of magnitude.

I also considered implementing some kind of boundary tracing algorithm in the past. Since it would require equal boundary point values, it could not be used with continuous coloring, so I dropped the idea and came up with the interpolating technique instead. It proved to be a good trade-off between reasonable savings and nice visuals.

I wonder if this method could be extended? For instance, instead of requiring it to be monotonic, require that it change directions no more than once (like a parabola). Making it line up properly would be tricky though.

Botond, that's really nice. Where do the seemingly random lines come from? They seem the be just as monotonic as everything else, pretty much. I could imagine that they are the places to which either side the iteration increases, but the doesn't explain why there are sometimes two crossing each other, or why they wind back, etc.

Botond: I assume you're using either a linear or a logarithmic color map for turning the smooth iteration values into colors? I tried this algorithm with HPDZ's rank order coloring strategy (http://www.fractalforums.com/programming/non-parametric-color-mapping-techniques/) and it had some very intriguing errors. I think they're fixable, though--I'm going to work on it.

You're right. These lines contain pixels where either the horizontal or vertical line has a local maximum or minimum of iterations. See the attachment. The left image has continuous coloring, the middle one uses integer iteration values only, and the right one shows only the computed pixels. The curves on the right image cross the stripe boundaries at their extreme (leftmost, bottommost etc.) points.

The crossing lines in one of my previous examples (y.png) are a result of some rounding errors produced by the double-double arithmetic (http://www.fractalforums.com/programming/%28java%29-double-double-library-for-128-bit-precision/ (http://www.fractalforums.com/programming/%28java%29-double-double-library-for-128-bit-precision/)). This has no visible effect on the image quality though.

This could be quite tricky, but it could spare the curves demonstrated in my previous post. I will give it a try. Maybe instead of checking the monotonicity of the line, I could check for the monotonicity of the first differential. That could allow such parabolic areas to be interpolated directly.

In fact, when I interpolate large areas, I have to use some "cheating". You can see some computed pixels aligned on a grid inside the large interpolated areas. I need them to avoid false interpolations, because my algorithm cannot decide if the rectangle contains a convex or concave area based on the boundary values only (see attachment). So if the size of the interpolated area exceeds a certain threshold (8x8 pixels), I compute this grid of pixels, interpolate the vertical and horizontal lines between those pixels, then interpolate the resulting small rectangles.

If you can get the second order (parabolic) interpolation to work, it should automatically be able to approximate convex and concave cases.

I am not sure if any kind of interpolation can be precise on a larger area, since the actual pixel values do not follow any analytic function. (If that were the case, it wouldn't be a fractal.) So I would have to use a grid of calculated inner points anyway, only a sparser one. But even the grid I currently use has only 1 calculated point for every 8x8 rectangle, that is only 1.5% of the total pixels.

I have modified my monotonicity checking algorithm. First I implemented a monotonicity check for the differential of the values, but combined with the harmonic interpolation it produced quite a few visual glitches. Then I inserted a threshold into the original monotonicity check:

if(Math.max(Math.abs(minDiff),Math.abs(maxDiff))<THRESHOLD) then monotonic=true;

After trying different threshold values, I found that 0.3 has the most savings while still not distorting the visuals. Here are two examples about the effect of this threshold (left: original monotonicity checking; right: original monotonicity checking + threshold).

As you can see, the curves in the middle of monotonic areas have disappeared. This results in savings of up to 30%, depending on the image.

Wow, that algorithm certainly looks like it's working. Very nice!

where is the difference to "normal" guessing algorithm ?!
and what the heck are these bands, that do not belong to the set, (mostly blue and curly )

@Trifox: The normal guessing algorithm only works if the colors are exactly the same. This works even if they change, and then it interpolates. Guessing does no interpolating.

@Botond:

Actually, they do (I think). Please check out the Riemann mapping theorem: There exists, for any shape in the complex plane, an analytic function mapping the shape to the unit disk. And in the case of Julia sets, the potential can be calculated by taking the inverse of the function and measuring the distance to the disk.

Does this also mean that the actual number of iterations before bailout (and including the fractional part) on a straight line (the boundary of an interpolated area) follows an analytic function?

Those bands are of course not parts of the set, they simply consist of outer points where the iteration count measured on a horizontal or vertical line has a local minimum or maximum. They are not visible on the final (interpolated) image. Also, the newest version of my algorithm eliminates them completely (see my last post with attachments).