# Deep Zoom

Deep zoom theory and practice for the Mandelbrot set and other fractals.

As used in Fraktaler 3 and other renderers.

# 1 The Mandelbrot Set

High precision reference orbit:

$Z_{m+1} = Z_m^2 + C$

$m$ starts at $0$ with $Z_0 = 0$ .

# 2 Perturbation

Low precision deltas relative to high precision orbit. Pixel orbit $Z_m + z_n$ , $C + c$ .

$z_{n+1} = 2 Z_m z_n + z_n^2 + c$

$m$ and $n$ start at $0$ with $z_0 = 0$ .

# 2.1 Rebasing

Rebasing to avoid glitches: when $|Z_m + z_n| < |z_n|$ replace $z_n$ with $Z_m + z_n$ and reset the reference iteration count $m$ to $0$ .

# 3 Bivariate Linear Approximation

Sometimes, $l$ iterations starting at $n$ can be approximated by bivariate linear function;

$z_{n+l} = A_{n,l} z_n + B_{n,l} c$

This is valid when the non-linear part of the full perturbation iterations is so small that omitting it would cause fewer problems than the rounding error of the low precision data type.

# 3.1 Single Step BLA

Approximation of a single step by bilinear form is valid when

$\begin{aligned} |z_n^2| &<< |2 Z_n z_n + c| \\ &\Uparrow \quad \text{ assume neglibility of } c \\ |z_n^2| &<< |2 Z_n z_n| \\ &\Uparrow \quad \text{ factor out } z_n \\ |z_n| &<< |2 Z_n| \\ &\Uparrow \quad \text{ definition of } A_{n,1}, B_{n,1} \text{ for single step } \\ |z_n| &<< |A_{n,1}| =: R_{n, 1} \end{aligned}$

My earlier attempt at a validity check was nonsense, best to ignore that part of the older posts.

# 3.2 Merging BLA Steps

If $T_x$ skips $l_x$ iterations from iteration $m_x$ when $|z| < R_x$ and $T_y$ skips $l_y$ iterations from iteration $m_x + l_x$ when $|z| < R_y$ then $T_z = T_y \circ T_x$ skips $l_x + l_y$ iterations from iteration $m_x$ when $|z| < R_z$ :

$\begin{aligned} z_{m_x + l_x + l_y} &= A_y (A_x z_{m_x} + B_x c) + B_y c = A_z z_{m_x} + B_z c \\ A_{m_x, l_x + l_y} = A_z &= A_y A_x \\ B_{m_x, l_x + l_y} = B_z &= A_y B_x + B_y \\ R_{m_x, l_x + l_y} = R_z &= \max\left\{ 0, \min\left\{ R_x, \frac{R_y - |B_x| |c|}{|A_x|} \right\} \right\} \end{aligned}$

# 3.3 BLA Table Construction

This style of table construction is suboptimal according to Zhuoran.

Suppose the reference has $M$ iterations. Create $M$ BLAs each skipping $1$ iteration (this can be done in parallel). Then merge neighbours without overlap to create $\left\lceil \frac{M}{2} \right\rceil$ each skipping $2$ iterations (except for perhaps the last which skips less). Repeat until there is only $1$ BLA skipping $M-1$ iterations: it’s best to start the merge from iteration $1$ because reference iteration $0$ always corresponds to a non-linear perturbation step as $Z = 0$ .

The resulting table has $O(M)$ elements.

# 3.4 BLA Table Lookup

Find the BLA starting from iteration $m$ that has the largest skip $l$ satisfying $|z| < R$ . If there is none, do a perturbation iteration. Check for rebasing opportunities after each BLA application or perturbation step.

# 4 BLA Extensions

# 4.1 Non-Conformal BLA

The Mandelbrot set is conformal (angles are preserved). This means complex numbers can be used for derivatives. Some other formulas are not conformal, for example the Tricorn aka Mandelbar, defined by: $X + i Y \to (X - i Y)^2 + C$

For non-conformal formulas, replace complex numbers by $2 \times 2$ real matrices for $A, B$ . Dual numbers with two dual parts can be used to calculate the derivatives.

Be careful finding norms. Define $\sup|M|$ and $\inf|M|$ as the largest and smallest singular values of $M$ . Then single step BLA radius becomes $R = \epsilon \inf|A| - \frac{\sup|B|}{\inf|A|} |c|$ and merging BLA steps radius becomes $R_z = \max\left\{ 0, \min\left\{ R_x, \frac{R_y - \sup|B_x| |c|}{\sup|A_x|} \right\} \right\}$

# 4.2 ABS Variation BLA

The only problem with the Mandelbrot set is the non-linearity, but some other formulas have other problems, for example the Burning Ship, defined by: $X + i Y \to (|X| + i |Y|)^2 + C$ The absolute value folds the plane when $X$ or $Y$ are near $0$ , so the single step BLA radius becomes the minimum of the non-linearity radius and the folding radii: $R = \max\left\{ 0, \min\left\{ \epsilon \inf|A| - \frac{\sup|B|}{\inf|A|} |c|, |X|, |Y| \right\} \right\}$ Currently Fraktaler 3 uses a fudge factor for paranoia, dividing $|X|$ and $|Y|$ by $2$ . The merged BLA step radius is unchanged.

# 4.3 Hybrid BLA

For a hybrid loop with multiple phases, you need multiple references, one starting at each phase in the loop. Rebasing switches to the reference for the current phase. You need one BLA table per reference.

# 4.4 Multiple Critical Points

Some formulas (but none among those implemented in Fraktaler 3) have multiple critical points. In this case some modifications need to be made: you need a reference per critical point, and rebasing needs to switch to the nearest orbit among all critical points. There needs to be a separate BLA table for each reference. This also applies to hybrids, you need one reference and BLA table per critical point per phase.

# 5 Distance Estimation

Keep track of derivatives of $Z+z$ wrt. pixel coordinates $k$ . As $Z$ is constant for the whole image, you just need $\frac{dz}{dk}$ . An easy way to do this is with dual numbers for automatic numeric differentiation. Set up the pixel coordinates as dual numbers with dual part $1+0i$ , then transform them to the complex $C+c$ plane of the fractal iterations. At the end you plug the complex derivative into the (directional) distance estimate formula, it is already prescaled by the pixel spacing (this also helps to avoid overflow during iteration).

For non-complex-analytic formulas (like Mandelbar and Burning Ship), you can use dual numbers with two dual parts, for each of the real and imaginary components. At the end they can be combined into a Jacobian matrix and used in the (directional) distance estimate formula for general iterations.

# 6 Interior Detection

Keep track of derivatives of $Z+z$ wrt. $Z_1+z_1$ (where $Z_0+z_0$ is at the critical point, usually $0$ ). When the absolute value of the derivative drops below a threshold such as $0.001$ , classify it as interior and stop iterating. For non-complex-analytic formulas, dual numbers with four dual parts can be used (two for distance estimation and two for interior detection), along with matrix operator norm.

Using $\frac{dz}{dz_1}$ sometimes works because:

$\begin{aligned} &\frac{d(Z+x)}{d(Z_1+z_1)} \\ =& \frac{dZ}{d(Z_1+z_1)} + \frac{dz}{d(Z_1+z_1)} \\ =& \frac{1}{\frac{dZ_1}{dZ} + \frac{dz_1}{dZ}} + \frac{1}{\frac{dZ_1}{dz} + \frac{dz_1}{dz}} \\ =& \frac{1}{\frac{dZ_1}{dZ} + 0} + \frac{1}{0 + \frac{dz_1}{dz}} \\ =& \frac{dZ}{dZ_1} + \frac{dz}{dz_1} \\ =& 0 + \frac{dz}{dz_1} \\ =& \frac{dz}{dz_1} \end{aligned}$

where the last two lines hold when $C$ is periodic with $Z = 0$ in the orbit which happens precisely when the formula has a critical point at $0$ and $C$ is the nucleus of a hyperbolic component.

# 7 References

perturbation technique: science.eclipse.co.uk/sft_maths.pdf
rebasing and BLA: fractalforums.org/f/28/t/4360 (archive)
distance estimates: mathr.co.uk/helm
interior detection: fractalforums.org/f/28/t/4802 (archive)
earlier blog posts: deep zoom theory and practice; deep zoom theory and practice again