# bresenham-circle

Bresenham's midpoint circle algorithm, stepped one decision at a time, next to a
Poisson sprinkle that draws the same circle with **zero** exact symmetries.

Written in [Nim](https://nim-lang.org) with [naylib](https://github.com/planetis-m/naylib).

![screenshot](docs/screenshot.png)

## Build

```sh
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) |
| `[` `]` | sprinkle 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 π.

```nim
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:

```nim
[(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: Poisson sprinkle

```nim
for _ in 1 .. n:
  let t = rng.rand(2.0 * PI)
  samples.add (int(round(r * cos(t))), int(round(r * sin(t))))
```

No octants, no mirroring, no decision variable. Its output has a **trivial
automorphism group** — no rotation or reflection maps the pixel set to itself —
yet it is isotropic *in distribution*, because uniform sampling on the circle is
rotation-invariant. This is the causal-set trick: give up exact symmetry, keep
symmetry of the measure.

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

### The measurable difference

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 C₄ forces 90° periodicity — and is exactly zero elsewhere. Forbidden
harmonics, like a crystal's forbidden diffraction peaks. At r = 2000:

| | power at k = 4, 8, 12, … | everywhere else |
|---|---|---|
| Bresenham | 0.00354 | **0.000000** |
| sprinkle | 0.00250 | 0.00085 |

The sprinkle is broadband: no structure, no preferred directions.

That trade is why production renderers use stochastic and blue-noise sampling —
structured aliasing (moiré, banding, visible staircases) is far more
objectionable than unstructured noise of the same magnitude. The price is
visible in the panel: several samples rolled per cell landed, more cells for the
same circle, no determinism, and trig plus an RNG where Bresenham used integer
adds. Drop the oversample to 1× with `[` and holes open in the ring — the
coupon-collector problem, on screen.

## License

MIT