src/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 }
  75
  76 CubicBezier::~CubicBezier() {
  77 }
  78
  79 double CubicBezier::Solve(double x) const {
  80   return eval_bezier(y1_, y2_, bezier_interp(x1_, x2_, x));
  81 }
  82
  83 double CubicBezier::Slope(double x) const {
  84   double t = bezier_interp(x1_, x2_, x);
  85   double dx_dt = eval_bezier_derivative(x1_, x2_, t);
  86   double dy_dt = eval_bezier_derivative(y1_, y2_, t);
  87   return dy_dt / dx_dt;
  88 }
  89
  90 void CubicBezier::Range(double* min, double* max) const {
  91   *min = 0;
  92   *max = 1;
  93   if (0 <= y1_ && y1_ < 1 && 0 <= y2_ && y2_ <= 1)
  94     return;
  95
  96   // Represent the function's derivative in the form at^2 + bt + c.
  97   // (Technically this is (dy/dt)*(1/3), which is suitable for finding zeros
  98   // but does not actually give the slope of the curve.)
  99   double a = 3 * (y1_ - y2_) + 1;
 100   double b = 2 * (y2_ - 2 * y1_);
 101   double c = y1_;
 102
 103   // Check if the derivative is constant.
 104   if (std::abs(a) < kBezierEpsilon &&
 105       std::abs(b) < kBezierEpsilon)
 106     return;
 107
 108   // Zeros of the function's derivative.
 109   double t_1 = 0;
 110   double t_2 = 0;
 111
 112   if (std::abs(a) < kBezierEpsilon) {
 113     // The function's derivative is linear.
 114     t_1 = -c / b;
 115   } else {
 116     // The function's derivative is a quadratic. We find the zeros of this
 117     // quadratic using the quadratic formula.
 118     double discriminant = b * b - 4 * a * c;
 119     if (discriminant < 0)
 120       return;
 121     double discriminant_sqrt = sqrt(discriminant);
 122     t_1 = (-b + discriminant_sqrt) / (2 * a);
 123     t_2 = (-b - discriminant_sqrt) / (2 * a);
 124   }
 125
 126   double sol_1 = 0;
 127   double sol_2 = 0;
 128
 129   if (0 < t_1 && t_1 < 1)
 130     sol_1 = eval_bezier(y1_, y2_, t_1);
 131
 132   if (0 < t_2 && t_2 < 1)
 133     sol_2 = eval_bezier(y1_, y2_, t_2);
 134
 135   *min = std::min(std::min(*min, sol_1), sol_2);
 136   *max = std::max(std::max(*max, sol_1), sol_2);
 137 }
 138
 139 }  // namespace gfx