fastanim_core/
transform_diff.rs

1//! `TransformDiff` (SPEC §7): turns an edit script between two keyed sequences of parts into
2//! choreographed animation, so unchanged parts slide, moved parts arc and only real changes
3//! fade or morph.
4
5use std::f32::consts::PI;
6use std::hash::Hash;
7use std::ops::{Deref, Range};
8
9use fastanim_diff::{Algorithm, DiffOptions, Differ, Op, expand};
10use kurbo::{Affine, Point, Vec2};
11
12use crate::Interpolate;
13use crate::anim::{Animation, RateFn};
14use crate::color::{BLUE, Color, GREEN, GREY, ORANGE, RED, YELLOW};
15use crate::geom::align;
16use crate::mobject::{MobjectId, SceneState, VState};
17use crate::timeline::Scene;
18
19/// Mobjects in the scene grouped into keyed parts, e.g. a text's glyphs grouped into tokens.
20/// Derefs to the ids, so it can be passed wherever `&[MobjectId]` is expected.
21#[derive(Debug, Clone, PartialEq)]
22pub struct Group<K> {
23    /// The mobjects, in order.
24    pub ids: Vec<MobjectId>,
25    /// Each part's key and its range of [`ids`](Group::ids); contiguous and in order.
26    pub parts: Vec<(K, Range<usize>)>,
27    /// Runs of [`parts`](Group::parts) forming lines, diffed coarse-to-fine (SPEC §5.6);
28    /// contiguous and in order. Empty means one line.
29    pub lines: Vec<Range<usize>>,
30}
31
32/// Shapes grouped into keyed parts and lines, not yet in a scene: what a [`Group`] is added
33/// from or transforms into. Fields are as in [`Group`].
34#[derive(Debug, Clone, PartialEq)]
35pub struct Layout<K> {
36    /// The shapes, in order.
37    pub states: Vec<VState>,
38    /// Each part's key and its range of [`states`](Layout::states).
39    pub parts: Vec<(K, Range<usize>)>,
40    /// Runs of parts forming lines; empty means one line.
41    pub lines: Vec<Range<usize>>,
42}
43
44impl<K: Clone> Group<K> {
45    /// Adds the layout's shapes to the scene as one group.
46    pub fn add(s: &mut Scene, layout: &Layout<K>) -> Self {
47        Self {
48            ids: layout.states.iter().map(|m| s.add(m.clone())).collect(),
49            parts: layout.parts.clone(),
50            lines: layout.lines.clone(),
51        }
52    }
53}
54
55impl<K> Deref for Group<K> {
56    type Target = [MobjectId];
57    fn deref(&self) -> &[MobjectId] {
58        &self.ids
59    }
60}
61
62/// When each kind of op animates within the clip.
63#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
64pub enum Phasing {
65    /// Deletes, then everything that stays, then inserts, one after another.
66    Sequential,
67    /// The phases overlap (SPEC §7.3): deletes first, inserts last.
68    #[default]
69    Overlapped,
70}
71
72/// How replaced parts change.
73#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
74pub enum ReplaceStyle {
75    /// Aligned path morph.
76    #[default]
77    Morph,
78    /// The old shape fades out, then the new one fades in.
79    CrossFade,
80}
81
82/// Choreography of a [`TransformDiff`].
83#[derive(Debug, Clone, Copy, PartialEq)]
84pub struct DiffStyle {
85    /// When each kind of op runs.
86    pub phasing: Phasing,
87    /// Stagger between mobjects within a phase, as a fraction of one mobject's duration.
88    pub lag_ratio: f32,
89    /// Moved parts travel along an arc of this angle (radians); 0 is a straight line.
90    pub move_arc: f64,
91    /// How replaced parts change.
92    pub replace: ReplaceStyle,
93    /// Briefly tint inserted and replaced parts.
94    pub highlight_changes: bool,
95    /// Color parts by op while the clip plays (SPEC §7.4): green insert, red delete, blue move,
96    /// amber replace, grey equal.
97    pub debug: bool,
98}
99
100impl Default for DiffStyle {
101    fn default() -> Self {
102        Self {
103            phasing: Phasing::Overlapped,
104            lag_ratio: 0.05,
105            move_arc: std::f64::consts::FRAC_PI_3,
106            replace: ReplaceStyle::Morph,
107            highlight_changes: false,
108            debug: false,
109        }
110    }
111}
112
113/// What happens to one mobject.
114#[derive(Debug, Clone, Copy, PartialEq, Eq)]
115enum Kind {
116    Delete,
117    Equal,
118    Move,
119    Replace,
120    Insert,
121}
122
123impl Kind {
124    /// Phase as a fraction of the clip.
125    fn phase(self, phasing: Phasing) -> (f32, f32) {
126        match (phasing, self) {
127            (Phasing::Overlapped, Kind::Delete) => (0.0, 0.35),
128            (Phasing::Overlapped, Kind::Equal | Kind::Move) => (0.2, 0.8),
129            (Phasing::Overlapped, Kind::Replace) => (0.3, 0.85),
130            (Phasing::Overlapped, Kind::Insert) => (0.6, 1.0),
131            (Phasing::Sequential, Kind::Delete) => (0.0, 1.0 / 3.0),
132            (Phasing::Sequential, Kind::Equal | Kind::Move | Kind::Replace) => {
133                (1.0 / 3.0, 2.0 / 3.0)
134            }
135            (Phasing::Sequential, Kind::Insert) => (2.0 / 3.0, 1.0),
136        }
137    }
138
139    fn debug_color(self) -> Color {
140        match self {
141            Kind::Delete => RED,
142            Kind::Equal => GREY,
143            Kind::Move => BLUE,
144            Kind::Replace => ORANGE,
145            Kind::Insert => GREEN,
146        }
147    }
148}
149
150struct Track {
151    id: MobjectId,
152    kind: Kind,
153    /// `None` for deletes: the mobject leaves the scene.
154    target: Option<VState>,
155    /// Aligned start and end, set by `plan`.
156    ends: Option<(VState, VState)>,
157    /// Start and length as fractions of the clip, set by `plan`.
158    window: (f32, f32),
159}
160
161/// Animates a [`Group`] into a new arrangement planned by diffing part keys; made by
162/// [`Group::transform_diff`].
163pub struct TransformDiff {
164    tracks: Vec<Track>,
165    ops: Vec<Op>,
166    style: DiffStyle,
167}
168
169impl<K: Eq + Hash + Clone> Group<K> {
170    /// Plans the morph of this group into `to` and updates the group to describe the result.
171    /// Play the returned animation next.
172    ///
173    /// Parts are matched by key, line by line first with patience diff when there are lines,
174    /// then with Myers' diff (see [`diff`](Group::diff)). New mobjects are added now,
175    /// invisible; deleted ones leave the scene when the animation ends.
176    pub fn transform_diff<C: Eq + Hash>(
177        &mut self,
178        s: &mut Scene,
179        to: &Layout<K>,
180        class: impl Fn(&K) -> Option<C>,
181    ) -> TransformDiff {
182        let ops = self.diff(s.state(), to, class);
183        self.transform_ops(s, to, ops)
184    }
185
186    /// The edit script from this group's parts to `to`'s.
187    ///
188    /// Lines are diffed first with patience diff, keyed by their parts' keys; parts of equal
189    /// or moved lines pair in order, and replaced runs of lines are diffed part by part. Moves and replacements
190    /// pair by distance, and non-adjacent deletes and inserts of the same `class` pair into a
191    /// replacement (e.g. `+` → `−`).
192    pub fn diff<C: Eq + Hash>(
193        &self,
194        state: &SceneState,
195        to: &Layout<K>,
196        class: impl Fn(&K) -> Option<C>,
197    ) -> Vec<Op> {
198        let ca: Vec<Point> = (self.parts.iter())
199            .map(|(_, r)| center(self.ids[r.clone()].iter().map(|id| &state[id])))
200            .collect();
201        let cb: Vec<Point> = (to.parts.iter())
202            .map(|(_, r)| center(to.states[r.clone()].iter()))
203            .collect();
204        #[allow(clippy::single_range_in_vec_init, reason = "one line of all parts")]
205        let lines = |l: &[Range<usize>], n: usize| match l {
206            [] => vec![0..n],
207            l => l.to_vec(),
208        };
209        let (la, lb) = (
210            lines(&self.lines, self.parts.len()),
211            lines(&to.lines, to.parts.len()),
212        );
213        let keys = |parts: &[(K, Range<usize>)], l: &[Range<usize>]| -> Vec<Vec<K>> {
214            (l.iter())
215                .map(|r| parts[r.clone()].iter().map(|(k, _)| k.clone()).collect())
216                .collect()
217        };
218        let (ka, kb) = (keys(&self.parts, &la), keys(&to.parts, &lb));
219        let outer = Differ::new(&ka, &kb, |k| k.clone())
220            .options(DiffOptions {
221                algorithm: Algorithm::Patience,
222                ..DiffOptions::default()
223            })
224            .run();
225        expand(&outer, &la, &lb, |ra, rb| {
226            let (ao, bo) = (ra.start, rb.start);
227            Differ::new(&self.parts[ra], &to.parts[rb], |(k, _)| k.clone())
228                .cost(|i, j| ca[ao + i].distance(cb[bo + j]))
229                .class(|(k, _)| class(k))
230                .run()
231        })
232    }
233
234    /// Like [`transform_diff`](Group::transform_diff), with the edit script given, e.g. a
235    /// [`diff`](Group::diff) with ops rewritten.
236    pub fn transform_ops(&mut self, s: &mut Scene, to: &Layout<K>, ops: Vec<Op>) -> TransformDiff {
237        let glyphs = |parts: &[(K, Range<usize>)], r: Range<usize>| -> Vec<usize> {
238            parts[r].iter().flat_map(|(_, g)| g.clone()).collect()
239        };
240        let mut tracks = Vec::new();
241        let mut new_ids = vec![None; to.states.len()];
242        for op in &ops {
243            let (a, b, kind) = match op {
244                Op::Equal { a, b } => (*a..a + 1, *b..b + 1, Kind::Equal),
245                Op::Move { a, b } => (*a..a + 1, *b..b + 1, Kind::Move),
246                Op::Replace { a, b } => (a.clone(), b.clone(), Kind::Replace),
247                Op::Delete { a } => (*a..a + 1, 0..0, Kind::Delete),
248                Op::Insert { b } => (0..0, *b..b + 1, Kind::Insert),
249            };
250            let (a, b) = (glyphs(&self.parts, a), glyphs(&to.parts, b));
251            // Pair mobjects in order; leftovers fade out or in.
252            for k in 0..a.len().max(b.len()) {
253                let (id, kind) = match (a.get(k), b.get(k)) {
254                    (Some(&i), Some(_)) => (self.ids[i], kind),
255                    (Some(&i), None) => (self.ids[i], Kind::Delete),
256                    (None, Some(&j)) => (
257                        s.add(VState {
258                            opacity: 0.0,
259                            ..to.states[j].clone()
260                        }),
261                        Kind::Insert,
262                    ),
263                    (None, None) => unreachable!(),
264                };
265                let target = b.get(k).map(|&j| {
266                    new_ids[j] = Some(id);
267                    to.states[j].clone()
268                });
269                tracks.push(Track {
270                    id,
271                    kind,
272                    target,
273                    ends: None,
274                    window: (0.0, 1.0),
275                });
276            }
277        }
278
279        self.ids = new_ids
280            .into_iter()
281            .map(|id| id.expect("ops cover every target part"))
282            .collect();
283        self.parts = to.parts.clone();
284        self.lines = to.lines.clone();
285        TransformDiff {
286            tracks,
287            ops,
288            style: DiffStyle::default(),
289        }
290    }
291}
292
293/// Center of the joint bounding box; the origin when empty.
294pub(crate) fn center<'a>(states: impl Iterator<Item = &'a VState>) -> Point {
295    states
296        .filter_map(|m| m.path.bbox())
297        .reduce(|a, b| a.union(b))
298        .map_or(Point::ORIGIN, |b| b.center())
299}
300
301/// Shrunk to a fifth about its center and transparent: where inserts come from and deletes go.
302fn vanished(m: &VState) -> VState {
303    VState {
304        opacity: 0.0,
305        ..m.clone().scale(0.2)
306    }
307}
308
309impl TransformDiff {
310    /// Sets the choreography.
311    pub fn style(self, style: DiffStyle) -> Self {
312        Self { style, ..self }
313    }
314
315    /// Colors parts by op while the clip plays; see [`DiffStyle::debug`].
316    pub fn debug(mut self) -> Self {
317        self.style.debug = true;
318        self
319    }
320
321    /// The edit script between the parts, for inspection and tests.
322    pub fn ops(&self) -> &[Op] {
323        &self.ops
324    }
325}
326
327impl Animation for TransformDiff {
328    fn plan(&mut self, state: &SceneState) {
329        // Stagger like `write`: within a phase, each mobject starts `lag_ratio` of its duration
330        // after the previous one.
331        let phasing = self.style.phasing;
332        // Kinds sharing a phase are staggered together (and recomputed identically per kind).
333        for kind in [
334            Kind::Delete,
335            Kind::Equal,
336            Kind::Move,
337            Kind::Replace,
338            Kind::Insert,
339        ] {
340            let (s, e) = kind.phase(phasing);
341            let in_phase = |t: &&mut Track| t.kind.phase(phasing) == (s, e);
342            let n = self.tracks.iter_mut().filter(in_phase).count();
343            let lag = self.style.lag_ratio;
344            let w = (e - s) / (1.0 + n.saturating_sub(1) as f32 * lag);
345            let mut k = 0.0;
346            for t in self.tracks.iter_mut().filter(in_phase) {
347                t.window = (s + k * lag * w, w);
348                k += 1.0;
349            }
350        }
351        for t in &mut self.tracks {
352            let from = state[&t.id].clone();
353            t.ends = Some(match (&t.target, t.kind) {
354                (None, _) => (from.clone(), vanished(&from)),
355                (Some(to), Kind::Insert) => (vanished(to), to.clone()),
356                (Some(to), _) => {
357                    let (a, b) = align(&from.path, &to.path);
358                    (
359                        VState { path: a, ..from },
360                        VState {
361                            path: b,
362                            ..to.clone()
363                        },
364                    )
365                }
366            });
367        }
368    }
369
370    fn sample(&self, alpha: f32, state: &mut SceneState) {
371        for t in &self.tracks {
372            // Exact endpoint: alignment re-segments paths, and deletes leave the scene.
373            if alpha >= 1.0 {
374                match &t.target {
375                    Some(to) => state.insert(t.id, to.clone()),
376                    None => state.remove(&t.id),
377                };
378                continue;
379            }
380            let (a, b) = t.ends.as_ref().expect("sample before plan");
381            let p = RateFn::Smooth.apply((alpha - t.window.0) / t.window.1);
382            let mut m = if t.kind == Kind::Replace && self.style.replace == ReplaceStyle::CrossFade
383            {
384                let (m, f) = if p < 0.5 {
385                    (a, 1.0 - 2.0 * p)
386                } else {
387                    (b, 2.0 * p - 1.0)
388                };
389                VState {
390                    opacity: m.opacity * f,
391                    ..m.clone()
392                }
393            } else {
394                VState::lerp(a, b, p)
395            };
396            if t.kind == Kind::Move && self.style.move_arc != 0.0 {
397                // ponytail: a parabolic bow with the arc's sagitta, not a true circular arc.
398                // Moving right bows up and moving left bows down, so swapping parts pass on
399                // opposite sides.
400                let d = b.path.center() - a.path.center();
401                let bow = Vec2::new(-d.y, d.x) * (0.5 * (self.style.move_arc / 4.0).tan());
402                let h = f64::from(4.0 * p * (1.0 - p));
403                m = m.transform(Affine::translate(bow * h));
404            }
405            if self.style.debug {
406                m.fill = t.kind.debug_color().with_alpha(m.fill.a.max(0.5));
407            } else if self.style.highlight_changes && matches!(t.kind, Kind::Insert | Kind::Replace)
408            {
409                m.fill = Color::lerp(&m.fill, &YELLOW.with_alpha(m.fill.a), 0.8 * (PI * p).sin());
410            }
411            state.insert(t.id, m);
412        }
413    }
414
415    fn rate_fn(&self) -> RateFn {
416        // Each mobject eases within its own phase.
417        RateFn::Linear
418    }
419}
fastanim_core/transform_diff.rs

fastanim_core/
transform_diff.rs
