After first pass (1.0 sec.)
After second pass (3.0 sec.)
After third pass (9 sec)
After fourth pass (27 sec)
Robert P. Munafo, 2010 Feb 25.
Successive Refinement algorithms vary, but the common principle is to scan the grid at a "coarse" spacing, then again (in one or several passes) at increasingly finer spacings.
Successive refinement is used in Mandelbrot programs as both a user interface device and as an optimization. The improvement that it provides cannot be overemphasized. It will instantly transform a barely useable program into a powerful viewer. The program will complete its work typically 2-3 times faster, and often a hundred times faster. What's more, the successive refinement of the image during the imaging process allows the user an early glimpse of the final result, often foregoing the need to wait for completion.
|
After first pass (1.0 sec.) | After second pass (3.0 sec.) |
|
After third pass (9 sec) | After fourth pass (27 sec) |
As a user interface device, successive refinement allows the user to view a coarse representation of the current image, followed soon after by a less coarse version, then by better and better versions gradually over time. The implementation is fairly simple, consisting of little more than several successive raster scans. This can be done as follows:
On each iteration of the outermost FOR loop, the grid is scanned, evaluated, and plotted in squares of the current chunk size. The subroutine "fill_rectangle" takes five parameters, as shown: the top-left coordinates, the width and height, and a color.
This implementation is of course slower in the end than a single grid scan, because 25% of the squares are iterated and drawn twice, and 6.25% are drawn three times, etc.
With fairly little effort we can avoid this extra computation.
Inside the three loops we have added two tests. The first ensures that the first scan (chunk_size 16) will be complete. The second allows subsequent passes to skip the squares computed on the previous pass.
Optimization via Successive Refinement is a little more difficult, but well worth the effort. The technique is to watch the neighboring points during the grid scan and skip the Mandelbrot iteration if all of the neighbors have the same "count". This works quite well for the Mandelbrot Set (at least at the low magnifications that most beginning explorers use — see Optimizations - Domains of Efficacy)
Implementation starts by declaring an array to hold the computed count values :
Our three loops are the same :
We compute the coordinates of the current square's "parent". These are the coordinates of the square from the previous pass that the current square is a part of. For example, on the second pass, the square at (8,24) is an 8x8 square which is a part of the 16x16 square at (0,16). Thus (0,16) are the coordinates of the "parent" of (8,24).
The computation of parent_y is similar :
We then perform a test to see if the current square should be evaluated. The first part of the IF ensures that all squares will be drawn on the first pass, just as before :
The second part, just as before, ensures that we skip squares that were drawn on the previous pass — note however that the test is now simplified because we can use the variables parent_x and parent_y :
The third part is the new test : it calls a subroutine, "all-neighbors-same", which will return TRUE if all of the neighboring squares have the same count as the square given by the parameters parent_x and parent_y. "chunk_size * 2" is the spacing between the parent square and the neighboring parent squares. Eight neighbors will be tested :
The last part of the IF is the default : if none of the other tests worked, we must evaluate the point :
After determining if we evaluate, we then proceed as follows :
This instructs the computer to use the "parent"'s count value if we are on a square that is being skipped. Then we proceed to draw :
This is the same as before, the only difference being that we store our count value in the array for use on the next pass. (Sharp readers will note that when a square has the same coordinates as its parent, we redraw it. This is of little consequence.) Now we end our loops :
As a user-interface improvement, Successive Refinement can work even better if the pixels are split in two (vertically or horizontally on alternating passes) instead of in four. In other words, if the first pass produces 8x8 pixels, the second would produce 4x8 pixels, the third 4x4 pixels, the fourth 2x4 pixels and so on.
While these pseudo-code examples have used the Dwell or Escape-Iterations function for rendering the Mandelbrot Set, Successive Refinement lends itself equally well and with similar results to the Distance Estimator function.
With great effort, Successive Refinement can be applied to the Synchronous-Orbit Algorithm.
This work is licensed under a Creative Commons Attribution 2.5
License. Details here
s.13