Adjacency Optimization

Robert P. Munafo, 2023 Aug 9.

"Adjacency Optimization" refers to a family of algorithmic techniques used in rendering, image processing, and other generally grid-oriented compute-intensive operations. The common principle is to exploit local similarity in the image.

Many other methods are used to increase speed; see Speed Improvements for an overview of all of them.

Here are some popular adjacency algorithms used in evaluating views of the Mandelbrot Set and Julia Sets:

Successive Refinement with solid guessing, whereby a grid is scanned coarsely, and the resulting coarse grid is used to locate solid regions. Solid regions are skipped while the grid is re-scanned at a finer resolution. Successive refinement can miss narrow features such as cusps.

Boundary Scanning, whereby a grid is traversed using a recursive or queue-oriented method similar to maze-solving algorithms. Starting generally at one pixel on an edge or corner of the grid, neighboring pixels are evaluated if they are adjacent to a pixel that has been evaluated and if they are either on the edge of the grid or if they have at least two neighbors which have been evaluated and are of differing values. Boundary scanning will sometimes miss features if the maximum dwell is too low.

Mariani/Silver Algorithm, whereby a rectangular grid is recursively subdivided into subrectangles (with less efficiency, it could also be done without recursion). The pixels on the boundary of the grid are evaluated, and if they all evaluate to the same result the rectangle is filled in with a solid color; otherwise the rectangle is divided into two or more smaller rectangles and the algorithm is applied to each piece. Mariani/Silver will occasionally miss features if the maximum dwell is too low, and will miss parts of cusps that are narrower than the pixel spacing.

Circle Tiling, whereby a grid is filled with circles that are guaranteed not to intersect the boundary of the Mandelbrot Set by using the Distance Estimator (and possibly also Interior Distance Estimator) iteration techniques. Test points (starting with a point known to be outside the Mandelbrot Set) are generated using a recursive or queue-oriented algorithm similar to Boundary Scanning. After all circles have been generated and filled the remaining unfilled grid elements comprise the set of all pixels that contain part of the Mandelbrot Set. If the distance estimate calculation is done correctly, Circle Tiling is guaranteed never to mis-identify points as exterior, but its poor performance in areas of higher box-counting dimension produces unusual pictures and often misses features, unless combined with other algorithms.

Best Algorithm for the Job

Certain adjacency optimizations are preferable for certain applications.

If you want the best speed improvement, it's hard to beat successive refinement. The amount of speed improvement depends on the compiler and the skill of the programmer, but usually successive refinement will do the best. It wins out because of the pure simplicity of the algorithm (essentially just several grid scans in a row) and the lack of a need for any special data structures (boundary scanning and circle tiling both require some sort of linked list or queue; Mariani/Silver is done most efficiently with a two-dimensional pixel-grid array, or a stack of one-dimensional arrays). In addition, it requires no recursion to implement the algorithm (the efficient implementations of Mariani/Silver do, and the others do if implemented without a queue.)

If you want the best modeless user interface for browsing and zooming, you should use Successive Refinement. It is the best for modeless UI because it presents an acceptable approximation of the final image right away. The user can wait for more resolution, or can move on to another view right away. See Successive Tradeoffs method.

If you want the most accurate view of the Mandelbrot Set (i.e. the fewest "missed pixel errors") you should use Mariani/Silver. Boundary scanning is the second best. Circle tiling will not miss anything in the Set itself, but it does a horrible job of showing the Dwell Bands; you should probably only use it to render a filaments-only view.

If you wish to use an adjacency algorithm to speed up a distance estimator plot, use circle tiling. However, if your plot will show DEM contours, you may use either successive refinement or Mariani/Silver. Boundary Scanning will not work.

You cannot use any adjacency algorithm in the pixel counting method of estimating the area of the Mandelbrot Set. Even Mariani/Silver (which has the fewest missed pixels) will sometimes miss pixels inside cusps.

Another Adjacency-Based Optimization

If you are plotting a view that displays both dwell bands and filaments computed with the distance estimator, and if you are also using Successive Refinement, then you can exploit the successive refinement optimization in a special way to make things even faster.

Successive refinement involves looking at neighboring points and deciding whether to evaluate an area at higher resolution by detecting the presence of boundaries. If the area is to be evaluated at higher resolution, one or more points are then iterated and drawn.

When iterating, you would normally use the distance estimator function, which gives both the dwell and the distance estimate. For many points, the resulting distance estimate will be sufficiently far away from a filament that the distance information will not be used and the color of the pixel will depend only on the dwell.

This is where the optimization can be applied. When the neighbors are checked to determine if you're near a boundary, you can also check the distance that was computed at those neighbors. If they were all reasonably far away then we know that the interpolated points will also be reasonably far away. It is therefore okay to compute only the dwell (which is usually several times faster than computing dwell and distance estimate).

revisions: 20040226 oldest on record; 20230809 solid guessing, circle tiling exterior guarantee

Mu-ency main page — index — recent changes — DEMZ

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2023 Aug 09.

s.27