mathr / blog / #

Optimizing zoom animations

re-use 25% of samples without recomputation

Suppose one has a generative image, as a function from position to colour. Some such images are interesting enough to want to be able to generate animations zooming in to a particular point. For example, the Mandelbrot Set is one such interesting generative image. Suppose you zoom in by a factor of two: it turns out that you can re-use pixels computed at the previous zoom level, which means you don't have to recompute 25% of the new image.

Furthermore, to generate smoother appearance for images with lots of fine details, one generally wants to oversample to reduce aliasing artifacts: that is, one computes more than one point per pixel. Now supposing you have sufficiently oversampled your images, and generated a zoom image sequence with a twofold zoom between each consecutive pair of images, you can interpolate between scaled versions of these oversampled images, so as to maintain a constant points-per-pixel density: this should in theory generate a smooth zoom animation, with much less computation than calculating each pixel of each frame.

blend between oversampled zoom images

The optimal (in terms of maintaining constant points per pixel) blend factor for t in [0..1] with zoom 2^t turns out to be:

b(t) = (1 - 4^(-t)) / (4^(1-t) - 4^(-t))

Suppose one wants 4x4 oversampling at a frame size of 788x576, to generate a zoom animation lasting 5mins at 25fps with a final zoom factor of 2^64 compared to the first frame. The standard method would compute:

5 * 60 * 25 * 4 * 4 * 788 * 576 = 54,466,560,000 points

5 * 60 * 25 = 7,500 image downscales

0 image blends

The optimizations described above would compute:

64 * 2 * 2 * 4 * 4 * 788 * 576 * 3 / 4 + 1 * 2 * 2 * 4 * 4 * 788 * 576 * 4 / 4 = 1,423,392,768 points

5 * 60 * 25 * 2 = 15,000 image downscales

5 * 60 * 25 = 7,500 image blends

The 97% reduction in the number of points that need to be calculated should hopefully outweigh the additional costs of downscaling and blending.