kurbo/
stroke.rs

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    Affine, Arc, BezPath, CubicBez, Line, ParamCurve, ParamCurveArclen, PathEl, PathSeg, Point,
15    QuadBez, Vec2, common::solve_quadratic,
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/// The visual style of a stroke.
45#[derive(Clone, Debug, PartialEq)]
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.
66#[derive(Clone, Copy, Debug, PartialEq)]
67pub struct StrokeOpts {
68    opt_level: StrokeOptLevel,
69    /// When `true`, dashes are emitted in the order they appear along the path. The default `false` delays a subpath's first dash so it can be merged with a dash that wraps through `ClosePath`; this option disables both the reorder and the wraparound merge, so a dash spanning the seam is truncated there.
70    stable_dash_order: bool,
71}
72
73/// Optimization level for computing stroke outlines.
74///
75/// Note that in the current implementation, this setting has no effect.
76/// However, having a tradeoff between optimization of number of segments
77/// and speed makes sense and may be added in the future, so applications
78/// should set it appropriately. For real time rendering, the appropriate
79/// value is `Subdivide`.
80#[derive(Clone, Copy, Debug, Eq, PartialEq)]
81pub enum StrokeOptLevel {
82    /// Adaptively subdivide segments in half.
83    Subdivide,
84    /// Compute optimized subdivision points to minimize error.
85    Optimized,
86}
87
88impl Default for StrokeOpts {
89    fn default() -> Self {
90        let opt_level = StrokeOptLevel::Subdivide;
91        StrokeOpts {
92            opt_level,
93            stable_dash_order: false,
94        }
95    }
96}
97
98impl Default for Stroke {
99    fn default() -> Self {
100        Self::new(1.0)
101    }
102}
103
104impl Stroke {
105    /// Creates a new stroke with the specified width.
106    pub const fn new(width: f64) -> Self {
107        Self {
108            width,
109            join: Join::Round,
110            miter_limit: 4.0,
111            start_cap: Cap::Round,
112            end_cap: Cap::Round,
113            dash_pattern: SmallVec::new_const(),
114            dash_offset: 0.0,
115        }
116    }
117
118    /// Builder method for setting the join style.
119    pub const fn with_join(mut self, join: Join) -> Self {
120        self.join = join;
121        self
122    }
123
124    /// Builder method for setting the limit for miter joins.
125    pub const fn with_miter_limit(mut self, limit: f64) -> Self {
126        self.miter_limit = limit;
127        self
128    }
129
130    /// Builder method for setting the cap style for the start of the stroke.
131    pub const fn with_start_cap(mut self, cap: Cap) -> Self {
132        self.start_cap = cap;
133        self
134    }
135
136    /// Builder method for setting the cap style for the end of the stroke.
137    pub const fn with_end_cap(mut self, cap: Cap) -> Self {
138        self.end_cap = cap;
139        self
140    }
141
142    /// Builder method for setting the cap style.
143    pub const fn with_caps(mut self, cap: Cap) -> Self {
144        self.start_cap = cap;
145        self.end_cap = cap;
146        self
147    }
148
149    /// Builder method for setting the dashing parameters.
150    pub fn with_dashes<P>(mut self, offset: f64, pattern: P) -> Self
151    where
152        P: IntoIterator,
153        P::Item: Borrow<f64>,
154    {
155        self.dash_offset = offset;
156        self.dash_pattern.clear();
157        self.dash_pattern
158            .extend(pattern.into_iter().map(|dash| *dash.borrow()));
159        self
160    }
161
162    /// Returns `true` if all floating-point stroke parameters are [finite].
163    ///
164    /// [finite]: f64::is_finite
165    pub fn is_finite(&self) -> bool {
166        self.width.is_finite()
167            && self.miter_limit.is_finite()
168            && self.dash_offset.is_finite()
169            && self.dash_pattern.iter().all(|dash| dash.is_finite())
170    }
171
172    /// Returns `true` if any floating-point stroke parameter is [`NaN`].
173    ///
174    /// [`NaN`]: f64::is_nan
175    pub fn is_nan(&self) -> bool {
176        self.width.is_nan()
177            || self.miter_limit.is_nan()
178            || self.dash_offset.is_nan()
179            || self.dash_pattern.iter().any(|dash| dash.is_nan())
180    }
181}
182
183impl StrokeOpts {
184    /// Set optimization level for computing stroke outlines.
185    pub fn opt_level(mut self, opt_level: StrokeOptLevel) -> Self {
186        self.opt_level = opt_level;
187        self
188    }
189
190    /// When `true`, dashes are emitted in the order they appear along the path.
191    pub fn stable_dash_order(mut self, stable: bool) -> Self {
192        self.stable_dash_order = stable;
193        self
194    }
195}
196
197/// Collection of values representing lengths in a dash pattern.
198pub type Dashes = SmallVec<[f64; 4]>;
199
200/// A structure that is used for creating strokes.
201///
202/// See also [`stroke_with`].
203#[derive(Default, Debug)]
204pub struct StrokeCtx {
205    // As a possible future optimization, we might not need separate storage
206    // for forward and backward paths, we can add forward to the output in-place.
207    // However, this structure is clearer and the cost fairly modest.
208    output: BezPath,
209    forward_path: BezPath,
210    backward_path: BezPath,
211    result_path: BezPath,
212    start_pt: Point,
213    start_norm: Vec2,
214    start_tan: Vec2,
215    last_pt: Point,
216    last_tan: Vec2,
217    // Precomputation of the join threshold, to optimize per-join logic.
218    // If hypot < (hypot + dot) * join_thresh, omit join altogether.
219    join_thresh: f64,
220}
221
222impl StrokeCtx {
223    /// Return the path that defines the expanded stroke.
224    pub fn output(&self) -> &BezPath {
225        &self.output
226    }
227}
228
229impl StrokeCtx {
230    fn reset(&mut self) {
231        self.output.truncate(0);
232        self.forward_path.truncate(0);
233        self.backward_path.truncate(0);
234        self.start_pt = Point::default();
235        self.start_norm = Vec2::default();
236        self.start_tan = Vec2::default();
237        self.last_pt = Point::default();
238        self.last_tan = Vec2::default();
239        self.join_thresh = 0.0;
240    }
241}
242
243/// Expand a stroke into a fill.
244///
245/// The `tolerance` parameter controls the accuracy of the result. In general,
246/// the number of subdivisions in the output scales at least to the -1/4 power
247/// of the parameter, for example making it 1/16 as big generates twice as many
248/// segments. Currently the algorithm is not tuned for extremely fine tolerances.
249/// The theoretically optimum scaling exponent is -1/6, but achieving this may
250/// require slow numerical techniques (currently a subject of research). The
251/// appropriate value depends on the application; if the result of the stroke
252/// will be scaled up, a smaller value is needed.
253///
254/// This method attempts a fairly high degree of correctness, but ultimately
255/// is based on computing parallel curves and adding joins and caps, rather than
256/// computing the rigorously correct parallel sweep (which requires evolutes in
257/// the general case). See [Nehab 2020] for more discussion.
258///
259/// [Nehab 2020]: https://dl.acm.org/doi/10.1145/3386569.3392392
260pub fn stroke(
261    path: impl IntoIterator<Item = PathEl>,
262    style: &Stroke,
263    opts: &StrokeOpts,
264    tolerance: f64,
265) -> BezPath {
266    let mut ctx = StrokeCtx::default();
267    stroke_with(path, style, opts, tolerance, &mut ctx);
268
269    ctx.output
270}
271
272/// Expand a stroke into a fill.
273///
274/// This is the same as [`stroke`], except for the fact that you can explicitly pass a
275/// `StrokeCtx`. By doing so, you can reuse the same context over multiple calls and ensure
276/// that the number of reallocations is minimized.
277///
278/// Unlike [`stroke`], this method doesn't return an owned version of the expanded stroke as a
279/// [`BezPath`]. Instead, you can get a reference to the resulting path by calling
280/// [`StrokeCtx::output`].
281pub fn stroke_with(
282    path: impl IntoIterator<Item = PathEl>,
283    style: &Stroke,
284    opts: &StrokeOpts,
285    tolerance: f64,
286    ctx: &mut StrokeCtx,
287) {
288    if style.dash_pattern.is_empty() {
289        stroke_undashed(path, style, tolerance, ctx);
290    } else {
291        let dashed = dash_iter(
292            path.into_iter(),
293            style.dash_offset,
294            &style.dash_pattern,
295            opts.stable_dash_order,
296        );
297        stroke_undashed(dashed, style, tolerance, ctx);
298    }
299}
300
301/// Version of stroke expansion for styles with no dashes.
302fn stroke_undashed(
303    path: impl IntoIterator<Item = PathEl>,
304    style: &Stroke,
305    tolerance: f64,
306    ctx: &mut StrokeCtx,
307) {
308    ctx.reset();
309    ctx.join_thresh = 2.0 * tolerance / style.width;
310
311    for el in path {
312        let p0 = ctx.last_pt;
313        match el {
314            PathEl::MoveTo(p) => {
315                ctx.finish(style);
316                ctx.start_pt = p;
317                ctx.last_pt = p;
318            }
319            PathEl::LineTo(p1) => {
320                if p1 != p0 {
321                    let tangent = p1 - p0;
322                    ctx.do_join(style, tangent);
323                    ctx.last_tan = tangent;
324                    ctx.do_line(style, tangent, p1);
325                }
326            }
327            PathEl::QuadTo(p1, p2) => {
328                if p1 != p0 || p2 != p0 {
329                    let q = QuadBez::new(p0, p1, p2);
330                    let (tan0, tan1) = PathSeg::Quad(q).tangents();
331                    ctx.do_join(style, tan0);
332                    ctx.do_cubic(style, q.raise(), tolerance);
333                    ctx.last_tan = tan1;
334                }
335            }
336            PathEl::CurveTo(p1, p2, p3) => {
337                if p1 != p0 || p2 != p0 || p3 != p0 {
338                    let c = CubicBez::new(p0, p1, p2, p3);
339                    let (tan0, tan1) = PathSeg::Cubic(c).tangents();
340                    ctx.do_join(style, tan0);
341                    ctx.do_cubic(style, c, tolerance);
342                    ctx.last_tan = tan1;
343                }
344            }
345            PathEl::ClosePath => {
346                if p0 != ctx.start_pt {
347                    let tangent = ctx.start_pt - p0;
348                    ctx.do_join(style, tangent);
349                    ctx.last_tan = tangent;
350                    ctx.do_line(style, tangent, ctx.start_pt);
351                }
352                ctx.finish_closed(style);
353            }
354        }
355    }
356    ctx.finish(style);
357}
358
359fn round_cap(out: &mut BezPath, tolerance: f64, center: Point, norm: Vec2) {
360    round_join(out, tolerance, center, norm, PI);
361}
362
363fn round_join(out: &mut BezPath, tolerance: f64, center: Point, norm: Vec2, angle: f64) {
364    let a = Affine::new([norm.x, norm.y, -norm.y, norm.x, center.x, center.y]);
365    let arc = Arc::new(Point::ORIGIN, (1.0, 1.0), PI - angle, angle, 0.0);
366    arc.to_cubic_beziers(tolerance, |p1, p2, p3| out.curve_to(a * p1, a * p2, a * p3));
367}
368
369fn round_join_rev(out: &mut BezPath, tolerance: f64, center: Point, norm: Vec2, angle: f64) {
370    let a = Affine::new([norm.x, norm.y, norm.y, -norm.x, center.x, center.y]);
371    let arc = Arc::new(Point::ORIGIN, (1.0, 1.0), PI - angle, angle, 0.0);
372    arc.to_cubic_beziers(tolerance, |p1, p2, p3| out.curve_to(a * p1, a * p2, a * p3));
373}
374
375fn square_cap(out: &mut BezPath, close: bool, center: Point, norm: Vec2) {
376    let a = Affine::new([norm.x, norm.y, -norm.y, norm.x, center.x, center.y]);
377    out.line_to(a * Point::new(1.0, 1.0));
378    out.line_to(a * Point::new(-1.0, 1.0));
379    if close {
380        out.close_path();
381    } else {
382        out.line_to(a * Point::new(-1.0, 0.0));
383    }
384}
385
386fn extend_reversed(out: &mut BezPath, elements: &[PathEl]) {
387    for i in (1..elements.len()).rev() {
388        let end = elements[i - 1].end_point().unwrap();
389        match elements[i] {
390            PathEl::LineTo(_) => out.line_to(end),
391            PathEl::QuadTo(p1, _) => out.quad_to(p1, end),
392            PathEl::CurveTo(p1, p2, _) => out.curve_to(p2, p1, end),
393            _ => unreachable!(),
394        }
395    }
396}
397
398impl StrokeCtx {
399    /// Append forward and backward paths to output.
400    fn finish(&mut self, style: &Stroke) {
401        // TODO: scale
402        let tolerance = 1e-3;
403        if self.forward_path.is_empty() {
404            return;
405        }
406        self.output.extend(&self.forward_path);
407        let back_els = self.backward_path.elements();
408        let return_p = back_els[back_els.len() - 1].end_point().unwrap();
409        let d = self.last_pt - return_p;
410        match style.end_cap {
411            Cap::Butt => self.output.line_to(return_p),
412            Cap::Round => round_cap(&mut self.output, tolerance, self.last_pt, d),
413            Cap::Square => square_cap(&mut self.output, false, self.last_pt, d),
414        }
415        extend_reversed(&mut self.output, back_els);
416        match style.start_cap {
417            Cap::Butt => self.output.close_path(),
418            Cap::Round => round_cap(&mut self.output, tolerance, self.start_pt, self.start_norm),
419            Cap::Square => square_cap(&mut self.output, true, self.start_pt, self.start_norm),
420        }
421
422        self.forward_path.truncate(0);
423        self.backward_path.truncate(0);
424    }
425
426    /// Finish a closed path
427    fn finish_closed(&mut self, style: &Stroke) {
428        if self.forward_path.is_empty() {
429            return;
430        }
431        self.do_join(style, self.start_tan);
432        self.output.extend(&self.forward_path);
433        self.output.close_path();
434        let back_els = self.backward_path.elements();
435        let last_pt = back_els[back_els.len() - 1].end_point().unwrap();
436        self.output.move_to(last_pt);
437        extend_reversed(&mut self.output, back_els);
438        self.output.close_path();
439        self.forward_path.truncate(0);
440        self.backward_path.truncate(0);
441    }
442
443    fn do_join(&mut self, style: &Stroke, tan0: Vec2) {
444        // TODO: scale
445        let tolerance = 1e-3;
446        let scale = 0.5 * style.width / tan0.hypot();
447        let norm = scale * Vec2::new(-tan0.y, tan0.x);
448        let p0 = self.last_pt;
449        if self.forward_path.elements().is_empty() {
450            self.forward_path.move_to(p0 - norm);
451            self.backward_path.move_to(p0 + norm);
452            self.start_tan = tan0;
453            self.start_norm = norm;
454        } else {
455            let ab = self.last_tan;
456            let cd = tan0;
457            let cross = ab.cross(cd);
458            let dot = ab.dot(cd);
459            let hypot = cross.hypot(dot);
460            // possible TODO: a minor speedup could be squaring both sides
461            if dot <= 0.0 || cross.abs() >= hypot * self.join_thresh {
462                match style.join {
463                    Join::Bevel => {
464                        self.forward_path.line_to(p0 - norm);
465                        self.backward_path.line_to(p0 + norm);
466                    }
467                    Join::Miter => {
468                        if 2.0 * hypot < (hypot + dot) * style.miter_limit.powi(2) {
469                            // TODO: maybe better to store last_norm or derive from path?
470                            let last_scale = 0.5 * style.width / ab.hypot();
471                            let last_norm = last_scale * Vec2::new(-ab.y, ab.x);
472                            if cross > 0.0 {
473                                let fp_last = p0 - last_norm;
474                                let fp_this = p0 - norm;
475                                let h = ab.cross(fp_this - fp_last) / cross;
476                                let miter_pt = fp_this - cd * h;
477                                self.forward_path.line_to(miter_pt);
478                                self.backward_path.line_to(p0);
479                            } else if cross < 0.0 {
480                                let fp_last = p0 + last_norm;
481                                let fp_this = p0 + norm;
482                                let h = ab.cross(fp_this - fp_last) / cross;
483                                let miter_pt = fp_this - cd * h;
484                                self.backward_path.line_to(miter_pt);
485                                self.forward_path.line_to(p0);
486                            }
487                        }
488                        self.forward_path.line_to(p0 - norm);
489                        self.backward_path.line_to(p0 + norm);
490                    }
491                    Join::Round => {
492                        let angle = cross.atan2(dot);
493                        if angle > 0.0 {
494                            self.backward_path.line_to(p0 + norm);
495                            round_join(&mut self.forward_path, tolerance, p0, norm, angle);
496                        } else {
497                            self.forward_path.line_to(p0 - norm);
498                            round_join_rev(&mut self.backward_path, tolerance, p0, -norm, -angle);
499                        }
500                    }
501                }
502            }
503        }
504    }
505
506    fn do_line(&mut self, style: &Stroke, tangent: Vec2, p1: Point) {
507        let scale = 0.5 * style.width / tangent.hypot();
508        let norm = scale * Vec2::new(-tangent.y, tangent.x);
509        self.forward_path.line_to(p1 - norm);
510        self.backward_path.line_to(p1 + norm);
511        self.last_pt = p1;
512    }
513
514    fn do_cubic(&mut self, style: &Stroke, c: CubicBez, tolerance: f64) {
515        // First, detect degenerate linear case
516
517        // Ordinarily, this is the direction of the chord, but if the chord is very
518        // short, we take the longer control arm.
519        let chord = c.p3 - c.p0;
520        let mut chord_ref = chord;
521        let mut chord_ref_hypot2 = chord_ref.hypot2();
522        let d01 = c.p1 - c.p0;
523        if d01.hypot2() > chord_ref_hypot2 {
524            chord_ref = d01;
525            chord_ref_hypot2 = chord_ref.hypot2();
526        }
527        let d23 = c.p3 - c.p2;
528        if d23.hypot2() > chord_ref_hypot2 {
529            chord_ref = d23;
530            chord_ref_hypot2 = chord_ref.hypot2();
531        }
532        // Project Bézier onto chord
533        let p0 = c.p0.to_vec2().dot(chord_ref);
534        let p1 = c.p1.to_vec2().dot(chord_ref);
535        let p2 = c.p2.to_vec2().dot(chord_ref);
536        let p3 = c.p3.to_vec2().dot(chord_ref);
537        const ENDPOINT_D: f64 = 0.01;
538        if p3 <= p0
539            || p1 > p2
540            || p1 < p0 + ENDPOINT_D * (p3 - p0)
541            || p2 > p3 - ENDPOINT_D * (p3 - p0)
542        {
543            // potentially a cusp inside
544            let x01 = d01.cross(chord_ref);
545            let x23 = d23.cross(chord_ref);
546            let x03 = chord.cross(chord_ref);
547            let thresh = tolerance.powi(2) * chord_ref_hypot2;
548            if x01 * x01 < thresh && x23 * x23 < thresh && x03 * x03 < thresh {
549                // control points are nearly co-linear
550                let midpoint = c.p0.midpoint(c.p3);
551                // Mapping back from projection of reference chord
552                let ref_vec = chord_ref / chord_ref_hypot2;
553                let ref_pt = midpoint - 0.5 * (p0 + p3) * ref_vec;
554                self.do_linear(style, c, [p0, p1, p2, p3], ref_pt, ref_vec);
555                return;
556            }
557        }
558
559        crate::offset::offset_cubic(c, -0.5 * style.width, tolerance, &mut self.result_path);
560        self.forward_path.extend(self.result_path.iter().skip(1));
561        crate::offset::offset_cubic(c, 0.5 * style.width, tolerance, &mut self.result_path);
562        self.backward_path.extend(self.result_path.iter().skip(1));
563        self.last_pt = c.p3;
564    }
565
566    /// Do a cubic which is actually linear.
567    ///
568    /// The `p` argument is the control points projected to the reference chord.
569    /// The ref arguments are the inverse map of a projection back to the client
570    /// coordinate space.
571    fn do_linear(
572        &mut self,
573        style: &Stroke,
574        c: CubicBez,
575        p: [f64; 4],
576        ref_pt: Point,
577        ref_vec: Vec2,
578    ) {
579        // Always do round join, to model cusp as limit of finite curvature (see Nehab).
580        let style = Stroke::new(style.width).with_join(Join::Round);
581        // Tangents of endpoints (for connecting to joins)
582        let (tan0, tan1) = PathSeg::Cubic(c).tangents();
583        self.last_tan = tan0;
584        // find cusps
585        let c0 = p[1] - p[0];
586        let c1 = 2.0 * p[2] - 4.0 * p[1] + 2.0 * p[0];
587        let c2 = p[3] - 3.0 * p[2] + 3.0 * p[1] - p[0];
588        let roots = solve_quadratic(c0, c1, c2);
589        // discard cusps right at endpoints
590        const EPSILON: f64 = 1e-6;
591        for t in roots {
592            if t > EPSILON && t < 1.0 - EPSILON {
593                let mt = 1.0 - t;
594                let z = mt * (mt * mt * p[0] + 3.0 * t * (mt * p[1] + t * p[2])) + t * t * t * p[3];
595                let p = ref_pt + z * ref_vec;
596                let tan = p - self.last_pt;
597                self.do_join(&style, tan);
598                self.do_line(&style, tan, p);
599                self.last_tan = tan;
600            }
601        }
602        let tan = c.p3 - self.last_pt;
603        self.do_join(&style, tan);
604        self.do_line(&style, tan, c.p3);
605        self.last_tan = tan;
606        self.do_join(&style, tan1);
607    }
608}
609
610/// An implementation of dashing as an iterator-to-iterator transformation.
611struct DashIterator<'a, T> {
612    inner: T,
613    input_done: bool,
614    closepath_pending: bool,
615    dashes: &'a [f64],
616    dash_ix: usize,
617    init_dash_ix: usize,
618    init_dash_remaining: f64,
619    init_is_active: bool,
620    is_active: bool,
621    state: DashState,
622    current_seg: PathSeg,
623    t: f64,
624    dash_remaining: f64,
625    seg_remaining: f64,
626    start_pt: Point,
627    last_pt: Point,
628    stash: Vec<PathEl>,
629    stash_ix: usize,
630    stable_dash_order: bool,
631    needs_moveto: bool,
632}
633
634#[derive(PartialEq, Eq)]
635enum DashState {
636    NeedInput,
637    ToStash,
638    Working,
639    FromStash,
640}
641
642impl<T: Iterator<Item = PathEl>> Iterator for DashIterator<'_, T> {
643    type Item = PathEl;
644
645    fn next(&mut self) -> Option<PathEl> {
646        loop {
647            match self.state {
648                DashState::NeedInput => {
649                    if self.input_done {
650                        return None;
651                    }
652                    self.get_input();
653                    if self.input_done {
654                        return None;
655                    }
656                    self.state = DashState::ToStash;
657                }
658                DashState::ToStash => {
659                    if let Some(el) = self.step() {
660                        if self.stable_dash_order {
661                            return Some(el);
662                        }
663                        self.stash.push(el);
664                    }
665                }
666                DashState::Working => {
667                    if let Some(el) = self.step() {
668                        return Some(el);
669                    }
670                }
671                DashState::FromStash => {
672                    if let Some(el) = self.stash.get(self.stash_ix) {
673                        self.stash_ix += 1;
674                        return Some(*el);
675                    } else {
676                        self.stash.clear();
677                        self.stash_ix = 0;
678                        if self.input_done {
679                            return None;
680                        }
681                        if self.closepath_pending {
682                            self.closepath_pending = false;
683                            self.state = DashState::NeedInput;
684                        } else {
685                            self.state = DashState::ToStash;
686                        }
687                    }
688                }
689            }
690        }
691    }
692}
693
694fn seg_to_el(el: &PathSeg) -> PathEl {
695    match el {
696        PathSeg::Line(l) => PathEl::LineTo(l.p1),
697        PathSeg::Quad(q) => PathEl::QuadTo(q.p1, q.p2),
698        PathSeg::Cubic(c) => PathEl::CurveTo(c.p1, c.p2, c.p3),
699    }
700}
701
702const DASH_ACCURACY: f64 = 1e-6;
703
704/// Create a new dashing iterator.
705///
706/// Handling of dashes is fairly orthogonal to stroke expansion. This iterator
707/// is an internal detail of the stroke expansion logic, but is also available
708/// separately, and is expected to be useful when doing stroke expansion on
709/// GPU.
710///
711/// It is implemented as an iterator-to-iterator transform. Because it consumes
712/// the input sequentially and produces consistent output with correct joins,
713/// it requires internal state and may allocate.
714///
715/// Accuracy is currently hard-coded to 1e-6. This is better than generally
716/// expected, and care is taken to get cusps correct, among other things.
717pub fn dash<'a>(
718    inner: impl Iterator<Item = PathEl> + 'a,
719    dash_offset: f64,
720    dashes: &'a [f64],
721) -> impl Iterator<Item = PathEl> + 'a {
722    dash_iter(inner, dash_offset, dashes, false)
723}
724
725fn dash_iter<'a>(
726    inner: impl Iterator<Item = PathEl> + 'a,
727    dash_offset: f64,
728    dashes: &'a [f64],
729    stable_dash_order: bool,
730) -> DashIterator<'a, impl Iterator<Item = PathEl> + 'a> {
731    // Ensure that offset is positive and minimal by normalization using period
732    let period = dashes.iter().sum();
733    // The SVG spec requires odd-length dash arrays to be doubled to become even-length:
734    // <https://www.w3.org/TR/SVG2/painting.html#StrokeDasharrayProperty>
735    // This prevents gaps and dashes from swapping with one another as the offset increases.
736    let period = if dashes.len() % 2 == 1 {
737        2.0 * period
738    } else {
739        period
740    };
741    let dash_offset = dash_offset.rem_euclid(period);
742
743    let mut dash_ix = 0;
744    let mut dash_remaining = dashes[dash_ix] - dash_offset;
745    let mut is_active = true;
746    // Find place in dashes array for initial offset.
747    while dash_remaining < 0.0 {
748        dash_ix = (dash_ix + 1) % dashes.len();
749        dash_remaining += dashes[dash_ix];
750        is_active = !is_active;
751    }
752    DashIterator {
753        inner,
754        input_done: false,
755        closepath_pending: false,
756        dashes,
757        dash_ix,
758        init_dash_ix: dash_ix,
759        init_dash_remaining: dash_remaining,
760        init_is_active: is_active,
761        is_active,
762        state: DashState::NeedInput,
763        current_seg: PathSeg::Line(Line::new(Point::ORIGIN, Point::ORIGIN)),
764        t: 0.0,
765        dash_remaining,
766        seg_remaining: 0.0,
767        start_pt: Point::ORIGIN,
768        last_pt: Point::ORIGIN,
769        stash: Vec::new(),
770        stash_ix: 0,
771        stable_dash_order,
772        needs_moveto: true,
773    }
774}
775
776impl<'a, T: Iterator<Item = PathEl>> DashIterator<'a, T> {
777    fn get_input(&mut self) {
778        loop {
779            if self.closepath_pending {
780                self.handle_closepath();
781                break;
782            }
783            let Some(next_el) = self.inner.next() else {
784                self.input_done = true;
785                self.state = DashState::FromStash;
786                return;
787            };
788            let p0 = self.last_pt;
789            match next_el {
790                PathEl::MoveTo(p) => {
791                    if !self.stash.is_empty() {
792                        self.state = DashState::FromStash;
793                    }
794                    self.start_pt = p;
795                    self.last_pt = p;
796                    self.reset_phase();
797                    continue;
798                }
799                PathEl::LineTo(p1) => {
800                    let l = Line::new(p0, p1);
801                    self.seg_remaining = l.arclen(DASH_ACCURACY);
802                    self.current_seg = PathSeg::Line(l);
803                    self.last_pt = p1;
804                }
805                PathEl::QuadTo(p1, p2) => {
806                    let q = QuadBez::new(p0, p1, p2);
807                    self.seg_remaining = q.arclen(DASH_ACCURACY);
808                    self.current_seg = PathSeg::Quad(q);
809                    self.last_pt = p2;
810                }
811                PathEl::CurveTo(p1, p2, p3) => {
812                    let c = CubicBez::new(p0, p1, p2, p3);
813                    self.seg_remaining = c.arclen(DASH_ACCURACY);
814                    self.current_seg = PathSeg::Cubic(c);
815                    self.last_pt = p3;
816                }
817                PathEl::ClosePath => {
818                    self.closepath_pending = true;
819                    if p0 != self.start_pt {
820                        let l = Line::new(p0, self.start_pt);
821                        self.seg_remaining = l.arclen(DASH_ACCURACY);
822                        self.current_seg = PathSeg::Line(l);
823                        self.last_pt = self.start_pt;
824                    } else {
825                        self.handle_closepath();
826                    }
827                }
828            }
829            break;
830        }
831        self.t = 0.0;
832    }
833
834    /// Move arc length forward to next event.
835    fn step(&mut self) -> Option<PathEl> {
836        let mut result = None;
837        if self.state == DashState::ToStash && self.needs_moveto {
838            self.needs_moveto = false;
839            if self.is_active {
840                result = Some(PathEl::MoveTo(self.current_seg.start()));
841            } else {
842                self.state = DashState::Working;
843            }
844        } else if self.dash_remaining < self.seg_remaining {
845            // next transition is a dash transition
846            let seg = self.current_seg.subsegment(self.t..1.0);
847            let t1 = seg.inv_arclen(self.dash_remaining, DASH_ACCURACY);
848            if self.is_active {
849                let subseg = seg.subsegment(0.0..t1);
850                result = Some(seg_to_el(&subseg));
851                self.state = DashState::Working;
852            } else {
853                let p = seg.eval(t1);
854                result = Some(PathEl::MoveTo(p));
855            }
856            self.is_active = !self.is_active;
857            self.t += t1 * (1.0 - self.t);
858            self.seg_remaining -= self.dash_remaining;
859            self.dash_ix += 1;
860            if self.dash_ix == self.dashes.len() {
861                self.dash_ix = 0;
862            }
863            self.dash_remaining = self.dashes[self.dash_ix];
864        } else {
865            if self.is_active {
866                let seg = self.current_seg.subsegment(self.t..1.0);
867                result = Some(seg_to_el(&seg));
868            }
869            self.dash_remaining -= self.seg_remaining;
870            self.get_input();
871        }
872        result
873    }
874
875    fn handle_closepath(&mut self) {
876        if self.state == DashState::ToStash {
877            // Have looped back without breaking a dash, just play it back
878            self.stash.push(PathEl::ClosePath);
879        } else if self.is_active && !self.stable_dash_order {
880            // connect with path in stash, skip MoveTo.
881            self.stash_ix = 1;
882        }
883        self.state = DashState::FromStash;
884        self.reset_phase();
885    }
886
887    fn reset_phase(&mut self) {
888        self.dash_ix = self.init_dash_ix;
889        self.dash_remaining = self.init_dash_remaining;
890        self.is_active = self.init_is_active;
891        self.needs_moveto = true;
892    }
893}
894
895#[cfg(test)]
896mod tests {
897    use super::dash_iter;
898    use crate::{
899        BezPath, Cap::Butt, CubicBez, Join::Miter, Line, PathEl, PathSeg, Shape, Stroke,
900        StrokeOpts, dash, segments, stroke,
901    };
902
903    // A degenerate stroke with a cusp at the endpoint.
904    #[test]
905    fn pathological_stroke() {
906        let curve = CubicBez::new(
907            (602.469, 286.585),
908            (641.975, 286.585),
909            (562.963, 286.585),
910            (562.963, 286.585),
911        );
912        let path = curve.into_path(0.1);
913        let stroke_style = Stroke::new(1.);
914        let stroked = stroke(path, &stroke_style, &StrokeOpts::default(), 0.001);
915        assert!(stroked.is_finite());
916    }
917
918    #[test]
919    /// <https://github.com/linebender/kurbo/issues/482>
920    fn dash_miter_join() {
921        let path = BezPath::from_vec(vec![
922            PathEl::MoveTo((70.0, 80.0).into()),
923            PathEl::LineTo((0.0, 80.0).into()),
924            PathEl::LineTo((0.0, 77.0).into()),
925        ]);
926        let expected_stroke = BezPath::from_vec(vec![
927            PathEl::MoveTo((70.0, 90.0).into()),
928            PathEl::LineTo((0.0, 90.0).into()),
929            // Miter join point on forward path
930            PathEl::LineTo((-10.0, 90.0).into()),
931            PathEl::LineTo((-10.0, 80.0).into()),
932            PathEl::LineTo((-10.0, 77.0).into()),
933            PathEl::LineTo((10.0, 77.0).into()),
934            PathEl::LineTo((10.0, 80.0).into()),
935            // Miter join point on backward path
936            PathEl::LineTo((0.0, 80.0).into()),
937            PathEl::LineTo((0.0, 70.0).into()),
938            PathEl::LineTo((70.0, 70.0).into()),
939            PathEl::ClosePath,
940        ]);
941        let stroke_style = Stroke::new(20.0)
942            .with_join(Miter)
943            .with_caps(Butt)
944            .with_dashes(0.0, [73.0, 12.0]);
945        let stroke = stroke(path, &stroke_style, &StrokeOpts::default(), 0.25);
946        assert_eq!(stroke, expected_stroke);
947    }
948
949    // Test cases adapted from https://github.com/linebender/vello/pull/388
950    #[test]
951    fn broken_strokes() {
952        let broken_cubics = [
953            [
954                (465.24423, 107.11105),
955                (475.50754, 107.11105),
956                (475.50754, 107.11105),
957                (475.50754, 107.11105),
958            ],
959            [(0., -0.01), (128., 128.001), (128., -0.01), (0., 128.001)], // Near-cusp
960            [(0., 0.), (0., -10.), (0., -10.), (0., 10.)],                // Flat line with 180
961            [(10., 0.), (0., 0.), (20., 0.), (10., 0.)],                  // Flat line with 2 180s
962            [(39., -39.), (40., -40.), (40., -40.), (0., 0.)],            // Flat diagonal with 180
963            [(40., 40.), (0., 0.), (200., 200.), (0., 0.)],               // Diag w/ an internal 180
964            [(0., 0.), (1e-2, 0.), (-1e-2, 0.), (0., 0.)],                // Circle
965            // Flat line with no turns:
966            [
967                (400.75, 100.05),
968                (400.75, 100.05),
969                (100.05, 300.95),
970                (100.05, 300.95),
971            ],
972            [(0.5, 0.), (0., 0.), (20., 0.), (10., 0.)], // Flat line with 2 180s
973            [(10., 0.), (0., 0.), (10., 0.), (10., 0.)], // Flat line with a 180
974        ];
975        let stroke_style = Stroke::new(30.).with_caps(Butt).with_join(Miter);
976        for cubic in &broken_cubics {
977            let path = CubicBez::new(cubic[0], cubic[1], cubic[2], cubic[3]).into_path(0.1);
978            let stroked = stroke(path, &stroke_style, &StrokeOpts::default(), 0.001);
979            assert!(stroked.is_finite());
980        }
981    }
982
983    #[test]
984    fn dash_sequence() {
985        let shape = Line::new((0.0, 0.0), (21.0, 0.0));
986        let dashes = [1., 5., 2., 5.];
987        let expansion = [
988            PathSeg::Line(Line::new((6., 0.), (8., 0.))),
989            PathSeg::Line(Line::new((13., 0.), (14., 0.))),
990            PathSeg::Line(Line::new((19., 0.), (21., 0.))),
991            PathSeg::Line(Line::new((0., 0.), (1., 0.))),
992        ];
993        let iter = segments(dash(shape.path_elements(0.), 0., &dashes));
994        assert_eq!(iter.collect::<Vec<PathSeg>>(), expansion);
995    }
996
997    #[test]
998    fn dash_sequence_closed_path() {
999        let shape = crate::Rect::from_points((0.0, 0.0), (4.0, 4.0));
1000        let dashes = [5., 1.];
1001        let expansion = [
1002            PathEl::MoveTo((4.0, 2.0).into()),
1003            PathEl::LineTo((4.0, 4.0).into()),
1004            PathEl::LineTo((1.0, 4.0).into()),
1005            PathEl::MoveTo((0.0, 4.0).into()),
1006            PathEl::LineTo((0.0, 0.0).into()),
1007            PathEl::LineTo((4.0, 0.0).into()),
1008            PathEl::LineTo((4.0, 1.0).into()),
1009        ];
1010        let iter = dash(shape.path_elements(0.), 0., &dashes);
1011        assert_eq!(iter.collect::<Vec<PathEl>>(), expansion);
1012    }
1013
1014    #[test]
1015    fn dash_sequence_stable_order() {
1016        let shape = Line::new((0.0, 0.0), (21.0, 0.0));
1017        let dashes = [1., 5., 2., 5.];
1018        let expansion = [
1019            PathSeg::Line(Line::new((0., 0.), (1., 0.))),
1020            PathSeg::Line(Line::new((6., 0.), (8., 0.))),
1021            PathSeg::Line(Line::new((13., 0.), (14., 0.))),
1022            PathSeg::Line(Line::new((19., 0.), (21., 0.))),
1023        ];
1024        let iter = segments(dash_iter(shape.path_elements(0.), 0., &dashes, true));
1025        assert_eq!(iter.collect::<Vec<PathSeg>>(), expansion);
1026    }
1027
1028    #[test]
1029    fn dash_sequence_closed_path_stable_order() {
1030        let shape = crate::Rect::from_points((0.0, 0.0), (4.0, 4.0));
1031        let dashes = [5., 1.];
1032        let expansion = [
1033            PathEl::MoveTo((0.0, 0.0).into()),
1034            PathEl::LineTo((4.0, 0.0).into()),
1035            PathEl::LineTo((4.0, 1.0).into()),
1036            PathEl::MoveTo((4.0, 2.0).into()),
1037            PathEl::LineTo((4.0, 4.0).into()),
1038            PathEl::LineTo((1.0, 4.0).into()),
1039            PathEl::MoveTo((0.0, 4.0).into()),
1040            PathEl::LineTo((0.0, 0.0).into()),
1041        ];
1042        let iter = dash_iter(shape.path_elements(0.), 0., &dashes, true);
1043        assert_eq!(iter.collect::<Vec<PathEl>>(), expansion);
1044    }
1045
1046    #[test]
1047    fn dash_sequence_offset() {
1048        // Same as dash_sequence, but with a dash offset
1049        // of 3, which skips the first dash and cuts into
1050        // the first gap.
1051        let shape = Line::new((0.0, 0.0), (21.0, 0.0));
1052        let dashes = [1., 5., 2., 5.];
1053        let expansion = [
1054            PathSeg::Line(Line::new((3., 0.), (5., 0.))),
1055            PathSeg::Line(Line::new((10., 0.), (11., 0.))),
1056            PathSeg::Line(Line::new((16., 0.), (18., 0.))),
1057        ];
1058        let iter = segments(dash(shape.path_elements(0.), 3., &dashes));
1059        assert_eq!(iter.collect::<Vec<PathSeg>>(), expansion);
1060    }
1061
1062    // Differently-sized subpaths verify stable mode restarts the dash pattern per subpath without leaking state.
1063    #[test]
1064    fn dash_stable_order_multi_subpath() {
1065        let mut path = BezPath::new();
1066        path.move_to((0., 0.));
1067        path.line_to((2., 0.));
1068        path.line_to((2., 2.));
1069        path.line_to((0., 2.));
1070        path.close_path();
1071        path.move_to((10., 10.));
1072        path.line_to((15., 10.));
1073        path.line_to((15., 14.));
1074        path.line_to((10., 14.));
1075        path.close_path();
1076        let dashes = [3., 1.];
1077        let expansion = [
1078            PathEl::MoveTo((0., 0.).into()),
1079            PathEl::LineTo((2., 0.).into()),
1080            PathEl::LineTo((2., 1.).into()),
1081            PathEl::MoveTo((2., 2.).into()),
1082            PathEl::LineTo((0., 2.).into()),
1083            PathEl::LineTo((0., 1.).into()),
1084            PathEl::MoveTo((10., 10.).into()),
1085            PathEl::LineTo((13., 10.).into()),
1086            PathEl::MoveTo((14., 10.).into()),
1087            PathEl::LineTo((15., 10.).into()),
1088            PathEl::LineTo((15., 12.).into()),
1089            PathEl::MoveTo((15., 13.).into()),
1090            PathEl::LineTo((15., 14.).into()),
1091            PathEl::LineTo((13., 14.).into()),
1092            PathEl::MoveTo((12., 14.).into()),
1093            PathEl::LineTo((10., 14.).into()),
1094            PathEl::LineTo((10., 13.).into()),
1095            PathEl::MoveTo((10., 12.).into()),
1096            PathEl::LineTo((10., 10.).into()),
1097        ];
1098        let iter = dash_iter(path.into_iter(), 0., &dashes, true);
1099        assert_eq!(iter.collect::<Vec<PathEl>>(), expansion);
1100    }
1101
1102    #[test]
1103    fn dash_negative_offset() {
1104        let shape = Line::new((0.0, 0.0), (28.0, 0.0));
1105        let dashes = [4., 2.];
1106        let pos = segments(dash(shape.path_elements(0.), 60., &dashes)).collect::<Vec<PathSeg>>();
1107        let neg = segments(dash(shape.path_elements(0.), -60., &dashes)).collect::<Vec<PathSeg>>();
1108        assert_eq!(neg, pos);
1109    }
1110
1111    #[test]
1112    fn dash_odd_length_matches_doubled() {
1113        let shape = Line::new((0.0, 0.0), (50.0, 0.0));
1114        let odd = [10.];
1115        let doubled = [10., 10.];
1116        for offset in [0., 5., 9., 10., 11., 15., 20., 25., 100., -7.] {
1117            let from_odd =
1118                segments(dash(shape.path_elements(0.), offset, &odd)).collect::<Vec<PathSeg>>();
1119            let from_doubled =
1120                segments(dash(shape.path_elements(0.), offset, &doubled)).collect::<Vec<PathSeg>>();
1121            assert_eq!(from_odd, from_doubled, "mismatch at offset {offset}");
1122        }
1123    }
1124
1125    #[test]
1126    fn dash_three_element_matches_doubled() {
1127        let shape = Line::new((0.0, 0.0), (200.0, 0.0));
1128        let three = [20., 10., 3.];
1129        let doubled = [20., 10., 3., 20., 10., 3.];
1130        for offset in [0., 15., 32., 33., 34., 50., 66., 99.] {
1131            let from_three =
1132                segments(dash(shape.path_elements(0.), offset, &three)).collect::<Vec<PathSeg>>();
1133            let from_doubled =
1134                segments(dash(shape.path_elements(0.), offset, &doubled)).collect::<Vec<PathSeg>>();
1135            assert_eq!(from_three, from_doubled, "mismatch at offset {offset}");
1136        }
1137    }
1138
1139    #[test]
1140    fn stroke_is_finite_fields() {
1141        let finite = Stroke::new(2.0)
1142            .with_miter_limit(4.0)
1143            .with_dashes(0.0, [1.0, 2.0]);
1144        assert!(finite.is_finite());
1145
1146        let non_finite_width = Stroke::new(f64::INFINITY);
1147        assert!(!non_finite_width.is_finite());
1148
1149        let non_finite_miter = Stroke::new(2.0).with_miter_limit(f64::NAN);
1150        assert!(!non_finite_miter.is_finite());
1151
1152        let non_finite_dash_offset = Stroke::new(2.0).with_dashes(f64::NEG_INFINITY, [1.0, 2.0]);
1153        assert!(!non_finite_dash_offset.is_finite());
1154
1155        let non_finite_dash_pattern = Stroke::new(2.0).with_dashes(0.0, [1.0, f64::NAN]);
1156        assert!(!non_finite_dash_pattern.is_finite());
1157    }
1158
1159    #[test]
1160    fn stroke_is_nan_fields() {
1161        let finite = Stroke::new(2.0)
1162            .with_miter_limit(4.0)
1163            .with_dashes(0.0, [1.0, 2.0]);
1164        assert!(!finite.is_nan());
1165
1166        let nan_width = Stroke::new(f64::NAN);
1167        assert!(nan_width.is_nan());
1168
1169        let nan_miter = Stroke::new(2.0).with_miter_limit(f64::NAN);
1170        assert!(nan_miter.is_nan());
1171
1172        let nan_dash_offset = Stroke::new(2.0).with_dashes(f64::NAN, [1.0, 2.0]);
1173        assert!(nan_dash_offset.is_nan());
1174
1175        let nan_dash_pattern = Stroke::new(2.0).with_dashes(0.0, [1.0, f64::NAN]);
1176        assert!(nan_dash_pattern.is_nan());
1177
1178        let infinite_width = Stroke::new(f64::INFINITY);
1179        assert!(!infinite_width.is_nan());
1180    }
1181}
kurbo/stroke.rs

kurbo/
stroke.rs
