kay@warwick.UUCP (Kay Dekker) (11/04/85)
I've been writing a 'browser' to examine the Mandelbrot set for interesting
areas. It works fine, except for one thing which I haven't been able to
fathom.
The browser decides that a point lies within the set if its magnitude after
a maximum number of iterations is < 2.0.
I've seen browsers posted recently in net.sources, and examined them to see
if they address my difficulty, but no luck.
How should one choose the maximum number of iterations for any particular
region of the complex plane? Sure, one can always pick a value that's
"big enough" for any particular view ("big enough" meaning, intuitively,
that not too many pixels are marked as lying within the set when in fact
they aren't), but having such a large value makes the browser far too slow
when that many iterations aren't needed.
Is there a method for finding adequate values for the maximum? Or must
I continue to rely on trial and error?
Any help or pointers to information gratefully received.
Kay.
--
"Be careful: the system is complex and chaotic, though it
has many attractive features..."
_The Pot-holes of the Yorkshire Moors_
... mcvax!ukc!warwick!flame!kaycsdf@mit-vax.UUCP (Charles Forsythe) (11/10/85)
In article <2346@flame.warwick.UUCP> kay@flame.UUCP (Kay Dekker) writes: >How should one choose the maximum number of iterations for any particular >region of the complex plane? Sure, one can always pick a value that's >"big enough" for any particular view ("big enough" meaning, intuitively, >that not too many pixels are marked as lying within the set when in fact >they aren't), but having such a large value makes the browser far too slow >when that many iterations aren't needed. The "browsers" that I've seen choose a maximum number of 1000, and I think it's arbitrary. The programs also check, on each iteration, whether or not |z|>2. It seems to me, you could increase the maximum iterations to any number. That way, you could intelligently evaluate points that require more than 1000 iterations, while also including those that require less. The only problem is that you increase your wait -- I think that 1000 was picked because they figured that was "long enough." -- -Charles
hutch@sdcsvax.UUCP (Jim Hutchison) (11/11/85)
In article <2346@flame.warwick.UUCP> kay@flame.UUCP (Kay Dekker) writes: > >The browser decides that a point lies within the set if its magnitude after >a maximum number of iterations is < 2.0. > Is this the set relating to the inverse function f(z) = z^2 + c? I guess that is what you are up to (Really, there is much more). You get to iterate the function. It is infact very time consuming. If you wish to just get outlines, then it is cheaper (use error analysis, see also Bresenham, who is never sufficiently blessed). The reason for the choice of 2.0 is that for this given function, if it passes the value of 2.0, then it is going to go to infinity (which is what you are really checking for). The "Mandelbrot Space", (not my term, just as a touchstone), is the area where the function never goes to infinity. The pretty colors ('stones'), are chosen by the speed at which practical infinity is reached. 2.0 = infinity, for proper values of 2.0 :-) >"Be careful: the system is complex and chaotic, though it > has many attractive features..." > _The Pot-holes of the Yorkshire Moors_ Fractals? -- /* Jim Hutchison UUCP: {dcdwest,ucbvax}!sdcsvax!hutch ARPA: hutch@sdcsvax [ Of course, these statements were typed into my terminal while I was away. ] */
jnw@mcnc.UUCP (John White) (11/13/85)
>How should one choose the maximum number of iterations for any particular >region of the complex plane? Sure, one can always pick a value that's >"big enough" for any particular view ("big enough" meaning, intuitively, >that not too many pixels are marked as lying within the set when in fact >they aren't), but having such a large value makes the browser far too slow >when that many iterations aren't needed. > >Is there a method for finding adequate values for the maximum? Or must >I continue to rely on trial and error? I can't help you much with that problem. You might be able to adjust the limit depending on the proportion of pixels just outside the mandelbrot set that are near your limit. In my "browser", I use a very low resolution (160 by 100) and a low count limit for panning and zooming. Then, when I get a frame I like, I write down its parameters. I then queue up a bunch of such regions to be done overnight at high resolution and high count limit. I can usually guess what a good count limit would be from looking at the low-res version. Also, I use an algorithm for reducing the number of points that need to be computed. If there are no points in the mandelbrot set in the frame, then this helps a little. But if there are large areas of mandelbrot set, this algorithm can mean more than an order of magnitude savings as only the boundry points will be computed. This algorithm requires you to divide your frame into areas that you can fit into your available memory. The code starts in the upper left corner and looks along the edge and along count boundries. Points that still need no be checked are kept in a queue. I have found that this algorithm works very well, but there is a case where it fails. If the specified region contains the entire mandelbrot set, then after going around the entire edge no count boundry will be seen and the entire region will be set to count=1. You can map the real counts onto a smaller range, allowing evalbuf to be a char array. This also allows the algorithm to go a little faster as there are fewer count boundries to compute. But if the mapping is too weird, then the algorithm might not work. For example, I sometimes scale the count values by some constant and map the result on 1-253. Then, I let 255 be where the count limit was hit, and 254 represent all counts between that represented by 253 and 255. If the gap between 255 and 253 was a factor of 2, then the algorithm still worked. But, if the gap was a factor of 4, then the algorithm would often not see areas in the mandelbrot set that were completely surounded by points assigned to 254. Note that a count of 0 must never be used as this is a flag value. I tore the below code out of my program and I hope you find it useful. -------------------- tear here --------------------- #define EVAL_QUEUE_SIZE 2048 /* must be big enough */ #define EXSIZE 160 /* X size of evaluation buffer */ #define EYSIZE 100 /* Y size of evaluation buffer */ short evalbuf[EXSIZE][EYSIZE]; /* for the quick evaluation algorithm */ int maxdepth; /* log max use of queue */ int eval_x_queue[EVAL_QUEUE_SIZE], eval_y_queue[EVAL_QUEUE_SIZE]; int eval_start_ptr, eval_end_ptr; /**** put the below code in your driving routine */ for(i=0; i<EXSIZE; i++) for(j=0; j<EYSIZE; j++) evalbuf[j][i]=0; eval_start_ptr=eval_end_ptr=0; eval_point(0, 0); while(eval_start_ptr!=eval_end_ptr){ int x=eval_x_stack[eval_start_ptr]; int y=eval_y_stack[eval_start_ptr]; if(++eval_start_ptr>=EVAL_STACK_SIZE) eval_start_ptr=0; if(!evalbuf[y][x]) eval_point(x, y); } eval_fill(); /**** evalbuf now contains the region of the mandelbrot set */ /* quick evaluation routine */ eval_point(x, y){ int n; /**** ***** Replace the below line with something that assigns to the ***** variable "n" the number of iterations from evaluating the ***** point at x,y where 0<=x<EXSIZE, 0<=y<EYSIZE . ***** real_offset, imaginary_offset, xstep, ystep, and compute_point ***** are just dummy variables I put here to give you the general idea. ****/ n=compute_point(real_offset + xstep*x, imaginary_offset - ystep*y); /**** if you want to display the points as you compute them, you can ***** add that here. */ evalbuf[y][x]=n; check_point(x-1, y-1, n); check_point(x, y-1, n); check_point(x+1, y-1, n); check_point(x+1, y, n); check_point(x+1, y+1, n); check_point(x, y+1, n); check_point(x-1, y+1, n); check_point(x-1, y, n); } check_point(x, y, k){ int j; if(x<0 || x>=EXSIZE || y<0 || y>=EYSIZE || evalbuf[y][x]) return; if(x==0 || x==EXSIZE-1 || y==0 || y==EYSIZE-1){ add_point: eval_x_queue[eval_end_ptr]=x; eval_y_queue[eval_end_ptr]=y; if(++eval_end_ptr>=EVAL_QUEUE_SIZE) eval_end_ptr=0; if(eval_start_ptr==eval_end_ptr){ /* compress queue */ j=eval_start_ptr; do{ if(evalbuf[eval_y_queue[j]][eval_x_queue[j]]==0){ eval_x_queue[eval_end_ptr]=eval_x_queue[j]; eval_y_queue[eval_end_ptr]=eval_y_queue[j]; if(++eval_end_ptr>=EVAL_QUEUE_SIZE) eval_end_ptr=0; } if(++j>=EVAL_QUEUE_SIZE) j=0; } while(j!=eval_start_ptr); j=eval_end_ptr-eval_start_ptr; if(j<0) j+= EVAL_QUEUE_SIZE; if(j>maxdepth) maxdepth=j; if(eval_start_ptr==eval_end_ptr) printf("eval_point: queue exceeded\n"); } return; } if((j=evalbuf[y-1][x-1]) && j!=k) goto add_point; if((j=evalbuf[y-1][x]) && j!=k) goto add_point; if((j=evalbuf[y-1][x+1]) && j!=k) goto add_point; if((j=evalbuf[y][x+1]) && j!=k) goto add_point; if((j=evalbuf[y+1][x+1]) && j!=k) goto add_point; if((j=evalbuf[y+1][x]) && j!=k) goto add_point; if((j=evalbuf[y+1][x-1]) && j!=k) goto add_point; if((j=evalbuf[y][x-1]) && j!=k) goto add_point; } eval_fill(){ int i, n, x, y; for(y=1; y<EYSIZE-1; y++){ for(x=0; x<EXSIZE-1; x++){ if(i=evalbuf[y][x]) n=i; else{ evalbuf[y][x]=n; /**** if you want to display the points as you fill them in, you can ***** add that here. */ } } } }
jnw@mcnc.UUCP (John White) (11/13/85)
> short evalbuf[EXSIZE][EYSIZE]; /* for the quick evaluation algorithm */
Oops, that should be evalbuf[EYSIZE][EXSIZE].
I slipped when I tried to neaten it up after extracting it from my program.
These #defines used to be numbers, but I made them #defines so they could
be changed more easily.
Sorry for the error.