I thought of a new optimization for rendering the Mandlebrot set on a computer screen. It involves prioritizing pixels based on whether or not their color has changed since the last iteration, and it is useful for real-time rendering.
Consider an unrendered 1,000x1,000 px canvas. On it are 1,000,000 pixels to calculate. The traditional naive method is to iterate over every pixel and stop only when the dwell is reached or the orbit escapes. Such a method is computationally costly when the dwell is considerably large and there are large portions of pixels in the set (i.e. traditionally black pixels) within the current canvas. One purpose of real-time rendering is to see just outside the set, not where the set is per se. This new rendering method will algorithmically priorotize colored pixels to calculate in a computationally efficient manner to tend to render the bands first before spending time verifying that pixels in the set will cap out at the current dwell.
For the purposes of illustration, let us also assume that our 1000x1000 canvas is centered at the origin with horizontal and vertical ranges of [-2,2].
My optimization algorithm will start with the assumption that all pixels are in the same band, so we will only calculate one iteration of the top-left-most pixel.
This is easy to display, as the point (-2,2) escapes before the first iteration:
Next, we break down this "one" pixel into 4 sub-pixels and check to see what their color is. As a result, you get a 2x2 Mandelbrot set render:
As you can see, we are already starting to see the shape of the set, and we've only calculated 13 pixels. The next version will only select those smaller pixels whose color is different from its parent and break them down to get a 16x16 render:
As a result of selectively ignoring stagnant pixels, we can rush to render those regions which are interesting. Now for 4 iterations this particular algorithm isn't any more impressive than if you simply rendered pixels in subchunks with no prioritizing, but this method starts to shine in areas where there are large regions of black, like a zoom-in to a mini-mandelbrot.
The details of the prioritizing process is left as an exercise to developers, but a few notes may aid the process.
1. It may be useful to only deprioritize regions for a few iterations, as seen in the example above, a naive deprioritization will lead to interesting areas being left unrendered until the end.
2. Be sure to calculate each pixel all the way to its dwell, as coupling the dwell with the current iteration in the render will result in mandelbrot set members to be focused on.
Got it working!
You can see that it very quickly finds a lot of the noisy parts of the image, and defers computation for areas which have neighboring colors that are the same.
Update: Already got it quite a bit faster!
The big blue area is where the dwell is maxed out.
