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 x1, double x2, double t) {
  20   const double x1_times_3 = 3.0 * x1;
  21   const double x2_times_3 = 3.0 * x2;
  22   const double h3 = x1_times_3;
  23   const double h1 = x1_times_3 - x2_times_3 + 1.0;
  24   const double h2 = x2_times_3 - 6.0 * x1;
  25   return t * (t * (t * h1 + h2) + h3);
  26 }
  27
  28 static double bezier_interp(double x1,
  29                             double y1,
  30                             double x2,
  31                             double y2,
  32                             double x) {
  33   DCHECK_GE(1.0, x1);
  34   DCHECK_LE(0.0, x1);
  35   DCHECK_GE(1.0, x2);
  36   DCHECK_LE(0.0, x2);
  37
  38   x1 = std::min(std::max(x1, 0.0), 1.0);
  39   x2 = std::min(std::max(x2, 0.0), 1.0);
  40   x = std::min(std::max(x, 0.0), 1.0);
  41
  42   // Step 1. Find the t corresponding to the given x. I.e., we want t such that
  43   // eval_bezier(x1, x2, t) = x. There is a unique solution if x1 and x2 lie
  44   // within (0, 1).
  45   //
  46   // We're just going to do bisection for now (for simplicity), but we could
  47   // easily do some newton steps if this turns out to be a bottleneck.
  48   double t = 0.0;
  49   double step = 1.0;
  50   for (int i = 0; i < MAX_STEPS; ++i, step *= 0.5) {
  51     const double error = eval_bezier(x1, x2, t) - x;
  52     if (std::abs(error) < kBezierEpsilon)
  53       break;
  54     t += error > 0.0 ? -step : step;
  55   }
  56
  57   // We should have terminated the above loop because we got close to x, not
  58   // because we exceeded MAX_STEPS. Do a DCHECK here to confirm.
  59   DCHECK_GT(kBezierEpsilon, std::abs(eval_bezier(x1, x2, t) - x));
  60
  61   // Step 2. Return the interpolated y values at the t we computed above.
  62   return eval_bezier(y1, y2, t);
  63 }
  64
  65 }  // namespace
  66
  67 CubicBezier::CubicBezier(double x1, double y1, double x2, double y2)
  68     : x1_(x1),
  69       y1_(y1),
  70       x2_(x2),
  71       y2_(y2) {
  72 }
  73
  74 CubicBezier::~CubicBezier() {
  75 }
  76
  77 double CubicBezier::Solve(double x) const {
  78   return bezier_interp(x1_, y1_, x2_, y2_, x);
  79 }
  80
  81 void CubicBezier::Range(double* min, double* max) const {
  82   *min = 0;
  83   *max = 1;
  84   if (0 <= y1_ && y1_ < 1 && 0 <= y2_ && y2_ <= 1)
  85     return;
  86
  87   // Represent the function's derivative in the form at^2 + bt + c.
  88   double a = 3 * (y1_ - y2_) + 1;
  89   double b = 2 * (y2_ - 2 * y1_);
  90   double c = y1_;
  91
  92   // Check if the derivative is constant.
  93   if (std::abs(a) < kBezierEpsilon &&
  94       std::abs(b) < kBezierEpsilon)
  95     return;
  96
  97   // Zeros of the function's derivative.
  98   double t_1 = 0;
  99   double t_2 = 0;
 100
 101   if (std::abs(a) < kBezierEpsilon) {
 102     // The function's derivative is linear.
 103     t_1 = -c / b;
 104   } else {
 105     // The function's derivative is a quadratic. We find the zeros of this
 106     // quadratic using the quadratic formula.
 107     double discriminant = b * b - 4 * a * c;
 108     if (discriminant < 0)
 109       return;
 110     double discriminant_sqrt = sqrt(discriminant);
 111     t_1 = (-b + discriminant_sqrt) / (2 * a);
 112     t_2 = (-b - discriminant_sqrt) / (2 * a);
 113   }
 114
 115   double sol_1 = 0;
 116   double sol_2 = 0;
 117
 118   if (0 < t_1 && t_1 < 1)
 119     sol_1 = eval_bezier(y1_, y2_, t_1);
 120
 121   if (0 < t_2 && t_2 < 1)
 122     sol_2 = eval_bezier(y1_, y2_, t_2);
 123
 124   *min = std::min(std::min(*min, sol_1), sol_2);
 125   *max = std::max(std::max(*max, sol_1), sol_2);
 126 }
 127
 128 }  // namespace gfx