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
eval_bezier(double x1,double x2,double t)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
bezier_interp(double x1,double y1,double x2,double y2,double x)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
CubicBezier(double x1,double y1,double x2,double y2)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
~CubicBezier()74 CubicBezier::~CubicBezier() {
75 }
76
Solve(double x) const77 double CubicBezier::Solve(double x) const {
78 return bezier_interp(x1_, y1_, x2_, y2_, x);
79 }
80
Range(double * min,double * max) const81 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
129