Skip to main content

teksilo_canvas/
path.rs

1// SPDX-License-Identifier: MPL-2.0
2// SPDX-FileCopyrightText: 2026 FernTech
3
4use crate::geometry::{Point, Rect, Transform2D};
5use crate::paint::FillRule;
6use teksilo_tokens::CornerRadius;
7
8/// A path command for building arbitrary shapes (Tier 3 rendering).
9#[derive(Debug, Clone, Copy, PartialEq)]
10pub enum PathCommand {
11    MoveTo(Point),
12    LineTo(Point),
13    QuadTo {
14        control: Point,
15        to: Point,
16    },
17    CubicTo {
18        control1: Point,
19        control2: Point,
20        to: Point,
21    },
22    ArcTo {
23        rect: Rect,
24        start_angle: f32,
25        sweep_angle: f32,
26    },
27    Close,
28}
29
30/// The seed a fresh [`Path`]'s [`stamp`](Path::stamp) starts from.
31///
32/// An arbitrary odd constant — the point is only that an empty path's stamp is
33/// not `0`, so a stamp that was never folded is distinguishable from one folded
34/// with a zero word.
35const STAMP_SEED: u64 = 0x2545_F491_4F6C_DD1D;
36
37/// Fold one 64-bit word into a rolling content stamp.
38///
39/// SplitMix64's finalizer, applied to `state ^ (word * golden)`. Chosen over a
40/// plain FNV step because the words folded here are IEEE-754 bit patterns whose
41/// high bits barely move between neighbouring coordinates, and FNV-1a's
42/// avalanche is weakest exactly there — two points a texel apart would differ
43/// in a handful of low bits and stay correlated through the fold.
44///
45/// Order-sensitive (the state is carried), so `MoveTo(a); LineTo(b)` and
46/// `MoveTo(b); LineTo(a)` are distinct, and constant-time, which is the whole
47/// reason this exists: see [`Path::stamp`].
48#[inline]
49const fn fold(state: u64, word: u64) -> u64 {
50    let mut x = state ^ word.wrapping_mul(0x9E37_79B9_7F4A_7C15);
51    x ^= x >> 30;
52    x = x.wrapping_mul(0xBF58_476D_1CE4_E5B9);
53    x ^= x >> 27;
54    x = x.wrapping_mul(0x94D0_49BB_1331_11EB);
55    x ^ (x >> 31)
56}
57
58#[inline]
59fn fold_f32(state: u64, v: f32) -> u64 {
60    // `to_bits` rather than the value: `NaN` must fold reproducibly, and two
61    // paths differing only in the sign of a zero are not the same path to a
62    // rasterizer that winds by direction.
63    fold(state, v.to_bits() as u64)
64}
65
66#[inline]
67fn fold_point(state: u64, p: Point) -> u64 {
68    fold_f32(fold_f32(state, p.x), p.y)
69}
70
71/// Fold one command into a rolling stamp.
72fn fold_command(state: u64, cmd: &PathCommand) -> u64 {
73    match *cmd {
74        PathCommand::MoveTo(p) => fold_point(fold(state, 1), p),
75        PathCommand::LineTo(p) => fold_point(fold(state, 2), p),
76        PathCommand::QuadTo { control, to } => fold_point(fold_point(fold(state, 3), control), to),
77        PathCommand::CubicTo {
78            control1,
79            control2,
80            to,
81        } => fold_point(
82            fold_point(fold_point(fold(state, 4), control1), control2),
83            to,
84        ),
85        PathCommand::ArcTo {
86            rect,
87            start_angle,
88            sweep_angle,
89        } => {
90            let s = fold(state, 5);
91            let s = fold_f32(
92                fold_f32(fold_f32(fold_f32(s, rect.x), rect.y), rect.width),
93                rect.height,
94            );
95            fold_f32(fold_f32(s, start_angle), sweep_angle)
96        }
97        PathCommand::Close => fold(state, 6),
98    }
99}
100
101/// A path composed of drawing commands. Used for Tier 3 (CPU rasterized) shapes.
102///
103/// # Why the command list is not a public field
104///
105/// A path carries a **content stamp** ([`stamp`](Self::stamp)) maintained
106/// incrementally as commands are appended, so a consumer that needs to know
107/// "is this the same geometry I saw last frame?" can ask in constant time
108/// instead of walking the commands. The renderer's path-mask cache is that
109/// consumer, and the difference is not a micro-optimisation: keyed by a walk, a
110/// *cache hit* on a long stroke cost microseconds and grew with the stroke — so
111/// a stroke that grows by one point per pointer sample paid O(n) to discover it
112/// had nothing to do, which is O(n²) over the stroke. The measured table lives
113/// in `docs/ink.md` §5 and is quoted nowhere else, so that the two columns stay
114/// one run of one machine; the gate that holds the shape rather than the
115/// numbers is `a_cache_hit_does_not_scale_with_the_paths_length` in
116/// `crates/teksilo-render/tests/wet_stroke_cost.rs`.
117///
118/// A public `Vec` cannot be kept in step with a stamp, so the commands are
119/// reached through [`commands`](Self::commands) and appended through the
120/// builders or [`push`](Self::push).
121#[derive(Debug, Clone)]
122pub struct Path {
123    commands: Vec<PathCommand>,
124    stamp: u64,
125}
126
127impl Default for Path {
128    fn default() -> Self {
129        Self {
130            commands: Vec::new(),
131            stamp: STAMP_SEED,
132        }
133    }
134}
135
136impl PartialEq for Path {
137    /// Compares the commands. The stamp is a pure function of them, so
138    /// including it would only be able to *agree*.
139    fn eq(&self, other: &Self) -> bool {
140        self.commands == other.commands
141    }
142}
143
144impl Path {
145    pub fn new() -> Self {
146        Self::default()
147    }
148
149    /// Build a path from a command list, folding each into the stamp.
150    ///
151    /// The door for a producer that assembles commands elsewhere — the SVG
152    /// path-data parser is the one in-tree caller.
153    pub fn from_commands(commands: Vec<PathCommand>) -> Self {
154        let stamp = commands.iter().fold(STAMP_SEED, fold_command);
155        Self { commands, stamp }
156    }
157
158    /// The commands, in order.
159    #[inline]
160    pub fn commands(&self) -> &[PathCommand] {
161        &self.commands
162    }
163
164    /// A 64-bit stamp of this path's contents, maintained incrementally.
165    ///
166    /// Two paths with identical command sequences have identical stamps; two
167    /// with different ones differ with the collision probability of a 64-bit
168    /// hash. Reading it is O(1) — appending a command costs one fold, so
169    /// building an n-command path costs O(n) *once* rather than O(n) per
170    /// interrogation.
171    ///
172    /// Not stable across releases, and not to be persisted: it is an in-process
173    /// identity for caches, nothing more.
174    #[inline]
175    pub fn stamp(&self) -> u64 {
176        self.stamp
177    }
178
179    /// Append one command.
180    pub fn push(&mut self, cmd: PathCommand) -> &mut Self {
181        self.stamp = fold_command(self.stamp, &cmd);
182        self.commands.push(cmd);
183        self
184    }
185
186    /// Drop every command, returning to the empty path.
187    pub fn clear(&mut self) -> &mut Self {
188        self.commands.clear();
189        self.stamp = STAMP_SEED;
190        self
191    }
192
193    pub fn move_to(&mut self, p: Point) -> &mut Self {
194        self.push(PathCommand::MoveTo(p))
195    }
196
197    pub fn line_to(&mut self, p: Point) -> &mut Self {
198        self.push(PathCommand::LineTo(p))
199    }
200
201    pub fn quad_to(&mut self, control: Point, to: Point) -> &mut Self {
202        self.push(PathCommand::QuadTo { control, to })
203    }
204
205    pub fn cubic_to(&mut self, control1: Point, control2: Point, to: Point) -> &mut Self {
206        self.push(PathCommand::CubicTo {
207            control1,
208            control2,
209            to,
210        })
211    }
212
213    pub fn arc_to(&mut self, rect: Rect, start_angle: f32, sweep_angle: f32) -> &mut Self {
214        self.push(PathCommand::ArcTo {
215            rect,
216            start_angle,
217            sweep_angle,
218        })
219    }
220
221    pub fn close(&mut self) -> &mut Self {
222        self.push(PathCommand::Close)
223    }
224
225    pub fn is_empty(&self) -> bool {
226        self.commands.is_empty()
227    }
228
229    /// Compute the axis-aligned bounding box of this path.
230    /// Only considers control points (not exact curve bounds), which is
231    /// sufficient for atlas allocation.
232    pub fn bounds(&self) -> Rect {
233        let mut min_x = f32::MAX;
234        let mut min_y = f32::MAX;
235        let mut max_x = f32::MIN;
236        let mut max_y = f32::MIN;
237
238        let mut include = |p: Point| {
239            min_x = min_x.min(p.x);
240            min_y = min_y.min(p.y);
241            max_x = max_x.max(p.x);
242            max_y = max_y.max(p.y);
243        };
244
245        for cmd in &self.commands {
246            match *cmd {
247                PathCommand::MoveTo(p) | PathCommand::LineTo(p) => include(p),
248                PathCommand::QuadTo { control, to } => {
249                    include(control);
250                    include(to);
251                }
252                PathCommand::CubicTo {
253                    control1,
254                    control2,
255                    to,
256                } => {
257                    include(control1);
258                    include(control2);
259                    include(to);
260                }
261                PathCommand::ArcTo { rect, .. } => {
262                    include(Point::new(rect.x, rect.y));
263                    include(Point::new(rect.right(), rect.bottom()));
264                }
265                PathCommand::Close => {}
266            }
267        }
268
269        if min_x > max_x {
270            return Rect::ZERO;
271        }
272        Rect::new(min_x, min_y, max_x - min_x, max_y - min_y)
273    }
274
275    /// Create a circle path.
276    pub fn circle(center: Point, radius: f32) -> Self {
277        let rect = Rect::new(
278            center.x - radius,
279            center.y - radius,
280            radius * 2.0,
281            radius * 2.0,
282        );
283        let mut path = Self::new();
284        // A subpath must open with a `MoveTo`, or a renderer has no start point
285        // for the arc and draws a stray line from the origin. The arc begins at
286        // angle 0 — the rightmost point (center.x + radius, center.y).
287        path.move_to(Point::new(center.x + radius, center.y));
288        path.arc_to(rect, 0.0, 360.0);
289        path.close();
290        path
291    }
292
293    /// Create a rounded rectangle path using arc segments for each corner.
294    pub fn rounded_rect(rect: Rect, radii: CornerRadius) -> Self {
295        let [tl, tr, br, bl] = radii.to_array();
296        let mut path = Self::new();
297
298        // Start at top edge after top-left radius
299        path.move_to(Point::new(rect.x + tl, rect.y));
300
301        // Top edge → top-right arc
302        path.line_to(Point::new(rect.right() - tr, rect.y));
303        if tr > 0.0 {
304            let arc_rect = Rect::new(rect.right() - tr * 2.0, rect.y, tr * 2.0, tr * 2.0);
305            path.arc_to(arc_rect, -90.0, 90.0);
306        }
307
308        // Right edge → bottom-right arc
309        path.line_to(Point::new(rect.right(), rect.bottom() - br));
310        if br > 0.0 {
311            let arc_rect = Rect::new(
312                rect.right() - br * 2.0,
313                rect.bottom() - br * 2.0,
314                br * 2.0,
315                br * 2.0,
316            );
317            path.arc_to(arc_rect, 0.0, 90.0);
318        }
319
320        // Bottom edge → bottom-left arc
321        path.line_to(Point::new(rect.x + bl, rect.bottom()));
322        if bl > 0.0 {
323            let arc_rect = Rect::new(rect.x, rect.bottom() - bl * 2.0, bl * 2.0, bl * 2.0);
324            path.arc_to(arc_rect, 90.0, 90.0);
325        }
326
327        // Left edge → top-left arc
328        path.line_to(Point::new(rect.x, rect.y + tl));
329        if tl > 0.0 {
330            let arc_rect = Rect::new(rect.x, rect.y, tl * 2.0, tl * 2.0);
331            path.arc_to(arc_rect, 180.0, 90.0);
332        }
333
334        path.close();
335        path
336    }
337
338    /// Create a star path.
339    pub fn star(center: Point, outer_radius: f32, inner_radius: f32, points: u32) -> Self {
340        let mut path = Self::new();
341        let total = points * 2;
342        for i in 0..total {
343            let angle =
344                (i as f32) * std::f32::consts::PI / points as f32 - std::f32::consts::FRAC_PI_2;
345            let r = if i % 2 == 0 {
346                outer_radius
347            } else {
348                inner_radius
349            };
350            let p = Point::new(center.x + r * angle.cos(), center.y + r * angle.sin());
351            if i == 0 {
352                path.move_to(p);
353            } else {
354                path.line_to(p);
355            }
356        }
357        path.close();
358        path
359    }
360
361    /// Create a non-rounded rectangle path.
362    pub fn rect(rect: Rect) -> Self {
363        let mut path = Self::new();
364        path.move_to(Point::new(rect.x, rect.y));
365        path.line_to(Point::new(rect.right(), rect.y));
366        path.line_to(Point::new(rect.right(), rect.bottom()));
367        path.line_to(Point::new(rect.x, rect.bottom()));
368        path.close();
369        path
370    }
371
372    /// Create a single line segment path.
373    pub fn line(from: Point, to: Point) -> Self {
374        let mut path = Self::new();
375        path.move_to(from);
376        path.line_to(to);
377        path
378    }
379
380    /// Create an ellipse inscribed in the given rectangle (4 cubic Bézier arcs).
381    pub fn ellipse(rect: Rect) -> Self {
382        // Approximate an ellipse with 4 cubic Bézier curves.
383        // Magic number for quarter-circle cubic approximation: κ ≈ 0.5522847498
384        const KAPPA: f32 = 0.552_284_8;
385        let cx = rect.x + rect.width / 2.0;
386        let cy = rect.y + rect.height / 2.0;
387        let rx = rect.width / 2.0;
388        let ry = rect.height / 2.0;
389        let kx = rx * KAPPA;
390        let ky = ry * KAPPA;
391
392        let mut path = Self::new();
393        // Start at top center
394        path.move_to(Point::new(cx, cy - ry));
395        // Top-right quadrant
396        path.cubic_to(
397            Point::new(cx + kx, cy - ry),
398            Point::new(cx + rx, cy - ky),
399            Point::new(cx + rx, cy),
400        );
401        // Bottom-right quadrant
402        path.cubic_to(
403            Point::new(cx + rx, cy + ky),
404            Point::new(cx + kx, cy + ry),
405            Point::new(cx, cy + ry),
406        );
407        // Bottom-left quadrant
408        path.cubic_to(
409            Point::new(cx - kx, cy + ry),
410            Point::new(cx - rx, cy + ky),
411            Point::new(cx - rx, cy),
412        );
413        // Top-left quadrant
414        path.cubic_to(
415            Point::new(cx - rx, cy - ky),
416            Point::new(cx - kx, cy - ry),
417            Point::new(cx, cy - ry),
418        );
419        path.close();
420        path
421    }
422
423    /// Append all commands from another path.
424    pub fn append(&mut self, other: &Path) {
425        for cmd in &other.commands {
426            self.push(*cmd);
427        }
428    }
429
430    /// Create a copy of this path with all points transformed by the given
431    /// affine transform. **Exact for every affine**, curves included.
432    ///
433    /// Lines and Béziers transform by their points, which is exact by
434    /// definition. An [`ArcTo`](PathCommand::ArcTo) cannot: it is stored as a
435    /// rectangle plus two angles, and only a translate combined with a
436    /// positive axis-aligned scale maps that onto another rectangle-plus-the-
437    /// same-angles (see [`arc_transform_is_exact`]). Under a rotation, a shear
438    /// or a mirror, transforming the rectangle and keeping the angles puts the
439    /// arc's endpoints in the wrong place — a rotated rounded rectangle comes
440    /// back with square-ish corners in the wrong quadrants. So an arc that the
441    /// transform cannot carry is expanded into the cubics
442    /// [`arc_to_cubics`] would have drawn it as, and those transform exactly.
443    ///
444    /// That expansion is the same approximation the renderer already paints
445    /// the arc with, so a transformed path hit-tests as what is on screen. It
446    /// is one-way: the returned path has cubics where this one had an arc.
447    pub fn transformed(&self, transform: &Transform2D) -> Path {
448        let arcs_survive = arc_transform_is_exact(transform);
449        let mut result = Path::new();
450        for cmd in &self.commands {
451            match *cmd {
452                PathCommand::MoveTo(p) => {
453                    result.move_to(transform.apply_point(p));
454                }
455                PathCommand::LineTo(p) => {
456                    result.line_to(transform.apply_point(p));
457                }
458                PathCommand::QuadTo { control, to } => {
459                    result.quad_to(transform.apply_point(control), transform.apply_point(to));
460                }
461                PathCommand::CubicTo {
462                    control1,
463                    control2,
464                    to,
465                } => {
466                    result.cubic_to(
467                        transform.apply_point(control1),
468                        transform.apply_point(control2),
469                        transform.apply_point(to),
470                    );
471                }
472                PathCommand::ArcTo {
473                    rect,
474                    start_angle,
475                    sweep_angle,
476                } => {
477                    if arcs_survive {
478                        result.arc_to(transform.apply_rect(rect), start_angle, sweep_angle);
479                    } else {
480                        for seg in arc_to_cubics(rect, start_angle, sweep_angle) {
481                            let from = transform.apply_point(seg.from);
482                            match result.commands.last() {
483                                // Already standing on the arc's start point:
484                                // no connector.
485                                Some(PathCommand::MoveTo(p) | PathCommand::LineTo(p))
486                                    if *p == from => {}
487                                Some(
488                                    PathCommand::QuadTo { to, .. }
489                                    | PathCommand::CubicTo { to, .. },
490                                ) if *to == from => {}
491                                // An arc that *opens* a subpath — the first
492                                // command of the path, or the first after a
493                                // `Close`. [`Path::flatten`] starts such a
494                                // subpath at the arc's own first point, and
495                                // that is what the `arcs_survive` branch above
496                                // leaves the surviving `ArcTo` to do, so the
497                                // expansion has to start one too. A `line_to`
498                                // here would hand `flatten` a command with no
499                                // subpath open, which opens one at the
500                                // *cursor* — the point the `Close` returned it
501                                // to, i.e. the previous subpath's start — and
502                                // so joins two separate loops with an edge
503                                // that is in neither the untransformed path
504                                // nor the arc-preserving transform of it.
505                                None | Some(PathCommand::Close) => {
506                                    result.move_to(from);
507                                }
508                                // Continuing an open subpath from somewhere
509                                // else: a straight connector, which is what
510                                // `flatten` and the renderers both draw.
511                                Some(_) => {
512                                    result.line_to(from);
513                                }
514                            }
515                            result.cubic_to(
516                                transform.apply_point(seg.control1),
517                                transform.apply_point(seg.control2),
518                                transform.apply_point(seg.to),
519                            );
520                        }
521                    }
522                }
523                PathCommand::Close => {
524                    result.close();
525                }
526            }
527        }
528        result
529    }
530
531    /// Create a closed polygon from a list of points.
532    pub fn polygon(points: &[Point]) -> Self {
533        let mut path = Self::new();
534        if let Some((&first, rest)) = points.split_first() {
535            path.move_to(first);
536            for &p in rest {
537                path.line_to(p);
538            }
539            path.close();
540        }
541        path
542    }
543
544    /// Subdivide every curve command into line segments no further than
545    /// `tolerance` from the true curve, yielding one [`Subpath`] per `MoveTo`
546    /// run.
547    ///
548    /// `tolerance` is in the path's own units and is clamped to a sane floor,
549    /// so a caller cannot ask for unbounded subdivision; each individual curve
550    /// is additionally capped at 64 segments. Arcs go through
551    /// [`arc_to_cubics`] first, so the whole command set is covered.
552    ///
553    /// A `LineTo` or curve arriving with no preceding `MoveTo` opens a subpath
554    /// at the origin, matching how the renderers treat the same input.
555    pub fn flatten(&self, tolerance: f32) -> Vec<Subpath> {
556        let mut out: Vec<Subpath> = Vec::new();
557        let mut current: Vec<Point> = Vec::new();
558        let mut closed = false;
559        let mut cursor = Point::ZERO;
560
561        for cmd in &self.commands {
562            match *cmd {
563                PathCommand::MoveTo(p) => {
564                    flush_subpath(&mut out, &mut current, &mut closed);
565                    current.push(p);
566                    cursor = p;
567                }
568                PathCommand::LineTo(p) => {
569                    if current.is_empty() {
570                        current.push(cursor);
571                    }
572                    current.push(p);
573                    cursor = p;
574                }
575                PathCommand::QuadTo { control, to } => {
576                    if current.is_empty() {
577                        current.push(cursor);
578                    }
579                    push_quad(&mut current, cursor, control, to, tolerance);
580                    cursor = to;
581                }
582                PathCommand::CubicTo {
583                    control1,
584                    control2,
585                    to,
586                } => {
587                    if current.is_empty() {
588                        current.push(cursor);
589                    }
590                    push_cubic(&mut current, cursor, control1, control2, to, tolerance);
591                    cursor = to;
592                }
593                PathCommand::ArcTo {
594                    rect,
595                    start_angle,
596                    sweep_angle,
597                } => {
598                    for seg in arc_to_cubics(rect, start_angle, sweep_angle) {
599                        if current.is_empty() {
600                            current.push(seg.from);
601                        } else if current[current.len() - 1] != seg.from {
602                            // The arc starts away from the cursor: the renderers
603                            // draw a straight connector there, so the polyline
604                            // must carry the same edge.
605                            current.push(seg.from);
606                        }
607                        push_cubic(
608                            &mut current,
609                            seg.from,
610                            seg.control1,
611                            seg.control2,
612                            seg.to,
613                            tolerance,
614                        );
615                        cursor = seg.to;
616                    }
617                }
618                PathCommand::Close => {
619                    if !current.is_empty() {
620                        closed = true;
621                        let start = current[0];
622                        flush_subpath(&mut out, &mut current, &mut closed);
623                        cursor = start;
624                    }
625                }
626            }
627        }
628        flush_subpath(&mut out, &mut current, &mut closed);
629        out
630    }
631
632    /// Curve-accurate bounding box, to within `tolerance`.
633    ///
634    /// [`Path::bounds`] is the *control-point hull* and over-reports every
635    /// curve (a cubic never reaches its control points); this flattens first.
636    /// Use `bounds()` where an over-estimate is free (atlas allocation) and
637    /// this where the box is a hit-test or culling boundary.
638    pub fn exact_bounds(&self, tolerance: f32) -> Rect {
639        let subpaths = self.flatten(tolerance);
640        let mut acc: Option<Rect> = None;
641        for sp in &subpaths {
642            if sp.points.is_empty() {
643                continue;
644            }
645            let b = sp.bounds();
646            acc = Some(match acc {
647                None => b,
648                Some(a) => {
649                    let x = a.x.min(b.x);
650                    let y = a.y.min(b.y);
651                    Rect::new(
652                        x,
653                        y,
654                        a.right().max(b.right()) - x,
655                        a.bottom().max(b.bottom()) - y,
656                    )
657                }
658            });
659        }
660        acc.unwrap_or(Rect::ZERO)
661    }
662
663    /// Whether `p` lies inside the path's filled region under `rule`.
664    ///
665    /// Every subpath is treated as closed, matching SVG fill semantics (an
666    /// open subpath is filled as though a closing edge were present), so a
667    /// ring authored as two subpaths has a real hole under
668    /// [`FillRule::EvenOdd`].
669    ///
670    /// Flattens on every call. Callers testing the same path repeatedly
671    /// should flatten once and reuse the [`Subpath`]s.
672    pub fn contains_point(&self, p: Point, rule: FillRule, tolerance: f32) -> bool {
673        subpaths_contain_point(&self.flatten(tolerance), p, rule)
674    }
675}
676
677/// Close off the in-progress subpath, if it has any geometry, and reset the
678/// closed flag for the next one.
679fn flush_subpath(out: &mut Vec<Subpath>, current: &mut Vec<Point>, closed: &mut bool) {
680    if !current.is_empty() {
681        out.push(Subpath {
682            points: std::mem::take(current),
683            closed: *closed,
684        });
685    }
686    *closed = false;
687}
688
689/// One cubic Bézier segment of an arc approximation.
690///
691/// `from` is the segment's start point — the previous segment's `to`, or the
692/// arc's own start point for the first segment — so a consumer can emit each
693/// segment independently without tracking a cursor.
694#[derive(Debug, Clone, Copy, PartialEq)]
695pub struct ArcCubic {
696    pub from: Point,
697    pub control1: Point,
698    pub control2: Point,
699    pub to: Point,
700}
701
702/// Whether `transform` maps an [`ArcTo`](PathCommand::ArcTo) — a rectangle plus
703/// a start and sweep **angle** — onto another arc with the same angles.
704///
705/// It does exactly when the linear part is a positive axis-aligned scale (a
706/// translation is always free). An arc point is
707/// `(cx + rx·cos θ, cy + ry·sin θ)`; under `x ↦ a·x + tx`, `y ↦ d·y + ty` with
708/// `a > 0` and `d > 0` that becomes the same parameterisation of the scaled
709/// rectangle, so the rectangle can be transformed and the angles kept. A
710/// rotation or shear mixes the two axes, and a negative scale mirrors the
711/// sweep, so neither survives: [`Path::transformed`] expands the arc into
712/// cubics instead.
713pub fn arc_transform_is_exact(transform: &Transform2D) -> bool {
714    const EPS: f32 = 1e-5;
715    let [a, b, c, d, _, _] = transform.m;
716    b.abs() < EPS && c.abs() < EPS && a > 0.0 && d > 0.0
717}
718
719/// Approximate an elliptical arc inscribed in `rect` with cubic Bézier
720/// segments, one per 90° (or less) of sweep.
721///
722/// `start_angle` / `sweep_angle` are in **degrees**, matching
723/// [`Path::arc_to`] and its callers ([`Path::circle`],
724/// [`Path::rounded_rect`]). Returns an empty vector for a sweep small enough
725/// to be invisible (below `0.001` rad ≈ 0.057°).
726///
727/// This is the one arc→cubic conversion in the tree: [`Path::flatten`] uses it,
728/// [`Path::transformed`] uses it for an arc a transform cannot carry, and so
729/// does `teksilo-render`'s path atlas (which scales each returned point into
730/// device space before feeding tiny-skia).
731pub fn arc_to_cubics(rect: Rect, start_angle: f32, sweep_angle: f32) -> Vec<ArcCubic> {
732    let rx = rect.width * 0.5;
733    let ry = rect.height * 0.5;
734    let center_x = rect.x + rx;
735    let center_y = rect.y + ry;
736
737    let mut out = Vec::new();
738    let mut remaining = sweep_angle.to_radians();
739    let mut angle = start_angle.to_radians();
740    if !remaining.is_finite() || !angle.is_finite() {
741        return out;
742    }
743    let sign = if remaining >= 0.0 { 1.0 } else { -1.0 };
744
745    while remaining.abs() > 0.001 {
746        let chunk = sign * remaining.abs().min(std::f32::consts::FRAC_PI_2);
747        let half = chunk * 0.5;
748        let k = (4.0 / 3.0) * (1.0 - half.cos()) / half.sin();
749
750        let cos_a = angle.cos();
751        let sin_a = angle.sin();
752        let cos_b = (angle + chunk).cos();
753        let sin_b = (angle + chunk).sin();
754
755        out.push(ArcCubic {
756            from: Point::new(center_x + rx * cos_a, center_y + ry * sin_a),
757            control1: Point::new(
758                center_x + rx * (cos_a - k * sin_a),
759                center_y + ry * (sin_a + k * cos_a),
760            ),
761            control2: Point::new(
762                center_x + rx * (cos_b + k * sin_b),
763                center_y + ry * (sin_b - k * cos_b),
764            ),
765            to: Point::new(center_x + rx * cos_b, center_y + ry * sin_b),
766        });
767
768        angle += chunk;
769        remaining -= chunk;
770    }
771    out
772}
773
774/// One flattened subpath: a polyline plus whether its author closed it.
775///
776/// Produced by [`Path::flatten`]. `points` always has the subpath's start
777/// point first; the closing edge back to that point is **implied** by
778/// `closed` rather than duplicated, so a triangle is three points, not four.
779#[derive(Debug, Clone, PartialEq)]
780pub struct Subpath {
781    /// The polyline vertices, in order. Never empty for a subpath returned by
782    /// [`Path::flatten`].
783    pub points: Vec<Point>,
784    /// Whether the author wrote a [`PathCommand::Close`] for this subpath.
785    /// Fill treats every subpath as closed regardless (SVG semantics); a
786    /// *stroke* only walks the closing edge when this is `true`.
787    pub closed: bool,
788}
789
790impl Subpath {
791    /// Axis-aligned bounding box of the polyline. [`Rect::ZERO`] when empty.
792    ///
793    /// This is what makes a per-subpath reject cheap: a point or region that
794    /// misses this box cannot touch any of the subpath's segments, so a long
795    /// ink stroke answers "no" without walking its segments.
796    pub fn bounds(&self) -> Rect {
797        bounds_of_points(&self.points)
798    }
799
800    /// Whether the polyline has no vertices.
801    pub fn is_empty(&self) -> bool {
802        self.points.is_empty()
803    }
804
805    /// Iterate the subpath's segments as `(from, to)` pairs, including the
806    /// closing edge when `close_implicitly` is set (fill semantics) or when
807    /// the subpath was explicitly closed.
808    pub fn segments(&self, close_implicitly: bool) -> impl Iterator<Item = (Point, Point)> + '_ {
809        let n = self.points.len();
810        let wrap = (self.closed || close_implicitly) && n > 2;
811        (0..n.saturating_sub(1))
812            .map(move |i| (self.points[i], self.points[i + 1]))
813            .chain(wrap.then(|| (self.points[n - 1], self.points[0])))
814    }
815}
816
817fn bounds_of_points(points: &[Point]) -> Rect {
818    let mut min_x = f32::MAX;
819    let mut min_y = f32::MAX;
820    let mut max_x = f32::MIN;
821    let mut max_y = f32::MIN;
822    for p in points {
823        min_x = min_x.min(p.x);
824        min_y = min_y.min(p.y);
825        max_x = max_x.max(p.x);
826        max_y = max_y.max(p.y);
827    }
828    if min_x > max_x {
829        return Rect::ZERO;
830    }
831    Rect::new(min_x, min_y, max_x - min_x, max_y - min_y)
832}
833
834/// Upper bound on the segments any one curve is subdivided into. A curve that
835/// wants more than this is already far past the point where a hit-test can
836/// tell the difference, and the cap is what keeps a pathological control
837/// polygon from allocating without bound.
838const MAX_CURVE_SEGMENTS: u32 = 64;
839
840fn quad_segment_count(p0: Point, c: Point, p1: Point, tolerance: f32) -> u32 {
841    // Max deviation of the n-segment polyline from a quadratic is
842    // |p0 - 2c + p1| / (8 n²). Solve for n.
843    let dx = p0.x - 2.0 * c.x + p1.x;
844    let dy = p0.y - 2.0 * c.y + p1.y;
845    let d = (dx * dx + dy * dy).sqrt();
846    segment_count(d / 8.0, tolerance)
847}
848
849fn cubic_segment_count(p0: Point, c1: Point, c2: Point, p1: Point, tolerance: f32) -> u32 {
850    // Max deviation of the n-segment polyline from a cubic is bounded by
851    // (3/4) · max(|p0 - 2c1 + c2|, |c1 - 2c2 + p1|) / n².
852    let d1 = ((p0.x - 2.0 * c1.x + c2.x).powi(2) + (p0.y - 2.0 * c1.y + c2.y).powi(2)).sqrt();
853    let d2 = ((c1.x - 2.0 * c2.x + p1.x).powi(2) + (c1.y - 2.0 * c2.y + p1.y).powi(2)).sqrt();
854    segment_count(0.75 * d1.max(d2), tolerance)
855}
856
857fn segment_count(numerator: f32, tolerance: f32) -> u32 {
858    let tol = tolerance.max(1e-4);
859    if !numerator.is_finite() || numerator <= 0.0 {
860        return 1;
861    }
862    let n = (numerator / tol).sqrt().ceil();
863    if !n.is_finite() {
864        return MAX_CURVE_SEGMENTS;
865    }
866    (n as u32).clamp(1, MAX_CURVE_SEGMENTS)
867}
868
869fn push_quad(out: &mut Vec<Point>, p0: Point, c: Point, p1: Point, tolerance: f32) {
870    let n = quad_segment_count(p0, c, p1, tolerance);
871    for i in 1..=n {
872        let t = i as f32 / n as f32;
873        let mt = 1.0 - t;
874        out.push(Point::new(
875            mt * mt * p0.x + 2.0 * mt * t * c.x + t * t * p1.x,
876            mt * mt * p0.y + 2.0 * mt * t * c.y + t * t * p1.y,
877        ));
878    }
879}
880
881fn push_cubic(out: &mut Vec<Point>, p0: Point, c1: Point, c2: Point, p1: Point, tolerance: f32) {
882    let n = cubic_segment_count(p0, c1, c2, p1, tolerance);
883    for i in 1..=n {
884        let t = i as f32 / n as f32;
885        let mt = 1.0 - t;
886        let a = mt * mt * mt;
887        let b = 3.0 * mt * mt * t;
888        let c = 3.0 * mt * t * t;
889        let d = t * t * t;
890        out.push(Point::new(
891            a * p0.x + b * c1.x + c * c2.x + d * p1.x,
892            a * p0.y + b * c1.y + c * c2.y + d * p1.y,
893        ));
894    }
895}
896
897/// Point-in-polygons test over already-flattened subpaths.
898///
899/// Every subpath is treated as closed (SVG fill semantics). Shared by
900/// [`Path::contains_point`] and by consumers that cache their flattening.
901pub fn subpaths_contain_point(subpaths: &[Subpath], p: Point, rule: FillRule) -> bool {
902    let mut winding: i32 = 0;
903    let mut crossings: u32 = 0;
904    for sp in subpaths {
905        // Fewer than three vertices encloses no area. Counting such a
906        // subpath's one edge would give a spurious winding: the closing edge
907        // SVG semantics imply retraces it, and the two cancel.
908        if sp.points.len() < 3 {
909            continue;
910        }
911        for (a, b) in sp.segments(true) {
912            // Half-open in y so a vertex shared by two edges is counted once.
913            if (a.y <= p.y) == (b.y <= p.y) {
914                continue;
915            }
916            let t = (p.y - a.y) / (b.y - a.y);
917            let x = a.x + t * (b.x - a.x);
918            if x > p.x {
919                crossings += 1;
920                winding += if b.y > a.y { 1 } else { -1 };
921            }
922        }
923    }
924    match rule {
925        FillRule::Winding => winding != 0,
926        FillRule::EvenOdd => crossings % 2 == 1,
927    }
928}
929
930#[cfg(test)]
931mod tests {
932    use super::*;
933
934    // ------------------------------------------------------------------
935    // Flattening, exact bounds, point-in-path
936    // ------------------------------------------------------------------
937
938    #[test]
939    fn flatten_polyline_is_verbatim() {
940        let mut path = Path::new();
941        path.move_to(Point::new(0.0, 0.0))
942            .line_to(Point::new(10.0, 0.0))
943            .line_to(Point::new(10.0, 10.0));
944        let sp = path.flatten(0.25);
945        assert_eq!(sp.len(), 1);
946        assert_eq!(sp[0].points.len(), 3);
947        assert!(!sp[0].closed);
948    }
949
950    #[test]
951    fn flatten_close_marks_subpath_and_does_not_duplicate_start() {
952        let p = Path::rect(Rect::new(0.0, 0.0, 10.0, 10.0));
953        let sp = p.flatten(0.25);
954        assert_eq!(sp.len(), 1);
955        assert!(sp[0].closed);
956        // MoveTo + 3 LineTo = 4 vertices; the closing edge is implied.
957        assert_eq!(sp[0].points.len(), 4);
958    }
959
960    #[test]
961    fn flatten_splits_on_each_moveto() {
962        let mut path = Path::new();
963        path.move_to(Point::new(0.0, 0.0))
964            .line_to(Point::new(10.0, 0.0));
965        path.move_to(Point::new(20.0, 20.0))
966            .line_to(Point::new(30.0, 20.0));
967        assert_eq!(path.flatten(0.25).len(), 2);
968    }
969
970    #[test]
971    fn flatten_quad_tracks_the_true_curve() {
972        // The quadratic from (0,0) with control (50,100) to (100,0) reaches
973        // y = 50 at its apex, NOT the control point's y = 100.
974        let mut path = Path::new();
975        path.move_to(Point::new(0.0, 0.0))
976            .quad_to(Point::new(50.0, 100.0), Point::new(100.0, 0.0));
977        let sp = path.flatten(0.25);
978        let max_y = sp[0].points.iter().fold(f32::MIN, |m, p| m.max(p.y));
979        assert!(
980            (max_y - 50.0).abs() < 1.0,
981            "apex should be ~50, got {max_y}"
982        );
983    }
984
985    #[test]
986    fn exact_bounds_beats_control_point_hull() {
987        let mut path = Path::new();
988        path.move_to(Point::new(0.0, 0.0))
989            .quad_to(Point::new(50.0, 100.0), Point::new(100.0, 0.0));
990        assert_eq!(path.bounds().height, 100.0, "hull over-reports");
991        let exact = path.exact_bounds(0.25);
992        assert!(
993            (exact.height - 50.0).abs() < 1.0,
994            "exact bounds should be ~50 tall, got {}",
995            exact.height
996        );
997        assert!((exact.width - 100.0).abs() < 0.01);
998    }
999
1000    #[test]
1001    fn exact_bounds_of_empty_path_is_zero() {
1002        assert_eq!(Path::new().exact_bounds(0.25), Rect::ZERO);
1003    }
1004
1005    #[test]
1006    fn contains_point_square() {
1007        let p = Path::rect(Rect::new(0.0, 0.0, 100.0, 100.0));
1008        assert!(p.contains_point(Point::new(50.0, 50.0), FillRule::Winding, 0.25));
1009        assert!(!p.contains_point(Point::new(150.0, 50.0), FillRule::Winding, 0.25));
1010        assert!(!p.contains_point(Point::new(50.0, -1.0), FillRule::Winding, 0.25));
1011    }
1012
1013    #[test]
1014    fn contains_point_even_odd_ring_has_a_hole() {
1015        // Two concentric squares, same winding direction. Winding fills the
1016        // hole; even-odd punches it out.
1017        let mut p = Path::new();
1018        p.move_to(Point::new(0.0, 0.0))
1019            .line_to(Point::new(100.0, 0.0))
1020            .line_to(Point::new(100.0, 100.0))
1021            .line_to(Point::new(0.0, 100.0))
1022            .close();
1023        p.move_to(Point::new(25.0, 25.0))
1024            .line_to(Point::new(75.0, 25.0))
1025            .line_to(Point::new(75.0, 75.0))
1026            .line_to(Point::new(25.0, 75.0))
1027            .close();
1028
1029        let centre = Point::new(50.0, 50.0);
1030        let band = Point::new(10.0, 50.0);
1031        assert!(p.contains_point(centre, FillRule::Winding, 0.25));
1032        assert!(!p.contains_point(centre, FillRule::EvenOdd, 0.25));
1033        assert!(p.contains_point(band, FillRule::Winding, 0.25));
1034        assert!(p.contains_point(band, FillRule::EvenOdd, 0.25));
1035    }
1036
1037    #[test]
1038    fn contains_point_open_subpath_fills_as_closed() {
1039        // No `close()` - SVG fills it anyway.
1040        let mut p = Path::new();
1041        p.move_to(Point::new(0.0, 0.0))
1042            .line_to(Point::new(100.0, 0.0))
1043            .line_to(Point::new(100.0, 100.0))
1044            .line_to(Point::new(0.0, 100.0));
1045        assert!(p.contains_point(Point::new(50.0, 50.0), FillRule::Winding, 0.25));
1046    }
1047
1048    #[test]
1049    fn contains_point_ignores_a_degenerate_subpath() {
1050        // A two-point "polygon" is a line: it encloses nothing, and a
1051        // half-plane answer here is what made a zero-width path query select
1052        // everything on one side of the line.
1053        let p = Path::line(Point::new(0.0, 0.0), Point::new(100.0, 100.0));
1054        assert!(!p.contains_point(Point::new(2.0, 85.0), FillRule::Winding, 0.25));
1055        assert!(!p.contains_point(Point::new(85.0, 2.0), FillRule::Winding, 0.25));
1056    }
1057
1058    #[test]
1059    fn contains_point_circle() {
1060        let c = Path::circle(Point::new(50.0, 50.0), 25.0);
1061        assert!(c.contains_point(Point::new(50.0, 50.0), FillRule::Winding, 0.25));
1062        assert!(c.contains_point(Point::new(68.0, 50.0), FillRule::Winding, 0.25));
1063        assert!(!c.contains_point(Point::new(80.0, 50.0), FillRule::Winding, 0.25));
1064    }
1065
1066    #[test]
1067    fn arc_to_cubics_covers_a_full_circle_in_four_segments() {
1068        let segs = arc_to_cubics(Rect::new(0.0, 0.0, 100.0, 100.0), 0.0, 360.0);
1069        assert_eq!(segs.len(), 4);
1070        // Starts at angle 0 - the rightmost point.
1071        assert!((segs[0].from.x - 100.0).abs() < 0.01);
1072        assert!((segs[0].from.y - 50.0).abs() < 0.01);
1073        // Each segment continues from the last.
1074        for w in segs.windows(2) {
1075            assert!((w[0].to.x - w[1].from.x).abs() < 0.01);
1076            assert!((w[0].to.y - w[1].from.y).abs() < 0.01);
1077        }
1078    }
1079
1080    #[test]
1081    fn arc_to_cubics_ignores_a_sub_threshold_sweep() {
1082        assert!(arc_to_cubics(Rect::new(0.0, 0.0, 10.0, 10.0), 0.0, 0.0).is_empty());
1083    }
1084
1085    #[test]
1086    fn subpath_segments_wrap_only_when_closed() {
1087        let open = Subpath {
1088            points: vec![
1089                Point::new(0.0, 0.0),
1090                Point::new(10.0, 0.0),
1091                Point::new(10.0, 10.0),
1092            ],
1093            closed: false,
1094        };
1095        assert_eq!(open.segments(false).count(), 2);
1096        assert_eq!(open.segments(true).count(), 3);
1097        let shut = Subpath {
1098            closed: true,
1099            ..open.clone()
1100        };
1101        assert_eq!(shut.segments(false).count(), 3);
1102    }
1103
1104    #[test]
1105    fn subpath_bounds_is_the_polyline_box() {
1106        let sp = Subpath {
1107            points: vec![Point::new(10.0, 20.0), Point::new(50.0, 80.0)],
1108            closed: false,
1109        };
1110        assert_eq!(sp.bounds(), Rect::new(10.0, 20.0, 40.0, 60.0));
1111        assert_eq!(
1112            Subpath {
1113                points: vec![],
1114                closed: false
1115            }
1116            .bounds(),
1117            Rect::ZERO
1118        );
1119    }
1120
1121    #[test]
1122    fn curve_subdivision_is_capped() {
1123        // A wildly-out-of-range control polygon must not allocate without
1124        // bound: one curve is capped at 64 segments (65 emitted points).
1125        let mut path = Path::new();
1126        path.move_to(Point::new(0.0, 0.0)).cubic_to(
1127            Point::new(1.0e9, 1.0e9),
1128            Point::new(-1.0e9, 1.0e9),
1129            Point::new(1.0, 0.0),
1130        );
1131        let sp = path.flatten(0.001);
1132        assert_eq!(sp[0].points.len(), 65);
1133    }
1134
1135    #[test]
1136    fn flatten_tolerance_floor_keeps_a_zero_request_finite() {
1137        let mut path = Path::new();
1138        path.move_to(Point::new(0.0, 0.0))
1139            .quad_to(Point::new(50.0, 100.0), Point::new(100.0, 0.0));
1140        assert!(path.flatten(0.0)[0].points.len() <= 65);
1141    }
1142
1143    #[test]
1144    fn circle_path_not_empty() {
1145        let p = Path::circle(Point::new(50.0, 50.0), 25.0);
1146        assert!(!p.is_empty());
1147    }
1148
1149    #[test]
1150    fn circle_path_opens_with_moveto() {
1151        // A subpath must open with a MoveTo or a renderer draws a stray line
1152        // from the origin to the arc. The circle starts at angle 0 (rightmost).
1153        let p = Path::circle(Point::new(50.0, 50.0), 25.0);
1154        match p.commands.first() {
1155            Some(PathCommand::MoveTo(pt)) => {
1156                assert!((pt.x - 75.0).abs() < 0.01 && (pt.y - 50.0).abs() < 0.01);
1157            }
1158            other => panic!("circle must open with MoveTo, got {other:?}"),
1159        }
1160    }
1161
1162    #[test]
1163    fn star_path_has_correct_commands() {
1164        let p = Path::star(Point::new(50.0, 50.0), 30.0, 15.0, 5);
1165        assert!(!p.is_empty());
1166        // 5-point star: 10 vertices + 1 close
1167        assert_eq!(p.commands.len(), 11);
1168    }
1169
1170    #[test]
1171    fn bounds_of_simple_path() {
1172        let mut path = Path::new();
1173        path.move_to(Point::new(10.0, 20.0));
1174        path.line_to(Point::new(50.0, 80.0));
1175        path.line_to(Point::new(30.0, 40.0));
1176        let b = path.bounds();
1177        assert_eq!(b.x, 10.0);
1178        assert_eq!(b.y, 20.0);
1179        assert_eq!(b.width, 40.0);
1180        assert_eq!(b.height, 60.0);
1181    }
1182
1183    #[test]
1184    fn bounds_of_empty_path_is_zero() {
1185        let path = Path::new();
1186        let b = path.bounds();
1187        assert_eq!(b, Rect::ZERO);
1188    }
1189
1190    #[test]
1191    fn rounded_rect_uses_corner_radii() {
1192        use teksilo_tokens::CornerRadius;
1193        let p = Path::rounded_rect(
1194            Rect::new(0.0, 0.0, 100.0, 50.0),
1195            CornerRadius::uniform(10.0),
1196        );
1197        // Should have arcs for each corner — more commands than a plain rect
1198        assert!(p.commands.len() > 5);
1199        // Should contain ArcTo commands
1200        let arc_count = p
1201            .commands
1202            .iter()
1203            .filter(|c| matches!(c, PathCommand::ArcTo { .. }))
1204            .count();
1205        assert_eq!(arc_count, 4); // One per corner
1206    }
1207
1208    #[test]
1209    fn rounded_rect_zero_radii_is_plain_rect() {
1210        use teksilo_tokens::CornerRadius;
1211        let p = Path::rounded_rect(Rect::new(0.0, 0.0, 100.0, 50.0), CornerRadius::uniform(0.0));
1212        // No arcs with zero radii
1213        let arc_count = p
1214            .commands
1215            .iter()
1216            .filter(|c| matches!(c, PathCommand::ArcTo { .. }))
1217            .count();
1218        assert_eq!(arc_count, 0);
1219    }
1220
1221    #[test]
1222    fn rect_path_has_four_lines() {
1223        let p = Path::rect(Rect::new(10.0, 20.0, 30.0, 40.0));
1224        // MoveTo + 3 LineTo + Close = 5 commands
1225        assert_eq!(p.commands.len(), 5);
1226        assert!(matches!(p.commands[0], PathCommand::MoveTo(_)));
1227        assert!(matches!(p.commands[4], PathCommand::Close));
1228    }
1229
1230    #[test]
1231    fn line_path() {
1232        let p = Path::line(Point::new(0.0, 0.0), Point::new(100.0, 50.0));
1233        assert_eq!(p.commands.len(), 2);
1234        assert!(matches!(p.commands[0], PathCommand::MoveTo(_)));
1235        assert!(matches!(p.commands[1], PathCommand::LineTo(_)));
1236    }
1237
1238    #[test]
1239    fn ellipse_path_uses_cubics() {
1240        let p = Path::ellipse(Rect::new(0.0, 0.0, 100.0, 50.0));
1241        let cubic_count = p
1242            .commands
1243            .iter()
1244            .filter(|c| matches!(c, PathCommand::CubicTo { .. }))
1245            .count();
1246        assert_eq!(cubic_count, 4);
1247    }
1248
1249    #[test]
1250    fn polygon_path() {
1251        let points = vec![
1252            Point::new(0.0, 0.0),
1253            Point::new(100.0, 0.0),
1254            Point::new(50.0, 80.0),
1255        ];
1256        let p = Path::polygon(&points);
1257        // MoveTo + 2 LineTo + Close = 4 commands
1258        assert_eq!(p.commands.len(), 4);
1259    }
1260
1261    #[test]
1262    fn polygon_empty_points() {
1263        let p = Path::polygon(&[]);
1264        assert!(p.is_empty());
1265    }
1266
1267    #[test]
1268    fn append_merges_paths() {
1269        let mut a = Path::new();
1270        a.move_to(Point::new(0.0, 0.0));
1271        a.line_to(Point::new(10.0, 10.0));
1272
1273        let mut b = Path::new();
1274        b.move_to(Point::new(20.0, 20.0));
1275        b.line_to(Point::new(30.0, 30.0));
1276
1277        a.append(&b);
1278        assert_eq!(a.commands.len(), 4);
1279        assert!(matches!(a.commands[2], PathCommand::MoveTo(p) if (p.x - 20.0).abs() < 0.01));
1280    }
1281
1282    #[test]
1283    fn append_empty_is_noop() {
1284        let mut a = Path::new();
1285        a.move_to(Point::new(1.0, 2.0));
1286        let b = Path::new();
1287        a.append(&b);
1288        assert_eq!(a.commands.len(), 1);
1289    }
1290
1291    #[test]
1292    fn transformed_translate() {
1293        let mut path = Path::new();
1294        path.move_to(Point::new(10.0, 20.0));
1295        path.line_to(Point::new(30.0, 40.0));
1296        path.close();
1297
1298        let t = Transform2D::translate(100.0, 200.0);
1299        let result = path.transformed(&t);
1300
1301        assert_eq!(result.commands.len(), 3);
1302        match result.commands[0] {
1303            PathCommand::MoveTo(p) => {
1304                assert!((p.x - 110.0).abs() < 0.01);
1305                assert!((p.y - 220.0).abs() < 0.01);
1306            }
1307            _ => panic!("expected MoveTo"),
1308        }
1309        match result.commands[1] {
1310            PathCommand::LineTo(p) => {
1311                assert!((p.x - 130.0).abs() < 0.01);
1312                assert!((p.y - 240.0).abs() < 0.01);
1313            }
1314            _ => panic!("expected LineTo"),
1315        }
1316        assert!(matches!(result.commands[2], PathCommand::Close));
1317    }
1318
1319    #[test]
1320    fn transformed_scale() {
1321        let mut path = Path::new();
1322        path.move_to(Point::new(10.0, 20.0));
1323        path.quad_to(Point::new(15.0, 25.0), Point::new(30.0, 40.0));
1324
1325        let t = Transform2D::scale(2.0, 3.0);
1326        let result = path.transformed(&t);
1327
1328        match result.commands[1] {
1329            PathCommand::QuadTo { control, to } => {
1330                assert!((control.x - 30.0).abs() < 0.01);
1331                assert!((control.y - 75.0).abs() < 0.01);
1332                assert!((to.x - 60.0).abs() < 0.01);
1333                assert!((to.y - 120.0).abs() < 0.01);
1334            }
1335            _ => panic!("expected QuadTo"),
1336        }
1337    }
1338
1339    #[test]
1340    fn transformed_cubic() {
1341        let mut path = Path::new();
1342        path.move_to(Point::new(0.0, 0.0));
1343        path.cubic_to(
1344            Point::new(1.0, 0.0),
1345            Point::new(2.0, 1.0),
1346            Point::new(3.0, 3.0),
1347        );
1348
1349        let t = Transform2D::translate(10.0, 20.0);
1350        let result = path.transformed(&t);
1351
1352        match result.commands[1] {
1353            PathCommand::CubicTo {
1354                control1,
1355                control2,
1356                to,
1357            } => {
1358                assert!((control1.x - 11.0).abs() < 0.01);
1359                assert!((control2.x - 12.0).abs() < 0.01);
1360                assert!((to.x - 13.0).abs() < 0.01);
1361            }
1362            _ => panic!("expected CubicTo"),
1363        }
1364    }
1365
1366    #[test]
1367    fn transformed_preserves_command_count() {
1368        let p = Path::circle(Point::new(50.0, 50.0), 25.0);
1369        let t = Transform2D::scale(2.0, 2.0);
1370        let result = p.transformed(&t);
1371        assert_eq!(result.commands.len(), p.commands.len());
1372    }
1373
1374    #[test]
1375    fn arc_transform_is_exact_only_for_a_positive_axis_aligned_scale() {
1376        assert!(arc_transform_is_exact(&Transform2D::identity()));
1377        assert!(arc_transform_is_exact(&Transform2D::translate(9.0, -3.0)));
1378        assert!(arc_transform_is_exact(&Transform2D::scale(2.0, 7.0)));
1379        assert!(
1380            !arc_transform_is_exact(&Transform2D::rotate(0.4)),
1381            "a rotation mixes the axes"
1382        );
1383        assert!(
1384            !arc_transform_is_exact(&Transform2D::rotate(std::f32::consts::FRAC_PI_2)),
1385            "even a quarter turn: the angles would have to move with it"
1386        );
1387        assert!(
1388            !arc_transform_is_exact(&Transform2D::scale(-1.0, 1.0)),
1389            "a mirror reverses the sweep"
1390        );
1391    }
1392
1393    #[test]
1394    fn a_rotated_circle_is_still_that_circle() {
1395        // The defect this exists for: transforming an `ArcTo`'s *rectangle* and
1396        // keeping its angles turns a rotation into a resize. A circle of radius
1397        // 30 about the origin is invariant under rotation, so any growth is the
1398        // bug, and a point 38 out must stay outside at every angle.
1399        let c = Path::circle(Point::ZERO, 30.0);
1400        for turns in 1..8 {
1401            let t = Transform2D::rotate(turns as f32 * 0.4);
1402            let rotated = c.transformed(&t);
1403            let b = rotated.exact_bounds(0.25);
1404            assert!(
1405                (b.width - 60.0).abs() < 0.5 && (b.height - 60.0).abs() < 0.5,
1406                "rotation by {turns} resized the circle to {b:?}"
1407            );
1408            let outside = t.apply_point(Point::new(38.0, 0.0));
1409            assert!(
1410                !rotated.contains_point(outside, FillRule::Winding, 0.25),
1411                "a pure rotation must not change containment (turn {turns})"
1412            );
1413            assert!(rotated.contains_point(
1414                t.apply_point(Point::new(20.0, 0.0)),
1415                FillRule::Winding,
1416                0.25
1417            ));
1418        }
1419    }
1420
1421    #[test]
1422    fn a_rotated_rounded_rect_keeps_its_corners_where_they_belong() {
1423        let r = Path::rounded_rect(
1424            Rect::new(-50.0, -50.0, 100.0, 100.0),
1425            teksilo_tokens::CornerRadius::uniform(25.0),
1426        );
1427        let t = Transform2D::rotate(std::f32::consts::FRAC_PI_4);
1428        let rotated = r.transformed(&t);
1429        assert!(rotated.contains_point(Point::ZERO, FillRule::Winding, 0.25));
1430        // The rotated silhouette is the same rounded square turned half a right
1431        // angle, so the image of a point in the original's transparent corner
1432        // is still out.
1433        let corner = t.apply_point(Point::new(-49.0, -49.0));
1434        assert!(!rotated.contains_point(corner, FillRule::Winding, 0.25));
1435        // ...and the image of a point on the original's edge is still in.
1436        let edge = t.apply_point(Point::new(0.0, -49.0));
1437        assert!(rotated.contains_point(edge, FillRule::Winding, 0.25));
1438    }
1439
1440    #[test]
1441    fn an_arc_the_transform_cannot_carry_becomes_cubics_not_a_moved_rectangle() {
1442        // The mechanism, stated: the arc survives as an arc under a scale and
1443        // is expanded under a rotation. Deleting the expansion makes the
1444        // rotated path keep its `ArcTo` and this reddens.
1445        let c = Path::circle(Point::ZERO, 10.0);
1446        let arcs = |p: &Path| {
1447            p.commands
1448                .iter()
1449                .filter(|c| matches!(c, PathCommand::ArcTo { .. }))
1450                .count()
1451        };
1452        assert!(arcs(&c) > 0);
1453        assert_eq!(
1454            arcs(&c.transformed(&Transform2D::scale(3.0, 2.0))),
1455            arcs(&c)
1456        );
1457        assert_eq!(arcs(&c.transformed(&Transform2D::rotate(0.3))), 0);
1458    }
1459
1460    // ------------------------------------------------------------------
1461    // `transformed` preserves subpath structure — the two branches, checked
1462    // against one another
1463    // ------------------------------------------------------------------
1464
1465    /// The tolerance every structural comparison below flattens at.
1466    const STRUCT_TOL: f32 = 0.05;
1467
1468    /// One flattened subpath, described in the **source** path's own frame:
1469    /// whether the author closed it, where it starts, and the ground it
1470    /// covers.
1471    ///
1472    /// Deliberately says nothing about how many vertices the subpath has or
1473    /// where they fall: the two branches of [`Path::transformed`] sample a
1474    /// curve at different places by construction (one flattens a surviving
1475    /// arc, the other flattens the cubics it was expanded into), and the
1476    /// arc→cubic expansion is free to change. What may never differ is which
1477    /// loops there are and where each one runs.
1478    #[derive(Debug, Clone, Copy)]
1479    struct SubpathShape {
1480        closed: bool,
1481        start: Point,
1482        bounds: Rect,
1483    }
1484
1485    fn structure(p: &Path, back: &Transform2D) -> Vec<SubpathShape> {
1486        p.flatten(STRUCT_TOL)
1487            .iter()
1488            .map(|sp| {
1489                let pts: Vec<Point> = sp.points.iter().map(|q| back.apply_point(*q)).collect();
1490                SubpathShape {
1491                    closed: sp.closed,
1492                    start: pts[0],
1493                    bounds: bounds_of_points(&pts),
1494                }
1495            })
1496            .collect()
1497    }
1498
1499    /// Transforming a path and flattening it must give the same loops as
1500    /// flattening it and transforming the points — for **every** affine, so
1501    /// the arc-preserving branch and the arc-expanding branch are held to one
1502    /// rule and therefore to each other.
1503    ///
1504    /// Bounds are compared within a few times the flatten tolerance because
1505    /// the two branches genuinely sample a curve at different parameters; a
1506    /// structural defect is off by the distance between two subpaths, not by
1507    /// a fraction of the flattening error.
1508    #[track_caller]
1509    fn assert_transform_commutes_with_flatten(label: &str, p: &Path, t: &Transform2D) {
1510        const NEAR: f32 = 4.0 * STRUCT_TOL;
1511        let back = t.inverse().expect("test transforms are invertible");
1512        let plain = structure(p, &Transform2D::identity());
1513        let moved = structure(&p.transformed(t), &back);
1514        assert_eq!(
1515            moved.len(),
1516            plain.len(),
1517            "{label}: {} subpaths after the transform, {} before\n  after:  {moved:?}\n  before: {plain:?}",
1518            moved.len(),
1519            plain.len()
1520        );
1521        for (i, (m, e)) in moved.iter().zip(&plain).enumerate() {
1522            assert_eq!(m.closed, e.closed, "{label}: subpath {i} closed flag");
1523            assert!(
1524                (m.start.x - e.start.x).abs() < NEAR && (m.start.y - e.start.y).abs() < NEAR,
1525                "{label}: subpath {i} starts at {:?}, not {:?}",
1526                m.start,
1527                e.start
1528            );
1529            assert!(
1530                (m.bounds.x - e.bounds.x).abs() < NEAR
1531                    && (m.bounds.y - e.bounds.y).abs() < NEAR
1532                    && (m.bounds.width - e.bounds.width).abs() < NEAR
1533                    && (m.bounds.height - e.bounds.height).abs() < NEAR,
1534                "{label}: subpath {i} covers {:?}, not {:?}",
1535                m.bounds,
1536                e.bounds
1537            );
1538        }
1539    }
1540
1541    /// One arc rect, used by the battery below.
1542    fn arc_rect() -> Rect {
1543        Rect::new(180.0, -20.0, 40.0, 40.0)
1544    }
1545
1546    fn square() -> Path {
1547        let mut p = Path::new();
1548        p.move_to(Point::new(0.0, 0.0))
1549            .line_to(Point::new(10.0, 0.0))
1550            .line_to(Point::new(10.0, 10.0))
1551            .line_to(Point::new(0.0, 10.0))
1552            .close();
1553        p
1554    }
1555
1556    /// Every position an `ArcTo` — and, for contrast, a `QuadTo` / `CubicTo` —
1557    /// can sit in relative to a `Close` and to each other.
1558    fn structural_battery() -> Vec<(&'static str, Path)> {
1559        let mut out: Vec<(&'static str, Path)> = Vec::new();
1560
1561        // The defect this section exists for: a closed loop, then an arc.
1562        let mut p = square();
1563        p.arc_to(arc_rect(), 0.0, 360.0).close();
1564        out.push(("close then full-sweep arc", p));
1565
1566        // ...and with a partial sweep, where the spurious edge encloses real
1567        // area instead of exactly retracing the closing edge.
1568        let mut p = square();
1569        p.arc_to(arc_rect(), 0.0, 200.0).close();
1570        out.push(("close then partial arc", p));
1571
1572        let mut p = Path::new();
1573        p.arc_to(arc_rect(), 0.0, 360.0);
1574        out.push(("arc opens the path", p));
1575
1576        let mut p = Path::new();
1577        p.close();
1578        p.arc_to(arc_rect(), 0.0, 360.0);
1579        out.push(("close with no geometry, then arc", p));
1580
1581        let mut p = Path::new();
1582        p.move_to(Point::new(5.0, 5.0)).close();
1583        p.arc_to(arc_rect(), 0.0, 360.0);
1584        out.push(("lone move_to, close, then arc", p));
1585
1586        let mut p = Path::new();
1587        p.move_to(Point::new(220.0, 0.0));
1588        p.arc_to(arc_rect(), 0.0, 180.0);
1589        p.arc_to(arc_rect(), 180.0, 180.0);
1590        out.push(("arc continuing an arc at the shared point", p));
1591
1592        let mut p = Path::new();
1593        p.arc_to(arc_rect(), 0.0, 90.0);
1594        p.arc_to(Rect::new(0.0, 0.0, 20.0, 20.0), 0.0, 90.0);
1595        out.push(("arc after a disjoint arc", p));
1596
1597        let mut p = Path::new();
1598        p.move_to(Point::new(50.0, 50.0));
1599        p.arc_to(arc_rect(), 0.0, 360.0);
1600        out.push(("arc after a move_to somewhere else", p));
1601
1602        let mut p = square();
1603        p.quad_to(Point::new(120.0, -40.0), Point::new(200.0, 0.0));
1604        out.push(("close then quad", p));
1605
1606        let mut p = square();
1607        p.cubic_to(
1608            Point::new(60.0, -40.0),
1609            Point::new(140.0, 40.0),
1610            Point::new(200.0, 0.0),
1611        );
1612        out.push(("close then cubic", p));
1613
1614        let mut p = Path::new();
1615        p.quad_to(Point::new(120.0, -40.0), Point::new(200.0, 0.0));
1616        out.push(("quad opens the path", p));
1617
1618        let mut p = Path::new();
1619        p.cubic_to(
1620            Point::new(60.0, -40.0),
1621            Point::new(140.0, 40.0),
1622            Point::new(200.0, 0.0),
1623        );
1624        out.push(("cubic opens the path", p));
1625
1626        let mut p = square();
1627        p.line_to(Point::new(200.0, 0.0));
1628        out.push(("close then line", p));
1629
1630        out.push(("rounded rect", {
1631            Path::rounded_rect(
1632                Rect::new(-50.0, -50.0, 100.0, 100.0),
1633                teksilo_tokens::CornerRadius::uniform(25.0),
1634            )
1635        }));
1636        out.push(("circle", Path::circle(Point::new(30.0, 10.0), 20.0)));
1637
1638        out
1639    }
1640
1641    #[test]
1642    fn transformed_preserves_subpath_structure_in_both_branches() {
1643        // A positive axis-aligned scale keeps the `ArcTo` (the `arcs_survive`
1644        // branch); a rotation expands it (the other one). Holding both to the
1645        // same oracle is what makes this a comparison *between the branches*
1646        // rather than a fixture of whatever the expansion currently emits.
1647        let survives = Transform2D::scale(3.0, 2.0);
1648        let expands = Transform2D::rotate(30f32.to_radians());
1649        assert!(arc_transform_is_exact(&survives));
1650        assert!(!arc_transform_is_exact(&expands));
1651
1652        for (label, path) in structural_battery() {
1653            assert_transform_commutes_with_flatten(
1654                &format!("{label} / arcs survive"),
1655                &path,
1656                &survives,
1657            );
1658            assert_transform_commutes_with_flatten(
1659                &format!("{label} / arcs expand"),
1660                &path,
1661                &expands,
1662            );
1663        }
1664    }
1665
1666    #[test]
1667    fn an_expanded_arc_after_a_close_opens_its_own_subpath() {
1668        // The defect, named: the expansion emitted a `line_to`, which
1669        // `flatten` opens at the cursor the `Close` left behind — the
1670        // *previous* loop's start — welding two separate loops together.
1671        let mut p = square();
1672        p.arc_to(arc_rect(), 0.0, 360.0).close();
1673
1674        let rotated = p.transformed(&Transform2D::rotate(30f32.to_radians()));
1675        let after_close = rotated
1676            .commands
1677            .iter()
1678            .position(|c| matches!(c, PathCommand::Close))
1679            .expect("the square is closed")
1680            + 1;
1681        assert!(
1682            matches!(rotated.commands[after_close], PathCommand::MoveTo(_)),
1683            "the arc has to open a subpath, got {:?}",
1684            rotated.commands[after_close]
1685        );
1686
1687        // And the loop it opens still covers only the arc: 40 x 40, not the
1688        // 220-wide box a connector back to the square's start would give it.
1689        let sub = rotated.flatten(STRUCT_TOL);
1690        assert_eq!(sub.len(), 2, "two loops, still");
1691        let back = Transform2D::rotate(30f32.to_radians()).inverse().unwrap();
1692        let pts: Vec<Point> = sub[1].points.iter().map(|q| back.apply_point(*q)).collect();
1693        let b = bounds_of_points(&pts);
1694        assert!(
1695            (b.width - 40.0).abs() < 0.2 && (b.height - 40.0).abs() < 0.2,
1696            "the arc's loop grew to {b:?}"
1697        );
1698    }
1699
1700    #[test]
1701    fn a_rotated_arc_that_opens_a_subpath_still_opens_one() {
1702        // An `arc_to` with no preceding `move_to`: the expansion has to start
1703        // the subpath itself rather than emitting a dangling `line_to`.
1704        let mut p = Path::new();
1705        p.arc_to(Rect::new(0.0, 0.0, 20.0, 20.0), 0.0, 360.0);
1706        let rotated = p.transformed(&Transform2D::rotate(0.7));
1707        assert!(matches!(
1708            rotated.commands.first(),
1709            Some(PathCommand::MoveTo(_))
1710        ));
1711        assert_eq!(rotated.flatten(0.25).len(), 1);
1712    }
1713}