| Successive Refinement |
Robert P. Munafo, 1998 Dec 9.
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 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.
The user interface device 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, exaluated, 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 :
IF ( chunk_size EQUALS 16) THEN
LET do_evaluate = TRUE
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 :
ELSE IF ( (x EQUALS parent_x) AND (y EQUALS parent_y) ) THEN
LET do_evaluate = FALSE
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 :
ELSE IF (all-neighbors-same(parent_x, parent_y,
chunk_size * 2) ) THEN
LET do_evaluate = FALSE
The last part of the IF is the default : if none of the other tests
worked, we must evaluate the point :
ELSE
LET do_evaluate = TRUE
END IF
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
.