## Two ways to put a circle on a grid, side by side. ## ## left -- Bresenham: integer decisions, one octant, mirrored 8 ways. ## right -- Poisson sprinkle: uniform directions snapped to cells. ## ## Both land on the same lattice. The difference is the symmetry of the ## *selection*: Bresenham's is exactly 8-fold, the sprinkle's is trivial. ## ## Controls: SPACE step A auto R reset UP/DOWN radius [ ] oversample ESC import raylib, std/[strformat, os, math, strutils, random, sets, hashes] const InitW = 1400 InitH = 760 PanelWant = 380 MinCell = 2 MinRadius = 2 Bg = Color(r: 18, g: 18, b: 24, a: 255) GridLine = Color(r: 36, g: 36, b: 46, a: 255) Axis = Color(r: 70, g: 70, b: 88, a: 255) TrueArc = Color(r: 100, g: 100, b: 128, a: 255) Octant = Color(r: 88, g: 166, b: 255, a: 255) Mirror = Color(r: 88, g: 166, b: 255, a: 105) Sprink = Color(r: 118, g: 222, b: 160, a: 210) Cursor = Color(r: 255, g: 176, b: 64, a: 255) Candidate = Color(r: 255, g: 176, b: 64, a: 60) Mid = Color(r: 255, g: 92, b: 92, a: 255) Ink = Color(r: 226, g: 226, b: 236, a: 255) Dim = Color(r: 130, g: 130, b: 148, a: 255) HiLine = Color(r: 40, g: 62, b: 92, a: 255) type Branch = enum brNone, brEast, brSouthEast Cells = HashSet[(int, int)] State = object r: int # -- Bresenham x, y, d: int ## the entire algorithm state: three integers plotted: seq[(int, int)] ## octant only; the rest is reflection bcells: Cells ## all 8 octants, for counting branch: Branch lastUpdate: string done: bool # -- Poisson sprinkle over: int ## samples per Bresenham pixel samples: seq[(int, int)] ## pre-rolled, revealed progressively revealed: int scells: Cells perStep: int # ---------------------------------------------------------------- algorithms -- proc mirrors(x, y: int): array[8, (int, int)] = ## The complete symmetry group of the square lattice: D4, order 8. [(x, y), (y, x), (y, -x), (x, -y), (-x, -y), (-y, -x), (-y, x), (-x, y)] proc reset(s: var State, r: int, over = -1) = if over >= 0: s.over = over if s.over == 0: s.over = 4 s.r = r s.x = 0 s.y = r s.d = 1 - r ## F(1, r - 1/2), the 1/4 dropped so d stays integral s.plotted = @[] s.bcells = initHashSet[(int, int)]() s.branch = brNone s.lastUpdate = "" s.done = false # Sprinkle: uniform in angle, so isotropic in distribution but with no # exact symmetry at all. Fixed seed per radius so runs are reproducible. var rng = initRand(0xC0FFEE + r * 7919) let n = int(s.over.float * 4.0 * sqrt(2.0) * r.float) s.samples = newSeqOfCap[(int, int)](n) for _ in 1 .. n: let t = rng.rand(2.0 * PI) s.samples.add (int(round(r.float * cos(t))), int(round(r.float * sin(t)))) s.revealed = 0 s.scells = initHashSet[(int, int)]() s.perStep = max(1, n div max(1, int(r.float / sqrt(2.0)))) proc reveal(s: var State, k: int) = let stop = min(s.revealed + k, s.samples.len) while s.revealed < stop: s.scells.incl s.samples[s.revealed] inc s.revealed proc step(s: var State) = ## Exactly one iteration of the Bresenham loop body, plus the sprinkle's ## proportional share of samples so the two fill at a comparable rate. if s.done: return if s.x > s.y: s.done = true s.branch = brNone s.reveal(s.samples.len) return s.plotted.add (s.x, s.y) for m in mirrors(s.x, s.y): s.bcells.incl m if s.d < 0: # midpoint (x+1, y-1/2) is INSIDE the circle -> East, keep y s.branch = brEast s.lastUpdate = fmt"d += 2*{s.x} + 3 = {2 * s.x + 3}" s.d += 2 * s.x + 3 else: # midpoint is OUTSIDE -> South-East, step y in s.branch = brSouthEast s.lastUpdate = fmt"d += 2*({s.x} - {s.y}) + 5 = {2 * (s.x - s.y) + 5}" s.d += 2 * (s.x - s.y) + 5 dec s.y inc s.x s.reveal(s.perStep) if s.x > s.y: s.done = true s.reveal(s.samples.len) proc symmetries(c: Cells): int = ## How many of the lattice's 8 symmetries actually map this pixel set to ## itself. Bresenham: 8. A sprinkle: 1 (the identity), essentially always. if c.len == 0: return 0 for k in 0 ..< 8: var ok = true for (x, y) in c: if mirrors(x, y)[k] notin c: ok = false break if ok: inc result # ------------------------------------------------------------------- layout -- proc layout(sw, sh: int): tuple[panelW, gridW, halfW, maxR, cellCap: int] = let panelW = clamp(PanelWant, 280, sw div 3) let gridW = sw - panelW let halfW = gridW div 2 let avail = max(min(halfW - 30, sh - 150), MinCell) let maxR = max(MinRadius, (avail div MinCell - 3) div 2) (panelW, gridW, halfW, maxR, avail) # ------------------------------------------------------------------ drawing -- type View = object ox, oy, cell, half: int proc cx(v: View, gx: int): int = v.ox + gx * v.cell - v.half proc cy(v: View, gy: int): int = v.oy - gy * v.cell - v.half proc drawRect(x, y, w, h: int, c: Color) = drawRectangle(x.int32, y.int32, w.int32, h.int32, c) proc drawRectLines(x, y, w, h: int, c: Color) = drawRectangleLines(x.int32, y.int32, w.int32, h.int32, c) proc drawLn(x1, y1, x2, y2: int, c: Color) = drawLine(x1.int32, y1.int32, x2.int32, y2.int32, c) proc text(s: string, x, y, size: int, c: Color) = drawText(s, x.int32, y.int32, size.int32, c) proc backdrop(v: View, r: int) = ## Grid, axes and the ideal circle both methods are chasing. let ext = r + 1 if v.cell >= 9: for i in -ext .. ext: drawLn(v.cx(-ext), v.cy(i) + v.half, v.cx(ext) + v.cell, v.cy(i) + v.half, GridLine) drawLn(v.cx(i) + v.half, v.cy(-ext) + v.cell, v.cx(i) + v.half, v.cy(ext), GridLine) drawLn(v.cx(-ext), v.oy, v.cx(ext) + v.cell, v.oy, Axis) drawLn(v.ox, v.cy(-ext) + v.cell, v.ox, v.cy(ext), Axis) drawCircleLines(v.ox.int32, v.oy.int32, float32(r * v.cell), TrueArc) proc main = setConfigFlags(flags(WindowResizable)) initWindow(InitW, InitH, "Bresenham vs Poisson sprinkle") defer: closeWindow() setWindowMinSize(900, 640) setTargetFPS(60) var s = State() auto = false held = 0 tick = 0 frames = 0 shot = "--shot" in commandLineParams() shotFrame = 400 startR = 12 for a in commandLineParams(): if a.startsWith("--r="): startR = max(parseInt(a[4 .. ^1]), MinRadius) elif a.startsWith("--frame="): shotFrame = parseInt(a[8 .. ^1]) s.over = 4 s.reset(min(startR, layout(getScreenWidth().int, getScreenHeight().int).maxR)) if shot: auto = true while not windowShouldClose(): inc frames let sw = getScreenWidth().int sh = getScreenHeight().int (panelW, gridW, halfW, maxR, _) = layout(sw, sh) if s.r > maxR: s.reset(maxR) # ---- input if isKeyPressed(Space): s.step() if isKeyPressed(A): auto = not auto if isKeyPressed(R): s.reset(s.r) if isKeyPressed(RightBracket) and s.over < 12: s.reset(s.r, s.over + 1) if isKeyPressed(LeftBracket) and s.over > 1: s.reset(s.r, s.over - 1) var delta = 0 if isKeyPressed(Up): delta = 1 elif isKeyPressed(Down): delta = -1 elif isKeyDown(Up) or isKeyDown(Down): inc held if held > 18: let fast = if held > 70: 1 else: 3 if held mod fast == 0: delta = if isKeyDown(Up): 1 else: -1 else: held = 0 if delta != 0: let want = clamp(s.r + delta, MinRadius, maxR) if want != s.r: s.reset(want) if auto and not s.done: inc tick if tick mod max(1, 10 - s.r div 8) == 0: s.step() # ---- both panes share a cell size so they are directly comparable let span = 2 * s.r + 3 cell = max(min(halfW - 30, sh - 150) div span, MinCell) oy = sh div 2 + 10 left = View(ox: halfW div 2, oy: oy, cell: cell, half: cell div 2) right = View(ox: halfW + halfW div 2, oy: oy, cell: cell, half: cell div 2) drawing: clearBackground(Bg) # ================= left: Bresenham ================= backdrop(left, s.r) let ext = s.r + 1 drawLn(left.ox, left.oy, left.ox, left.cy(ext) + left.half, Axis) drawLn(left.ox, left.oy, left.cx(ext) + left.half, left.cy(ext) + left.half, Axis) for (px, py) in s.plotted: for k, (mx, my) in mirrors(px, py): drawRect(left.cx(mx), left.cy(my), cell, cell, if k == 0: Octant else: Mirror) if not s.done: drawRectLines(left.cx(s.x), left.cy(s.y), cell, cell, Cursor) if s.x + 1 <= s.y: drawRect(left.cx(s.x + 1), left.cy(s.y), cell, cell, Candidate) drawRect(left.cx(s.x + 1), left.cy(s.y - 1), cell, cell, Candidate) drawCircle(int32(left.cx(s.x + 1) + left.half), int32(left.cy(s.y) + cell), float32(max(3, cell div 5)), Mid) # ================= right: Poisson sprinkle ================= backdrop(right, s.r) for (mx, my) in s.scells: drawRect(right.cx(mx), right.cy(my), cell, cell, Sprink) # ---- titles and per-pane stats let bSym = symmetries(s.bcells) sSym = symmetries(s.scells) lx = 24 rx = halfW + 24 text("BRESENHAM", lx, 16, 20, Octant) text("one octant, mirrored 8 ways", lx, 40, 14, Dim) text("POISSON SPRINKLE", rx, 16, 20, Sprink) text(fmt"uniform directions, snapped ({s.over}x oversample)", rx, 40, 14, Dim) let by = sh - 66 text(fmt"{s.bcells.len} cells {s.plotted.len} computed, rest free", lx, by, 16, Ink) text(fmt"exact symmetries: {bSym} / 8", lx, by + 22, 16, Octant) text(fmt"{s.scells.len} cells {s.revealed} samples rolled", rx, by, 16, Ink) text(fmt"exact symmetries: {sSym} / 8", rx, by + 22, 16, Sprink) drawLn(halfW, 0, halfW, sh, GridLine) # ================= panel ================= let px = gridW + 24 drawLn(gridW, 0, gridW, sh, GridLine) text("MIDPOINT CIRCLE", px, 20, 22, Ink) text(fmt"radius {s.r} (max {maxR} at {sw}x{sh})", px, 48, 15, Dim) let code = [ "x = 0; y = r; d = 1 - r", "while x <= y:", " plot8(x, y)", " if d < 0: # mid inside", " d += 2*x + 3", " else: # mid outside", " d += 2*(x - y) + 5", " y -= 1", " x += 1", ] let lit = case s.branch of brEast: @[2, 3, 4, 8] of brSouthEast: @[2, 5, 6, 7, 8] of brNone: @[] for i, line in code: let ly = 84 + i * 22 if i in lit: drawRect(px - 8, ly - 3, panelW - 32, 22, HiLine) text(line, px, ly, 16, if i in lit: Ink else: Dim) var sy = 300 text("state", px, sy, 16, Dim); sy += 26 text(fmt"x = {s.x}", px, sy, 20, Ink); sy += 26 text(fmt"y = {s.y}", px, sy, 20, Ink); sy += 26 text(fmt"d = {s.d}", px, sy, 20, (if s.d < 0: Octant else: Cursor)); sy += 32 text(s.lastUpdate, px, sy, 15, Cursor); sy += 30 if s.done: text("done -- x > y, octant closed", px, sy, 18, Octant) elif s.x + 1 <= s.y: text(fmt"testing midpoint ({s.x + 1}, {s.y}-1/2)", px, sy, 15, Mid) var ly = sh - 170 text("cost of zero symmetry", px, ly, 15, Dim); ly += 24 if s.done and s.scells.len > 0: let waste = s.revealed.float / s.scells.len.float text(fmt"{waste:.1f} samples per cell drawn", px, ly, 15, Sprink); ly += 22 let gap = 100.0 * (s.scells.len.float / max(1, s.bcells.len).float - 1.0) text(fmt"{gap:+.0f}% cells vs bresenham", px, ly, 15, Sprink); ly += 30 else: ly += 52 text("SPACE step A auto R reset", px, ly, 15, (if auto: Cursor else: Dim)); ly += 20 text("UP/DOWN radius (hold to scrub)", px, ly, 15, Dim); ly += 20 text("[ ] sprinkle oversample", px, ly, 15, Dim) if shot and frames == shotFrame: takeScreenshot("shot.png") break main()