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