src/third_party/WebKit/Source/platform/animation/UnitBezier.h

   1 /*
   2  * Copyright (C) 2008 Apple Inc. All Rights Reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef UnitBezier_h
  27 #define UnitBezier_h
  28
  29 #include "platform/PlatformExport.h"
  30 #include "wtf/Assertions.h"
  31 #include <math.h>
  32
  33 namespace WebCore {
  34
  35 struct UnitBezier {
  36     UnitBezier(double p1x, double p1y, double p2x, double p2y)
  37     {
  38         // Calculate the polynomial coefficients, implicit first and last control points are (0,0) and (1,1).
  39         cx = 3.0 * p1x;
  40         bx = 3.0 * (p2x - p1x) - cx;
  41         ax = 1.0 - cx -bx;
  42
  43         cy = 3.0 * p1y;
  44         by = 3.0 * (p2y - p1y) - cy;
  45         ay = 1.0 - cy - by;
  46
  47         // End-point gradients are used to calculate timing function results
  48         // outside the range [0, 1].
  49         //
  50         // There are three possibilities for the gradient at each end:
  51         // (1) the closest control point is not horizontally coincident with regard to
  52         //     (0, 0) or (1, 1). In this case the line between the end point and
  53         //     the control point is tangent to the bezier at the end point.
  54         // (2) the closest control point is coincident with the end point. In
  55         //     this case the line between the end point and the far control
  56         //     point is tangent to the bezier at the end point.
  57         // (3) the closest control point is horizontally coincident with the end
  58         //     point, but vertically distinct. In this case the gradient at the
  59         //     end point is Infinite. However, this causes issues when
  60         //     interpolating. As a result, we break down to a simple case of
  61         //     0 gradient under these conditions.
  62
  63         if (p1x > 0)
  64             m_startGradient = p1y / p1x;
  65         else if (!p1y && p2x > 0)
  66             m_startGradient = p2y / p2x;
  67         else
  68             m_startGradient = 0;
  69
  70         if (p2x < 1)
  71             m_endGradient = (p2y - 1) / (p2x - 1);
  72         else if (p2x == 1 && p1x < 1)
  73             m_endGradient = (p1y - 1) / (p1x - 1);
  74         else
  75             m_endGradient = 0;
  76     }
  77
  78     double sampleCurveX(double t)
  79     {
  80         // `ax t^3 + bx t^2 + cx t' expanded using Horner's rule.
  81         return ((ax * t + bx) * t + cx) * t;
  82     }
  83
  84     double sampleCurveY(double t)
  85     {
  86         return ((ay * t + by) * t + cy) * t;
  87     }
  88
  89     double sampleCurveDerivativeX(double t)
  90     {
  91         return (3.0 * ax * t + 2.0 * bx) * t + cx;
  92     }
  93
  94     // Given an x value, find a parametric value it came from.
  95     double solveCurveX(double x, double epsilon)
  96     {
  97         ASSERT(x >= 0.0);
  98         ASSERT(x <= 1.0);
  99
 100         double t0;
 101         double t1;
 102         double t2;
 103         double x2;
 104         double d2;
 105         int i;
 106
 107         // First try a few iterations of Newton's method -- normally very fast.
 108         for (t2 = x, i = 0; i < 8; i++) {
 109             x2 = sampleCurveX(t2) - x;
 110             if (fabs (x2) < epsilon)
 111                 return t2;
 112             d2 = sampleCurveDerivativeX(t2);
 113             if (fabs(d2) < 1e-6)
 114                 break;
 115             t2 = t2 - x2 / d2;
 116         }
 117
 118         // Fall back to the bisection method for reliability.
 119         t0 = 0.0;
 120         t1 = 1.0;
 121         t2 = x;
 122
 123         while (t0 < t1) {
 124             x2 = sampleCurveX(t2);
 125             if (fabs(x2 - x) < epsilon)
 126                 return t2;
 127             if (x > x2)
 128                 t0 = t2;
 129             else
 130                 t1 = t2;
 131             t2 = (t1 - t0) * .5 + t0;
 132         }
 133
 134         // Failure.
 135         return t2;
 136     }
 137
 138     // Evaluates y at the given x. The epsilon parameter provides a hint as to the required
 139     // accuracy and is not guaranteed.
 140     double solve(double x, double epsilon)
 141     {
 142         if (x < 0.0)
 143             return 0.0 + m_startGradient * x;
 144         if (x > 1.0)
 145             return 1.0 + m_endGradient * (x - 1.0);
 146         return sampleCurveY(solveCurveX(x, epsilon));
 147     }
 148
 149 private:
 150     double ax;
 151     double bx;
 152     double cx;
 153
 154     double ay;
 155     double by;
 156     double cy;
 157
 158     double m_startGradient;
 159     double m_endGradient;
 160 };
 161
 162 } // namespace WebCore
 163
 164 #endif // UnitBezier_h