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::{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 pixel spans of a scanline, as `[first, past_last)`.
39fn spans(edges: &[Edge], row: f64, even_odd: bool) -> Vec<(i64, i64)> {
40    let mut crossings: Vec<(f64, i32)> = Vec::new();
41    for edge in edges {
42        let low = edge.y0.min(edge.y1);
43        let high = edge.y0.max(edge.y1);
44        if row < low || row >= high {
45            continue;
46        }
47        let t = (row - edge.y0) / (edge.y1 - edge.y0);
48        crossings.push((edge.x0 + t * (edge.x1 - edge.x0), edge.winding));
49    }
50    if crossings.is_empty() {
51        return Vec::new();
52    }
53    crossings.sort_by(|left, right| left.0.total_cmp(&right.0));
54
55    let mut result = Vec::new();
56    let mut winding = 0;
57    let mut start_x: Option<f64> = None;
58    for (x, direction) in crossings {
59        let was_inside = if even_odd {
60            winding & 1 != 0
61        } else {
62            winding != 0
63        };
64        if even_odd {
65            winding += 1;
66        } else {
67            winding += direction;
68        }
69        let is_inside = if even_odd {
70            winding & 1 != 0
71        } else {
72            winding != 0
73        };
74        match (was_inside, is_inside) {
75            (false, true) => start_x = Some(x),
76            (true, false) => {
77                if let Some(start) = start_x.take() {
78                    let (first, past) = pixel_range(start, x);
79                    if past > first {
80                        result.push((first, past));
81                    }
82                }
83            }
84            _ => {}
85        }
86    }
87    if let Some(start) = start_x {
88        let (first, past) = pixel_range(start, start);
89        if past > first {
90            result.push((first, past));
91        }
92    }
93    result
94}
95
96/// Pixels whose centres fall in `[start, end)`.
97fn pixel_range(start: f64, end: f64) -> (i64, i64) {
98    #[allow(clippy::cast_possible_truncation)]
99    let first = (start - 0.5).ceil() as i64;
100    #[allow(clippy::cast_possible_truncation)]
101    let past = (end - 0.5).ceil() as i64;
102    (first, past.max(first))
103}
104
105/// Fill polygons with `color`, restricted to `mask`.
106///
107/// `even_odd` selects the even-odd rule; otherwise the non-zero winding rule
108/// applies. The scanline is sampled at pixel centres, so results are crisp and
109/// deterministic — no anti-aliasing yet.
110pub fn fill_polygons(
111    canvas: &mut Canvas,
112    mask: &ClipMask,
113    polygons: &[Vec<Point>],
114    color: Color,
115    even_odd: bool,
116    alpha: f64,
117) {
118    if polygons.is_empty() {
119        return;
120    }
121    let edges = edges_of(polygons);
122    if edges.is_empty() {
123        return;
124    }
125    for y in 0..canvas.height() {
126        let row = f64::from(y) + 0.5;
127        for (first, past) in spans(&edges, row, even_odd) {
128            let from = first.max(0);
129            let to = past.min(i64::from(canvas.width()));
130            for x in from..to {
131                #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
132                let x = x as u32;
133                if mask.contains(x, y) {
134                    canvas.blend(x, y, color, alpha);
135                }
136            }
137        }
138    }
139}
140
141/// Rasterise polygons into a clip mask of the given size: inside where the
142/// fill rule says painted, outside everywhere else.
143pub fn clip_mask(width: u32, height: u32, polygons: &[Vec<Point>], even_odd: bool) -> ClipMask {
144    let mut mask = ClipMask::none(width, height);
145    let edges = edges_of(polygons);
146    for y in 0..height {
147        let row = f64::from(y) + 0.5;
148        for (first, past) in spans(&edges, row, even_odd) {
149            let from = first.max(0);
150            let to = past.min(i64::from(width));
151            for x in from..to {
152                #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
153                mask.set(x as u32, y, true);
154            }
155        }
156    }
157    mask
158}
159
160#[cfg(test)]
161mod tests {
162    use super::{clip_mask, edges_of, fill_polygons, spans};
163    use crate::canvas::{Canvas, ClipMask, Color};
164    use crate::geom::Point;
165
166    fn rect(x: f64, y: f64, width: f64, height: f64) -> Vec<Point> {
167        vec![
168            Point::new(x, y),
169            Point::new(x + width, y),
170            Point::new(x + width, y + height),
171            Point::new(x, y + height),
172        ]
173    }
174
175    #[test]
176    fn a_rectangle_covers_its_centre_pixels() {
177        let mut canvas = Canvas::new(10, 10, Color::WHITE);
178        let mask = ClipMask::all(10, 10);
179        fill_polygons(
180            &mut canvas,
181            &mask,
182            &[rect(2.0, 3.0, 4.0, 2.0)],
183            Color::BLACK,
184            false,
185            1.0,
186        );
187        assert_eq!(canvas.pixel(3, 4), Some([0, 0, 0, 255]));
188        assert_eq!(canvas.pixel(1, 4), Some([255, 255, 255, 255]));
189        assert_eq!(canvas.pixel(3, 2), Some([255, 255, 255, 255]));
190        assert_eq!(canvas.pixel(6, 4), Some([255, 255, 255, 255]));
191    }
192
193    #[test]
194    fn the_even_odd_rule_cuts_the_overlap() {
195        let polygons = [rect(0.0, 0.0, 6.0, 6.0), rect(2.0, 2.0, 6.0, 6.0)];
196        let mut nonzero = Canvas::new(10, 10, Color::WHITE);
197        fill_polygons(
198            &mut nonzero,
199            &ClipMask::all(10, 10),
200            &polygons,
201            Color::BLACK,
202            false,
203            1.0,
204        );
205        assert_eq!(nonzero.pixel(3, 3), Some([0, 0, 0, 255]));
206
207        let mut even_odd = Canvas::new(10, 10, Color::WHITE);
208        fill_polygons(
209            &mut even_odd,
210            &ClipMask::all(10, 10),
211            &polygons,
212            Color::BLACK,
213            true,
214            1.0,
215        );
216        assert_eq!(even_odd.pixel(3, 3), Some([255, 255, 255, 255]));
217        assert_eq!(even_odd.pixel(1, 1), Some([0, 0, 0, 255]));
218    }
219
220    #[test]
221    fn the_mask_restricts_painting() {
222        let mut mask = ClipMask::all(10, 10);
223        for x in 0..5 {
224            mask.set(x, 0, false);
225        }
226        let mut canvas = Canvas::new(10, 10, Color::WHITE);
227        fill_polygons(
228            &mut canvas,
229            &mask,
230            &[rect(0.0, 0.0, 10.0, 1.0)],
231            Color::BLACK,
232            false,
233            1.0,
234        );
235        assert_eq!(canvas.pixel(0, 0), Some([255, 255, 255, 255]));
236        assert_eq!(canvas.pixel(6, 0), Some([0, 0, 0, 255]));
237    }
238
239    #[test]
240    fn a_clip_mask_covers_exactly_the_clip_path() {
241        let mask = clip_mask(10, 10, &[rect(2.0, 2.0, 3.0, 3.0)], false);
242        assert!(mask.contains(3, 3));
243        assert!(!mask.contains(1, 1));
244        assert!(!mask.contains(6, 6));
245        assert_eq!(mask.count(), 9);
246    }
247
248    #[test]
249    fn spans_handle_shared_edges() {
250        let edges = edges_of(&[rect(0.0, 0.0, 4.0, 4.0)]);
251        let row = spans(&edges, 2.5, false);
252        assert_eq!(row, vec![(0, 4)]);
253        assert!(spans(&edges, 5.5, false).is_empty());
254    }
255}