cover.bend

gralha-coverage@0.1.0.1 · 1,280 lines · 199 definitions

1# Analytic coverage: line lists in pixel space are scan-converted with a winding
2# count on a few sub-scanlines per row (exact span extents in x, so the fill
3# rule holds even where contours overlap), and the result is a sparse quadtree
4# mask.
5import Base
6import gralha-text-scan@0.1.0.1/scan.bend as U
7
8# A directed line in pixel coordinates of the target grid.
9type CovLine is Data:
10  CovLine{x0: F32, y0: F32, x1: F32, y1: F32}
11
12# Coverage over a power-of-two square: uniform cells collapse to one leaf.
13type CovTree is Data:
14  CovFlat{value: F32}
15  CovQuad{a: CovTree, b: CovTree, c: CovTree, d: CovTree}
16
17# A run of cells [x0, x1) of one nonzero coverage value in a row.
18type Run is Data:
19  Run{x0: U32, x1: U32, value: F32}
20
21# A mask's coverage: rows of runs (top first, ascending runs), which a fill is
22# painted from directly, or the tree, which clip masks and sampled tiles need
23# for block and pixel queries.
24type CovData is Data:
25  CovRows{rows: List<&2, List<&2, Run>>}
26  CovTreed{tree: CovTree}
27
28# A mask placed at pixel (x, y) of its grid, size = 2^depth cells on a side.
29# w by h cells of it hold coverage; size = 2^depth is the tree's side.
30type CovMask is Data:
31  CovMask{x: U32, y: U32, w: U32, h: U32, size: U32, depth: Nat, data: CovData, present: Bool}
32
33def mask.none() -> CovMask:
34  CovMask{0, 0, 0, 0, 0, 0n, CovTreed{CovFlat{0.0}}, False{}}
35
36# Coverage of a cell from rows of runs; a slow path for masks built without a tree.
37def runs.at(rs: List<&2, Run>, +x: U32) -> F32:
38  match rs:
39    case Nil{}: 0.0
40    case Con{Run{a, b, v}, rest}:
41      +aa = a
42      +bb = b
43      +vv = v
44      U.choose(F32, U32.is_ge(x, aa) && U32.is_lt(x, bb), vv, runs.at(rest, x))
45
46def rows.at(rows: List<&2, List<&2, Run>>, +y: U32, +x: U32) -> F32:
47  match rows:
48    case Nil{}: 0.0
49    case Con{r, rest}: U.choose(F32, U32.is_eq(y, 0), runs.at(r, x), rows.at(rest, (y - 1 : U32), x))
50
51def mask.present(+m: CovMask) -> Bool:
52  CovMask{x, y, w, h, size, depth, tree, present} = m
53  present
54
55@unsafe
56def tree.at(t: CovTree, +half: U32, +x: U32, +y: U32) -> F32:
57  match t:
58    case CovFlat{v}: v
59    case CovQuad{a, b, c, d}:
60      +left = U32.is_lt(x, half)
61      +top = U32.is_lt(y, half)
62      +xx = U.choose(U32, left, x, (x - half : U32))
63      +yy = U.choose(U32, top, y, (y - half : U32))
64      +next = U32.div(half, 2)
65      tree.at(U.choose(CovTree, top, U.choose(CovTree, left, a, b), U.choose(CovTree, left, c, d)), next, xx, yy)
66
67def data.at(d: CovData, +half: U32, +x: U32, +y: U32) -> F32:
68  match d:
69    case CovTreed{t}: tree.at(t, half, x, y)
70    case CovRows{rows}: rows.at(rows, y, x)
71
72def mask.at.in(outside: Bool, d: CovData, +half: U32, +x: U32, +y: U32) -> F32:
73  match outside:
74    case True{}: 0.0
75    case False{}: data.at(d, half, x, y)
76
77# Coverage of the pixel containing (px, py), in grid pixel coordinates; the
78# reads branch through matches, not lambdas, since they run once per pixel.
79def mask.at(+m: CovMask, +px: F32, +py: F32) -> F32:
80  CovMask{x, y, w, h, size, depth, data, present} = m
81  +sizeDup = size
82  +yDup = y
83  +xDup = x
84  +fx = F32.floor(px)
85  +fy = F32.floor(py)
86  +ix = (F32.to_u32(U.max(fx, 0.0)) - xDup : U32)
87  +iy = (F32.to_u32(U.max(fy, 0.0)) - yDup : U32)
88  mask.at.in(F32.is_lt(fx, U32.to_f32(xDup)) || F32.is_lt(fy, U32.to_f32(yDup)) || U32.is_ge(ix, sizeDup) || U32.is_ge(iy, sizeDup), data, U32.div(sizeDup, 2), ix, iy)
89
90# Coverage over the cell rectangle [x0, x1) by [y0, y1) of a node's square at
91# (nx, ny) of side size, when every cell in it holds the same value; -1 otherwise.
92# acc is 2 before any cell is seen, -1 once cells disagree, else the value so far.
93def tree.same.as(+v: F32, +u: F32) -> F32:
94  U.choose(F32, F32.is_gt(v, 1.5), u, U.choose(F32, F32.is_lt(v, 0.0) || F32.is_lt(u, 0.0) || Bool.not(F32.is_eq(v, u)), F32.neg(1.0), v))
95
96def tree.overlaps(+nx: U32, +ny: U32, +size: U32, +x0: U32, +y0: U32, +x1: U32, +y1: U32) -> Bool:
97  U32.is_lt(nx, x1) && U32.is_lt(x0, (nx + size : U32)) && U32.is_lt(ny, y1) && U32.is_lt(y0, (ny + size : U32))
98
99@unsafe
100def tree.uniform(t: CovTree, +nx: U32, +ny: U32, +size: U32, +x0: U32, +y0: U32, +x1: U32, +y1: U32, +acc: F32) -> F32:
101  match t:
102    case CovFlat{v}: U.choose(F32, tree.overlaps(nx, ny, size, x0, y0, x1, y1), tree.same.as(acc, v), acc)
103    case CovQuad{a, b, c, d}:
104      +half = U32.div(size, 2)
105      U.branch(F32, Bool.not(tree.overlaps(nx, ny, size, x0, y0, x1, y1)) || F32.is_lt(acc, F32.neg(0.5)), _ => acc,
106        _ => tree.uniform(d, (nx + half : U32), (ny + half : U32), half, x0, y0, x1, y1,
107          tree.uniform(c, nx, (ny + half : U32), half, x0, y0, x1, y1,
108            tree.uniform(b, (nx + half : U32), ny, half, x0, y0, x1, y1,
109              tree.uniform(a, nx, ny, half, x0, y0, x1, y1, acc)))))
110
111# The mask's coverage over the grid rectangle [x0, x1) by [y0, y1) when it is
112# uniform (2 means "unvisited", so an empty rectangle reads as uniform 0), else -1.
113# The uniform value of runs over the columns [x0, x1): a run covering them
114# all gives its value, none touching them gives 0, anything else -1.
115def runs.over(rs: List<&2, Run>, +x0: U32, +x1: U32, +acc: F32) -> F32:
116  match rs:
117    case Nil{}: U.choose(F32, F32.is_gt(acc, 1.5), 0.0, acc)
118    case Con{Run{a, b, v}, rest}:
119      +aa = a
120      +bb = b
121      +vv = v
122      +overlaps = U32.is_lt(aa, x1) && U32.is_lt(x0, bb)
123      +covers = U32.is_le(aa, x0) && U32.is_ge(bb, x1)
124      runs.over(rest, x0, x1, U.choose(F32, Bool.not(overlaps), acc, U.choose(F32, covers && F32.is_gt(acc, 1.5), vv, F32.neg(1.0))))
125
126# The uniform value of rows over the cell rectangle [x0, x1) by [y0, y1) in
127# grid cells relative to the mask; rows past the list are empty.
128@unsafe
129def rows.over(rows: List<&2, List<&2, Run>>, +y: U32, +x0: U32, +y0: U32, +x1: U32, +y1: U32, +acc: F32) -> F32:
130  match rows:
131    case Nil{}: U.choose(F32, U32.is_lt(y, y1), tree.same.as(acc, 0.0), acc)
132    case Con{r, rest}:
133      U.choose(F32, U32.is_ge(y, y1) || F32.is_lt(acc, F32.neg(0.5)), acc,
134        rows.over(rest, (y + 1 : U32), x0, y0, x1, y1, U.choose(F32, U32.is_lt(y, y0), acc, tree.same.as(acc, runs.over(r, x0, x1, 2.0)))))
135
136def data.uniform(d: CovData, +mx: U32, +my: U32, +sz: U32, +x0: U32, +y0: U32, +x1: U32, +y1: U32) -> F32:
137  match d:
138    case CovTreed{t}: tree.uniform(t, mx, my, sz, x0, y0, x1, y1, 2.0)
139    case CovRows{rows}: rows.over(rows, 0, (x0 - mx : U32), (y0 - my : U32), (x1 - mx : U32), (y1 - my : U32), 2.0)
140
141def mask.uniform.in(+m: CovMask, +x0: U32, +y0: U32, +x1: U32, +y1: U32) -> F32:
142  CovMask{x, y, w, h, size, depth, data, present} = m
143  +mx = x
144  +my = y
145  +sz = size
146  +outside = U32.is_lt(x0, mx) || U32.is_lt(y0, my) || U32.is_gt(x1, (mx + sz : U32)) || U32.is_gt(y1, (my + sz : U32))
147  +inside = data.uniform(data, mx, my, sz, U.max.u32(x0, mx), U.max.u32(y0, my), U.min.u32(x1, (mx + sz : U32)), U.min.u32(y1, (my + sz : U32)))
148  +v = U.choose(F32, F32.is_gt(inside, 1.5), 0.0, inside)
149  U.choose(F32, outside && F32.is_gt(v, 0.0), F32.neg(1.0), v)
150
151def mask.uniform(+m: CovMask, +x0: U32, +y0: U32, +x1: U32, +y1: U32) -> F32:
152  U.choose(F32, U32.is_ge(x0, x1) || U32.is_ge(y0, y1), 0.0, mask.uniform.in(m, x0, y0, x1, y1))
153
154# ---- clipping to the grid's horizontal extent ----
155
156def line.split(l: CovLine, +at: F32) -> List<&2, CovLine>:
157  CovLine{x0, y0, x1, y1} = l
158  +ax = x0
159  +ay = y0
160  +bx = x1
161  +by = y1
162  +t = ((at - ax) / (bx - ax) : F32)
163  +my = (ay + (by - ay) * t : F32)
164  U.branch(List<&2, CovLine>, (F32.is_lt(ax, at) && F32.is_gt(bx, at)) || (F32.is_gt(ax, at) && F32.is_lt(bx, at)),
165    _ => Con{CovLine{ax, ay, at, my}, Con{CovLine{at, my, bx, by}, Nil{}}},
166    _ => Con{CovLine{ax, ay, bx, by}, Nil{}})
167
168def lines.append(xs: List<&2, CovLine>, ys: List<&2, CovLine>) -> List<&2, CovLine>:
169  match xs:
170    case Nil{}: ys
171    case Con{h, t}: Con{h, lines.append(t, ys)}
172
173def lines.split(xs: List<&2, CovLine>, +at: F32) -> List<&2, CovLine>:
174  match xs:
175    case Nil{}: Nil{}
176    case Con{l, rest}: lines.append(line.split(l, at), lines.split(rest, at))
177
178# Pieces left of 0 or right of w become vertical lines on that boundary, which keeps
179# the winding of every cell inside [0, w) intact.
180def lines.clamp(xs: List<&2, CovLine>, +w: F32, acc: List<&2, CovLine>, +n: U32) -> List<&2, CovLine> & U32:
181  match xs:
182    case Nil{}: (acc, n)
183    case Con{CovLine{x0, y0, x1, y1}, rest}: lines.clamp(rest, w, Con{CovLine{U.clamp(x0, 0.0, w), y0, U.clamp(x1, 0.0, w), y1}, acc}, (n + 1 : U32))
184
185# The clipped lines, in no particular order, with their count.
186def lines.clip(xs: List<&2, CovLine>, +w: F32) -> List<&2, CovLine> & U32:
187  lines.clamp(lines.split(lines.split(xs, 0.0), w), w, Nil{}, 0)
188
189# One pass over the lines: shift by the mask's origin, split at the grid's
190# left and right edges and clamp the pieces to it, counting them. Pieces
191# left of 0 or right of w become vertical lines on that edge, which keeps
192# the winding of every cell inside intact.
193def line.push(+ax: F32, +ay: F32, +bx: F32, +by: F32, +w: F32, st: List<&2, CovLine> & U32) -> List<&2, CovLine> & U32:
194  (acc, n) = st
195  (Con{CovLine{U.clamp(ax, 0.0, w), ay, U.clamp(bx, 0.0, w), by}, acc}, (n + 1 : U32))
196
197# Split at x = at when the line crosses it, pushing the piece before the
198# crossing; the rest continues.
199def line.cut.at(cross: Bool, +ax: F32, +ay: F32, +bx: F32, +by: F32, +at: F32, +w: F32, st: List<&2, CovLine> & U32) -> (List<&2, CovLine> & U32) & (F32 & F32):
200  match cross:
201    case False{}: (st, (ax, ay))
202    case True{}:
203      +my = (ay + (by - ay) * ((at - ax) / (bx - ax)) : F32)
204      (line.push(ax, ay, at, my, w, st), (at, my))
205
206def line.cut(+ax: F32, +ay: F32, +bx: F32, +by: F32, +at: F32, +w: F32, st: List<&2, CovLine> & U32) -> (List<&2, CovLine> & U32) & (F32 & F32):
207  line.cut.at((F32.is_lt(ax, at) && F32.is_gt(bx, at)) || (F32.is_gt(ax, at) && F32.is_lt(bx, at)), ax, ay, bx, by, at, w, st)
208
209def line.prepare.last(got: (List<&2, CovLine> & U32) & (F32 & F32), +bx: F32, +by: F32, +w: F32) -> List<&2, CovLine> & U32:
210  (st, (ax, ay)) = got
211  line.push(ax, ay, bx, by, w, st)
212
213def line.prepare.right(got: (List<&2, CovLine> & U32) & (F32 & F32), +bx: F32, +by: F32, +w: F32) -> List<&2, CovLine> & U32:
214  (st, (ax, ay)) = got
215  line.prepare.last(line.cut(ax, ay, bx, by, w, w, st), bx, by, w)
216
217def lines.prepare(xs: List<&2, CovLine>, +dx: F32, +dy: F32, +w: F32, st: List<&2, CovLine> & U32) -> List<&2, CovLine> & U32:
218  match xs:
219    case Nil{}: st
220    case Con{CovLine{x0, y0, x1, y1}, rest}:
221      +ax = (x0 - dx : F32)
222      +bx = (x1 - dx : F32)
223      +by = (y1 - dy : F32)
224      lines.prepare(rest, dx, dy, w, line.prepare.right(line.cut(ax, (y0 - dy : F32), bx, by, 0.0, w, st), bx, by, w))
225
226# ---- sub-scanline winding ----
227# Each pixel row is sampled on `sub` horizontal scanlines. The lines reaching
228# a scanline are kept in a list sorted by their x on it: one pass per
229# scanline walks that list with a winding count, emitting the inside spans as
230# events, and at the same time places every line that still reaches the next
231# scanline into the next list at its x there (lines keep their order almost
232# everywhere, so the insertion is a prepend). Lines start when the sorted
233# pending list reaches their top and end when the next scanline passes their
234# bottom. Coverage is exact in x and quantized to 1/sub in y, overlapping
235# contours follow the fill rule exactly, and nothing is sorted from scratch.
236
237def line.top(+l: CovLine) -> F32:
238  CovLine{x0, y0, x1, y1} = l
239  U.min(y0, y1)
240
241# A line on the scanlines: x at the current one is cur; slope is dx/dy.
242type Act is Data:
243  Act{cur: F32, x0: F32, y0: F32, slope: F32, bottom: F32, dir: F32}
244
245# Insert into a list descending by cur, after the elements not below it.
246type Ins is Data:
247  Placed{list: List<&2, Act>}
248  Passed{h: Act, t: List<&2, Act>, a: Act}
249
250def act.ins.pick(hit: Bool, a: Act, h: Act, t: List<&2, Act>) -> Ins:
251  match hit:
252    case True{}: Placed{Con{a, Con{h, t}}}
253    case False{}: Passed{h, t, a}
254
255@unsafe
256def act.insert.go(i: Ins) -> List<&2, Act>:
257  match i:
258    case Placed{list}: list
259    case Passed{h, t, a}:
260      match t:
261        case Nil{}: Con{h, Con{a, Nil{}}}
262        case Con{Act{c2, x2, y2, s2, b2, d2}, t2}:
263          Act{ac, ax, ay, as, ab, ad} = a
264          +cc = c2
265          +acc = ac
266          Con{h, act.insert.go(act.ins.pick(F32.is_ge(acc, cc), Act{acc, ax, ay, as, ab, ad}, Act{cc, x2, y2, s2, b2, d2}, t2))}
267
268def act.insert(a: Act, xs: List<&2, Act>) -> List<&2, Act>:
269  Act{ac, ax, ay, as, ab, ad} = a
270  match xs:
271    case Nil{}: Con{Act{ac, ax, ay, as, ab, ad}, Nil{}}
272    case Con{Act{c2, x2, y2, s2, b2, d2}, t2}:
273      +cc = c2
274      +acc = ac
275      act.insert.go(act.ins.pick(F32.is_ge(acc, cc), Act{acc, ax, ay, as, ab, ad}, Act{cc, x2, y2, s2, b2, d2}, t2))
276
277def act.reverse(xs: List<&2, Act>, acc: List<&2, Act>) -> List<&2, Act>:
278  match xs:
279    case Nil{}: acc
280    case Con{a, rest}: act.reverse(rest, Con{a, acc})
281
282# The line as it will stand on scanline sy, placed into the descending list.
283def act.keep(keep: Bool, +x0: F32, +y0: F32, +slope: F32, +bottom: F32, +dir: F32, +sy: F32, acc: List<&2, Act>) -> List<&2, Act>:
284  match keep:
285    case False{}: acc
286    case True{}: act.insert(Act{(x0 + (sy - y0) * slope : F32), x0, y0, slope, bottom, dir}, acc)
287
288# A line covers [top, bottom) so a shared vertex counts once; a horizontal line
289# never crosses. Lines whose bottom the scanline has passed are dropped.
290def act.add(l: CovLine, +sy: F32, acc: List<&2, Act>) -> List<&2, Act>:
291  CovLine{x0, y0, x1, y1} = l
292  +ax = x0
293  +ay = y0
294  +bx = x1
295  +by = y1
296  +up = F32.is_lt(ay, by)
297  +bottom = U.max(ay, by)
298  act.keep(F32.is_lt(sy, bottom) && Bool.not(F32.is_eq(ay, by)), ax, ay, ((bx - ax) / (by - ay) : F32), bottom, U.choose(F32, up, 1.0, F32.neg(1.0)), sy, acc)
299
300# Lines from the sorted pending list whose top the scanline sy has reached.
301type Take is Data:
302  Take{done: Bool, pending: List<&2, CovLine>, acc: List<&2, Act>}
303
304def take.pick(hit: Bool, l: CovLine, rest: List<&2, CovLine>, +sy: F32, acc: List<&2, Act>) -> Take:
305  match hit:
306    case True{}: Take{False{}, rest, act.add(l, sy, acc)}
307    case False{}: Take{True{}, Con{l, rest}, acc}
308
309@unsafe
310def take.go(t: Take, +sy: F32) -> Take:
311  match t:
312    case Take{done, pending, acc}:
313      match done:
314        case True{}: Take{True{}, pending, acc}
315        case False{}:
316          match pending:
317            case Nil{}: Take{True{}, Nil{}, acc}
318            case Con{l, rest}:
319              +ll = l
320              take.go(take.pick(F32.is_le(line.top(ll), sy), ll, rest, sy, acc), sy)
321
322# ---- span events ----
323# A span [xa, xb) of weight w touches its two end cells directly (their partial
324# overlap) and every cell between them in full. An event carries a direct
325# contribution to one cell and a delta that applies to that cell and all cells
326# to its right: +w at the first interior cell and -w at the last cell, so a
327# span costs three events however wide it is. Events are kept in descending
328# cell order (a walk goes left to right and prepends).
329
330type CovEv is Data:
331  CovEv{cell: U32, direct: F32, delta: F32}
332
333def ev.push.if(skip: Bool, +cell: U32, +direct: F32, +delta: F32, acc: List<&2, CovEv>) -> List<&2, CovEv>:
334  match skip:
335    case True{}: acc
336    case False{}: Con{CovEv{cell, direct, delta}, acc}
337
338def ev.push(+cell: U32, +direct: F32, +delta: F32, acc: List<&2, CovEv>) -> List<&2, CovEv>:
339  ev.push.if(F32.is_eq(direct, 0.0) && F32.is_eq(delta, 0.0), cell, direct, delta, acc)
340
341def span.events.cells(one: Bool, +ia: U32, +ib: U32, +xa: F32, +xb: F32, +w: F32, acc: List<&2, CovEv>) -> List<&2, CovEv>:
342  match one:
343    case True{}: ev.push(ia, ((xb - xa) * w : F32), 0.0, acc)
344    case False{}: ev.push(ib, ((xb - U32.to_f32(ib)) * w : F32), F32.neg(w), ev.push((ia + 1 : U32), 0.0, w, ev.push(ia, ((U32.to_f32(ia) + 1.0 - xa) * w : F32), 0.0, acc)))
345
346# Events of the span [xa, xb) when it is inside; both ends lie within [0, width].
347def span.events(inside: Bool, +xa: F32, +xb: F32, +w: F32, acc: List<&2, CovEv>) -> List<&2, CovEv>:
348  match inside:
349    case False{}: acc
350    case True{}:
351      +ia = F32.to_u32(F32.floor(xa))
352      +ib = F32.to_u32(F32.floor(xb))
353      span.events.cells(U32.is_ge(ia, ib), ia, ib, xa, xb, w, acc)
354
355def winding.inside(+wind: F32, +even: Bool) -> Bool:
356  U.choose(Bool, even, F32.is_gt(F32.abs((wind - 2.0 * F32.floor((wind / 2.0 : F32)) : F32)), 0.5), F32.is_gt(F32.abs(wind), 0.5))
357
358# One scanline: walk the ascending list, emit the inside spans' events, and
359# build the descending list for the next scanline sy2.
360type Step is Data:
361  Step{events: List<&2, CovEv>, next: List<&2, Act>}
362
363@unsafe
364def step(xs: List<&2, Act>, +sy2: F32, +wind: F32, +last: F32, +even: Bool, +weight: F32, evs: List<&2, CovEv>, acc: List<&2, Act>) -> Step:
365  match xs:
366    case Nil{}: Step{evs, acc}
367    case Con{Act{cur, x0, y0, slope, bottom, dir}, rest}:
368      +c = cur
369      +d = dir
370      +b = bottom
371      step(rest, sy2, (wind + d : F32), c, even, weight, span.events(winding.inside(wind, even), last, c, weight, evs),
372        act.keep(F32.is_lt(sy2, b), x0, y0, slope, b, d, sy2, acc))
373
374# Merge two descending event lists, larger cells first.
375type EvOrder is Data:
376  EvOrder{first: CovEv, rest: List<&2, CovEv>, other: List<&2, CovEv>}
377
378def ev.cell(+e: CovEv) -> U32:
379  CovEv{cell, direct, delta} = e
380  cell
381
382def ev.order.pick(hit: Bool, x: CovEv, xt: List<&2, CovEv>, y: CovEv, yt: List<&2, CovEv>) -> EvOrder:
383  match hit:
384    case True{}: EvOrder{x, xt, Con{y, yt}}
385    case False{}: EvOrder{y, yt, Con{x, xt}}
386
387def ev.order(x: CovEv, xt: List<&2, CovEv>, y: CovEv, yt: List<&2, CovEv>) -> EvOrder:
388  +xx = x
389  +yy = y
390  ev.order.pick(U32.is_ge(ev.cell(xx), ev.cell(yy)), xx, xt, yy, yt)
391
392@unsafe
393def ev.merge.go(o: EvOrder) -> List<&2, CovEv>:
394  match o:
395    case EvOrder{first, rest, other}:
396      match rest:
397        case Nil{}: Con{first, other}
398        case Con{x, xt}:
399          match other:
400            case Nil{}: Con{first, Con{x, xt}}
401            case Con{y, yt}: Con{first, ev.merge.go(ev.order(x, xt, y, yt))}
402
403def ev.merge(xs: List<&2, CovEv>, ys: List<&2, CovEv>) -> List<&2, CovEv>:
404  match xs:
405    case Nil{}: ys
406    case Con{x, xt}:
407      match ys:
408        case Nil{}: Con{x, xt}
409        case Con{y, yt}: ev.merge.go(ev.order(x, xt, y, yt))
410
411# ---- rows of runs ----
412# A row's events, swept from the right, become runs [x0, x1) of one nonzero
413# coverage value in ascending order; cells in no run are zero. Sweeping from
414# the right, the coverage of a cell is the negated sum of the deltas to its
415# right (all deltas of a row sum to zero) plus its direct contributions.
416
417# Sums of a weight's multiples cancel exactly for power-of-two sub counts and
418# to within rounding otherwise; noise below a millionth reads as empty.
419def run.snap(+v: F32) -> F32:
420  U.choose(F32, F32.is_lt(F32.abs(v), 0.000001), 0.0, v)
421
422def runs.emit.join(join: Bool, +x0: U32, +x1: U32, +v: F32, +b: U32, head: Run, rest: List<&2, Run>) -> List<&2, Run>:
423  match join:
424    case True{}: Con{Run{x0, b, v}, rest}
425    case False{}: Con{Run{x0, x1, v}, Con{head, rest}}
426
427def runs.emit.some(skip: Bool, +x0: U32, +x1: U32, +v: F32, acc: List<&2, Run>) -> List<&2, Run>:
428  match skip:
429    case True{}: acc
430    case False{}:
431      match acc:
432        case Nil{}: Con{Run{x0, x1, v}, Nil{}}
433        case Con{Run{a, b, u}, rest}:
434          +aa = a
435          +bb = b
436          +uu = u
437          runs.emit.join(U32.is_eq(aa, x1) && F32.is_eq(uu, v), x0, x1, v, bb, Run{aa, bb, uu}, rest)
438
439# Prepend the run [x0, x1) of value v, extending the head when they meet with one value.
440def runs.emit(+x0: U32, +x1: U32, +v: F32, acc: List<&2, Run>) -> List<&2, Run>:
441  runs.emit.some(U32.is_ge(x0, x1) || F32.is_eq(v, 0.0), x0, x1, v, acc)
442
443# Sweep state: sum is the total delta at cells >= upper, the runs so far cover
444# cells >= upper, and the open group collects the events of cell c.
445type Sweep is Data:
446  Sweep{sum: F32, upper: U32, c: U32, direct: F32, delta: F32, acc: List<&2, Run>}
447
448# Close the group at c: the gap (c, upper) holds -sum, cell c adds its directs.
449def sweep.flush(+sum: F32, +upper: U32, +c: U32, +direct: F32, acc: List<&2, Run>) -> List<&2, Run>:
450  runs.emit(c, (c + 1 : U32), run.snap((direct - sum : F32)), runs.emit((c + 1 : U32), upper, run.snap(F32.neg(sum)), acc))
451
452def sweep.step(same: Bool, +cell: U32, +direct: F32, +delta: F32, +sum: F32, +upper: U32, +c: U32, +dsum: F32, +dlsum: F32, acc: List<&2, Run>) -> Sweep:
453  match same:
454    case True{}: Sweep{sum, upper, c, (dsum + direct : F32), (dlsum + delta : F32), acc}
455    case False{}: Sweep{(sum + dlsum : F32), c, cell, direct, delta, sweep.flush(sum, upper, c, dsum, acc)}
456
457@unsafe
458def sweep(st: Sweep, evs: List<&2, CovEv>) -> List<&2, Run>:
459  Sweep{sum, upper, c, dsum, dlsum, acc} = st
460  match evs:
461    case Nil{}: sweep.flush(sum, upper, c, dsum, acc)
462    case Con{CovEv{cell, direct, delta}, rest}:
463      +cc = c
464      +ce = cell
465      sweep(sweep.step(U32.is_eq(ce, cc), ce, direct, delta, sum, upper, cc, dsum, dlsum, acc), rest)
466
467# The runs of a row of width w from its descending events.
468def row.runs(evs: List<&2, CovEv>, +w: U32) -> List<&2, Run>:
469  sweep(Sweep{0.0, w, w, 0.0, 0.0, Nil{}}, evs)
470
471# ---- sorting lines by top ----
472
473type LineOrder is Data:
474  LineOrder{first: CovLine, rest: List<&2, CovLine>, other: List<&2, CovLine>}
475
476def lines.order.pick(hit: Bool, x: CovLine, xt: List<&2, CovLine>, y: CovLine, yt: List<&2, CovLine>) -> LineOrder:
477  match hit:
478    case True{}: LineOrder{x, xt, Con{y, yt}}
479    case False{}: LineOrder{y, yt, Con{x, xt}}
480
481def lines.order(x: CovLine, xt: List<&2, CovLine>, y: CovLine, yt: List<&2, CovLine>) -> LineOrder:
482  +xx = x
483  +yy = y
484  lines.order.pick(F32.is_le(line.top(xx), line.top(yy)), xx, xt, yy, yt)
485
486@unsafe
487def lines.merge.go(o: LineOrder) -> List<&2, CovLine>:
488  match o:
489    case LineOrder{first, rest, other}:
490      match rest:
491        case Nil{}: Con{first, other}
492        case Con{x, xt}:
493          match other:
494            case Nil{}: Con{first, Con{x, xt}}
495            case Con{y, yt}: Con{first, lines.merge.go(lines.order(x, xt, y, yt))}
496
497def lines.merge(xs: List<&2, CovLine>, ys: List<&2, CovLine>) -> List<&2, CovLine>:
498  match xs:
499    case Nil{}: ys
500    case Con{x, xt}:
501      match ys:
502        case Nil{}: Con{x, xt}
503        case Con{y, yt}: lines.merge.go(lines.order(x, xt, y, yt))
504
505type LineSplit is Data:
506  LineSplit{left: List<&2, CovLine>, right: List<&2, CovLine>}
507
508def lines.deal(xs: List<&2, CovLine>, left: List<&2, CovLine>, right: List<&2, CovLine>) -> LineSplit:
509  match xs:
510    case Nil{}: LineSplit{left, right}
511    case Con{x, Nil{}}: LineSplit{Con{x, left}, right}
512    case Con{x, Con{y, rest}}: lines.deal(rest, Con{x, left}, Con{y, right})
513
514# Merge sort by top.
515@unsafe
516def lines.sort.go(s: LineSplit) -> List<&2, CovLine>:
517  match s:
518    case LineSplit{left, right}:
519      match right:
520        case Nil{}: left
521        case Con{y, yt}: lines.merge(lines.sort.go(lines.deal(left, Nil{}, Nil{})), lines.sort.go(lines.deal(Con{y, yt}, Nil{}, Nil{})))
522
523def lines.sort(xs: List<&2, CovLine>) -> List<&2, CovLine>:
524  lines.sort.go(lines.deal(xs, Nil{}, Nil{}))
525
526# ---- the scan ----
527# The active list stands at the current scanline; each step walks it, merges
528# the scanline's events into the row's, and readies the list for the next
529# scanline, taking the lines that start before it. The rows list is built top
530# row last (prepended) and reversed at the end.
531
532type Subs is Data:
533  Subs{active: List<&2, Act>, pending: List<&2, CovLine>, events: List<&2, CovEv>}
534
535def subs.done(t: Take, events: List<&2, CovEv>) -> Subs:
536  Take{done, pending, acc} = t
537  Subs{act.reverse(acc, Nil{}), pending, events}
538
539def subs.after(s: Step, pending: List<&2, CovLine>, +sy2: F32, events: List<&2, CovEv>) -> Subs:
540  Step{evs, acc} = s
541  subs.done(take.go(Take{False{}, pending, acc}, sy2), ev.merge(evs, events))
542
543def subs.step(st: Subs, +sy: F32, +dy: F32, +even: Bool, +weight: F32) -> Subs:
544  Subs{active, pending, events} = st
545  +sy2 = (sy + dy : F32)
546  subs.after(step(active, sy2, 0.0, 0.0, even, weight, Nil{}, Nil{}), pending, sy2, events)
547
548@unsafe
549def scan.subs(st: Subs, n: Nat, +sy: F32, +dy: F32, +even: Bool, +weight: F32) -> Subs:
550  match n:
551    case 0n: st
552    case 1n+d: scan.subs(subs.step(st, sy, dy, even, weight), d, (sy + dy : F32), dy, even, weight)
553
554type Scan is Data:
555  Scan{rows: List<&2, List<&2, Run>>, active: List<&2, Act>, pending: List<&2, CovLine>}
556
557def scan.row.done(st: Subs, rows: List<&2, List<&2, Run>>, +w: U32) -> Scan:
558  Subs{active, pending, events} = st
559  Scan{Con{row.runs(events, w), rows}, active, pending}
560
561def scan.row(st: Scan, +y: U32, +sub: U32, +even: Bool, +w: U32) -> Scan:
562  Scan{rows, active, pending} = st
563  +dy = (1.0 / U32.to_f32(sub) : F32)
564  scan.row.done(scan.subs(Subs{active, pending, Nil{}}, U32.to_nat(sub), (U32.to_f32(y) + dy * 0.5 : F32), dy, even, dy), rows, w)
565
566@unsafe
567def scan.rows.go(st: Scan, n: Nat, +y: U32, +sub: U32, +even: Bool, +w: U32) -> Scan:
568  match n:
569    case 0n: st
570    case 1n+d: scan.rows.go(scan.row(st, y, sub, even, w), d, (y + 1 : U32), sub, even, w)
571
572def rows.reverse(rows: List<&2, List<&2, Run>>, acc: List<&2, List<&2, Run>>) -> List<&2, List<&2, Run>>:
573  match rows:
574    case Nil{}: acc
575    case Con{r, rest}: rows.reverse(rest, Con{r, acc})
576
577def scan.done(st: Scan) -> List<&2, List<&2, Run>>:
578  Scan{rows, active, pending} = st
579  rows.reverse(rows, Nil{})
580
581def scan.start(t: Take) -> Scan:
582  Take{done, pending, acc} = t
583  Scan{Nil{}, act.reverse(acc, Nil{}), pending}
584
585# The rows of runs (top first) of the lines, sorted by top, over a width by height grid.
586def scan.rows(+h: U32, +sub: U32, sorted: List<&2, CovLine>, +even: Bool, +w: U32) -> List<&2, List<&2, Run>>:
587  scan.done(scan.rows.go(scan.start(take.go(Take{False{}, sorted, Nil{}}, (0.5 / U32.to_f32(sub) : F32))), U32.to_nat(h), 0, sub, even, w))
588
589@unsafe
590def depth.for(+size: U32, +side: U32, +depth: Nat) -> Nat:
591  U.branch(Nat, U32.is_ge(side, size), _ => depth, _ => depth.for(size, (side * 2 : U32), 1n+depth))
592
593# ---- exact area scan ----
594# When a shape's contours never overlap, the winding number is 0 or +-1
595# everywhere and a pixel's coverage is the absolute value of the winding
596# integrated over it. That integral is a sum over the lines: a line piece
597# inside the row contributes, for each cell it passes through, the area to
598# its right within that cell (direct) and its height to every cell further
599# right (a delta). The contributions of a row go into a row buffer with two
600# slots per cell, which costs writes and no allocation; the runs are then
601# read off the touched cells only, right to left, and the buffer is cleared
602# behind the read. One pass per row, exact in both axes, nothing sampled. A
603# row whose integral exceeds one somewhere reveals an overlap, and the shape
604# is scanned again with sub-scanlines; even-odd fills always are.
605
606# A line for the exact scan: x = x0 + (y - y0) * slope over [top, bottom).
607type Piece is Data:
608  Piece{x0: F32, y0: F32, slope: F32, top: F32, bottom: F32, dir: F32}
609
610def piece.of(l: CovLine) -> Piece:
611  CovLine{x0, y0, x1, y1} = l
612  +ax = x0
613  +ay = y0
614  +bx = x1
615  +by = y1
616  Piece{ax, ay, ((bx - ax) / (by - ay) : F32), U.min(ay, by), U.max(ay, by), U.choose(F32, F32.is_lt(ay, by), 1.0, F32.neg(1.0))}
617
618def piece.bottom(+p: Piece) -> F32:
619  Piece{x0, y0, slope, top, bottom, dir} = p
620  bottom
621
622# The row buffer: slot 2c holds cell c's direct area and slot 2c + 1 its
623# delta; a bitmap marks the touched cells so the read skips empty words;
624# lo and hi bound the touched cells (lo > hi when none). Arrays cannot sit
625# in a constructor, so the buffer is the tuple ((slots, bitmap), (lo, hi)).
626
627def buf.add.got(got: Array<F32> & F32, +i: U32, +v: F32) -> Array<F32>:
628  (a, old) = got
629  Array.set(F32, a, i, (old + v : F32))
630
631def buf.add(a: Array<F32>, +i: U32, +v: F32) -> Array<F32>:
632  buf.add.got(Array.get(F32, a, i), i, v)
633
634def bits.set.got(got: Array<U32> & U32, +i: U32, +bit: U32) -> Array<U32>:
635  (bm, word) = got
636  Array.set(U32, bm, i, U32.or(word, bit))
637
638def bits.set(bm: Array<U32>, +c: U32) -> Array<U32>:
639  bits.set.got(Array.get(U32, bm, U32.div(c, 32)), U32.div(c, 32), U32.shln(1, U32.to_nat(U32.mod(c, 32))))
640
641# A cut's direct area goes to its cell (dropped at or past the width, which
642# lies outside the row) and its delta to the next cell, capped at the width
643# so every delta still counts in the sum.
644def buf.put(b: (Array<F32> & Array<U32>) & (U32 & U32), +cell: U32, +direct: F32, +delta: F32, +w: U32) -> (Array<F32> & Array<U32>) & (U32 & U32):
645  ((a, bm), (lo, hi)) = b
646  +c = U.min.u32(cell, w)
647  +next = U.min.u32((cell + 1 : U32), w)
648  ((buf.add(buf.add(a, (c * 2 : U32), U.choose(F32, U32.is_lt(cell, w), direct, 0.0)), (next * 2 + 1 : U32), delta), bits.set(bits.set(bm, c), next)), (U.min.u32(lo, c), U.max.u32(hi, next)))
649
650def buf.put.if(skip: Bool, b: (Array<F32> & Array<U32>) & (U32 & U32), +cell: U32, +direct: F32, +delta: F32, +w: U32) -> (Array<F32> & Array<U32>) & (U32 & U32):
651  match skip:
652    case True{}: b
653    case False{}: buf.put(b, cell, direct, delta, w)
654
655# The piece of a line between heights ya and yb, from xa to xb, cut at the
656# cell boundaries it crosses: each cut of height dy within cell i adds the
657# area to its right, dy * (i + 1 - mid x), to cell i and dy to the cells
658# beyond. `n` bounds the cuts (the cells crossed plus one); `done` holds once
659# a cut reached yb.
660@unsafe
661def piece.cuts(done: Bool, n: Nat, +xa: F32, +ya: F32, +xb: F32, +yb: F32, +dir: F32, +slope: F32, +w: U32, b: (Array<F32> & Array<U32>) & (U32 & U32)) -> (Array<F32> & Array<U32>) & (U32 & U32):
662  match done:
663    case True{}: b
664    case False{}:
665      match n:
666        case 0n: b
667        case 1n+d:
668          +ahead = F32.is_le(xa, xb)
669          +i = U.choose(F32, ahead, F32.floor(xa), (F32.ceil(xa) - 1.0 : F32))
670          +right = (i + 1.0 : F32)
671          +bound = U.choose(F32, ahead, right, i)
672          +full = U.choose(Bool, ahead, F32.is_le(xb, bound), F32.is_ge(xb, bound))
673          +xc = U.choose(F32, full, xb, bound)
674          +yc = U.choose(F32, full, yb, U.choose(F32, F32.is_lt(F32.abs(slope), 0.000001), yb, (ya + (xc - xa) / slope : F32)))
675          +dy = (yc - ya : F32)
676          piece.cuts(full, d, xc, yc, xb, yb, dir, slope, w,
677            buf.put.if(F32.is_eq(dy, 0.0), b, F32.to_u32(U.max(i, 0.0)), (dir * dy * (right - (xa + xc) * 0.5) : F32), (dir * dy : F32), w))
678
679# The contributions of a line piece clipped to the row [y, y + 1).
680def piece.events(p: Piece, +y: F32, +w: U32, b: (Array<F32> & Array<U32>) & (U32 & U32)) -> (Array<F32> & Array<U32>) & (U32 & U32):
681  Piece{x0, y0, slope, top, bottom, dir} = p
682  +xx0 = x0
683  +yy0 = y0
684  +s = slope
685  +ya = U.max(top, y)
686  +yb = U.min(bottom, (y + 1.0 : F32))
687  +xa = (xx0 + (ya - yy0) * s : F32)
688  +xb = (xx0 + (yb - yy0) * s : F32)
689  +span = F32.to_u32((F32.abs((F32.floor(xb) - F32.floor(xa) : F32)) + 2.0 : F32))
690  piece.cuts(F32.is_le(yb, ya), U32.to_nat(span), xa, ya, xb, yb, dir, s, w, b)
691
692# The pieces still reaching below the row, with the row's buffer filled.
693
694def piece.keep(keep: Bool, p: Piece, active: List<&2, Piece>) -> List<&2, Piece>:
695  match keep:
696    case True{}: Con{p, active}
697    case False{}: active
698
699@unsafe
700# The row's pieces all go into the buffer and come back as a list (in any
701# order); those the next row no longer reaches are retired afterwards.
702def pieces.row(xs: List<&2, Piece>, +y: F32, +w: U32, active: List<&2, Piece>, b: (Array<F32> & Array<U32>) & (U32 & U32)) -> List<&2, Piece> & ((Array<F32> & Array<U32>) & (U32 & U32)):
703  match xs:
704    case Nil{}: (active, b)
705    case Con{p, rest}:
706      +pp = p
707      pieces.row(rest, y, w, Con{pp, active}, piece.events(pp, y, w, b))
708
709def pieces.retire(xs: List<&2, Piece>, +bottom: F32, acc: List<&2, Piece>) -> List<&2, Piece>:
710  match xs:
711    case Nil{}: acc
712    case Con{p, rest}:
713      +pp = p
714      pieces.retire(rest, bottom, piece.keep(F32.is_gt(piece.bottom(pp), bottom), pp, acc))
715
716# A piece as a line shifted so the row starts at zero, for the sub-scanline
717# scan of a row whose exact areas showed an overlap.
718def piece.line(+p: Piece, +y: F32) -> CovLine:
719  Piece{x0, y0, slope, top, bottom, dir} = p
720  +xx0 = x0
721  +yy0 = y0
722  +s = slope
723  +t = top
724  +b = bottom
725  +xt = (xx0 + (t - yy0) * s : F32)
726  +xb = (xx0 + (b - yy0) * s : F32)
727  U.choose(CovLine, F32.is_gt(dir, 0.0), CovLine{xt, (t - y : F32), xb, (b - y : F32)}, CovLine{xb, (b - y : F32), xt, (t - y : F32)})
728
729def pieces.lines(xs: List<&2, Piece>, +y: F32, acc: List<&2, CovLine>) -> List<&2, CovLine>:
730  match xs:
731    case Nil{}: acc
732    case Con{p, rest}: pieces.lines(rest, y, Con{piece.line(p, y), acc})
733
734def line.bottom(+l: CovLine) -> F32:
735  CovLine{x0, y0, x1, y1} = l
736  U.max(y0, y1)
737
738# ---- lines in arrays, ordered by top row ----
739# The lines go into one array of four floats each, and an index array orders
740# them by the row their top lies in (a counting sort over the rows), so the
741# scan takes lines as its rows reach them without a comparison sort and
742# without a list per pass. The fallback scans read the lines back in order.
743
744def row.of(+top: F32, +h: U32) -> U32:
745  F32.to_u32(U.clamp(F32.floor(top), 0.0, U32.to_f32(h)))
746
747def counts.inc.got(got: Array<U32> & U32, +r: U32) -> Array<U32>:
748  (c, v) = got
749  Array.set(U32, c, r, (v + 1 : U32))
750
751def counts.inc(c: Array<U32>, +r: U32) -> Array<U32>:
752  counts.inc.got(Array.get(U32, c, r), r)
753
754# Store each line at 4i and count its top row.
755def soa.store.go(xs: List<&2, CovLine>, a: Array<F32>, counts: Array<U32>, +i: U32, +h: U32) -> Array<F32> & Array<U32>:
756  match xs:
757    case Nil{}: (a, counts)
758    case Con{CovLine{x0, y0, x1, y1}, rest}:
759      +ay = y0
760      +by = y1
761      +base = (i * 4 : U32)
762      soa.store.go(rest, Array.set(F32, Array.set(F32, Array.set(F32, Array.set(F32, a, base, x0), (base + 1 : U32), ay), (base + 2 : U32), x1), (base + 3 : U32), by),
763        counts.inc(counts, row.of(U.min(ay, by), h)), (i + 1 : U32), h)
764
765# Turn counts into starting positions.
766def counts.prefix.got(got: Array<U32> & U32, +i: U32, +acc: U32) -> Array<U32> & U32:
767  (c, v) = got
768  (Array.set(U32, c, i, acc), (acc + v : U32))
769
770@unsafe
771def counts.prefix(st: Array<U32> & U32, n: Nat, +i: U32) -> Array<U32> & U32:
772  (c, acc) = st
773  match n:
774    case 0n: (c, acc)
775    case 1n+d: counts.prefix(counts.prefix.got(Array.get(U32, c, i), i, acc), d, (i + 1 : U32))
776
777def counts.done(st: Array<U32> & U32) -> Array<U32>:
778  (c, acc) = st
779  c
780
781# Place line i at its row's next position.
782def soa.place.pos(got: Array<U32> & U32, a: Array<F32>, order: Array<U32>, +i: U32, +r: U32) -> Array<F32> & (Array<U32> & Array<U32>):
783  (starts, pos) = got
784  +p = pos
785  (a, (Array.set(U32, starts, r, (p + 1 : U32)), Array.set(U32, order, p, i)))
786
787def soa.place.y1(got: Array<F32> & F32, starts: Array<U32>, order: Array<U32>, +y0: F32, +i: U32, +h: U32) -> Array<F32> & (Array<U32> & Array<U32>):
788  (a, y1) = got
789  +r = row.of(U.min(y0, y1), h)
790  soa.place.pos(Array.get(U32, starts, r), a, order, i, r)
791
792def soa.place.y0(got: Array<F32> & F32, starts: Array<U32>, order: Array<U32>, +i: U32, +h: U32) -> Array<F32> & (Array<U32> & Array<U32>):
793  (a, y0) = got
794  soa.place.y1(Array.get(F32, a, (i * 4 + 3 : U32)), starts, order, y0, i, h)
795
796@unsafe
797def soa.place(st: Array<F32> & (Array<U32> & Array<U32>), n: Nat, +i: U32, +h: U32) -> Array<F32> & (Array<U32> & Array<U32>):
798  (a, (starts, order)) = st
799  match n:
800    case 0n: (a, (starts, order))
801    case 1n+d: soa.place(soa.place.y0(Array.get(F32, a, (i * 4 + 1 : U32)), starts, order, i, h), d, (i + 1 : U32), h)
802
803def soa.placed(st: Array<F32> & (Array<U32> & Array<U32>)) -> Array<F32> & Array<U32>:
804  (a, (starts, order)) = st
805  (a, order)
806
807def soa.stored(st: Array<F32> & Array<U32>, +n: U32, +h: U32) -> Array<F32> & Array<U32>:
808  (a, counts) = st
809  soa.placed(soa.place((a, (counts.done(counts.prefix((counts, 0), U32.to_nat((h + 2 : U32)), 0)), Array.new(U32, depth.for((n + 1 : U32), 1, 0n), 0))), U32.to_nat(n), 0, h))
810
811# The lines as (values, order) arrays, ordered by top row.
812def soa.build(xs: List<&2, CovLine>, +n: U32, +h: U32) -> Array<F32> & Array<U32>:
813  soa.stored(soa.store.go(xs, Array.new(F32, depth.for((n * 4 + 4 : U32), 1, 0n), 0.0), Array.new(U32, depth.for((h + 3 : U32), 1, 0n), 0), 0, h), n, h)
814
815# The lines back as a list in order, for the sub-scanline scans.
816def soa.line.x1(got: Array<F32> & F32, +x0: F32, +y0: F32, +y1: F32, acc: List<&2, CovLine>) -> Array<F32> & List<&2, CovLine>:
817  (a, x1) = got
818  (a, Con{CovLine{x0, y0, x1, y1}, acc})
819
820def soa.line.y1(got: Array<F32> & F32, +x0: F32, +y0: F32, +base: U32, acc: List<&2, CovLine>) -> Array<F32> & List<&2, CovLine>:
821  (a, y1) = got
822  soa.line.x1(Array.get(F32, a, (base + 2 : U32)), x0, y0, y1, acc)
823
824def soa.line.y0(got: Array<F32> & F32, +x0: F32, +base: U32, acc: List<&2, CovLine>) -> Array<F32> & List<&2, CovLine>:
825  (a, y0) = got
826  soa.line.y1(Array.get(F32, a, (base + 3 : U32)), x0, y0, base, acc)
827
828def soa.line.x0(got: Array<F32> & F32, +base: U32, acc: List<&2, CovLine>) -> Array<F32> & List<&2, CovLine>:
829  (a, x0) = got
830  soa.line.y0(Array.get(F32, a, (base + 1 : U32)), x0, base, acc)
831
832def soa.line.pair(got: Array<F32> & List<&2, CovLine>, order: Array<U32>) -> Array<F32> & (Array<U32> & List<&2, CovLine>):
833  (a, acc) = got
834  (a, (order, acc))
835
836def soa.line.idx(got: Array<U32> & U32, a: Array<F32>, acc: List<&2, CovLine>) -> Array<F32> & (Array<U32> & List<&2, CovLine>):
837  (order, i) = got
838  +base = (i * 4 : U32)
839  soa.line.pair(soa.line.x0(Array.get(F32, a, base), base, acc), order)
840
841@unsafe
842def soa.lines.go(st: Array<F32> & (Array<U32> & List<&2, CovLine>), n: Nat, +k: U32) -> Array<F32> & (Array<U32> & List<&2, CovLine>):
843  (a, (order, acc)) = st
844  match n:
845    case 0n: (a, (order, acc))
846    case 1n+d: soa.lines.go(soa.line.idx(Array.get(U32, order, k), a, acc), d, (k - 1 : U32))
847
848def soa.lines.done(st: Array<F32> & (Array<U32> & List<&2, CovLine>)) -> List<&2, CovLine>:
849  (a, (order, acc)) = st
850  acc
851
852def soa.lines(arrays: Array<F32> & Array<U32>, +n: U32) -> List<&2, CovLine>:
853  (a, order) = arrays
854  soa.lines.done(soa.lines.go((a, (order, {Nil{} : List<&2, CovLine>})), U32.to_nat(n), (n - 1 : U32)))
855
856# Lines whose top the row's bottom has passed become pieces; a horizontal
857# one is skipped. The cursor k walks the order array.
858type PieceTake is Data:
859  PieceTake{done: Bool, k: U32, n: U32, active: List<&2, Piece>}
860
861def piece.take.x1(got: Array<F32> & F32, order: Array<U32>, +x0: F32, +y0: F32, +y1: F32, +k: U32, +n: U32, active: List<&2, Piece>) -> (Array<F32> & Array<U32>) & PieceTake:
862  (a, x1) = got
863  ((a, order), PieceTake{False{}, (k + 1 : U32), n, Con{piece.of(CovLine{x0, y0, x1, y1}), active}})
864
865def piece.take.x0(got: Array<F32> & F32, order: Array<U32>, +y0: F32, +y1: F32, +base: U32, +k: U32, +n: U32, active: List<&2, Piece>) -> (Array<F32> & Array<U32>) & PieceTake:
866  (a, x0) = got
867  piece.take.x1(Array.get(F32, a, (base + 2 : U32)), order, x0, y0, y1, k, n, active)
868
869def piece.take.pick(hit: Bool, flat: Bool, a: Array<F32>, order: Array<U32>, +y0: F32, +y1: F32, +base: U32, +k: U32, +n: U32, active: List<&2, Piece>) -> (Array<F32> & Array<U32>) & PieceTake:
870  match hit:
871    case False{}: ((a, order), PieceTake{True{}, k, n, active})
872    case True{}:
873      match flat:
874        case True{}: ((a, order), PieceTake{False{}, (k + 1 : U32), n, active})
875        case False{}: piece.take.x0(Array.get(F32, a, base), order, y0, y1, base, k, n, active)
876
877def piece.take.y1(got: Array<F32> & F32, order: Array<U32>, +y0: F32, +base: U32, +k: U32, +n: U32, +bottom: F32, active: List<&2, Piece>) -> (Array<F32> & Array<U32>) & PieceTake:
878  (a, y1) = got
879  +yy1 = y1
880  +top = U.min(y0, yy1)
881  piece.take.pick(F32.is_lt(top, bottom), F32.is_le(U.max(y0, yy1), top), a, order, y0, yy1, base, k, n, active)
882
883def piece.take.y0(got: Array<F32> & F32, order: Array<U32>, +base: U32, +k: U32, +n: U32, +bottom: F32, active: List<&2, Piece>) -> (Array<F32> & Array<U32>) & PieceTake:
884  (a, y0) = got
885  piece.take.y1(Array.get(F32, a, (base + 3 : U32)), order, y0, base, k, n, bottom, active)
886
887def piece.take.idx(got: Array<U32> & U32, a: Array<F32>, +k: U32, +n: U32, +bottom: F32, active: List<&2, Piece>) -> (Array<F32> & Array<U32>) & PieceTake:
888  (order, i) = got
889  +base = (i * 4 : U32)
890  piece.take.y0(Array.get(F32, a, (base + 1 : U32)), order, base, k, n, bottom, active)
891
892def piece.take.more(arrays: Array<F32> & Array<U32>, more: Bool, +k: U32, +n: U32, +bottom: F32, active: List<&2, Piece>) -> (Array<F32> & Array<U32>) & PieceTake:
893  (a, order) = arrays
894  match more:
895    case True{}: piece.take.idx(Array.get(U32, order, k), a, k, n, bottom, active)
896    case False{}: ((a, order), PieceTake{True{}, k, n, active})
897
898@unsafe
899def piece.take(st: (Array<F32> & Array<U32>) & PieceTake, +bottom: F32) -> (Array<F32> & Array<U32>) & PieceTake:
900  (arrays, t) = st
901  match t:
902    case PieceTake{done, k, n, active}:
903      match done:
904        case True{}: (arrays, PieceTake{True{}, k, n, active})
905        case False{}:
906          +kk = k
907          +nn = n
908          piece.take(piece.take.more(arrays, U32.is_lt(kk, nn), kk, nn, bottom, active), bottom)
909
910# Reading the runs off the buffer, touched cells only, from hi down to lo: a
911# cell's coverage is the magnitude of its direct area minus the deltas to its
912# right (a row's deltas cancel), clamped to one, and the untouched cells
913# between two touched ones share the magnitude of those deltas. A magnitude
914# past one marks an overlap. Every slot and bitmap word read is cleared, so
915# the buffer is empty for the next row.
916type XState is Data:
917  XState{sum: F32, bad: Bool, upper: U32, acc: List<&2, Run>}
918
919def xrun.value(+v: F32) -> F32:
920  U.min(1.0, run.snap(F32.abs(v)))
921
922def xrow.delta(got: Array<F32> & F32, bm: Array<U32>, +direct: F32, +c: U32, st: XState) -> (Array<F32> & Array<U32>) & XState:
923  (a, delta) = got
924  XState{sum, bad, upper, acc} = st
925  +ss = sum
926  +v = (direct - ss : F32)
927  +gap = F32.neg(ss)
928  ((Array.set(F32, Array.set(F32, a, (c * 2 : U32), 0.0), (c * 2 + 1 : U32), 0.0), bm),
929    XState{(ss + delta : F32), bad || F32.is_gt(F32.abs(v), 1.002) || F32.is_gt(F32.abs(gap), 1.002), c,
930      runs.emit(c, (c + 1 : U32), xrun.value(v), runs.emit((c + 1 : U32), upper, xrun.value(gap), acc))})
931
932def xrow.direct(got: Array<F32> & F32, bm: Array<U32>, +c: U32, st: XState) -> (Array<F32> & Array<U32>) & XState:
933  (a, direct) = got
934  xrow.delta(Array.get(F32, a, (c * 2 + 1 : U32)), bm, direct, c, st)
935
936def xrow.cell(arrays: Array<F32> & Array<U32>, hit: Bool, +c: U32, st: XState) -> (Array<F32> & Array<U32>) & XState:
937  (a, bm) = arrays
938  match hit:
939    case True{}: xrow.direct(Array.get(F32, a, (c * 2 : U32)), bm, c, st)
940    case False{}: ((a, bm), st)
941
942# The set bits of a word, from bit 31 down: mask halves at each step.
943@unsafe
944def xrow.bits(st: (Array<F32> & Array<U32>) & XState, n: Nat, +word: U32, +mask: U32, +cell: U32) -> (Array<F32> & Array<U32>) & XState:
945  (arrays, state) = st
946  match n:
947    case 0n: (arrays, state)
948    case 1n+d: xrow.bits(xrow.cell(arrays, U32.is_gt(U32.and(word, mask), 0), cell, state), d, word, U32.div(mask, 2), (cell - 1 : U32))
949
950def xrow.word.if(empty: Bool, a: Array<F32>, bm: Array<U32>, +i: U32, +word: U32, st: XState) -> (Array<F32> & Array<U32>) & XState:
951  match empty:
952    case True{}: ((a, bm), st)
953    case False{}: xrow.bits(((a, Array.set(U32, bm, i, 0)), st), 32n, word, 2147483648, (i * 32 + 31 : U32))
954
955def xrow.word(got: Array<U32> & U32, a: Array<F32>, +i: U32, st: XState) -> (Array<F32> & Array<U32>) & XState:
956  (bm, word) = got
957  +ww = word
958  xrow.word.if(U32.is_eq(ww, 0), a, bm, i, ww, st)
959
960def xrow.word.of(st: (Array<F32> & Array<U32>) & XState, +i: U32) -> (Array<F32> & Array<U32>) & XState:
961  ((a, bm), state) = st
962  xrow.word(Array.get(U32, bm, i), a, i, state)
963
964# Words from the one holding hi down to the one holding lo.
965@unsafe
966def xrow.words(st: (Array<F32> & Array<U32>) & XState, n: Nat, +i: U32) -> (Array<F32> & Array<U32>) & XState:
967  match n:
968    case 0n: st
969    case 1n+d: xrow.words(xrow.word.of(st, i), d, (i - 1 : U32))
970
971# A row's result: ((runs, overlap seen), the cleared buffer).
972def xrow.done(st: (Array<F32> & Array<U32>) & XState, +w: U32) -> (List<&2, Run> & Bool) & ((Array<F32> & Array<U32>) & (U32 & U32)):
973  (arrays, state) = st
974  XState{sum, bad, upper, acc} = state
975  +ss = sum
976  ((runs.emit(0, upper, xrun.value(F32.neg(ss)), acc), bad || F32.is_gt(F32.abs(ss), 1.002)), (arrays, ((w + 1 : U32), 0)))
977
978def xrow.count(+lo: U32, +hi: U32) -> U32:
979  U.choose(U32, U32.is_gt(lo, hi), 0, (U32.div(hi, 32) - U32.div(lo, 32) + 1 : U32))
980
981def xrow.from(arrays: Array<F32> & Array<U32>, +lo: U32, +hi: U32, +w: U32) -> (List<&2, Run> & Bool) & ((Array<F32> & Array<U32>) & (U32 & U32)):
982  xrow.done(xrow.words((arrays, XState{0.0, False{}, w, {Nil{} : List<&2, Run>}}), U32.to_nat(xrow.count(lo, hi)), U32.div(hi, 32)), w)
983
984# The runs of a row from its buffer, which comes back cleared.
985def xrow.runs(b: (Array<F32> & Array<U32>) & (U32 & U32), +w: U32) -> (List<&2, Run> & Bool) & ((Array<F32> & Array<U32>) & (U32 & U32)):
986  (arrays, (lo, hi)) = b
987  xrow.from(arrays, lo, hi, w)
988
989# The scan state: the row buffer, the line arrays, and the rest as a record.
990type XData is Data:
991  XData{lo: U32, hi: U32, rows: List<&2, List<&2, Run>>, active: List<&2, Piece>, k: U32, n: U32, sub: U32}
992
993def rows.head(rows: List<&2, List<&2, Run>>) -> List<&2, Run>:
994  match rows:
995    case Nil{}: Nil{}
996    case Con{r, rest}: r
997
998# A row whose exact areas showed an overlap is scanned again with the
999# sub-scanlines over its own pieces; other rows keep their runs. Either way
1000# the pieces the next row no longer reaches are retired.
1001def xscan.fix(bad: Bool, runs: List<&2, Run>, active: List<&2, Piece>, +y: F32, +sub: U32, +w: U32) -> List<&2, Run> & List<&2, Piece>:
1002  match bad:
1003    case False{}: (runs, pieces.retire(active, (y + 1.0 : F32), Nil{}))
1004    case True{}:
1005      +act = active
1006      (rows.head(scan.rows(1, sub, lines.sort(pieces.lines(act, y, Nil{})), False{}, w)), pieces.retire(act, (y + 1.0 : F32), Nil{}))
1007
1008def xscan.push(fixed: List<&2, Run> & List<&2, Piece>, buf: (Array<F32> & Array<U32>) & (U32 & U32), lines: Array<F32> & Array<U32>, rows: List<&2, List<&2, Run>>, +k: U32, +n: U32, +sub: U32) -> ((Array<F32> & Array<U32>) & (Array<F32> & Array<U32>)) & XData:
1009  (runs, active) = fixed
1010  (buf, (lo, hi)) = buf
1011  ((buf, lines), XData{lo, hi, Con{runs, rows}, active, k, n, sub})
1012
1013def xscan.swept(r: (List<&2, Run> & Bool) & ((Array<F32> & Array<U32>) & (U32 & U32)), lines: Array<F32> & Array<U32>, rows: List<&2, List<&2, Run>>, active: List<&2, Piece>, +y: F32, +k: U32, +n: U32, +sub: U32, +w: U32) -> ((Array<F32> & Array<U32>) & (Array<F32> & Array<U32>)) & XData:
1014  ((runs, bad), buf) = r
1015  xscan.push(xscan.fix(bad, runs, active, y, sub, w), buf, lines, rows, k, n, sub)
1016
1017def xscan.rowed(s: List<&2, Piece> & ((Array<F32> & Array<U32>) & (U32 & U32)), lines: Array<F32> & Array<U32>, rows: List<&2, List<&2, Run>>, +y: F32, +k: U32, +n: U32, +sub: U32, +w: U32) -> ((Array<F32> & Array<U32>) & (Array<F32> & Array<U32>)) & XData:
1018  (active, b) = s
1019  xscan.swept(xrow.runs(b, w), lines, rows, active, y, k, n, sub, w)
1020
1021def xscan.taken(t: (Array<F32> & Array<U32>) & PieceTake, buf: (Array<F32> & Array<U32>) & (U32 & U32), rows: List<&2, List<&2, Run>>, +y: F32, +sub: U32, +w: U32) -> ((Array<F32> & Array<U32>) & (Array<F32> & Array<U32>)) & XData:
1022  (lines, take) = t
1023  PieceTake{done, k, n, active} = take
1024  xscan.rowed(pieces.row(active, y, w, Nil{}, buf), lines, rows, y, k, n, sub, w)
1025
1026def xscan.row(st: ((Array<F32> & Array<U32>) & (Array<F32> & Array<U32>)) & XData, +y: U32, +w: U32) -> ((Array<F32> & Array<U32>) & (Array<F32> & Array<U32>)) & XData:
1027  ((buf, lines), data) = st
1028  XData{lo, hi, rows, active, k, n, sub} = data
1029  +yf = U32.to_f32(y)
1030  xscan.taken(piece.take((lines, PieceTake{False{}, k, n, active}), (yf + 1.0 : F32)), (buf, (lo, hi)), rows, yf, sub, w)
1031
1032@unsafe
1033def xscan.rows.go(st: ((Array<F32> & Array<U32>) & (Array<F32> & Array<U32>)) & XData, n: Nat, +y: U32, +w: U32) -> ((Array<F32> & Array<U32>) & (Array<F32> & Array<U32>)) & XData:
1034  match n:
1035    case 0n: st
1036    case 1n+d: xscan.rows.go(xscan.row(st, y, w), d, (y + 1 : U32), w)
1037
1038def xscan.done(st: ((Array<F32> & Array<U32>) & (Array<F32> & Array<U32>)) & XData) -> List<&2, List<&2, Run>>:
1039  ((buf, lines), data) = st
1040  XData{lo, hi, rows, active, k, n, sub} = data
1041  rows.reverse(rows, Nil{})
1042
1043# The rows of runs of the lines (in their arrays, n of them) by exact areas,
1044# rows with an overlap done with `sub` scanlines.
1045def xscan.rows(+h: U32, lines: Array<F32> & Array<U32>, +n: U32, +sub: U32, +w: U32) -> List<&2, List<&2, Run>>:
1046  xscan.done(xscan.rows.go((((Array.new(F32, depth.for((w * 2 + 4 : U32), 1, 0n), 0.0), Array.new(U32, depth.for((U32.div(w, 32) + 2 : U32), 1, 0n), 0)), lines),
1047    XData{(w + 1 : U32), 0, {Nil{} : List<&2, List<&2, Run>>}, {Nil{} : List<&2, Piece>}, 0, n, sub}), U32.to_nat(h), 0, w))
1048
1049# ---- the tree ----
1050# A node is built top-down from the rows of runs that lie inside it, clipped
1051# to its columns. One pass over a node's rows tells whether it is uniform (no
1052# runs, or in every row one run spanning the node with the same value) and at
1053# the same time splits the rows into the four quarters, each row's runs cut at
1054# the middle column, so no list is shared between the node and its children
1055# and a uniform node's rows are never looked at again.
1056
1057# A row's runs cut at mid into the left and right halves, with the row's
1058# uniform value over [x0, x1): 0 for no runs, the value of a single run that
1059# spans the columns, -1 otherwise.
1060type Halves is Data:
1061  Halves{value: F32, left: List<&2, Run>, right: List<&2, Run>}
1062
1063def halves.place(onLeft: Bool, onRight: Bool, +v: F32, +a: U32, +b: U32, +u: F32, +mid: U32, left: List<&2, Run>, right: List<&2, Run>) -> Halves:
1064  match onLeft onRight:
1065    case True{} _: Halves{v, Con{Run{a, b, u}, left}, right}
1066    case False{} True{}: Halves{v, left, Con{Run{a, b, u}, right}}
1067    case False{} False{}: Halves{v, Con{Run{a, mid, u}, left}, Con{Run{mid, b, u}, right}}
1068
1069def halves.push(h: Halves, +a: U32, +b: U32, +u: F32, +mid: U32, +x0: U32, +x1: U32) -> Halves:
1070  match h:
1071    case Halves{value, left, right}:
1072      +vv = value
1073      +full = F32.is_eq(vv, 0.0) && U32.is_eq(a, x0) && U32.is_eq(b, x1)
1074      halves.place(U32.is_le(b, mid), U32.is_ge(a, mid), U.choose(F32, full, u, F32.neg(1.0)), a, b, u, mid, left, right)
1075
1076def runs.halves(rs: List<&2, Run>, +mid: U32, +x0: U32, +x1: U32) -> Halves:
1077  match rs:
1078    case Nil{}: Halves{0.0, Nil{}, Nil{}}
1079    case Con{Run{a, b, u}, rest}: halves.push(runs.halves(rest, mid, x0, x1), a, b, u, mid, x0, x1)
1080
1081# A node's uniform value (2 before any row, -1 once rows disagree) and its
1082# quarters' rows; flat holds when the node is uniform (no rows means empty).
1083type Node is Data:
1084  Node{flat: Bool, value: F32, tl: List<&2, List<&2, Run>>, tr: List<&2, List<&2, Run>>, bl: List<&2, List<&2, Run>>, br: List<&2, List<&2, Run>>}
1085
1086def node.push(n: Node, h: Halves, top: Bool) -> Node:
1087  Node{flat, value, tl, tr, bl, br} = n
1088  Halves{v, left, right} = h
1089  match top:
1090    case True{}: Node{flat, tree.same.as(value, v), Con{left, tl}, Con{right, tr}, bl, br}
1091    case False{}: Node{flat, tree.same.as(value, v), tl, tr, Con{left, bl}, Con{right, br}}
1092
1093# Rows past the end of the list are empty; row i of size is a top row when i < half.
1094def node.rows(rows: List<&2, List<&2, Run>>, +i: U32, +size: U32, +half: U32, +x0: U32) -> Node:
1095  match rows:
1096    case Nil{}: Node{False{}, U.choose(F32, U32.is_lt(i, size), 0.0, 2.0), Nil{}, Nil{}, Nil{}, Nil{}}
1097    case Con{r, rest}: node.push(node.rows(rest, (i + 1 : U32), size, half, x0), runs.halves(r, (x0 + half : U32), x0, (x0 + size : U32)), U32.is_lt(i, half))
1098
1099def node.mark(n: Node) -> Node:
1100  Node{flat, value, tl, tr, bl, br} = n
1101  +vv = value
1102  Node{Bool.not(F32.is_lt(vv, 0.0)), vv, tl, tr, bl, br}
1103
1104def node.of(rows: List<&2, List<&2, Run>>, +size: U32, +x0: U32) -> Node:
1105  node.mark(node.rows(rows, 0, size, U32.div(size, 2), x0))
1106
1107def node.value(+v: F32) -> F32:
1108  U.choose(F32, F32.is_gt(v, 1.5), 0.0, v)
1109
1110@unsafe
1111def tree.node(n: Node, depth: Nat, +x0: U32, +size: U32) -> CovTree:
1112  match n:
1113    case Node{flat, value, tl, tr, bl, br}:
1114      match flat:
1115        case True{}: CovFlat{node.value(value)}
1116        case False{}:
1117          match depth:
1118            case 0n: CovFlat{node.value(value)}
1119            case 1n+d:
1120              +dd = d
1121              +half = U32.shln(1, dd)
1122              +x1 = (x0 + half : U32)
1123              CovQuad{tree.node(node.of(tl, half, x0), dd, x0, half), tree.node(node.of(tr, half, x1), dd, x1, half),
1124                tree.node(node.of(bl, half, x0), dd, x0, half), tree.node(node.of(br, half, x1), dd, x1, half)}
1125
1126# ---- entry ----
1127
1128type CovBox is Data:
1129  CovBox{x0: F32, y0: F32, x1: F32, y1: F32}
1130
1131def lines.bounds(xs: List<&2, CovLine>, +x0: F32, +y0: F32, +x1: F32, +y1: F32) -> CovBox:
1132  match xs:
1133    case Nil{}: CovBox{x0, y0, x1, y1}
1134    case Con{CovLine{ax, ay, bx, by}, rest}:
1135      +byDup = by
1136      +bxDup = bx
1137      +ayDup = ay
1138      +axDup = ax
1139      +lx = U.min(axDup, bxDup)
1140      +ly = U.min(ayDup, byDup)
1141      +hx = U.max(axDup, bxDup)
1142      +hy = U.max(ayDup, byDup)
1143      lines.bounds(rest, U.min(x0, lx), U.min(y0, ly), U.max(x1, hx), U.max(y1, hy))
1144
1145def lines.shift(xs: List<&2, CovLine>, +dx: F32, +dy: F32) -> List<&2, CovLine>:
1146  match xs:
1147    case Nil{}: Nil{}
1148    case Con{CovLine{ax, ay, bx, by}, rest}: Con{CovLine{(ax - dx : F32), (ay - dy : F32), (bx - dx : F32), (by - dy : F32)}, lines.shift(rest, dx, dy)}
1149
1150def mask.data(trees: Bool, rows: List<&2, List<&2, Run>>, +size: U32, +depth: Nat) -> CovData:
1151  match trees:
1152    case True{}: CovTreed{tree.node(node.of(rows, size, 0), depth, 0, size)}
1153    case False{}: CovRows{rows}
1154
1155def mask.arrays(xs: List<&2, CovLine>, +n: U32, +h: U32, +sub: U32, +w: U32) -> List<&2, List<&2, Run>>:
1156  xscan.rows(h, soa.build(xs, n, h), n, sub, w)
1157
1158# Even-odd fills rely on the winding parity, which only the sub-scanline scan follows.
1159def mask.scan(clipped: List<&2, CovLine> & U32, even: Bool, +h: U32, +sub: U32, +w: U32) -> List<&2, List<&2, Run>>:
1160  (xs, n) = clipped
1161  match even:
1162    case True{}: scan.rows(h, sub, lines.sort(xs), True{}, w)
1163    case False{}: mask.arrays(xs, n, h, sub, w)
1164
1165def mask.build(xs: List<&2, CovLine>, +gx: U32, +gy: U32, +w: U32, +h: U32, +even: Bool, +sub: U32, +trees: Bool) -> CovMask:
1166  +side = U.choose(U32, U32.is_gt(w, h), w, h)
1167  +depth = depth.for(side, 1, 0n)
1168  +size = U32.shln(1, depth)
1169  CovMask{gx, gy, w, h, size, depth, mask.data(trees, mask.scan(lines.prepare(xs, U32.to_f32(gx), U32.to_f32(gy), U32.to_f32(w), ({Nil{} : List<&2, CovLine>}, 0)), even, h, sub, w), size, depth), True{}}
1170
1171def mask.box(+xs: List<&2, CovLine>, +even: Bool, +width: U32, +height: U32, +sub: U32, box: CovBox, +trees: Bool) -> CovMask:
1172  CovBox{x0, y0, x1, y1} = box
1173  +gx = F32.to_u32(U.clamp(F32.floor(x0), 0.0, U32.to_f32(width)))
1174  +gy = F32.to_u32(U.clamp(F32.floor(y0), 0.0, U32.to_f32(height)))
1175  +ex = F32.to_u32(U.clamp(F32.ceil(x1), 0.0, U32.to_f32(width)))
1176  +ey = F32.to_u32(U.clamp(F32.ceil(y1), 0.0, U32.to_f32(height)))
1177  U.branch(CovMask, U32.is_ge(gx, ex) || U32.is_ge(gy, ey), _ => CovMask{0, 0, 0, 0, 0, 0n, CovTreed{CovFlat{0.0}}, True{}},
1178    _ => mask.build(xs, gx, gy, (ex - gx : U32), (ey - gy : U32), even, sub, trees))
1179
1180# A closed rectangle on whole pixels: four axis-aligned lines on the box edges
1181# with integer coordinates (the usual viewport clip and the common rect), whose
1182# mask is a tree of full and empty leaves with no scan at all.
1183def line.on.box(+ax: F32, +ay: F32, +bx: F32, +by: F32, +x0: F32, +y0: F32, +x1: F32, +y1: F32) -> Bool:
1184  (F32.is_eq(ax, bx) && (F32.is_eq(ax, x0) || F32.is_eq(ax, x1))) || (F32.is_eq(ay, by) && (F32.is_eq(ay, y0) || F32.is_eq(ay, y1)))
1185
1186# Zero-length lines (a path's move and close) are ignored; the four real ones must lie on the box.
1187def lines.on.box(xs: List<&2, CovLine>, +x0: F32, +y0: F32, +x1: F32, +y1: F32, +count: U32) -> Bool:
1188  match xs:
1189    case Nil{}: U32.is_eq(count, 4)
1190    case Con{CovLine{ax, ay, bx, by}, rest}:
1191      +axx = ax
1192      +ayy = ay
1193      +bxx = bx
1194      +byy = by
1195      +empty = F32.is_eq(axx, bxx) && F32.is_eq(ayy, byy)
1196      (empty || line.on.box(axx, ayy, bxx, byy, x0, y0, x1, y1)) && lines.on.box(rest, x0, y0, x1, y1, U.choose(U32, empty, count, (count + 1 : U32)))
1197
1198def whole(+v: F32) -> Bool:
1199  F32.is_eq(v, F32.floor(v))
1200
1201def rect.aligned(+xs: List<&2, CovLine>, +box: CovBox) -> Bool:
1202  CovBox{x0, y0, x1, y1} = box
1203  whole(x0) && whole(y0) && whole(x1) && whole(y1) && F32.is_lt(x0, x1) && F32.is_lt(y0, y1) && lines.on.box(xs, x0, y0, x1, y1, 0)
1204
1205@unsafe
1206def tree.rect(depth: Nat, +x: U32, +y: U32, +w: U32, +h: U32) -> CovTree:
1207  match depth:
1208    case 0n: CovFlat{U.choose(F32, U32.is_lt(x, w) && U32.is_lt(y, h), 1.0, 0.0)}
1209    case 1n+d:
1210      +dd = d
1211      +half = U32.shln(1, dd)
1212      +size = (half * 2 : U32)
1213      U.branch(CovTree, U32.is_ge(x, w) || U32.is_ge(y, h), _ => CovFlat{0.0},
1214        _ => U.branch(CovTree, U32.is_le((x + size : U32), w) && U32.is_le((y + size : U32), h), _ => CovFlat{1.0},
1215          _ => CovQuad{tree.rect(dd, x, y, w, h), tree.rect(dd, (x + half : U32), y, w, h), tree.rect(dd, x, (y + half : U32), w, h), tree.rect(dd, (x + half : U32), (y + half : U32), w, h)}))
1216
1217# A full rectangle as rows: one run per row.
1218def rect.rows(n: Nat, +w: U32, acc: List<&2, List<&2, Run>>) -> List<&2, List<&2, Run>>:
1219  match n:
1220    case 0n: acc
1221    case 1n+d: rect.rows(d, w, Con{Con{Run{0, w, 1.0}, Nil{}}, acc})
1222
1223def rect.data(trees: Bool, +depth: Nat, +w: U32, +h: U32) -> CovData:
1224  match trees:
1225    case True{}: CovTreed{tree.rect(depth, 0, 0, w, h)}
1226    case False{}: CovRows{rect.rows(U32.to_nat(h), w, Nil{})}
1227
1228def mask.rect(+width: U32, +height: U32, +box: CovBox, +trees: Bool) -> CovMask:
1229  CovBox{x0, y0, x1, y1} = box
1230  +gx = F32.to_u32(U.clamp(x0, 0.0, U32.to_f32(width)))
1231  +gy = F32.to_u32(U.clamp(y0, 0.0, U32.to_f32(height)))
1232  +ex = F32.to_u32(U.clamp(x1, 0.0, U32.to_f32(width)))
1233  +ey = F32.to_u32(U.clamp(y1, 0.0, U32.to_f32(height)))
1234  +w = (ex - gx : U32)
1235  +h = (ey - gy : U32)
1236  +depth = depth.for(U.choose(U32, U32.is_gt(w, h), w, h), 1, 0n)
1237  U.branch(CovMask, U32.is_ge(gx, ex) || U32.is_ge(gy, ey), _ => CovMask{0, 0, 0, 0, 0, 0n, CovTreed{CovFlat{0.0}}, True{}},
1238    _ => CovMask{gx, gy, w, h, U32.shln(1, depth), depth, rect.data(trees, depth, w, h), True{}})
1239
1240def mask.shape(aligned: Bool, +xs: List<&2, CovLine>, +even: Bool, +width: U32, +height: U32, +sub: U32, +box: CovBox, +trees: Bool) -> CovMask:
1241  match aligned:
1242    case True{}: mask.rect(width, height, box, trees)
1243    case False{}: mask.box(xs, even, width, height, sub, box, trees)
1244
1245# Rasterize closed contours given as directed lines in pixel coordinates of a
1246# width by height grid, with `sub` scanlines per pixel row; nonzero winding, or
1247# even-odd when `even` holds.
1248# even-odd when `even` holds; with `trees` the mask carries the quadtree that
1249# block and pixel queries need, else only its rows of runs.
1250def mask(+xs: List<&2, CovLine>, +even: Bool, +width: U32, +height: U32, +sub: U32, +trees: Bool) -> CovMask:
1251  +box = lines.bounds(xs, 1000000000.0, 1000000000.0, F32.neg(1000000000.0), F32.neg(1000000000.0))
1252  mask.shape(rect.aligned(xs, box), xs, even, width, height, sub, box, trees)
1253
1254# Lines gathered with their bounds and count as they are made, so the mask
1255# needs no pass of its own over them; only a handful of lines can be a
1256# rectangle, so the others skip that test too.
1257type CovLines is Data:
1258  CovLines{lines: List<&2, CovLine>, x0: F32, y0: F32, x1: F32, y1: F32, count: U32}
1259
1260def lines.empty() -> CovLines:
1261  CovLines{Nil{}, 1000000000.0, 1000000000.0, F32.neg(1000000000.0), F32.neg(1000000000.0), 0}
1262
1263def lines.add(l: CovLines, +ax: F32, +ay: F32, +bx: F32, +by: F32) -> CovLines:
1264  CovLines{xs, x0, y0, x1, y1, n} = l
1265  CovLines{Con{CovLine{ax, ay, bx, by}, xs}, U.min(x0, U.min(ax, bx)), U.min(y0, U.min(ay, by)), U.max(x1, U.max(ax, bx)), U.max(y1, U.max(ay, by)), (n + 1 : U32)}
1266
1267def mask.lined.pick(few: Bool, xs: List<&2, CovLine>, box: CovBox, +even: Bool, +width: U32, +height: U32, +sub: U32, +trees: Bool) -> CovMask:
1268  match few:
1269    case True{}:
1270      +ls = xs
1271      +b = box
1272      mask.shape(rect.aligned(ls, b), ls, even, width, height, sub, b, trees)
1273    case False{}: mask.box(xs, even, width, height, sub, box, trees)
1274
1275def mask.lined(l: CovLines, +even: Bool, +width: U32, +height: U32, +sub: U32, +trees: Bool) -> CovMask:
1276  CovLines{xs, x0, y0, x1, y1, n} = l
1277  mask.lined.pick(U32.is_le(n, 5), xs, CovBox{x0, y0, x1, y1}, even, width, height, sub, trees)
1278
1279def mask.scanned(+xs: List<&2, CovLine>, +even: Bool, +width: U32, +height: U32, +sub: U32, +trees: Bool) -> CovMask:
1280  mask.box(xs, even, width, height, sub, lines.bounds(xs, 1000000000.0, 1000000000.0, F32.neg(1000000000.0), F32.neg(1000000000.0)), trees)