Skip to main content

font_shape/
raster.rs

1//! The scanline rasteriser: exact analytic coverage.
2//!
3//! `fill_path` walks each pixel row, finds where the path's edges cross it,
4//! determines the inside spans from the fill rule, and computes the **exact**
5//! area each span covers in each pixel column. The result is an 8-bit coverage
6//! mask, one byte per pixel, `0..=255`.
7//!
8//! # Why exact, and what that buys
9//!
10//! The alternative — supersampling a point-in-path test — is approximate, and
11//! its error is worst exactly where a glyph rasteriser is most sensitive: thin
12//! stems and small sizes. Analytic area gives two properties that are
13//! directly testable:
14//!
15//! - An **axis-aligned rectangle** gets exactly the coverage its geometry
16//!   implies: a rectangle on integer boundaries is all `255`, the same
17//!   rectangle shifted half a pixel is exactly half covered on each edge.
18//! - The **sum of a mask's coverage** equals the polygon's area to within the
19//!   curve-flattening tolerance, so `mask_sum / 255 ≈ path_area` for any shape.
20//!   That is the single number that bounds every antialiasing claim this crate
21//!   makes.
22//!
23//! Curves are flattened first, so the exactness is with respect to the
24//! *polygon*; the flattening tolerance sets how far a mask can be from the true
25//! curve, and it is chosen from the geometry rather than hard-coded.
26//!
27//! # Coordinates
28//!
29//! Device space with **y down**: pixel `(x, y)` covers the unit square
30//! `[x, x+1) × [y, y+1)`. A glyph is flipped into that space before
31//! rasterisation, which is why a font's y-up outlines and a bitmap's y-down
32//! rows do not need to be reconciled anywhere else.
33
34use alloc::vec;
35use alloc::vec::Vec;
36
37use crate::error::ShapeError;
38use crate::path::Path2D;
39
40/// Which rule decides whether a point is inside the path.
41#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
42pub enum FillRule {
43    /// Inside where the winding number is non-zero. The default, and what a
44    /// glyph wants: a glyph's outer and inner contours usually run the same
45    /// way, so non-zero makes the counter the same colour.
46    #[default]
47    NonZero,
48    /// Inside where the crossing count is odd. This is the rule that punches a
49    /// hole in a nested contour regardless of its direction.
50    EvenOdd,
51}
52
53/// The largest mask this crate will allocate: 4096 × 4096 = 16 MiB of coverage.
54pub const MAX_MASK_ELEMENTS: usize = 16_777_216;
55
56/// The flattener's tolerance for fill, as a fraction of a pixel.
57///
58/// A quarter of a pixel would be visible; 1/64th keeps a curve's flattened
59/// area within a few hundredths of a percent of the true area, well inside the
60/// 1 % the tests allow.
61const FILL_TOLERANCE: f32 = 1.0 / 64.0;
62
63/// Fill `path` into an 8-bit coverage mask `width` × `height`.
64///
65/// `data.len()` is exactly `width × height`, row-major from the top-left.
66///
67/// Returns `Ok(Vec::new())` for a zero-sized raster, and an empty mask for a
68/// path that covers nothing.
69///
70/// # Errors
71/// [`ShapeError::RasterTooLarge`] when `width × height` exceeds
72/// [`MAX_MASK_ELEMENTS`] — a guard against a size argument that would allocate
73/// gigabytes.
74///
75/// ```
76/// use font_shape::{fill_path, FillRule, PathBuilder};
77///
78/// let mut b = PathBuilder::new();
79/// b.rect(4.0, 4.0, 8.0, 8.0);          // exactly 8x8 pixels
80/// let path = b.build();
81/// let mask = fill_path(&path, FillRule::NonZero, 16, 16).unwrap();
82///
83/// assert_eq!(mask.len(), 16 * 16);
84/// // Every pixel of the 8x8 block is fully covered...
85/// for y in 4..12 {
86///     for x in 4..12 {
87///         assert_eq!(mask[y * 16 + x], 255, "({x}, {y})");
88///     }
89/// }
90/// // ...and nothing outside it is.
91/// assert_eq!(mask[3 * 16 + 4], 0);
92/// assert_eq!(mask[0], 0);
93/// ```
94#[allow(clippy::result_large_err)]
95pub fn fill_path(
96    path: &Path2D,
97    fill_rule: FillRule,
98    width: u32,
99    height: u32,
100) -> Result<Vec<u8>, ShapeError> {
101    let w = usize::try_from(width).unwrap_or(usize::MAX);
102    let h = usize::try_from(height).unwrap_or(usize::MAX);
103    if w == 0 || h == 0 {
104        return Ok(Vec::new());
105    }
106    let pixels = w.saturating_mul(h);
107    if pixels > MAX_MASK_ELEMENTS {
108        return Err(ShapeError::RasterTooLarge {
109            pixels,
110            limit: MAX_MASK_ELEMENTS,
111        });
112    }
113    let mut mask = vec![0u8; pixels];
114    let edges = collect_edges(path);
115    if edges.is_empty() {
116        return Ok(mask);
117    }
118    let coverage = rasterize(&edges, fill_rule, w, h);
119    for (slot, &c) in mask.iter_mut().zip(coverage.iter()) {
120        *slot = c;
121    }
122    Ok(mask)
123}
124
125/// The total coverage of a mask, in 0..255 units. Dividing by 255 gives the
126/// ink area in pixels.
127#[must_use]
128pub fn mask_coverage(mask: &[u8]) -> f64 {
129    mask.iter().map(|&v| f64::from(v)).sum::<f64>()
130}
131
132/// A flattened line segment, as the rasteriser sees it.
133#[derive(Debug, Clone, Copy, PartialEq)]
134struct Edge {
135    /// x at `y_min`.
136    x0: f32,
137    y0: f32,
138    /// x at `y_max`.
139    x1: f32,
140    y1: f32,
141    /// The winding contribution: +1 when the original edge went down in y.
142    dir: i32,
143}
144
145impl Edge {
146    /// The lower y of the edge's active span.
147    const fn y_min(&self) -> f32 {
148        self.y0
149    }
150
151    /// The upper y of the edge's active span.
152    const fn y_max(&self) -> f32 {
153        self.y1
154    }
155
156    /// x at height `y`, which must lie within the edge's span.
157    fn x_at(&self, y: f32) -> f32 {
158        let dy = self.y1 - self.y0;
159        if dy == 0.0 {
160            self.x0
161        } else {
162            self.x0 + (self.x1 - self.x0) * (y - self.y0) / dy
163        }
164    }
165}
166
167/// Flatten a path into edges, dropping horizontal and non-finite segments.
168fn collect_edges(path: &Path2D) -> Vec<Edge> {
169    let polys = path.flatten(FILL_TOLERANCE);
170    let mut out = Vec::new();
171    for poly in polys {
172        for pair in poly.windows(2) {
173            let (Some(a), Some(b)) = (pair.first(), pair.get(1)) else {
174                continue;
175            };
176            if !a.0.is_finite() || !a.1.is_finite() || !b.0.is_finite() || !b.1.is_finite() {
177                continue;
178            }
179            // A horizontal edge bounds no area, and the half-open row rule
180            // handles the rest.
181            if (a.1 - b.1).abs() < 1e-12 {
182                continue;
183            }
184            let dir = if b.1 > a.1 { 1 } else { -1 };
185            let (lo, hi) = if dir > 0 { (*a, *b) } else { (*b, *a) };
186            out.push(Edge {
187                x0: lo.0,
188                y0: lo.1,
189                x1: hi.0,
190                y1: hi.1,
191                dir,
192            });
193        }
194    }
195    out
196}
197
198/// The per-pixel coverage of a set of edges.
199fn rasterize(edges: &[Edge], rule: FillRule, width: usize, height: usize) -> Vec<u8> {
200    let mut out = vec![0u8; width.saturating_mul(height)];
201    // Bucket edges by the first pixel row they touch, so each row only walks
202    // its own edges.
203    let mut rows: Vec<Vec<usize>> = vec![Vec::new(); height];
204    for (i, e) in edges.iter().enumerate() {
205        let first = floor_to_i32(e.y_min());
206        let last = ceil_to_i32(e.y_max());
207        let mut r = first.max(0);
208        while r < last.min(height as i32) {
209            if let Some(bucket) = rows.get_mut(r as usize) {
210                bucket.push(i);
211            }
212            r += 1;
213        }
214    }
215    for (y, bucket) in rows.iter().enumerate() {
216        if bucket.is_empty() {
217            continue;
218        }
219        let row_edges: Vec<Edge> = bucket
220            .iter()
221            .filter_map(|i| edges.get(*i).copied())
222            .collect();
223        rasterize_row(&mut out, &row_edges, rule, y, width);
224    }
225    out
226}
227
228/// Fill one pixel row, splitting it into bands where the edge set is stable.
229///
230/// The naive approach — order the row's edges once and integrate each span
231/// from the row's top to its bottom — is wrong for a curve. A circle's top arc
232/// crosses a row several times, so the edge that is "left" at the row's top is
233/// not the edge that is left at its bottom, and clamping a span to one edge's
234/// y range throws away most of the row's ink.
235///
236/// Splitting the row at every active edge's endpoints makes each band's edge
237/// set fixed, and within a band the x-ordering cannot change (two straight
238/// edges that swap order would have to cross, and a crossing inside a band
239/// would have been a split point). Ordering by the band's midline is then
240/// exact for that band.
241fn rasterize_row(out: &mut [u8], row_edges: &[Edge], rule: FillRule, y: usize, width: usize) {
242    let row_top = y as f32;
243    let row_bottom = row_top + 1.0;
244
245    // Band breakpoints: the row's edges, plus every place one of them starts
246    // or stops.
247    let mut breaks: Vec<f32> = vec![row_top, row_bottom];
248    for e in row_edges {
249        for v in [e.y_min(), e.y_max()] {
250            if v > row_top && v < row_bottom {
251                breaks.push(v);
252            }
253        }
254    }
255    breaks.sort_by(|a, b| a.partial_cmp(b).unwrap_or(core::cmp::Ordering::Equal));
256    breaks.dedup_by(|a, b| (*a - *b).abs() < f32::EPSILON);
257
258    for w in breaks.windows(2) {
259        let (Some(&t0), Some(&t1)) = (w.first(), w.get(1)) else {
260            continue;
261        };
262        if t1 <= t0 {
263            continue;
264        }
265        let midline = (t0 + t1) * 0.5;
266        let active: Vec<Edge> = row_edges
267            .iter()
268            .copied()
269            .filter(|e| e.y_min() <= midline && midline <= e.y_max())
270            .collect();
271        if active.is_empty() {
272            continue;
273        }
274        for (left, right) in inside_spans(&active, rule, midline) {
275            add_band(out, &(left, right), t0, t1, y, width);
276        }
277    }
278}
279
280/// The inside spans of one pixel row: `(left edge, right edge)` pairs.
281///
282/// `midline` is the y at which the edges are ordered. Ordering by any value
283/// that is constant across the row's edges — their own midpoints, say — gets
284/// curved rows wrong: two edges of a circle that meet at the row's top can be
285/// the wrong way round by the bottom. The midline is inside the row, so its
286/// ordering is the ordering that holds.
287fn inside_spans(row_edges: &[Edge], rule: FillRule, midline: f32) -> Vec<(Edge, Edge)> {
288    let mut active: Vec<Edge> = row_edges.to_vec();
289    active.sort_by(|a, b| {
290        a.x_at(midline)
291            .partial_cmp(&b.x_at(midline))
292            .unwrap_or(core::cmp::Ordering::Equal)
293            .then(a.dir.cmp(&b.dir))
294    });
295    let mut out = Vec::new();
296    let mut winding = 0i32;
297    let mut parity = 0u32;
298    // The left edge of the span currently being built.
299    let mut open: Option<Edge> = None;
300    for e in active {
301        let was_inside = match rule {
302            FillRule::NonZero => winding != 0,
303            FillRule::EvenOdd => parity % 2 == 1,
304        };
305        match rule {
306            FillRule::NonZero => winding += e.dir,
307            FillRule::EvenOdd => parity = parity.wrapping_add(1),
308        }
309        let is_inside = match rule {
310            FillRule::NonZero => winding != 0,
311            FillRule::EvenOdd => parity % 2 == 1,
312        };
313        match (was_inside, is_inside) {
314            (false, true) => open = Some(e),
315            (true, false) => {
316                if let Some(left) = open.take() {
317                    out.push((left, e));
318                }
319            }
320            _ => {}
321        }
322    }
323    out
324}
325
326/// Add one span's exact area to the mask, over the y band `[ya, yb)`.
327fn add_band(out: &mut [u8], span: &(Edge, Edge), ya: f32, yb: f32, y: usize, width: usize) {
328    let (left, right) = span;
329    if yb <= ya {
330        return;
331    }
332    // The span's x extent at the ends of the band bounds the columns it can
333    // touch. Using the midpoint x would clip a slanted band short, so the
334    // bounds are the min and max over the band.
335    let lx0 = left.x_at(ya);
336    let lx1 = left.x_at(yb);
337    let rx0 = right.x_at(ya);
338    let rx1 = right.x_at(yb);
339    let min_x = lx0.min(lx1).min(rx0.min(rx1));
340    let max_x = lx0.max(lx1).max(rx0.max(rx1));
341    let first = floor_to_i32(min_x);
342    let last = ceil_to_i32(max_x);
343    let mut cx = first.max(0);
344    while cx < last {
345        let col = cx as f32;
346        let area = span_column_area(left, right, ya, yb, col);
347        if area > 0.0 {
348            // `libm::roundf` rather than `f32::round`: `round` and `clamp` are
349            // `std` methods on floats and this crate is `no_std`. So the
350            // saturating `max`/`min` stands in for `clamp`, which would also
351            // panic on a NaN bound — and a NaN area can reach here.
352            #[allow(clippy::manual_clamp)]
353            let cov = libm::roundf(area * 255.0).max(0.0).min(255.0) as u32;
354            let v = cov.min(255) as u8;
355            let idx = y.saturating_mul(width).saturating_add(cx as usize);
356            if let Some(slot) = out.get_mut(idx) {
357                // A row is filled band by band, so bands accumulate rather
358                // than overwrite. Saturating, because the bands are disjoint
359                // in y and cannot exceed full coverage.
360                *slot = slot.saturating_add(v);
361            }
362        }
363        cx += 1;
364    }
365}
366
367/// The exact area a span covers in column `[cx, cx+1)` over `y ∈ [ya, yb)`.
368///
369/// The integrand is
370/// `clamp(min(lx(y), rx(y), cx+1) − max(lx(y), rx(y), cx), 0, 1)`, which is
371/// piecewise linear in `y` with breakpoints wherever an edge crosses `cx` or
372/// `cx+1`. Splitting at those breakpoints and summing trapezoids is exact.
373fn span_column_area(left: &Edge, right: &Edge, ya: f32, yb: f32, cx: f32) -> f32 {
374    let mut breaks = vec![ya, yb];
375    for e in [left, right] {
376        for edge_x in [cx, cx + 1.0] {
377            if let Some(t) = edge_crosses_at(e, edge_x, ya, yb) {
378                breaks.push(t);
379            }
380        }
381    }
382    breaks.sort_by(|a, b| a.partial_cmp(b).unwrap_or(core::cmp::Ordering::Equal));
383    let mut total = 0.0f32;
384    for w in breaks.windows(2) {
385        let (Some(t0), Some(t1)) = (w.first(), w.get(1)) else {
386            continue;
387        };
388        if *t1 <= *t0 {
389            continue;
390        }
391        let f0 = span_fraction(left, right, *t0, cx);
392        let f1 = span_fraction(left, right, *t1, cx);
393        total += (f0 + f1) * 0.5 * (t1 - t0);
394    }
395    total
396}
397
398/// The height at which `edge` crosses `x`, if it does within `[ya, yb)`.
399fn edge_crosses_at(edge: &Edge, x: f32, ya: f32, yb: f32) -> Option<f32> {
400    let a = edge.x_at(ya);
401    let b = edge.x_at(yb);
402    if (a - x) * (b - x) > 0.0 || a == b {
403        return None;
404    }
405    let dx = b - a;
406    if dx == 0.0 {
407        return None;
408    }
409    let t = ya + (x - a) / dx * (yb - ya);
410    if t > ya && t < yb {
411        Some(t)
412    } else {
413        None
414    }
415}
416
417/// The span's horizontal overlap with `[cx, cx+1)` at height `y`, in `0..=1`.
418fn span_fraction(left: &Edge, right: &Edge, y: f32, cx: f32) -> f32 {
419    let a = left.x_at(y);
420    let b = right.x_at(y);
421    // A span is between its two edges; if the polygon self-crosses the two
422    // can swap order mid-row, so sort before taking the ends.
423    let (lo_edge, hi_edge) = if a <= b { (a, b) } else { (b, a) };
424    let lo = lo_edge.max(cx);
425    let hi = hi_edge.min(cx + 1.0);
426    // `.max`/`.min` rather than `clamp`: `clamp` panics on a NaN bound, and a
427    // NaN coordinate can reach here.
428    #[allow(clippy::manual_clamp)] // `clamp` panics on a NaN bound; a NaN can reach here.
429    let frac = (hi - lo).max(0.0).min(1.0);
430    frac
431}
432
433/// `floor` as an `i32`, saturating at the type's bounds.
434fn floor_to_i32(v: f32) -> i32 {
435    if v.is_nan() {
436        return 0;
437    }
438    if v <= i32::MIN as f32 {
439        return i32::MIN;
440    }
441    if v >= i32::MAX as f32 {
442        return i32::MAX;
443    }
444    libm::floorf(v) as i32
445}
446
447/// `ceil` as an `i32`, saturating at the type's bounds.
448fn ceil_to_i32(v: f32) -> i32 {
449    if v.is_nan() {
450        return 0;
451    }
452    if v <= i32::MIN as f32 {
453        return i32::MIN;
454    }
455    if v >= i32::MAX as f32 {
456        return i32::MAX;
457    }
458    libm::ceilf(v) as i32
459}
460
461/// The tight pixel bounds a path occupies in a raster of the given size, or
462/// `None` when it covers nothing.
463///
464/// Used by [`GlyphBitmap`] placement](crate::GlyphBitmap) and by the tests
465/// that check a mask against its geometry.
466#[must_use]
467pub fn path_pixel_bounds(path: &Path2D, width: u32, height: u32) -> Option<(i32, i32, i32, i32)> {
468    let bbox = path.bbox()?;
469    if bbox.is_empty() {
470        return None;
471    }
472    let x0 = floor_to_i32(bbox.min_x).max(0);
473    let y0 = floor_to_i32(bbox.min_y).max(0);
474    let x1 = ceil_to_i32(bbox.max_x).min(width as i32);
475    let y1 = ceil_to_i32(bbox.max_y).min(height as i32);
476    if x1 <= x0 || y1 <= y0 {
477        return None;
478    }
479    Some((x0, y0, x1 - x0, y1 - y0))
480}
481
482#[cfg(test)]
483mod tests {
484    #![allow(
485        clippy::unwrap_used,
486        clippy::expect_used,
487        clippy::panic,
488        clippy::indexing_slicing,
489        clippy::float_cmp
490    )]
491    use super::{
492        collect_edges, fill_path, mask_coverage, path_pixel_bounds, Edge, FillRule,
493        MAX_MASK_ELEMENTS,
494    };
495    use crate::path::PathBuilder;
496    use crate::ShapeError;
497
498    // Test harness: assertions legitimately panic; the lib target stays
499    // lint-clean.
500
501    /// The total ink of a mask, in pixels.
502    fn ink(mask: &[u8]) -> f64 {
503        mask_coverage(mask) / 255.0
504    }
505
506    fn close(a: f32, b: f32) -> bool {
507        (a - b).abs() < 1e-4
508    }
509
510    fn rect(x: f32, y: f32, w: f32, h: f32) -> crate::Path2D {
511        let mut b = PathBuilder::new();
512        b.rect(x, y, w, h);
513        b.build()
514    }
515
516    fn donut(outer: f32, inner: f32) -> crate::Path2D {
517        // Two concentric circles wound the *same* way: the case that
518        // distinguishes the rules.
519        let mut b = PathBuilder::new();
520        b.circle(50.0, 50.0, outer);
521        b.circle(50.0, 50.0, inner);
522        b.build()
523    }
524
525    #[test]
526    fn axis_aligned_rectangle_at_integer_offsets_is_exact() {
527        let mask = fill_path(&rect(4.0, 4.0, 8.0, 8.0), FillRule::NonZero, 16, 16).expect("fills");
528        for y in 4..12 {
529            for x in 4..12 {
530                assert_eq!(mask[y * 16 + x], 255, "({x}, {y}) should be solid");
531            }
532        }
533        // Nothing outside the 8x8 block has any ink.
534        assert_eq!(ink(&mask), 64.0, "exactly 64 pixels of ink");
535    }
536
537    #[test]
538    fn half_pixel_offsets_give_exact_half_coverage() {
539        // A rectangle from 4.5 to 8.5 horizontally: each edge column is half
540        // covered, and analytically that is exactly 128.
541        let mask = fill_path(&rect(4.5, 4.0, 4.0, 8.0), FillRule::NonZero, 16, 16).expect("fills");
542        for y in 4..12 {
543            assert_eq!(mask[y * 16 + 4], 128, "left edge at y={y}");
544            assert_eq!(mask[y * 16 + 5], 255, "interior at y={y}");
545            assert_eq!(mask[y * 16 + 6], 255, "interior at y={y}");
546            assert_eq!(mask[y * 16 + 7], 255, "interior at y={y}");
547            assert_eq!(mask[y * 16 + 8], 128, "right edge at y={y}");
548        }
549        // 4 pixels of ink per row: 0.5 + 3 + 0.5. The half edges are quantised
550        // to 128, which is 0.50196 of a pixel rather than 0.5, so the total
551        // carries 16 half-quantisation steps of slack.
552        assert!((ink(&mask) - 32.0).abs() < 0.04, "ink {}", ink(&mask));
553    }
554
555    #[test]
556    fn quarter_pixel_offsets_are_exact_too() {
557        // 4.25 to 7.75 is 3.5 wide: columns 4 and 7 each hold three quarters, with
558        // two solid columns between.
559        let mask = fill_path(&rect(4.25, 0.0, 3.5, 4.0), FillRule::NonZero, 12, 4).expect("fills");
560        assert_eq!(mask[4], 191, "three quarters of 255 rounds to 191");
561        assert_eq!(mask[5], 255, "solid interior");
562        assert_eq!(mask[6], 255, "solid interior");
563        assert_eq!(mask[7], 191, "three quarters again");
564        assert_eq!(mask[3], 0, "outside the left edge");
565        assert_eq!(mask[8], 0, "outside the right edge");
566        // 3.5 px of ink per row, 4 rows.
567        assert!((ink(&mask) - 14.0).abs() < 0.02, "ink {}", ink(&mask));
568    }
569
570    #[test]
571    fn nonzero_and_even_odd_differ_on_a_same_wound_donut() {
572        let path = donut(40.0, 18.0);
573        let nz = fill_path(&path, FillRule::NonZero, 100, 100).expect("fills");
574        let eo = fill_path(&path, FillRule::EvenOdd, 100, 100).expect("fills");
575        // Non-zero: the whole disc is ink (the two contours agree in
576        // direction, so the winding never returns to zero).
577        assert_eq!(nz[50 * 100 + 50], 255, "the centre is ink under non-zero");
578        assert!(ink(&nz) > 1000.0, "non-zero ink {}", ink(&nz));
579        // Even-odd: the inner contour punches a hole.
580        assert_eq!(eo[50 * 100 + 50], 0, "the centre is a hole under even-odd");
581        assert!(
582            ink(&eo) < ink(&nz) * 0.9,
583            "even-odd {} vs non-zero {}",
584            ink(&eo),
585            ink(&nz)
586        );
587        // The hole really is a hole: a ring of ink around an empty centre.
588        assert_eq!(eo[50 * 100 + 50], 0, "the middle row's centre is a hole");
589        // The ring at the outer edge is ink, though the flattened circle's
590        // chord sits a hair inside the true circle, so it is 253 not 255.
591        assert!(
592            eo[50 * 100 + 10] > 250,
593            "the ring around the hole is ink: {}",
594            eo[50 * 100 + 10]
595        );
596        // Row 10 is above the inner circle but still inside the outer one: ink, and
597        // the flattened chord sits a hair inside, so 254 rather than 255.
598        assert!(
599            eo[10 * 100 + 50] > 250,
600            "above the hole: {}",
601            eo[10 * 100 + 50]
602        );
603        // The very centre of the raster is deep inside the ring on both rules.
604        assert_eq!(nz[50 * 100 + 50], 255, "non-zero fills the middle");
605        assert_eq!(eo[50 * 100 + 50], 0, "even-odd punches it out");
606    }
607
608    #[test]
609    fn opposite_wound_donut_is_a_hole_under_both_rules() {
610        // An outer circle one way, an inner circle the other: the classic
611        // counter, where both rules agree the middle is a hole.
612        //
613        // `Path2D::reverse` flips *every* subpath, so the inner contour is
614        // built and reversed on its own before being appended.
615        let mut outer_builder = PathBuilder::new();
616        outer_builder.circle(50.0, 50.0, 40.0);
617        let outer = outer_builder.build();
618
619        let mut inner_builder = PathBuilder::new();
620        inner_builder.circle(50.0, 50.0, 18.0);
621        let mut inner = inner_builder.build();
622        inner.reverse();
623
624        let mut b = PathBuilder::new();
625        b.extend(&outer);
626        b.extend(&inner);
627        let path = b.build();
628
629        for rule in [FillRule::NonZero, FillRule::EvenOdd] {
630            let mask = fill_path(&path, rule, 100, 100).expect("fills");
631            assert_eq!(mask[50 * 100 + 50], 0, "hole under {rule:?}");
632            assert!(
633                mask[50 * 100 + 10] > 250,
634                "the ring is ink under {rule:?}: {}",
635                mask[50 * 100 + 10]
636            );
637            // A point well inside the ring, clear of the flattened circle's
638            // edge, is solid.
639            assert!(
640                mask[10 * 100 + 50] > 250,
641                "solid ring under {rule:?}: {}",
642                mask[10 * 100 + 50]
643            );
644        }
645    }
646
647    #[test]
648    fn self_intersecting_star_differs_between_the_rules() {
649        // A five-pointed star drawn as one self-intersecting contour: the
650        // middle pentagon is wound twice, so non-zero fills it and even-odd
651        // punches it out. This is the case that separates the rules.
652        let pts = [
653            (50.0, 10.0),
654            (19.0, 90.0),
655            (90.0, 38.0),
656            (10.0, 38.0),
657            (81.0, 90.0),
658        ];
659        let mut b = PathBuilder::new();
660        for (i, p) in pts.iter().enumerate() {
661            if i == 0 {
662                b.move_to(p.0, p.1);
663            } else {
664                b.line_to(p.0, p.1);
665            }
666        }
667        b.close();
668        let path = b.build();
669
670        let nz = fill_path(&path, FillRule::NonZero, 100, 100).expect("fills");
671        let eo = fill_path(&path, FillRule::EvenOdd, 100, 100).expect("fills");
672        // The doubly-wound centre: ink under non-zero, a hole under even-odd.
673        assert_eq!(nz[50 * 100 + 50], 255, "non-zero keeps the centre");
674        assert_eq!(eo[50 * 100 + 50], 0, "even-odd empties the centre");
675        // Both rules agree on a point in a single-wound arm.
676        assert_eq!(nz[32 * 100 + 50], 255, "single-wound arm");
677        assert_eq!(eo[32 * 100 + 50], 255, "single-wound arm");
678        // And the empty corner outside the star.
679        assert_eq!(nz[50 * 100 + 5], 0);
680        assert_eq!(eo[50 * 100 + 5], 0);
681        // The two rules really do differ by the pentagon.
682        assert!(
683            ink(&nz) - ink(&eo) > 100.0,
684            "non-zero {} vs even-odd {}",
685            ink(&nz),
686            ink(&eo)
687        );
688    }
689
690    #[test]
691    fn degenerate_paths_produce_no_panic_and_no_ink() {
692        let empty = crate::Path2D::new();
693        let mask = fill_path(&empty, FillRule::NonZero, 8, 8).expect("fills");
694        assert!(mask.iter().all(|&v| v == 0));
695
696        // A lone point.
697        let mut b = PathBuilder::new();
698        b.move_to(4.0, 4.0);
699        let mask = fill_path(&b.build(), FillRule::NonZero, 8, 8).expect("fills");
700        assert_eq!(ink(&mask), 0.0);
701
702        // A zero-length line.
703        let mut b = PathBuilder::new();
704        b.move_to(4.0, 4.0);
705        b.line_to(4.0, 4.0);
706        b.close();
707        let mask = fill_path(&b.build(), FillRule::NonZero, 8, 8).expect("fills");
708        assert_eq!(ink(&mask), 0.0);
709
710        // A zero-area contour: a degenerate polygon.
711        let mut b = PathBuilder::new();
712        b.move_to(1.0, 1.0);
713        b.line_to(5.0, 1.0);
714        b.line_to(3.0, 1.0);
715        b.close();
716        let mask = fill_path(&b.build(), FillRule::NonZero, 8, 8).expect("fills");
717        assert!(
718            ink(&mask) < 0.01,
719            "a flat contour has no area: {}",
720            ink(&mask)
721        );
722
723        // A self-cancelling outline: a shape drawn forwards then backwards.
724        let mut b = PathBuilder::new();
725        b.rect(1.0, 1.0, 4.0, 4.0);
726        b.rect(1.0, 1.0, 4.0, 4.0);
727        let mask = fill_path(&b.build(), FillRule::NonZero, 8, 8).expect("fills");
728        assert!((ink(&mask) - 16.0).abs() < 0.01, "overlap still fills");
729    }
730
731    #[test]
732    fn triangle_coverage_sums_to_its_area() {
733        // A right triangle with legs 64: area = 2048. The mask's total ink must
734        // match within 0.1 %, which is the bound the analytic filler earns.
735        let mut b = PathBuilder::new();
736        b.move_to(0.0, 0.0);
737        b.line_to(64.0, 0.0);
738        b.line_to(0.0, 64.0);
739        b.close();
740        let path = b.build();
741        let mask = fill_path(&path, FillRule::NonZero, 64, 64).expect("fills");
742        let total = ink(&mask);
743        let exact = 0.5 * 64.0 * 64.0;
744        let err = (total - exact).abs() / exact;
745        assert!(
746            err < 0.001,
747            "triangle ink {total} vs area {exact}: relative error {err}"
748        );
749        // A tilted triangle: the same bound with diagonal edges, where a
750        // supersampling rasteriser would drift.
751        let mut t = PathBuilder::new();
752        t.move_to(10.0, 10.0);
753        t.line_to(90.0, 20.0);
754        t.line_to(30.0, 90.0);
755        t.close();
756        let mask = fill_path(&t.build(), FillRule::NonZero, 100, 100).expect("fills");
757        // Shoelace of the exact triangle, summed in `f64` from `f32` vertices.
758        let pts = [(10.0f32, 10.0f32), (90.0, 20.0), (30.0, 90.0)];
759        let mut acc = 0.0f64;
760        for (i, a) in pts.iter().enumerate() {
761            let b = pts[(i + 1) % 3];
762            acc += f64::from(a.0) * f64::from(b.1) - f64::from(b.0) * f64::from(a.1);
763        }
764        let exact = (acc * 0.5).abs();
765        let err = (ink(&mask) - exact).abs() / exact;
766        assert!(err < 0.002, "tilted triangle error {err}");
767    }
768
769    #[test]
770    fn circle_coverage_sums_to_its_area() {
771        // A radius-40 circle: area = pi·1600 ≈ 5026.5. The flattening tolerance
772        // bounds the error, so 1 % is generous.
773        let mut b = PathBuilder::new();
774        b.circle(50.0, 50.0, 40.0);
775        let mask = fill_path(&b.build(), FillRule::NonZero, 100, 100).expect("fills");
776        let want = core::f64::consts::PI * 1600.0;
777        let err = (ink(&mask) - want).abs() / want;
778        assert!(err < 0.01, "circle ink error {err}");
779    }
780
781    #[test]
782    fn zero_sized_raster_is_empty() {
783        let p = rect(0.0, 0.0, 4.0, 4.0);
784        assert!(fill_path(&p, FillRule::NonZero, 0, 8)
785            .expect("fills")
786            .is_empty());
787        assert!(fill_path(&p, FillRule::NonZero, 8, 0)
788            .expect("fills")
789            .is_empty());
790        assert!(fill_path(&p, FillRule::NonZero, 0, 0)
791            .expect("fills")
792            .is_empty());
793    }
794
795    #[test]
796    fn oversized_raster_is_refused() {
797        let p = rect(0.0, 0.0, 1.0, 1.0);
798        match fill_path(&p, FillRule::NonZero, 100_000, 100_000).unwrap_err() {
799            ShapeError::RasterTooLarge { pixels, limit } => {
800                assert_eq!(pixels, 10_000_000_000);
801                assert_eq!(limit, MAX_MASK_ELEMENTS);
802            }
803            other => panic!("expected RasterTooLarge, got {other:?}"),
804        }
805        // And the message names the numbers.
806        let msg = alloc::format!(
807            "{}",
808            ShapeError::RasterTooLarge {
809                pixels: 10_000_000_000,
810                limit: MAX_MASK_ELEMENTS
811            }
812        );
813        assert!(msg.contains("10000000000"));
814    }
815
816    #[test]
817    fn geometry_entirely_outside_the_raster_is_empty() {
818        let p = rect(100.0, 100.0, 10.0, 10.0);
819        let mask = fill_path(&p, FillRule::NonZero, 8, 8).expect("fills");
820        assert_eq!(ink(&mask), 0.0);
821        // And partly outside is clipped, not wrapped.
822        let p = rect(-4.0, -4.0, 8.0, 8.0);
823        let mask = fill_path(&p, FillRule::NonZero, 8, 8).expect("fills");
824        assert!((ink(&mask) - 16.0).abs() < 0.01, "clipped to a quarter");
825    }
826
827    #[test]
828    fn collect_edges_drops_horizontal_and_non_finite_segments() {
829        // A horizontal-only path has no edges at all.
830        let mut b = PathBuilder::new();
831        b.move_to(0.0, 5.0);
832        b.line_to(10.0, 5.0);
833        b.close();
834        assert!(collect_edges(&b.build()).is_empty());
835
836        // A NaN segment is dropped, and the good one survives.
837        let mut b = PathBuilder::new();
838        b.move_to(0.0, 0.0);
839        b.line_to(f32::NAN, 10.0);
840        b.line_to(10.0, 20.0);
841        b.close();
842        let edges = collect_edges(&b.build());
843        assert_eq!(edges.len(), 1, "one usable edge");
844        assert!(edges[0].x0.is_finite() && edges[0].x1.is_finite());
845    }
846
847    #[test]
848    fn edges_report_their_direction() {
849        let down = Edge {
850            x0: 0.0,
851            y0: 0.0,
852            x1: 1.0,
853            y1: 4.0,
854            dir: 1,
855        };
856        assert_eq!(down.y_min(), 0.0);
857        assert_eq!(down.y_max(), 4.0);
858        assert!(close(down.x_at(0.0), 0.0));
859        assert!(close(down.x_at(2.0), 0.5));
860        assert!(close(down.x_at(4.0), 1.0));
861        // A degenerate edge with no vertical extent evaluates to x0.
862        let flat = Edge {
863            x0: 3.0,
864            y0: 1.0,
865            x1: 3.0,
866            y1: 1.0,
867            dir: 1,
868        };
869        assert!(close(flat.x_at(1.0), 3.0));
870    }
871
872    #[test]
873    fn fill_rule_default_is_non_zero() {
874        assert_eq!(FillRule::default(), FillRule::NonZero);
875    }
876
877    #[test]
878    fn transform_of_a_path_matches_its_mask_bounds() {
879        // Fill a rectangle, then a transformed copy: the ink is the same
880        // because a transform of a path is a transform of its coverage.
881        let p = rect(20.0, 30.0, 20.0, 10.0);
882        let a = fill_path(&p, FillRule::NonZero, 64, 64).expect("fills");
883        let t = p.transformed(&crate::Affine2D::translate(4.0, -6.0));
884        let b = fill_path(&t, FillRule::NonZero, 64, 64).expect("fills");
885        assert!(
886            (ink(&a) - ink(&b)).abs() < 0.5,
887            "{} vs {}",
888            ink(&a),
889            ink(&b)
890        );
891        // A uniform scale by 2 quadruples the area.
892        let big = p.transformed(&crate::Affine2D::scale(2.0, 2.0));
893        let c = fill_path(&big, FillRule::NonZero, 128, 128).expect("fills");
894        assert!(
895            (ink(&c) - ink(&a) * 4.0).abs() < 1.0,
896            "{} vs {}",
897            ink(&c),
898            ink(&a) * 4.0
899        );
900    }
901
902    #[test]
903    fn pixel_bounds_of_a_path() {
904        let p = rect(4.25, 6.75, 10.0, 5.0);
905        assert_eq!(path_pixel_bounds(&p, 64, 64), Some((4, 6, 11, 6)));
906        // Clipped to the raster.
907        assert_eq!(path_pixel_bounds(&p, 8, 8), Some((4, 6, 4, 2)));
908        // Nothing at all when off-raster.
909        assert_eq!(path_pixel_bounds(&rect(100.0, 100.0, 1.0, 1.0), 8, 8), None);
910        // And an empty path has no bounds.
911        assert_eq!(path_pixel_bounds(&crate::Path2D::new(), 8, 8), None);
912    }
913
914    #[test]
915    fn mask_values_are_always_in_range() {
916        // A wild path: a star, several overlapping shapes, and a curve.
917        let mut b = PathBuilder::new();
918        b.circle(32.0, 32.0, 30.0);
919        for i in 0..7 {
920            let a = i as f32 * 0.9;
921            b.move_to(32.0, 32.0);
922            b.line_to(32.0 + 25.0 * libm::cosf(a), 32.0 + 25.0 * libm::sinf(a));
923        }
924        b.rect(0.0, 0.0, 64.0, 64.0);
925        for rule in [FillRule::NonZero, FillRule::EvenOdd] {
926            let mask = fill_path(&b.build(), rule, 64, 64).expect("fills");
927            assert_eq!(mask.len(), 64 * 64);
928            // Every pixel is a valid coverage byte — the type says so — and
929            // the total ink cannot exceed the frame it covers.
930            assert!(ink(&mask) <= 64.0 * 64.0 + 1e-6);
931            assert!(ink(&mask) > 0.0, "the star and the frame both draw");
932        }
933    }
934}