Beta Mandelbrot Set Generator For Pandora

[centus]

Here's a little something I've been working on, it's a pretty simple Fractal generator which currently does Mandelbrot set.
It supports zoom in and out, panning, changing the number of iterations which is needed when you zoom in a lot and want to see more details, when you increase the number of iterations, though, performance goes down, so be warned... it is currently capped at 20000 which should be enough for the amount of zoom possible using double precision variables for the calculations (which I am).

It uses SDL, so should be easy to recompile to Pandora once it finally gets here...

Attached is a zip with both a 64-bit Linux executable (I'm almost sure it is 64-bit... and an XP 32-bit version.

Some notes on how to use it:
mouse left click = center + zoom in
mouse right click = center + zoom out
mouse middle click = center
+ = increase iterations by 20
CTRL + = increase iterations by 100
SHIFT + = increase iterations by 500
ALT + = increase iterations by 2000
- = decrease iterations by 20
CTRL - = decrease iterations by 100
SHIFT - = decrease iterations by 500
ALT - = decrease iterations by 2000
s = save BMP file (numbered since current run began)
r = reset all (goes back to initial zoom and iterations (100 iterations)

There is still a lot of work to be done with the controls and I'm planning on adding a help screen, but I think I'll wait for the Pandora to figure out the best controls...

Let me know what you think, any suggestions, comments, flames are welcome.
Also attached a screenshot done with it, currently it only saves BMP but will be changed to PNG...

 

[dflemstr]

Works awesomely!

Some things you might want to consider adding:

• Easy:
  • Display the zoom box while you're dragging the mouse
  • Adjust the max number of iterations for the Mandelbrot function when you zoom in automatically
  • Use a distance estimation algorithm to make the coloring "smooth"
• Medium:
  • Allow for custom palettes
  • Use more accurate numbers, e.g. not floats or doubles but something more precise that allows you to zoom in ad infinitum
  • Do binning to avoid recalculating the same pixel twice. E.g., if you've already calculated the number of iterations for coordinate (x, y) and stumble upon that coordinate when calculating another pixel, just take the number of iterations for (x, y), add the current number of iterations for the current pixel, and escape quickly
  • Anti aliasing! Add the option to render an image that is x times larger than your screen, and downscale it. Bonus points if you manage doing it without using an x² times as large buffer
• Hard:
  • Calculate chunks in separate threads (using two threads, no more, no less, should give an advantage on ARM afaik).
  • Calculate the fractal with interleaving so that the user at first gets a blurry approximation and then a more accurate version of the fractal as time goes by
  • Add support for more fractals

If you do all of this, you'll almost be at the level of XaoS!

BTW: Yes, the executable is Linux x86_64

 

[centus]

Works awesomely!

Some things you might want to consider adding:

• Easy:
  • Display the zoom box while you're dragging the mouse

• 
  Done originally, removed for easier Pandora porting, I was told that click+drag is not that simple on a touch screen...
  
  

  • Adjust the max number of iterations for the Mandelbrot function when you zoom in automatically
  • Use a distance estimation algorithm to make the coloring "smooth"

  Both on my to-do list, thanks for the thought though.
  
  

  [*]Medium:
  

  • Allow for custom palettes
  • Use more accurate numbers, e.g. not floats or doubles but something more precise that allows you to zoom in ad infinitum
  • Do binning to avoid recalculating the same pixel twice. E.g., if you've already calculated the number of iterations for coordinate (x, y) and stumble upon that coordinate when calculating another pixel, just take the number of iterations for (x, y), add the current number of iterations for the current pixel, and escape quickly
  • Anti aliasing! Add the option to render an image that is x times larger than your screen, and downscale it. Bonus points if you manage doing it without using an x² times as large buffer

  Hmm... well, the first one would kill performance, went with doubles because they give a good enough level of zoom without being too difficult to hard on the CPU, any thoughts on how to optimize performance?
  As for the second and third, they would both require a large amount of memory, but come to think of it, this code is based on a similar application I wrote for a Cowon A2 (used to own one before it was stolen), I guess I can use a bit more RAM with the Pandora.. I've been thinking small and thin as possible, but there really isn't any reason... Thanks!
  
  

  [*]Hard:
  

  • Calculate chunks in separate threads (using two threads, no more, no less, should give an advantage on ARM afaik).
  • Calculate the fractal with interleaving so that the user at first gets a blurry approximation and then a more accurate version of the fractal as time goes by
  • Add support for more fractals

If you do all of this, you'll almost be at the level of XaoS!

BTW: Yes, the executable is Linux x86_64

OK I did the second one initially, I didn't do it well so it just took longer for the calculation, I'll re-do it nicer so that the performance hit isn't as big as re-calculating everything.
Are you sure about the first one? I was thinking of going with threads but wasn't sure how the ARM is with those.
Third one is a given...

Thanks for the good review, really appreciated!

Oh, and by the way, loved your Panorama, I will definitely be installing it!

 

[lulzfish]

It would be nice if your fractal.zip had a subdirectory so the files stay in one place when I unzip them.

Also, you can check *Edit: Check whether your system is* 32 bit vs. 64 bit by calling "uname -a" from a terminal and looking for a x86_64 in there.

 

[dflemstr]

@lulzfish I found out via "file fractal"

• Easy:
  • Display the zoom box while you're dragging the mouse

Done originally, removed for easier Pandora porting, I was told that click+drag is not that simple on a touch screen...

I don't see why it wouldn't be simple. The touch screen works just like a mouse afaik, e.g. when you drag your finger it triggers the same action as when you click and hold a mouse.

• Medium:
  • Allow for custom palettes
  • Use more accurate numbers, e.g. not floats or doubles but something more precise that allows you to zoom in ad infinitum
  • Do binning to avoid recalculating the same pixel twice. E.g., if you've already calculated the number of iterations for coordinate (x, y) and stumble upon that coordinate when calculating another pixel, just take the number of iterations for (x, y), add the current number of iterations for the current pixel, and escape quickly
  • Anti aliasing! Add the option to render an image that is x times larger than your screen, and downscale it. Bonus points if you manage doing it without using an x² times as large buffer

Hmm... well, the first one would kill performance, went with doubles because they give a good enough level of zoom without being too difficult to hard on the CPU, any thoughts on how to optimize performance?

The first one? Using palettes? Shouldn't be that much of a performance-eater.
In case you meant the second point then yes, it would indeed kill performance (doubles are already incredibly slow on the Pandora from what I've been told; I would avoid using even those, at all, if I were you). But it might be an idea to maybe switch rendering engine based on zoom level? Would make this more difficult to implement, though. Just a thought.

As for the second and third, they would both require a large amount of memory, but come to think of it, this code is based on a similar application I wrote for a Cowon A2 (used to own one before it was stolen), I guess I can use a bit more RAM with the Pandora.. I've been thinking small and thin as possible, but there really isn't any reason... Thanks!

Well, binning shouldn't use any more memory than your current implementation. You keep the bitmap of the fractal in memory anyways, right? And, that bitmap is presumably not (at first) one containing color information, but instead the escape time for every pixel, right? So, in your Mandelbrot function, do this:

//Just using a basic algorithm here because I have no idea which one you're using
//Assuming: 
// - result is an array of ints containing the escape time for each pixel
// - maxIter is the max number of iterations
float re0 = transformX(xCoord); // transformX could be something like (xCoord / (float)width) * 4f - 2f
float im0 = transformY(yCoord); // might do something like (yCoord / (float)height) * 3f - 1.5f
float re = re0;
float im = im0;
int iter = 0;

while((im * im + re * re < 4f) && iter < maxIter)
{
   float newRe = re * re - im * im + re0;
   im = 2 * re * im + im0;
   re = newRe;

   //Do a "bin check"
   int resX = untransformY(im);
   int resY = untransformX(re);
   int resIter = result[resY * width + resX)]; //Boundary checks omitted
   if(resIter > 0)
   {
     result[yCoord * width + xCoord] = resIter + iter;
     break;
   }
   iter++;
}
result[yCoord*width + xCoord] = iter;
//(Don't blame me if this doesn't compile; haven't tested it)

Anti-aliasing will indeed consume more memory, so yeah.

• Hard:
  • Calculate chunks in separate threads (using two threads, no more, no less, should give an advantage on ARM afaik).
  • Calculate the fractal with interleaving so that the user at first gets a blurry approximation and then a more accurate version of the fractal as time goes by
  • Add support for more fractals

If you do all of this, you'll almost be at the level of XaoS!

BTW: Yes, the executable is Linux x86_64

OK I did the second one initially, I didn't do it well so it just took longer for the calculation, I'll re-do it nicer so that the performance hit isn't as big as re-calculating everything.
Are you sure about the first one? I was thinking of going with threads but wasn't sure how the ARM is with those.
Third one is a given...

Second one does usually add some performance overhead, but it can be done in a nice way, too. E.g., when you try to implement something like that, you usually try to just draw 5x5 squares for the first iteration, 2x2 squares for the next two iterations, and individual pixels for the last iteration, right (if you want a total of 4 iterations)? If you let SDL do this, it will be slow as heck, but if you abuse the fact that you're drawing actual squares and draw them yourself, you can do some optimizations, e.g. by unwinding the loop that the SDL rect implementation would otherwise use. With ARM vector instructions, this should make it possible to draw all 25 pixels of a 5x5 square "simultaneously" aka with many less instructions than you would have needed otherwise.

The ARM CPU can execute several instructions at once under certain conditions, but I'd have to look more into that as I don't know how that is implemented/abused. Either way, threading shouldn't hurt (because the overhead isn't that huge when using threads, and you don't have to change anything once you decide to port the application to e.g. a CPU with multiple cores)

Glad to hear that you won't just do Mandelbrot!

BTW, this kind of program might be fun to construct using GLSL, I might try to do something like that...

 

[centus]

Could you explain the bit about the subdirectory?
I just assumed whoever needs the linux one will take just that out of the ZIP and whoever wants the XP would only unzip that file, why would you want a Subdirectory?

Just read the next post and got your problem, well, sorta, isn't it a given that a file with a .exe extension is a windows/dos executable? I was working under that assumption... sorry if I was wrong.

As for the uname -a, thanks! I've been looking for that command, I remembered umask for some reason...

 

[centus]

@lulzfish I found out via "file fractal"

• Easy:
  • Display the zoom box while you're dragging the mouse

Done originally, removed for easier Pandora porting, I was told that click+drag is not that simple on a touch screen...

I don't see why it wouldn't be simple. The touch screen works just like a mouse afaik, e.g. when you drag your finger it triggers the same action as when you click and hold a mouse.

I'll put it back in then, I kept that code somewhere...

• Medium:
  • Allow for custom palettes
  • Use more accurate numbers, e.g. not floats or doubles but something more precise that allows you to zoom in ad infinitum
  • Do binning to avoid recalculating the same pixel twice. E.g., if you've already calculated the number of iterations for coordinate (x, y) and stumble upon that coordinate when calculating another pixel, just take the number of iterations for (x, y), add the current number of iterations for the current pixel, and escape quickly
  • Anti aliasing! Add the option to render an image that is x times larger than your screen, and downscale it. Bonus points if you manage doing it without using an x² times as large buffer

Hmm... well, the first one would kill performance, went with doubles because they give a good enough level of zoom without being too difficult to hard on the CPU, any thoughts on how to optimize performance?

The first one? Using palettes? Shouldn't be that much of a performance-eater.
In case you meant the second point then yes, it would indeed kill performance (doubles are already incredibly slow on the Pandora from what I've been told; I would avoid using even those, at all, if I were you). But it might be an idea to maybe switch rendering engine based on zoom level? Would make this more difficult to implement, though. Just a thought.

Yeah, meant the second one... been thinking of how to implement user-controlled palettes, I definitely want to add that...
As for switching rendering engine based on zoom, I was toying with the idea of going with long integers for the first few levels of zoom, been wanting to try it out for a while.. I like the idea of switching to doubles and (god forbid) to floats when the zoom level increases.

As for the second and third, they would both require a large amount of memory, but come to think of it, this code is based on a similar application I wrote for a Cowon A2 (used to own one before it was stolen), I guess I can use a bit more RAM with the Pandora.. I've been thinking small and thin as possible, but there really isn't any reason... Thanks!

Well, binning shouldn't use any more memory than your current implementation. You keep the bitmap of the fractal in memory anyways, right? And, that bitmap is presumably not (at first) one containing color information, but instead the escape time for every pixel, right? So, in your Mandelbrot function, do this:

//Just using a basic algorithm here because I have no idea which one you're using
//Assuming: 
// - result is an array of ints containing the escape time for each pixel
// - maxIter is the max number of iterations
float re0 = transformX(xCoord); // transformX could be something like (xCoord / (float)width) * 4f - 2f
float im0 = transformY(yCoord); // might do something like (yCoord / (float)height) * 3f - 1.5f
float re = re0;
float im = im0;
int iter = 0;

while((im * im + re * re < 4f) && iter < maxIter)
{
   float newRe = re * re - im * im + re0;
   im = 2 * re * im + im0;
   re = newRe;

   //Do a "bin check"
   int resX = untransformY(im);
   int resY = untransformX(re);
   int resIter = result[resY * width + resX)]; //Boundary checks omitted
   if(resIter > 0)
   {
     result[yCoord * width + xCoord] = resIter + iter;
     break;
   }
   iter++;
}
result[yCoord*width + xCoord] = iter;
//(Don't blame me if this doesn't compile; haven't tested it)

Hmm... I'm a bit confused, why would you add the current iteration number to the original result? could you elaborate on the whole 'binning' concept?

You mention GLSL, is that like OpenGL ES?
What would be the benefit of using OpenGL instead of SDL? currently I only Flip the physical screen after drawing a third at a time, I found out the worst performance hit was when I was drawing each pixel as I calculate them, when I do the whole screen at once I get the best performance but then it is sometimes annoying (waiting 10 seconds for an update).
Would OpenGL make the drawing of single pixels faster?

Thanks for the help.

 

[dflemstr]

Hmm... I'm a bit confused, why would you add the current iteration number to the original result? could you elaborate on the whole 'binning' concept?

OK, imagine that you're somewhere in the middle of calculating the fractal, and you're rendering at some random zoom level. Then, let's say that you're currently on some random pixel, e.g. (x = 352, y = 723). You convert those pixels to a complex number (re = 0.5, im = 0.4) (which isn't realistic but just for the sake of this example...) and start running the algorithm on them.
The numbers then change each iteration like this (again, unrealistic made-up permutation):
(0.54, 0.45)
(0.32, 0.42)
(0.10, 0.31)
...
And then your algorithm notices, "Hey, I already calculated the value for (0.10, 0.31) which corresponds to the pixel (x = 256, y = 742), I've already calculated that pixel, so I know what will come for (re, im) in the next iterations!". Because it knows that, it also knows that it will take, let's say, an additional 272 iterations to finish the current pixel, because that's the value at (x = 256, y = 742), so it just adds the value of the other pixel to the local number of iterations and breaks out.

This probably isn't as easy as I've made it out to be; I've probably forgotten how you should deal with re0 and im0 that are offsets in the algorithm but I'm too tired to remember right now

You mention GLSL, is that like OpenGL ES?
What would be the benefit of using OpenGL instead of SDL? currently I only Flip the physical screen after drawing a third at a time, I found out the worst performance hit was when I was drawing each pixel as I calculate them, when I do the whole screen at once I get the best performance but then it is sometimes annoying (waiting 10 seconds for an update).
Would OpenGL make the drawing of single pixels faster?

GLSL is a programming language for describing how things are to be drawn in OpenGL. It has the benefit that whatever you write in GLSL gets executed massively-parallel on the graphics card.
It works like this:

• You tell OpenGL to draw for example a rectangle (let's say that it is 800x480 in size, *hint* *hint*), passing in a shader program which is a compiled GLSL program.
• OpenGL executes one part of that shader program on the graphics card called the "vertex program". It's not necessary to mention what it does in this context.
• OpenGL then executes what is called the "fragment program" of the shader. Now, this is more interesting. OpenGL will basically take each pixel (aka fragment) that is to be rendered, and execute a small program for each of those pixels. That program will determine the color information for that pixel.
  The layout of a fragment program is really simple: There's a main method, a number of built-in variables (I don't know how many of them are present in OpenGL ES 2.0 though) that you can use, a number of built-in functions etc. The main method has to, at some point, write to a variable called "gl_FragColor", that determines the color of the fragment.
  Short example, this would generate a completely red rectangle:
  

  void main(void)
  {
    gl_FragColor = vec4(1.0, 0.0, 0.0, 1.0); //R, G, B, A
  }

  Result: http://i47.tinypic.com/22xr42.png
  
  ...and this would generate a horizontal green/vertical red gradient that repeats every 100x100 pixels:
  

  void main(void)
  {
    //Gets the current frag's coordinate in screen coordinates... 
    //This is just a hack; you usually use gl_TexCoord[0] + some related stuff instead
    vec2 coord = gl_FragCoord.xy;
    //Sets the color. "mod" is a modulo function, but it works on floats as well as ints
    gl_FragColor = vec4(mod(coord.y, 100.0) / 100.0, mod(coord.x, 100.0) / 100.0, 0.0, 1.0);
  }

  Result: http://i48.tinypic.com/2rmrv9e.png

As you might imagine, this method of drawing would be very well suited for drawing fractals on the SGX on the Pandora. With this, you could easily get live zooming or something like that, because GLSL is *really* fast. You would probably save some performance, since the SGX is optimized for doing this stuff, while the main CPU has to struggle to do rendering like this.

 

[lulzfish]

GLSL would use pixel shading code on the GPU. It would be a zillion times faster and a few times less accurate than CPU rendering. Even with a mobile graphics chip like the SGX, it might be near real-time. Somebody should test it.

I've done GLSL Mandelbrots before, it's great. :lol: Sadly, I think I deleted the code as I wasn't sure whether zooming should be a transform or a uniform and it got really screwed up and I broke it.

 

[dflemstr]

GLSL would use pixel shading code on the GPU. It would be a zillion times faster and a few times less accurate than CPU rendering. Even with a mobile graphics chip like the SGX, it might be near real-time. Somebody should test it.

In GLSL 1.5, you are able to specify the accuracy of your floats (not whether to use doubles but rather one of "highp", "mediump" or "lowp" e.g. "highp float color = 1.0 / 3.0" is usually a 64-bit double).

I've done GLSL Mandelbrots before, it's great. :lol: Sadly, I think I deleted the code as I wasn't sure whether zooming should be a transform or a uniform and it got really screwed up and I broke it.

You should have chosen an uniform
There's nothing called a "transform" variable, did you mean "varying"? Or did you actually want to transform the rect you rendered to zoom in?

BTW, the best OpenGL reference in extstence:
http://www.khronos.org/files/opengl-quick-reference-card.pdf

 

[centus]

Thanks guys, sounds like a very interesting learning experience, I'll get to it...

 

[centus]

dflemstr, I went ahead and attempted your binning algorithm, but something doesn't add up, according to your code snippet, if I break out of the while when the bin check comes back positive, I still replace the value in the result array with the current value of iter (since it is the next command after the while within the larger loop of xcoord/ycoord).

I tried just setting the iter variable to iter+result_iter inside the bin test (before the break) but that only produced weirder stuff, the first 50 or so lines looked almost normal but then it went to hell with some strange looking non-mandelbrot fractal...

Any thoughts?

 

[dflemstr]

As I said, that was unchecked pseudocode I posted (I was on a jailed Windows-computer without anything resembling a C compiler) so I just wanted to convey the general gist of how it'd work, and not post working code.

The strange fractal you're getting comes from the fact that you don't consider "re0" and "im0" when determining the untransformed position (neither did I as you can see). The actual bin you want to check is at an offset and I think that you need something like the Riemann zeta function to determine where that is... I might do some research for you if I get time for it.

 

[centus]

Hey dude, I'm sorry if I came across as blaming, was just stating that it didn't work and I had no idea why.
Your logic made perfect sense to me, but I don't get your note about re0 and im0, don't we take them into account when we convert the current re and im to pixels? I mean, the conversion to pixels before the first iteration is a conversion of re0 and im0 into pixels, after that we look at the current re and im per iteration and see if it has jumed to a place we already calculated by converting re and im back to pixels using the same logic used for re0 and im0, but we don't need to use re0 and im0 again for that, only the xstart/ystart and xincrement yincrement, right?

I must admit my math knowledge is one of an biology undergraduate...

Thanks for all your help, it IS appreciated.

 

[dflemstr]

Your logic made perfect sense to me, but I don't get your note about re0 and im0, don't we take them into account when we convert the current re and im to pixels? I mean, the conversion to pixels before the first iteration is a conversion of re0 and im0 into pixels, after that we look at the current re and im per iteration and see if it has jumed to a place we already calculated by converting re and im back to pixels using the same logic used for re0 and im0, but we don't need to use re0 and im0 again for that, only the xstart/ystart and xincrement yincrement, right?

OK, so I'll try to clarify what I mean.

I'll go into some mathematics here so if you don't want to bother with such matters, you'll find a tl;dr at the end.

Remember that the formula/function/equation/whatever for the Mandelbrot set is:

...where

is an iterative function,

is the variable that is being iterated, so

in the program, and

is the "offset variable" so that

. All variables are in the complex plane ℂ (think of it like that every number is a 2D number, with a real part and imaginary part, like the X's and Y's of a coordinate).

What this means for the non-mathematician, is that every pixel of the fractal is calculated exactly the same way, except for that they each have a different input variable c (obviously). In the program, that c corresponds to the coordinate that you want to draw. So, in pseudo code, the (mathematical) Mandelbrot equation can be written like this:

complex c = currentCoordinate;
int iterations = 0;
complex z = 0;
//4 is the bailout value; if z aka (re*re + im*im) is more than 4, it will eventually escape to infinity
//The abs() function takes the pythagorean absolute length of the vector it is given.
while(abs(z) < 4)
{
    z = z² + c;
    iterations ++;
}

Now, imagine the following situation:

You're trying to determine the colors of pixels a and b. You would normally of course not calculate them in parallel, but for this visualization, let's say that they are calculated at the same time. Also, note that this isn't a realistic calculation that is actually depicting a part of the Mandelbrot set, it's just been drawn at random.
So, a starts out with the coordinates (re0 = 6, im0 = 3) and b starts out with (re0 = 7, im0 = 5).
They then go through the iterations:

a 5|5 3|5 2|3 3|2 4|3
b 4|6 2|5 1|3 2|1 4|1 5|2 4|3

...where coordinates are represented as "re|im".

Now, note that the two pixels happen to collide with one another at (re = 4, im = 3). It is in this kind of situation that it is possible to perform a binning optimization, since if you know the path of e.g. a, you can predict the path of b.

However, the thing to be aware of here is that although the z variable of a and b are in the same location, they do not share the same direction, and this is because they don't have the same c variable. So, you can't predict the path of b without some knowledge about how c is going to affect the path of b relative to a in the future.
Makes sense?

Another way to think about it: Imagine that c is e.g. 1. This means that the z variable will be "pulled" one step to the right every iteration because c adds a 1 to the coordinate. If c had been something else, it would have "pulled" z in a different direction.

So, in order to perform this optimization, you need to know which direction the z variable of a had when it passed through (4, 3), and predict how this affects the direction of b.

tl;dr: The lazy man's way of doing this is to, in the "result" array, store not only the number of iterations each pixel had when it finished, but also what the value of (re0, im0) aka c was. Then, to perform the binning operation, you have some kind of threshold value EPSILON that is small enough for it not to matter, but big enough to be bigger than 0. Choosing a good EPSILON value is essential for the optimization to succeed. A good idea would be to make it dependent on the zoom level, because if you choose a large EPSILON that yields a good image at 100% zoom, it might be that it introduces artifacts when at e.g. a zoom level of 1600%. I would try setting "EPSILON = 1 / (heightOrWidthOfWindow * zoomLevel)" or some such (it really depends on how your algorithm works).
You then perform a test like: "if((re*re + im*im)/iter - (otherRe*otherRe + otherIm*otherIm)/otherIter > EPSILON)" as the condition for the binning (combined with "resIter > 0" of course), and then proceed as normal.

What this does is that it checks if the both c values are different enough for it to have a major effect on the path of the pixel, and if it doesn't, which it doesn't if the change it would introduce is smaller than the width of one pixel, it can proceed with the binning.

This will require some fiddling to get to work perfectly, because these algorithms are very sensitive to tiny inaccuracies. It might be best for you to have a look at how some open source fractal rendering software has implemented their algorithms to get some inspiration.

 

[lulzfish]

That seems like it would be nearly impossible to pull off, and require huge amounts of memory.
You say it's actually been used?

 

[dflemstr]

That seems like it would be nearly impossible to pull off, and require huge amounts of memory.
You say it's actually been used?

What is your definition of impossible? As I demonstrated at the end of the post, it's really easy to implement, although I have not tested it (I'm lazy). And if it doesn't work as is, then note that I from the start said that this would be difficult to implement.
And yes, I've seen it being used, but only in commercial software like UltraFractal where I had to deduce how it worked by looking at a (scripted) alternate implementation (but I never got to see the actual built-in version that was used), and I think that XaoS uses/used something similar but that was based on a bloom map for the (c, iter) combinations.

I'll look up the source code for you if I can find it, but no guarantees.

EDIT: Ah, whatever, I didn't find what I was looking for, so it might be that this kind of algorithm isn't as widespread as I had thought. I've seen it work, though, but it shouldn't necessarily be on the high-priority list to get working any time soon

 

[gp32rich]

Here's an idea that I used years back to massively increase draw speeds...

split the area into boxes and test the corners / edges / midpoints - however many points and if they are all the same you can infer that the whole of the box is the same and can just block colour it all.

Use recursion to find smaller and smaller boxes until it pops out at a single pixel
For more accuracy at high detail levels - increase the number of points to be tested

Example.
The zoomed out set the four corners (outside the main set) each return '1' the centre point will bail out after [iter]
so then you check four boxes each a quater size (or nine, or sixteen, or ...)

this reduced run time of a zoomed out set on a 386 to a tenth in turboPascal
[but later converted to c] I prolly have the code somewhere if you like but it is just repeated calls to TestBox(x[],y[])


The only drawback is the page is drawn non-linearly and doesn't appear smoothly

 

[dflemstr]

Here's an idea that I used years back to massively increase draw speeds...

split the area into boxes and test the corners / edges / midpoints - however many points and if they are all the same you can infer that the whole of the box is the same and can just block colour it all.

Hey, this, I hadn't thought of. This should *really* speed things up, at least as long as you don't use distance estimation for the shading. Very good idea!
It won't work as soon as you zoom out so that the whole Mandelbrot set is inside one of the rectangles but hey, you can just disable it then.

 

[gp32rich]

Here's an idea that I used years back to massively increase draw speeds...

split the area into boxes and test the corners / edges / midpoints - however many points and if they are all the same you can infer that the whole of the box is the same and can just block colour it all.

Hey, this, I hadn't thought of. This should *really* speed things up, at least as long as you don't use distance estimation for the shading. Very good idea!
It won't work as soon as you zoom out so that the whole Mandelbrot set is inside one of the rectangles but hey, you can just disable it then.

And if you zoom so that a stalk goes through parts you're not testing, so at high zoom levels some detail can be lost, but it just means increasing the number of points to test, or plot everything anyway.
The bin-check should be used so the same points aren't repeatedly tested too.

Thinking about it. I first saw this in 'TurboBrot' for Amiga waaay back in the early 90's before implementing it myself on 16 colour EGA.
Can't seem to find any mention of it now

The only drawback is the non-linear drawing pattern isn't 'pretty' to watch.