1// Copyright 2023 the Kurbo Authors
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4use core::{borrow::Borrow, f64::consts::PI};
5
6use alloc::vec::Vec;
7
8use smallvec::SmallVec;
9
10#[cfg(not(feature = "std"))]
11use crate::common::FloatFuncs;
12
13use crate::{
14 common::solve_quadratic, fit_to_bezpath, fit_to_bezpath_opt, offset::CubicOffset, Affine, Arc,
15 BezPath, CubicBez, Line, ParamCurve, ParamCurveArclen, PathEl, PathSeg, Point, QuadBez, Vec2,
16};
17
18/// Defines the connection between two segments of a stroke.
19#[derive(Copy, Clone, PartialEq, Eq, Debug)]
20pub enum Join {
21 /// A straight line connecting the segments.
22 Bevel,
23 /// The segments are extended to their natural intersection point.
24 Miter,
25 /// An arc between the segments.
26 Round,
27}
28
29/// Defines the shape to be drawn at the ends of a stroke.
30#[derive(Copy, Clone, PartialEq, Eq, Debug)]
31pub enum Cap {
32 /// Flat cap.
33 Butt,
34 /// Square cap with dimensions equal to half the stroke width.
35 Square,
36 /// Rounded cap with radius equal to half the stroke width.
37 Round,
38}
39
40/// Describes the visual style of a stroke.
41#[derive(Clone, Debug)]
42pub struct Stroke {
43 /// Width of the stroke.
44 pub width: f64,
45 /// Style for connecting segments of the stroke.
46 pub join: Join,
47 /// Limit for miter joins.
48 pub miter_limit: f64,
49 /// Style for capping the beginning of an open subpath.
50 pub start_cap: Cap,
51 /// Style for capping the end of an open subpath.
52 pub end_cap: Cap,
53 /// Lengths of dashes in alternating on/off order.
54 pub dash_pattern: Dashes,
55 /// Offset of the first dash.
56 pub dash_offset: f64,
57}
58
59/// Options for path stroking.
60pub struct StrokeOpts {
61 opt_level: StrokeOptLevel,
62}
63
64/// Optimization level for computing
65pub enum StrokeOptLevel {
66 /// Adaptively subdivide segments in half.
67 Subdivide,
68 /// Compute optimized subdivision points to minimize error.
69 Optimized,
70}
71
72impl Default for StrokeOpts {
73 fn default() -> Self {
74 let opt_level: StrokeOptLevel = StrokeOptLevel::Subdivide;
75 StrokeOpts { opt_level }
76 }
77}
78
79impl Default for Stroke {
80 fn default() -> Self {
81 Self {
82 width: 1.0,
83 join: Join::Round,
84 miter_limit: 4.0,
85 start_cap: Cap::Round,
86 end_cap: Cap::Round,
87 dash_pattern: Default::default(),
88 dash_offset: 0.0,
89 }
90 }
91}
92
93impl Stroke {
94 /// Creates a new stroke with the specified width.
95 pub fn new(width: f64) -> Self {
96 Self {
97 width,
98 ..Default::default()
99 }
100 }
101
102 /// Builder method for setting the join style.
103 pub fn with_join(mut self, join: Join) -> Self {
104 self.join = join;
105 self
106 }
107
108 /// Builder method for setting the limit for miter joins.
109 pub fn with_miter_limit(mut self, limit: f64) -> Self {
110 self.miter_limit = limit;
111 self
112 }
113
114 /// Builder method for setting the cap style for the start of the stroke.
115 pub fn with_start_cap(mut self, cap: Cap) -> Self {
116 self.start_cap = cap;
117 self
118 }
119
120 /// Builder method for setting the cap style for the end of the stroke.
121 pub fn with_end_cap(mut self, cap: Cap) -> Self {
122 self.end_cap = cap;
123 self
124 }
125
126 /// Builder method for setting the cap style.
127 pub fn with_caps(mut self, cap: Cap) -> Self {
128 self.start_cap = cap;
129 self.end_cap = cap;
130 self
131 }
132
133 /// Builder method for setting the dashing parameters.
134 pub fn with_dashes<P>(mut self, offset: f64, pattern: P) -> Self
135 where
136 P: IntoIterator,
137 P::Item: Borrow<f64>,
138 {
139 self.dash_offset = offset;
140 self.dash_pattern.clear();
141 self.dash_pattern
142 .extend(pattern.into_iter().map(|dash| *dash.borrow()));
143 self
144 }
145}
146
147impl StrokeOpts {
148 /// Set optimization level for computing stroke outlines.
149 pub fn opt_level(mut self, opt_level: StrokeOptLevel) -> Self {
150 self.opt_level = opt_level;
151 self
152 }
153}
154
155/// Collection of values representing lengths in a dash pattern.
156pub type Dashes = SmallVec<[f64; 4]>;
157
158/// Internal structure used for creating strokes.
159#[derive(Default)]
160struct StrokeCtx {
161 // As a possible future optimization, we might not need separate storage
162 // for forward and backward paths, we can add forward to the output in-place.
163 // However, this structure is clearer and the cost fairly modest.
164 output: BezPath,
165 forward_path: BezPath,
166 backward_path: BezPath,
167 start_pt: Point,
168 start_norm: Vec2,
169 start_tan: Vec2,
170 last_pt: Point,
171 last_tan: Vec2,
172 // Precomputation of the join threshold, to optimize per-join logic.
173 // If hypot < (hypot + dot) * join_thresh, omit join altogether.
174 join_thresh: f64,
175}
176
177/// Expand a stroke into a fill.
178///
179/// The `tolerance` parameter controls the accuracy of the result. In general,
180/// the number of subdivisions in the output scales to the -1/6 power of the
181/// parameter, for example making it 1/64 as big generates twice as many
182/// segments. The appropriate value depends on the application; if the result
183/// of the stroke will be scaled up, a smaller value is needed.
184///
185/// This method attempts a fairly high degree of correctness, but ultimately
186/// is based on computing parallel curves and adding joins and caps, rather than
187/// computing the rigorously correct parallel sweep (which requires evolutes in
188/// the general case). See [Nehab 2020] for more discussion.
189///
190/// [Nehab 2020]: https://dl.acm.org/doi/10.1145/3386569.3392392
191pub fn stroke(
192 path: impl IntoIterator<Item = PathEl>,
193 style: &Stroke,
194 opts: &StrokeOpts,
195 tolerance: f64,
196) -> BezPath {
197 if style.dash_pattern.is_empty() {
198 stroke_undashed(path, style, tolerance, opts)
199 } else {
200 let dashed: impl Iterator = dash(inner:path.into_iter(), style.dash_offset, &style.dash_pattern);
201 stroke_undashed(path:dashed, style, tolerance, opts)
202 }
203}
204
205/// Version of stroke expansion for styles with no dashes.
206fn stroke_undashed(
207 path: impl IntoIterator<Item = PathEl>,
208 style: &Stroke,
209 tolerance: f64,
210 opts: &StrokeOpts,
211) -> BezPath {
212 let mut ctx = StrokeCtx {
213 join_thresh: 2.0 * tolerance / style.width,
214 ..Default::default()
215 };
216 for el in path {
217 let p0 = ctx.last_pt;
218 match el {
219 PathEl::MoveTo(p) => {
220 ctx.finish(style);
221 ctx.start_pt = p;
222 ctx.last_pt = p;
223 }
224 PathEl::LineTo(p1) => {
225 if p1 != p0 {
226 let tangent = p1 - p0;
227 ctx.do_join(style, tangent);
228 ctx.last_tan = tangent;
229 ctx.do_line(style, tangent, p1);
230 }
231 }
232 PathEl::QuadTo(p1, p2) => {
233 if p1 != p0 || p2 != p0 {
234 let q = QuadBez::new(p0, p1, p2);
235 let (tan0, tan1) = PathSeg::Quad(q).tangents();
236 ctx.do_join(style, tan0);
237 ctx.do_cubic(style, q.raise(), tolerance, opts);
238 ctx.last_tan = tan1;
239 }
240 }
241 PathEl::CurveTo(p1, p2, p3) => {
242 if p1 != p0 || p2 != p0 || p3 != p0 {
243 let c = CubicBez::new(p0, p1, p2, p3);
244 let (tan0, tan1) = PathSeg::Cubic(c).tangents();
245 ctx.do_join(style, tan0);
246 ctx.do_cubic(style, c, tolerance, opts);
247 ctx.last_tan = tan1;
248 }
249 }
250 PathEl::ClosePath => {
251 if p0 != ctx.start_pt {
252 let tangent = ctx.start_pt - p0;
253 ctx.do_join(style, tangent);
254 ctx.last_tan = tangent;
255 ctx.do_line(style, tangent, ctx.start_pt);
256 }
257 ctx.finish_closed(style);
258 }
259 }
260 }
261 ctx.finish(style);
262 ctx.output
263}
264
265fn round_cap(out: &mut BezPath, tolerance: f64, center: Point, norm: Vec2) {
266 round_join(out, tolerance, center, norm, PI);
267}
268
269fn round_join(out: &mut BezPath, tolerance: f64, center: Point, norm: Vec2, angle: f64) {
270 let a: Affine = Affine::new([norm.x, norm.y, -norm.y, norm.x, center.x, center.y]);
271 let arc: Arc = Arc::new(center:Point::ORIGIN, (1.0, 1.0), PI - angle, sweep_angle:angle, x_rotation:0.0);
272 arc.to_cubic_beziers(tolerance, |p1: Point, p2: Point, p3: Point| out.curve_to(p1:a * p1, p2:a * p2, p3:a * p3));
273}
274
275fn round_join_rev(out: &mut BezPath, tolerance: f64, center: Point, norm: Vec2, angle: f64) {
276 let a: Affine = Affine::new([norm.x, norm.y, norm.y, -norm.x, center.x, center.y]);
277 let arc: Arc = Arc::new(center:Point::ORIGIN, (1.0, 1.0), PI - angle, sweep_angle:angle, x_rotation:0.0);
278 arc.to_cubic_beziers(tolerance, |p1: Point, p2: Point, p3: Point| out.curve_to(p1:a * p1, p2:a * p2, p3:a * p3));
279}
280
281fn square_cap(out: &mut BezPath, close: bool, center: Point, norm: Vec2) {
282 let a: Affine = Affine::new([norm.x, norm.y, -norm.y, norm.x, center.x, center.y]);
283 out.line_to(a * Point::new(x:1.0, y:1.0));
284 out.line_to(a * Point::new(x:-1.0, y:1.0));
285 if close {
286 out.close_path();
287 } else {
288 out.line_to(a * Point::new(x:-1.0, y:0.0));
289 }
290}
291
292fn extend_reversed(out: &mut BezPath, elements: &[PathEl]) {
293 for i: usize in (1..elements.len()).rev() {
294 let end: Point = elements[i - 1].end_point().unwrap();
295 match elements[i] {
296 PathEl::LineTo(_) => out.line_to(end),
297 PathEl::QuadTo(p1: Point, _) => out.quad_to(p1, p2:end),
298 PathEl::CurveTo(p1: Point, p2: Point, _) => out.curve_to(p1:p2, p2:p1, p3:end),
299 _ => unreachable!(),
300 }
301 }
302}
303
304fn fit_with_opts(co: &CubicOffset, tolerance: f64, opts: &StrokeOpts) -> BezPath {
305 match opts.opt_level {
306 StrokeOptLevel::Subdivide => fit_to_bezpath(source:co, accuracy:tolerance),
307 StrokeOptLevel::Optimized => fit_to_bezpath_opt(source:co, accuracy:tolerance),
308 }
309}
310
311impl StrokeCtx {
312 /// Append forward and backward paths to output.
313 fn finish(&mut self, style: &Stroke) {
314 // TODO: scale
315 let tolerance = 1e-3;
316 if self.forward_path.is_empty() {
317 return;
318 }
319 self.output.extend(&self.forward_path);
320 let back_els = self.backward_path.elements();
321 let return_p = back_els[back_els.len() - 1].end_point().unwrap();
322 let d = self.last_pt - return_p;
323 match style.end_cap {
324 Cap::Butt => self.output.line_to(return_p),
325 Cap::Round => round_cap(&mut self.output, tolerance, self.last_pt, d),
326 Cap::Square => square_cap(&mut self.output, false, self.last_pt, d),
327 }
328 extend_reversed(&mut self.output, back_els);
329 match style.start_cap {
330 Cap::Butt => self.output.close_path(),
331 Cap::Round => round_cap(&mut self.output, tolerance, self.start_pt, self.start_norm),
332 Cap::Square => square_cap(&mut self.output, true, self.start_pt, self.start_norm),
333 }
334
335 self.forward_path.truncate(0);
336 self.backward_path.truncate(0);
337 }
338
339 /// Finish a closed path
340 fn finish_closed(&mut self, style: &Stroke) {
341 self.do_join(style, self.start_tan);
342 self.output.extend(&self.forward_path);
343 self.output.close_path();
344 let back_els = self.backward_path.elements();
345 let last_pt = back_els[back_els.len() - 1].end_point().unwrap();
346 self.output.move_to(last_pt);
347 extend_reversed(&mut self.output, back_els);
348 self.output.close_path();
349 self.forward_path.truncate(0);
350 self.backward_path.truncate(0);
351 }
352
353 fn do_join(&mut self, style: &Stroke, tan0: Vec2) {
354 // TODO: scale
355 let tolerance = 1e-3;
356 let scale = 0.5 * style.width / tan0.hypot();
357 let norm = scale * Vec2::new(-tan0.y, tan0.x);
358 let p0 = self.last_pt;
359 if self.forward_path.elements().is_empty() {
360 self.forward_path.move_to(p0 - norm);
361 self.backward_path.move_to(p0 + norm);
362 self.start_tan = tan0;
363 self.start_norm = norm;
364 } else {
365 let ab = self.last_tan;
366 let cd = tan0;
367 let cross = ab.cross(cd);
368 let dot = ab.dot(cd);
369 let hypot = cross.hypot(dot);
370 // possible TODO: a minor speedup could be squaring both sides
371 if dot <= 0.0 || cross.abs() >= hypot * self.join_thresh {
372 match style.join {
373 Join::Bevel => {
374 self.forward_path.line_to(p0 - norm);
375 self.backward_path.line_to(p0 + norm);
376 }
377 Join::Miter => {
378 if 2.0 * hypot < (hypot + dot) * style.miter_limit.powi(2) {
379 // TODO: maybe better to store last_norm or derive from path?
380 let last_scale = 0.5 * style.width / ab.hypot();
381 let last_norm = last_scale * Vec2::new(-ab.y, ab.x);
382 if cross > 0.0 {
383 let fp_last = p0 - last_norm;
384 let fp_this = p0 - norm;
385 let h = ab.cross(fp_this - fp_last) / cross;
386 let miter_pt = fp_this - cd * h;
387 self.forward_path.line_to(miter_pt);
388 } else if cross < 0.0 {
389 let fp_last = p0 + last_norm;
390 let fp_this = p0 + norm;
391 let h = ab.cross(fp_this - fp_last) / cross;
392 let miter_pt = fp_this - cd * h;
393 self.backward_path.line_to(miter_pt);
394 }
395 }
396 self.forward_path.line_to(p0 - norm);
397 self.backward_path.line_to(p0 + norm);
398 }
399 Join::Round => {
400 let angle = cross.atan2(dot);
401 if angle > 0.0 {
402 self.backward_path.line_to(p0 + norm);
403 round_join(&mut self.forward_path, tolerance, p0, norm, angle);
404 } else {
405 self.forward_path.line_to(p0 - norm);
406 round_join_rev(&mut self.backward_path, tolerance, p0, -norm, -angle);
407 }
408 }
409 }
410 }
411 }
412 }
413
414 fn do_line(&mut self, style: &Stroke, tangent: Vec2, p1: Point) {
415 let scale = 0.5 * style.width / tangent.hypot();
416 let norm = scale * Vec2::new(-tangent.y, tangent.x);
417 self.forward_path.line_to(p1 - norm);
418 self.backward_path.line_to(p1 + norm);
419 self.last_pt = p1;
420 }
421
422 fn do_cubic(&mut self, style: &Stroke, c: CubicBez, tolerance: f64, opts: &StrokeOpts) {
423 // First, detect degenerate linear case
424
425 // Ordinarily, this is the direction of the chord, but if the chord is very
426 // short, we take the longer control arm.
427 let chord = c.p3 - c.p0;
428 let mut chord_ref = chord;
429 let mut chord_ref_hypot2 = chord_ref.hypot2();
430 let d01 = c.p1 - c.p0;
431 if d01.hypot2() > chord_ref_hypot2 {
432 chord_ref = d01;
433 chord_ref_hypot2 = chord_ref.hypot2();
434 }
435 let d23 = c.p3 - c.p2;
436 if d23.hypot2() > chord_ref_hypot2 {
437 chord_ref = d23;
438 chord_ref_hypot2 = chord_ref.hypot2();
439 }
440 // Project Bézier onto chord
441 let p0 = c.p0.to_vec2().dot(chord_ref);
442 let p1 = c.p1.to_vec2().dot(chord_ref);
443 let p2 = c.p2.to_vec2().dot(chord_ref);
444 let p3 = c.p3.to_vec2().dot(chord_ref);
445 const ENDPOINT_D: f64 = 0.01;
446 if p3 <= p0
447 || p1 > p2
448 || p1 < p0 + ENDPOINT_D * (p3 - p0)
449 || p2 > p3 - ENDPOINT_D * (p3 - p0)
450 {
451 // potentially a cusp inside
452 let x01 = d01.cross(chord_ref);
453 let x23 = d23.cross(chord_ref);
454 let x03 = chord.cross(chord_ref);
455 let thresh = tolerance.powi(2) * chord_ref_hypot2;
456 if x01 * x01 < thresh && x23 * x23 < thresh && x03 * x03 < thresh {
457 // control points are nearly co-linear
458 let midpoint = c.p0.midpoint(c.p3);
459 // Mapping back from projection of reference chord
460 let ref_vec = chord_ref / chord_ref_hypot2;
461 let ref_pt = midpoint - 0.5 * (p0 + p3) * ref_vec;
462 self.do_linear(style, c, [p0, p1, p2, p3], ref_pt, ref_vec);
463 return;
464 }
465 }
466
467 // A tuning parameter for regularization. A value too large may distort the curve,
468 // while a value too small may fail to generate smooth curves. This is a somewhat
469 // arbitrary value, and should be revisited.
470 const DIM_TUNE: f64 = 0.25;
471 let dimension = tolerance * DIM_TUNE;
472 let co = CubicOffset::new_regularized(c, -0.5 * style.width, dimension);
473 let forward = fit_with_opts(&co, tolerance, opts);
474 self.forward_path.extend(forward.into_iter().skip(1));
475 let co = CubicOffset::new_regularized(c, 0.5 * style.width, dimension);
476 let backward = fit_with_opts(&co, tolerance, opts);
477 self.backward_path.extend(backward.into_iter().skip(1));
478 self.last_pt = c.p3;
479 }
480
481 /// Do a cubic which is actually linear.
482 ///
483 /// The `p` argument is the control points projected to the reference chord.
484 /// The ref arguments are the inverse map of a projection back to the client
485 /// coordinate space.
486 fn do_linear(
487 &mut self,
488 style: &Stroke,
489 c: CubicBez,
490 p: [f64; 4],
491 ref_pt: Point,
492 ref_vec: Vec2,
493 ) {
494 // Always do round join, to model cusp as limit of finite curvature (see Nehab).
495 let style = Stroke::new(style.width).with_join(Join::Round);
496 // Tangents of endpoints (for connecting to joins)
497 let (tan0, tan1) = PathSeg::Cubic(c).tangents();
498 self.last_tan = tan0;
499 // find cusps
500 let c0 = p[1] - p[0];
501 let c1 = 2.0 * p[2] - 4.0 * p[1] + 2.0 * p[0];
502 let c2 = p[3] - 3.0 * p[2] + 3.0 * p[1] - p[0];
503 let roots = solve_quadratic(c0, c1, c2);
504 // discard cusps right at endpoints
505 const EPSILON: f64 = 1e-12;
506 for t in roots {
507 if t > EPSILON && t < 1.0 - EPSILON {
508 let mt = 1.0 - t;
509 let z = mt * (mt * mt * p[0] + 3.0 * t * (mt * p[1] + t * p[2])) + t * t * t * p[3];
510 let p = ref_pt + z * ref_vec;
511 let tan = p - self.last_pt;
512 self.do_join(&style, tan);
513 self.do_line(&style, tan, p);
514 self.last_tan = tan;
515 }
516 }
517 let tan = c.p3 - self.last_pt;
518 self.do_join(&style, tan);
519 self.do_line(&style, tan, c.p3);
520 self.last_tan = tan;
521 self.do_join(&style, tan1);
522 }
523}
524
525/// An implementation of dashing as an iterator-to-iterator transformation.
526#[doc(hidden)]
527pub struct DashIterator<'a, T> {
528 inner: T,
529 input_done: bool,
530 closepath_pending: bool,
531 dashes: &'a [f64],
532 dash_ix: usize,
533 init_dash_ix: usize,
534 init_dash_remaining: f64,
535 init_is_active: bool,
536 is_active: bool,
537 state: DashState,
538 current_seg: PathSeg,
539 t: f64,
540 dash_remaining: f64,
541 seg_remaining: f64,
542 start_pt: Point,
543 last_pt: Point,
544 stash: Vec<PathEl>,
545 stash_ix: usize,
546}
547
548#[derive(PartialEq, Eq)]
549enum DashState {
550 NeedInput,
551 ToStash,
552 Working,
553 FromStash,
554}
555
556impl<'a, T: Iterator<Item = PathEl>> Iterator for DashIterator<'a, T> {
557 type Item = PathEl;
558
559 fn next(&mut self) -> Option<PathEl> {
560 loop {
561 match self.state {
562 DashState::NeedInput => {
563 if self.input_done {
564 return None;
565 }
566 self.get_input();
567 if self.input_done {
568 return None;
569 }
570 self.state = DashState::ToStash;
571 }
572 DashState::ToStash => {
573 if let Some(el) = self.step() {
574 self.stash.push(el);
575 }
576 }
577 DashState::Working => {
578 if let Some(el) = self.step() {
579 return Some(el);
580 }
581 }
582 DashState::FromStash => {
583 if let Some(el) = self.stash.get(self.stash_ix) {
584 self.stash_ix += 1;
585 return Some(*el);
586 } else {
587 self.stash.clear();
588 self.stash_ix = 0;
589 if self.input_done {
590 return None;
591 }
592 if self.closepath_pending {
593 self.closepath_pending = false;
594 self.state = DashState::NeedInput;
595 } else {
596 self.state = DashState::ToStash;
597 }
598 }
599 }
600 }
601 }
602 }
603}
604
605fn seg_to_el(el: &PathSeg) -> PathEl {
606 match el {
607 PathSeg::Line(l: &Line) => PathEl::LineTo(l.p1),
608 PathSeg::Quad(q: &QuadBez) => PathEl::QuadTo(q.p1, q.p2),
609 PathSeg::Cubic(c: &CubicBez) => PathEl::CurveTo(c.p1, c.p2, c.p3),
610 }
611}
612
613const DASH_ACCURACY: f64 = 1e-6;
614
615/// Create a new dashing iterator.
616///
617/// Handling of dashes is fairly orthogonal to stroke expansion. This iterator
618/// is an internal detail of the stroke expansion logic, but is also available
619/// separately, and is expected to be useful when doing stroke expansion on
620/// GPU.
621///
622/// It is implemented as an iterator-to-iterator transform. Because it consumes
623/// the input sequentially and produces consistent output with correct joins,
624/// it requires internal state and may allocate.
625///
626/// Accuracy is currently hard-coded to 1e-6. This is better than generally
627/// expected, and care is taken to get cusps correct, among other things.
628pub fn dash<'a>(
629 inner: impl Iterator<Item = PathEl> + 'a,
630 dash_offset: f64,
631 dashes: &'a [f64],
632) -> impl Iterator<Item = PathEl> + 'a {
633 dash_impl(inner, dash_offset, dashes)
634}
635
636// This is only a separate function to make `DashIterator::new()` typecheck.
637fn dash_impl<T: Iterator<Item = PathEl>>(
638 inner: T,
639 dash_offset: f64,
640 dashes: &[f64],
641) -> DashIterator<T> {
642 let mut dash_ix = 0;
643 let mut dash_remaining = dash_offset;
644 let mut is_active = true;
645 // Find place in dashes array for initial offset.
646 while dash_remaining > 0.0 {
647 let dash_len = dashes[dash_ix];
648 if dash_remaining < dash_len {
649 break;
650 }
651 dash_remaining -= dash_len;
652 dash_ix = (dash_ix + 1) % dashes.len();
653 is_active = !is_active;
654 }
655 DashIterator {
656 inner,
657 input_done: false,
658 closepath_pending: false,
659 dashes,
660 dash_ix,
661 init_dash_ix: dash_ix,
662 init_dash_remaining: dash_remaining,
663 init_is_active: is_active,
664 is_active,
665 state: DashState::NeedInput,
666 current_seg: PathSeg::Line(Line::new(Point::ORIGIN, Point::ORIGIN)),
667 t: 0.0,
668 dash_remaining,
669 seg_remaining: 0.0,
670 start_pt: Point::ORIGIN,
671 last_pt: Point::ORIGIN,
672 stash: Vec::new(),
673 stash_ix: 0,
674 }
675}
676
677impl<'a, T: Iterator<Item = PathEl>> DashIterator<'a, T> {
678 #[doc(hidden)]
679 #[deprecated(since = "0.10.4", note = "use dash() instead")]
680 pub fn new(inner: T, dash_offset: f64, dashes: &'a [f64]) -> Self {
681 dash_impl(inner, dash_offset, dashes)
682 }
683
684 fn get_input(&mut self) {
685 loop {
686 if self.closepath_pending {
687 self.handle_closepath();
688 break;
689 }
690 let Some(next_el) = self.inner.next() else {
691 self.input_done = true;
692 self.state = DashState::FromStash;
693 return;
694 };
695 let p0 = self.last_pt;
696 match next_el {
697 PathEl::MoveTo(p) => {
698 if !self.stash.is_empty() {
699 self.state = DashState::FromStash;
700 }
701 self.start_pt = p;
702 self.last_pt = p;
703 self.reset_phase();
704 continue;
705 }
706 PathEl::LineTo(p1) => {
707 let l = Line::new(p0, p1);
708 self.seg_remaining = l.arclen(DASH_ACCURACY);
709 self.current_seg = PathSeg::Line(l);
710 self.last_pt = p1;
711 }
712 PathEl::QuadTo(p1, p2) => {
713 let q = QuadBez::new(p0, p1, p2);
714 self.seg_remaining = q.arclen(DASH_ACCURACY);
715 self.current_seg = PathSeg::Quad(q);
716 self.last_pt = p2;
717 }
718 PathEl::CurveTo(p1, p2, p3) => {
719 let c = CubicBez::new(p0, p1, p2, p3);
720 self.seg_remaining = c.arclen(DASH_ACCURACY);
721 self.current_seg = PathSeg::Cubic(c);
722 self.last_pt = p3;
723 }
724 PathEl::ClosePath => {
725 self.closepath_pending = true;
726 if p0 != self.start_pt {
727 let l = Line::new(p0, self.start_pt);
728 self.seg_remaining = l.arclen(DASH_ACCURACY);
729 self.current_seg = PathSeg::Line(l);
730 self.last_pt = self.start_pt;
731 } else {
732 self.handle_closepath();
733 }
734 }
735 }
736 break;
737 }
738 self.t = 0.0;
739 }
740
741 /// Move arc length forward to next event.
742 fn step(&mut self) -> Option<PathEl> {
743 let mut result = None;
744 if self.state == DashState::ToStash && self.stash.is_empty() {
745 if self.is_active {
746 result = Some(PathEl::MoveTo(self.current_seg.start()));
747 } else {
748 self.state = DashState::Working;
749 }
750 } else if self.dash_remaining < self.seg_remaining {
751 // next transition is a dash transition
752 let seg = self.current_seg.subsegment(self.t..1.0);
753 let t1 = seg.inv_arclen(self.dash_remaining, DASH_ACCURACY);
754 if self.is_active {
755 let subseg = seg.subsegment(0.0..t1);
756 result = Some(seg_to_el(&subseg));
757 self.state = DashState::Working;
758 } else {
759 let p = seg.eval(t1);
760 result = Some(PathEl::MoveTo(p));
761 }
762 self.is_active = !self.is_active;
763 self.t += t1 * (1.0 - self.t);
764 self.seg_remaining -= self.dash_remaining;
765 self.dash_ix += 1;
766 if self.dash_ix == self.dashes.len() {
767 self.dash_ix = 0;
768 }
769 self.dash_remaining = self.dashes[self.dash_ix];
770 } else {
771 if self.is_active {
772 let seg = self.current_seg.subsegment(self.t..1.0);
773 result = Some(seg_to_el(&seg));
774 }
775 self.dash_remaining -= self.seg_remaining;
776 self.get_input();
777 }
778 result
779 }
780
781 fn handle_closepath(&mut self) {
782 if self.state == DashState::ToStash {
783 // Have looped back without breaking a dash, just play it back
784 self.stash.push(PathEl::ClosePath);
785 } else if self.is_active {
786 // connect with path in stash, skip MoveTo.
787 self.stash_ix = 1;
788 }
789 self.state = DashState::FromStash;
790 self.reset_phase();
791 }
792
793 fn reset_phase(&mut self) {
794 self.dash_ix = self.init_dash_ix;
795 self.dash_remaining = self.init_dash_remaining;
796 self.is_active = self.init_is_active;
797 }
798}
799
800#[cfg(test)]
801mod tests {
802 use crate::{stroke, Cap::Butt, CubicBez, Join::Miter, Shape, Stroke};
803
804 // A degenerate stroke with a cusp at the endpoint.
805 #[test]
806 fn pathological_stroke() {
807 let curve = CubicBez::new(
808 (602.469, 286.585),
809 (641.975, 286.585),
810 (562.963, 286.585),
811 (562.963, 286.585),
812 );
813 let path = curve.into_path(0.1);
814 let stroke_style = Stroke::new(1.);
815 let stroked = stroke(path, &stroke_style, &Default::default(), 0.001);
816 assert!(stroked.is_finite());
817 }
818
819 // Test cases adapted from https://github.com/linebender/vello/pull/388
820 #[test]
821 fn broken_strokes() {
822 let broken_cubics = [
823 [(0., -0.01), (128., 128.001), (128., -0.01), (0., 128.001)], // Near-cusp
824 [(0., 0.), (0., -10.), (0., -10.), (0., 10.)], // Flat line with 180
825 [(10., 0.), (0., 0.), (20., 0.), (10., 0.)], // Flat line with 2 180s
826 [(39., -39.), (40., -40.), (40., -40.), (0., 0.)], // Flat diagonal with 180
827 [(40., 40.), (0., 0.), (200., 200.), (0., 0.)], // Diag w/ an internal 180
828 [(0., 0.), (1e-2, 0.), (-1e-2, 0.), (0., 0.)], // Circle
829 // Flat line with no turns:
830 [
831 (400.75, 100.05),
832 (400.75, 100.05),
833 (100.05, 300.95),
834 (100.05, 300.95),
835 ],
836 [(0.5, 0.), (0., 0.), (20., 0.), (10., 0.)], // Flat line with 2 180s
837 [(10., 0.), (0., 0.), (10., 0.), (10., 0.)], // Flat line with a 180
838 ];
839 let stroke_style = Stroke::new(30.).with_caps(Butt).with_join(Miter);
840 for cubic in &broken_cubics {
841 let path = CubicBez::new(cubic[0], cubic[1], cubic[2], cubic[3]).into_path(0.1);
842 let stroked = stroke(path, &stroke_style, &Default::default(), 0.001);
843 assert!(stroked.is_finite());
844 }
845 }
846}
847