1use crate::canvas::{BlendMode, Canvas, ClipMask, Color};
5use crate::geom::Point;
6
7struct 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
38fn 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
96fn 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
105const AA_SUBROWS: usize = 4;
109
110#[allow(clippy::cast_possible_truncation)]
111fn x_i32(x: i64) -> i32 {
112 x as i32
113}
114
115pub 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 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 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
213pub 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 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 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}