1// Copyright 2014 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
7// This module is a mix of SkDashPath, SkDashPathEffect, SkContourMeasure and SkPathMeasure.
8
9use alloc::vec::Vec;
10
11use arrayref::array_ref;
12
13use crate::{Path, Point};
14
15use crate::floating_point::{FiniteF32, NonZeroPositiveF32, NormalizedF32, NormalizedF32Exclusive};
16use crate::path::{PathSegment, PathSegmentsIter, PathVerb};
17use crate::path_builder::PathBuilder;
18use crate::path_geometry;
19use crate::scalar::Scalar;
20
21#[cfg(all(not(feature = "std"), feature = "no-std-float"))]
22use crate::NoStdFloat;
23
24/// A stroke dashing properties.
25///
26/// Contains an array of pairs, where the first number indicates an "on" interval
27/// and the second one indicates an "off" interval;
28/// a dash offset value and internal properties.
29///
30/// # Guarantees
31///
32/// - The dash array always have an even number of values.
33/// - All dash array values are finite and >= 0.
34/// - There is at least two dash array values.
35/// - The sum of all dash array values is positive and finite.
36/// - Dash offset is finite.
37#[derive(Clone, PartialEq, Debug)]
38pub struct StrokeDash {
39 array: Vec<f32>,
40 offset: f32,
41 interval_len: NonZeroPositiveF32,
42 first_len: f32, // TODO: PositiveF32
43 first_index: usize,
44}
45
46impl StrokeDash {
47 /// Creates a new stroke dashing object.
48 pub fn new(dash_array: Vec<f32>, dash_offset: f32) -> Option<Self> {
49 let dash_offset = FiniteF32::new(dash_offset)?;
50
51 if dash_array.len() < 2 || dash_array.len() % 2 != 0 {
52 return None;
53 }
54
55 if dash_array.iter().any(|n| *n < 0.0) {
56 return None;
57 }
58
59 let interval_len: f32 = dash_array.iter().sum();
60 let interval_len = NonZeroPositiveF32::new(interval_len)?;
61
62 let dash_offset = adjust_dash_offset(dash_offset.get(), interval_len.get());
63 debug_assert!(dash_offset >= 0.0);
64 debug_assert!(dash_offset < interval_len.get());
65
66 let (first_len, first_index) = find_first_interval(&dash_array, dash_offset);
67 debug_assert!(first_len >= 0.0);
68 debug_assert!(first_index < dash_array.len());
69
70 Some(StrokeDash {
71 array: dash_array,
72 offset: dash_offset,
73 interval_len,
74 first_len,
75 first_index,
76 })
77 }
78}
79
80#[cfg(test)]
81mod tests {
82 use super::*;
83 use alloc::vec;
84
85 #[test]
86 fn test() {
87 assert_eq!(StrokeDash::new(vec![], 0.0), None);
88 assert_eq!(StrokeDash::new(vec![1.0], 0.0), None);
89 assert_eq!(StrokeDash::new(vec![1.0, 2.0, 3.0], 0.0), None);
90 assert_eq!(StrokeDash::new(vec![1.0, -2.0], 0.0), None);
91 assert_eq!(StrokeDash::new(vec![0.0, 0.0], 0.0), None);
92 assert_eq!(StrokeDash::new(vec![1.0, -1.0], 0.0), None);
93 assert_eq!(StrokeDash::new(vec![1.0, 1.0], f32::INFINITY), None);
94 assert_eq!(StrokeDash::new(vec![1.0, f32::INFINITY], 0.0), None);
95 }
96
97 #[test]
98 fn bug_26() {
99 let mut pb = PathBuilder::new();
100 pb.move_to(665.54, 287.3);
101 pb.line_to(675.67, 273.04);
102 pb.line_to(675.52, 271.32);
103 pb.line_to(674.79, 269.61);
104 pb.line_to(674.05, 268.04);
105 pb.line_to(672.88, 266.47);
106 pb.line_to(671.27, 264.9);
107 let path = pb.finish().unwrap();
108
109 let stroke_dash = StrokeDash::new(vec![6.0, 4.5], 0.0).unwrap();
110
111 assert!(path.dash(&stroke_dash, 1.0).is_some());
112 }
113}
114
115// Adjust phase to be between 0 and len, "flipping" phase if negative.
116// e.g., if len is 100, then phase of -20 (or -120) is equivalent to 80.
117fn adjust_dash_offset(mut offset: f32, len: f32) -> f32 {
118 if offset < 0.0 {
119 offset = -offset;
120 if offset > len {
121 offset %= len;
122 }
123
124 offset = len - offset;
125
126 // Due to finite precision, it's possible that phase == len,
127 // even after the subtract (if len >>> phase), so fix that here.
128 debug_assert!(offset <= len);
129 if offset == len {
130 offset = 0.0;
131 }
132
133 offset
134 } else if offset >= len {
135 offset % len
136 } else {
137 offset
138 }
139}
140
141fn find_first_interval(dash_array: &[f32], mut dash_offset: f32) -> (f32, usize) {
142 for (i: usize, gap: f32) in dash_array.iter().copied().enumerate() {
143 if dash_offset > gap || (dash_offset == gap && gap != 0.0) {
144 dash_offset -= gap;
145 } else {
146 return (gap - dash_offset, i);
147 }
148 }
149
150 // If we get here, phase "appears" to be larger than our length. This
151 // shouldn't happen with perfect precision, but we can accumulate errors
152 // during the initial length computation (rounding can make our sum be too
153 // big or too small. In that event, we just have to eat the error here.
154 (dash_array[0], 0)
155}
156
157impl Path {
158 /// Converts the current path into a dashed one.
159 ///
160 /// `resolution_scale` can be obtained via
161 /// [`compute_resolution_scale`](crate::PathStroker::compute_resolution_scale).
162 ///
163 /// Returns `None` when more than 1_000_000 dashes had to be produced
164 /// or when the final path has an invalid bounding box.
165 pub fn dash(&self, dash: &StrokeDash, resolution_scale: f32) -> Option<Path> {
166 dash_impl(self, dash, res_scale:resolution_scale)
167 }
168}
169
170fn dash_impl(src: &Path, dash: &StrokeDash, res_scale: f32) -> Option<Path> {
171 // We do not support the `cull_path` branch here.
172 // Skia has a lot of code for cases when a path contains only a single zero-length line
173 // or when a path is a rect. Not sure why.
174 // We simply ignoring it for the sake of simplicity.
175
176 // We also doesn't support the `SpecialLineRec` case.
177 // I have no idea what the point in it.
178
179 fn is_even(x: usize) -> bool {
180 x % 2 == 0
181 }
182
183 let mut pb = PathBuilder::new();
184 let mut dash_count = 0.0;
185 for contour in ContourMeasureIter::new(src, res_scale) {
186 let mut skip_first_segment = contour.is_closed;
187 let mut added_segment = false;
188 let length = contour.length;
189 let mut index = dash.first_index;
190
191 // Since the path length / dash length ratio may be arbitrarily large, we can exert
192 // significant memory pressure while attempting to build the filtered path. To avoid this,
193 // we simply give up dashing beyond a certain threshold.
194 //
195 // The original bug report (http://crbug.com/165432) is based on a path yielding more than
196 // 90 million dash segments and crashing the memory allocator. A limit of 1 million
197 // segments seems reasonable: at 2 verbs per segment * 9 bytes per verb, this caps the
198 // maximum dash memory overhead at roughly 17MB per path.
199 const MAX_DASH_COUNT: usize = 1000000;
200 dash_count += length * (dash.array.len() >> 1) as f32 / dash.interval_len.get();
201 if dash_count > MAX_DASH_COUNT as f32 {
202 return None;
203 }
204
205 // Using double precision to avoid looping indefinitely due to single precision rounding
206 // (for extreme path_length/dash_length ratios). See test_infinite_dash() unittest.
207 let mut distance = 0.0;
208 let mut d_len = dash.first_len;
209
210 while distance < length {
211 debug_assert!(d_len >= 0.0);
212 added_segment = false;
213 if is_even(index) && !skip_first_segment {
214 added_segment = true;
215 contour.push_segment(distance, distance + d_len, true, &mut pb);
216 }
217
218 distance += d_len;
219
220 // clear this so we only respect it the first time around
221 skip_first_segment = false;
222
223 // wrap around our intervals array if necessary
224 index += 1;
225 debug_assert!(index <= dash.array.len());
226 if index == dash.array.len() {
227 index = 0;
228 }
229
230 // fetch our next d_len
231 d_len = dash.array[index];
232 }
233
234 // extend if we ended on a segment and we need to join up with the (skipped) initial segment
235 if contour.is_closed && is_even(dash.first_index) && dash.first_len >= 0.0 {
236 contour.push_segment(0.0, dash.first_len, !added_segment, &mut pb);
237 }
238 }
239
240 pb.finish()
241}
242
243const MAX_T_VALUE: u32 = 0x3FFFFFFF;
244
245struct ContourMeasureIter<'a> {
246 iter: PathSegmentsIter<'a>,
247 tolerance: f32,
248}
249
250impl<'a> ContourMeasureIter<'a> {
251 fn new(path: &'a Path, res_scale: f32) -> Self {
252 // can't use tangents, since we need [0..1..................2] to be seen
253 // as definitely not a line (it is when drawn, but not parametrically)
254 // so we compare midpoints
255 const CHEAP_DIST_LIMIT: f32 = 0.5; // just made this value up
256
257 ContourMeasureIter {
258 iter: path.segments(),
259 tolerance: CHEAP_DIST_LIMIT * res_scale.invert(),
260 }
261 }
262}
263
264impl Iterator for ContourMeasureIter<'_> {
265 type Item = ContourMeasure;
266
267 // If it encounters a zero-length contour, it is skipped.
268 fn next(&mut self) -> Option<Self::Item> {
269 // Note:
270 // as we accumulate distance, we have to check that the result of +=
271 // actually made it larger, since a very small delta might be > 0, but
272 // still have no effect on distance (if distance >>> delta).
273 //
274 // We do this check below, and in compute_quad_segs and compute_cubic_segs
275
276 let mut contour = ContourMeasure::default();
277
278 let mut point_index = 0;
279 let mut distance = 0.0;
280 let mut have_seen_close = false;
281 let mut prev_p = Point::zero();
282 while let Some(seg) = self.iter.next() {
283 match seg {
284 PathSegment::MoveTo(p0) => {
285 contour.points.push(p0);
286 prev_p = p0;
287 }
288 PathSegment::LineTo(p0) => {
289 let prev_d = distance;
290 distance = contour.compute_line_seg(prev_p, p0, distance, point_index);
291
292 if distance > prev_d {
293 contour.points.push(p0);
294 point_index += 1;
295 }
296
297 prev_p = p0;
298 }
299 PathSegment::QuadTo(p0, p1) => {
300 let prev_d = distance;
301 distance = contour.compute_quad_segs(
302 prev_p,
303 p0,
304 p1,
305 distance,
306 0,
307 MAX_T_VALUE,
308 point_index,
309 self.tolerance,
310 );
311
312 if distance > prev_d {
313 contour.points.push(p0);
314 contour.points.push(p1);
315 point_index += 2;
316 }
317
318 prev_p = p1;
319 }
320 PathSegment::CubicTo(p0, p1, p2) => {
321 let prev_d = distance;
322 distance = contour.compute_cubic_segs(
323 prev_p,
324 p0,
325 p1,
326 p2,
327 distance,
328 0,
329 MAX_T_VALUE,
330 point_index,
331 self.tolerance,
332 );
333
334 if distance > prev_d {
335 contour.points.push(p0);
336 contour.points.push(p1);
337 contour.points.push(p2);
338 point_index += 3;
339 }
340
341 prev_p = p2;
342 }
343 PathSegment::Close => {
344 have_seen_close = true;
345 }
346 }
347
348 // TODO: to contour iter?
349 if self.iter.next_verb() == Some(PathVerb::Move) {
350 break;
351 }
352 }
353
354 if !distance.is_finite() {
355 return None;
356 }
357
358 if have_seen_close {
359 let prev_d = distance;
360 let first_pt = contour.points[0];
361 distance = contour.compute_line_seg(
362 contour.points[point_index],
363 first_pt,
364 distance,
365 point_index,
366 );
367
368 if distance > prev_d {
369 contour.points.push(first_pt);
370 }
371 }
372
373 contour.length = distance;
374 contour.is_closed = have_seen_close;
375
376 if contour.points.is_empty() {
377 None
378 } else {
379 Some(contour)
380 }
381 }
382}
383
384#[derive(Copy, Clone, PartialEq, Debug)]
385enum SegmentType {
386 Line,
387 Quad,
388 Cubic,
389}
390
391#[derive(Copy, Clone, Debug)]
392struct Segment {
393 distance: f32, // total distance up to this point
394 point_index: usize, // index into the ContourMeasure::points array
395 t_value: u32,
396 kind: SegmentType,
397}
398
399impl Segment {
400 fn scalar_t(&self) -> f32 {
401 debug_assert!(self.t_value <= MAX_T_VALUE);
402 // 1/kMaxTValue can't be represented as a float, but it's close and the limits work fine.
403 const MAX_T_RECIPROCAL: f32 = 1.0 / MAX_T_VALUE as f32;
404 self.t_value as f32 * MAX_T_RECIPROCAL
405 }
406}
407
408#[derive(Default, Debug)]
409struct ContourMeasure {
410 segments: Vec<Segment>,
411 points: Vec<Point>,
412 length: f32,
413 is_closed: bool,
414}
415
416impl ContourMeasure {
417 fn push_segment(
418 &self,
419 mut start_d: f32,
420 mut stop_d: f32,
421 start_with_move_to: bool,
422 pb: &mut PathBuilder,
423 ) {
424 if start_d < 0.0 {
425 start_d = 0.0;
426 }
427
428 if stop_d > self.length {
429 stop_d = self.length;
430 }
431
432 if !(start_d <= stop_d) {
433 // catch NaN values as well
434 return;
435 }
436
437 if self.segments.is_empty() {
438 return;
439 }
440
441 let (seg_index, mut start_t) = match self.distance_to_segment(start_d) {
442 Some(v) => v,
443 None => return,
444 };
445 let mut seg = self.segments[seg_index];
446
447 let (stop_seg_index, stop_t) = match self.distance_to_segment(stop_d) {
448 Some(v) => v,
449 None => return,
450 };
451 let stop_seg = self.segments[stop_seg_index];
452
453 debug_assert!(stop_seg_index <= stop_seg_index);
454 let mut p = Point::zero();
455 if start_with_move_to {
456 compute_pos_tan(
457 &self.points[seg.point_index..],
458 seg.kind,
459 start_t,
460 Some(&mut p),
461 None,
462 );
463 pb.move_to(p.x, p.y);
464 }
465
466 if seg.point_index == stop_seg.point_index {
467 segment_to(
468 &self.points[seg.point_index..],
469 seg.kind,
470 start_t,
471 stop_t,
472 pb,
473 );
474 } else {
475 let mut new_seg_index = seg_index;
476 loop {
477 segment_to(
478 &self.points[seg.point_index..],
479 seg.kind,
480 start_t,
481 NormalizedF32::ONE,
482 pb,
483 );
484
485 let old_point_index = seg.point_index;
486 loop {
487 new_seg_index += 1;
488 if self.segments[new_seg_index].point_index != old_point_index {
489 break;
490 }
491 }
492 seg = self.segments[new_seg_index];
493
494 start_t = NormalizedF32::ZERO;
495
496 if seg.point_index >= stop_seg.point_index {
497 break;
498 }
499 }
500
501 segment_to(
502 &self.points[seg.point_index..],
503 seg.kind,
504 NormalizedF32::ZERO,
505 stop_t,
506 pb,
507 );
508 }
509 }
510
511 fn distance_to_segment(&self, distance: f32) -> Option<(usize, NormalizedF32)> {
512 debug_assert!(distance >= 0.0 && distance <= self.length);
513
514 let mut index = find_segment(&self.segments, distance);
515 // don't care if we hit an exact match or not, so we xor index if it is negative
516 index ^= index >> 31;
517 let index = index as usize;
518 let seg = self.segments[index];
519
520 // now interpolate t-values with the prev segment (if possible)
521 let mut start_t = 0.0;
522 let mut start_d = 0.0;
523 // check if the prev segment is legal, and references the same set of points
524 if index > 0 {
525 start_d = self.segments[index - 1].distance;
526 if self.segments[index - 1].point_index == seg.point_index {
527 debug_assert!(self.segments[index - 1].kind == seg.kind);
528 start_t = self.segments[index - 1].scalar_t();
529 }
530 }
531
532 debug_assert!(seg.scalar_t() > start_t);
533 debug_assert!(distance >= start_d);
534 debug_assert!(seg.distance > start_d);
535
536 let t =
537 start_t + (seg.scalar_t() - start_t) * (distance - start_d) / (seg.distance - start_d);
538 let t = NormalizedF32::new(t)?;
539 Some((index, t))
540 }
541
542 fn compute_line_seg(
543 &mut self,
544 p0: Point,
545 p1: Point,
546 mut distance: f32,
547 point_index: usize,
548 ) -> f32 {
549 let d = p0.distance(p1);
550 debug_assert!(d >= 0.0);
551 let prev_d = distance;
552 distance += d;
553 if distance > prev_d {
554 debug_assert!(point_index < self.points.len());
555 self.segments.push(Segment {
556 distance,
557 point_index,
558 t_value: MAX_T_VALUE,
559 kind: SegmentType::Line,
560 });
561 }
562
563 distance
564 }
565
566 fn compute_quad_segs(
567 &mut self,
568 p0: Point,
569 p1: Point,
570 p2: Point,
571 mut distance: f32,
572 min_t: u32,
573 max_t: u32,
574 point_index: usize,
575 tolerance: f32,
576 ) -> f32 {
577 if t_span_big_enough(max_t - min_t) != 0 && quad_too_curvy(p0, p1, p2, tolerance) {
578 let mut tmp = [Point::zero(); 5];
579 let half_t = (min_t + max_t) >> 1;
580
581 path_geometry::chop_quad_at(&[p0, p1, p2], NormalizedF32Exclusive::HALF, &mut tmp);
582 distance = self.compute_quad_segs(
583 tmp[0],
584 tmp[1],
585 tmp[2],
586 distance,
587 min_t,
588 half_t,
589 point_index,
590 tolerance,
591 );
592 distance = self.compute_quad_segs(
593 tmp[2],
594 tmp[3],
595 tmp[4],
596 distance,
597 half_t,
598 max_t,
599 point_index,
600 tolerance,
601 );
602 } else {
603 let d = p0.distance(p2);
604 let prev_d = distance;
605 distance += d;
606 if distance > prev_d {
607 debug_assert!(point_index < self.points.len());
608 self.segments.push(Segment {
609 distance,
610 point_index,
611 t_value: max_t,
612 kind: SegmentType::Quad,
613 });
614 }
615 }
616
617 distance
618 }
619
620 fn compute_cubic_segs(
621 &mut self,
622 p0: Point,
623 p1: Point,
624 p2: Point,
625 p3: Point,
626 mut distance: f32,
627 min_t: u32,
628 max_t: u32,
629 point_index: usize,
630 tolerance: f32,
631 ) -> f32 {
632 if t_span_big_enough(max_t - min_t) != 0 && cubic_too_curvy(p0, p1, p2, p3, tolerance) {
633 let mut tmp = [Point::zero(); 7];
634 let half_t = (min_t + max_t) >> 1;
635
636 path_geometry::chop_cubic_at2(
637 &[p0, p1, p2, p3],
638 NormalizedF32Exclusive::HALF,
639 &mut tmp,
640 );
641 distance = self.compute_cubic_segs(
642 tmp[0],
643 tmp[1],
644 tmp[2],
645 tmp[3],
646 distance,
647 min_t,
648 half_t,
649 point_index,
650 tolerance,
651 );
652 distance = self.compute_cubic_segs(
653 tmp[3],
654 tmp[4],
655 tmp[5],
656 tmp[6],
657 distance,
658 half_t,
659 max_t,
660 point_index,
661 tolerance,
662 );
663 } else {
664 let d = p0.distance(p3);
665 let prev_d = distance;
666 distance += d;
667 if distance > prev_d {
668 debug_assert!(point_index < self.points.len());
669 self.segments.push(Segment {
670 distance,
671 point_index,
672 t_value: max_t,
673 kind: SegmentType::Cubic,
674 });
675 }
676 }
677
678 distance
679 }
680}
681
682fn find_segment(base: &[Segment], key: f32) -> i32 {
683 let mut lo: u32 = 0u32;
684 let mut hi: u32 = (base.len() - 1) as u32;
685
686 while lo < hi {
687 let mid: u32 = (hi + lo) >> 1;
688 if base[mid as usize].distance < key {
689 lo = mid + 1;
690 } else {
691 hi = mid;
692 }
693 }
694
695 if base[hi as usize].distance < key {
696 hi += 1;
697 hi = !hi;
698 } else if key < base[hi as usize].distance {
699 hi = !hi;
700 }
701
702 hi as i32
703}
704
705fn compute_pos_tan(
706 points: &[Point],
707 seg_kind: SegmentType,
708 t: NormalizedF32,
709 pos: Option<&mut Point>,
710 tangent: Option<&mut Point>,
711) {
712 match seg_kind {
713 SegmentType::Line => {
714 if let Some(pos) = pos {
715 *pos = Point::from_xy(
716 interp(points[0].x, points[1].x, t),
717 interp(points[0].y, points[1].y, t),
718 );
719 }
720
721 if let Some(tangent) = tangent {
722 tangent.set_normalize(points[1].x - points[0].x, points[1].y - points[0].y);
723 }
724 }
725 SegmentType::Quad => {
726 let src = array_ref![points, 0, 3];
727 if let Some(pos) = pos {
728 *pos = path_geometry::eval_quad_at(src, t);
729 }
730
731 if let Some(tangent) = tangent {
732 *tangent = path_geometry::eval_quad_tangent_at(src, t);
733 tangent.normalize();
734 }
735 }
736 SegmentType::Cubic => {
737 let src = array_ref![points, 0, 4];
738 if let Some(pos) = pos {
739 *pos = path_geometry::eval_cubic_pos_at(src, t);
740 }
741
742 if let Some(tangent) = tangent {
743 *tangent = path_geometry::eval_cubic_tangent_at(src, t);
744 tangent.normalize();
745 }
746 }
747 }
748}
749
750fn segment_to(
751 points: &[Point],
752 seg_kind: SegmentType,
753 start_t: NormalizedF32,
754 stop_t: NormalizedF32,
755 pb: &mut PathBuilder,
756) {
757 debug_assert!(start_t <= stop_t);
758
759 if start_t == stop_t {
760 if let Some(pt) = pb.last_point() {
761 // If the dash as a zero-length on segment, add a corresponding zero-length line.
762 // The stroke code will add end caps to zero length lines as appropriate.
763 pb.line_to(pt.x, pt.y);
764 }
765
766 return;
767 }
768
769 match seg_kind {
770 SegmentType::Line => {
771 if stop_t == NormalizedF32::ONE {
772 pb.line_to(points[1].x, points[1].y);
773 } else {
774 pb.line_to(
775 interp(points[0].x, points[1].x, stop_t),
776 interp(points[0].y, points[1].y, stop_t),
777 );
778 }
779 }
780 SegmentType::Quad => {
781 let mut tmp0 = [Point::zero(); 5];
782 let mut tmp1 = [Point::zero(); 5];
783 if start_t == NormalizedF32::ZERO {
784 if stop_t == NormalizedF32::ONE {
785 pb.quad_to_pt(points[1], points[2]);
786 } else {
787 let stop_t = NormalizedF32Exclusive::new_bounded(stop_t.get());
788 path_geometry::chop_quad_at(points, stop_t, &mut tmp0);
789 pb.quad_to_pt(tmp0[1], tmp0[2]);
790 }
791 } else {
792 let start_tt = NormalizedF32Exclusive::new_bounded(start_t.get());
793 path_geometry::chop_quad_at(points, start_tt, &mut tmp0);
794 if stop_t == NormalizedF32::ONE {
795 pb.quad_to_pt(tmp0[3], tmp0[4]);
796 } else {
797 let new_t = (stop_t.get() - start_t.get()) / (1.0 - start_t.get());
798 let new_t = NormalizedF32Exclusive::new_bounded(new_t);
799 path_geometry::chop_quad_at(&tmp0[2..], new_t, &mut tmp1);
800 pb.quad_to_pt(tmp1[1], tmp1[2]);
801 }
802 }
803 }
804 SegmentType::Cubic => {
805 let mut tmp0 = [Point::zero(); 7];
806 let mut tmp1 = [Point::zero(); 7];
807 if start_t == NormalizedF32::ZERO {
808 if stop_t == NormalizedF32::ONE {
809 pb.cubic_to_pt(points[1], points[2], points[3]);
810 } else {
811 let stop_t = NormalizedF32Exclusive::new_bounded(stop_t.get());
812 path_geometry::chop_cubic_at2(array_ref![points, 0, 4], stop_t, &mut tmp0);
813 pb.cubic_to_pt(tmp0[1], tmp0[2], tmp0[3]);
814 }
815 } else {
816 let start_tt = NormalizedF32Exclusive::new_bounded(start_t.get());
817 path_geometry::chop_cubic_at2(array_ref![points, 0, 4], start_tt, &mut tmp0);
818 if stop_t == NormalizedF32::ONE {
819 pb.cubic_to_pt(tmp0[4], tmp0[5], tmp0[6]);
820 } else {
821 let new_t = (stop_t.get() - start_t.get()) / (1.0 - start_t.get());
822 let new_t = NormalizedF32Exclusive::new_bounded(new_t);
823 path_geometry::chop_cubic_at2(array_ref![tmp0, 3, 4], new_t, &mut tmp1);
824 pb.cubic_to_pt(tmp1[1], tmp1[2], tmp1[3]);
825 }
826 }
827 }
828 }
829}
830
831fn t_span_big_enough(t_span: u32) -> u32 {
832 debug_assert!(t_span <= MAX_T_VALUE);
833 t_span >> 10
834}
835
836fn quad_too_curvy(p0: Point, p1: Point, p2: Point, tolerance: f32) -> bool {
837 // diff = (a/4 + b/2 + c/4) - (a/2 + c/2)
838 // diff = -a/4 + b/2 - c/4
839 let dx: f32 = (p1.x).half() - (p0.x + p2.x).half().half();
840 let dy: f32 = (p1.y).half() - (p0.y + p2.y).half().half();
841
842 let dist: f32 = dx.abs().max(dy.abs());
843 dist > tolerance
844}
845
846fn cubic_too_curvy(p0: Point, p1: Point, p2: Point, p3: Point, tolerance: f32) -> bool {
847 let n0: bool = cheap_dist_exceeds_limit(
848 pt:p1,
849 x:interp_safe(p0.x, p3.x, 1.0 / 3.0),
850 y:interp_safe(a:p0.y, b:p3.y, t:1.0 / 3.0),
851 tolerance,
852 );
853
854 let n1: bool = cheap_dist_exceeds_limit(
855 pt:p2,
856 x:interp_safe(p0.x, p3.x, 2.0 / 3.0),
857 y:interp_safe(a:p0.y, b:p3.y, t:2.0 / 3.0),
858 tolerance,
859 );
860
861 n0 || n1
862}
863
864fn cheap_dist_exceeds_limit(pt: Point, x: f32, y: f32, tolerance: f32) -> bool {
865 let dist: f32 = (x - pt.x).abs().max((y - pt.y).abs());
866 // just made up the 1/2
867 dist > tolerance
868}
869
870/// Linearly interpolate between A and B, based on t.
871///
872/// If t is 0, return A. If t is 1, return B else interpolate.
873fn interp(a: f32, b: f32, t: NormalizedF32) -> f32 {
874 a + (b - a) * t.get()
875}
876
877fn interp_safe(a: f32, b: f32, t: f32) -> f32 {
878 debug_assert!(t >= 0.0 && t <= 1.0);
879 a + (b - a) * t
880}
881