servo/components/style/bezier.rs

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
   4
   5 //! Parametric Bézier curves.
   6 //!
   7 //! This is based on `WebCore/platform/graphics/UnitBezier.h` in WebKit.
   8
   9 #![deny(missing_docs)]
  10
  11 use crate::values::CSSFloat;
  12
  13 const NEWTON_METHOD_ITERATIONS: u8 = 8;
  14
  15 /// A unit cubic Bézier curve, used for timing functions in CSS transitions and animations.
  16 pub struct Bezier {
  17     ax: f64,
  18     bx: f64,
  19     cx: f64,
  20     ay: f64,
  21     by: f64,
  22     cy: f64,
  23 }
  24
  25 impl Bezier {
  26     /// Calculate the output of a unit cubic Bézier curve from the two middle control points.
  27     ///
  28     /// X coordinate is time, Y coordinate is function advancement.
  29     /// The nominal range for both is 0 to 1.
  30     ///
  31     /// The start and end points are always (0, 0) and (1, 1) so that a transition or animation
  32     /// starts at 0% and ends at 100%.
  33     pub fn calculate_bezier_output(
  34         progress: f64,
  35         epsilon: f64,
  36         x1: f32,
  37         y1: f32,
  38         x2: f32,
  39         y2: f32,
  40     ) -> f64 {
  41         // Check for a linear curve.
  42         if x1 == y1 && x2 == y2 {
  43             return progress;
  44         }
  45
  46         // Ensure that we return 0 or 1 on both edges.
  47         if progress == 0.0 {
  48             return 0.0;
  49         }
  50         if progress == 1.0 {
  51             return 1.0;
  52         }
  53
  54         // For negative values, try to extrapolate with tangent (p1 - p0) or,
  55         // if p1 is coincident with p0, with (p2 - p0).
  56         if progress < 0.0 {
  57             if x1 > 0.0 {
  58                 return progress * y1 as f64 / x1 as f64;
  59             }
  60             if y1 == 0.0 && x2 > 0.0 {
  61                 return progress * y2 as f64 / x2 as f64;
  62             }
  63             // If we can't calculate a sensible tangent, don't extrapolate at all.
  64             return 0.0;
  65         }
  66
  67         // For values greater than 1, try to extrapolate with tangent (p2 - p3) or,
  68         // if p2 is coincident with p3, with (p1 - p3).
  69         if progress > 1.0 {
  70             if x2 < 1.0 {
  71                 return 1.0 + (progress - 1.0) * (y2 as f64 - 1.0) / (x2 as f64 - 1.0);
  72             }
  73             if y2 == 1.0 && x1 < 1.0 {
  74                 return 1.0 + (progress - 1.0) * (y1 as f64 - 1.0) / (x1 as f64 - 1.0);
  75             }
  76             // If we can't calculate a sensible tangent, don't extrapolate at all.
  77             return 1.0;
  78         }
  79
  80         Bezier::new(x1, y1, x2, y2).solve(progress, epsilon)
  81     }
  82
  83     #[inline]
  84     fn new(x1: CSSFloat, y1: CSSFloat, x2: CSSFloat, y2: CSSFloat) -> Bezier {
  85         let cx = 3. * x1 as f64;
  86         let bx = 3. * (x2 as f64 - x1 as f64) - cx;
  87
  88         let cy = 3. * y1 as f64;
  89         let by = 3. * (y2 as f64 - y1 as f64) - cy;
  90
  91         Bezier {
  92             ax: 1.0 - cx - bx,
  93             bx: bx,
  94             cx: cx,
  95             ay: 1.0 - cy - by,
  96             by: by,
  97             cy: cy,
  98         }
  99     }
 100
 101     #[inline]
 102     fn sample_curve_x(&self, t: f64) -> f64 {
 103         // ax * t^3 + bx * t^2 + cx * t
 104         ((self.ax * t + self.bx) * t + self.cx) * t
 105     }
 106
 107     #[inline]
 108     fn sample_curve_y(&self, t: f64) -> f64 {
 109         ((self.ay * t + self.by) * t + self.cy) * t
 110     }
 111
 112     #[inline]
 113     fn sample_curve_derivative_x(&self, t: f64) -> f64 {
 114         (3.0 * self.ax * t + 2.0 * self.bx) * t + self.cx
 115     }
 116
 117     #[inline]
 118     fn solve_curve_x(&self, x: f64, epsilon: f64) -> f64 {
 119         // Fast path: Use Newton's method.
 120         let mut t = x;
 121         for _ in 0..NEWTON_METHOD_ITERATIONS {
 122             let x2 = self.sample_curve_x(t);
 123             if x2.approx_eq(x, epsilon) {
 124                 return t;
 125             }
 126             let dx = self.sample_curve_derivative_x(t);
 127             if dx.approx_eq(0.0, 1e-6) {
 128                 break;
 129             }
 130             t -= (x2 - x) / dx;
 131         }
 132
 133         // Slow path: Use bisection.
 134         let (mut lo, mut hi, mut t) = (0.0, 1.0, x);
 135
 136         if t < lo {
 137             return lo;
 138         }
 139         if t > hi {
 140             return hi;
 141         }
 142
 143         while lo < hi {
 144             let x2 = self.sample_curve_x(t);
 145             if x2.approx_eq(x, epsilon) {
 146                 return t;
 147             }
 148             if x > x2 {
 149                 lo = t
 150             } else {
 151                 hi = t
 152             }
 153             t = (hi - lo) / 2.0 + lo
 154         }
 155
 156         t
 157     }
 158
 159     /// Solve the bezier curve for a given `x` and an `epsilon`, that should be
 160     /// between zero and one.
 161     #[inline]
 162     fn solve(&self, x: f64, epsilon: f64) -> f64 {
 163         self.sample_curve_y(self.solve_curve_x(x, epsilon))
 164     }
 165 }
 166
 167 trait ApproxEq {
 168     fn approx_eq(self, value: Self, epsilon: Self) -> bool;
 169 }
 170
 171 impl ApproxEq for f64 {
 172     #[inline]
 173     fn approx_eq(self, value: f64, epsilon: f64) -> bool {
 174         (self - value).abs() < epsilon
 175     }
 176 }