1// Copyright 2009 The Android Open Source Project
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 arrayvec::ArrayVec;
8
9use tiny_skia_path::{NormalizedF32Exclusive, SCALAR_MAX};
10
11use crate::{Path, Point, Rect};
12
13use crate::edge_builder::{edge_iter, PathEdge, PathEdgeIter};
14use crate::line_clipper;
15use crate::path_geometry;
16
17#[cfg(all(not(feature = "std"), feature = "no-std-float"))]
18use tiny_skia_path::NoStdFloat;
19
20// This is a fail-safe `arr[n..n+3].try_into().unwrap()` alternative.
21// Everything is checked at compile-time so there is no bound checking and panics.
22macro_rules! copy_3_points {
23 ($arr:expr, $i:expr) => {
24 [$arr[$i], $arr[$i + 1], $arr[$i + 2]]
25 };
26}
27
28macro_rules! copy_4_points {
29 ($arr:expr, $i:expr) => {
30 [$arr[$i], $arr[$i + 1], $arr[$i + 2], $arr[$i + 3]]
31 };
32}
33
34/// Max curvature in X and Y split cubic into 9 pieces, * (line + cubic).
35const MAX_VERBS: usize = 18;
36
37pub type ClippedEdges = ArrayVec<PathEdge, MAX_VERBS>;
38
39pub struct EdgeClipper {
40 clip: Rect,
41 can_cull_to_the_right: bool,
42 edges: ClippedEdges,
43}
44
45impl EdgeClipper {
46 fn new(clip: Rect, can_cull_to_the_right: bool) -> Self {
47 EdgeClipper {
48 clip,
49 can_cull_to_the_right,
50 edges: ArrayVec::new(),
51 }
52 }
53
54 fn clip_line(mut self, p0: Point, p1: Point) -> Option<ClippedEdges> {
55 let mut points = [Point::zero(); line_clipper::MAX_POINTS];
56 let points = line_clipper::clip(
57 &[p0, p1],
58 &self.clip,
59 self.can_cull_to_the_right,
60 &mut points,
61 );
62 if !points.is_empty() {
63 for i in 0..points.len() - 1 {
64 self.push_line(points[i], points[i + 1]);
65 }
66 }
67
68 if self.edges.is_empty() {
69 None
70 } else {
71 Some(self.edges)
72 }
73 }
74
75 fn push_line(&mut self, p0: Point, p1: Point) {
76 self.edges.push(PathEdge::LineTo(p0, p1));
77 }
78
79 fn push_vline(&mut self, x: f32, mut y0: f32, mut y1: f32, reverse: bool) {
80 if reverse {
81 core::mem::swap(&mut y0, &mut y1);
82 }
83
84 self.edges.push(PathEdge::LineTo(
85 Point::from_xy(x, y0),
86 Point::from_xy(x, y1),
87 ));
88 }
89
90 fn clip_quad(mut self, p0: Point, p1: Point, p2: Point) -> Option<ClippedEdges> {
91 let pts = [p0, p1, p2];
92 let bounds = Rect::from_points(&pts)?;
93
94 if !quick_reject(&bounds, &self.clip) {
95 let mut mono_y = [Point::zero(); 5];
96 let count_y = path_geometry::chop_quad_at_y_extrema(&pts, &mut mono_y);
97 for y in 0..=count_y {
98 let mut mono_x = [Point::zero(); 5];
99 let y_points: [Point; 3] = copy_3_points!(mono_y, y * 2);
100 let count_x = path_geometry::chop_quad_at_x_extrema(&y_points, &mut mono_x);
101 for x in 0..=count_x {
102 let x_points: [Point; 3] = copy_3_points!(mono_x, x * 2);
103 self.clip_mono_quad(&x_points);
104 }
105 }
106 }
107
108 if self.edges.is_empty() {
109 None
110 } else {
111 Some(self.edges)
112 }
113 }
114
115 // src[] must be monotonic in X and Y
116 fn clip_mono_quad(&mut self, src: &[Point; 3]) {
117 let mut pts = [Point::zero(); 3];
118 let mut reverse = sort_increasing_y(src, &mut pts);
119
120 // are we completely above or below
121 if pts[2].y <= self.clip.top() || pts[0].y >= self.clip.bottom() {
122 return;
123 }
124
125 // Now chop so that pts is contained within clip in Y
126 chop_quad_in_y(&self.clip, &mut pts);
127
128 if pts[0].x > pts[2].x {
129 pts.swap(0, 2);
130 reverse = !reverse;
131 }
132 debug_assert!(pts[0].x <= pts[1].x);
133 debug_assert!(pts[1].x <= pts[2].x);
134
135 // Now chop in X has needed, and record the segments
136
137 if pts[2].x <= self.clip.left() {
138 // wholly to the left
139 self.push_vline(self.clip.left(), pts[0].y, pts[2].y, reverse);
140 return;
141 }
142
143 if pts[0].x >= self.clip.right() {
144 // wholly to the right
145 if !self.can_cull_to_the_right {
146 self.push_vline(self.clip.right(), pts[0].y, pts[2].y, reverse);
147 }
148
149 return;
150 }
151
152 let mut t = NormalizedF32Exclusive::ANY;
153 let mut tmp = [Point::zero(); 5];
154
155 // are we partially to the left
156 if pts[0].x < self.clip.left() {
157 if chop_mono_quad_at_x(&pts, self.clip.left(), &mut t) {
158 path_geometry::chop_quad_at(&pts, t, &mut tmp);
159 self.push_vline(self.clip.left(), tmp[0].y, tmp[2].y, reverse);
160 // clamp to clean up imprecise numerics in the chop
161 tmp[2].x = self.clip.left();
162 tmp[3].x = tmp[3].x.max(self.clip.left());
163
164 pts[0] = tmp[2];
165 pts[1] = tmp[3];
166 } else {
167 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
168 // so we just clamp against the left
169 self.push_vline(self.clip.left(), pts[0].y, pts[2].y, reverse);
170 return;
171 }
172 }
173
174 // are we partially to the right
175 if pts[2].x > self.clip.right() {
176 if chop_mono_quad_at_x(&pts, self.clip.right(), &mut t) {
177 path_geometry::chop_quad_at(&pts, t, &mut tmp);
178 // clamp to clean up imprecise numerics in the chop
179 tmp[1].x = tmp[1].x.min(self.clip.right());
180 tmp[2].x = self.clip.right();
181
182 self.push_quad(&copy_3_points!(tmp, 0), reverse);
183 self.push_vline(self.clip.right(), tmp[2].y, tmp[4].y, reverse);
184 } else {
185 // if chopMonoQuadAtY failed, then we may have hit inexact numerics
186 // so we just clamp against the right
187 pts[1].x = pts[1].x.min(self.clip.right());
188 pts[2].x = pts[2].x.min(self.clip.right());
189 self.push_quad(&pts, reverse);
190 }
191 } else {
192 // wholly inside the clip
193 self.push_quad(&pts, reverse);
194 }
195 }
196
197 fn push_quad(&mut self, pts: &[Point; 3], reverse: bool) {
198 if reverse {
199 self.edges.push(PathEdge::QuadTo(pts[2], pts[1], pts[0]));
200 } else {
201 self.edges.push(PathEdge::QuadTo(pts[0], pts[1], pts[2]));
202 }
203 }
204
205 fn clip_cubic(mut self, p0: Point, p1: Point, p2: Point, p3: Point) -> Option<ClippedEdges> {
206 let pts = [p0, p1, p2, p3];
207 let bounds = Rect::from_points(&pts)?;
208
209 // check if we're clipped out vertically
210 if bounds.bottom() > self.clip.top() && bounds.top() < self.clip.bottom() {
211 if too_big_for_reliable_float_math(&bounds) {
212 // can't safely clip the cubic, so we give up and draw a line (which we can safely clip)
213 //
214 // If we rewrote chopcubicat*extrema and chopmonocubic using doubles, we could very
215 // likely always handle the cubic safely, but (it seems) at a big loss in speed, so
216 // we'd only want to take that alternate impl if needed.
217 return self.clip_line(p0, p3);
218 } else {
219 let mut mono_y = [Point::zero(); 10];
220 let count_y = path_geometry::chop_cubic_at_y_extrema(&pts, &mut mono_y);
221 for y in 0..=count_y {
222 let mut mono_x = [Point::zero(); 10];
223 let y_points: [Point; 4] = copy_4_points!(mono_y, y * 3);
224 let count_x = path_geometry::chop_cubic_at_x_extrema(&y_points, &mut mono_x);
225 for x in 0..=count_x {
226 let x_points: [Point; 4] = copy_4_points!(mono_x, x * 3);
227 self.clip_mono_cubic(&x_points);
228 }
229 }
230 }
231 }
232
233 if self.edges.is_empty() {
234 None
235 } else {
236 Some(self.edges)
237 }
238 }
239
240 // src[] must be monotonic in X and Y
241 fn clip_mono_cubic(&mut self, src: &[Point; 4]) {
242 let mut pts = [Point::zero(); 4];
243 let mut reverse = sort_increasing_y(src, &mut pts);
244
245 // are we completely above or below
246 if pts[3].y <= self.clip.top() || pts[0].y >= self.clip.bottom() {
247 return;
248 }
249
250 // Now chop so that pts is contained within clip in Y
251 chop_cubic_in_y(&self.clip, &mut pts);
252
253 if pts[0].x > pts[3].x {
254 pts.swap(0, 3);
255 pts.swap(1, 2);
256 reverse = !reverse;
257 }
258
259 // Now chop in X has needed, and record the segments
260
261 if pts[3].x <= self.clip.left() {
262 // wholly to the left
263 self.push_vline(self.clip.left(), pts[0].y, pts[3].y, reverse);
264 return;
265 }
266
267 if pts[0].x >= self.clip.right() {
268 // wholly to the right
269 if !self.can_cull_to_the_right {
270 self.push_vline(self.clip.right(), pts[0].y, pts[3].y, reverse);
271 }
272
273 return;
274 }
275
276 // are we partially to the left
277 if pts[0].x < self.clip.left() {
278 let mut tmp = [Point::zero(); 7];
279 chop_mono_cubic_at_x(&pts, self.clip.left(), &mut tmp);
280 self.push_vline(self.clip.left(), tmp[0].y, tmp[3].y, reverse);
281
282 // tmp[3, 4].fX should all be to the right of clip.left().
283 // Since we can't trust the numerics of
284 // the chopper, we force those conditions now
285 tmp[3].x = self.clip.left();
286 tmp[4].x = tmp[4].x.max(self.clip.left());
287
288 pts[0] = tmp[3];
289 pts[1] = tmp[4];
290 pts[2] = tmp[5];
291 }
292
293 // are we partially to the right
294 if pts[3].x > self.clip.right() {
295 let mut tmp = [Point::zero(); 7];
296 chop_mono_cubic_at_x(&pts, self.clip.right(), &mut tmp);
297 tmp[3].x = self.clip.right();
298 tmp[2].x = tmp[2].x.min(self.clip.right());
299
300 self.push_cubic(&copy_4_points!(tmp, 0), reverse);
301 self.push_vline(self.clip.right(), tmp[3].y, tmp[6].y, reverse);
302 } else {
303 // wholly inside the clip
304 self.push_cubic(&pts, reverse);
305 }
306 }
307
308 fn push_cubic(&mut self, pts: &[Point; 4], reverse: bool) {
309 if reverse {
310 self.edges
311 .push(PathEdge::CubicTo(pts[3], pts[2], pts[1], pts[0]));
312 } else {
313 self.edges
314 .push(PathEdge::CubicTo(pts[0], pts[1], pts[2], pts[3]));
315 }
316 }
317}
318
319pub struct EdgeClipperIter<'a> {
320 edge_iter: PathEdgeIter<'a>,
321 clip: Rect,
322 can_cull_to_the_right: bool,
323}
324
325impl<'a> EdgeClipperIter<'a> {
326 pub fn new(path: &'a Path, clip: Rect, can_cull_to_the_right: bool) -> Self {
327 EdgeClipperIter {
328 edge_iter: edge_iter(path),
329 clip,
330 can_cull_to_the_right,
331 }
332 }
333}
334
335impl Iterator for EdgeClipperIter<'_> {
336 type Item = ClippedEdges;
337
338 fn next(&mut self) -> Option<Self::Item> {
339 for edge in &mut self.edge_iter {
340 let clipper = EdgeClipper::new(self.clip, self.can_cull_to_the_right);
341
342 match edge {
343 PathEdge::LineTo(p0, p1) => {
344 if let Some(edges) = clipper.clip_line(p0, p1) {
345 return Some(edges);
346 }
347 }
348 PathEdge::QuadTo(p0, p1, p2) => {
349 if let Some(edges) = clipper.clip_quad(p0, p1, p2) {
350 return Some(edges);
351 }
352 }
353 PathEdge::CubicTo(p0, p1, p2, p3) => {
354 if let Some(edges) = clipper.clip_cubic(p0, p1, p2, p3) {
355 return Some(edges);
356 }
357 }
358 }
359 }
360
361 None
362 }
363}
364
365fn quick_reject(bounds: &Rect, clip: &Rect) -> bool {
366 bounds.top() >= clip.bottom() || bounds.bottom() <= clip.top()
367}
368
369// src[] must be monotonic in Y. This routine copies src into dst, and sorts
370// it to be increasing in Y. If it had to reverse the order of the points,
371// it returns true, otherwise it returns false
372fn sort_increasing_y(src: &[Point], dst: &mut [Point]) -> bool {
373 // We need the data to be monotonically increasing in Y.
374 // Never fails, because src is always non-empty.
375 if src[0].y > src.last().unwrap().y {
376 for (i: usize, p: &Point) in src.iter().rev().enumerate() {
377 dst[i] = *p;
378 }
379
380 true
381 } else {
382 dst[0..src.len()].copy_from_slice(src);
383 false
384 }
385}
386
387/// Modifies pts[] in place so that it is clipped in Y to the clip rect.
388fn chop_quad_in_y(clip: &Rect, pts: &mut [Point; 3]) {
389 let mut t = NormalizedF32Exclusive::ANY;
390 let mut tmp = [Point::zero(); 5];
391
392 // are we partially above
393 if pts[0].y < clip.top() {
394 if chop_mono_quad_at_y(pts, clip.top(), &mut t) {
395 // take the 2nd chopped quad
396 path_geometry::chop_quad_at(pts, t, &mut tmp);
397 // clamp to clean up imprecise numerics in the chop
398 tmp[2].y = clip.top();
399 tmp[3].y = tmp[3].y.max(clip.top());
400
401 pts[0] = tmp[2];
402 pts[1] = tmp[3];
403 } else {
404 // if chop_mono_quad_at_y failed, then we may have hit inexact numerics
405 // so we just clamp against the top
406 for p in pts.iter_mut() {
407 if p.y < clip.top() {
408 p.y = clip.top();
409 }
410 }
411 }
412 }
413
414 // are we partially below
415 if pts[2].y > clip.bottom() {
416 if chop_mono_quad_at_y(pts, clip.bottom(), &mut t) {
417 path_geometry::chop_quad_at(pts, t, &mut tmp);
418 // clamp to clean up imprecise numerics in the chop
419 tmp[1].y = tmp[1].y.min(clip.bottom());
420 tmp[2].y = clip.bottom();
421
422 pts[1] = tmp[1];
423 pts[2] = tmp[2];
424 } else {
425 // if chop_mono_quad_at_y failed, then we may have hit inexact numerics
426 // so we just clamp against the bottom
427 for p in pts.iter_mut() {
428 if p.y > clip.bottom() {
429 p.y = clip.bottom();
430 }
431 }
432 }
433 }
434}
435
436fn chop_mono_quad_at_x(pts: &[Point; 3], x: f32, t: &mut NormalizedF32Exclusive) -> bool {
437 chop_mono_quad_at(c0:pts[0].x, c1:pts[1].x, c2:pts[2].x, target:x, t)
438}
439
440fn chop_mono_quad_at_y(pts: &[Point; 3], y: f32, t: &mut NormalizedF32Exclusive) -> bool {
441 chop_mono_quad_at(c0:pts[0].y, c1:pts[1].y, c2:pts[2].y, target:y, t)
442}
443
444fn chop_mono_quad_at(
445 c0: f32,
446 c1: f32,
447 c2: f32,
448 target: f32,
449 t: &mut NormalizedF32Exclusive,
450) -> bool {
451 // Solve F(t) = y where F(t) := [0](1-t)^2 + 2[1]t(1-t) + [2]t^2
452 // We solve for t, using quadratic equation, hence we have to rearrange
453 // our coefficients to look like At^2 + Bt + C
454 let a: f32 = c0 - c1 - c1 + c2;
455 let b: f32 = 2.0 * (c1 - c0);
456 let c: f32 = c0 - target;
457
458 let mut roots: [NormalizedF32Exclusive; 3] = path_geometry::new_t_values();
459 let count: usize = path_geometry::find_unit_quad_roots(a, b, c, &mut roots);
460 if count != 0 {
461 *t = roots[0];
462 true
463 } else {
464 false
465 }
466}
467
468fn too_big_for_reliable_float_math(r: &Rect) -> bool {
469 // limit set as the largest float value for which we can still reliably compute things like
470 // - chopping at XY extrema
471 // - chopping at Y or X values for clipping
472 //
473 // Current value chosen just by experiment. Larger (and still succeeds) is always better.
474
475 let limit: f32 = (1 << 22) as f32;
476 r.left() < -limit || r.top() < -limit || r.right() > limit || r.bottom() > limit
477}
478
479/// Modifies pts[] in place so that it is clipped in Y to the clip rect.
480fn chop_cubic_in_y(clip: &Rect, pts: &mut [Point; 4]) {
481 // are we partially above
482 if pts[0].y < clip.top() {
483 let mut tmp = [Point::zero(); 7];
484 chop_mono_cubic_at_y(pts, clip.top(), &mut tmp);
485
486 // For a large range in the points, we can do a poor job of chopping, such that the t
487 // we computed resulted in the lower cubic still being partly above the clip.
488 //
489 // If just the first or first 2 Y values are above the fTop, we can just smash them
490 // down. If the first 3 Ys are above fTop, we can't smash all 3, as that can really
491 // distort the cubic. In this case, we take the first output (tmp[3..6] and treat it as
492 // a guess, and re-chop against fTop. Then we fall through to checking if we need to
493 // smash the first 1 or 2 Y values.
494 if tmp[3].y < clip.top() && tmp[4].y < clip.top() && tmp[5].y < clip.top() {
495 let tmp2: [Point; 4] = copy_4_points!(tmp, 3);
496 chop_mono_cubic_at_y(&tmp2, clip.top(), &mut tmp);
497 }
498
499 // tmp[3, 4].y should all be to the below clip.fTop.
500 // Since we can't trust the numerics of the chopper, we force those conditions now
501 tmp[3].y = clip.top();
502 tmp[4].y = tmp[4].y.max(clip.top());
503
504 pts[0] = tmp[3];
505 pts[1] = tmp[4];
506 pts[2] = tmp[5];
507 }
508
509 // are we partially below
510 if pts[3].y > clip.bottom() {
511 let mut tmp = [Point::zero(); 7];
512 chop_mono_cubic_at_y(pts, clip.bottom(), &mut tmp);
513 tmp[3].y = clip.bottom();
514 tmp[2].y = tmp[2].y.min(clip.bottom());
515
516 pts[1] = tmp[1];
517 pts[2] = tmp[2];
518 pts[3] = tmp[3];
519 }
520}
521
522fn chop_mono_cubic_at_x(src: &[Point; 4], x: f32, dst: &mut [Point; 7]) {
523 if path_geometry::chop_mono_cubic_at_x(src, x, dst) {
524 return;
525 }
526
527 let src_values: [f32; 4] = [src[0].x, src[1].x, src[2].x, src[3].x];
528 path_geometry::chop_cubic_at2(src, mono_cubic_closest_t(&src_values, x), dst);
529}
530
531fn chop_mono_cubic_at_y(src: &[Point; 4], y: f32, dst: &mut [Point; 7]) {
532 if path_geometry::chop_mono_cubic_at_y(src, y, dst) {
533 return;
534 }
535
536 let src_values: [f32; 4] = [src[0].y, src[1].y, src[2].y, src[3].y];
537 path_geometry::chop_cubic_at2(src, mono_cubic_closest_t(&src_values, x:y), dst);
538}
539
540fn mono_cubic_closest_t(src: &[f32; 4], mut x: f32) -> NormalizedF32Exclusive {
541 let mut t = 0.5;
542 let mut last_t;
543 let mut best_t = t;
544 let mut step = 0.25;
545 let d = src[0];
546 let a = src[3] + 3.0 * (src[1] - src[2]) - d;
547 let b = 3.0 * (src[2] - src[1] - src[1] + d);
548 let c = 3.0 * (src[1] - d);
549 x -= d;
550 let mut closest = SCALAR_MAX;
551 loop {
552 let loc = ((a * t + b) * t + c) * t;
553 let dist = (loc - x).abs();
554 if closest > dist {
555 closest = dist;
556 best_t = t;
557 }
558
559 last_t = t;
560 t += if loc < x { step } else { -step };
561 step *= 0.5;
562
563 if !(closest > 0.25 && last_t != t) {
564 break;
565 }
566 }
567
568 NormalizedF32Exclusive::new(best_t).unwrap()
569}
570