motion_content/vector/
morph.rs

1//! Shape morphing between vector trees by matching filled parts.
2
3use super::*;
4use crate::MorphPath;
5use motion_core::Shape;
6
7#[derive(Clone, Debug)]
8struct Part {
9    address: Vec<usize>,
10    world: Path2D,
11    inverse: Transform,
12    paint: Paint,
13    rule: FillRule,
14    key: Option<String>,
15    role: u8,
16    area: f64,
17}
18
19#[derive(Clone, Debug)]
20struct Pair {
21    source: Option<Part>,
22    target: Option<Part>,
23    from: MorphPath,
24    to: MorphPath,
25}
26
27/// Prepared, replayable semantic tree morph. Leaf IDs take priority, followed by
28/// position and signed-curve-area magnitude. Unmatched parts grow/shrink at their
29/// own center. Fill/stroke/image geometry shares MorphPath's original curves.
30/// Spatial paints and differing clipping/isolation crossfade the two retained
31/// hierarchies; solid colors interpolate in Oklab on the morphed geometry.
32#[derive(Clone, Debug)]
33pub struct Morph {
34    source: VectorTree,
35    target: VectorTree,
36    pairs: Arc<[Pair]>,
37}
38
39fn curve_area(path: &Path2D) -> f64 {
40    let mut curve = kurbo::BezPath::new();
41    for verb in path.verbs() {
42        match *verb {
43            motion_core::PathVerb::MoveTo(point) => curve.move_to((point.x, point.y)),
44            motion_core::PathVerb::LineTo(point) => curve.line_to((point.x, point.y)),
45            motion_core::PathVerb::QuadraticTo(control, end) => {
46                curve.quad_to((control.x, control.y), (end.x, end.y))
47            }
48            motion_core::PathVerb::CubicTo(first, second, end) => {
49                curve.curve_to((first.x, first.y), (second.x, second.y), (end.x, end.y))
50            }
51            motion_core::PathVerb::Close => curve.close_path(),
52        }
53    }
54    kurbo::Shape::area(&curve).abs()
55}
56
57fn parts(tree: &VectorTree) -> Result<Vec<Part>, ValidationError> {
58    let mut result = Vec::new();
59    for leaf in tree.paint_leaves() {
60        let inverse = leaf.transform.inverse().ok_or_else(|| {
61            invalid(
62                "transform",
63                "Tree morph requires invertible local-to-tree matrices",
64            )
65        })?;
66        let id = tree
67            .ids()
68            .iter()
69            .filter(|(_, address)| !address.is_empty() && leaf.address.starts_with(address))
70            .max_by_key(|(_, address)| address.len())
71            .map(|(id, address)| format!("{id}/{:?}", &leaf.address[address.len()..]));
72        let mut append = |geometry: Path2D,
73                          paint: Paint,
74                          rule: FillRule,
75                          role: u8|
76         -> Result<(), ValidationError> {
77            let world = geometry.transformed(&leaf.transform)?;
78            let area = curve_area(&world);
79            if !area.is_finite() {
80                return Err(invalid("area", "Curve area overflow"));
81            }
82            result.push(Part {
83                address: leaf.address.clone(),
84                world,
85                inverse,
86                paint,
87                rule,
88                key: id.as_ref().map(|id| format!("{id}:{role}")),
89                role,
90                area,
91            });
92            if result.len() > 1024 {
93                return Err(limited("Morph admits at most 1024 painted parts per tree"));
94            }
95            Ok(())
96        };
97        match leaf.item {
98            VectorItem::Path(path) => {
99                if let Some((paint, rule)) = &path.fill {
100                    append(path.path.as_ref().clone(), paint.clone(), *rule, 0)?;
101                }
102                if let Some((style, paint)) = &path.stroke {
103                    append(
104                        style.outline(&path.path, "vector_tree.morph.stroke")?,
105                        paint.clone(),
106                        FillRule::NonZero,
107                        1,
108                    )?;
109                }
110            }
111            VectorItem::Image(image) => {
112                if image.rect.width() > 0.0 && image.rect.height() > 0.0 {
113                    append(
114                        Path2D::from_rect(image.rect)?,
115                        image.pattern().into(),
116                        FillRule::NonZero,
117                        2,
118                    )?;
119                }
120            }
121            VectorItem::Group(_) => unreachable!(),
122        }
123    }
124    Ok(result)
125}
126
127impl Morph {
128    /// Prepares bounded leaf matching and exact cubic path pairs once. Input
129    /// trees remain immutable. Up to 1024 painted parts per side are admitted.
130    pub fn new(source: &VectorTree, target: &VectorTree) -> Result<Self, ValidationError> {
131        let sources = parts(source)?;
132        let targets = parts(target)?;
133        let mut used = vec![false; targets.len()];
134        let mut pairs = Vec::new();
135        let reserved = sources
136            .iter()
137            .filter_map(|part| part.key.clone())
138            .collect::<std::collections::BTreeSet<_>>();
139        let scale = source
140            .view_box()
141            .width()
142            .max(source.view_box().height())
143            .max(target.view_box().width())
144            .max(target.view_box().height())
145            .max(1.0);
146        for source in sources {
147            let exact = source.key.as_ref().and_then(|key| {
148                targets
149                    .iter()
150                    .enumerate()
151                    .find(|(index, target)| !used[*index] && target.key.as_ref() == Some(key))
152                    .map(|(index, _)| index)
153            });
154            let target = exact.or_else(|| {
155                targets
156                    .iter()
157                    .enumerate()
158                    .filter(|(index, target)| {
159                        !used[*index]
160                            && !target
161                                .key
162                                .as_ref()
163                                .is_some_and(|key| reserved.contains(key))
164                    })
165                    .min_by(|(_, first), (_, second)| {
166                        let cost = |target: &Part| {
167                            let source_center = source.world.bounding_box().center();
168                            let target_center = target.world.bounding_box().center();
169                            let horizontal = (source_center.x - target_center.x) / scale;
170                            let vertical = (source_center.y - target_center.y) / scale;
171                            horizontal * horizontal
172                                + vertical * vertical
173                                + (source.area - target.area).abs()
174                                    / (source.area + target.area).max(f64::MIN_POSITIVE)
175                                + if source.role == target.role { 0.0 } else { 2.0 }
176                        };
177                        cost(first).total_cmp(&cost(second))
178                    })
179                    .map(|(index, _)| index)
180            });
181            let target = target.map(|index| {
182                used[index] = true;
183                targets[index].clone()
184            });
185            let (from, to) = MorphPath::pair(
186                source.world.clone(),
187                target
188                    .as_ref()
189                    .map_or_else(Path2D::new, |part| part.world.clone()),
190            )?;
191            pairs.push(Pair {
192                source: Some(source),
193                target,
194                from,
195                to,
196            });
197        }
198        for (index, target) in targets.into_iter().enumerate() {
199            if !used[index] {
200                let (from, to) = MorphPath::pair(Path2D::new(), target.world.clone())?;
201                pairs.push(Pair {
202                    source: None,
203                    target: Some(target),
204                    from,
205                    to,
206                });
207            }
208        }
209        Ok(Self {
210            source: source.clone(),
211            target: target.clone(),
212            pairs: pairs.into(),
213        })
214    }
215
216    /// Evaluates without pairing again, I/O or history. Exact endpoints preserve
217    /// the original trees; finite progress clamps to 0..=1. Group opacity is not
218    /// multiplied independently into overlapping leaves.
219    pub fn sample(&self, progress: f64) -> Result<Node, ValidationError> {
220        if !progress.is_finite() {
221            return Err(invalid("progress", "Morph progress must be finite"));
222        }
223        let progress = progress.clamp(0.0, 1.0);
224        if progress == 0.0 || Arc::ptr_eq(&self.source.data, &self.target.data) {
225            return Ok(self.source.node());
226        }
227        if progress == 1.0 {
228            return Ok(self.target.node());
229        }
230        let mut source = BTreeMap::<Vec<usize>, Vec<Node>>::new();
231        let mut target = BTreeMap::<Vec<usize>, Vec<Node>>::new();
232        for pair in self.pairs.iter() {
233            let geometry = pair.from.try_interpolate(&pair.to, progress)?.path();
234            let color = match (&pair.source, &pair.target) {
235                (Some(source), Some(target)) => match (&source.paint, &target.paint) {
236                    (Paint::Solid(source), Paint::Solid(target)) => {
237                        Some(Paint::Solid(source.interpolate(target, progress)))
238                    }
239                    _ => None,
240                },
241                _ => None,
242            };
243            for (part, output) in [(&pair.source, &mut source), (&pair.target, &mut target)] {
244                if let Some(part) = part {
245                    let path = VectorPath {
246                        id: None,
247                        path: Arc::new(geometry.transformed(&part.inverse)?),
248                        fill: Some((color.as_ref().unwrap_or(&part.paint).clone(), part.rule)),
249                        stroke: None,
250                        source: None,
251                    };
252                    output
253                        .entry(part.address.clone())
254                        .or_default()
255                        .push(Node::from(path));
256                }
257            }
258        }
259
260        fn build(
261            group: &VectorGroup,
262            address: &mut Vec<usize>,
263            parts: &BTreeMap<Vec<usize>, Vec<Node>>,
264        ) -> Node {
265            let children = group
266                .children
267                .iter()
268                .enumerate()
269                .map(|(index, item)| {
270                    address.push(index);
271                    let node = match item {
272                        VectorItem::Group(child) => build(child, address, parts),
273                        _ => Node::group(parts.get(address).cloned().unwrap_or_default()),
274                    };
275                    address.pop();
276                    node
277                })
278                .collect::<Vec<_>>();
279            group.decorate(children)
280        }
281        Node::weighted_sum([
282            (
283                build(self.source.root(), &mut Vec::new(), &source),
284                1.0 - progress,
285            ),
286            (
287                build(self.target.root(), &mut Vec::new(), &target),
288                progress,
289            ),
290        ])
291    }
292}
293
294#[cfg(test)]
295mod tests {
296    use super::*;
297    use motion_core::{Color, PixelSize, RasterLimits, Size};
298    use motion_render::RenderPrepare;
299
300    fn tree(colors: &[Color], reverse: bool) -> Result<VectorTree, ValidationError> {
301        let mut children = colors
302            .iter()
303            .enumerate()
304            .map(|(index, color)| {
305                let mut path = VectorPath::filled(
306                    Path2D::from_rect(Rect::new(
307                        1.0 + index as f64 * 5.0,
308                        1.0,
309                        5.0 + index as f64 * 5.0,
310                        5.0,
311                    ))
312                    .unwrap(),
313                    *color,
314                );
315                path.id = Some(format!("part-{index}").into());
316                VectorItem::Path(path)
317            })
318            .collect::<Vec<_>>();
319        if reverse {
320            children.reverse();
321        }
322        VectorTree::new(
323            Rect::new(0.0, 0.0, 20.0, 8.0),
324            VectorGroup {
325                opacity: 0.5,
326                children,
327                ..Default::default()
328            },
329        )
330    }
331
332    fn pixels(node: Node) -> motion_core::Result<motion_render::LinearFrame> {
333        Ok(node
334            .compile(
335                Size::new(20.0, 8.0),
336                PixelSize::new(20, 8),
337                ValidationLimits::default(),
338            )?
339            .prepare(ValidationLimits::default(), RasterLimits::default())?
340            .render_linear(RasterLimits::default())?)
341    }
342
343    #[test]
344    fn tree_morph_pairs_ids_grows_missing_leaves_and_preserves_group_alpha()
345    -> motion_core::Result<()> {
346        let from = tree(&[Color::rgb(255, 0, 0), Color::WHITE], false)?;
347        let to = tree(&[Color::rgb(0, 0, 255), Color::WHITE, Color::WHITE], true)?;
348        let morph = Morph::new(&from, &to)?;
349        assert_eq!(
350            pixels(morph.sample(0.0)?)?.pixels(),
351            pixels(from.node())?.pixels()
352        );
353        assert_eq!(
354            pixels(morph.sample(1.0)?)?.pixels(),
355            pixels(to.node())?.pixels()
356        );
357        let middle = pixels(morph.sample(0.5)?)?;
358        assert_eq!(middle.pixel(2, 2).unwrap()[3], 0.5);
359        assert!(middle.pixel(2, 2).unwrap()[0] > 0.0 && middle.pixel(2, 2).unwrap()[2] > 0.0);
360        assert!(middle.pixel(12, 2).unwrap()[3] > 0.0);
361        assert_eq!(middle.pixels(), pixels(morph.sample(0.5)?)?.pixels());
362        let empty = VectorTree::new(from.view_box(), VectorGroup::default())?;
363        assert!(
364            pixels(Morph::new(&from, &empty)?.sample(1.0)?)?
365                .pixels()
366                .iter()
367                .all(|pixel| *pixel == [0.0; 4])
368        );
369        assert!(morph.sample(f64::NAN).is_err());
370        Ok(())
371    }
372
373    #[test]
374    fn exact_ids_are_reserved_before_geometry_and_overlapping_groups_isolate_once()
375    -> motion_core::Result<()> {
376        let base = tree(&[Color::WHITE, Color::WHITE], false)?;
377        let mut source = base.root().clone();
378        if let VectorItem::Path(path) = &mut source.children[0] {
379            path.id = Some("missing".into());
380        }
381        let source = VectorTree::new(base.view_box(), source)?;
382        let mut target = base.root().clone();
383        target.children.remove(0);
384        let target = VectorTree::new(base.view_box(), target)?;
385        let morph = Morph::new(&source, &target)?;
386        assert!(morph.pairs[0].target.is_none());
387        assert!(morph.pairs[1].target.is_some());
388        let mut source = base.root().clone();
389        source.children[1] = source.children[0].clone();
390        if let VectorItem::Path(path) = &mut source.children[1] {
391            path.id = Some("overlap".into());
392        }
393        let source = VectorTree::new(base.view_box(), source)?;
394        let mut target = source.root().clone();
395        let mut extra = target.children[0].clone();
396        if let VectorItem::Path(path) = &mut extra {
397            path.id = Some("extra".into());
398        }
399        target.children.push(extra);
400        let target = VectorTree::new(base.view_box(), target)?;
401        assert_eq!(
402            pixels(Morph::new(&source, &target)?.sample(0.5)?)?
403                .pixel(2, 2)
404                .unwrap()[3],
405            0.5
406        );
407        Ok(())
408    }
409}
motion_content/vector/morph.rs

motion_content/vector/
morph.rs
