Skip to main content

alpha2_model/
easing.rs

1//! Timing curves shared by keyframe interpolation and transitions.
2//!
3//! The one parametric curve is CSS Easing Functions Level 1 `cubic-bezier(x1, y1, x2, y2)`,
4//! the same definition web animation, Lottie and motion tools use. Named presets (`ease`,
5//! `ease-in`, ...) are values of it kept by hosts, not the model.
6//!
7//! Evaluation uses only `f64` add, subtract, multiply and divide (no transcendental
8//! functions, no fused multiply-add) with a fixed iteration budget, so wasm and native
9//! produce identical bits.
10
11use serde::{Deserialize, Serialize};
12
13/// A CSS `cubic-bezier(x1, y1, x2, y2)` timing curve.
14///
15/// `x1` and `x2` lie in `0..=1`, which keeps the curve a function of its input. `y1` and `y2`
16/// are unbounded, so a curve may overshoot.
17#[derive(Copy, Clone, Debug, Deserialize, PartialEq, Serialize)]
18#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
19#[serde(deny_unknown_fields)]
20pub struct CubicBezier {
21    /// Horizontal coordinate of the first control point, in `0..=1`.
22    pub x1: f32,
23    /// Vertical coordinate of the first control point.
24    pub y1: f32,
25    /// Horizontal coordinate of the second control point, in `0..=1`.
26    pub x2: f32,
27    /// Vertical coordinate of the second control point.
28    pub y2: f32,
29}
30
31/// Newton steps tried before bisection takes over.
32const NEWTON_STEPS: usize = 8;
33/// Bisection halvings; 2^-64 is far below the tolerance.
34const BISECTION_STEPS: usize = 64;
35/// Accepted distance between the curve's `x` and the requested progress.
36const TOLERANCE: f64 = 1e-12;
37/// A slope this flat would send a Newton step far outside the curve.
38const MIN_SLOPE: f64 = 1e-9;
39
40impl CubicBezier {
41    /// Creates a curve from its two inner control points.
42    #[must_use]
43    pub const fn new(x1: f32, y1: f32, x2: f32, y2: f32) -> Self {
44        Self { x1, y1, x2, y2 }
45    }
46
47    /// Whether every coordinate is finite and `x1`, `x2` lie in `0..=1`.
48    #[must_use]
49    pub fn is_valid(self) -> bool {
50        [self.x1, self.y1, self.x2, self.y2]
51            .into_iter()
52            .all(f32::is_finite)
53            && (0.0..=1.0).contains(&self.x1)
54            && (0.0..=1.0).contains(&self.x2)
55    }
56
57    /// The curve's output at linear `progress`, which is clamped to `0..=1`.
58    ///
59    /// 0 maps exactly to 0 and 1 to 1. Between them the output may leave `0..=1` when `y1` or
60    /// `y2` does.
61    #[must_use]
62    pub fn apply(self, progress: f64) -> f64 {
63        let x = progress.clamp(0.0, 1.0);
64        if x <= 0.0 {
65            return 0.0;
66        }
67        if x >= 1.0 {
68            return 1.0;
69        }
70        let parameter = self.parameter_at(x);
71        component(parameter, f64::from(self.y1), f64::from(self.y2))
72    }
73
74    /// The part of the curve between linear progress `from` and `to`, rescaled to the unit
75    /// square, so that it shows the same output over that part of a segment. `None` when the
76    /// output is equal at both ends (or the part is empty), which no rescaled curve can show.
77    ///
78    /// Uses only the operations of [`Self::apply`], so every platform gets the same bits.
79    #[must_use]
80    #[allow(clippy::cast_possible_truncation)]
81    pub fn between(self, from: f64, to: f64) -> Option<Self> {
82        let parameter = |progress: f64| {
83            if progress <= 0.0 {
84                0.0
85            } else if progress >= 1.0 {
86                1.0
87            } else {
88                self.parameter_at(progress)
89            }
90        };
91        let (u, v) = (parameter(from), parameter(to));
92        let part = |p1: f32, p2: f32| {
93            let points = [0.0, f64::from(p1), f64::from(p2), 1.0];
94            [
95                blossom(points, u, u, u),
96                blossom(points, u, u, v),
97                blossom(points, u, v, v),
98                blossom(points, v, v, v),
99            ]
100        };
101        let (x, y) = (part(self.x1, self.x2), part(self.y1, self.y2));
102        let (width, height) = (x[3] - x[0], y[3] - y[0]);
103        if width <= 0.0 || height == 0.0 {
104            return None;
105        }
106        let curve = Self::new(
107            ((x[1] - x[0]) / width).clamp(0.0, 1.0) as f32,
108            ((y[1] - y[0]) / height) as f32,
109            ((x[2] - x[0]) / width).clamp(0.0, 1.0) as f32,
110            ((y[2] - y[0]) / height) as f32,
111        );
112        curve.is_valid().then_some(curve)
113    }
114
115    /// The Bezier parameter whose `x` equals `x`, for `x` in `(0, 1)`.
116    fn parameter_at(self, x: f64) -> f64 {
117        self.newton(x).unwrap_or_else(|| self.bisection(x))
118    }
119
120    /// Newton's method from `t = x`, if it lands within `NEWTON_STEPS` without leaving `0..=1`.
121    fn newton(self, x: f64) -> Option<f64> {
122        let (x1, x2) = (f64::from(self.x1), f64::from(self.x2));
123        let mut parameter = x;
124        for _ in 0..NEWTON_STEPS {
125            let error = component(parameter, x1, x2) - x;
126            if error.abs() < TOLERANCE {
127                return (0.0..=1.0).contains(&parameter).then_some(parameter);
128            }
129            let slope = slope(parameter, x1, x2);
130            if slope.abs() < MIN_SLOPE {
131                return None;
132            }
133            parameter -= error / slope;
134        }
135        None
136    }
137
138    /// Bisection on `0..=1`, where `x(t)` is non-decreasing because `x1` and `x2` lie in `0..=1`.
139    /// It converges where Newton fails on flat parts.
140    fn bisection(self, x: f64) -> f64 {
141        let (x1, x2) = (f64::from(self.x1), f64::from(self.x2));
142        let (mut low, mut high) = (0.0_f64, 1.0_f64);
143        let mut parameter = x;
144        for _ in 0..BISECTION_STEPS {
145            let value = component(parameter, x1, x2);
146            if (value - x).abs() < TOLERANCE {
147                break;
148            }
149            if value < x {
150                low = parameter;
151            } else {
152                high = parameter;
153            }
154            parameter = low + (high - low) * 0.5;
155        }
156        parameter
157    }
158}
159
160/// One coordinate of the curve at parameter `t` for inner control coordinates `p1`, `p2`:
161/// `3 (1-t)^2 t p1 + 3 (1-t) t^2 p2 + t^3`, in Horner form.
162fn component(t: f64, p1: f64, p2: f64) -> f64 {
163    let c = 3.0 * p1;
164    let b = 3.0 * (p2 - p1) - c;
165    let a = 1.0 - c - b;
166    ((a * t + b) * t + c) * t
167}
168
169/// The blossom of a cubic with control values `points` at `(u, v, w)`: de Casteljau with one
170/// parameter per level. `(u, u, v)` and `(u, v, v)` are the inner controls of the part `u..=v`.
171fn blossom(points: [f64; 4], u: f64, v: f64, w: f64) -> f64 {
172    let lerp = |a: f64, b: f64, t: f64| a + (b - a) * t;
173    let first = [
174        lerp(points[0], points[1], u),
175        lerp(points[1], points[2], u),
176        lerp(points[2], points[3], u),
177    ];
178    let second = [lerp(first[0], first[1], v), lerp(first[1], first[2], v)];
179    lerp(second[0], second[1], w)
180}
181
182/// The derivative of [`component`] with respect to `t`.
183fn slope(t: f64, p1: f64, p2: f64) -> f64 {
184    let c = 3.0 * p1;
185    let b = 3.0 * (p2 - p1) - c;
186    let a = 1.0 - c - b;
187    (3.0 * a * t + 2.0 * b) * t + c
188}
189
190/// A timing curve from linear progress to eased progress, without a hold.
191///
192/// Transitions use it directly; keyframe [`crate::Interpolation`] adds `hold`.
193#[derive(Copy, Clone, Debug, Deserialize, PartialEq, Serialize)]
194#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
195#[serde(tag = "type", rename_all = "snake_case", from = "EasingWire")]
196pub enum Easing {
197    /// Progress advances at a constant rate.
198    Linear,
199    /// Progress follows a CSS `cubic-bezier()` curve.
200    CubicBezier(CubicBezier),
201}
202
203/// The wire form of [`Easing`].
204///
205/// serde lets an internally tagged unit variant ignore extra fields even with
206/// `deny_unknown_fields`; empty struct variants reject them, as the published schema does.
207#[derive(Deserialize)]
208#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
209#[cfg_attr(feature = "schema", schemars(rename = "Easing"))]
210#[serde(tag = "type", rename_all = "snake_case", deny_unknown_fields)]
211pub(crate) enum EasingWire {
212    /// Progress advances at a constant rate.
213    Linear {},
214    /// Progress follows a CSS `cubic-bezier()` curve.
215    CubicBezier(CubicBezier),
216}
217
218impl From<EasingWire> for Easing {
219    fn from(wire: EasingWire) -> Self {
220        match wire {
221            EasingWire::Linear {} => Self::Linear,
222            EasingWire::CubicBezier(curve) => Self::CubicBezier(curve),
223        }
224    }
225}
226
227impl Easing {
228    /// Whether the curve's parameters are usable.
229    #[must_use]
230    pub fn is_valid(self) -> bool {
231        match self {
232            Self::Linear => true,
233            Self::CubicBezier(curve) => curve.is_valid(),
234        }
235    }
236
237    /// Eased progress for linear `progress`, which is clamped to `0..=1`.
238    #[must_use]
239    pub fn apply(self, progress: f64) -> f64 {
240        match self {
241            Self::Linear => progress.clamp(0.0, 1.0),
242            Self::CubicBezier(curve) => curve.apply(progress),
243        }
244    }
245}
246
247#[cfg(test)]
248mod tests {
249    use super::{CubicBezier, Easing};
250
251    const EASE: CubicBezier = CubicBezier::new(0.25, 0.1, 0.25, 1.0);
252
253    #[test]
254    fn css_ease_matches_its_reference_value() {
255        // CSS `ease` at x = 0.5 is 0.80240338758485699 at t = 0.69957243870638562, computed
256        // independently by 200-step bisection in 50-digit decimal arithmetic. The f32 control
257        // points move it by under 1e-9.
258        assert!((EASE.apply(0.5) - 0.802_403_387_584_857).abs() < 1e-9);
259        assert!((EASE.parameter_at(0.5) - 0.699_572_438_706_385_6).abs() < 1e-9);
260        let ease_in_out = CubicBezier::new(0.42, 0.0, 0.58, 1.0);
261        // 0.42 and 0.58 are not exact in f32, so the symmetry is to ~1e-8.
262        assert!((ease_in_out.apply(0.5) - 0.5).abs() < 1e-7);
263        for x in [0.1, 0.25, 0.4] {
264            let mirrored = 1.0 - ease_in_out.apply(1.0 - x);
265            assert!((ease_in_out.apply(x) - mirrored).abs() < 1e-7);
266        }
267    }
268
269    #[test]
270    fn ends_are_exact_and_input_is_clamped() {
271        for curve in [EASE, CubicBezier::new(0.0, -2.0, 1.0, 3.0)] {
272            assert_eq!(curve.apply(0.0).to_bits(), 0.0_f64.to_bits());
273            assert_eq!(curve.apply(1.0).to_bits(), 1.0_f64.to_bits());
274            assert_eq!(curve.apply(-4.0).to_bits(), 0.0_f64.to_bits());
275            assert_eq!(curve.apply(9.0).to_bits(), 1.0_f64.to_bits());
276        }
277    }
278
279    #[test]
280    fn the_linear_curve_is_the_identity() {
281        let linear = CubicBezier::new(0.0, 0.0, 1.0, 1.0);
282        for index in 0..=64 {
283            let x = f64::from(index) / 64.0;
284            assert!((linear.apply(x) - x).abs() < 1e-12, "{x}");
285            assert!((Easing::Linear.apply(x) - x).abs() < f64::EPSILON);
286        }
287    }
288
289    #[test]
290    fn flat_curves_fall_back_to_bisection_and_stay_accurate() {
291        // x(t) = t^3 is flat at t = 0 and x(t) = 1 - (1 - t)^3 at t = 1, so Newton from t = x
292        // overshoots on the first and has no slope on the second.
293        let cases = [
294            (CubicBezier::new(0.0, 0.0, 0.0, 0.0), 0.001, 0.1),
295            (CubicBezier::new(1.0, 1.0, 1.0, 1.0), 0.999, 0.9),
296        ];
297        for (curve, x, parameter) in cases {
298            assert_eq!(curve.newton(x), None, "Newton must give up on {curve:?}");
299            let found = curve.parameter_at(x);
300            assert!((found - parameter).abs() < 1e-9, "{curve:?}: {found}");
301            let x_back = super::component(found, f64::from(curve.x1), f64::from(curve.x2));
302            assert!((x_back - x).abs() < 1e-12);
303        }
304    }
305
306    #[test]
307    fn a_part_of_a_curve_rescaled_shows_the_same_output() {
308        let curves = [
309            EASE,
310            CubicBezier::new(0.42, 0.0, 0.58, 1.0),
311            CubicBezier::new(0.3, -0.5, 0.7, 1.5),
312            CubicBezier::new(0.0, 0.0, 1.0, 1.0),
313        ];
314        for curve in curves {
315            for (from, to) in [
316                (0.0, 0.37),
317                (0.37, 1.0),
318                (0.1, 0.9),
319                (0.5, 0.55),
320                (0.0, 1.0),
321            ] {
322                let part = curve.between(from, to).expect("a curve that moves");
323                assert!(part.is_valid(), "{curve:?} {from} {to}");
324                let (low, high) = (curve.apply(from), curve.apply(to));
325                for step in 0..=1000 {
326                    let x = from + (to - from) * f64::from(step) / 1000.0;
327                    let local = (x - from) / (to - from);
328                    let shown = low + (high - low) * part.apply(local);
329                    // The part's controls are `f32`, as every curve of a document is.
330                    assert!(
331                        (shown - curve.apply(x)).abs() < 1e-6,
332                        "{curve:?} {from}..{to} at {x}: {shown} {}",
333                        curve.apply(x)
334                    );
335                }
336            }
337        }
338    }
339
340    #[test]
341    fn an_empty_part_has_no_curve() {
342        assert_eq!(EASE.between(0.4, 0.4), None);
343    }
344
345    #[test]
346    fn overshooting_curves_leave_the_unit_interval_between_the_ends() {
347        let back = CubicBezier::new(0.34, 1.56, 0.64, 1.0);
348        let peak = (1..100)
349            .map(|index| back.apply(f64::from(index) / 100.0))
350            .fold(f64::MIN, f64::max);
351        assert!(peak > 1.05, "ease-out-back overshoots: {peak}");
352        assert!((Easing::CubicBezier(back).apply(1.0) - 1.0).abs() < f64::EPSILON);
353    }
354
355    #[test]
356    fn control_points_outside_the_unit_square_are_rejected_horizontally_only() {
357        assert!(CubicBezier::new(0.0, -5.0, 1.0, 5.0).is_valid());
358        assert!(!CubicBezier::new(-0.1, 0.0, 1.0, 1.0).is_valid());
359        assert!(!CubicBezier::new(0.0, 0.0, 1.1, 1.0).is_valid());
360        assert!(!CubicBezier::new(0.0, f32::NAN, 1.0, 1.0).is_valid());
361        assert!(!Easing::CubicBezier(CubicBezier::new(0.0, 0.0, 2.0, 1.0)).is_valid());
362    }
363
364    #[test]
365    fn the_wire_form_is_a_tagged_object() {
366        let easing: Easing =
367            serde_json::from_str(r#"{"type":"cubic_bezier","x1":0.42,"y1":0,"x2":0.58,"y2":1}"#)
368                .expect("cubic bezier easing");
369        assert_eq!(
370            easing,
371            Easing::CubicBezier(CubicBezier::new(0.42, 0.0, 0.58, 1.0))
372        );
373        let linear: Easing = serde_json::from_str(r#"{"type":"linear"}"#).expect("linear");
374        assert_eq!(linear, Easing::Linear);
375        assert!(serde_json::from_str::<Easing>(r#""linear""#).is_err());
376        assert!(serde_json::from_str::<Easing>(r#"{"type":"linear","x1":0}"#).is_err());
377    }
378}