# bs
Realtime Burning Ship fractal explorer implemented in browser-based Javascript.
# 1 Burning Ship
See Burning Ship for brief intro.
For more on the theory below see also Deep Zoom.
# 2 Reference Orbit
A point with \(C\) near the view, iterated with high precision using fixed point arithmetic.
Computing the reference orbit is an inherently sequential calculation, with possible acceleration still a topic of ongoing research.
In bs
, when the reference calculation takes too long in comparison
to the zooming interaction, the image gets highly pixelated. Depending
on location this is typically starts to happen around zoom level 600 to 700.
# 3 Perturbed Pixels
The difference of each visualized point from the reference orbit
is iterated with low precision (hardware double
)
floating point arithmetic.
This uses laser blaster’s diffabs()
case analysis
for evaluating \(|X+x|-|X|\) without catastrophic absorption and cancellation.
If the actual point (visualized point’s difference plus reference) is closer to zero (the critical point) than the size of the difference, then rebase:
- replace difference with sum of difference plus reference
- replace index into reference orbit with zero
(Zhuoran’s rebase for Mandelbrot set prevents precision loss glitches and also seems to work for Burning Ship.)
The metric max(abs(x), abs(y))
is used instead of sqrt(x*x + y*y)
to avoid underflow problems (where you get 0 instead of a tiny non-zero
number; this is another trick from Zhuoran).
# 4 Linear Acceleration
For deep zooms, most of the time the small region of the view ends up bouncing around the complex plane in a mostly linear way. Only when the region is near zero (when non-linear squaring is significant) or either componenent is near zero (when abs-folding can happen) is it necessary to do a full perturbed iteration, the rest of the time each iteration can be approximated linearly by
\[ z := A z + B c \]
considering complex \(z, c\) as length 2 real vectors and \(A, B\) as 2x2 matrices.
Now the composition of two linear functions is another linear function, and validity radii for the linear approximation can be computed and combined alongside, allowing to build a table of linear coefficients that are equivalent to progressively longer counts of regular iterations. (Zhuoran says the mipmap-style tables that I use are not optimal for Mandelbrot set, but they seem to work well enough, and the technique works for Burning Ship too.)
Each step, see if you can do a long linear step, falling back to regular non-linear perturbed steps if there is no entry in the table.
This technique vastly accelerate calculations of deep zooms, making per-pixel cost approximately constant (typically a few thousand steps are enough).
# 5 Voronoi Tesselation
bs
doesn’t use a pixel grid, instead it generates points at random
and generates the final image by colouring each pixel according to the
nearest calculated point.
It does this with a
Voronoi tesselation in Manhattan metrix. Unlike
the CPU-based implementation on that page, bs
draws a small square pyramid
for each point, using depth so that neighbouring points’ pyramids overlap
in the right way to form the tesselation. A Euclidean metric Voronoi
tesselation would draw circular cones instead of square pyramids.
It’s not 100% perfect, because the pyramids are scaled to be smaller the more points there are (to avoid GPU-based denial of service: 100k full-screen pyramids will probably crash the desktop session), sometimes there can be gaps between them if the points are distributed unevenly. But on average it works fine.
# 6 Foveated Rendering
Interactive zoom in generates more points near the focus of the zoom so that quality is higher in the region of interest and stays higher for longer (points far from the zoom center would quickly move out of view). Points far out of frame are culled to keep things responsive.
Zoom out generates more points further from the focus (including some far out of frame, whch will soon move into view) and culls points near the focus, to reduce uneven density (which can cause various problems).
# 7 Auto Stretch
Under the keel and bow of miniships, the features get highly stretched. Using statistics based on directional distance estimates can give a transformation matrix that, applied to the \(c\) coordinate, would make the features conformally neutral (as round as possible).
The stretch amount is reduced so that stretching happens over several animation frames instead of instantly, this avoids sudden movements.
There is an issue where sometimes the image wobbles slightly, in this case you can disable auto stretch with a checkbox control in the top right bar.
The stretch level is shown in the bottom left status bar (S
).
# 8 Auto Equalization
Colour is based on directional distance estimates combined with equalized iteration count. A sample is taken of the points, and their iteration counts are sorted. Then during image generation, each point looks up into the sorted array of iteration counts and takes its own (fractionally interpolated) index to control brightness. This is similar (but not identical) to histogram equalisation.
There is an issue where sometimes the image flickers slightly, usually zooming in or out a small amount stabilizes the view.