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    // Clamp the walk to the mask itself. Hostile-extent geometry (±1e30 spans
343    // are legal input — nothing bounds a caller's coordinates) saturates
344    // `last` at `i32::MAX`, and an unclamped walk is a billion-iteration
345    // silent hang — found by font-conformance case `huge_extent_polygon`:
346    // fill never returned. The write below is already bounded by `get_mut`;
347    // the walk must be bounded too. (`width` ≤ MAX_MASK_ELEMENTS by the
348    // `fill_path` entry check, far under `i32::MAX`.)
349    let last = ceil_to_i32(max_x).min(width as i32);
350    let mut cx = first.max(0);
351    while cx < last {
352        let col = cx as f32;
353        let area = span_column_area(left, right, ya, yb, col);
354        if area > 0.0 {
355            // `libm::roundf` rather than `f32::round`: `round` and `clamp` are
356            // `std` methods on floats and this crate is `no_std`. So the
357            // saturating `max`/`min` stands in for `clamp`, which would also
358            // panic on a NaN bound — and a NaN area can reach here.
359            #[allow(clippy::manual_clamp)]
360            let cov = libm::roundf(area * 255.0).max(0.0).min(255.0) as u32;
361            let v = cov.min(255) as u8;
362            let idx = y.saturating_mul(width).saturating_add(cx as usize);
363            if let Some(slot) = out.get_mut(idx) {
364                // A row is filled band by band, so bands accumulate rather
365                // than overwrite. Saturating, because the bands are disjoint
366                // in y and cannot exceed full coverage.
367                *slot = slot.saturating_add(v);
368            }
369        }
370        cx += 1;
371    }
372}
373
374/// The exact area a span covers in column `[cx, cx+1)` over `y ∈ [ya, yb)`.
375///
376/// The integrand is
377/// `clamp(min(lx(y), rx(y), cx+1) − max(lx(y), rx(y), cx), 0, 1)`, which is
378/// piecewise linear in `y` with breakpoints wherever an edge crosses `cx` or
379/// `cx+1`. Splitting at those breakpoints and summing trapezoids is exact.
380fn span_column_area(left: &Edge, right: &Edge, ya: f32, yb: f32, cx: f32) -> f32 {
381    let mut breaks = vec![ya, yb];
382    for e in [left, right] {
383        for edge_x in [cx, cx + 1.0] {
384            if let Some(t) = edge_crosses_at(e, edge_x, ya, yb) {
385                breaks.push(t);
386            }
387        }
388    }
389    breaks.sort_by(|a, b| a.partial_cmp(b).unwrap_or(core::cmp::Ordering::Equal));
390    let mut total = 0.0f32;
391    for w in breaks.windows(2) {
392        let (Some(t0), Some(t1)) = (w.first(), w.get(1)) else {
393            continue;
394        };
395        if *t1 <= *t0 {
396            continue;
397        }
398        let f0 = span_fraction(left, right, *t0, cx);
399        let f1 = span_fraction(left, right, *t1, cx);
400        total += (f0 + f1) * 0.5 * (t1 - t0);
401    }
402    total
403}
404
405/// The height at which `edge` crosses `x`, if it does within `[ya, yb)`.
406fn edge_crosses_at(edge: &Edge, x: f32, ya: f32, yb: f32) -> Option<f32> {
407    let a = edge.x_at(ya);
408    let b = edge.x_at(yb);
409    if (a - x) * (b - x) > 0.0 || a == b {
410        return None;
411    }
412    let dx = b - a;
413    if dx == 0.0 {
414        return None;
415    }
416    let t = ya + (x - a) / dx * (yb - ya);
417    if t > ya && t < yb {
418        Some(t)
419    } else {
420        None
421    }
422}
423
424/// The span's horizontal overlap with `[cx, cx+1)` at height `y`, in `0..=1`.
425fn span_fraction(left: &Edge, right: &Edge, y: f32, cx: f32) -> f32 {
426    let a = left.x_at(y);
427    let b = right.x_at(y);
428    // A span is between its two edges; if the polygon self-crosses the two
429    // can swap order mid-row, so sort before taking the ends.
430    let (lo_edge, hi_edge) = if a <= b { (a, b) } else { (b, a) };
431    let lo = lo_edge.max(cx);
432    let hi = hi_edge.min(cx + 1.0);
433    // `.max`/`.min` rather than `clamp`: `clamp` panics on a NaN bound, and a
434    // NaN coordinate can reach here.
435    #[allow(clippy::manual_clamp)] // `clamp` panics on a NaN bound; a NaN can reach here.
436    let frac = (hi - lo).max(0.0).min(1.0);
437    frac
438}
439
440/// `floor` as an `i32`, saturating at the type's bounds.
441fn floor_to_i32(v: f32) -> i32 {
442    if v.is_nan() {
443        return 0;
444    }
445    if v <= i32::MIN as f32 {
446        return i32::MIN;
447    }
448    if v >= i32::MAX as f32 {
449        return i32::MAX;
450    }
451    libm::floorf(v) as i32
452}
453
454/// `ceil` as an `i32`, saturating at the type's bounds.
455fn ceil_to_i32(v: f32) -> i32 {
456    if v.is_nan() {
457        return 0;
458    }
459    if v <= i32::MIN as f32 {
460        return i32::MIN;
461    }
462    if v >= i32::MAX as f32 {
463        return i32::MAX;
464    }
465    libm::ceilf(v) as i32
466}
467
468/// The tight pixel bounds a path occupies in a raster of the given size, or
469/// `None` when it covers nothing.
470///
471/// Used by [`GlyphBitmap`] placement](crate::GlyphBitmap) and by the tests
472/// that check a mask against its geometry.
473#[must_use]
474pub fn path_pixel_bounds(path: &Path2D, width: u32, height: u32) -> Option<(i32, i32, i32, i32)> {
475    let bbox = path.bbox()?;
476    if bbox.is_empty() {
477        return None;
478    }
479    let x0 = floor_to_i32(bbox.min_x).max(0);
480    let y0 = floor_to_i32(bbox.min_y).max(0);
481    let x1 = ceil_to_i32(bbox.max_x).min(width as i32);
482    let y1 = ceil_to_i32(bbox.max_y).min(height as i32);
483    if x1 <= x0 || y1 <= y0 {
484        return None;
485    }
486    Some((x0, y0, x1 - x0, y1 - y0))
487}
488
489#[cfg(test)]
490mod tests {
491    #![allow(
492        clippy::unwrap_used,
493        clippy::expect_used,
494        clippy::panic,
495        clippy::indexing_slicing,
496        clippy::float_cmp
497    )]
498    use super::{
499        collect_edges, fill_path, mask_coverage, path_pixel_bounds, Edge, FillRule,
500        MAX_MASK_ELEMENTS,
501    };
502    use crate::path::PathBuilder;
503    use crate::ShapeError;
504
505    // Test harness: assertions legitimately panic; the lib target stays
506    // lint-clean.
507
508    /// The total ink of a mask, in pixels.
509    fn ink(mask: &[u8]) -> f64 {
510        mask_coverage(mask) / 255.0
511    }
512
513    fn close(a: f32, b: f32) -> bool {
514        (a - b).abs() < 1e-4
515    }
516
517    fn rect(x: f32, y: f32, w: f32, h: f32) -> crate::Path2D {
518        let mut b = PathBuilder::new();
519        b.rect(x, y, w, h);
520        b.build()
521    }
522
523    fn donut(outer: f32, inner: f32) -> crate::Path2D {
524        // Two concentric circles wound the *same* way: the case that
525        // distinguishes the rules.
526        let mut b = PathBuilder::new();
527        b.circle(50.0, 50.0, outer);
528        b.circle(50.0, 50.0, inner);
529        b.build()
530    }
531
532    #[test]
533    fn axis_aligned_rectangle_at_integer_offsets_is_exact() {
534        let mask = fill_path(&rect(4.0, 4.0, 8.0, 8.0), FillRule::NonZero, 16, 16).expect("fills");
535        for y in 4..12 {
536            for x in 4..12 {
537                assert_eq!(mask[y * 16 + x], 255, "({x}, {y}) should be solid");
538            }
539        }
540        // Nothing outside the 8x8 block has any ink.
541        assert_eq!(ink(&mask), 64.0, "exactly 64 pixels of ink");
542    }
543
544    #[test]
545    fn half_pixel_offsets_give_exact_half_coverage() {
546        // A rectangle from 4.5 to 8.5 horizontally: each edge column is half
547        // covered, and analytically that is exactly 128.
548        let mask = fill_path(&rect(4.5, 4.0, 4.0, 8.0), FillRule::NonZero, 16, 16).expect("fills");
549        for y in 4..12 {
550            assert_eq!(mask[y * 16 + 4], 128, "left edge at y={y}");
551            assert_eq!(mask[y * 16 + 5], 255, "interior at y={y}");
552            assert_eq!(mask[y * 16 + 6], 255, "interior at y={y}");
553            assert_eq!(mask[y * 16 + 7], 255, "interior at y={y}");
554            assert_eq!(mask[y * 16 + 8], 128, "right edge at y={y}");
555        }
556        // 4 pixels of ink per row: 0.5 + 3 + 0.5. The half edges are quantised
557        // to 128, which is 0.50196 of a pixel rather than 0.5, so the total
558        // carries 16 half-quantisation steps of slack.
559        assert!((ink(&mask) - 32.0).abs() < 0.04, "ink {}", ink(&mask));
560    }
561
562    #[test]
563    fn quarter_pixel_offsets_are_exact_too() {
564        // 4.25 to 7.75 is 3.5 wide: columns 4 and 7 each hold three quarters, with
565        // two solid columns between.
566        let mask = fill_path(&rect(4.25, 0.0, 3.5, 4.0), FillRule::NonZero, 12, 4).expect("fills");
567        assert_eq!(mask[4], 191, "three quarters of 255 rounds to 191");
568        assert_eq!(mask[5], 255, "solid interior");
569        assert_eq!(mask[6], 255, "solid interior");
570        assert_eq!(mask[7], 191, "three quarters again");
571        assert_eq!(mask[3], 0, "outside the left edge");
572        assert_eq!(mask[8], 0, "outside the right edge");
573        // 3.5 px of ink per row, 4 rows.
574        assert!((ink(&mask) - 14.0).abs() < 0.02, "ink {}", ink(&mask));
575    }
576
577    #[test]
578    fn nonzero_and_even_odd_differ_on_a_same_wound_donut() {
579        let path = donut(40.0, 18.0);
580        let nz = fill_path(&path, FillRule::NonZero, 100, 100).expect("fills");
581        let eo = fill_path(&path, FillRule::EvenOdd, 100, 100).expect("fills");
582        // Non-zero: the whole disc is ink (the two contours agree in
583        // direction, so the winding never returns to zero).
584        assert_eq!(nz[50 * 100 + 50], 255, "the centre is ink under non-zero");
585        assert!(ink(&nz) > 1000.0, "non-zero ink {}", ink(&nz));
586        // Even-odd: the inner contour punches a hole.
587        assert_eq!(eo[50 * 100 + 50], 0, "the centre is a hole under even-odd");
588        assert!(
589            ink(&eo) < ink(&nz) * 0.9,
590            "even-odd {} vs non-zero {}",
591            ink(&eo),
592            ink(&nz)
593        );
594        // The hole really is a hole: a ring of ink around an empty centre.
595        assert_eq!(eo[50 * 100 + 50], 0, "the middle row's centre is a hole");
596        // The ring at the outer edge is ink, though the flattened circle's
597        // chord sits a hair inside the true circle, so it is 253 not 255.
598        assert!(
599            eo[50 * 100 + 10] > 250,
600            "the ring around the hole is ink: {}",
601            eo[50 * 100 + 10]
602        );
603        // Row 10 is above the inner circle but still inside the outer one: ink, and
604        // the flattened chord sits a hair inside, so 254 rather than 255.
605        assert!(
606            eo[10 * 100 + 50] > 250,
607            "above the hole: {}",
608            eo[10 * 100 + 50]
609        );
610        // The very centre of the raster is deep inside the ring on both rules.
611        assert_eq!(nz[50 * 100 + 50], 255, "non-zero fills the middle");
612        assert_eq!(eo[50 * 100 + 50], 0, "even-odd punches it out");
613    }
614
615    #[test]
616    fn opposite_wound_donut_is_a_hole_under_both_rules() {
617        // An outer circle one way, an inner circle the other: the classic
618        // counter, where both rules agree the middle is a hole.
619        //
620        // `Path2D::reverse` flips *every* subpath, so the inner contour is
621        // built and reversed on its own before being appended.
622        let mut outer_builder = PathBuilder::new();
623        outer_builder.circle(50.0, 50.0, 40.0);
624        let outer = outer_builder.build();
625
626        let mut inner_builder = PathBuilder::new();
627        inner_builder.circle(50.0, 50.0, 18.0);
628        let mut inner = inner_builder.build();
629        inner.reverse();
630
631        let mut b = PathBuilder::new();
632        b.extend(&outer);
633        b.extend(&inner);
634        let path = b.build();
635
636        for rule in [FillRule::NonZero, FillRule::EvenOdd] {
637            let mask = fill_path(&path, rule, 100, 100).expect("fills");
638            assert_eq!(mask[50 * 100 + 50], 0, "hole under {rule:?}");
639            assert!(
640                mask[50 * 100 + 10] > 250,
641                "the ring is ink under {rule:?}: {}",
642                mask[50 * 100 + 10]
643            );
644            // A point well inside the ring, clear of the flattened circle's
645            // edge, is solid.
646            assert!(
647                mask[10 * 100 + 50] > 250,
648                "solid ring under {rule:?}: {}",
649                mask[10 * 100 + 50]
650            );
651        }
652    }
653
654    #[test]
655    fn self_intersecting_star_differs_between_the_rules() {
656        // A five-pointed star drawn as one self-intersecting contour: the
657        // middle pentagon is wound twice, so non-zero fills it and even-odd
658        // punches it out. This is the case that separates the rules.
659        let pts = [
660            (50.0, 10.0),
661            (19.0, 90.0),
662            (90.0, 38.0),
663            (10.0, 38.0),
664            (81.0, 90.0),
665        ];
666        let mut b = PathBuilder::new();
667        for (i, p) in pts.iter().enumerate() {
668            if i == 0 {
669                b.move_to(p.0, p.1);
670            } else {
671                b.line_to(p.0, p.1);
672            }
673        }
674        b.close();
675        let path = b.build();
676
677        let nz = fill_path(&path, FillRule::NonZero, 100, 100).expect("fills");
678        let eo = fill_path(&path, FillRule::EvenOdd, 100, 100).expect("fills");
679        // The doubly-wound centre: ink under non-zero, a hole under even-odd.
680        assert_eq!(nz[50 * 100 + 50], 255, "non-zero keeps the centre");
681        assert_eq!(eo[50 * 100 + 50], 0, "even-odd empties the centre");
682        // Both rules agree on a point in a single-wound arm.
683        assert_eq!(nz[32 * 100 + 50], 255, "single-wound arm");
684        assert_eq!(eo[32 * 100 + 50], 255, "single-wound arm");
685        // And the empty corner outside the star.
686        assert_eq!(nz[50 * 100 + 5], 0);
687        assert_eq!(eo[50 * 100 + 5], 0);
688        // The two rules really do differ by the pentagon.
689        assert!(
690            ink(&nz) - ink(&eo) > 100.0,
691            "non-zero {} vs even-odd {}",
692            ink(&nz),
693            ink(&eo)
694        );
695    }
696
697    #[test]
698    fn degenerate_paths_produce_no_panic_and_no_ink() {
699        let empty = crate::Path2D::new();
700        let mask = fill_path(&empty, FillRule::NonZero, 8, 8).expect("fills");
701        assert!(mask.iter().all(|&v| v == 0));
702
703        // A lone point.
704        let mut b = PathBuilder::new();
705        b.move_to(4.0, 4.0);
706        let mask = fill_path(&b.build(), FillRule::NonZero, 8, 8).expect("fills");
707        assert_eq!(ink(&mask), 0.0);
708
709        // A zero-length line.
710        let mut b = PathBuilder::new();
711        b.move_to(4.0, 4.0);
712        b.line_to(4.0, 4.0);
713        b.close();
714        let mask = fill_path(&b.build(), FillRule::NonZero, 8, 8).expect("fills");
715        assert_eq!(ink(&mask), 0.0);
716
717        // A zero-area contour: a degenerate polygon.
718        let mut b = PathBuilder::new();
719        b.move_to(1.0, 1.0);
720        b.line_to(5.0, 1.0);
721        b.line_to(3.0, 1.0);
722        b.close();
723        let mask = fill_path(&b.build(), FillRule::NonZero, 8, 8).expect("fills");
724        assert!(
725            ink(&mask) < 0.01,
726            "a flat contour has no area: {}",
727            ink(&mask)
728        );
729
730        // A self-cancelling outline: a shape drawn forwards then backwards.
731        let mut b = PathBuilder::new();
732        b.rect(1.0, 1.0, 4.0, 4.0);
733        b.rect(1.0, 1.0, 4.0, 4.0);
734        let mask = fill_path(&b.build(), FillRule::NonZero, 8, 8).expect("fills");
735        assert!((ink(&mask) - 16.0).abs() < 0.01, "overlap still fills");
736    }
737
738    #[test]
739    fn triangle_coverage_sums_to_its_area() {
740        // A right triangle with legs 64: area = 2048. The mask's total ink must
741        // match within 0.1 %, which is the bound the analytic filler earns.
742        let mut b = PathBuilder::new();
743        b.move_to(0.0, 0.0);
744        b.line_to(64.0, 0.0);
745        b.line_to(0.0, 64.0);
746        b.close();
747        let path = b.build();
748        let mask = fill_path(&path, FillRule::NonZero, 64, 64).expect("fills");
749        let total = ink(&mask);
750        let exact = 0.5 * 64.0 * 64.0;
751        let err = (total - exact).abs() / exact;
752        assert!(
753            err < 0.001,
754            "triangle ink {total} vs area {exact}: relative error {err}"
755        );
756        // A tilted triangle: the same bound with diagonal edges, where a
757        // supersampling rasteriser would drift.
758        let mut t = PathBuilder::new();
759        t.move_to(10.0, 10.0);
760        t.line_to(90.0, 20.0);
761        t.line_to(30.0, 90.0);
762        t.close();
763        let mask = fill_path(&t.build(), FillRule::NonZero, 100, 100).expect("fills");
764        // Shoelace of the exact triangle, summed in `f64` from `f32` vertices.
765        let pts = [(10.0f32, 10.0f32), (90.0, 20.0), (30.0, 90.0)];
766        let mut acc = 0.0f64;
767        for (i, a) in pts.iter().enumerate() {
768            let b = pts[(i + 1) % 3];
769            acc += f64::from(a.0) * f64::from(b.1) - f64::from(b.0) * f64::from(a.1);
770        }
771        let exact = (acc * 0.5).abs();
772        let err = (ink(&mask) - exact).abs() / exact;
773        assert!(err < 0.002, "tilted triangle error {err}");
774    }
775
776    #[test]
777    fn circle_coverage_sums_to_its_area() {
778        // A radius-40 circle: area = pi·1600 ≈ 5026.5. The flattening tolerance
779        // bounds the error, so 1 % is generous.
780        let mut b = PathBuilder::new();
781        b.circle(50.0, 50.0, 40.0);
782        let mask = fill_path(&b.build(), FillRule::NonZero, 100, 100).expect("fills");
783        let want = core::f64::consts::PI * 1600.0;
784        let err = (ink(&mask) - want).abs() / want;
785        assert!(err < 0.01, "circle ink error {err}");
786    }
787
788    #[test]
789    fn zero_sized_raster_is_empty() {
790        let p = rect(0.0, 0.0, 4.0, 4.0);
791        assert!(fill_path(&p, FillRule::NonZero, 0, 8)
792            .expect("fills")
793            .is_empty());
794        assert!(fill_path(&p, FillRule::NonZero, 8, 0)
795            .expect("fills")
796            .is_empty());
797        assert!(fill_path(&p, FillRule::NonZero, 0, 0)
798            .expect("fills")
799            .is_empty());
800    }
801
802    #[test]
803    fn oversized_raster_is_refused() {
804        let p = rect(0.0, 0.0, 1.0, 1.0);
805        match fill_path(&p, FillRule::NonZero, 100_000, 100_000).unwrap_err() {
806            ShapeError::RasterTooLarge { pixels, limit } => {
807                assert_eq!(pixels, 10_000_000_000);
808                assert_eq!(limit, MAX_MASK_ELEMENTS);
809            }
810            other => panic!("expected RasterTooLarge, got {other:?}"),
811        }
812        // And the message names the numbers.
813        let msg = alloc::format!(
814            "{}",
815            ShapeError::RasterTooLarge {
816                pixels: 10_000_000_000,
817                limit: MAX_MASK_ELEMENTS
818            }
819        );
820        assert!(msg.contains("10000000000"));
821    }
822
823    #[test]
824    fn geometry_entirely_outside_the_raster_is_empty() {
825        let p = rect(100.0, 100.0, 10.0, 10.0);
826        let mask = fill_path(&p, FillRule::NonZero, 8, 8).expect("fills");
827        assert_eq!(ink(&mask), 0.0);
828        // And partly outside is clipped, not wrapped.
829        let p = rect(-4.0, -4.0, 8.0, 8.0);
830        let mask = fill_path(&p, FillRule::NonZero, 8, 8).expect("fills");
831        assert!((ink(&mask) - 16.0).abs() < 0.01, "clipped to a quarter");
832    }
833
834    #[test]
835    fn collect_edges_drops_horizontal_and_non_finite_segments() {
836        // A horizontal-only path has no edges at all.
837        let mut b = PathBuilder::new();
838        b.move_to(0.0, 5.0);
839        b.line_to(10.0, 5.0);
840        b.close();
841        assert!(collect_edges(&b.build()).is_empty());
842
843        // A NaN segment is dropped, and the good one survives.
844        let mut b = PathBuilder::new();
845        b.move_to(0.0, 0.0);
846        b.line_to(f32::NAN, 10.0);
847        b.line_to(10.0, 20.0);
848        b.close();
849        let edges = collect_edges(&b.build());
850        assert_eq!(edges.len(), 1, "one usable edge");
851        assert!(edges[0].x0.is_finite() && edges[0].x1.is_finite());
852    }
853
854    #[test]
855    fn edges_report_their_direction() {
856        let down = Edge {
857            x0: 0.0,
858            y0: 0.0,
859            x1: 1.0,
860            y1: 4.0,
861            dir: 1,
862        };
863        assert_eq!(down.y_min(), 0.0);
864        assert_eq!(down.y_max(), 4.0);
865        assert!(close(down.x_at(0.0), 0.0));
866        assert!(close(down.x_at(2.0), 0.5));
867        assert!(close(down.x_at(4.0), 1.0));
868        // A degenerate edge with no vertical extent evaluates to x0.
869        let flat = Edge {
870            x0: 3.0,
871            y0: 1.0,
872            x1: 3.0,
873            y1: 1.0,
874            dir: 1,
875        };
876        assert!(close(flat.x_at(1.0), 3.0));
877    }
878
879    #[test]
880    fn fill_rule_default_is_non_zero() {
881        assert_eq!(FillRule::default(), FillRule::NonZero);
882    }
883
884    #[test]
885    fn transform_of_a_path_matches_its_mask_bounds() {
886        // Fill a rectangle, then a transformed copy: the ink is the same
887        // because a transform of a path is a transform of its coverage.
888        let p = rect(20.0, 30.0, 20.0, 10.0);
889        let a = fill_path(&p, FillRule::NonZero, 64, 64).expect("fills");
890        let t = p.transformed(&crate::Affine2D::translate(4.0, -6.0));
891        let b = fill_path(&t, FillRule::NonZero, 64, 64).expect("fills");
892        assert!(
893            (ink(&a) - ink(&b)).abs() < 0.5,
894            "{} vs {}",
895            ink(&a),
896            ink(&b)
897        );
898        // A uniform scale by 2 quadruples the area.
899        let big = p.transformed(&crate::Affine2D::scale(2.0, 2.0));
900        let c = fill_path(&big, FillRule::NonZero, 128, 128).expect("fills");
901        assert!(
902            (ink(&c) - ink(&a) * 4.0).abs() < 1.0,
903            "{} vs {}",
904            ink(&c),
905            ink(&a) * 4.0
906        );
907    }
908
909    #[test]
910    fn pixel_bounds_of_a_path() {
911        let p = rect(4.25, 6.75, 10.0, 5.0);
912        assert_eq!(path_pixel_bounds(&p, 64, 64), Some((4, 6, 11, 6)));
913        // Clipped to the raster.
914        assert_eq!(path_pixel_bounds(&p, 8, 8), Some((4, 6, 4, 2)));
915        // Nothing at all when off-raster.
916        assert_eq!(path_pixel_bounds(&rect(100.0, 100.0, 1.0, 1.0), 8, 8), None);
917        // And an empty path has no bounds.
918        assert_eq!(path_pixel_bounds(&crate::Path2D::new(), 8, 8), None);
919    }
920
921    #[test]
922    fn mask_values_are_always_in_range() {
923        // A wild path: a star, several overlapping shapes, and a curve.
924        let mut b = PathBuilder::new();
925        b.circle(32.0, 32.0, 30.0);
926        for i in 0..7 {
927            let a = i as f32 * 0.9;
928            b.move_to(32.0, 32.0);
929            b.line_to(32.0 + 25.0 * libm::cosf(a), 32.0 + 25.0 * libm::sinf(a));
930        }
931        b.rect(0.0, 0.0, 64.0, 64.0);
932        for rule in [FillRule::NonZero, FillRule::EvenOdd] {
933            let mask = fill_path(&b.build(), rule, 64, 64).expect("fills");
934            assert_eq!(mask.len(), 64 * 64);
935            // Every pixel is a valid coverage byte — the type says so — and
936            // the total ink cannot exceed the frame it covers.
937            assert!(ink(&mask) <= 64.0 * 64.0 + 1e-6);
938            assert!(ink(&mask) > 0.0, "the star and the frame both draw");
939        }
940    }
941}