Skip to main content

pdf2_render/
raster.rs

1//! Scanline rasterisation: filling polygons into the canvas through a clip mask,
2//! and turning polygons into a clip mask.
3
4use crate::canvas::{BlendMode, Canvas, ClipMask, Color};
5use crate::geom::Point;
6
7/// One polygon edge, with the winding direction it contributes.
8struct Edge {
9    x0: f64,
10    y0: f64,
11    x1: f64,
12    y1: f64,
13    winding: i32,
14}
15
16fn edges_of(polygons: &[Vec<Point>]) -> Vec<Edge> {
17    let mut edges = Vec::new();
18    for polygon in polygons {
19        for index in 0..polygon.len() {
20            let start = polygon[index];
21            let end = polygon[(index + 1) % polygon.len()];
22            if (start.y - end.y).abs() < f64::EPSILON {
23                continue;
24            }
25            let winding = if end.y > start.y { 1 } else { -1 };
26            edges.push(Edge {
27                x0: start.x,
28                y0: start.y,
29                x1: end.x,
30                y1: end.y,
31                winding,
32            });
33        }
34    }
35    edges
36}
37
38/// Horizontal spans of a scanline in device x, fractional at the ends.
39///
40/// Anti-aliasing needs the *fraction* of a pixel a span covers, so this returns
41/// the exact crossing positions rather than rounding them; [`pixel_range`] does
42/// the rounding for the clip mask, which is a boolean by nature.
43fn spans_of(edges: &[Edge], row: f64, even_odd: bool) -> Vec<(f64, f64)> {
44    let mut crossings: Vec<(f64, i32)> = Vec::new();
45    for edge in edges {
46        let low = edge.y0.min(edge.y1);
47        let high = edge.y0.max(edge.y1);
48        if row < low || row >= high {
49            continue;
50        }
51        let t = (row - edge.y0) / (edge.y1 - edge.y0);
52        crossings.push((edge.x0 + t * (edge.x1 - edge.x0), edge.winding));
53    }
54    if crossings.is_empty() {
55        return Vec::new();
56    }
57    crossings.sort_by(|left, right| left.0.total_cmp(&right.0));
58
59    let mut result = Vec::new();
60    let mut winding = 0;
61    let mut start_x: Option<f64> = None;
62    for (x, direction) in crossings {
63        let was_inside = if even_odd {
64            winding & 1 != 0
65        } else {
66            winding != 0
67        };
68        if even_odd {
69            winding += 1;
70        } else {
71            winding += direction;
72        }
73        let is_inside = if even_odd {
74            winding & 1 != 0
75        } else {
76            winding != 0
77        };
78        match (was_inside, is_inside) {
79            (false, true) => start_x = Some(x),
80            (true, false) => {
81                if let Some(start) = start_x.take()
82                    && x > start
83                {
84                    result.push((start, x));
85                }
86            }
87            _ => {}
88        }
89    }
90    if let Some(start) = start_x {
91        result.push((start, start));
92    }
93    result
94}
95
96/// Device x range a fractional span touches, as `[first, past)`.
97fn span_pixels(start: f64, end: f64) -> (i64, i64) {
98    #[allow(clippy::cast_possible_truncation)]
99    let first = start.floor() as i64;
100    #[allow(clippy::cast_possible_truncation)]
101    let past = end.ceil() as i64;
102    (first, past.max(first))
103}
104
105/// Sub-scanlines per device row: 1 would be no anti-aliasing, 4 is enough to
106/// take the staircase off a glyph edge at normal sizes, and the horizontal
107/// coverage is exact, so the error is vertical only.
108const AA_SUBROWS: usize = 4;
109
110#[allow(clippy::cast_possible_truncation)]
111fn x_i32(x: i64) -> i32 {
112    x as i32
113}
114
115/// Fill polygons with `color`, restricted to `mask`.
116///
117/// `even_odd` selects the even-odd rule; otherwise the non-zero winding rule
118/// applies. The scanline is sampled at pixel centres, so results are crisp and
119/// deterministic — no anti-aliasing yet.
120pub fn fill_polygons(
121    canvas: &mut Canvas,
122    mask: &ClipMask,
123    polygons: &[Vec<Point>],
124    color: Color,
125    even_odd: bool,
126    alpha: f64,
127    mode: BlendMode,
128) {
129    if polygons.is_empty() {
130        return;
131    }
132    let edges = edges_of(polygons);
133    if edges.is_empty() {
134        return;
135    }
136    // Only the rows the outline touches: a glyph is a dozen rows tall, and
137    // scanning the whole canvas for each of the two thousand glyphs on a page of
138    // prose was most of that page's render time.
139    let (low, high) = edges
140        .iter()
141        .fold((f64::MAX, f64::MIN), |(low, high), edge| {
142            (
143                low.min(edge.y0.min(edge.y1)),
144                high.max(edge.y0.max(edge.y1)),
145            )
146        });
147    if high <= low {
148        return;
149    }
150    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
151    let first_row = ((low - 0.5).ceil().max(0.0) as u32).min(canvas.height());
152    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
153    let past_last = ((high - 0.5).ceil().max(0.0) as u32).min(canvas.height());
154    for y in first_row..past_last {
155        // Four sub-scanlines per device row, each contributing an exact
156        // horizontal fraction, summed and blended **once** per pixel: blending
157        // four times at a quarter alpha is not the same thing — it lands on
158        // `1-(1-a/4)^4`, about 68 % instead of 100 %.
159        let mut sub_spans: [Vec<(f64, f64)>; AA_SUBROWS] = Default::default();
160        let mut low_x = i64::MAX;
161        let mut high_x = i64::MIN;
162        for (sub, spans) in sub_spans.iter_mut().enumerate() {
163            #[allow(clippy::cast_precision_loss)]
164            let offset = (sub as f64 + 0.5) / AA_SUBROWS as f64;
165            *spans = spans_of(&edges, f64::from(y) + offset, even_odd);
166            for (start, end) in spans.iter() {
167                let (first, past) = span_pixels(*start, *end);
168                low_x = low_x.min(first);
169                high_x = high_x.max(past);
170            }
171        }
172        if low_x >= high_x {
173            continue;
174        }
175        let mut coverage = vec![0.0_f64; usize::try_from(high_x - low_x).unwrap_or(0)];
176        for spans in &sub_spans {
177            for (start, end) in spans {
178                let (first, past) = span_pixels(*start, *end);
179                for x in first.max(low_x)..past.min(high_x) {
180                    #[allow(clippy::cast_precision_loss)]
181                    let left = (x as f64).max(*start);
182                    #[allow(clippy::cast_precision_loss)]
183                    let right = ((x + 1) as f64).min(*end);
184                    if right > left {
185                        let index = usize::try_from(x - low_x).unwrap_or(0);
186                        coverage[index] += (right - left).min(1.0);
187                    }
188                }
189            }
190        }
191        for (index, covered) in coverage.iter().enumerate() {
192            if *covered <= 0.0 {
193                continue;
194            }
195            let Some(x) = low_x.checked_add(i64::try_from(index).unwrap_or(0)) else {
196                continue;
197            };
198            if x < 0 || x >= i64::from(canvas.width()) {
199                continue;
200            }
201            #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
202            let pixel_x = x as u32;
203            let mask_coverage = mask.alpha(pixel_x, y);
204            if mask_coverage <= 0.0 {
205                continue;
206            }
207            let fraction = (covered / AA_SUBROWS as f64).min(1.0);
208            canvas.blend_with(pixel_x, y, color, alpha * mask_coverage * fraction, mode);
209        }
210    }
211}
212
213/// Rasterise polygons into a clip mask of the given size: inside where the
214/// fill rule says painted, outside everywhere else.
215pub fn clip_mask(width: u32, height: u32, polygons: &[Vec<Point>], even_odd: bool) -> ClipMask {
216    let mut mask = ClipMask::none(width, height);
217    let edges = edges_of(polygons);
218    for y in 0..height {
219        let row = f64::from(y) + 0.5;
220        for (start, end) in spans_of(&edges, row, even_odd) {
221            let (first, past) = span_pixels(start, end);
222            let from = first.max(0);
223            let to = past.min(i64::from(width));
224            for x in from..to {
225                // A pixel belongs to the clip when its centre is covered.
226                let centre = f64::from(x_i32(x)) + 0.5;
227                if start <= centre && centre < end {
228                    #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
229                    mask.set(x as u32, y, true);
230                }
231            }
232        }
233    }
234    mask
235}
236
237#[cfg(test)]
238mod tests {
239    use super::{clip_mask, edges_of, fill_polygons, spans_of};
240    use crate::canvas::{BlendMode, Canvas, ClipMask, Color};
241    use crate::geom::Point;
242
243    fn rect(x: f64, y: f64, width: f64, height: f64) -> Vec<Point> {
244        vec![
245            Point::new(x, y),
246            Point::new(x + width, y),
247            Point::new(x + width, y + height),
248            Point::new(x, y + height),
249        ]
250    }
251
252    #[test]
253    fn a_rectangle_covers_its_centre_pixels() {
254        let mut canvas = Canvas::new(10, 10, Color::WHITE);
255        let mask = ClipMask::all(10, 10);
256        fill_polygons(
257            &mut canvas,
258            &mask,
259            &[rect(2.0, 3.0, 4.0, 2.0)],
260            Color::BLACK,
261            false,
262            1.0,
263            BlendMode::Normal,
264        );
265        assert_eq!(canvas.pixel(3, 4), Some([0, 0, 0, 255]));
266        assert_eq!(canvas.pixel(1, 4), Some([255, 255, 255, 255]));
267        assert_eq!(canvas.pixel(3, 2), Some([255, 255, 255, 255]));
268        assert_eq!(canvas.pixel(6, 4), Some([255, 255, 255, 255]));
269    }
270
271    #[test]
272    fn the_even_odd_rule_cuts_the_overlap() {
273        let polygons = [rect(0.0, 0.0, 6.0, 6.0), rect(2.0, 2.0, 6.0, 6.0)];
274        let mut nonzero = Canvas::new(10, 10, Color::WHITE);
275        fill_polygons(
276            &mut nonzero,
277            &ClipMask::all(10, 10),
278            &polygons,
279            Color::BLACK,
280            false,
281            1.0,
282            BlendMode::Normal,
283        );
284        assert_eq!(nonzero.pixel(3, 3), Some([0, 0, 0, 255]));
285
286        let mut even_odd = Canvas::new(10, 10, Color::WHITE);
287        fill_polygons(
288            &mut even_odd,
289            &ClipMask::all(10, 10),
290            &polygons,
291            Color::BLACK,
292            true,
293            1.0,
294            BlendMode::Normal,
295        );
296        assert_eq!(even_odd.pixel(3, 3), Some([255, 255, 255, 255]));
297        assert_eq!(even_odd.pixel(1, 1), Some([0, 0, 0, 255]));
298    }
299
300    #[test]
301    fn the_mask_restricts_painting() {
302        let mut mask = ClipMask::all(10, 10);
303        for x in 0..5 {
304            mask.set(x, 0, false);
305        }
306        let mut canvas = Canvas::new(10, 10, Color::WHITE);
307        fill_polygons(
308            &mut canvas,
309            &mask,
310            &[rect(0.0, 0.0, 10.0, 1.0)],
311            Color::BLACK,
312            false,
313            1.0,
314            BlendMode::Normal,
315        );
316        assert_eq!(canvas.pixel(0, 0), Some([255, 255, 255, 255]));
317        assert_eq!(canvas.pixel(6, 0), Some([0, 0, 0, 255]));
318    }
319
320    #[test]
321    fn a_clip_mask_covers_exactly_the_clip_path() {
322        let mask = clip_mask(10, 10, &[rect(2.0, 2.0, 3.0, 3.0)], false);
323        assert!(mask.contains(3, 3));
324        assert!(!mask.contains(1, 1));
325        assert!(!mask.contains(6, 6));
326        assert_eq!(mask.count(), 9);
327    }
328
329    #[test]
330    fn spans_handle_shared_edges() {
331        let edges = edges_of(&[rect(0.0, 0.0, 4.0, 4.0)]);
332        let row = spans_of(&edges, 2.5, false);
333        assert_eq!(row, vec![(0.0, 4.0)]);
334        assert!(spans_of(&edges, 5.5, false).is_empty());
335    }
336
337    #[test]
338    fn an_edge_through_a_pixel_paints_half_of_it() {
339        // A rectangle whose right edge is at x = 3.5 covers half of pixel 3: with
340        // four sub-scanlines the blend composes to about 50 % grey.
341        let mut canvas = Canvas::new(8, 4, Color::WHITE);
342        fill_polygons(
343            &mut canvas,
344            &ClipMask::all(8, 4),
345            &[rect(1.0, 1.0, 2.5, 2.0)],
346            Color::BLACK,
347            false,
348            1.0,
349            BlendMode::Normal,
350        );
351        let partial = canvas.pixel(3, 2).expect("inside");
352        assert!(
353            (120..=135).contains(&u16::from(partial[0])),
354            "half coverage is about 128, got {partial:?}"
355        );
356        assert_eq!(canvas.pixel(2, 2), Some([0, 0, 0, 255]), "fully inside");
357        assert_eq!(canvas.pixel(4, 2), Some([255, 255, 255, 255]), "outside");
358    }
359
360    #[test]
361    fn an_edge_on_a_pixel_boundary_leaves_no_half_pixels() {
362        let mut canvas = Canvas::new(8, 4, Color::WHITE);
363        fill_polygons(
364            &mut canvas,
365            &ClipMask::all(8, 4),
366            &[rect(1.0, 1.0, 3.0, 2.0)],
367            Color::BLACK,
368            false,
369            1.0,
370            BlendMode::Normal,
371        );
372        for x in 1..4 {
373            assert_eq!(canvas.pixel(x, 2), Some([0, 0, 0, 255]), "pixel {x}");
374        }
375        assert_eq!(canvas.pixel(0, 2), Some([255, 255, 255, 255]));
376        assert_eq!(canvas.pixel(4, 2), Some([255, 255, 255, 255]));
377    }
378}