1use crate::scalar::Scalar;
2use crate::CubicBezierSegment;
3///! Computes intersection parameters for two cubic bézier curves using bézier clipping, also known
4///! as fat line clipping.
5///!
6///! The implementation here was originally ported from that of paper.js:
7///! https://github.com/paperjs/paper.js/blob/0deddebb2c83ea2a0c848f7c8ba5e22fa7562a4e/src/path/Curve.js#L2008
8///! See "bézier Clipping method" in
9///! https://scholarsarchive.byu.edu/facpub/1/
10///! for motivation and details of how the process works.
11use crate::{point, Box2D, Point};
12use arrayvec::ArrayVec;
13use core::mem;
14use core::ops::Range;
15
16// Computes the intersections (if any) between two cubic bézier curves in the form of the `t`
17// parameters of each intersection point along the curves.
18//
19// Returns endpoint intersections where an endpoint intersects the interior of the other curve,
20// but not endpoint/endpoint intersections.
21//
22// Returns no intersections if either curve is a point or if the curves are parallel lines.
23pub fn cubic_bezier_intersections_t<S: Scalar>(
24 curve1: &CubicBezierSegment<S>,
25 curve2: &CubicBezierSegment<S>,
26) -> ArrayVec<(S, S), 9> {
27 if !curve1
28 .fast_bounding_box()
29 .intersects(&curve2.fast_bounding_box())
30 || curve1 == curve2
31 || (curve1.from == curve2.to
32 && curve1.ctrl1 == curve2.ctrl2
33 && curve1.ctrl2 == curve2.ctrl1
34 && curve1.to == curve2.from)
35 {
36 return ArrayVec::new();
37 }
38
39 let mut result = ArrayVec::new();
40
41 #[inline]
42 fn midpoint<S: Scalar>(point1: &Point<S>, point2: &Point<S>) -> Point<S> {
43 point(
44 (point1.x + point2.x) * S::HALF,
45 (point1.y + point2.y) * S::HALF,
46 )
47 }
48
49 let curve1_is_a_point = curve1.is_a_point(S::EPSILON);
50 let curve2_is_a_point = curve2.is_a_point(S::EPSILON);
51 if curve1_is_a_point && !curve2_is_a_point {
52 let point1 = midpoint(&curve1.from, &curve1.to);
53 let curve_params = point_curve_intersections(&point1, curve2, S::EPSILON);
54 for t in curve_params {
55 if t > S::EPSILON && t < S::ONE - S::EPSILON {
56 result.push((S::ZERO, t));
57 }
58 }
59 } else if !curve1_is_a_point && curve2_is_a_point {
60 let point2 = midpoint(&curve2.from, &curve2.to);
61 let curve_params = point_curve_intersections(&point2, curve1, S::EPSILON);
62 for t in curve_params {
63 if t > S::EPSILON && t < S::ONE - S::EPSILON {
64 result.push((t, S::ZERO));
65 }
66 }
67 }
68 if curve1_is_a_point || curve2_is_a_point {
69 // Caller is always responsible for checking endpoints and overlaps, in the case that both
70 // curves were points.
71 return result;
72 }
73
74 let linear1 = curve1.is_linear(S::EPSILON);
75 let linear2 = curve2.is_linear(S::EPSILON);
76 if linear1 && !linear2 {
77 result = line_curve_intersections(curve1, curve2, /* flip */ false);
78 } else if !linear1 && linear2 {
79 result = line_curve_intersections(curve2, curve1, /* flip */ true);
80 } else if linear1 && linear2 {
81 result = line_line_intersections(curve1, curve2);
82 } else {
83 add_curve_intersections(
84 curve1,
85 curve2,
86 &(S::ZERO..S::ONE),
87 &(S::ZERO..S::ONE),
88 &mut result,
89 /* flip */ false,
90 /* recursion_count */ 0,
91 /* call_count */ 0,
92 /* original curve1 */ curve1,
93 /* original curve2 */ curve2,
94 );
95 }
96
97 result
98}
99
100fn point_curve_intersections<S: Scalar>(
101 pt: &Point<S>,
102 curve: &CubicBezierSegment<S>,
103 epsilon: S,
104) -> ArrayVec<S, 9> {
105 let mut result = ArrayVec::new();
106
107 // (If both endpoints are epsilon close, we only return S::ZERO.)
108 if (*pt - curve.from).square_length() < epsilon {
109 result.push(S::ZERO);
110 return result;
111 }
112 if (*pt - curve.to).square_length() < epsilon {
113 result.push(S::ONE);
114 return result;
115 }
116
117 let curve_x_t_params = curve.solve_t_for_x(pt.x);
118 let curve_y_t_params = curve.solve_t_for_y(pt.y);
119 // We want to coalesce parameters representing the same intersection from the x and y
120 // directions, but the parameter calculations aren't very accurate, so give a little more
121 // leeway there (TODO: this isn't perfect, as you might expect - the dupes that pass here are
122 // currently being detected in add_intersection).
123 let param_eps = S::TEN * epsilon;
124 for params in [curve_x_t_params, curve_y_t_params].iter() {
125 for t in params {
126 let t = *t;
127 if (*pt - curve.sample(t)).square_length() > epsilon {
128 continue;
129 }
130 let mut already_found_t = false;
131 for u in &result {
132 if S::abs(t - *u) < param_eps {
133 already_found_t = true;
134 break;
135 }
136 }
137 if !already_found_t {
138 result.push(t);
139 }
140 }
141 }
142
143 if !result.is_empty() {
144 return result;
145 }
146
147 // The remaining case is if pt is within epsilon of an interior point of curve, but not within
148 // the x-range or y-range of the curve (which we already checked) - for example if curve is a
149 // horizontal line that extends beyond its endpoints, and pt is just outside an end of the line;
150 // or if the curve has a cusp in one of the corners of its convex hull and pt is
151 // diagonally just outside the hull. This is a rare case (could we even ignore it?).
152 #[inline]
153 fn maybe_add<S: Scalar>(
154 t: S,
155 pt: &Point<S>,
156 curve: &CubicBezierSegment<S>,
157 epsilon: S,
158 result: &mut ArrayVec<S, 9>,
159 ) -> bool {
160 if (curve.sample(t) - *pt).square_length() < epsilon {
161 result.push(t);
162 return true;
163 }
164 false
165 }
166
167 let _ = maybe_add(curve.x_minimum_t(), pt, curve, epsilon, &mut result)
168 || maybe_add(curve.x_maximum_t(), pt, curve, epsilon, &mut result)
169 || maybe_add(curve.y_minimum_t(), pt, curve, epsilon, &mut result)
170 || maybe_add(curve.y_maximum_t(), pt, curve, epsilon, &mut result);
171
172 result
173}
174
175fn line_curve_intersections<S: Scalar>(
176 line_as_curve: &CubicBezierSegment<S>,
177 curve: &CubicBezierSegment<S>,
178 flip: bool,
179) -> ArrayVec<(S, S), 9> {
180 let mut result: ArrayVec<(S, S), 9> = ArrayVec::new();
181 let baseline: LineSegment = line_as_curve.baseline();
182 let curve_intersections: ArrayVec = curve.line_intersections_t(&baseline.to_line());
183 let line_is_mostly_vertical: bool =
184 S::abs(self:baseline.from.y - baseline.to.y) >= S::abs(self:baseline.from.x - baseline.to.x);
185 for curve_t: S in curve_intersections {
186 let line_intersections: ArrayVec = if line_is_mostly_vertical {
187 let intersection_y: S = curve.y(curve_t);
188 line_as_curve.solve_t_for_y(intersection_y)
189 } else {
190 let intersection_x: S = curve.x(curve_t);
191 line_as_curve.solve_t_for_x(intersection_x)
192 };
193
194 for line_t: S in line_intersections {
195 add_intersection(t1:line_t, orig_curve1:line_as_curve, t2:curve_t, orig_curve2:curve, flip, &mut result);
196 }
197 }
198
199 result
200}
201
202fn line_line_intersections<S: Scalar>(
203 curve1: &CubicBezierSegment<S>,
204 curve2: &CubicBezierSegment<S>,
205) -> ArrayVec<(S, S), 9> {
206 let mut result = ArrayVec::new();
207
208 let intersection = curve1
209 .baseline()
210 .to_line()
211 .intersection(&curve2.baseline().to_line());
212 if intersection.is_none() {
213 return result;
214 }
215
216 let intersection = intersection.unwrap();
217
218 #[inline]
219 fn parameters_for_line_point<S: Scalar>(
220 curve: &CubicBezierSegment<S>,
221 pt: &Point<S>,
222 ) -> ArrayVec<S, 3> {
223 let line_is_mostly_vertical =
224 S::abs(curve.from.y - curve.to.y) >= S::abs(curve.from.x - curve.to.x);
225 if line_is_mostly_vertical {
226 curve.solve_t_for_y(pt.y)
227 } else {
228 curve.solve_t_for_x(pt.x)
229 }
230 }
231
232 let line1_params = parameters_for_line_point(curve1, &intersection);
233 if line1_params.is_empty() {
234 return result;
235 }
236
237 let line2_params = parameters_for_line_point(curve2, &intersection);
238 if line2_params.is_empty() {
239 return result;
240 }
241
242 for t1 in &line1_params {
243 for t2 in &line2_params {
244 // It could be argued that an endpoint intersection located in the interior of one
245 // or both curves should be returned here; we currently don't.
246 add_intersection(*t1, curve1, *t2, curve2, /* flip */ false, &mut result);
247 }
248 }
249
250 result
251}
252
253// This function implements the main bézier clipping algorithm by recursively subdividing curve1 and
254// curve2 in to smaller and smaller portions of the original curves with the property that one of
255// the curves intersects the fat line of the other curve at each stage.
256//
257// curve1 and curve2 at each stage are sub-bézier curves of the original curves; flip tells us
258// whether curve1 at a given stage is a sub-curve of the original curve1 or the original curve2;
259// similarly for curve2. domain1 and domain2 shrink (or stay the same) at each stage and describe
260// which subdomain of an original curve the current curve1 and curve2 correspond to. (The domains of
261// curve1 and curve2 are 0..1 at every stage.)
262#[allow(clippy::too_many_arguments)]
263fn add_curve_intersections<S: Scalar>(
264 curve1: &CubicBezierSegment<S>,
265 curve2: &CubicBezierSegment<S>,
266 domain1: &Range<S>,
267 domain2: &Range<S>,
268 intersections: &mut ArrayVec<(S, S), 9>,
269 flip: bool,
270 mut recursion_count: u32,
271 mut call_count: u32,
272 orig_curve1: &CubicBezierSegment<S>,
273 orig_curve2: &CubicBezierSegment<S>,
274) -> u32 {
275 call_count += 1;
276 recursion_count += 1;
277 if call_count >= 4096 || recursion_count >= 60 {
278 return call_count;
279 }
280
281 let epsilon = if inputs_are_f32::<S>() {
282 S::value(5e-6)
283 } else {
284 S::value(1e-9)
285 };
286
287 if domain2.start == domain2.end || curve2.is_a_point(S::ZERO) {
288 add_point_curve_intersection(
289 curve2,
290 /* point is curve1 */ false,
291 curve1,
292 domain2,
293 domain1,
294 intersections,
295 flip,
296 );
297 return call_count;
298 } else if curve2.from == curve2.to {
299 // There's no curve2 baseline to fat-line against (and we'll (debug) crash if we try with
300 // the current implementation), so split curve2 and try again.
301 let new_2_curves = orig_curve2.split_range(domain2.clone()).split(S::HALF);
302 let domain2_mid = (domain2.start + domain2.end) * S::HALF;
303 call_count = add_curve_intersections(
304 curve1,
305 &new_2_curves.0,
306 domain1,
307 &(domain2.start..domain2_mid),
308 intersections,
309 flip,
310 recursion_count,
311 call_count,
312 orig_curve1,
313 orig_curve2,
314 );
315 call_count = add_curve_intersections(
316 curve1,
317 &new_2_curves.1,
318 domain1,
319 &(domain2_mid..domain2.end),
320 intersections,
321 flip,
322 recursion_count,
323 call_count,
324 orig_curve1,
325 orig_curve2,
326 );
327 return call_count;
328 }
329
330 // (Don't call this before checking for point curves: points are inexact and can lead to false
331 // negatives here.)
332 if !rectangles_overlap(&curve1.fast_bounding_box(), &curve2.fast_bounding_box()) {
333 return call_count;
334 }
335
336 let (t_min_clip, t_max_clip) = match restrict_curve_to_fat_line(curve1, curve2) {
337 Some((min, max)) => (min, max),
338 None => return call_count,
339 };
340
341 // t_min_clip and t_max_clip are (0, 1)-based, so project them back to get the new restricted
342 // range:
343 let new_domain1 =
344 &(domain_value_at_t(domain1, t_min_clip)..domain_value_at_t(domain1, t_max_clip));
345
346 if S::max(
347 domain2.end - domain2.start,
348 new_domain1.end - new_domain1.start,
349 ) < epsilon
350 {
351 let t1 = (new_domain1.start + new_domain1.end) * S::HALF;
352 let t2 = (domain2.start + domain2.end) * S::HALF;
353 if inputs_are_f32::<S>() {
354 // There's an unfortunate tendency for curve2 endpoints that end near (but not all
355 // that near) to the interior of curve1 to register as intersections, so try to avoid
356 // that. (We could be discarding a legitimate intersection here.)
357 let end_eps = S::value(1e-3);
358 if (t2 < end_eps || t2 > S::ONE - end_eps)
359 && (orig_curve1.sample(t1) - orig_curve2.sample(t2)).length() > S::FIVE
360 {
361 return call_count;
362 }
363 }
364 add_intersection(t1, orig_curve1, t2, orig_curve2, flip, intersections);
365 return call_count;
366 }
367
368 // Reduce curve1 to the part that might intersect curve2.
369 let curve1 = &orig_curve1.split_range(new_domain1.clone());
370
371 // (Note: it's possible for new_domain1 to have become a point, even if
372 // t_min_clip < t_max_clip. It's also possible for curve1 to not be a point even if new_domain1
373 // is a point (but then curve1 will be very small).)
374 if new_domain1.start == new_domain1.end || curve1.is_a_point(S::ZERO) {
375 add_point_curve_intersection(
376 curve1,
377 /* point is curve1 */ true,
378 curve2,
379 new_domain1,
380 domain2,
381 intersections,
382 flip,
383 );
384 return call_count;
385 }
386
387 // If the new range is still 80% or more of the old range, subdivide and try again.
388 if t_max_clip - t_min_clip > S::EIGHT / S::TEN {
389 // Subdivide the curve which has converged the least.
390 if new_domain1.end - new_domain1.start > domain2.end - domain2.start {
391 let new_1_curves = curve1.split(S::HALF);
392 let new_domain1_mid = (new_domain1.start + new_domain1.end) * S::HALF;
393 call_count = add_curve_intersections(
394 curve2,
395 &new_1_curves.0,
396 domain2,
397 &(new_domain1.start..new_domain1_mid),
398 intersections,
399 !flip,
400 recursion_count,
401 call_count,
402 orig_curve2,
403 orig_curve1,
404 );
405 call_count = add_curve_intersections(
406 curve2,
407 &new_1_curves.1,
408 domain2,
409 &(new_domain1_mid..new_domain1.end),
410 intersections,
411 !flip,
412 recursion_count,
413 call_count,
414 orig_curve2,
415 orig_curve1,
416 );
417 } else {
418 let new_2_curves = orig_curve2.split_range(domain2.clone()).split(S::HALF);
419 let domain2_mid = (domain2.start + domain2.end) * S::HALF;
420 call_count = add_curve_intersections(
421 &new_2_curves.0,
422 curve1,
423 &(domain2.start..domain2_mid),
424 new_domain1,
425 intersections,
426 !flip,
427 recursion_count,
428 call_count,
429 orig_curve2,
430 orig_curve1,
431 );
432 call_count = add_curve_intersections(
433 &new_2_curves.1,
434 curve1,
435 &(domain2_mid..domain2.end),
436 new_domain1,
437 intersections,
438 !flip,
439 recursion_count,
440 call_count,
441 orig_curve2,
442 orig_curve1,
443 );
444 }
445 } else {
446 // Iterate.
447 if domain2.end - domain2.start >= epsilon {
448 call_count = add_curve_intersections(
449 curve2,
450 curve1,
451 domain2,
452 new_domain1,
453 intersections,
454 !flip,
455 recursion_count,
456 call_count,
457 orig_curve2,
458 orig_curve1,
459 );
460 } else {
461 // The interval on curve2 is already tight enough, so just continue iterating on curve1.
462 call_count = add_curve_intersections(
463 curve1,
464 curve2,
465 new_domain1,
466 domain2,
467 intersections,
468 flip,
469 recursion_count,
470 call_count,
471 orig_curve1,
472 orig_curve2,
473 );
474 }
475 }
476
477 call_count
478}
479
480fn add_point_curve_intersection<S: Scalar>(
481 pt_curve: &CubicBezierSegment<S>,
482 pt_curve_is_curve1: bool,
483 curve: &CubicBezierSegment<S>,
484 pt_domain: &Range<S>,
485 curve_domain: &Range<S>,
486 intersections: &mut ArrayVec<(S, S), 9>,
487 flip: bool,
488) {
489 let pt = pt_curve.from;
490 // We assume pt is curve1 when we add intersections below.
491 let flip = if pt_curve_is_curve1 { flip } else { !flip };
492
493 // Generally speaking |curve| will be quite small at this point, so see if we can get away with
494 // just sampling here.
495
496 let epsilon = epsilon_for_point(&pt);
497 let pt_t = (pt_domain.start + pt_domain.end) * S::HALF;
498
499 let curve_t = {
500 let mut t_for_min = S::ZERO;
501 let mut min_dist_sq = epsilon;
502 let tenths = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0];
503 for &t in tenths.iter() {
504 let t = S::value(t);
505 let d = (pt - curve.sample(t)).square_length();
506 if d < min_dist_sq {
507 t_for_min = t;
508 min_dist_sq = d;
509 }
510 }
511
512 if min_dist_sq == epsilon {
513 -S::ONE
514 } else {
515 let curve_t = domain_value_at_t(curve_domain, t_for_min);
516 curve_t
517 }
518 };
519
520 if curve_t != -S::ONE {
521 add_intersection(pt_t, pt_curve, curve_t, curve, flip, intersections);
522 return;
523 }
524
525 // If sampling didn't work, try a different approach.
526 let results = point_curve_intersections(&pt, curve, epsilon);
527 for t in results {
528 let curve_t = domain_value_at_t(curve_domain, t);
529 add_intersection(pt_t, pt_curve, curve_t, curve, flip, intersections);
530 }
531}
532
533// TODO: replace with Scalar::epsilon_for?
534// If we're comparing distances between samples of curves, our epsilon should depend on how big the
535// points we're comparing are. This function returns an epsilon appropriate for the size of pt.
536fn epsilon_for_point<S: Scalar>(pt: &Point<S>) -> S {
537 let max: S = S::max(S::abs(pt.x), S::abs(self:pt.y));
538 let epsilon: S = if inputs_are_f32::<S>() {
539 match max.to_i32().unwrap() {
540 0..=9 => S::value(0.001),
541 10..=99 => S::value(0.01),
542 100..=999 => S::value(0.1),
543 1_000..=9_999 => S::value(0.25),
544 10_000..=999_999 => S::HALF,
545 _ => S::ONE,
546 }
547 } else {
548 match max.to_i64().unwrap() {
549 0..=99_999 => S::EPSILON,
550 100_000..=99_999_999 => S::value(1e-5),
551 100_000_000..=9_999_999_999 => S::value(1e-3),
552 _ => S::value(1e-1),
553 }
554 };
555
556 epsilon
557}
558
559fn add_intersection<S: Scalar>(
560 t1: S,
561 orig_curve1: &CubicBezierSegment<S>,
562 t2: S,
563 orig_curve2: &CubicBezierSegment<S>,
564 flip: bool,
565 intersections: &mut ArrayVec<(S, S), 9>,
566) {
567 let (t1, t2) = if flip { (t2, t1) } else { (t1, t2) };
568 // (This should probably depend in some way on how large our input coefficients are.)
569 let epsilon = if inputs_are_f32::<S>() {
570 S::value(1e-3)
571 } else {
572 S::EPSILON
573 };
574 // Discard endpoint/endpoint intersections.
575 let t1_is_an_endpoint = t1 < epsilon || t1 > S::ONE - epsilon;
576 let t2_is_an_endpoint = t2 < epsilon || t2 > S::ONE - epsilon;
577 if t1_is_an_endpoint && t2_is_an_endpoint {
578 return;
579 }
580
581 // We can get repeated intersections when we split a curve at an intersection point, or when
582 // two curves intersect at a point where the curves are very close together, or when the fat
583 // line process breaks down.
584 for i in 0..intersections.len() {
585 let (old_t1, old_t2) = intersections[i];
586 // f32 errors can be particularly bad (over a hundred) if we wind up keeping the "wrong"
587 // duplicate intersection, so always keep the one that minimizes sample distance.
588 if S::abs(t1 - old_t1) < epsilon && S::abs(t2 - old_t2) < epsilon {
589 let cur_dist =
590 (orig_curve1.sample(old_t1) - orig_curve2.sample(old_t2)).square_length();
591 let new_dist = (orig_curve1.sample(t1) - orig_curve2.sample(t2)).square_length();
592 if new_dist < cur_dist {
593 intersections[i] = (t1, t2);
594 }
595 return;
596 }
597 }
598
599 if intersections.len() < 9 {
600 intersections.push((t1, t2));
601 }
602}
603
604// Returns an interval (t_min, t_max) with the property that for parameter values outside that
605// interval, curve1 is guaranteed to not intersect curve2; uses the fat line of curve2 as its basis
606// for the guarantee. (See the Sederberg document for what's going on here.)
607fn restrict_curve_to_fat_line<S: Scalar>(
608 curve1: &CubicBezierSegment<S>,
609 curve2: &CubicBezierSegment<S>,
610) -> Option<(S, S)> {
611 // TODO: Consider clipping against the perpendicular fat line as well (recommended by
612 // Sederberg).
613 // TODO: The current algorithm doesn't handle the (rare) case where curve1 and curve2 are
614 // overlapping lines.
615
616 let baseline2: LineEquation = curve2.baseline().to_line().equation();
617
618 let d_0: S = baseline2.signed_distance_to_point(&curve1.from);
619 let d_1: S = baseline2.signed_distance_to_point(&curve1.ctrl1);
620 let d_2: S = baseline2.signed_distance_to_point(&curve1.ctrl2);
621 let d_3: S = baseline2.signed_distance_to_point(&curve1.to);
622
623 let mut top: ArrayVec, 4> = ArrayVec::new();
624 let mut bottom: ArrayVec, 4> = ArrayVec::new();
625 convex_hull_of_distance_curve(d0:d_0, d1:d_1, d2:d_2, d3:d_3, &mut top, &mut bottom);
626 let (d_min: S, d_max: S) = curve2.fat_line_min_max();
627
628 clip_convex_hull_to_fat_line(&mut top, &mut bottom, d_min, d_max)
629}
630
631// Returns the convex hull of the curve that's the graph of the function
632// t -> d(curve1(t), baseline(curve2)). The convex hull is described as a top and a bottom, where
633// each of top and bottom is described by the list of its vertices from left to right (the number of
634// vertices for each is variable).
635fn convex_hull_of_distance_curve<S: Scalar>(
636 d0: S,
637 d1: S,
638 d2: S,
639 d3: S,
640 top: &mut ArrayVec<Point<S>, 4>,
641 bottom: &mut ArrayVec<Point<S>, 4>,
642) {
643 debug_assert!(top.is_empty());
644 debug_assert!(bottom.is_empty());
645
646 let p0 = point(S::ZERO, d0);
647 let p1 = point(S::ONE / S::THREE, d1);
648 let p2 = point(S::TWO / S::THREE, d2);
649 let p3 = point(S::ONE, d3);
650 // Compute the vertical signed distance of p1 and p2 from [p0, p3].
651 let dist1 = d1 - (S::TWO * d0 + d3) / S::THREE;
652 let dist2 = d2 - (d0 + S::TWO * d3) / S::THREE;
653
654 // Compute the hull assuming p1 is on top - we'll switch later if needed.
655 if dist1 * dist2 < S::ZERO {
656 // p1 and p2 lie on opposite sides of [p0, p3], so the hull is a quadrilateral:
657 let _ = top.try_extend_from_slice(&[p0, p1, p3]);
658 let _ = bottom.try_extend_from_slice(&[p0, p2, p3]);
659 } else {
660 // p1 and p2 lie on the same side of [p0, p3]. The hull can be a triangle or a
661 // quadrilateral, and [p0, p3] is part of the hull. The hull is a triangle if the vertical
662 // distance of one of the middle points p1, p2 is <= half the vertical distance of the
663 // other middle point.
664 let dist1 = S::abs(dist1);
665 let dist2 = S::abs(dist2);
666 if dist1 >= S::TWO * dist2 {
667 let _ = top.try_extend_from_slice(&[p0, p1, p3]);
668 let _ = bottom.try_extend_from_slice(&[p0, p3]);
669 } else if dist2 >= S::TWO * dist1 {
670 let _ = top.try_extend_from_slice(&[p0, p2, p3]);
671 let _ = bottom.try_extend_from_slice(&[p0, p3]);
672 } else {
673 let _ = top.try_extend_from_slice(&[p0, p1, p2, p3]);
674 let _ = bottom.try_extend_from_slice(&[p0, p3]);
675 }
676 }
677
678 // Flip the hull if needed:
679 if dist1 < S::ZERO || (dist1 == S::ZERO && dist2 < S::ZERO) {
680 mem::swap(top, bottom);
681 }
682}
683
684// Returns the min and max values at which the convex hull enters the fat line min/max offset lines.
685fn clip_convex_hull_to_fat_line<S: Scalar>(
686 hull_top: &mut [Point<S>],
687 hull_bottom: &mut [Point<S>],
688 d_min: S,
689 d_max: S,
690) -> Option<(S, S)> {
691 // Walk from the left corner of the convex hull until we enter the fat line limits:
692 let t_clip_min: S = walk_convex_hull_start_to_fat_line(hull_top, hull_bottom, d_min, d_max)?;
693
694 // Now walk from the right corner of the convex hull until we enter the fat line limits - to
695 // walk right to left we just reverse the order of the hull vertices, so that hull_top and
696 // hull_bottom start at the right corner now:
697 hull_top.reverse();
698 hull_bottom.reverse();
699 let t_clip_max: S = walk_convex_hull_start_to_fat_line(hull_top, hull_bottom, d_min, d_max)?;
700
701 Some((t_clip_min, t_clip_max))
702}
703
704// Walk the edges of the convex hull until you hit a fat line offset value, starting from the
705// (first vertex in hull_top_vertices == first vertex in hull_bottom_vertices).
706fn walk_convex_hull_start_to_fat_line<S: Scalar>(
707 hull_top_vertices: &[Point<S>],
708 hull_bottom_vertices: &[Point<S>],
709 d_min: S,
710 d_max: S,
711) -> Option<S> {
712 let start_corner: Point2D = hull_top_vertices[0];
713
714 if start_corner.y < d_min {
715 walk_convex_hull_edges_to_fat_line(hull_vertices:hull_top_vertices, vertices_are_for_top:true, threshold:d_min)
716 } else if start_corner.y > d_max {
717 walk_convex_hull_edges_to_fat_line(hull_vertices:hull_bottom_vertices, vertices_are_for_top:false, threshold:d_max)
718 } else {
719 Some(start_corner.x)
720 }
721}
722
723// Do the actual walking, starting from the first vertex of hull_vertices.
724fn walk_convex_hull_edges_to_fat_line<S: Scalar>(
725 hull_vertices: &[Point<S>],
726 vertices_are_for_top: bool,
727 threshold: S,
728) -> Option<S> {
729 for i: usize in 0..hull_vertices.len() - 1 {
730 let p: Point2D = hull_vertices[i];
731 let q: Point2D = hull_vertices[i + 1];
732 if (vertices_are_for_top && q.y >= threshold) || (!vertices_are_for_top && q.y <= threshold)
733 {
734 return if q.y == threshold {
735 Some(q.x)
736 } else {
737 Some(p.x + (threshold - p.y) * (q.x - p.x) / (q.y - p.y))
738 };
739 }
740 }
741 // All points of the hull are outside the threshold:
742 None
743}
744
745#[inline]
746fn inputs_are_f32<S: Scalar>() -> bool {
747 S::EPSILON > S::value(1e-6)
748}
749
750#[inline]
751// Return the point of domain corresponding to the point t, 0 <= t <= 1.
752fn domain_value_at_t<S: Scalar>(domain: &Range<S>, t: S) -> S {
753 domain.start + (domain.end - domain.start) * t
754}
755
756#[inline]
757// Box2D::intersects doesn't count edge/corner intersections, this version does.
758fn rectangles_overlap<S: Scalar>(r1: &Box2D<S>, r2: &Box2D<S>) -> bool {
759 r1.min.x <= r2.max.x && r2.min.x <= r1.max.x && r1.min.y <= r2.max.y && r2.min.y <= r1.max.y
760}
761
762#[cfg(test)]
763fn do_test<S: Scalar>(
764 curve1: &CubicBezierSegment<S>,
765 curve2: &CubicBezierSegment<S>,
766 intersection_count: i32,
767) {
768 do_test_once(curve1, curve2, intersection_count);
769 do_test_once(curve2, curve1, intersection_count);
770}
771
772#[cfg(test)]
773fn do_test_once<S: Scalar>(
774 curve1: &CubicBezierSegment<S>,
775 curve2: &CubicBezierSegment<S>,
776 intersection_count: i32,
777) {
778 let intersections = cubic_bezier_intersections_t(curve1, curve2);
779 for intersection in &intersections {
780 let p1 = curve1.sample(intersection.0);
781 let p2 = curve2.sample(intersection.1);
782 check_dist(&p1, &p2);
783 }
784
785 assert_eq!(intersections.len() as i32, intersection_count);
786}
787
788#[cfg(test)]
789fn check_dist<S: Scalar>(p1: &Point<S>, p2: &Point<S>) {
790 let dist = S::sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
791 if dist > S::HALF {
792 assert!(false, "Intersection points too far apart.");
793 }
794}
795
796#[test]
797fn test_cubic_curve_curve_intersections() {
798 do_test(
799 &CubicBezierSegment {
800 from: point(0.0, 0.0),
801 ctrl1: point(0.0, 1.0),
802 ctrl2: point(0.0, 1.0),
803 to: point(1.0, 1.0),
804 },
805 &CubicBezierSegment {
806 from: point(0.0, 1.0),
807 ctrl1: point(1.0, 1.0),
808 ctrl2: point(1.0, 1.0),
809 to: point(1.0, 0.0),
810 },
811 1,
812 );
813 do_test(
814 &CubicBezierSegment {
815 from: point(48.0f32, 84.0),
816 ctrl1: point(104.0, 176.0),
817 ctrl2: point(190.0, 37.0),
818 to: point(121.0, 75.0),
819 },
820 &CubicBezierSegment {
821 from: point(68.0, 145.0),
822 ctrl1: point(74.0, 6.0),
823 ctrl2: point(143.0, 197.0),
824 to: point(138.0, 55.0),
825 },
826 4,
827 );
828 do_test(
829 &CubicBezierSegment {
830 from: point(0.0, 0.0),
831 ctrl1: point(0.5, 1.0),
832 ctrl2: point(0.5, 1.0),
833 to: point(1.0, 0.0),
834 },
835 &CubicBezierSegment {
836 from: point(0.0, 1.0),
837 ctrl1: point(0.5, 0.0),
838 ctrl2: point(0.5, 0.0),
839 to: point(1.0, 1.0),
840 },
841 2,
842 );
843 do_test(
844 &CubicBezierSegment {
845 from: point(0.2, 0.0),
846 ctrl1: point(0.5, 3.0),
847 ctrl2: point(0.5, -2.0),
848 to: point(0.8, 1.0),
849 },
850 &CubicBezierSegment {
851 from: point(0.0, 0.0),
852 ctrl1: point(2.5, 0.5),
853 ctrl2: point(-1.5, 0.5),
854 to: point(1.0, 0.0),
855 },
856 9,
857 );
858
859 // (A previous version of the code was returning two practically identical
860 // intersection points here.)
861 do_test(
862 &CubicBezierSegment {
863 from: point(718133.1363092018, 673674.987999388),
864 ctrl1: point(-53014.13135835016, 286988.87959900266),
865 ctrl2: point(-900630.1880107201, -7527.6889376943),
866 to: point(417822.48349384824, -149039.14932848653),
867 },
868 &CubicBezierSegment {
869 from: point(924715.3309247112, 719414.5221912428),
870 ctrl1: point(965365.9679664494, -563421.3040676294),
871 ctrl2: point(273552.85484064696, 643090.0890117711),
872 to: point(-113963.134524995, 732017.9466050486),
873 },
874 1,
875 );
876
877 // On these curves the algorithm runs to a state at which the new clipped domain1 becomes a
878 // point even though t_min_clip < t_max_clip (because domain1 was small enough to begin with
879 // relative to the small distance between t_min_clip and t_max_clip), and the new curve1 is not
880 // a point (it's split off the old curve1 using t_min_clip < t_max_clip).
881 do_test(
882 &CubicBezierSegment {
883 from: point(423394.5967598548, -91342.7434613118),
884 ctrl1: point(333212.450870987, 225564.45711810607),
885 ctrl2: point(668108.668469816, -626100.8367380127),
886 to: point(-481885.0610437216, 893767.5320803947),
887 },
888 &CubicBezierSegment {
889 from: point(-484505.2601961801, -222621.44229855016),
890 ctrl1: point(22432.829984141514, -944727.7102144773),
891 ctrl2: point(-433294.66549074976, -168018.60431004688),
892 to: point(567688.5977972192, 13975.09633399453),
893 },
894 3,
895 );
896}
897
898#[test]
899fn test_cubic_control_point_touching() {
900 // After splitting the curve2 loop in half, curve1.ctrl1 (and only that
901 // point) touches the curve2 fat line - make sure we don't accept that as an
902 // intersection. [We're really only interested in the right half of the loop - the rest of the
903 // loop is there just to get past an initial fast_bounding_box check.]
904 do_test(
905 &CubicBezierSegment {
906 from: point(-1.0, 0.0),
907 ctrl1: point(0.0, 0.0),
908 ctrl2: point(-1.0, -0.1),
909 to: point(-1.0, -0.1),
910 },
911 &CubicBezierSegment {
912 from: point(0.0, 0.0),
913 ctrl1: point(5.0, -5.0),
914 ctrl2: point(-5.0, -5.0),
915 to: point(0.0, 0.0),
916 },
917 0,
918 );
919}
920
921#[test]
922fn test_cubic_self_intersections() {
923 // Two self-intersecting curves intersecting at their self-intersections (the origin).
924 do_test(
925 &CubicBezierSegment {
926 from: point(-10.0, -13.636363636363636),
927 ctrl1: point(15.0, 11.363636363636363),
928 ctrl2: point(-15.0, 11.363636363636363),
929 to: point(10.0, -13.636363636363636),
930 },
931 &CubicBezierSegment {
932 from: point(13.636363636363636, -10.0),
933 ctrl1: point(-11.363636363636363, 15.0),
934 ctrl2: point(-11.363636363636363, -15.0),
935 to: point(13.636363636363636, 10.0),
936 },
937 4,
938 );
939}
940
941#[test]
942fn test_cubic_loops() {
943 // This gets up to a recursion count of 53 trying to find (0.0, 0.0) and (1.0, 1.0) (which
944 // aren't actually needed) - with the curves in the opposite order it gets up to 81!
945 do_test(
946 &CubicBezierSegment {
947 from: point(0.0, 0.0),
948 ctrl1: point(-10.0, 10.0),
949 ctrl2: point(10.0, 10.0),
950 to: point(0.0, 0.0),
951 },
952 &CubicBezierSegment {
953 from: point(0.0, 0.0),
954 ctrl1: point(-1.0, 1.0),
955 ctrl2: point(1.0, 1.0),
956 to: point(0.0, 0.0),
957 },
958 0,
959 );
960
961 do_test(
962 &CubicBezierSegment {
963 from: point(0.0f32, 0.0),
964 ctrl1: point(-100.0, 0.0),
965 ctrl2: point(-500.0, 500.0),
966 to: point(0.0, 0.0),
967 },
968 &CubicBezierSegment {
969 from: point(0.0, 0.0),
970 ctrl1: point(-800.0, 100.0),
971 ctrl2: point(500.0, 500.0),
972 to: point(0.0, 0.0),
973 },
974 3,
975 );
976}
977
978#[test]
979fn test_cubic_line_curve_intersections() {
980 do_test(
981 &CubicBezierSegment {
982 /* line */
983 from: point(1.0, 2.0),
984 ctrl1: point(20.0, 1.0),
985 ctrl2: point(1.0, 2.0),
986 to: point(20.0, 1.0),
987 },
988 &CubicBezierSegment {
989 from: point(1.0, 0.0),
990 ctrl1: point(1.0, 5.0),
991 ctrl2: point(20.0, 25.0),
992 to: point(20.0, 0.0),
993 },
994 2,
995 );
996
997 do_test(
998 &CubicBezierSegment {
999 /* line */
1000 from: point(0.0f32, 0.0),
1001 ctrl1: point(-10.0, 0.0),
1002 ctrl2: point(20.0, 0.0),
1003 to: point(10.0, 0.0),
1004 },
1005 &CubicBezierSegment {
1006 from: point(-1.0, -1.0),
1007 ctrl1: point(0.0, 4.0),
1008 ctrl2: point(10.0, -4.0),
1009 to: point(11.0, 1.0),
1010 },
1011 5,
1012 );
1013
1014 do_test(
1015 &CubicBezierSegment {
1016 from: point(-1.0, -2.0),
1017 ctrl1: point(-1.0, 8.0),
1018 ctrl2: point(1.0, -8.0),
1019 to: point(1.0, 2.0),
1020 },
1021 &CubicBezierSegment {
1022 /* line */
1023 from: point(-10.0, -10.0),
1024 ctrl1: point(20.0, 20.0),
1025 ctrl2: point(-20.0, -20.0),
1026 to: point(10.0, 10.0),
1027 },
1028 9,
1029 );
1030}
1031
1032#[test]
1033fn test_cubic_line_line_intersections() {
1034 do_test(
1035 &CubicBezierSegment {
1036 from: point(-10.0, -10.0),
1037 ctrl1: point(20.0, 20.0),
1038 ctrl2: point(-20.0, -20.0),
1039 to: point(10.0, 10.0),
1040 },
1041 &CubicBezierSegment {
1042 from: point(-10.0, 10.0),
1043 ctrl1: point(20.0, -20.0),
1044 ctrl2: point(-20.0, 20.0),
1045 to: point(10.0, -10.0),
1046 },
1047 9,
1048 );
1049
1050 // Overlapping line segments should return 0 intersections.
1051 do_test(
1052 &CubicBezierSegment {
1053 from: point(0.0, 0.0),
1054 ctrl1: point(0.0, 0.0),
1055 ctrl2: point(10.0, 0.0),
1056 to: point(10.0, 0.0),
1057 },
1058 &CubicBezierSegment {
1059 from: point(5.0, 0.0),
1060 ctrl1: point(5.0, 0.0),
1061 ctrl2: point(15.0, 0.0),
1062 to: point(15.0, 0.0),
1063 },
1064 0,
1065 );
1066}
1067
1068#[test]
1069// (This test used to fail on a previous version of the algorithm by returning an intersection close
1070// to (1.0, 0.0), but not close enough to consider it the same as (1.0, 0.0) - the curves are quite
1071// close at that endpoint.)
1072fn test_cubic_similar_loops() {
1073 do_test(
1074 &CubicBezierSegment {
1075 from: point(-0.281604145719379, -0.3129629924180608),
1076 ctrl1: point(-0.04393998118946163, 0.13714701102906668),
1077 ctrl2: point(0.4472584256288119, 0.2876115686206546),
1078 to: point(-0.281604145719379, -0.3129629924180608),
1079 },
1080 &CubicBezierSegment {
1081 from: point(-0.281604145719379, -0.3129629924180608),
1082 ctrl1: point(-0.1560415754252551, -0.22924729391648402),
1083 ctrl2: point(-0.9224550447067958, 0.19110227764357646),
1084 to: point(-0.281604145719379, -0.3129629924180608),
1085 },
1086 2,
1087 );
1088}
1089
1090#[test]
1091// (A previous version of the algorithm returned an intersection close to (0.5, 0.5), but not close
1092// enough to be considered the same as (0.5, 0.5).)
1093fn test_cubic_no_duplicated_root() {
1094 do_test(
1095 &CubicBezierSegment {
1096 from: point(0.0, 0.0),
1097 ctrl1: point(-10.0, 1.0),
1098 ctrl2: point(10.0, 1.0),
1099 to: point(0.0, 0.0),
1100 },
1101 &CubicBezierSegment {
1102 from: point(0.0, 0.0),
1103 ctrl1: point(-1.0, 1.0),
1104 ctrl2: point(1.0, 1.0),
1105 to: point(0.0, 0.0),
1106 },
1107 1,
1108 );
1109}
1110
1111#[test]
1112fn test_cubic_glancing_intersection() {
1113 use std::panic;
1114 // The f64 version currently fails on a very close fat line miss after 57 recursions.
1115 let result = panic::catch_unwind(|| {
1116 do_test(
1117 &CubicBezierSegment {
1118 from: point(0.0, 0.0),
1119 ctrl1: point(0.0, 8.0),
1120 ctrl2: point(10.0, 8.0),
1121 to: point(10.0, 0.0),
1122 },
1123 &CubicBezierSegment {
1124 from: point(0.0, 12.0),
1125 ctrl1: point(0.0, 4.0),
1126 ctrl2: point(10.0, 4.0),
1127 to: point(10.0, 12.0),
1128 },
1129 1,
1130 );
1131 });
1132 assert!(result.is_err());
1133
1134 let result = panic::catch_unwind(|| {
1135 do_test(
1136 &CubicBezierSegment {
1137 from: point(0.0f32, 0.0),
1138 ctrl1: point(0.0, 8.0),
1139 ctrl2: point(10.0, 8.0),
1140 to: point(10.0, 0.0),
1141 },
1142 &CubicBezierSegment {
1143 from: point(0.0, 12.0),
1144 ctrl1: point(0.0, 4.0),
1145 ctrl2: point(10.0, 4.0),
1146 to: point(10.0, 12.0),
1147 },
1148 1,
1149 );
1150 });
1151 assert!(result.is_err());
1152}
1153
1154#[test]
1155fn test_cubic_duplicated_intersections() {
1156 use std::panic;
1157 let result = panic::catch_unwind(|| {
1158 // This finds an extra intersection (0.49530116, 0.74361485) - the actual, also found, is
1159 // (0.49633604, 0.74361396). Their difference is (−0.00103488, 0.00000089) - we consider
1160 // the two to be the same if both difference values are < 1e-3.
1161 do_test(
1162 &CubicBezierSegment {
1163 from: point(-33307.36f32, -1804.0625),
1164 ctrl1: point(-59259.727, 70098.31),
1165 ctrl2: point(98661.78, 48235.703),
1166 to: point(28422.234, 31845.219),
1167 },
1168 &CubicBezierSegment {
1169 from: point(-21501.133, 51935.344),
1170 ctrl1: point(-95301.96, 95031.45),
1171 ctrl2: point(-25882.242, -12896.75),
1172 to: point(94618.97, 94288.66),
1173 },
1174 2,
1175 );
1176 });
1177 assert!(result.is_err());
1178}
1179
1180#[test]
1181fn test_cubic_endpoint_not_an_intersection() {
1182 // f32 curves seem to be somewhat prone to picking up not-an-intersections where an endpoint of
1183 // one curve is close to and points into the interior of the other curve, and both curves are
1184 // "mostly linear" on some level.
1185 use std::panic;
1186 let result = panic::catch_unwind(|| {
1187 do_test(
1188 &CubicBezierSegment {
1189 from: point(76868.875f32, 47679.28),
1190 ctrl1: point(65326.86, 856.21094),
1191 ctrl2: point(-85621.64, -80823.375),
1192 to: point(-56517.53, 28062.227),
1193 },
1194 &CubicBezierSegment {
1195 from: point(-67977.72, 77673.53),
1196 ctrl1: point(-59829.57, -41917.87),
1197 ctrl2: point(57.4375, 52822.97),
1198 to: point(51075.86, 85772.84),
1199 },
1200 0,
1201 );
1202 });
1203 assert!(result.is_err());
1204}
1205
1206#[test]
1207// The endpoints of curve2 intersect the interior of curve1.
1208fn test_cubic_interior_endpoint() {
1209 do_test(
1210 &CubicBezierSegment {
1211 // Has its apex at 6.0.
1212 from: point(-5.0, 0.0),
1213 ctrl1: point(-5.0, 8.0),
1214 ctrl2: point(5.0, 8.0),
1215 to: point(5.0, 0.0),
1216 },
1217 &CubicBezierSegment {
1218 from: point(0.0, 6.0),
1219 ctrl1: point(-5.0, 0.0),
1220 ctrl2: point(5.0, 0.0),
1221 to: point(0.0, 6.0),
1222 },
1223 2,
1224 );
1225}
1226
1227#[test]
1228fn test_cubic_point_curve_intersections() {
1229 let epsilon = 1e-5;
1230 {
1231 let curve1 = CubicBezierSegment {
1232 from: point(0.0, 0.0),
1233 ctrl1: point(0.0, 1.0),
1234 ctrl2: point(0.0, 1.0),
1235 to: point(1.0, 1.0),
1236 };
1237 let sample_t = 0.123456789;
1238 let pt = curve1.sample(sample_t);
1239 let curve2 = CubicBezierSegment {
1240 from: pt,
1241 ctrl1: pt,
1242 ctrl2: pt,
1243 to: pt,
1244 };
1245 let intersections = cubic_bezier_intersections_t(&curve1, &curve2);
1246 assert_eq!(intersections.len(), 1);
1247 let intersection_t = intersections[0].0;
1248 assert!(f64::abs(intersection_t - sample_t) < epsilon);
1249 }
1250 {
1251 let curve1 = CubicBezierSegment {
1252 from: point(-10.0, -13.636363636363636),
1253 ctrl1: point(15.0, 11.363636363636363),
1254 ctrl2: point(-15.0, 11.363636363636363),
1255 to: point(10.0, -13.636363636363636),
1256 };
1257 // curve1 has a self intersection at the following parameter values:
1258 let parameter1 = 0.7611164839335472;
1259 let parameter2 = 0.23888351606645375;
1260 let pt = curve1.sample(parameter1);
1261 let curve2 = CubicBezierSegment {
1262 from: pt,
1263 ctrl1: pt,
1264 ctrl2: pt,
1265 to: pt,
1266 };
1267 let intersections = cubic_bezier_intersections_t(&curve1, &curve2);
1268 assert_eq!(intersections.len(), 2);
1269 let intersection_t1 = intersections[0].0;
1270 let intersection_t2 = intersections[1].0;
1271 assert!(f64::abs(intersection_t1 - parameter1) < epsilon);
1272 assert!(f64::abs(intersection_t2 - parameter2) < epsilon);
1273 }
1274 {
1275 let epsilon = epsilon as f32;
1276 let curve1 = CubicBezierSegment {
1277 from: point(0.0f32, 0.0),
1278 ctrl1: point(50.0, 50.0),
1279 ctrl2: point(-50.0, -50.0),
1280 to: point(10.0, 10.0),
1281 };
1282 // curve1 is a line that passes through (5.0, 5.0) three times:
1283 let parameter1 = 0.96984464;
1284 let parameter2 = 0.037427425;
1285 let parameter3 = 0.44434106;
1286 let pt = curve1.sample(parameter1);
1287 let curve2 = CubicBezierSegment {
1288 from: pt,
1289 ctrl1: pt,
1290 ctrl2: pt,
1291 to: pt,
1292 };
1293 let intersections = cubic_bezier_intersections_t(&curve1, &curve2);
1294 assert_eq!(intersections.len(), 3);
1295 let intersection_t1 = intersections[0].0;
1296 let intersection_t2 = intersections[1].0;
1297 let intersection_t3 = intersections[2].0;
1298 assert!(f32::abs(intersection_t1 - parameter1) < epsilon);
1299 assert!(f32::abs(intersection_t2 - parameter2) < epsilon);
1300 assert!(f32::abs(intersection_t3 - parameter3) < epsilon);
1301 }
1302}
1303
1304#[test]
1305fn test_cubic_subcurve_intersections() {
1306 let curve1 = CubicBezierSegment {
1307 from: point(0.0, 0.0),
1308 ctrl1: point(0.0, 1.0),
1309 ctrl2: point(0.0, 1.0),
1310 to: point(1.0, 1.0),
1311 };
1312 let curve2 = curve1.split_range(0.25..0.75);
1313 // The algorithm will find as many intersections as you let it, basically - make sure we're
1314 // not allowing too many intersections to be added, and not crashing on out of resources.
1315 do_test(&curve1, &curve2, 9);
1316}
1317
1318#[test]
1319fn test_cubic_result_distance() {
1320 // In a previous version this used to return an intersection pair (0.17933762, 0.23783168),
1321 // close to an actual intersection, where the sampled intersection points on respective curves
1322 // were at distance 160.08488. The point here is that the old extra intersection was the result
1323 // of an anomalous fat line calculation, in other words an actual error, not just a "not quite
1324 // computationally close enough" error.
1325 do_test(
1326 &CubicBezierSegment {
1327 from: point(5893.133f32, -51377.152),
1328 ctrl1: point(-94403.984, 37668.156),
1329 ctrl2: point(-58914.684, 30339.195),
1330 to: point(4895.875, 83473.3),
1331 },
1332 &CubicBezierSegment {
1333 from: point(-51523.734, 75047.05),
1334 ctrl1: point(-58162.76, -91093.875),
1335 ctrl2: point(82137.516, -59844.35),
1336 to: point(46856.406, 40479.64),
1337 },
1338 3,
1339 );
1340}
1341