bresenham-circle

Bresenham's midpoint circle algorithm, stepped one decision at a time, next to a
golden-angle sampler that draws the same circle with zero lattice
symmetries — and no randomness at all.

Written in Nim with naylib.

screenshot

Build

nimble build
./bresenham

Flags: --r=N start at a radius, --shot render to shot.png and exit,
--frame=N which frame to capture.

Controls

key
`SPACE`	one iteration of the loop body
`A`	auto-step
`R`	reset
`UP` / `DOWN`	radius (hold to scrub, accelerating)
`[` `]`	golden-angle oversample factor
`ESC`	quit

The window is resizable, and the maximum radius is whatever currently fits —
grow the window and the cap grows with it.

Left pane: Bresenham

The whole algorithm is three integers and a sign test. No floats, no sqrt,
no trig, no π.

x = 0;  y = r;  d = 1 - r
while x <= y:
    plot8(x, y)
    if d < 0:                 # midpoint (x+1, y-1/2) is inside
        d += 2*x + 3
    else:                     # outside
        d += 2*(x - y) + 5
        y -= 1
    x += 1

d is the sign of F(x, y) = x² + y² − r² evaluated at the midpoint between
the two candidate pixels, carried forward incrementally. Inside means keep y,
outside means step it in. The visualization shows the two candidates (E/SE),
the midpoint under test, and lights up whichever branch just executed.

Only the 0°–45° octant is computed. Inside that wedge the slope stays between
0 and −1, so x advances by exactly 1 every iteration and y either holds or
drops by 1 — never more. The other seven octants are reflections:

[(x, y), (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)]

That is D₄, the complete symmetry group of the square lattice. There is no
ninth symmetry available to any shape on a square grid.

Cost is O(r): the loop runs r/√2 ≈ 0.707r times, so the full circle is
4√2·r ≈ 5.657 pixels per unit radius. (About 10% fewer than the circumference
2πr, because roughly half the steps are diagonal and cover √2 of arc for one
pixel.)

Right pane: golden angle

const golden = 2.0 * PI / ((1.0 + sqrt(5.0)) / 2.0) ^ 2   # ~137.507 deg
for k in 0 ..< n:
  let t = float(k) * golden
  samples.add (int(round(r * cos(t))), int(round(r * sin(t))))

No octants, no mirroring, no decision variable — and no randomness. It is as
deterministic as Bresenham. Yet its output has a trivial automorphism group:
no rotation or reflection of the lattice maps the pixel set to itself.

That is the point of using the golden angle rather than a random sprinkle. What
destroys the 8-fold symmetry is not unpredictability, it is incommensurability
with the grid. 2pi/phi^2 is the "most irrational" rotation available, so the
sequence never falls into step with the axes.

Both panes print a live symmetry count, computed by testing all 8 lattice
operations against the drawn cells. Bresenham reports 8/8, golden angle 1/8.

Coverage

Low discrepancy also means it never clumps, which independent random sampling
does. Worst angular hole in the ring at r = 2000, against Bresenham's
lattice-limited 0.041 deg:

oversample	golden angle	uniform random
1x	0.064 deg	0.382 deg
2x	0.041 deg	0.165 deg
4x	0.041 deg	0.103 deg
6x	0.041 deg	0.064 deg

Golden angle reaches the lattice limit at 2x oversample. Uniform random has not
got there by 6x. Press [ to drop toward 1x and watch holes open in the ring.

The spectral signature

Take the radial error as a function of angle and transform it. Bresenham's
spectrum has power only at harmonics that are multiples of 4 — the rotation
subgroup C4 forces 90-degree periodicity — and is exactly zero everywhere
else. Forbidden harmonics, like a crystal's forbidden diffraction peaks. At
r = 2000, mean power per harmonic over k = 1..60:

	multiples of 4	every other harmonic
Bresenham	0.00420	0.000000
golden angle	0.00239	0.00064
uniform random	0.00248	0.00109

Worth being precise about what this does and does not show. Golden angle still
carries a 4-fold component, and so does uniform random — that part is inherited
from snapping to a square lattice at all, not from the sampling rule. What
separates Bresenham is the exact zeros: it has harmonics that are structurally
forbidden, and the other two have no forbidden harmonics at all.

Golden angle is also not spectrally special here. Its advantage over random is
coverage and determinism, not a flatter spectrum.

What it costs

Visible in the panel: several angles taken per cell landed, ~25% more cells for
the same circle (rounding independent directions sometimes picks a cell further
from the curve than the midpoint test would), and trig per sample where
Bresenham used integer adds. For drawing one circle, Bresenham wins outright.

The trade only pays when structured error is worse than unstructured error of
the same size — which is exactly why production renderers reach for blue-noise
and low-discrepancy sampling, and why causal set theory in physics gives up a
regular lattice to keep Lorentz invariance.

License

MIT