nandi/bresenham-circle · README.md

⑂ 3d0b0a38a545e8531a7d6cb7182993e543ca51ed

README.md · 113 lines · 3.8 KBmarkdown    Blame HistoryRaw
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   1# bresenham-circle
3Bresenham's midpoint circle algorithm, stepped one decision at a time, next to a
4Poisson sprinkle that draws the same circle with **zero** exact symmetries.
6Written in [Nim](https://nim-lang.org) with [naylib](https://github.com/planetis-m/naylib).
8![screenshot](docs/screenshot.png)
13nimble build
14./bresenham
17Flags: `--r=N` start at a radius, `--shot` render to `shot.png` and exit,
18`--frame=N` which frame to capture.
20## Controls
22
23
24| `SPACE` | one iteration of the loop body |
25| `A` | auto-step |
26| `R` | reset |
27| `UP` / `DOWN` | radius (hold to scrub, accelerating) |
28| `[` `]` | sprinkle oversample factor |
29| `ESC` | quit |
31The window is resizable, and the maximum radius is whatever currently fits —
32grow the window and the cap grows with it.
34## Left pane: Bresenham
36The whole algorithm is three integers and a sign test. No floats, no `sqrt`,
37no trig, no π.
40x = 0;  y = r;  d = 1 - r
41while x <= y:
42    plot8(x, y)
43    if d < 0:                 # midpoint (x+1, y-1/2) is inside
44        d += 2*x + 3
45    else:                     # outside
46        d += 2*(x - y) + 5
48
51`d` is the sign of `F(x, y) = x² + y² − r²` evaluated at the midpoint between
52the two candidate pixels, carried forward incrementally. Inside means keep `y`,
53outside means step it in. The visualization shows the two candidates (`E`/`SE`),
54the midpoint under test, and lights up whichever branch just executed.
56Only the 0°–45° octant is computed. Inside that wedge the slope stays between
570 and −1, so `x` advances by exactly 1 every iteration and `y` either holds or
58drops by 1 — never more. The other seven octants are reflections:
61[(x, y), (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)]
64That is D₄, the complete symmetry group of the square lattice. There is no
65ninth symmetry available to any shape on a square grid.
67Cost is **O(r)**: the loop runs `r/√2 ≈ 0.707r` times, so the full circle is
68`4√2·r ≈ 5.657` pixels per unit radius. (About 10% fewer than the circumference
69`2πr`, because roughly half the steps are diagonal and cover √2 of arc for one
72## Right pane: Poisson sprinkle
75for _ in 1 .. n:
76  let t = rng.rand(2.0 * PI)
77  samples.add (int(round(r * cos(t))), int(round(r * sin(t))))
80No octants, no mirroring, no decision variable. Its output has a **trivial
81automorphism group** — no rotation or reflection maps the pixel set to itself —
82yet it is isotropic *in distribution*, because uniform sampling on the circle is
83rotation-invariant. This is the causal-set trick: give up exact symmetry, keep
84symmetry of the measure.
86Both panes print a live symmetry count, computed by testing all 8 lattice
87operations against the drawn cells. Bresenham reports 8/8, the sprinkle 1/8.
89### The measurable difference
91Take the radial error as a function of angle and transform it. Bresenham's
92spectrum has power **only** at harmonics that are multiples of 4 — the rotation
93subgroup C₄ forces 90° periodicity — and is exactly zero elsewhere. Forbidden
94harmonics, like a crystal's forbidden diffraction peaks. At r = 2000:
96| | power at k = 4, 8, 12, … | everywhere else |
97|---|---|---|
98| Bresenham | 0.00354 | **0.000000** |
99| sprinkle | 0.00250 | 0.00085 |
101The sprinkle is broadband: no structure, no preferred directions.
103That trade is why production renderers use stochastic and blue-noise sampling —
104structured aliasing (moiré, banding, visible staircases) is far more
105objectionable than unstructured noise of the same magnitude. The price is
106visible in the panel: several samples rolled per cell landed, more cells for the
107same circle, no determinism, and trig plus an RNG where Bresenham used integer
108adds. Drop the oversample to 1× with `[` and holes open in the ring — the
109coupon-collector problem, on screen.
111

Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago	1	# bresenham-circle
	2
	3	Bresenham's midpoint circle algorithm, stepped one decision at a time, next to a
	4	Poisson sprinkle that draws the same circle with zero exact symmetries.
	5
	6	Written in [Nim](https://nim-lang.org) with [naylib](https://github.com/planetis-m/naylib).
	7
	8	![screenshot](docs/screenshot.png)
	9
	10	## Build
	11
	12	```sh
	13	nimble build
	14	./bresenham
	15	```
	16
	17	Flags: `--r=N` start at a radius, `--shot` render to `shot.png` and exit,
	18	`--frame=N` which frame to capture.
	19
	20	## Controls
	21
	22	\| key \| \|
	23	\|---\|---\|
	24	\| `SPACE` \| one iteration of the loop body \|
	25	\| `A` \| auto-step \|
	26	\| `R` \| reset \|
	27	\| `UP` / `DOWN` \| radius (hold to scrub, accelerating) \|
	28	\| `[` `]` \| sprinkle oversample factor \|
	29	\| `ESC` \| quit \|
	30
	31	The window is resizable, and the maximum radius is whatever currently fits —
	32	grow the window and the cap grows with it.
	33
	34	## Left pane: Bresenham
	35
	36	The whole algorithm is three integers and a sign test. No floats, no `sqrt`,
	37	no trig, no π.
	38
	39	```nim
	40	x = 0; y = r; d = 1 - r
	41	while x <= y:
	42	plot8(x, y)
	43	if d < 0: # midpoint (x+1, y-1/2) is inside
	44	d += 2*x + 3
	45	else: # outside
	46	d += 2*(x - y) + 5
	47	y -= 1
	48	x += 1
	49	```
	50
	51	`d` is the sign of `F(x, y) = x² + y² − r²` evaluated at the midpoint between
	52	the two candidate pixels, carried forward incrementally. Inside means keep `y`,
	53	outside means step it in. The visualization shows the two candidates (`E`/`SE`),
	54	the midpoint under test, and lights up whichever branch just executed.
	55
	56	Only the 0°–45° octant is computed. Inside that wedge the slope stays between
	57	0 and −1, so `x` advances by exactly 1 every iteration and `y` either holds or
	58	drops by 1 — never more. The other seven octants are reflections:
	59
	60	```nim
	61	[(x, y), (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)]
	62	```
	63
	64	That is D₄, the complete symmetry group of the square lattice. There is no
65	ninth symmetry available to any shape on a square grid.
66
67	Cost is O(r): the loop runs `r/√2 ≈ 0.707r` times, so the full circle is
68	`4√2·r ≈ 5.657` pixels per unit radius. (About 10% fewer than the circumference
69	`2πr`, because roughly half the steps are diagonal and cover √2 of arc for one
70	pixel.)
71
72	## Right pane: Poisson sprinkle
73
74	```nim
75	for _ in 1 .. n:
76	let t = rng.rand(2.0 * PI)
77	samples.add (int(round(r * cos(t))), int(round(r * sin(t))))
78	```
79
80	No octants, no mirroring, no decision variable. Its output has a **trivial
81	automorphism group** — no rotation or reflection maps the pixel set to itself —
82	yet it is isotropic in distribution, because uniform sampling on the circle is
83	rotation-invariant. This is the causal-set trick: give up exact symmetry, keep
84	symmetry of the measure.
85
86	Both panes print a live symmetry count, computed by testing all 8 lattice
87	operations against the drawn cells. Bresenham reports 8/8, the sprinkle 1/8.
88
89	### The measurable difference
90
91	Take the radial error as a function of angle and transform it. Bresenham's
92	spectrum has power only at harmonics that are multiples of 4 — the rotation
93	subgroup C₄ forces 90° periodicity — and is exactly zero elsewhere. Forbidden
94	harmonics, like a crystal's forbidden diffraction peaks. At r = 2000:
95
96	\| \| power at k = 4, 8, 12, … \| everywhere else \|
97	\|---\|---\|---\|
98	\| Bresenham \| 0.00354 \| 0.000000 \|
99	\| sprinkle \| 0.00250 \| 0.00085 \|
100
101	The sprinkle is broadband: no structure, no preferred directions.
102
103	That trade is why production renderers use stochastic and blue-noise sampling —
104	structured aliasing (moiré, banding, visible staircases) is far more
105	objectionable than unstructured noise of the same magnitude. The price is
106	visible in the panel: several samples rolled per cell landed, more cells for the
107	same circle, no determinism, and trig plus an RNG where Bresenham used integer
108	adds. Drop the oversample to 1× with `[` and holes open in the ring — the
109	coupon-collector problem, on screen.
110
111	## License
112
113	MIT