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.
5	import Base
6	import gralha-text-scan@0.1.0.1/scan.bend as U
7	
8	# A directed line in pixel coordinates of the target grid.
9	type 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.
13	type 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.
18	type 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.
24	type 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.
30	type CovMask is Data:
31	  CovMask{x: U32, y: U32, w: U32, h: U32, size: U32, depth: Nat, data: CovData, present: Bool}
32	
33	def 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.
37	def 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	
46	def 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	
51	def mask.present(+m: CovMask) -> Bool:
52	  CovMask{x, y, w, h, size, depth, tree, present} = m
53	  present
54	
55	@unsafe
56	def 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	
67	def 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	
72	def 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.
79	def 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.
93	def 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	
96	def 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
100	def 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.
115	def 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
129	def 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	
136	def 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	
141	def 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	
151	def 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	
156	def 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	
168	def 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	
173	def 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.
180	def 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.
186	def 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.
193	def 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.
199	def 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	
206	def 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	
209	def 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	
213	def 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	
217	def 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	
237	def 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.
242	type 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.
246	type Ins is Data:
247	  Placed{list: List<&2, Act>}
248	  Passed{h: Act, t: List<&2, Act>, a: Act}
249	
250	def 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
256	def 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	
268	def 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	
277	def 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.
283	def 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.
290	def 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.
301	type Take is Data:
302	  Take{done: Bool, pending: List<&2, CovLine>, acc: List<&2, Act>}
303	
304	def 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
310	def 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	
330	type CovEv is Data:
331	  CovEv{cell: U32, direct: F32, delta: F32}
332	
333	def 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	
338	def 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	
341	def 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].
347	def 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	
355	def 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.
360	type Step is Data:
361	  Step{events: List<&2, CovEv>, next: List<&2, Act>}
362	
363	@unsafe
364	def 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.
375	type EvOrder is Data:
376	  EvOrder{first: CovEv, rest: List<&2, CovEv>, other: List<&2, CovEv>}
377	
378	def ev.cell(+e: CovEv) -> U32:
379	  CovEv{cell, direct, delta} = e
380	  cell
381	
382	def 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	
387	def 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
393	def 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	
403	def 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.
419	def run.snap(+v: F32) -> F32:
420	  U.choose(F32, F32.is_lt(F32.abs(v), 0.000001), 0.0, v)
421	
422	def 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	
427	def 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.
440	def 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.
445	type 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.
449	def 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	
452	def 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
458	def 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.
468	def 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	
473	type LineOrder is Data:
474	  LineOrder{first: CovLine, rest: List<&2, CovLine>, other: List<&2, CovLine>}
475	
476	def 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	
481	def 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
487	def 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	
497	def 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	
505	type LineSplit is Data:
506	  LineSplit{left: List<&2, CovLine>, right: List<&2, CovLine>}
507	
508	def 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
516	def 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	
523	def 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	
532	type Subs is Data:
533	  Subs{active: List<&2, Act>, pending: List<&2, CovLine>, events: List<&2, CovEv>}
534	
535	def subs.done(t: Take, events: List<&2, CovEv>) -> Subs:
536	  Take{done, pending, acc} = t
537	  Subs{act.reverse(acc, Nil{}), pending, events}
538	
539	def 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	
543	def 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
549	def 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	
554	type Scan is Data:
555	  Scan{rows: List<&2, List<&2, Run>>, active: List<&2, Act>, pending: List<&2, CovLine>}
556	
557	def 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	
561	def 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
567	def 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	
572	def 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	
577	def scan.done(st: Scan) -> List<&2, List<&2, Run>>:
578	  Scan{rows, active, pending} = st
579	  rows.reverse(rows, Nil{})
580	
581	def 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.
586	def 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
590	def 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).
607	type Piece is Data:
608	  Piece{x0: F32, y0: F32, slope: F32, top: F32, bottom: F32, dir: F32}
609	
610	def 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	
618	def 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	
627	def 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	
631	def buf.add(a: Array<F32>, +i: U32, +v: F32) -> Array<F32>:
632	  buf.add.got(Array.get(F32, a, i), i, v)
633	
634	def 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	
638	def 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.
644	def 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	
650	def 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
661	def 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).
680	def 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	
694	def 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.
702	def 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	
709	def 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.
718	def 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	
729	def 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	
734	def 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	
744	def row.of(+top: F32, +h: U32) -> U32:
745	  F32.to_u32(U.clamp(F32.floor(top), 0.0, U32.to_f32(h)))
746	
747	def 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	
751	def 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.
755	def 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.
766	def 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
771	def 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	
777	def 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.
782	def 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	
787	def 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	
792	def 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
797	def 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	
803	def soa.placed(st: Array<F32> & (Array<U32> & Array<U32>)) -> Array<F32> & Array<U32>:
804	  (a, (starts, order)) = st
805	  (a, order)
806	
807	def 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.
812	def 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.
816	def 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	
820	def 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	
824	def 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	
828	def 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	
832	def 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	
836	def 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
842	def 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	
848	def soa.lines.done(st: Array<F32> & (Array<U32> & List<&2, CovLine>)) -> List<&2, CovLine>:
849	  (a, (order, acc)) = st
850	  acc
851	
852	def 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.
858	type PieceTake is Data:
859	  PieceTake{done: Bool, k: U32, n: U32, active: List<&2, Piece>}
860	
861	def 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	
865	def 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	
869	def 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	
877	def 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	
883	def 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	
887	def 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	
892	def 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
899	def 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.
916	type XState is Data:
917	  XState{sum: F32, bad: Bool, upper: U32, acc: List<&2, Run>}
918	
919	def xrun.value(+v: F32) -> F32:
920	  U.min(1.0, run.snap(F32.abs(v)))
921	
922	def 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	
932	def 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	
936	def 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
944	def 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	
950	def 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	
955	def 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	
960	def 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
966	def 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).
972	def 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	
978	def 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	
981	def 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.
985	def 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.
990	type 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	
993	def 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.
1001	def 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	
1008	def 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	
1013	def 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	
1017	def 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	
1021	def 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	
1026	def 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
1033	def 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	
1038	def 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.
1045	def 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.
1060	type Halves is Data:
1061	  Halves{value: F32, left: List<&2, Run>, right: List<&2, Run>}
1062	
1063	def 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	
1069	def 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	
1076	def 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).
1083	type 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	
1086	def 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.
1094	def 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	
1099	def 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	
1104	def 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	
1107	def node.value(+v: F32) -> F32:
1108	  U.choose(F32, F32.is_gt(v, 1.5), 0.0, v)
1109	
1110	@unsafe
1111	def 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	
1128	type CovBox is Data:
1129	  CovBox{x0: F32, y0: F32, x1: F32, y1: F32}
1130	
1131	def 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	
1145	def 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	
1150	def 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	
1155	def 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.
1159	def 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	
1165	def 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	
1171	def 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.
1183	def 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.
1187	def 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	
1198	def whole(+v: F32) -> Bool:
1199	  F32.is_eq(v, F32.floor(v))
1200	
1201	def 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
1206	def 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.
1218	def 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	
1223	def 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	
1228	def 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	
1240	def 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.
1250	def 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.
1257	type CovLines is Data:
1258	  CovLines{lines: List<&2, CovLine>, x0: F32, y0: F32, x1: F32, y1: F32, count: U32}
1259	
1260	def lines.empty() -> CovLines:
1261	  CovLines{Nil{}, 1000000000.0, 1000000000.0, F32.neg(1000000000.0), F32.neg(1000000000.0), 0}
1262	
1263	def 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	
1267	def 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	
1275	def 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	
1279	def 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)