1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

//! Parametric Bézier curves.
//!
//! This is based on `WebCore/platform/graphics/UnitBezier.h` in WebKit.

#![deny(missing_docs)]

use values::CSSFloat;

const NEWTON_METHOD_ITERATIONS: u8 = 8;

/// A unit cubic Bézier curve, used for timing functions in CSS transitions and animations.
pub struct Bezier {
    ax: f64,
    bx: f64,
    cx: f64,
    ay: f64,
    by: f64,
    cy: f64,
}

impl Bezier {
    /// Create a unit cubic Bézier curve from the two middle control points.
    ///
    /// X coordinate is time, Y coordinate is function advancement.
    /// The nominal range for both is 0 to 1.
    ///
    /// The start and end points are always (0, 0) and (1, 1) so that a transition or animation
    /// starts at 0% and ends at 100%.
    #[inline]
    pub fn new(x1: CSSFloat, y1: CSSFloat, x2: CSSFloat, y2: CSSFloat) -> Bezier {
        let cx = 3. * x1 as f64;
        let bx = 3. * (x2 as f64 - x1 as f64) - cx;

        let cy = 3. * y1 as f64;
        let by = 3. * (y2 as f64 - y1 as f64) - cy;

        Bezier {
            ax: 1.0 - cx - bx,
            bx: bx,
            cx: cx,
            ay: 1.0 - cy - by,
            by: by,
            cy: cy,
        }
    }

    #[inline]
    fn sample_curve_x(&self, t: f64) -> f64 {
        // ax * t^3 + bx * t^2 + cx * t
        ((self.ax * t + self.bx) * t + self.cx) * t
    }

    #[inline]
    fn sample_curve_y(&self, t: f64) -> f64 {
        ((self.ay * t + self.by) * t + self.cy) * t
    }

    #[inline]
    fn sample_curve_derivative_x(&self, t: f64) -> f64 {
        (3.0 * self.ax * t + 2.0 * self.bx) * t + self.cx
    }

    #[inline]
    fn solve_curve_x(&self, x: f64, epsilon: f64) -> f64 {
        // Fast path: Use Newton's method.
        let mut t = x;
        for _ in 0..NEWTON_METHOD_ITERATIONS {
            let x2 = self.sample_curve_x(t);
            if x2.approx_eq(x, epsilon) {
                return t
            }
            let dx = self.sample_curve_derivative_x(t);
            if dx.approx_eq(0.0, 1e-6) {
                break
            }
            t -= (x2 - x) / dx;
        }

        // Slow path: Use bisection.
        let (mut lo, mut hi, mut t) = (0.0, 1.0, x);

        if t < lo {
            return lo
        }
        if t > hi {
            return hi
        }

        while lo < hi {
            let x2 = self.sample_curve_x(t);
            if x2.approx_eq(x, epsilon) {
                return t
            }
            if x > x2 {
                lo = t
            } else {
                hi = t
            }
            t = (hi - lo) / 2.0 + lo
        }

        t
    }

    /// Solve the bezier curve for a given `x` and an `epsilon`, that should be
    /// between zero and one.
    #[inline]
    pub fn solve(&self, x: f64, epsilon: f64) -> f64 {
        self.sample_curve_y(self.solve_curve_x(x, epsilon))
    }
}

trait ApproxEq {
    fn approx_eq(self, value: Self, epsilon: Self) -> bool;
}

impl ApproxEq for f64 {
    #[inline]
    fn approx_eq(self, value: f64, epsilon: f64) -> bool {
        (self - value).abs() < epsilon
    }
}