1use crate::canvas::{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(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
96fn 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
105pub 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
141pub 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}