Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_graphics/src/raster.rs

16.1 KiB, 26 runs

created by r1870400018:13950, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The rasteriser: polygons in, per-pixel coverage out.
2//!
3//! # How it works
4//!
5//! The usual way to anti-alias is to sample a shape many times per pixel and count the hits, which
6//! costs as many passes as samples and still only estimates the answer. This rasteriser computes
7//! the answer instead.
8//!
9//! Every edge of the polygon is walked one scanline at a time. For each pixel the edge passes
10//! through, the *signed area* the edge contributes is accumulated: positive where the edge runs
11//! down the screen, negative where it runs up. Once every edge has been walked, a running sum
12//! along each row turns those local contributions into the winding number at each pixel, weighted
13//! by how much of the pixel the shape actually covers. A pixel wholly inside the shape sums to one;
14//! a pixel the edge cuts in half sums to a half; a pixel outside sums to zero.
15//!
16//! # Fill rules
17//!
18//! What that running sum holds is easy to misread. It is not a winding number: it is the winding
19//! number *averaged over the pixel's area*, so a pixel whose left half lies in a region wound once
20//! and whose right half lies in a region wound twice sums to one and a half. A fill rule therefore
21//! cannot be read off the sum by testing it -- ask "is this odd?" of one and a half and there is no
22//! answer. The rule has to be extended from the integers, where it is defined, out to the reals,
23//! where the sum lives, by a map that runs straight between them, so that a half-covered pixel
24//! comes out half covered.
25//!
26//! The absolute value of the sum, clamped to one, is that extension for the **non-zero winding
27//! rule**, which is what glyph outlines are drawn for: an inner contour wound the other way
28//! subtracts, and a counter comes out hollow. A triangle wave of period two is the extension for
29//! the **even-odd rule**: nothing at even windings, everything at odd ones, and a ramp between, so
30//! that where two contours overlap a hole opens with a soft edge rather than a jagged one. See
31//! [`FillRule`].
32//!
33//! # Why the buffer is wider than the window
34//!
35//! Geometry off the left of the window is clamped to the left edge, where its winding still counts:
36//! a shape running off the left of the screen still fills the pixels that remain. Geometry off the
37//! right is clamped into two slack columns past the right edge, where it lands harmlessly, because
38//! a running sum that moves left to right can never be reached by anything to its right.
39//!
40//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
41//! Anthropic Claude
42
43use crate::path::Pt;
44
45/// Which points a path encloses, where its contours cross or overlap.
46///
47/// The two rules differ only where a point is wound more than once. A glyph, whose counters are
48/// wound against their outer contour, wants [`FillRule::NonZero`]; a self-intersecting star or a
49/// pair of overlapping rings, where the crossing is meant to read as a hole, wants
50/// [`FillRule::EvenOdd`].
51#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
52pub enum FillRule {
53 #[default]
54 NonZero, // inside where the winding number is not zero, as an outline font means
55 EvenOdd, // inside where it is odd, so a second layer of winding takes the paint back off
56}
57
58impl FillRule {
59
60 /// Turns an accumulated winding, weighted by coverage, into coverage from 0 to 1.
61 ///
62 /// See the module docs: the argument is an average of winding numbers over a pixel, not a
63 /// winding number, so each rule is applied as the straight-line extension of itself off the
64 /// integers. Non-zero saturates, even-odd folds back.
65 pub fn coverage(&self, acc: f32) -> f32 {
66 match self {
67 Self::NonZero => acc.abs().min(1.0),
68 Self::EvenOdd => {
69 // One period of the wave, from 0 up to 2, direction thrown away as the rule is
70 // blind to it.
71 let w = (acc % 2.0).abs();
72 if w > 1.0 { 2.0 - w } else { w }
73 },
74 }
75 }
76}
77
78/// Accumulates the signed area of a set of edges over a rectangular window of pixels.
79#[derive(Clone, Debug)]
80pub struct Raster {
81 w: usize, // window width, in pixels
82 h: usize, // window height, in pixels
83 a: Vec<f32>, // accumulation buffer, (w + 2) * h; see the module docs on the slack
84}
85
86impl Raster {
87
88 pub fn new(w: usize, h: usize) -> Self {
89 Self {
90 w,
91 h,
92 a: vec![0.0; (w + 2) * h],
93 }
94 }
95
96 pub fn width(&self) -> usize {
97 self.w
98 }
99
100 pub fn height(&self) -> usize {
101 self.h
102 }
103
104 /// Adds a closed contour, whose points are in window coordinates.
105 ///
106 /// The contour is closed whether or not its last point repeats its first, since only a closed
107 /// contour has an interior.
108 pub fn add_contour(&mut self, pts: &[Pt]) {
109 if pts.len() < 2 {
110 return;
111 }
112 for i in 0..pts.len() {
113 let p0 = pts[i];
114 let p1 = pts[(i + 1) % pts.len()];
115 self.add_edge(p0, p1);
116 }
117 }
118
119 /// Adds one edge, accumulating the signed area it contributes to each pixel it crosses.
120 pub fn add_edge(&mut self, p0: Pt, p1: Pt) {
121 if !p0.is_finite() || !p1.is_finite() {
122 return;
123 }
124 if (p0.y - p1.y).abs() <= f32::EPSILON {
125 return; // A horizontal edge sweeps no area.
126 }
127 // Walk downwards, remembering which way the edge really ran.
128 let (dir, top, bot) = if p0.y < p1.y {
129 (1.0f32, p0, p1)
130 } else {
131 (-1.0f32, p1, p0)
132 };
133 let hf = self.h as f32;
134 if bot.y <= 0.0 || top.y >= hf {
135 return; // Wholly above or below the window.
136 }
137 let dxdy = (bot.x - top.x) / (bot.y - top.y);
138 let x_at = |y: f32| -> f32 { top.x + (y - top.y) * dxdy };
139
140 let y_start = top.y.max(0.0);
141 let y_end = bot.y.min(hf);
142 let y0 = y_start.floor() as usize;
143 let y1 = (y_end.ceil() as usize).min(self.h);
144 let stride = self.w + 2;
145 // Clamping to the window width, not past it, keeps every index this method writes inside
146 // the two slack columns the buffer carries.
147 let xmax = self.w as f32;
148
149 for y in y0..y1 {
150 let ytop = (y as f32).max(y_start);
151 let ybot = ((y + 1) as f32).min(y_end);
152 let dy = ybot - ytop;
153 if dy <= 0.0 {
154 continue;
155 }
156 let d = dy * dir;
157 let xa = x_at(ytop).clamp(0.0, xmax);
158 let xb = x_at(ybot).clamp(0.0, xmax);
159 let (x0, x1) = if xa < xb { (xa, xb) } else { (xb, xa) };
160 let row = y * stride;
161
162 let x0floor = x0.floor();
163 let x0i = x0floor as usize;
164 let x1ceil = x1.ceil();
165 let x1i = x1ceil as usize;
166
167 if x1i <= x0i + 1 {
168 // The edge crosses this scanline within a single column, so the area splits between
169 // that column and the next by where the edge's midpoint sits.
170 let xmf = 0.5 * (x0 + x1) - x0floor;
171 self.a[row + x0i] += d * (1.0 - xmf);
172 self.a[row + x0i + 1] += d * xmf;
173 } else {
174 // The edge spans several columns: a wedge at each end, and a uniform slope between.
175 let s = (x1 - x0).recip();
176 let x0f = x0 - x0floor;
177 let a0 = 0.5 * s * (1.0 - x0f) * (1.0 - x0f);
178 let x1f = x1 - x1ceil + 1.0;
179 let am = 0.5 * s * x1f * x1f;
180 self.a[row + x0i] += d * a0;
181 if x1i == x0i + 2 {
182 self.a[row + x0i + 1] += d * (1.0 - a0 - am);
183 } else {
184 let a1 = s * (1.5 - x0f);
185 self.a[row + x0i + 1] += d * (a1 - a0);
186 for xi in (x0i + 2)..(x1i - 1) {
187 self.a[row + xi] += d * s;
188 }
189 let a2 = a1 + ((x1i - x0i - 3) as f32) * s;
190 self.a[row + x1i - 1] += d * (1.0 - a2 - am);
191 }
192 self.a[row + x1i] += d * am;
193 }
194 }
195 }
196
197 /// Resolves the accumulated areas into per-pixel coverage under the non-zero winding rule, from
198 /// 0 to 1, row-major, `w * h`.
199 pub fn coverage(&self) -> Vec<f32> {
200 self.coverage_with(FillRule::NonZero)
201 }
202
203 /// As [`Raster::coverage`], under a chosen fill rule.
204 ///
205 /// The running sum restarts on every row. A closed contour makes each row sum back to zero, so
206 /// restarting costs nothing and stops any drift from crossing into the row below.
207 pub fn coverage_with(&self, rule: FillRule) -> Vec<f32> {
208 let stride = self.w + 2;
209 let mut out = vec![0.0f32; self.w * self.h];
210 for y in 0..self.h {
211 let row = y * stride;
212 let orow = y * self.w;
213 let mut acc = 0.0f32;
214 for x in 0..self.w {
215 acc += self.a[row + x];
216 out[orow + x] = rule.coverage(acc);
217 }
218 }
219 out
220 }
221}
222
223#[cfg(test)]
224mod tests {
225 use super::*;
226
227 fn square(x0: f32, y0: f32, x1: f32, y1: f32) -> Vec<Pt> {
228 vec![
229 Pt::new(x0, y0),
230 Pt::new(x1, y0),
231 Pt::new(x1, y1),
232 Pt::new(x0, y1),
233 ]
234 }
235
236 #[test]
237 fn test_whole_pixels_are_fully_covered_00() {
238 let mut r = Raster::new(8, 8);
239 r.add_contour(&square(2.0, 2.0, 6.0, 6.0));
240 let cov = r.coverage();
241 // Inside.
242 assert!((cov[3 * 8 + 3] - 1.0).abs() < 1e-4, "found {}", cov[3 * 8 + 3]);
243 // Outside.
244 assert!(cov[0] < 1e-4, "found {}", cov[0]);
245 assert!(cov[7 * 8 + 7] < 1e-4);
246 }
247
248 #[test]
249 fn test_half_covered_pixel_is_half_01() {
250 // A square covering the left half of every pixel in column 0.
251 let mut r = Raster::new(4, 4);
252 r.add_contour(&square(0.0, 0.0, 0.5, 4.0));
253 let cov = r.coverage();
254 for y in 0..4 {
255 assert!(
256 (cov[y * 4] - 0.5).abs() < 1e-3,
257 "row {} should be half covered, found {}", y, cov[y * 4],
258 );
259 }
260 }
261
262 #[test]
263 fn test_winding_is_direction_blind_02() {
264 // The same square wound the other way covers the same pixels.
265 let mut cw = Raster::new(8, 8);
266 cw.add_contour(&square(2.0, 2.0, 6.0, 6.0));
267 let mut ccw = Raster::new(8, 8);
268 let mut pts = square(2.0, 2.0, 6.0, 6.0);
269 pts.reverse();
270 ccw.add_contour(&pts);
271 let (a, b) = (cw.coverage(), ccw.coverage());
272 for i in 0..a.len() {
273 assert!((a[i] - b[i]).abs() < 1e-4, "pixel {} differs: {} then {}", i, a[i], b[i]);
274 }
275 }
276
277 #[test]
278 fn test_reversed_inner_contour_cuts_a_hole_03() {
279 // The non-zero rule: an inner contour wound the other way subtracts.
280 let mut r = Raster::new(10, 10);
281 r.add_contour(&square(1.0, 1.0, 9.0, 9.0));
282 let mut hole = square(3.0, 3.0, 7.0, 7.0);
283 hole.reverse();
284 r.add_contour(&hole);
285 let cov = r.coverage();
286 assert!((cov[2 * 10 + 2] - 1.0).abs() < 1e-4, "the ring should be solid");
287 assert!(cov[5 * 10 + 5] < 1e-4, "the counter should be hollow, found {}", cov[5 * 10 + 5]);
288 }
289
290 #[test]
291 fn test_same_wound_overlap_does_not_exceed_one_04() {
292 let mut r = Raster::new(8, 8);
293 r.add_contour(&square(1.0, 1.0, 7.0, 7.0));
294 r.add_contour(&square(2.0, 2.0, 6.0, 6.0));
295 let cov = r.coverage();
296 for (i, c) in cov.iter().enumerate() {
297 assert!(*c <= 1.0 + 1e-6, "pixel {} exceeds full coverage at {}", i, c);
298 }
299 assert!((cov[4 * 8 + 4] - 1.0).abs() < 1e-4);
300 }
301
302 #[test]
303 fn test_geometry_off_the_window_is_clamped_not_crashed_05() {
304 // A shape running far off every edge must fill the window and index nothing out of range.
305 let mut r = Raster::new(8, 8);
306 r.add_contour(&square(-1000.0, -1000.0, 1000.0, 1000.0));
307 let cov = r.coverage();
308 for (i, c) in cov.iter().enumerate() {
309 assert!((c - 1.0).abs() < 1e-3, "pixel {} should be filled, found {}", i, c);
310 }
311 }
312
313 #[test]
314 fn test_shape_beyond_the_right_edge_paints_nothing_06() {
315 // Entirely off to the right: the slack columns swallow it.
316 let mut r = Raster::new(8, 8);
317 r.add_contour(&square(20.0, 0.0, 30.0, 8.0));
318 let cov = r.coverage();
319 for (i, c) in cov.iter().enumerate() {
320 assert!(*c < 1e-4, "pixel {} should be empty, found {}", i, c);
321 }
322 }
323
324 #[test]
325 fn test_a_triangle_is_antialiased_07() {
326 // The diagonal must produce partial coverage somewhere, or there is no anti-aliasing.
327 let mut r = Raster::new(16, 16);
328 r.add_contour(&[Pt::new(0.0, 0.0), Pt::new(16.0, 0.0), Pt::new(0.0, 16.0)]);
329 let cov = r.coverage();
330 let partial = cov.iter().filter(|c| **c > 0.05 && **c < 0.95).count();
331 assert!(partial > 8, "expected a soft diagonal, found {} partial pixels", partial);
332 }
333
334 /// A five-pointed star drawn as one self-crossing contour, whose middle is wound twice.
335 fn star(cx: f32, cy: f32, r: f32) -> Vec<Pt> {
336 let mut pts = Vec::with_capacity(5);
337 for k in 0..5 {
338 // Every second vertex of a pentagon, so the contour crosses itself.
339 let a = -std::f32::consts::FRAC_PI_2
340 + (k as f32) * 2.0 * std::f32::consts::TAU / 5.0;
341 pts.push(Pt::new(cx + r * a.cos(), cy + r * a.sin()));
342 }
343 pts
344 }
345
346 #[test]
347 fn test_non_zero_is_the_default_and_is_unchanged_09() {
348 // The rule-taking method must agree with the old one to the last bit, or every golden
349 // image downstream shifts.
350 let mut r = Raster::new(16, 16);
351 r.add_contour(&square(1.5, 1.5, 12.25, 9.75));
352 r.add_contour(&[Pt::new(2.0, 3.0), Pt::new(15.0, 4.5), Pt::new(6.0, 14.0)]);
353 let old = r.coverage();
354 let new = r.coverage_with(FillRule::NonZero);
355 assert_eq!(old, new, "the non-zero rule must be bit-identical");
356 assert_eq!(FillRule::default(), FillRule::NonZero);
357 }
358
359 #[test]
360 fn test_even_odd_makes_a_hole_of_an_overlap_10() {
361 // Two squares wound the same way. Non-zero unions them; even-odd cancels the overlap.
362 let mut r = Raster::new(8, 8);
363 r.add_contour(&square(0.0, 0.0, 6.0, 8.0));
364 r.add_contour(&square(3.5, 0.0, 8.0, 8.0));
365 let nz = r.coverage_with(FillRule::NonZero);
366 let eo = r.coverage_with(FillRule::EvenOdd);
367 // Column 5 lies in the overlap, wound twice.
368 assert!((nz[4 * 8 + 5] - 1.0).abs() < 1e-4, "non-zero should fill the overlap");
369 assert!(eo[4 * 8 + 5] < 1e-4, "even-odd should hollow it, found {}", eo[4 * 8 + 5]);
370 // Columns 1 and 7 lie under one square only, so both rules fill them.
371 assert!((eo[4 * 8 + 1] - 1.0).abs() < 1e-4, "found {}", eo[4 * 8 + 1]);
372 assert!((eo[4 * 8 + 7] - 1.0).abs() < 1e-4, "found {}", eo[4 * 8 + 7]);
373 }
374
375 #[test]
376 fn test_even_odd_softens_the_edge_of_the_hole_11() {
377 // The subtlety, pinned. Column 3 is half in the singly wound part and half in the doubly
378 // wound part, so the running sum there is 1.5: a number that is neither odd nor even. The
379 // answer is half coverage, which only a rule ramped between the integers can give. Testing
380 // the parity of the rounded sum would say nothing here, and clamping it would say one.
381 let mut r = Raster::new(8, 8);
382 r.add_contour(&square(0.0, 0.0, 6.0, 8.0));
383 r.add_contour(&square(3.5, 0.0, 8.0, 8.0));
384 let eo = r.coverage_with(FillRule::EvenOdd);
385 let c = eo[4 * 8 + 3];
386 assert!((c - 0.5).abs() < 1e-3, "the hole's edge should be half covered, found {}", c);
387 }
388
389 #[test]
390 fn test_even_odd_is_blind_to_direction_12() {
391 // Winding the second square the other way changes the sum's sign but not its parity, so
392 // even-odd hollows the overlap either way, where non-zero would only hollow one of them.
393 let mut same = Raster::new(8, 8);
394 same.add_contour(&square(0.0, 0.0, 6.0, 8.0));
395 same.add_contour(&square(3.5, 0.0, 8.0, 8.0));
396 let mut anti = Raster::new(8, 8);
397 anti.add_contour(&square(0.0, 0.0, 6.0, 8.0));
398 let mut back = square(3.5, 0.0, 8.0, 8.0);
399 back.reverse();
400 anti.add_contour(&back);
401 let (a, b) = (same.coverage_with(FillRule::EvenOdd), anti.coverage_with(FillRule::EvenOdd));
402 for i in 0..a.len() {
403 assert!((a[i] - b[i]).abs() < 1e-4, "pixel {} differs: {} then {}", i, a[i], b[i]);
404 }
405 }
406
407 #[test]
408 fn test_even_odd_hollows_a_self_crossing_star_13() {
409 // The classic case: the pentagon at the heart of a five-pointed star is wound twice.
410 let mut r = Raster::new(32, 32);
411 r.add_contour(&star(16.0, 16.0, 14.0));
412 let nz = r.coverage_with(FillRule::NonZero);
413 let eo = r.coverage_with(FillRule::EvenOdd);
414 assert!((nz[16 * 32 + 16] - 1.0).abs() < 1e-4, "non-zero should fill the heart");
415 assert!(eo[16 * 32 + 16] < 1e-4, "even-odd should hollow it, found {}", eo[16 * 32 + 16]);
416 // The arms are wound once, so they stand under either rule.
417 assert!((eo[5 * 32 + 16] - 1.0).abs() < 1e-3, "the top arm, found {}", eo[5 * 32 + 16]);
418 assert!((nz[5 * 32 + 16] - 1.0).abs() < 1e-3);
419 }
420
421 #[test]
422 fn test_the_rules_agree_where_nothing_overlaps_14() {
423 // A single simple contour is wound once or not at all, and one is odd, so the rules must
424 // give the same picture, anti-aliased edges and all.
425 let mut r = Raster::new(16, 16);
426 r.add_contour(&[Pt::new(1.3, 0.7), Pt::new(14.8, 2.2), Pt::new(5.5, 15.1)]);
427 let nz = r.coverage_with(FillRule::NonZero);
428 let eo = r.coverage_with(FillRule::EvenOdd);
429 for i in 0..nz.len() {
430 assert!((nz[i] - eo[i]).abs() < 1e-4, "pixel {} differs: {} then {}", i, nz[i], eo[i]);
431 }
432 }
433
434 #[test]
435 fn test_degenerate_input_is_survived_08() {
436 let mut r = Raster::new(4, 4);
437 r.add_contour(&[]);
438 r.add_contour(&[Pt::new(1.0, 1.0)]);
439 r.add_edge(Pt::new(f32::NAN, 0.0), Pt::new(1.0, 1.0));
440 r.add_edge(Pt::new(0.0, 2.0), Pt::new(4.0, 2.0)); // Horizontal.
441 let cov = r.coverage();
442 assert!(cov.iter().all(|c| *c < 1e-6));
443 }
444}