OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "ui/gfx/geometry/cubic_bezier.h" | 5 #include "ui/gfx/geometry/cubic_bezier.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <cmath> | 8 #include <cmath> |
9 | 9 |
10 #include "base/logging.h" | 10 #include "base/logging.h" |
11 | 11 |
12 namespace gfx { | 12 namespace gfx { |
13 | 13 |
14 namespace { | 14 namespace { |
15 | 15 |
16 static const double kBezierEpsilon = 1e-7; | 16 static const double kBezierEpsilon = 1e-7; |
17 static const int MAX_STEPS = 30; | 17 static const int MAX_STEPS = 30; |
18 | 18 |
19 static double eval_bezier(double x1, double x2, double t) { | 19 static double eval_bezier(double p1, double p2, double t) { |
20 const double x1_times_3 = 3.0 * x1; | 20 const double p1_times_3 = 3.0 * p1; |
21 const double x2_times_3 = 3.0 * x2; | 21 const double p2_times_3 = 3.0 * p2; |
22 const double h3 = x1_times_3; | 22 const double h3 = p1_times_3; |
23 const double h1 = x1_times_3 - x2_times_3 + 1.0; | 23 const double h1 = p1_times_3 - p2_times_3 + 1.0; |
24 const double h2 = x2_times_3 - 6.0 * x1; | 24 const double h2 = p2_times_3 - 6.0 * p1; |
25 return t * (t * (t * h1 + h2) + h3); | 25 return t * (t * (t * h1 + h2) + h3); |
26 } | 26 } |
27 | 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). |
28 static double bezier_interp(double x1, | 37 static double bezier_interp(double x1, |
29 double y1, | |
30 double x2, | 38 double x2, |
31 double y2, | |
32 double x) { | 39 double x) { |
33 DCHECK_GE(1.0, x1); | 40 DCHECK_GE(1.0, x1); |
34 DCHECK_LE(0.0, x1); | 41 DCHECK_LE(0.0, x1); |
35 DCHECK_GE(1.0, x2); | 42 DCHECK_GE(1.0, x2); |
36 DCHECK_LE(0.0, x2); | 43 DCHECK_LE(0.0, x2); |
37 | 44 |
38 x1 = std::min(std::max(x1, 0.0), 1.0); | 45 x1 = std::min(std::max(x1, 0.0), 1.0); |
39 x2 = std::min(std::max(x2, 0.0), 1.0); | 46 x2 = std::min(std::max(x2, 0.0), 1.0); |
40 x = std::min(std::max(x, 0.0), 1.0); | 47 x = std::min(std::max(x, 0.0), 1.0); |
41 | 48 |
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 | 49 // 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. | 50 // easily do some newton steps if this turns out to be a bottleneck. |
48 double t = 0.0; | 51 double t = 0.0; |
49 double step = 1.0; | 52 double step = 1.0; |
50 for (int i = 0; i < MAX_STEPS; ++i, step *= 0.5) { | 53 for (int i = 0; i < MAX_STEPS; ++i, step *= 0.5) { |
51 const double error = eval_bezier(x1, x2, t) - x; | 54 const double error = eval_bezier(x1, x2, t) - x; |
52 if (std::abs(error) < kBezierEpsilon) | 55 if (std::abs(error) < kBezierEpsilon) |
53 break; | 56 break; |
54 t += error > 0.0 ? -step : step; | 57 t += error > 0.0 ? -step : step; |
55 } | 58 } |
56 | 59 |
57 // We should have terminated the above loop because we got close to x, not | 60 // 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. | 61 // because we exceeded MAX_STEPS. Do a DCHECK here to confirm. |
59 DCHECK_GT(kBezierEpsilon, std::abs(eval_bezier(x1, x2, t) - x)); | 62 DCHECK_GT(kBezierEpsilon, std::abs(eval_bezier(x1, x2, t) - x)); |
60 | 63 |
61 // Step 2. Return the interpolated y values at the t we computed above. | 64 return t; |
62 return eval_bezier(y1, y2, t); | |
63 } | 65 } |
64 | 66 |
65 } // namespace | 67 } // namespace |
66 | 68 |
67 CubicBezier::CubicBezier(double x1, double y1, double x2, double y2) | 69 CubicBezier::CubicBezier(double x1, double y1, double x2, double y2) |
68 : x1_(x1), | 70 : x1_(x1), |
69 y1_(y1), | 71 y1_(y1), |
70 x2_(x2), | 72 x2_(x2), |
71 y2_(y2) { | 73 y2_(y2) { |
72 } | 74 } |
73 | 75 |
74 CubicBezier::~CubicBezier() { | 76 CubicBezier::~CubicBezier() { |
75 } | 77 } |
76 | 78 |
77 double CubicBezier::Solve(double x) const { | 79 double CubicBezier::Solve(double x) const { |
78 return bezier_interp(x1_, y1_, x2_, y2_, x); | 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; |
79 } | 88 } |
80 | 89 |
81 void CubicBezier::Range(double* min, double* max) const { | 90 void CubicBezier::Range(double* min, double* max) const { |
82 *min = 0; | 91 *min = 0; |
83 *max = 1; | 92 *max = 1; |
84 if (0 <= y1_ && y1_ < 1 && 0 <= y2_ && y2_ <= 1) | 93 if (0 <= y1_ && y1_ < 1 && 0 <= y2_ && y2_ <= 1) |
85 return; | 94 return; |
86 | 95 |
87 // Represent the function's derivative in the form at^2 + bt + c. | 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.) |
88 double a = 3 * (y1_ - y2_) + 1; | 99 double a = 3 * (y1_ - y2_) + 1; |
89 double b = 2 * (y2_ - 2 * y1_); | 100 double b = 2 * (y2_ - 2 * y1_); |
90 double c = y1_; | 101 double c = y1_; |
91 | 102 |
92 // Check if the derivative is constant. | 103 // Check if the derivative is constant. |
93 if (std::abs(a) < kBezierEpsilon && | 104 if (std::abs(a) < kBezierEpsilon && |
94 std::abs(b) < kBezierEpsilon) | 105 std::abs(b) < kBezierEpsilon) |
95 return; | 106 return; |
96 | 107 |
97 // Zeros of the function's derivative. | 108 // Zeros of the function's derivative. |
(...skipping 21 matching lines...) Expand all Loading... |
119 sol_1 = eval_bezier(y1_, y2_, t_1); | 130 sol_1 = eval_bezier(y1_, y2_, t_1); |
120 | 131 |
121 if (0 < t_2 && t_2 < 1) | 132 if (0 < t_2 && t_2 < 1) |
122 sol_2 = eval_bezier(y1_, y2_, t_2); | 133 sol_2 = eval_bezier(y1_, y2_, t_2); |
123 | 134 |
124 *min = std::min(std::min(*min, sol_1), sol_2); | 135 *min = std::min(std::min(*min, sol_1), sol_2); |
125 *max = std::max(std::max(*max, sol_1), sol_2); | 136 *max = std::max(std::max(*max, sol_1), sol_2); |
126 } | 137 } |
127 | 138 |
128 } // namespace gfx | 139 } // namespace gfx |
OLD | NEW |