UI GFX Geometry: Make UnitBezier a wrapper for gfx::CubicBezier

ui/gfx/geometry/cubic_bezier.cc

Index: ui/gfx/geometry/cubic_bezier.cc
diff --git a/ui/gfx/geometry/cubic_bezier.cc b/ui/gfx/geometry/cubic_bezier.cc
index fe6dfcc7ff1af6c44033845df6dadf3232dff1db..55ad4001b758e339e6dd7a560ff01b9b6f897e06 100644
--- a/ui/gfx/geometry/cubic_bezier.cc
+++ b/ui/gfx/geometry/cubic_bezier.cc
@@ -11,129 +11,91 @@
 
 namespace gfx {
 
-namespace {
-
 static const double kBezierEpsilon = 1e-7;
-static const int MAX_STEPS = 30;
-
-static double eval_bezier(double p1, double p2, double t) {
-  const double p1_times_3 = 3.0 * p1;
-  const double p2_times_3 = 3.0 * p2;
-  const double h3 = p1_times_3;
-  const double h1 = p1_times_3 - p2_times_3 + 1.0;
-  const double h2 = p2_times_3 - 6.0 * p1;
-  return t * (t * (t * h1 + h2) + h3);
-}
 
-static double eval_bezier_derivative(double p1, double p2, double t) {
-  const double h1 = 9.0 * p1 - 9.0 * p2 + 3.0;
-  const double h2 = 6.0 * p2 - 12.0 * p1;
-  const double h3 = 3.0 * p1;
-  return t * (t * h1 + h2) + h3;
+CubicBezier::CubicBezier(double p1x, double p1y, double p2x, double p2y) {
+  InitCoefficients(p1x, p1y, p2x, p2y);
+  InitGradients(p1x, p1y, p2x, p2y);
+  InitRange(p1y, p2y);
 }
 
-// Finds t such that eval_bezier(x1, x2, t) = x.
-// There is a unique solution if x1 and x2 lie within (0, 1).
-static double bezier_interp(double x1,
-                            double x2,
-                            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);
-
-  // 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 (std::abs(error) < kBezierEpsilon)
-      break;
-    t += error > 0.0 ? -step : step;
-  }
-
-  // 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(kBezierEpsilon, std::abs(eval_bezier(x1, x2, t) - x));
-
-  return t;
+void CubicBezier::InitCoefficients(double p1x,
+                                   double p1y,
+                                   double p2x,
+                                   double p2y) {
+  // Calculate the polynomial coefficients, implicit first and last control
+  // points are (0,0) and (1,1).
+  cx_ = 3.0 * p1x;
+  bx_ = 3.0 * (p2x - p1x) - cx_;
+  ax_ = 1.0 - cx_ - bx_;
+
+  cy_ = 3.0 * p1y;
+  by_ = 3.0 * (p2y - p1y) - cy_;
+  ay_ = 1.0 - cy_ - by_;
 }
 
-}  // namespace
-
-CubicBezier::CubicBezier(double x1, double y1, double x2, double y2)
-    : x1_(x1),
-      y1_(y1),
-      x2_(x2),
-      y2_(y2) {
-  InitGradients();
-}
-
-CubicBezier::~CubicBezier() {
-}
-
-void CubicBezier::InitGradients() {
-  if (x1_ > 0)
-    start_gradient_ = y1_ / x1_;
-  else if (!y1_ && x2_ > 0)
-    start_gradient_ = y2_ / x2_;
+void CubicBezier::InitGradients(double p1x,
+                                double p1y,
+                                double p2x,
+                                double p2y) {
+  // End-point gradients are used to calculate timing function results
+  // outside the range [0, 1].
+  //
+  // There are three possibilities for the gradient at each end:
+  // (1) the closest control point is not horizontally coincident with regard to
+  //     (0, 0) or (1, 1). In this case the line between the end point and
+  //     the control point is tangent to the bezier at the end point.
+  // (2) the closest control point is coincident with the end point. In
+  //     this case the line between the end point and the far control
+  //     point is tangent to the bezier at the end point.
+  // (3) the closest control point is horizontally coincident with the end
+  //     point, but vertically distinct. In this case the gradient at the
+  //     end point is Infinite. However, this causes issues when
+  //     interpolating. As a result, we break down to a simple case of
+  //     0 gradient under these conditions.
+
+  if (p1x > 0)
+    start_gradient_ = p1y / p1x;
+  else if (!p1y && p2x > 0)
+    start_gradient_ = p2y / p2x;
   else
     start_gradient_ = 0;
 
-  if (x2_ < 1)
-    end_gradient_ = (y2_ - 1) / (x2_ - 1);
-  else if (x2_ == 1 && x1_ < 1)
-    end_gradient_ = (y1_ - 1) / (x1_ - 1);
+  if (p2x < 1)
+    end_gradient_ = (p2y - 1) / (p2x - 1);
+  else if (p2x == 1 && p1x < 1)
+    end_gradient_ = (p1y - 1) / (p1x - 1);
   else
     end_gradient_ = 0;
 }
 
-double CubicBezier::Solve(double x) const {
-  if (x < 0)
-    return start_gradient_ * x;
-  if (x > 1)
-    return 1.0 + end_gradient_ * (x - 1.0);
-
-  return eval_bezier(y1_, y2_, bezier_interp(x1_, x2_, x));
-}
-
-double CubicBezier::Slope(double x) const {
-  double t = bezier_interp(x1_, x2_, x);
-  double dx_dt = eval_bezier_derivative(x1_, x2_, t);
-  double dy_dt = eval_bezier_derivative(y1_, y2_, t);
-  return dy_dt / dx_dt;
-}
-
-void CubicBezier::Range(double* min, double* max) const {
-  *min = 0;
-  *max = 1;
-  if (0 <= y1_ && y1_ < 1 && 0 <= y2_ && y2_ <= 1)
+void CubicBezier::InitRange(double p1y, double p2y) {
+  range_min_ = 0;
+  range_max_ = 1;
+  if (0 <= p1y && p1y < 1 && 0 <= p2y && p2y <= 1)
     return;
 
-  // Represent the function's derivative in the form at^2 + bt + c.
+  const double epsilon = kBezierEpsilon;
+
+  // Represent the function's derivative in the form at^2 + bt + c
+  // as in sampleCurveDerivativeY.
   // (Technically this is (dy/dt)*(1/3), which is suitable for finding zeros
   // but does not actually give the slope of the curve.)
-  double a = 3 * (y1_ - y2_) + 1;
-  double b = 2 * (y2_ - 2 * y1_);
-  double c = y1_;
+  const double a = 3.0 * ay_;
+  const double b = 2.0 * by_;
+  const double c = cy_;
 
   // Check if the derivative is constant.
-  if (std::abs(a) < kBezierEpsilon &&
-      std::abs(b) < kBezierEpsilon)
+  if (std::abs(a) < epsilon && std::abs(b) < epsilon)
     return;
 
   // Zeros of the function's derivative.
-  double t_1 = 0;
-  double t_2 = 0;
+  double t1 = 0;
+  double t2 = 0;
 
-  if (std::abs(a) < kBezierEpsilon) {
+  if (std::abs(a) < epsilon) {
     // The function's derivative is linear.
-    t_1 = -c / b;
+    t1 = -c / b;
   } else {
     // The function's derivative is a quadratic. We find the zeros of this
     // quadratic using the quadratic formula.
@@ -141,21 +103,79 @@ void CubicBezier::Range(double* min, double* max) const {
     if (discriminant < 0)
       return;
     double discriminant_sqrt = sqrt(discriminant);
-    t_1 = (-b + discriminant_sqrt) / (2 * a);
-    t_2 = (-b - discriminant_sqrt) / (2 * a);
+    t1 = (-b + discriminant_sqrt) / (2 * a);
+    t2 = (-b - discriminant_sqrt) / (2 * a);
+  }
+
+  double sol1 = 0;
+  double sol2 = 0;
+
+  if (0 < t1 && t1 < 1)
+    sol1 = SampleCurveY(t1);
+
+  if (0 < t2 && t2 < 1)
+    sol2 = SampleCurveY(t2);
+
+  range_min_ = std::min(std::min(range_min_, sol1), sol2);
+  range_max_ = std::max(std::max(range_max_, sol1), sol2);
+}
+
+double CubicBezier::SolveCurveX(double x, double epsilon) const {
+  DCHECK_GE(x, 0.0);
+  DCHECK_LE(x, 1.0);
+
+  double t0;
+  double t1;
+  double t2;
+  double x2;
+  double d2;
+  int i;
+
+  // First try a few iterations of Newton's method -- normally very fast.
+  for (t2 = x, i = 0; i < 8; i++) {
+    x2 = SampleCurveX(t2) - x;
+    if (fabs(x2) < epsilon)
+      return t2;
+    d2 = SampleCurveDerivativeX(t2);
+    if (fabs(d2) < 1e-6)
+      break;
+    t2 = t2 - x2 / d2;
   }
 
-  double sol_1 = 0;
-  double sol_2 = 0;
+  // Fall back to the bisection method for reliability.
+  t0 = 0.0;
+  t1 = 1.0;
+  t2 = x;
+
+  while (t0 < t1) {
+    x2 = SampleCurveX(t2);
+    if (fabs(x2 - x) < epsilon)
+      return t2;
+    if (x > x2)
+      t0 = t2;
+    else
+      t1 = t2;
+    t2 = (t1 - t0) * .5 + t0;
+  }
 
-  if (0 < t_1 && t_1 < 1)
-    sol_1 = eval_bezier(y1_, y2_, t_1);
+  // Failure.
+  return t2;
+}
 
-  if (0 < t_2 && t_2 < 1)
-    sol_2 = eval_bezier(y1_, y2_, t_2);
+double CubicBezier::Solve(double x) const {
+  return SolveWithEpsilon(x, kBezierEpsilon);
+}
 
-  *min = std::min(std::min(*min, sol_1), sol_2);
-  *max = std::max(std::max(*max, sol_1), sol_2);
+double CubicBezier::SlopeWithEpsilon(double x, double epsilon) const {
+  x = std::min(std::max(x, 0.0), 1.0);
+  double t = SolveCurveX(x, epsilon);
+  double dx = SampleCurveDerivativeX(t);
+  double dy = SampleCurveDerivativeY(t);
+  return dy / dx;
+}
+
+double CubicBezier::Slope(double x) const {
+  return SlopeWithEpsilon(x, kBezierEpsilon);
 }
 
 }  // namespace gfx