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

ui/gfx/geometry/cubic_bezier.h

Index: ui/gfx/geometry/cubic_bezier.h
diff --git a/ui/gfx/geometry/cubic_bezier.h b/ui/gfx/geometry/cubic_bezier.h
index 5a885f35db2f71e719184680ae4bbd2dcc8ec0d4..940ca524a0ddc6e398849c2cd6a988c024b2b6b7 100644
--- a/ui/gfx/geometry/cubic_bezier.h
+++ b/ui/gfx/geometry/cubic_bezier.h
@@ -5,6 +5,10 @@
 #ifndef UI_GFX_GEOMETRY_CUBIC_BEZIER_H_
 #define UI_GFX_GEOMETRY_CUBIC_BEZIER_H_
 
+#include <algorithm>
+#include <cmath>
+
+#include "base/logging.h"
 #include "base/macros.h"
 #include "ui/gfx/gfx_export.h"
 
@@ -12,30 +16,122 @@ namespace gfx {
 
 class GFX_EXPORT CubicBezier {
  public:
-  CubicBezier(double x1, double y1, double x2, double y2);
-  ~CubicBezier();
+  CubicBezier(double p1x, double p1y, double p2x, double p2y);
+
+  static double GetDefaultEpsilon();
+
+  double SampleCurveX(double t) const {
+    // `ax t^3 + bx t^2 + cx t' expanded using Horner's rule.
+    return ((ax * t + bx) * t + cx) * t;
+  }
+
+  double SampleCurveY(double t) const { return ((ay * t + by) * t + cy) * t; }
+
+  double SampleCurveDerivativeX(double t) const {
+    return (3.0 * ax * t + 2.0 * bx) * t + cx;
+  }
+
+  double SampleCurveDerivativeY(double t) const {
+    return (3.0 * ay * t + 2.0 * by) * t + cy;
+  }
+
+  // Given an x value, find a parametric value it came from.
+  double SolveCurveX(double x, double epsilon) const {

[danakj, 2016/04/01 01:35:58]

Put this in the .cc file.

[loyso (OOO), 2016/04/01 04:40:06]

Done.

+    DCHECK(x >= 0.0);

[danakj, 2016/04/01 01:35:58]

DCHECK_GE

[loyso (OOO), 2016/04/01 04:40:06]

Done.

+    DCHECK(x <= 1.0);
+
+    double t0;
+    double t1;
+    double t2;
+    double x2;
+    double d2;
+    int i;
 
-  // Returns an approximation of y at the given x.
-  double Solve(double x) const;
+    // 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;
+    }
+
+    // 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;
+    }
+
+    // Failure.
+    return t2;
+  }
+
+  // Evaluates y at the given x.
+  double Solve(double x) const {
+    return SolveWithEpsilon(x, GetDefaultEpsilon());
+  }
+
+  // Evaluates y at the given x. The epsilon parameter provides a hint as to the
+  // required
+  // accuracy and is not guaranteed.
+  double SolveWithEpsilon(double x, double epsilon) const {
+    if (x < 0.0)
+      return 0.0 + start_gradient_ * x;
+    if (x > 1.0)
+      return 1.0 + end_gradient_ * (x - 1.0);
+    return SampleCurveY(SolveCurveX(x, epsilon));
+  }
 
   // Returns an approximation of dy/dx at the given x.
-  double Slope(double x) const;
+  double Slope(double x) const {
+    return SlopeWithEpsilon(x, GetDefaultEpsilon());
+  }
+
+  double SlopeWithEpsilon(double x, double epsilon) const {
+    double t = SolveCurveX(x, epsilon);
+    double dx = SampleCurveDerivativeX(t);
+    double dy = SampleCurveDerivativeY(t);
+    return dy / dx;
+  }
 
   // Sets |min| and |max| to the bezier's minimum and maximium y values in the
   // interval [0, 1].
-  void Range(double* min, double* max) const;
+  void Range(double* min, double* max) const {

[danakj, 2016/04/01 01:35:58]

Just make 2 getters, minimum() and maximum()?

[loyso (OOO), 2016/04/01 02:58:03]

It would affect the call sites. Can we change the API in a separate CL?

[danakj, 2016/04/01 19:26:17]

Sure yep. Put a TODO?

[danakj, 2016/04/01 19:54:33]

Or, make the blink wrapper use the min/max accessors, with the TODO over there.

[loyso (OOO), 2016/04/04 03:39:58]

Done. It's CC-only for now.

+    *min = range_min_;
+    *max = range_max_;
+  }
 
  private:
-  void InitGradients();
+  void InitCoefficients(double p1x, double p1y, double p2x, double p2y);
+  void InitGradients(double p1x, double p1y, double p2x, double p2y);
+  void InitRange(double p1y, double p2y);
 
-  double x1_;
-  double y1_;
-  double x2_;
-  double y2_;
+  double ax;
+  double bx;
+  double cx;
+
+  double ay;
+  double by;
+  double cy;
 
   double start_gradient_;
   double end_gradient_;
 
+  double range_min_;
+  double range_max_;
+
   DISALLOW_ASSIGN(CubicBezier);
 };