OLD | NEW |
| (Empty) |
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 | |
OLD | NEW |