nandi/bresenham-circle · README.md

⑂ main

README.md · 147 lines · 5.3 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
Replace the random sprinkle with a golden-angle sequence   4golden-angle sampler that draws the same circle with **zero** lattice
5symmetries — and no randomness at all.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   6
7Written in [Nim](https://nim-lang.org) with [naylib](https://github.com/planetis-m/naylib).
9![screenshot](docs/screenshot.png)
14nimble build
15./bresenham
18Flags: `--r=N` start at a radius, `--shot` render to `shot.png` and exit,
19`--frame=N` which frame to capture.
21## Controls
23
24
25| `SPACE` | one iteration of the loop body |
26| `A` | auto-step |
27| `R` | reset |
28| `UP` / `DOWN` | radius (hold to scrub, accelerating) |
Replace the random sprinkle with a golden-angle sequence   29| `[` `]` | golden-angle oversample factor |
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   30| `ESC` | quit |
32The window is resizable, and the maximum radius is whatever currently fits —
33grow the window and the cap grows with it.
35## Left pane: Bresenham
37The whole algorithm is three integers and a sign test. No floats, no `sqrt`,
38no trig, no π.
41x = 0;  y = r;  d = 1 - r
42while x <= y:
43    plot8(x, y)
44    if d < 0:                 # midpoint (x+1, y-1/2) is inside
45        d += 2*x + 3
46    else:                     # outside
47        d += 2*(x - y) + 5
49
52`d` is the sign of `F(x, y) = x² + y² − r²` evaluated at the midpoint between
53the two candidate pixels, carried forward incrementally. Inside means keep `y`,
54outside means step it in. The visualization shows the two candidates (`E`/`SE`),
55the midpoint under test, and lights up whichever branch just executed.
57Only the 0°–45° octant is computed. Inside that wedge the slope stays between
580 and −1, so `x` advances by exactly 1 every iteration and `y` either holds or
59drops by 1 — never more. The other seven octants are reflections:
62[(x, y), (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)]
65That is D₄, the complete symmetry group of the square lattice. There is no
66ninth symmetry available to any shape on a square grid.
68Cost is **O(r)**: the loop runs `r/√2 ≈ 0.707r` times, so the full circle is
69`4√2·r ≈ 5.657` pixels per unit radius. (About 10% fewer than the circumference
70`2πr`, because roughly half the steps are diagonal and cover √2 of arc for one
Replace the random sprinkle with a golden-angle sequence   73## Right pane: golden angle
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   74
Replace the random sprinkle with a golden-angle sequence   76const golden = 2.0 * PI / ((1.0 + sqrt(5.0)) / 2.0) ^ 2   # ~137.507 deg
77for k in 0 ..< n:
78  let t = float(k) * golden
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   79  samples.add (int(round(r * cos(t))), int(round(r * sin(t))))
Replace the random sprinkle with a golden-angle sequence   82No octants, no mirroring, no decision variable — and **no randomness**. It is as
83deterministic as Bresenham. Yet its output has a *trivial automorphism group*:
84no rotation or reflection of the lattice maps the pixel set to itself.
86That is the point of using the golden angle rather than a random sprinkle. What
87destroys the 8-fold symmetry is not unpredictability, it is **incommensurability
88with the grid**. 2pi/phi^2 is the "most irrational" rotation available, so the
89sequence never falls into step with the axes.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   90
91Both panes print a live symmetry count, computed by testing all 8 lattice
Replace the random sprinkle with a golden-angle sequence   92operations against the drawn cells. Bresenham reports 8/8, golden angle 1/8.
94### Coverage
96Low discrepancy also means it never clumps, which independent random sampling
97does. Worst angular hole in the ring at r = 2000, against Bresenham's
98lattice-limited 0.041 deg:
100| oversample | golden angle | uniform random |
101|---|---|---|
102| 1x | 0.064 deg | 0.382 deg |
103| 2x | **0.041 deg** | 0.165 deg |
104| 4x | **0.041 deg** | 0.103 deg |
105| 6x | **0.041 deg** | 0.064 deg |
107Golden angle reaches the lattice limit at 2x oversample. Uniform random has not
108got there by 6x. Press `[` to drop toward 1x and watch holes open in the ring.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   109
Replace the random sprinkle with a golden-angle sequence   110### The spectral signature
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   111
112Take the radial error as a function of angle and transform it. Bresenham's
113spectrum has power **only** at harmonics that are multiples of 4 — the rotation
Replace the random sprinkle with a golden-angle sequence   114subgroup C4 forces 90-degree periodicity — and is *exactly zero* everywhere
115else. Forbidden harmonics, like a crystal's forbidden diffraction peaks. At
116r = 2000, mean power per harmonic over k = 1..60:
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   117
Replace the random sprinkle with a golden-angle sequence   118| | multiples of 4 | every other harmonic |
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   119|---|---|---|
Replace the random sprinkle with a golden-angle sequence   120| Bresenham | 0.00420 | **0.000000** |
121| golden angle | 0.00239 | 0.00064 |
122| uniform random | 0.00248 | 0.00109 |
124Worth being precise about what this does and does not show. Golden angle still
125carries a 4-fold component, and so does uniform random — that part is inherited
126from snapping to a square lattice at all, not from the sampling rule. What
127separates Bresenham is the *exact zeros*: it has harmonics that are structurally
128forbidden, and the other two have no forbidden harmonics at all.
130Golden angle is also not spectrally special here. Its advantage over random is
131coverage and determinism, not a flatter spectrum.
133### What it costs
135Visible in the panel: several angles taken per cell landed, ~25% more cells for
136the same circle (rounding independent directions sometimes picks a cell further
137from the curve than the midpoint test would), and trig per sample where
138Bresenham used integer adds. For drawing one circle, Bresenham wins outright.
140The trade only pays when structured error is worse than unstructured error of
141the same size — which is exactly why production renderers reach for blue-noise
142and low-discrepancy sampling, and why causal set theory in physics gives up a
143regular lattice to keep Lorentz invariance.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart   144
145

Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	1	# bresenham-circle
	2
	3	Bresenham's midpoint circle algorithm, stepped one decision at a time, next to a
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	4	golden-angle sampler that draws the same circle with zero lattice
	5	symmetries — and no randomness at all.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	6
	7	Written in [Nim](https://nim-lang.org) with [naylib](https://github.com/planetis-m/naylib).
	8
	9	![screenshot](docs/screenshot.png)
	10
	11	## Build
	12
	13	```sh
	14	nimble build
	15	./bresenham
	16	```
	17
	18	Flags: `--r=N` start at a radius, `--shot` render to `shot.png` and exit,
	19	`--frame=N` which frame to capture.
	20
	21	## Controls
	22
	23	\| key \| \|
	24	\|---\|---\|
	25	\| `SPACE` \| one iteration of the loop body \|
	26	\| `A` \| auto-step \|
	27	\| `R` \| reset \|
	28	\| `UP` / `DOWN` \| radius (hold to scrub, accelerating) \|
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	29	\| `[` `]` \| golden-angle oversample factor \|
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	30	\| `ESC` \| quit \|
	31
	32	The window is resizable, and the maximum radius is whatever currently fits —
	33	grow the window and the cap grows with it.
	34
	35	## Left pane: Bresenham
	36
	37	The whole algorithm is three integers and a sign test. No floats, no `sqrt`,
	38	no trig, no π.
	39
	40	```nim
	41	x = 0; y = r; d = 1 - r
	42	while x <= y:
	43	plot8(x, y)
	44	if d < 0: # midpoint (x+1, y-1/2) is inside
	45	d += 2*x + 3
	46	else: # outside
	47	d += 2*(x - y) + 5
	48	y -= 1
	49	x += 1
	50	```
	51
	52	`d` is the sign of `F(x, y) = x² + y² − r²` evaluated at the midpoint between
	53	the two candidate pixels, carried forward incrementally. Inside means keep `y`,
	54	outside means step it in. The visualization shows the two candidates (`E`/`SE`),
	55	the midpoint under test, and lights up whichever branch just executed.
	56
	57	Only the 0°–45° octant is computed. Inside that wedge the slope stays between
	58	0 and −1, so `x` advances by exactly 1 every iteration and `y` either holds or
	59	drops by 1 — never more. The other seven octants are reflections:
	60
	61	```nim
	62	[(x, y), (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)]
	63	```
	64
	65	That is D₄, the complete symmetry group of the square lattice. There is no
	66	ninth symmetry available to any shape on a square grid.
	67
	68	Cost is O(r): the loop runs `r/√2 ≈ 0.707r` times, so the full circle is
	69	`4√2·r ≈ 5.657` pixels per unit radius. (About 10% fewer than the circumference
	70	`2πr`, because roughly half the steps are diagonal and cover √2 of arc for one
	71	pixel.)
	72
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	73	## Right pane: golden angle
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	74
	75	```nim
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	76	const golden = 2.0 * PI / ((1.0 + sqrt(5.0)) / 2.0) ^ 2 # ~137.507 deg
	77	for k in 0 ..< n:
	78	let t = float(k) * golden
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	79	samples.add (int(round(r * cos(t))), int(round(r * sin(t))))
	80	```
	81
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	82	No octants, no mirroring, no decision variable — and no randomness. It is as
	83	deterministic as Bresenham. Yet its output has a trivial automorphism group:
	84	no rotation or reflection of the lattice maps the pixel set to itself.
	85
	86	That is the point of using the golden angle rather than a random sprinkle. What
	87	destroys the 8-fold symmetry is not unpredictability, it is **incommensurability
	88	with the grid**. 2pi/phi^2 is the "most irrational" rotation available, so the
	89	sequence never falls into step with the axes.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	90
	91	Both panes print a live symmetry count, computed by testing all 8 lattice
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	92	operations against the drawn cells. Bresenham reports 8/8, golden angle 1/8.
	93
	94	### Coverage
	95
	96	Low discrepancy also means it never clumps, which independent random sampling
	97	does. Worst angular hole in the ring at r = 2000, against Bresenham's
	98	lattice-limited 0.041 deg:
	99
	100	\| oversample \| golden angle \| uniform random \|
	101	\|---\|---\|---\|
	102	\| 1x \| 0.064 deg \| 0.382 deg \|
	103	\| 2x \| 0.041 deg \| 0.165 deg \|
	104	\| 4x \| 0.041 deg \| 0.103 deg \|
	105	\| 6x \| 0.041 deg \| 0.064 deg \|
	106
	107	Golden angle reaches the lattice limit at 2x oversample. Uniform random has not
	108	got there by 6x. Press `[` to drop toward 1x and watch holes open in the ring.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	109
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	110	### The spectral signature
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	111
	112	Take the radial error as a function of angle and transform it. Bresenham's
	113	spectrum has power only at harmonics that are multiples of 4 — the rotation
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	114	subgroup C4 forces 90-degree periodicity — and is exactly zero everywhere
	115	else. Forbidden harmonics, like a crystal's forbidden diffraction peaks. At
	116	r = 2000, mean power per harmonic over k = 1..60:
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	117
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	118	\| \| multiples of 4 \| every other harmonic \|
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	119	\|---\|---\|---\|
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 6h ago	120	\| Bresenham \| 0.00420 \| 0.000000 \|
	121	\| golden angle \| 0.00239 \| 0.00064 \|
	122	\| uniform random \| 0.00248 \| 0.00109 \|
	123
	124	Worth being precise about what this does and does not show. Golden angle still
	125	carries a 4-fold component, and so does uniform random — that part is inherited
	126	from snapping to a square lattice at all, not from the sampling rule. What
	127	separates Bresenham is the exact zeros: it has harmonics that are structurally
	128	forbidden, and the other two have no forbidden harmonics at all.
	129
	130	Golden angle is also not spectrally special here. Its advantage over random is
	131	coverage and determinism, not a flatter spectrum.
	132
	133	### What it costs
	134
	135	Visible in the panel: several angles taken per cell landed, ~25% more cells for
	136	the same circle (rounding independent directions sometimes picks a cell further
	137	from the curve than the midpoint test would), and trig per sample where
	138	Bresenham used integer adds. For drawing one circle, Bresenham wins outright.
	139
	140	The trade only pays when structured error is worse than unstructured error of
	141	the same size — which is exactly why production renderers reach for blue-noise
	142	and low-discrepancy sampling, and why causal set theory in physics gives up a
	143	regular lattice to keep Lorentz invariance.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 7h ago	144
	145	## License
	146
	147	MIT