motion_core/
path2d.rs

1//! Double-precision path values, with copy-on-write geometry.
2
3use crate::sync::MutexExt;
4use std::sync::{Arc, Mutex, OnceLock};
5
6use kurbo::Shape as _;
7
8use crate::{Pivot, Point, Rect, Transform, ValidationError, Vector2};
9
10mod boolean;
11mod builder;
12mod construction;
13mod editing;
14mod metrics;
15mod morph;
16#[cfg(test)]
17mod tests;
18mod validation;
19
20pub use boolean::{MAX_BOOLEAN_EDGES, PathBooleanOp, PathBooleanOptions};
21pub use builder::PathBuilder;
22pub use morph::MorphPath;
23
24/// Maximum stored verbs in one path; mutations beyond it fail atomically.
25pub const MAX_PATH_VERBS: usize = 16_384;
26
27/// Maximum UTF-8 bytes accepted by one SVG path-data import.
28pub const MAX_SVG_PATH_BYTES: usize = 1_048_576;
29
30/// An absolute logical-coordinate path operation.
31#[derive(Clone, Copy, Debug, PartialEq)]
32pub enum PathVerb {
33    /// Starts a subpath at a point without joining the previous subpath.
34    MoveTo(Point),
35    /// Adds a line from the current point.
36    LineTo(Point),
37    /// Adds a quadratic Bezier with one control and an endpoint.
38    QuadraticTo(Point, Point),
39    /// Adds a cubic Bezier with two controls and an endpoint.
40    CubicTo(Point, Point, Point),
41    /// Closes to the subpath's first point; subsequent segments resume there.
42    Close,
43}
44
45impl PathVerb {
46    /// Returns endpoint/control coordinates for validation without flattening this verb.
47    /// Unused entries are `None`; Close has no coordinates.
48    pub fn points(self) -> [Option<Point>; 3] {
49        match self {
50            Self::MoveTo(point) | Self::LineTo(point) => [Some(point), None, None],
51            Self::QuadraticTo(control, end) => [Some(control), Some(end), None],
52            Self::CubicTo(first, second, end) => [Some(first), Some(second), Some(end)],
53            Self::Close => [None, None, None],
54        }
55    }
56}
57
58/// A cheaply cloned, checked f64 path with lazily cached geometric bounds.
59///
60/// A path is always valid: the `try_` methods return failures immediately and
61/// leave the snapshot unchanged, and [`PathBuilder`] reports its first failure
62/// from [`PathBuilder::build`].
63/// Bounds include move positions and curve extrema, not the curve control hull.
64/// Empty paths have zero bounds at the origin. SVG path data imports through
65/// [`Self::parse_svg`]. Arc lengths use cached bounded Gaussian integration;
66/// partial curves retain their Bezier representation rather than flattening.
67/// [`crate::Shape::stroke`] expands bounded curves into fill outlines;
68/// Styled trim/dash share the same arc-length parameterization.
69///
70/// ```
71/// use motion_core::prelude::*;
72/// use motion_core::{
73///     DisplayList, RasterLimits, ResourceStore, ValidatedDisplayList, MAX_PATH_VERBS,
74///     MAX_STROKE_VERBS, MAX_SVG_PATH_BYTES, sample_offsets,
75/// };
76/// let path = Path2D::builder()
77///     .move_to(Point::ORIGIN)
78///     .quadratic_to(Point::new(10.0, 20.0), Point::new(20.0, 0.0))
79///     .close()
80///     .build()?;
81/// assert_eq!(path.bounding_box(), Rect::new(0.0, 0.0, 20.0, 10.0));
82/// let node = path
83///     .fill(Color::from_hex(0x24a49b))
84///     .fill_rule(FillRule::EvenOdd)
85///     .at(Point::new(100.0, 80.0));
86/// assert_eq!(
87///     node.measure(ValidationLimits::default())?,
88///     Rect::new(90.0, 75.0, 110.0, 85.0)
89/// );
90/// let list = node.compile(
91///     Size::new(200.0, 160.0),
92///     PixelSize::new(200, 160),
93///     ValidationLimits::default(),
94/// )?;
95/// assert_eq!(list.commands.len(), 1);
96/// assert!(matches!(
97///     list.commands[0],
98///     DrawCommand::Fill {
99///         rule: FillRule::EvenOdd,
100///         ..
101///     }
102/// ));
103/// # Ok::<(), motion_core::ValidationError>(())
104/// ```
105#[derive(Clone, Debug, Default)]
106pub struct Path2D {
107    data: Arc<PathData>,
108}
109
110type StrokeCache = Arc<Mutex<Vec<([u64; 4], PathData)>>>;
111
112#[derive(Clone, Debug, Default)]
113struct PathData {
114    verbs: Arc<Vec<PathVerb>>,
115    hull: Option<Rect>,
116    current: Option<Point>,
117    start: Option<Point>,
118    bounds: OnceLock<Rect>,
119    fingerprint: OnceLock<u64>,
120    metrics: OnceLock<Result<Arc<metrics::Metrics>, ValidationError>>,
121    strokes: OnceLock<StrokeCache>,
122}
123
124impl PartialEq for Path2D {
125    fn eq(&self, other: &Self) -> bool {
126        self.verbs() == other.verbs()
127    }
128}
129
130impl Path2D {
131    /// Creates an empty path without paint.
132    pub fn new() -> Self {
133        Self::default()
134    }
135
136    /// Starts a chainable builder that reports its first error from `build`.
137    ///
138    /// This is the public way to author paths. The in-place `try_*` appenders on `Path2D`
139    /// are hidden from the documentation and exist for content crates that grow a path in a loop.
140    pub fn builder() -> PathBuilder {
141        PathBuilder::new()
142    }
143
144    /// Returns the immutable absolute f64 verbs.
145    pub fn verbs(&self) -> &[PathVerb] {
146        &self.data.verbs
147    }
148
149    /// Returns cached f64 geometric bounds, retaining zero-area geometry.
150    pub fn bounding_box(&self) -> Rect {
151        *self.data.bounds.get_or_init(|| self.compute_bounds())
152    }
153
154    /// Maps all endpoints and controls without flattening or modifying this path.
155    pub fn transformed(&self, transform: &Transform) -> Result<Self, ValidationError> {
156        if !transform.is_finite() {
157            return Err(invalid("transform", "Path transform must be finite"));
158        }
159        let mut result = Self::new();
160        for verb in self.verbs() {
161            let mapped = match *verb {
162                PathVerb::MoveTo(point) => PathVerb::MoveTo(transform.apply(point)),
163                PathVerb::LineTo(point) => PathVerb::LineTo(transform.apply(point)),
164                PathVerb::QuadraticTo(control, end) => {
165                    PathVerb::QuadraticTo(transform.apply(control), transform.apply(end))
166                }
167                PathVerb::CubicTo(first, second, end) => PathVerb::CubicTo(
168                    transform.apply(first),
169                    transform.apply(second),
170                    transform.apply(end),
171                ),
172                PathVerb::Close => PathVerb::Close,
173            };
174            result.push(mapped)?;
175        }
176        Ok(result)
177    }
178
179    /// Shares only the immutable verb snapshot, without retaining metric caches.
180    /// Arc::make_mut on a returned handle cannot edit this path's snapshot.
181    pub fn shared_verbs(&self) -> Arc<Vec<PathVerb>> {
182        self.data.verbs.clone()
183    }
184
185    /// Bounds of a single nondegenerate four-edge axis-aligned closed contour.
186    /// Curves, extra contours, retraced edges and nonrectangular paths return None.
187    pub fn axis_aligned_rectangle(&self) -> Option<Rect> {
188        let [
189            PathVerb::MoveTo(first),
190            PathVerb::LineTo(second),
191            PathVerb::LineTo(third),
192            PathVerb::LineTo(fourth),
193            PathVerb::Close,
194        ] = self.verbs()
195        else {
196            return None;
197        };
198        let horizontal = first.y == second.y
199            && second.x == third.x
200            && third.y == fourth.y
201            && fourth.x == first.x;
202        let vertical = first.x == second.x
203            && second.y == third.y
204            && third.x == fourth.x
205            && fourth.y == first.y;
206        if !(horizontal || vertical) || first.x == third.x || first.y == third.y {
207            return None;
208        }
209        Some(Rect::new(
210            first.x.min(third.x),
211            first.y.min(third.y),
212            first.x.max(third.x),
213            first.y.max(third.y),
214        ))
215    }
216
217    /// Stable content fingerprint shared by clones and invalidated by successful edits.
218    /// This is a lookup hint, not a collision-free geometry identity.
219    pub fn fingerprint(&self) -> u64 {
220        *self.data.fingerprint.get_or_init(|| {
221            let mut value = 14695981039346656037_u64;
222            let mut write = |bytes: &[u8]| {
223                for byte in bytes {
224                    value = (value ^ u64::from(*byte)).wrapping_mul(1099511628211);
225                }
226            };
227            write(&(self.verbs().len() as u64).to_le_bytes());
228            for verb in self.verbs() {
229                write(&[match verb {
230                    PathVerb::MoveTo(_) => 0,
231                    PathVerb::LineTo(_) => 1,
232                    PathVerb::QuadraticTo(..) => 2,
233                    PathVerb::CubicTo(..) => 3,
234                    PathVerb::Close => 4,
235                }]);
236                for point in verb.points().into_iter().flatten() {
237                    write(&point.x.to_bits().to_le_bytes());
238                    write(&point.y.to_bits().to_le_bytes());
239                }
240            }
241            value
242        })
243    }
244
245    fn compute_bounds(&self) -> Rect {
246        let Some(hull) = self.data.hull else {
247            return Rect::default();
248        };
249        let normalize = |point: Point| {
250            (
251                if hull.width() == 0.0 {
252                    0.0
253                } else {
254                    (point.x - hull.left) / hull.width()
255                },
256                if hull.height() == 0.0 {
257                    0.0
258                } else {
259                    (point.y - hull.top) / hull.height()
260                },
261            )
262        };
263        let mut path = kurbo::BezPath::new();
264        for verb in self.verbs() {
265            match *verb {
266                PathVerb::MoveTo(point) => path.move_to(normalize(point)),
267                PathVerb::LineTo(point) => path.line_to(normalize(point)),
268                PathVerb::QuadraticTo(control, end) => {
269                    path.quad_to(normalize(control), normalize(end))
270                }
271                PathVerb::CubicTo(first, second, end) => {
272                    path.curve_to(normalize(first), normalize(second), normalize(end))
273                }
274                PathVerb::Close => path.close_path(),
275            }
276        }
277        let bounds = path.bounding_box();
278        if ![bounds.x0, bounds.y0, bounds.x1, bounds.y1]
279            .iter()
280            .all(|value| value.is_finite())
281        {
282            return hull;
283        }
284        let first = hull.anchor(Pivot::Relative(
285            bounds.x0.clamp(0.0, 1.0),
286            bounds.y0.clamp(0.0, 1.0),
287        ));
288        let last = hull.anchor(Pivot::Relative(
289            bounds.x1.clamp(0.0, 1.0),
290            bounds.y1.clamp(0.0, 1.0),
291        ));
292        let mut result = Rect::new(first.x, first.y, last.x, last.y);
293        for verb in self.verbs() {
294            if let PathVerb::MoveTo(point) = verb {
295                result = Rect::new(
296                    result.left.min(point.x),
297                    result.top.min(point.y),
298                    result.right.max(point.x),
299                    result.bottom.max(point.y),
300                );
301            }
302        }
303        result
304    }
305
306    pub(crate) fn cached_stroke(&self, key: [u64; 4]) -> Option<Path2D> {
307        let mut entries = self.data.strokes.get()?.lock_unpoisoned();
308        let index = entries.iter().position(|entry| entry.0 == key)?;
309        let entry = entries.remove(index);
310        let result = Self {
311            data: Arc::new(entry.1.clone()),
312        };
313        entries.push(entry);
314        Some(result)
315    }
316
317    pub(crate) fn retain_stroke(&self, key: [u64; 4], outline: &Path2D) {
318        let bytes = |data: &PathData| {
319            data.verbs.len() * std::mem::size_of::<PathVerb>()
320                + std::mem::size_of::<([u64; 4], PathData)>()
321        };
322        let cost = bytes(&outline.data);
323        if cost > 1024 * 1024 {
324            return;
325        }
326        outline.bounding_box();
327        outline.fingerprint();
328        let mut snapshot = (*outline.data).clone();
329        snapshot.metrics.take();
330        snapshot.strokes.take();
331        let mut entries = self
332            .data
333            .strokes
334            .get_or_init(|| Arc::new(Mutex::new(Vec::new())))
335            .lock_unpoisoned();
336        if entries.iter().any(|entry| entry.0 == key) {
337            return;
338        }
339        while !entries.is_empty()
340            && (entries.len() >= 4
341                || entries.iter().map(|entry| bytes(&entry.1)).sum::<usize>() + cost > 1024 * 1024)
342        {
343            entries.remove(0);
344        }
345        if entries.try_reserve(1).is_ok() {
346            entries.push((key, snapshot));
347        }
348    }
349}
350
351fn invalid(field: &str, message: &str) -> ValidationError {
352    ValidationError::invalid("path2d", field, message)
353}
motion_core/path2d.rs

motion_core/
path2d.rs
