Logo by wmauzey - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Support us via Flattr FLATTR Link
 
Home Help Search Gallery Downloads Login Register
*
Welcome, Guest. Please login or register. October 01, 2018, 05:04:01 PM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Welcome to Fractal Forums > Fractal Software > Programming > An obvious optimization for buddhabrot on GPU
Pages: [1]   Go Down
« previous next »
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: An obvious optimization for buddhabrot on GPU  (Read 1998 times)
0 Members and 1 Guest are viewing this topic.
ker2x
Fractal Molossus
**
Posts: 795


WWW
« on: December 02, 2010, 12:09:16 PM »
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 ?
Logged
often times... there are other approaches which are kinda crappy until you put them in the context of parallel machines
(en) http://www.blog-gpgpu.com/ , (fr) http://www.keru.org/ ,
Sysadmin & DBA @ http://www.over-blog.com/
tit_toinou
Iterator
*
Posts: 192
« Reply #1 on: February 22, 2012, 12:13:56 PM »
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  grin .
Logged
How do Complex Numbers warp the plane ?
knighty
Fractal Iambus
***
Posts: 819
« Reply #2 on: March 12, 2012, 07:53:49 PM »
Quote from: tit_toinou on February 22, 2012, 12:13:56 PM
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  grin .
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.  wink
Logged
ker2x
Fractal Molossus
**
Posts: 795


WWW
« Reply #3 on: March 13, 2012, 11:00:09 AM »
Quote from: knighty on March 12, 2012, 07:53:49 PM
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.  wink

indeed  grin
Logged
often times... there are other approaches which are kinda crappy until you put them in the context of parallel machines
(en) http://www.blog-gpgpu.com/ , (fr) http://www.keru.org/ ,
Sysadmin & DBA @ http://www.over-blog.com/
tit_toinou
Iterator
*
Posts: 192
« Reply #4 on: March 17, 2012, 03:10:27 PM »
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."
Logged
How do Complex Numbers warp the plane ?
ker2x
Fractal Molossus
**
Posts: 795


WWW
« Reply #5 on: March 21, 2012, 02:04:30 AM »
Quote from: tit_toinou on March 17, 2012, 03:10:27 PM
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 smiley

I'm trying to port your buddhabrot on Allegro Lisp windows. (right now the 1st error is about bordeaux-threads (not available on windows)
Logged
often times... there are other approaches which are kinda crappy until you put them in the context of parallel machines
(en) http://www.blog-gpgpu.com/ , (fr) http://www.keru.org/ ,
Sysadmin & DBA @ http://www.over-blog.com/
tit_toinou
Iterator
*
Posts: 192
« Reply #6 on: March 24, 2012, 02:13:54 PM »
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.
Logged
How do Complex Numbers warp the plane ?
knighty
Fractal Iambus
***
Posts: 819
« Reply #7 on: March 24, 2012, 02:49:33 PM »
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: Fn(c+E)=Fn(c)+E*Fn'(c)+0.5*E²*Fn''(c)+O(E3) where E is a circle. E=r*exp(i*theta).
Now:
Fn(c+E)-Fn(c)=E*Fn'(c)+0.5*E²*Fn''(c)+O(E3)
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(E3) (if we stop at the second derivative.) in order to obtain a conservative bounding circle.
« Last Edit: March 24, 2012, 03:19:46 PM by knighty » Logged
Pages: [1]   Go Down
« previous next »
  Print  
« previous next »
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Fractal search/optimization General Discussion twinbee 7 1557 Last post April 08, 2008, 01:56:05 PM
by cKleinhuis
Mandelbrot Exterior Optimization Programming « 1 2 3 » reesej2 35 7112 Last post April 15, 2010, 11:34:37 PM
by Botond Kósa
Major Raymarching Optimization Mandelbulb Implementation keldor314 8 4727 Last post December 27, 2013, 08:48:22 PM
by Syntopia
reflection rendering speed optimization Mandelbulb 3d dryo 3 3046 Last post February 20, 2012, 01:24:41 PM
by PhotoComix
raymarching optimization using golden ratio ... General Discussion cKleinhuis 4 1626 Last post December 29, 2012, 12:21:32 PM
by cKleinhuis

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.535 seconds with 24 queries. (Pretty URLs adds 0.076s, 2q)