fastanim_core/
geom.rs

1//! Vector geometry (SPEC §4.1) and path alignment (§4.3).
2//!
3//! Everything is normalized to cubic Béziers so interpolating two aligned paths is a plain
4//! control-point lerp.
5
6use std::f64::consts::FRAC_PI_2;
7use std::ops::Range;
8
9use kurbo::{Affine, CubicBez, ParamCurve, ParamCurveArclen, ParamCurveExtrema, Point, Rect};
10
11const ARCLEN_ACCURACY: f64 = 1e-6;
12
13/// A single closed or open contour made of cubic Béziers.
14#[derive(Debug, Clone, PartialEq)]
15pub struct SubPath {
16    /// The segments, each starting where the previous one ends.
17    pub segments: Vec<CubicBez>,
18    /// Whether the contour joins back to its start.
19    pub closed: bool,
20}
21
22/// A vector shape: possibly many contours (e.g. the glyph "B" has 3).
23#[derive(Debug, Clone, PartialEq, Default)]
24pub struct VPath {
25    /// The contours, in drawing order.
26    pub subpaths: Vec<SubPath>,
27}
28
29/// A straight line as a cubic (degree-elevated so it interpolates like any other segment).
30pub fn line_segment(a: Point, b: Point) -> CubicBez {
31    CubicBez::new(a, a.lerp(b, 1.0 / 3.0), a.lerp(b, 2.0 / 3.0), b)
32}
33
34impl SubPath {
35    /// Straight segments through `points`; `closed` adds the segment back to the first point.
36    pub fn polyline(points: &[Point], closed: bool) -> Self {
37        let mut segments: Vec<_> = points
38            .windows(2)
39            .map(|w| line_segment(w[0], w[1]))
40            .collect();
41        if closed && points.len() > 2 {
42            segments.push(line_segment(points[points.len() - 1], points[0]));
43        }
44        Self { segments, closed }
45    }
46
47    /// The mean of the segment start points.
48    pub fn centroid(&self) -> Point {
49        let n = self.segments.len().max(1) as f64;
50        let sum = self
51            .segments
52            .iter()
53            .fold(Point::ORIGIN, |acc, s| acc + s.p0.to_vec2());
54        Point::new(sum.x / n, sum.y / n)
55    }
56
57    /// Same topology as `self`, shrunk to a single point at its centroid.
58    fn collapsed(&self) -> Self {
59        let c = self.centroid();
60        let seg = CubicBez::new(c, c, c, c);
61        Self {
62            segments: vec![seg; self.segments.len()],
63            closed: self.closed,
64        }
65    }
66}
67
68impl VPath {
69    /// A circular arc around the origin, `sweep` radians from `start`, one cubic per quarter turn.
70    pub fn arc(radius: f64, start: f64, sweep: f64) -> Self {
71        let n = (sweep.abs() / FRAC_PI_2).ceil().max(1.0) as usize;
72        let step = sweep / n as f64;
73        let k = 4.0 / 3.0 * (step / 4.0).tan() * radius;
74        let at = |th: f64| Point::new(radius * th.cos(), radius * th.sin());
75        let segments = (0..n)
76            .map(|i| {
77                let (a, b) = (start + step * i as f64, start + step * (i + 1) as f64);
78                let (p0, p3) = (at(a), at(b));
79                let t0 = kurbo::Vec2::new(-a.sin(), a.cos()) * k;
80                let t1 = kurbo::Vec2::new(-b.sin(), b.cos()) * k;
81                CubicBez::new(p0, p0 + t0, p3 - t1, p3)
82            })
83            .collect();
84        let closed = (sweep.abs() - std::f64::consts::TAU).abs() < 1e-9;
85        Self {
86            subpaths: vec![SubPath { segments, closed }],
87        }
88    }
89
90    /// Straight segments through `points`.
91    pub fn polyline(points: &[Point], closed: bool) -> Self {
92        Self {
93            subpaths: vec![SubPath::polyline(points, closed)],
94        }
95    }
96
97    /// Applies an affine transform to every control point.
98    pub fn transform(&self, a: Affine) -> Self {
99        let subpaths = self
100            .subpaths
101            .iter()
102            .map(|sp| SubPath {
103                segments: sp.segments.iter().map(|s| a * *s).collect(),
104                closed: sp.closed,
105            })
106            .collect();
107        Self { subpaths }
108    }
109
110    /// Tight bounding box, or `None` for an empty path.
111    pub fn bbox(&self) -> Option<Rect> {
112        self.subpaths
113            .iter()
114            .flat_map(|sp| &sp.segments)
115            .map(|s| s.bounding_box())
116            .reduce(|a, b| a.union(b))
117    }
118
119    /// Center of the bounding box (the origin for an empty path).
120    pub fn center(&self) -> Point {
121        self.bbox().map_or(Point::ORIGIN, |r| r.center())
122    }
123
124    /// The part between fractions `range` of total arc length, as drawn by `Create`.
125    /// A partial path is always open.
126    pub fn trim(&self, range: Range<f32>) -> Self {
127        if range.start <= 0.0 && range.end >= 1.0 {
128            return self.clone();
129        }
130        let lens: Vec<Vec<f64>> = self
131            .subpaths
132            .iter()
133            .map(|sp| {
134                sp.segments
135                    .iter()
136                    .map(|s| s.arclen(ARCLEN_ACCURACY))
137                    .collect()
138            })
139            .collect();
140        let total: f64 = lens.iter().flatten().sum();
141        let (from, to) = (f64::from(range.start) * total, f64::from(range.end) * total);
142        let mut acc = 0.0;
143        let mut subpaths = Vec::new();
144        for (sp, lens) in self.subpaths.iter().zip(&lens) {
145            let mut segments = Vec::new();
146            for (seg, &len) in sp.segments.iter().zip(lens) {
147                let (l0, l1) = (acc, acc + len);
148                acc = l1;
149                if len == 0.0 || l1 <= from || l0 >= to {
150                    continue;
151                }
152                let t0 = if from > l0 {
153                    seg.inv_arclen(from - l0, ARCLEN_ACCURACY)
154                } else {
155                    0.0
156                };
157                let t1 = if to < l1 {
158                    seg.inv_arclen(to - l0, ARCLEN_ACCURACY)
159                } else {
160                    1.0
161                };
162                segments.push(seg.subsegment(t0..t1));
163            }
164            if !segments.is_empty() {
165                subpaths.push(SubPath {
166                    segments,
167                    closed: false,
168                });
169            }
170        }
171        Self { subpaths }
172    }
173}
174
175/// Brings two paths to the same topology so they can be lerped (SPEC §4.3).
176///
177/// Subpaths pair by index; missing ones grow from / shrink to a point. Within a pair the shorter
178/// side's longest segments are split until counts match, and closed contours are rotated to the
179/// start point that minimizes travel.
180// ponytail: subpaths pair by index; diff-based pairing via shape signatures (§5.6) lands with glyphs in M5/M6.
181pub fn align(a: &VPath, b: &VPath) -> (VPath, VPath) {
182    let n = a.subpaths.len().max(b.subpaths.len());
183    let (mut out_a, mut out_b) = (VPath::default(), VPath::default());
184    for i in 0..n {
185        let (sa, sb) = match (a.subpaths.get(i), b.subpaths.get(i)) {
186            (Some(x), Some(y)) => (x.clone(), y.clone()),
187            (Some(x), None) => (x.clone(), x.collapsed()),
188            (None, Some(y)) => (y.collapsed(), y.clone()),
189            (None, None) => unreachable!(),
190        };
191        let (sa, sb) = align_subpaths(sa, sb);
192        out_a.subpaths.push(sa);
193        out_b.subpaths.push(sb);
194    }
195    (out_a, out_b)
196}
197
198fn align_subpaths(mut a: SubPath, mut b: SubPath) -> (SubPath, SubPath) {
199    if a.segments.is_empty() {
200        a = SubPath {
201            closed: a.closed,
202            ..b.collapsed()
203        };
204    } else if b.segments.is_empty() {
205        b = SubPath {
206            closed: b.closed,
207            ..a.collapsed()
208        };
209    }
210    let n = a.segments.len().max(b.segments.len());
211    subdivide_to(&mut a.segments, n);
212    subdivide_to(&mut b.segments, n);
213    if a.closed && b.closed {
214        let travel = |r: usize| -> f64 {
215            (0..n)
216                .map(|i| (a.segments[(i + r) % n].p0 - b.segments[i].p0).hypot2())
217                .sum()
218        };
219        let best = (0..n)
220            .min_by(|&x, &y| travel(x).total_cmp(&travel(y)))
221            .unwrap_or(0);
222        a.segments.rotate_left(best);
223    }
224    (a, b)
225}
226
227// ponytail: O(n²) re-scan for the longest segment; fine for shapes, revisit if glyph runs get long.
228fn subdivide_to(segs: &mut Vec<CubicBez>, n: usize) {
229    while segs.len() < n {
230        let lens: Vec<f64> = segs.iter().map(|s| s.arclen(ARCLEN_ACCURACY)).collect();
231        let i = (0..segs.len())
232            .max_by(|&x, &y| lens[x].total_cmp(&lens[y]).then(y.cmp(&x)))
233            .unwrap();
234        let (l, r) = segs[i].subdivide();
235        segs[i] = l;
236        segs.insert(i + 1, r);
237    }
238}
fastanim_core/geom.rs

fastanim_core/
geom.rs
