An obvious optimization for buddhabrot on GPU

[ker2x]

I don't know why i never tought about it, it's really obvious.
Please correct me if there is a flaw in my logic.

Step 1 :
Generate a high resolution, high iteration mandelbrot where : 0 = not escaping. uint32 = nb of iteration required to escape.
Now you have a nice uint32 2D array that indicate the number of iteration need to escape.
That could be done on gpu (but it's not the subject of this thread)

Step 2 :
Now you want to generate a buddhabrot with a minimum iteration and a maximum iteration.
Parse the mandelbrot array and select all elements where : min-iteration > elements -> max-iteration
Create a new array from that selected points.

Step 3:
Now you have a good estimation of points that are, or not, in the "nb of iterations to escape the MSet" boundaries you needed.

Step 4:
Create one or more gpu thread per elements of the newly created 2D Array.

Step 5 :
You probably want sub-pixel resolution so compute the "size of a pixel" and you will select random real/imaginary point inside this pixel.
You will have to check, or not (if you accept to have some orbit that never escape), if the sub-pixel point selected is really escaping.
draw the orbit.

Step 6:
Enjoy.


Doing that, you should have a much greater luck to pick points of interest instead of doing the usual Monte Carlo method.
I'll try to take some times to write that.
Why can't see why it couldn't work, isn't it ?

[tit_toinou]

The flaw : Max_UINT32 = 2^32 = 4 294 967 295
( Max_UINT32 ) ^ 2 = 2^64
So you have 2^64 int (they indicate each the number of iteration to escape) = 4*2^64 octets = 4*2^34 GiB !!
Impossible to compute it and to store it  .

[knighty]

The flaw : Max_UINT32 = 2^32 = 4 294 967 295
( Max_UINT32 ) ^ 2 = 2^64
So you have 2^64 int (they indicate each the number of iteration to escape) = 4*2^64 octets = 4*2^34 GiB !!
Impossible to compute it and to store it  .

If I understand well, he is not talking about an ( Max_UINT32 ) ^ 2 sized array but a high resolution (without specifing size) 2D array containing uint32. 

[ker2x]

If I understand well, he is not talking about an ( Max_UINT32 ) ^ 2 sized array but a high resolution (without specifing size) 2D array containing uint32. 

indeed 

[tit_toinou]

Okay. My program is doing something similar, it's working well !

However I have read it here :
http://erleuchtet.org/2010/07/ridiculously-large-buddhabrot.html
"To partly remove some of the costly larger areas (like the non-circular bulbs labeled "3" and up in the image above) from within the Set i divided the plane into rectangular cells and chose random samples only from those cells that contained some part of the border of the Mandelbrot Set. Depending on the cell grid resolution and the iteration depth this gave a speedup of 3 to 8."

[ker2x]

Okay. My program is doing something similar, it's working well !

However I have read it here :
http://erleuchtet.org/2010/07/ridiculously-large-buddhabrot.html
"To partly remove some of the costly larger areas (like the non-circular bulbs labeled "3" and up in the image above) from within the Set i divided the plane into rectangular cells and chose random samples only from those cells that contained some part of the border of the Mandelbrot Set. Depending on the cell grid resolution and the iteration depth this gave a speedup of 3 to 8."

Ho... hey, btw... i love your 4k intro

I'm trying to port your buddhabrot on Allegro Lisp windows. (right now the 1st error is about bordeaux-threads (not available on windows)

[tit_toinou]

The blog is not mine. I was quoting this page that's all.
It is the only source on the internet about a "partially developed but high iterations orbits buddhabrot", which is what i'm interested in right now.

[knighty]

I think it is possible to develop this optimization (which is also useful when using CPU) by using DE (which is roughly comparable to constant iteration band's width) and Taylor expansion of the nth iterate.
1- Avoid processing interior points by using interior DE.
2- Avoid processing exterior points that do not contribute when zooming.
Say F(z)=z²+c.
The Taylor expansion is: F_n(c+E)=F_n(c)+E*F_n'(c)+0.5*E²*F_n''(c)+O(E³) where E is a circle. E=r*exp(i*theta).
Now:
F_n(c+E)-F_n(c)=E*F_n'(c)+0.5*E²*F_n''(c)+O(E³)
is a cycloid. It should be possible to get an appoximate (but sufficiently accurate) bounding circle of that cycloid and use it to determine if the area defined by the circle c+E contribute to the buddhabrot. That area will be rejected if all its iterates don't intersect the rendered area, if one of them is completely inside it is retained and if they intersect it will be subdivided up to some predetermined depth.

The main problem is related to the estimation of the O(E³) (if we stop at the second derivative.) in order to obtain a conservative bounding circle.