1// Copyright 2011 Google Inc.
2// Copyright 2020 Yevhenii Reizner
3//
4// Use of this source code is governed by a BSD-style license that can be
5// found in the LICENSE file.
6
7use alloc::vec::Vec;
8
9use tiny_skia_path::PathVerb;
10
11use crate::{Path, Point};
12
13use crate::edge::{CubicEdge, Edge, LineEdge, QuadraticEdge};
14use crate::edge_clipper::EdgeClipperIter;
15use crate::geom::ScreenIntRect;
16use crate::path_geometry;
17
18#[derive(Copy, Clone, PartialEq, Debug)]
19enum Combine {
20 No,
21 Partial,
22 Total,
23}
24
25#[derive(Copy, Clone, Debug)]
26pub struct ShiftedIntRect {
27 shifted: ScreenIntRect,
28 shift: i32,
29}
30
31impl ShiftedIntRect {
32 pub fn new(rect: &ScreenIntRect, shift: i32) -> Option<Self> {
33 let shifted = ScreenIntRect::from_xywh(
34 rect.x() << shift,
35 rect.y() << shift,
36 rect.width() << shift,
37 rect.height() << shift,
38 )?;
39 Some(ShiftedIntRect { shifted, shift })
40 }
41
42 pub fn shifted(&self) -> &ScreenIntRect {
43 &self.shifted
44 }
45
46 pub fn recover(&self) -> ScreenIntRect {
47 ScreenIntRect::from_xywh(
48 self.shifted.x() >> self.shift,
49 self.shifted.y() >> self.shift,
50 self.shifted.width() >> self.shift,
51 self.shifted.height() >> self.shift,
52 )
53 .unwrap() // cannot fail, because the original rect was valid
54 }
55}
56
57pub struct BasicEdgeBuilder {
58 edges: Vec<Edge>,
59 clip_shift: i32,
60}
61
62impl BasicEdgeBuilder {
63 pub fn new(clip_shift: i32) -> Self {
64 BasicEdgeBuilder {
65 edges: Vec::with_capacity(64), // TODO: stack array + fallback
66 clip_shift,
67 }
68 }
69
70 // Skia returns a linked list here, but it's a nightmare to use in Rust,
71 // so we're mimicking it with Vec.
72 pub fn build_edges(
73 path: &Path,
74 clip: Option<&ShiftedIntRect>,
75 clip_shift: i32,
76 ) -> Option<Vec<Edge>> {
77 // If we're convex, then we need both edges, even if the right edge is past the clip.
78 // let can_cull_to_the_right = !path.isConvex();
79 let can_cull_to_the_right = false; // TODO: this
80
81 let mut builder = BasicEdgeBuilder::new(clip_shift);
82 if !builder.build(path, clip, can_cull_to_the_right) {
83 log::warn!("infinite or NaN segments detected during edges building");
84 return None;
85 }
86
87 if builder.edges.len() < 2 {
88 return None;
89 }
90
91 Some(builder.edges)
92 }
93
94 // TODO: build_poly
95 pub fn build(
96 &mut self,
97 path: &Path,
98 clip: Option<&ShiftedIntRect>,
99 can_cull_to_the_right: bool,
100 ) -> bool {
101 if let Some(clip) = clip {
102 let clip = clip.recover().to_rect();
103 for edges in EdgeClipperIter::new(path, clip, can_cull_to_the_right) {
104 for edge in edges {
105 match edge {
106 PathEdge::LineTo(p0, p1) => {
107 if !p0.is_finite() || !p1.is_finite() {
108 return false;
109 }
110
111 self.push_line(&[p0, p1])
112 }
113 PathEdge::QuadTo(p0, p1, p2) => {
114 if !p0.is_finite() || !p1.is_finite() || !p2.is_finite() {
115 return false;
116 }
117
118 self.push_quad(&[p0, p1, p2])
119 }
120 PathEdge::CubicTo(p0, p1, p2, p3) => {
121 if !p0.is_finite()
122 || !p1.is_finite()
123 || !p2.is_finite()
124 || !p3.is_finite()
125 {
126 return false;
127 }
128
129 self.push_cubic(&[p0, p1, p2, p3])
130 }
131 }
132 }
133 }
134 } else {
135 for edge in edge_iter(path) {
136 match edge {
137 PathEdge::LineTo(p0, p1) => {
138 self.push_line(&[p0, p1]);
139 }
140 PathEdge::QuadTo(p0, p1, p2) => {
141 let points = [p0, p1, p2];
142 let mut mono_x = [Point::zero(); 5];
143 let n = path_geometry::chop_quad_at_y_extrema(&points, &mut mono_x);
144 for i in 0..=n {
145 self.push_quad(&mono_x[i * 2..]);
146 }
147 }
148 PathEdge::CubicTo(p0, p1, p2, p3) => {
149 let points = [p0, p1, p2, p3];
150 let mut mono_y = [Point::zero(); 10];
151 let n = path_geometry::chop_cubic_at_y_extrema(&points, &mut mono_y);
152 for i in 0..=n {
153 self.push_cubic(&mono_y[i * 3..]);
154 }
155 }
156 }
157 }
158 }
159
160 true
161 }
162
163 fn push_line(&mut self, points: &[Point; 2]) {
164 if let Some(edge) = LineEdge::new(points[0], points[1], self.clip_shift) {
165 let combine = if edge.is_vertical() && !self.edges.is_empty() {
166 if let Some(Edge::Line(last)) = self.edges.last_mut() {
167 combine_vertical(&edge, last)
168 } else {
169 Combine::No
170 }
171 } else {
172 Combine::No
173 };
174
175 match combine {
176 Combine::Total => {
177 self.edges.pop();
178 }
179 Combine::Partial => {}
180 Combine::No => self.edges.push(Edge::Line(edge)),
181 }
182 }
183 }
184
185 fn push_quad(&mut self, points: &[Point]) {
186 if let Some(edge) = QuadraticEdge::new(points, self.clip_shift) {
187 self.edges.push(Edge::Quadratic(edge));
188 }
189 }
190
191 fn push_cubic(&mut self, points: &[Point]) {
192 if let Some(edge) = CubicEdge::new(points, self.clip_shift) {
193 self.edges.push(Edge::Cubic(edge));
194 }
195 }
196}
197
198fn combine_vertical(edge: &LineEdge, last: &mut LineEdge) -> Combine {
199 if last.dx != 0 || edge.x != last.x {
200 return Combine::No;
201 }
202
203 if edge.winding == last.winding {
204 return if edge.last_y + 1 == last.first_y {
205 last.first_y = edge.first_y;
206 Combine::Partial
207 } else if edge.first_y == last.last_y + 1 {
208 last.last_y = edge.last_y;
209 Combine::Partial
210 } else {
211 Combine::No
212 };
213 }
214
215 if edge.first_y == last.first_y {
216 return if edge.last_y == last.last_y {
217 Combine::Total
218 } else if edge.last_y < last.last_y {
219 last.first_y = edge.last_y + 1;
220 Combine::Partial
221 } else {
222 last.first_y = last.last_y + 1;
223 last.last_y = edge.last_y;
224 last.winding = edge.winding;
225 Combine::Partial
226 };
227 }
228
229 if edge.last_y == last.last_y {
230 if edge.first_y > last.first_y {
231 last.last_y = edge.first_y - 1;
232 } else {
233 last.last_y = last.first_y - 1;
234 last.first_y = edge.first_y;
235 last.winding = edge.winding;
236 }
237
238 return Combine::Partial;
239 }
240
241 Combine::No
242}
243
244pub fn edge_iter(path: &Path) -> PathEdgeIter {
245 PathEdgeIter {
246 path,
247 verb_index: 0,
248 points_index: 0,
249 move_to: Point::zero(),
250 needs_close_line: false,
251 }
252}
253
254#[derive(Copy, Clone, PartialEq, Debug)]
255pub enum PathEdge {
256 LineTo(Point, Point),
257 QuadTo(Point, Point, Point),
258 CubicTo(Point, Point, Point, Point),
259}
260
261/// Lightweight variant of PathIter that only returns segments (e.g. lines/quads).
262///
263/// Does not return Move or Close. Always "auto-closes" each contour.
264pub struct PathEdgeIter<'a> {
265 path: &'a Path,
266 verb_index: usize,
267 points_index: usize,
268 move_to: Point,
269 needs_close_line: bool,
270}
271
272impl<'a> PathEdgeIter<'a> {
273 fn close_line(&mut self) -> Option<PathEdge> {
274 self.needs_close_line = false;
275
276 let edge: PathEdge = PathEdge::LineTo(self.path.points()[self.points_index - 1], self.move_to);
277 Some(edge)
278 }
279}
280
281impl<'a> Iterator for PathEdgeIter<'a> {
282 type Item = PathEdge;
283
284 fn next(&mut self) -> Option<Self::Item> {
285 if self.verb_index < self.path.verbs().len() {
286 let verb = self.path.verbs()[self.verb_index];
287 self.verb_index += 1;
288
289 match verb {
290 PathVerb::Move => {
291 if self.needs_close_line {
292 let res = self.close_line();
293 self.move_to = self.path.points()[self.points_index];
294 self.points_index += 1;
295 return res;
296 }
297
298 self.move_to = self.path.points()[self.points_index];
299 self.points_index += 1;
300 self.next()
301 }
302 PathVerb::Close => {
303 if self.needs_close_line {
304 return self.close_line();
305 }
306
307 self.next()
308 }
309 _ => {
310 // Actual edge.
311 self.needs_close_line = true;
312
313 let edge;
314 match verb {
315 PathVerb::Line => {
316 edge = PathEdge::LineTo(
317 self.path.points()[self.points_index - 1],
318 self.path.points()[self.points_index + 0],
319 );
320 self.points_index += 1;
321 }
322 PathVerb::Quad => {
323 edge = PathEdge::QuadTo(
324 self.path.points()[self.points_index - 1],
325 self.path.points()[self.points_index + 0],
326 self.path.points()[self.points_index + 1],
327 );
328 self.points_index += 2;
329 }
330 PathVerb::Cubic => {
331 edge = PathEdge::CubicTo(
332 self.path.points()[self.points_index - 1],
333 self.path.points()[self.points_index + 0],
334 self.path.points()[self.points_index + 1],
335 self.path.points()[self.points_index + 2],
336 );
337 self.points_index += 3;
338 }
339 _ => unreachable!(),
340 };
341
342 Some(edge)
343 }
344 }
345 } else if self.needs_close_line {
346 self.close_line()
347 } else {
348 None
349 }
350 }
351}
352