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

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: Poisson sprinkle

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113


# 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