Reenigne blog

Recently I was experimenting with drawing some Mandelbrot sets. Rather than scanning across the window pixel by pixel and doing one escape per pixel I generated a sequence of complex numbers within the window by repeatedly adding a complex number with irrational real and imaginary parts (the tangent of the argument of which was also irrational) and wrapping the real and imaginary parts into the window. This scatters points across the window evenly in such a way that no point is ever hit twice (within the bounds of precision) and that the pixel grid becomes gradually more dense. Thus the image sort of "rezzes in" and is gradually refined. Anti-aliasing is sort of built in - as the distance between samples gradually decreases, the effective resolution gradually increases. The program never completely stops but you can tell when it's done as the picture seems perfectly anti-aliased and stops changing. I didn't build this in, but the generated points could potentially be redrawn in a larger window to do a sort of (limited) real-time zoom (a la XaoS but hopefully with less artifacting - though it might take a lot of memory to store all that data).

This is kind of neat but I think we can do much better:

• The program doesn't take advantage of the natural structure of the Mandelbrot set (large "lakes" of high iteration count, which have detail only at the edges)
• The iteration limit is fixed (it would look wrong if some pixels had different iteration limits) - it would be nice if the iteration limit could be gradually increased (for points near the boundary) at the same time as resolution was gradually increased.
• There is no way of reusing the calculation for one point for a nearby point (Synchronous Orbit Iteration, which can really speed things up for very deep zooms)

I think all these things are possible with the right data structure. My idea is to form a sort of 2-dimensional linked list. The image is divided into rectangles. Each rectangle has iteration data (corresponding to its center) and 8 pointers to other rectangles, two on each edge. The two pointers may point to the same rectangle or to different rectangles. Suppose both right-pointers of rectangle A point to rectangle B. Then either the two left-pointers of rectangle B can point back to rectangle A, or only one of them does. Thus, each rectangle is bordered on each side by either two rectangles, one rectangle or half a rectangle. And by a process analogous to linked-list insertion, any rectangle can be subdivided horizontally (if it doesn't have half rectangles on either of the horizontal edges) and/or vertically (if it doesn't have half rectangles on either of the vertical edges).

Thus at any point we can increase resolution (by splitting rectangles) or iteration count (by iterating on existing rectangles). If a rectangle is bounded by lake on all sides it is probably also full of lake and we can avoid subdividing or iterating, meaning that we do less work (or defer work) in the boring areas. We also have a natural way of doing SOI (copying the iteration data when we split a rectangle).

We can also do real-time zooming, by noticing that the relationship between rectangle dimension and pixel dimension need not be fixed, and (if necessary) throwing away or paging out rectangles that are outside the window.

There are some fiddly parts, like "how do you divide your priorities between iterating and subdividing" and "what do you do at the edges" which are the reason why I haven't explored this any futher, but it's an interesting project.

This entry was posted on Tuesday, May 8th, 2007 at 9:08 pm and is filed under computer, fractals. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.