Do not clamp y values on internal knots of timing function bezier curves

Cubic bezier timing functions are based on two knots (x1, y1) and (x2, y2) (the
other knots are assumed to be (0, 0) and (1, 1)). We require that x1, x2 lie
within (0, 1) (so that the bezier does not 'fold back' on itself), but y1, and
y2 should have no such constraint. They currently do. This CL reimplements
bezier interpolation without this restriction. This interpolation has two steps:
   1) Find the t corresponding to the desired x.
   2) Interpolate y's at the t computed in step 1.
Step 1 is an iterative minimization. Here I do bisection for simplicity, but I
could take Newton steps if this turns out to be a bottleneck.

R=ajuma@chromium.org
BUG=178070

Review URL: https://chromiumcodereview.appspot.com/16112002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@202755 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 83 insertions, 78 deletions

diff --git a/cc/animation/timing_function.cc b/cc/animation/timing_function.cc
index 769e9f0..f5a4f9f 100644
--- a/cc/animation/timing_function.cc
+++ b/cc/animation/timing_function.cc
@@ -2,84 +2,66 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include <algorithm>
+
+#include "base/logging.h"
 #include "cc/animation/timing_function.h"
 
-#include "third_party/skia/include/core/SkMath.h"
+namespace cc {
 
-// TODO(danakj) These methods come from SkInterpolator.cpp. When such a method
-// is available in the public Skia API, we should switch to using that.
-// http://crbug.com/159735
 namespace {
 
-// Dot14 has 14 bits for decimal places, and the remainder for whole numbers.
-typedef int Dot14;
-#define DOT14_ONE (1 << 14)
-#define DOT14_HALF (1 << 13)
+static const double BEZIER_EPSILON = 1e-7;
+static const int MAX_STEPS = 30;
 
-static inline Dot14 Dot14Mul(Dot14 a, Dot14 b) {
-  return (a * b + DOT14_HALF) >> 14;
+static double eval_bezier(double x1, double x2, double t) {
+  const double x1_times_3 = 3.0 * x1;
+  const double x2_times_3 = 3.0 * x2;
+  const double h3 = x1_times_3;
+  const double h1 = x1_times_3 - x2_times_3 + 1.0;
+  const double h2 = x2_times_3 - 6.0 * x1;
+  return t * (t * (t * h1 + h2) + h3);
 }
 
-static inline Dot14 EvalCubic(Dot14 t, Dot14 A, Dot14 B, Dot14 C) {
-  return Dot14Mul(Dot14Mul(Dot14Mul(C, t) + B, t) + A, t);
-}
-
-static inline Dot14 PinAndConvert(SkScalar x) {
-  if (x <= 0)
-    return 0;
-  if (x >= SK_Scalar1)
-    return DOT14_ONE;
-  return SkScalarToFixed(x) >> 2;
-}
-
-SkScalar SkUnitCubicInterp(SkScalar bx,
-                           SkScalar by,
-                           SkScalar cx,
-                           SkScalar cy,
-                           SkScalar value) {
-  Dot14 x = PinAndConvert(value);
-
-  if (x == 0)
-    return 0;
-  if (x == DOT14_ONE)
-    return SK_Scalar1;
-
-  Dot14 b = PinAndConvert(bx);
-  Dot14 c = PinAndConvert(cx);
-
-  // Now compute our coefficients from the control points.
-  //  t   -> 3b
-  //  t^2 -> 3c - 6b
-  //  t^3 -> 3b - 3c + 1
-  Dot14 A = 3 * b;
-  Dot14 B = 3 * (c - 2 * b);
-  Dot14 C = 3 * (b - c) + DOT14_ONE;
-
-  // Now search for a t value given x.
-  Dot14 t = DOT14_HALF;
-  Dot14 dt = DOT14_HALF;
-  for (int i = 0; i < 13; i++) {
-    dt >>= 1;
-    Dot14 guess = EvalCubic(t, A, B, C);
-    if (x < guess)
-      t -= dt;
-    else
-      t += dt;
+static double bezier_interp(double x1,
+                            double y1,
+                            double x2,
+                            double y2,
+                            double x) {
+  DCHECK_GE(1.0, x1);
+  DCHECK_LE(0.0, x1);
+  DCHECK_GE(1.0, x2);
+  DCHECK_LE(0.0, x2);
+
+  x1 = std::min(std::max(x1, 0.0), 1.0);
+  x2 = std::min(std::max(x2, 0.0), 1.0);
+  x = std::min(std::max(x, 0.0), 1.0);
+
+  // Step 1. Find the t corresponding to the given x. I.e., we want t such that
+  // eval_bezier(x1, x2, t) = x. There is a unique solution if x1 and x2 lie
+  // within (0, 1).
+  //
+  // We're just going to do bisection for now (for simplicity), but we could
+  // easily do some newton steps if this turns out to be a bottleneck.
+  double t = 0.0;
+  double step = 1.0;
+  for (int i = 0; i < MAX_STEPS; ++i, step *= 0.5) {
+    const double error = eval_bezier(x1, x2, t) - x;
+    if (fabs(error) < BEZIER_EPSILON)
+      break;
+    t += error > 0.0 ? -step : step;
   }
 
-  // Now we have t, so compute the coefficient for Y and evaluate.
-  b = PinAndConvert(by);
-  c = PinAndConvert(cy);
-  A = 3 * b;
-  B = 3 * (c - 2 * b);
-  C = 3 * (b - c) + DOT14_ONE;
-  return SkFixedToScalar(EvalCubic(t, A, B, C) << 2);
+  // We should have terminated the above loop because we got close to x, not
+  // because we exceeded MAX_STEPS. Do a DCHECK here to confirm.
+  DCHECK_GT(BEZIER_EPSILON, fabs(eval_bezier(x1, x2, t) - x));
+
+  // Step 2. Return the interpolated y values at the t we computed above.
+  return eval_bezier(y1, y2, t);
 }
 
 }  // namespace
 
-namespace cc {
-
 TimingFunction::TimingFunction() {}
 
 TimingFunction::~TimingFunction() {}
@@ -89,10 +71,7 @@ double TimingFunction::Duration() const {
 }
 
 scoped_ptr<CubicBezierTimingFunction> CubicBezierTimingFunction::Create(
-    double x1,
-    double y1,
-    double x2,
-    double y2) {
+    double x1, double y1, double x2, double y2) {
   return make_scoped_ptr(new CubicBezierTimingFunction(x1, y1, x2, y2));
 }
 
@@ -100,16 +79,12 @@ CubicBezierTimingFunction::CubicBezierTimingFunction(double x1,
                                                      double y1,
                                                      double x2,
                                                      double y2)
-    : x1_(SkDoubleToScalar(x1)),
-      y1_(SkDoubleToScalar(y1)),
-      x2_(SkDoubleToScalar(x2)),
-      y2_(SkDoubleToScalar(y2)) {}
+    : x1_(x1), y1_(y1), x2_(x2), y2_(y2) {}
 
 CubicBezierTimingFunction::~CubicBezierTimingFunction() {}
 
 float CubicBezierTimingFunction::GetValue(double x) const {
-  SkScalar value = SkUnitCubicInterp(x1_, y1_, x2_, y2_, x);
-  return SkScalarToFloat(value);
+  return static_cast<float>(bezier_interp(x1_, y1_, x2_, y2_, x));
 }
 
 scoped_ptr<AnimationCurve> CubicBezierTimingFunction::Clone() const {
diff --git a/cc/animation/timing_function.h b/cc/animation/timing_function.h
index b1080e6..3aa2f25 100644
--- a/cc/animation/timing_function.h
+++ b/cc/animation/timing_function.h
@@ -39,10 +39,10 @@ class CC_EXPORT CubicBezierTimingFunction : public TimingFunction {
  protected:
   CubicBezierTimingFunction(double x1, double y1, double x2, double y2);
 
-  SkScalar x1_;
-  SkScalar y1_;
-  SkScalar x2_;
-  SkScalar y2_;
+  double x1_;
+  double y1_;
+  double x2_;
+  double y2_;
 
  private:
   DISALLOW_ASSIGN(CubicBezierTimingFunction);
diff --git a/cc/animation/timing_function_unittest.cc b/cc/animation/timing_function_unittest.cc
index c076d52..2caa12d 100644
--- a/cc/animation/timing_function_unittest.cc
+++ b/cc/animation/timing_function_unittest.cc
@@ -37,5 +37,35 @@ TEST(TimingFunctionTest, CubicBezierTimingFunction) {
   EXPECT_NEAR(function->GetValue(1), 1, epsilon);
 }
 
+// Tests that the bezier timing function works with knots with y not in (0, 1).
+TEST(TimingFunctionTest, CubicBezierTimingFunctionUnclampedYValues) {
+  scoped_ptr<CubicBezierTimingFunction> function =
+      CubicBezierTimingFunction::Create(0.5, -1.0, 0.5, 2.0);
+
+  double epsilon = 0.00015;
+
+  EXPECT_NEAR(function->GetValue(0.0), 0.0, epsilon);
+  EXPECT_NEAR(function->GetValue(0.05), -0.08954, epsilon);
+  EXPECT_NEAR(function->GetValue(0.1), -0.15613, epsilon);
+  EXPECT_NEAR(function->GetValue(0.15), -0.19641, epsilon);
+  EXPECT_NEAR(function->GetValue(0.2), -0.20651, epsilon);
+  EXPECT_NEAR(function->GetValue(0.25), -0.18232, epsilon);
+  EXPECT_NEAR(function->GetValue(0.3), -0.11992, epsilon);
+  EXPECT_NEAR(function->GetValue(0.35), -0.01672, epsilon);
+  EXPECT_NEAR(function->GetValue(0.4), 0.12660, epsilon);
+  EXPECT_NEAR(function->GetValue(0.45), 0.30349, epsilon);
+  EXPECT_NEAR(function->GetValue(0.5), 0.50000, epsilon);
+  EXPECT_NEAR(function->GetValue(0.55), 0.69651, epsilon);
+  EXPECT_NEAR(function->GetValue(0.6), 0.87340, epsilon);
+  EXPECT_NEAR(function->GetValue(0.65), 1.01672, epsilon);
+  EXPECT_NEAR(function->GetValue(0.7), 1.11992, epsilon);
+  EXPECT_NEAR(function->GetValue(0.75), 1.18232, epsilon);
+  EXPECT_NEAR(function->GetValue(0.8), 1.20651, epsilon);
+  EXPECT_NEAR(function->GetValue(0.85), 1.19641, epsilon);
+  EXPECT_NEAR(function->GetValue(0.9), 1.15613, epsilon);
+  EXPECT_NEAR(function->GetValue(0.95), 1.08954, epsilon);
+  EXPECT_NEAR(function->GetValue(1.0), 1.0, epsilon);
+}
+
 }  // namespace
 }  // namespace cc