ui/gfx/geometry/cubic_bezier.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "ui/gfx/geometry/cubic_bezier.h"
   6
   7 #include <algorithm>
   8 #include <cmath>
   9
  10 #include "base/logging.h"
  11
  12 namespace gfx {
  13
  14 namespace {
  15
  16 static const double kBezierEpsilon = 1e-7;
  17 static const int MAX_STEPS = 30;
  18
  19 static double eval_bezier(double p1, double p2, double t) {
  20   const double p1_times_3 = 3.0 * p1;
  21   const double p2_times_3 = 3.0 * p2;
  22   const double h3 = p1_times_3;
  23   const double h1 = p1_times_3 - p2_times_3 + 1.0;
  24   const double h2 = p2_times_3 - 6.0 * p1;
  25   return t * (t * (t * h1 + h2) + h3);
  26 }
  27
  28 static double eval_bezier_derivative(double p1, double p2, double t) {
  29   const double h1 = 9.0 * p1 - 9.0 * p2 + 3.0;
  30   const double h2 = 6.0 * p2 - 12.0 * p1;
  31   const double h3 = 3.0 * p1;
  32   return t * (t * h1 + h2) + h3;
  33 }
  34
  35 // Finds t such that eval_bezier(x1, x2, t) = x.
  36 // There is a unique solution if x1 and x2 lie within (0, 1).
  37 static double bezier_interp(double x1,
  38                             double x2,
  39                             double x) {
  40   DCHECK_GE(1.0, x1);
  41   DCHECK_LE(0.0, x1);
  42   DCHECK_GE(1.0, x2);
  43   DCHECK_LE(0.0, x2);
  44
  45   x1 = std::min(std::max(x1, 0.0), 1.0);
  46   x2 = std::min(std::max(x2, 0.0), 1.0);
  47   x = std::min(std::max(x, 0.0), 1.0);
  48
  49   // We're just going to do bisection for now (for simplicity), but we could
  50   // easily do some newton steps if this turns out to be a bottleneck.
  51   double t = 0.0;
  52   double step = 1.0;
  53   for (int i = 0; i < MAX_STEPS; ++i, step *= 0.5) {
  54     const double error = eval_bezier(x1, x2, t) - x;
  55     if (std::abs(error) < kBezierEpsilon)
  56       break;
  57     t += error > 0.0 ? -step : step;
  58   }
  59
  60   // We should have terminated the above loop because we got close to x, not
  61   // because we exceeded MAX_STEPS. Do a DCHECK here to confirm.
  62   DCHECK_GT(kBezierEpsilon, std::abs(eval_bezier(x1, x2, t) - x));
  63
  64   return t;
  65 }
  66
  67 }  // namespace
  68
  69 CubicBezier::CubicBezier(double x1, double y1, double x2, double y2)
  70     : x1_(x1),
  71       y1_(y1),
  72       x2_(x2),
  73       y2_(y2) {
  74   InitGradients();
  75 }
  76
  77 CubicBezier::~CubicBezier() {
  78 }
  79
  80 void CubicBezier::InitGradients() {
  81   if (x1_ > 0)
  82     start_gradient_ = y1_ / x1_;
  83   else if (!y1_ && x2_ > 0)
  84     start_gradient_ = y2_ / x2_;
  85   else
  86     start_gradient_ = 0;
  87
  88   if (x2_ < 1)
  89     end_gradient_ = (y2_ - 1) / (x2_ - 1);
  90   else if (x2_ == 1 && x1_ < 1)
  91     end_gradient_ = (y1_ - 1) / (x1_ - 1);
  92   else
  93     end_gradient_ = 0;
  94 }
  95
  96 double CubicBezier::Solve(double x) const {
  97   if (x < 0)
  98     return start_gradient_ * x;
  99   if (x > 1)
 100     return 1.0 + end_gradient_ * (x - 1.0);
 101
 102   return eval_bezier(y1_, y2_, bezier_interp(x1_, x2_, x));
 103 }
 104
 105 double CubicBezier::Slope(double x) const {
 106   double t = bezier_interp(x1_, x2_, x);
 107   double dx_dt = eval_bezier_derivative(x1_, x2_, t);
 108   double dy_dt = eval_bezier_derivative(y1_, y2_, t);
 109   return dy_dt / dx_dt;
 110 }
 111
 112 void CubicBezier::Range(double* min, double* max) const {
 113   *min = 0;
 114   *max = 1;
 115   if (0 <= y1_ && y1_ < 1 && 0 <= y2_ && y2_ <= 1)
 116     return;
 117
 118   // Represent the function's derivative in the form at^2 + bt + c.
 119   // (Technically this is (dy/dt)*(1/3), which is suitable for finding zeros
 120   // but does not actually give the slope of the curve.)
 121   double a = 3 * (y1_ - y2_) + 1;
 122   double b = 2 * (y2_ - 2 * y1_);
 123   double c = y1_;
 124
 125   // Check if the derivative is constant.
 126   if (std::abs(a) < kBezierEpsilon &&
 127       std::abs(b) < kBezierEpsilon)
 128     return;
 129
 130   // Zeros of the function's derivative.
 131   double t_1 = 0;
 132   double t_2 = 0;
 133
 134   if (std::abs(a) < kBezierEpsilon) {
 135     // The function's derivative is linear.
 136     t_1 = -c / b;
 137   } else {
 138     // The function's derivative is a quadratic. We find the zeros of this
 139     // quadratic using the quadratic formula.
 140     double discriminant = b * b - 4 * a * c;
 141     if (discriminant < 0)
 142       return;
 143     double discriminant_sqrt = sqrt(discriminant);
 144     t_1 = (-b + discriminant_sqrt) / (2 * a);
 145     t_2 = (-b - discriminant_sqrt) / (2 * a);
 146   }
 147
 148   double sol_1 = 0;
 149   double sol_2 = 0;
 150
 151   if (0 < t_1 && t_1 < 1)
 152     sol_1 = eval_bezier(y1_, y2_, t_1);
 153
 154   if (0 < t_2 && t_2 < 1)
 155     sol_2 = eval_bezier(y1_, y2_, t_2);
 156
 157   *min = std::min(std::min(*min, sol_1), sol_2);
 158   *max = std::max(std::max(*max, sol_1), sol_2);
 159 }
 160
 161 }  // namespace gfx