1 | use crate::{BackendCoord, BackendStyle, DrawingBackend, DrawingErrorKind}; |
2 | |
3 | use std::cmp::{Ord, Ordering, PartialOrd}; |
4 | |
5 | #[derive(Clone, Debug)] |
6 | struct Edge { |
7 | epoch: u32, |
8 | total_epoch: u32, |
9 | slave_begin: i32, |
10 | slave_end: i32, |
11 | } |
12 | |
13 | impl Edge { |
14 | fn horizontal_sweep(mut from: BackendCoord, mut to: BackendCoord) -> Option<Edge> { |
15 | if from.0 == to.0 { |
16 | return None; |
17 | } |
18 | |
19 | if from.0 > to.0 { |
20 | std::mem::swap(&mut from, &mut to); |
21 | } |
22 | |
23 | Some(Edge { |
24 | epoch: 0, |
25 | total_epoch: (to.0 - from.0) as u32, |
26 | slave_begin: from.1, |
27 | slave_end: to.1, |
28 | }) |
29 | } |
30 | |
31 | fn vertical_sweep(from: BackendCoord, to: BackendCoord) -> Option<Edge> { |
32 | Edge::horizontal_sweep((from.1, from.0), (to.1, to.0)) |
33 | } |
34 | |
35 | fn get_master_pos(&self) -> i32 { |
36 | (self.total_epoch - self.epoch) as i32 |
37 | } |
38 | |
39 | fn inc_epoch(&mut self) { |
40 | self.epoch += 1; |
41 | } |
42 | |
43 | fn get_slave_pos(&self) -> f64 { |
44 | f64::from(self.slave_begin) |
45 | + (i64::from(self.slave_end - self.slave_begin) * i64::from(self.epoch)) as f64 |
46 | / f64::from(self.total_epoch) |
47 | } |
48 | } |
49 | |
50 | impl PartialOrd for Edge { |
51 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { |
52 | self.get_slave_pos().partial_cmp(&other.get_slave_pos()) |
53 | } |
54 | } |
55 | |
56 | impl PartialEq for Edge { |
57 | fn eq(&self, other: &Self) -> bool { |
58 | self.get_slave_pos() == other.get_slave_pos() |
59 | } |
60 | } |
61 | |
62 | impl Eq for Edge {} |
63 | |
64 | impl Ord for Edge { |
65 | fn cmp(&self, other: &Self) -> Ordering { |
66 | self.get_slave_pos() |
67 | .partial_cmp(&other.get_slave_pos()) |
68 | .unwrap() |
69 | } |
70 | } |
71 | |
72 | pub fn fill_polygon<DB: DrawingBackend, S: BackendStyle>( |
73 | back: &mut DB, |
74 | vertices: &[BackendCoord], |
75 | style: &S, |
76 | ) -> Result<(), DrawingErrorKind<DB::ErrorType>> { |
77 | if let Some((x_span, y_span)) = |
78 | vertices |
79 | .iter() |
80 | .fold(None, |res: Option<((i32, i32), (i32, i32))>, (x, y)| { |
81 | Some( |
82 | res.map(|((min_x, max_x), (min_y, max_y))| { |
83 | ( |
84 | (min_x.min(*x), max_x.max(*x)), |
85 | (min_y.min(*y), max_y.max(*y)), |
86 | ) |
87 | }) |
88 | .unwrap_or(((*x, *x), (*y, *y))), |
89 | ) |
90 | }) |
91 | { |
92 | // First of all, let's handle the case that all the points is in a same vertical or |
93 | // horizontal line |
94 | if x_span.0 == x_span.1 || y_span.0 == y_span.1 { |
95 | return back.draw_line((x_span.0, y_span.0), (x_span.1, y_span.1), style); |
96 | } |
97 | |
98 | let horizontal_sweep = x_span.1 - x_span.0 > y_span.1 - y_span.0; |
99 | |
100 | let mut edges: Vec<_> = vertices |
101 | .iter() |
102 | .zip(vertices.iter().skip(1)) |
103 | .map(|(a, b)| (*a, *b)) |
104 | .collect(); |
105 | edges.push((vertices[vertices.len() - 1], vertices[0])); |
106 | edges.sort_by_key(|((x1, y1), (x2, y2))| { |
107 | if horizontal_sweep { |
108 | *x1.min(x2) |
109 | } else { |
110 | *y1.min(y2) |
111 | } |
112 | }); |
113 | |
114 | for edge in &mut edges.iter_mut() { |
115 | if horizontal_sweep { |
116 | if (edge.0).0 > (edge.1).0 { |
117 | std::mem::swap(&mut edge.0, &mut edge.1); |
118 | } |
119 | } else if (edge.0).1 > (edge.1).1 { |
120 | std::mem::swap(&mut edge.0, &mut edge.1); |
121 | } |
122 | } |
123 | |
124 | let (low, high) = if horizontal_sweep { x_span } else { y_span }; |
125 | |
126 | let mut idx = 0; |
127 | |
128 | let mut active_edge: Vec<Edge> = vec![]; |
129 | |
130 | for sweep_line in low..=high { |
131 | let mut new_vec = vec![]; |
132 | |
133 | for mut e in active_edge { |
134 | if e.get_master_pos() > 0 { |
135 | e.inc_epoch(); |
136 | new_vec.push(e); |
137 | } |
138 | } |
139 | |
140 | active_edge = new_vec; |
141 | |
142 | loop { |
143 | if idx >= edges.len() { |
144 | break; |
145 | } |
146 | let line = if horizontal_sweep { |
147 | (edges[idx].0).0 |
148 | } else { |
149 | (edges[idx].0).1 |
150 | }; |
151 | if line > sweep_line { |
152 | break; |
153 | } |
154 | |
155 | let edge_obj = if horizontal_sweep { |
156 | Edge::horizontal_sweep(edges[idx].0, edges[idx].1) |
157 | } else { |
158 | Edge::vertical_sweep(edges[idx].0, edges[idx].1) |
159 | }; |
160 | |
161 | if let Some(edge_obj) = edge_obj { |
162 | active_edge.push(edge_obj); |
163 | } |
164 | |
165 | idx += 1; |
166 | } |
167 | |
168 | active_edge.sort(); |
169 | |
170 | let mut first = None; |
171 | let mut second = None; |
172 | |
173 | for edge in active_edge.iter() { |
174 | if first.is_none() { |
175 | first = Some(edge.clone()) |
176 | } else if second.is_none() { |
177 | second = Some(edge.clone()) |
178 | } |
179 | |
180 | if let Some(a) = first.clone() { |
181 | if let Some(b) = second.clone() { |
182 | if a.get_master_pos() == 0 && b.get_master_pos() != 0 { |
183 | first = Some(b); |
184 | second = None; |
185 | continue; |
186 | } |
187 | |
188 | if a.get_master_pos() != 0 && b.get_master_pos() == 0 { |
189 | first = Some(a); |
190 | second = None; |
191 | continue; |
192 | } |
193 | |
194 | let from = a.get_slave_pos(); |
195 | let to = b.get_slave_pos(); |
196 | |
197 | if a.get_master_pos() == 0 && b.get_master_pos() == 0 && to - from > 1.0 { |
198 | first = None; |
199 | second = None; |
200 | continue; |
201 | } |
202 | |
203 | if horizontal_sweep { |
204 | check_result!(back.draw_line( |
205 | (sweep_line, from.ceil() as i32), |
206 | (sweep_line, to.floor() as i32), |
207 | &style.color(), |
208 | )); |
209 | check_result!(back.draw_pixel( |
210 | (sweep_line, from.floor() as i32), |
211 | style.color().mix(from.ceil() - from), |
212 | )); |
213 | check_result!(back.draw_pixel( |
214 | (sweep_line, to.ceil() as i32), |
215 | style.color().mix(to - to.floor()), |
216 | )); |
217 | } else { |
218 | check_result!(back.draw_line( |
219 | (from.ceil() as i32, sweep_line), |
220 | (to.floor() as i32, sweep_line), |
221 | &style.color(), |
222 | )); |
223 | check_result!(back.draw_pixel( |
224 | (from.floor() as i32, sweep_line), |
225 | style.color().mix(from.ceil() - from), |
226 | )); |
227 | check_result!(back.draw_pixel( |
228 | (to.ceil() as i32, sweep_line), |
229 | style.color().mix(to.floor() - to), |
230 | )); |
231 | } |
232 | |
233 | first = None; |
234 | second = None; |
235 | } |
236 | } |
237 | } |
238 | } |
239 | } |
240 | |
241 | Ok(()) |
242 | } |
243 | |