rickub
nandi/bresenham-circlepublic⑂ Fork 0
⑂ 686a3734f6c11f3f22f869c7300badcd271fe34a
Branches
main View all branches → View all tags →
Commits
⬇ Clone ▾
git clone https://git.rickub.com/nandi/bresenham-circle.git
git clone ssh://git@rickub.com/nandi/bresenham-circle.git

Host key fingerprint (ed25519): SHA256:iycHnxEyq0Q7uyVpB7JlznP0G7JrTPXLYRcAU5CSLhc — verify it before your first connect.

bresenham.nim · 359 lines · 12.6 KBNim Blame HistoryRaw
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago1## Two ways to put a circle on a grid, side by side.
2##
3## left -- Bresenham: integer decisions, one octant, mirrored 8 ways.
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago4## right -- Golden angle: k * 137.5 deg, snapped to cells.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago5##
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago6## Both land on the same lattice, and both are fully deterministic. The
7## difference is the symmetry of the *selection*: Bresenham's is exactly
8## 8-fold, the golden-angle sequence's is trivial. Randomness was never what
9## bought that -- incommensurability with the grid is.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago10##
11## Controls: SPACE step A auto R reset UP/DOWN radius [ ] oversample ESC
12
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago13import raylib, std/[strformat, os, math, strutils, algorithm, sets, hashes]
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago14
15const
16 InitW = 1400
17 InitH = 760
18 PanelWant = 380
19 MinCell = 2
20 MinRadius = 2
21
22 Bg = Color(r: 18, g: 18, b: 24, a: 255)
23 GridLine = Color(r: 36, g: 36, b: 46, a: 255)
24 Axis = Color(r: 70, g: 70, b: 88, a: 255)
25 TrueArc = Color(r: 100, g: 100, b: 128, a: 255)
26 Octant = Color(r: 88, g: 166, b: 255, a: 255)
27 Mirror = Color(r: 88, g: 166, b: 255, a: 105)
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago28 Golden = Color(r: 118, g: 222, b: 160, a: 210)
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago29 Cursor = Color(r: 255, g: 176, b: 64, a: 255)
30 Candidate = Color(r: 255, g: 176, b: 64, a: 60)
31 Mid = Color(r: 255, g: 92, b: 92, a: 255)
32 Ink = Color(r: 226, g: 226, b: 236, a: 255)
33 Dim = Color(r: 130, g: 130, b: 148, a: 255)
34 HiLine = Color(r: 40, g: 62, b: 92, a: 255)
35
36type
37 Branch = enum brNone, brEast, brSouthEast
38
39 Cells = HashSet[(int, int)]
40
41 State = object
42 r: int
43 # -- Bresenham
44 x, y, d: int ## the entire algorithm state: three integers
45 plotted: seq[(int, int)] ## octant only; the rest is reflection
46 bcells: Cells ## all 8 octants, for counting
47 branch: Branch
48 lastUpdate: string
49 done: bool
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago50 # -- Golden angle
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago51 over: int ## samples per Bresenham pixel
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago52 samples: seq[(int, int)] ## precomputed, revealed progressively
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago53 revealed: int
54 scells: Cells
55 perStep: int
56
57# ---------------------------------------------------------------- algorithms --
58
59proc mirrors(x, y: int): array[8, (int, int)] =
60 ## The complete symmetry group of the square lattice: D4, order 8.
61 [(x, y), (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)]
62
63proc reset(s: var State, r: int, over = -1) =
64 if over >= 0: s.over = over
65 if s.over == 0: s.over = 4
66 s.r = r
67 s.x = 0
68 s.y = r
69 s.d = 1 - r ## F(1, r - 1/2), the 1/4 dropped so d stays integral
70 s.plotted = @[]
71 s.bcells = initHashSet[(int, int)]()
72 s.branch = brNone
73 s.lastUpdate = ""
74 s.done = false
75
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago76 # Golden angle: theta_k = k * 2*pi/phi^2, about 137.507 degrees. Wholly
77 # deterministic, yet incommensurable with the lattice -- so no rotation or
78 # reflection maps the result to itself. Low discrepancy, so it also never
79 # clumps the way independent sampling does.
80 const golden = 2.0 * PI / ((1.0 + sqrt(5.0)) / 2.0) ^ 2
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago81 let n = int(s.over.float * 4.0 * sqrt(2.0) * r.float)
82 s.samples = newSeqOfCap[(int, int)](n)
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago83 for k in 0 ..< n:
84 let t = float(k) * golden
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago85 s.samples.add (int(round(r.float * cos(t))), int(round(r.float * sin(t))))
86 s.revealed = 0
87 s.scells = initHashSet[(int, int)]()
88 s.perStep = max(1, n div max(1, int(r.float / sqrt(2.0))))
89
90proc reveal(s: var State, k: int) =
91 let stop = min(s.revealed + k, s.samples.len)
92 while s.revealed < stop:
93 s.scells.incl s.samples[s.revealed]
94 inc s.revealed
95
96proc step(s: var State) =
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago97 ## Exactly one iteration of the Bresenham loop body, plus the golden-angle
98 ## sequence's proportional share so the two fill at a comparable rate.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago99 if s.done: return
100 if s.x > s.y:
101 s.done = true
102 s.branch = brNone
103 s.reveal(s.samples.len)
104 return
105
106 s.plotted.add (s.x, s.y)
107 for m in mirrors(s.x, s.y): s.bcells.incl m
108
109 if s.d < 0:
110 # midpoint (x+1, y-1/2) is INSIDE the circle -> East, keep y
111 s.branch = brEast
112 s.lastUpdate = fmt"d += 2*{s.x} + 3 = {2 * s.x + 3}"
113 s.d += 2 * s.x + 3
114 else:
115 # midpoint is OUTSIDE -> South-East, step y in
116 s.branch = brSouthEast
117 s.lastUpdate = fmt"d += 2*({s.x} - {s.y}) + 5 = {2 * (s.x - s.y) + 5}"
118 s.d += 2 * (s.x - s.y) + 5
119 dec s.y
120 inc s.x
121
122 s.reveal(s.perStep)
123 if s.x > s.y:
124 s.done = true
125 s.reveal(s.samples.len)
126
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago127proc largestGap(c: Cells): float =
128 ## Worst angular hole in the ring, in degrees. Bresenham is lattice-limited;
129 ## anything that samples directions has to buy its way down to that.
130 if c.len < 2: return 360.0
131 var a = newSeqOfCap[float](c.len)
132 for (x, y) in c: a.add arctan2(y.float, x.float).floorMod(2.0 * PI)
133 a.sort()
134 for i in 0 ..< a.high: result = max(result, a[i + 1] - a[i])
135 result = max(result, a[0] + 2.0 * PI - a[^1])
136 result = radToDeg(result)
137
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago138proc symmetries(c: Cells): int =
139 ## How many of the lattice's 8 symmetries actually map this pixel set to
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago140 ## itself. Bresenham: 8. The golden-angle set: 1, the identity alone.
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago141 if c.len == 0: return 0
142 for k in 0 ..< 8:
143 var ok = true
144 for (x, y) in c:
145 if mirrors(x, y)[k] notin c:
146 ok = false
147 break
148 if ok: inc result
149
150# ------------------------------------------------------------------- layout --
151
152proc layout(sw, sh: int): tuple[panelW, gridW, halfW, maxR, cellCap: int] =
153 let panelW = clamp(PanelWant, 280, sw div 3)
154 let gridW = sw - panelW
155 let halfW = gridW div 2
156 let avail = max(min(halfW - 30, sh - 150), MinCell)
157 let maxR = max(MinRadius, (avail div MinCell - 3) div 2)
158 (panelW, gridW, halfW, maxR, avail)
159
160# ------------------------------------------------------------------ drawing --
161
162type View = object
163 ox, oy, cell, half: int
164
165proc cx(v: View, gx: int): int = v.ox + gx * v.cell - v.half
166proc cy(v: View, gy: int): int = v.oy - gy * v.cell - v.half
167
168proc drawRect(x, y, w, h: int, c: Color) =
169 drawRectangle(x.int32, y.int32, w.int32, h.int32, c)
170
171proc drawRectLines(x, y, w, h: int, c: Color) =
172 drawRectangleLines(x.int32, y.int32, w.int32, h.int32, c)
173
174proc drawLn(x1, y1, x2, y2: int, c: Color) =
175 drawLine(x1.int32, y1.int32, x2.int32, y2.int32, c)
176
177proc text(s: string, x, y, size: int, c: Color) =
178 drawText(s, x.int32, y.int32, size.int32, c)
179
180proc backdrop(v: View, r: int) =
181 ## Grid, axes and the ideal circle both methods are chasing.
182 let ext = r + 1
183 if v.cell >= 9:
184 for i in -ext .. ext:
185 drawLn(v.cx(-ext), v.cy(i) + v.half, v.cx(ext) + v.cell, v.cy(i) + v.half, GridLine)
186 drawLn(v.cx(i) + v.half, v.cy(-ext) + v.cell, v.cx(i) + v.half, v.cy(ext), GridLine)
187 drawLn(v.cx(-ext), v.oy, v.cx(ext) + v.cell, v.oy, Axis)
188 drawLn(v.ox, v.cy(-ext) + v.cell, v.ox, v.cy(ext), Axis)
189 drawCircleLines(v.ox.int32, v.oy.int32, float32(r * v.cell), TrueArc)
190
191proc main =
192 setConfigFlags(flags(WindowResizable))
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago193 initWindow(InitW, InitH, "Bresenham vs golden angle")
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago194 defer: closeWindow()
195 setWindowMinSize(900, 640)
196 setTargetFPS(60)
197
198 var
199 s = State()
200 auto = false
201 held = 0
202 tick = 0
203 frames = 0
204 shot = "--shot" in commandLineParams()
205 shotFrame = 400
206 startR = 12
207 for a in commandLineParams():
208 if a.startsWith("--r="): startR = max(parseInt(a[4 .. ^1]), MinRadius)
209 elif a.startsWith("--frame="): shotFrame = parseInt(a[8 .. ^1])
210 s.over = 4
211 s.reset(min(startR, layout(getScreenWidth().int, getScreenHeight().int).maxR))
212 if shot: auto = true
213
214 while not windowShouldClose():
215 inc frames
216
217 let
218 sw = getScreenWidth().int
219 sh = getScreenHeight().int
220 (panelW, gridW, halfW, maxR, _) = layout(sw, sh)
221 if s.r > maxR: s.reset(maxR)
222
223 # ---- input
224 if isKeyPressed(Space): s.step()
225 if isKeyPressed(A): auto = not auto
226 if isKeyPressed(R): s.reset(s.r)
227 if isKeyPressed(RightBracket) and s.over < 12: s.reset(s.r, s.over + 1)
228 if isKeyPressed(LeftBracket) and s.over > 1: s.reset(s.r, s.over - 1)
229 var delta = 0
230 if isKeyPressed(Up): delta = 1
231 elif isKeyPressed(Down): delta = -1
232 elif isKeyDown(Up) or isKeyDown(Down):
233 inc held
234 if held > 18:
235 let fast = if held > 70: 1 else: 3
236 if held mod fast == 0: delta = if isKeyDown(Up): 1 else: -1
237 else:
238 held = 0
239 if delta != 0:
240 let want = clamp(s.r + delta, MinRadius, maxR)
241 if want != s.r: s.reset(want)
242 if auto and not s.done:
243 inc tick
244 if tick mod max(1, 10 - s.r div 8) == 0: s.step()
245
246 # ---- both panes share a cell size so they are directly comparable
247 let
248 span = 2 * s.r + 3
249 cell = max(min(halfW - 30, sh - 150) div span, MinCell)
250 oy = sh div 2 + 10
251 left = View(ox: halfW div 2, oy: oy, cell: cell, half: cell div 2)
252 right = View(ox: halfW + halfW div 2, oy: oy, cell: cell, half: cell div 2)
253
254 drawing:
255 clearBackground(Bg)
256
257 # ================= left: Bresenham =================
258 backdrop(left, s.r)
259 let ext = s.r + 1
260 drawLn(left.ox, left.oy, left.ox, left.cy(ext) + left.half, Axis)
261 drawLn(left.ox, left.oy, left.cx(ext) + left.half, left.cy(ext) + left.half, Axis)
262
263 for (px, py) in s.plotted:
264 for k, (mx, my) in mirrors(px, py):
265 drawRect(left.cx(mx), left.cy(my), cell, cell,
266 if k == 0: Octant else: Mirror)
267
268 if not s.done:
269 drawRectLines(left.cx(s.x), left.cy(s.y), cell, cell, Cursor)
270 if s.x + 1 <= s.y:
271 drawRect(left.cx(s.x + 1), left.cy(s.y), cell, cell, Candidate)
272 drawRect(left.cx(s.x + 1), left.cy(s.y - 1), cell, cell, Candidate)
273 drawCircle(int32(left.cx(s.x + 1) + left.half), int32(left.cy(s.y) + cell),
274 float32(max(3, cell div 5)), Mid)
275
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago276 # ================= right: golden angle =================
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago277 backdrop(right, s.r)
278 for (mx, my) in s.scells:
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago279 drawRect(right.cx(mx), right.cy(my), cell, cell, Golden)
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago280
281 # ---- titles and per-pane stats
282 let
283 bSym = symmetries(s.bcells)
284 sSym = symmetries(s.scells)
285 lx = 24
286 rx = halfW + 24
287 text("BRESENHAM", lx, 16, 20, Octant)
288 text("one octant, mirrored 8 ways", lx, 40, 14, Dim)
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago289 text("GOLDEN ANGLE", rx, 16, 20, Golden)
290 text(fmt"k x 137.507 deg, snapped ({s.over}x oversample)", rx, 40, 14, Dim)
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago291
292 let by = sh - 66
293 text(fmt"{s.bcells.len} cells {s.plotted.len} computed, rest free", lx, by, 16, Ink)
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago294 text(fmt"symmetries {bSym}/8 worst gap {largestGap(s.bcells):.2f} deg",
295 lx, by + 22, 16, Octant)
296 text(fmt"{s.scells.len} cells {s.revealed} angles taken", rx, by, 16, Ink)
297 text(fmt"symmetries {sSym}/8 worst gap {largestGap(s.scells):.2f} deg",
298 rx, by + 22, 16, Golden)
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago299
300 drawLn(halfW, 0, halfW, sh, GridLine)
301
302 # ================= panel =================
303 let px = gridW + 24
304 drawLn(gridW, 0, gridW, sh, GridLine)
305
306 text("MIDPOINT CIRCLE", px, 20, 22, Ink)
307 text(fmt"radius {s.r} (max {maxR} at {sw}x{sh})", px, 48, 15, Dim)
308
309 let code = [
310 "x = 0; y = r; d = 1 - r",
311 "while x <= y:",
312 " plot8(x, y)",
313 " if d < 0: # mid inside",
314 " d += 2*x + 3",
315 " else: # mid outside",
316 " d += 2*(x - y) + 5",
317 " y -= 1",
318 " x += 1",
319 ]
320 let lit =
321 case s.branch
322 of brEast: @[2, 3, 4, 8]
323 of brSouthEast: @[2, 5, 6, 7, 8]
324 of brNone: @[]
325 for i, line in code:
326 let ly = 84 + i * 22
327 if i in lit: drawRect(px - 8, ly - 3, panelW - 32, 22, HiLine)
328 text(line, px, ly, 16, if i in lit: Ink else: Dim)
329
330 var sy = 300
331 text("state", px, sy, 16, Dim); sy += 26
332 text(fmt"x = {s.x}", px, sy, 20, Ink); sy += 26
333 text(fmt"y = {s.y}", px, sy, 20, Ink); sy += 26
334 text(fmt"d = {s.d}", px, sy, 20, (if s.d < 0: Octant else: Cursor)); sy += 32
335 text(s.lastUpdate, px, sy, 15, Cursor); sy += 30
336 if s.done:
337 text("done -- x > y, octant closed", px, sy, 18, Octant)
338 elif s.x + 1 <= s.y:
339 text(fmt"testing midpoint ({s.x + 1}, {s.y}-1/2)", px, sy, 15, Mid)
340
341 var ly = sh - 170
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago342 text("cost of no lattice symmetry", px, ly, 15, Dim); ly += 24
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago343 if s.done and s.scells.len > 0:
344 let waste = s.revealed.float / s.scells.len.float
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago345 text(fmt"{waste:.1f} angles per cell drawn", px, ly, 15, Golden); ly += 22
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago346 let gap = 100.0 * (s.scells.len.float / max(1, s.bcells.len).float - 1.0)
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago347 text(fmt"{gap:+.0f}% cells vs bresenham", px, ly, 15, Golden); ly += 30
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago348 else:
349 ly += 52
350
351 text("SPACE step A auto R reset", px, ly, 15, (if auto: Cursor else: Dim)); ly += 20
352 text("UP/DOWN radius (hold to scrub)", px, ly, 15, Dim); ly += 20
Replace the random sprinkle with a golden-angle sequence 686a373 nandi 12h ago353 text("[ ] golden-angle oversample", px, ly, 15, Dim)
Bresenham midpoint circle visualizer, with a zero-symmetry counterpart 3d0b0a3 nandi 14h ago354
355 if shot and frames == shotFrame:
356 takeScreenshot("shot.png")
357 break
358
359main()