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 static const double kBezierEpsilon = 1e-7;
15
CubicBezier(double p1x,double p1y,double p2x,double p2y)16 CubicBezier::CubicBezier(double p1x, double p1y, double p2x, double p2y) {
17 InitCoefficients(p1x, p1y, p2x, p2y);
18 InitGradients(p1x, p1y, p2x, p2y);
19 InitRange(p1y, p2y);
20 }
21
22 CubicBezier::CubicBezier(const CubicBezier& other) = default;
23
InitCoefficients(double p1x,double p1y,double p2x,double p2y)24 void CubicBezier::InitCoefficients(double p1x,
25 double p1y,
26 double p2x,
27 double p2y) {
28 // Calculate the polynomial coefficients, implicit first and last control
29 // points are (0,0) and (1,1).
30 cx_ = 3.0 * p1x;
31 bx_ = 3.0 * (p2x - p1x) - cx_;
32 ax_ = 1.0 - cx_ - bx_;
33
34 cy_ = 3.0 * p1y;
35 by_ = 3.0 * (p2y - p1y) - cy_;
36 ay_ = 1.0 - cy_ - by_;
37 }
38
InitGradients(double p1x,double p1y,double p2x,double p2y)39 void CubicBezier::InitGradients(double p1x,
40 double p1y,
41 double p2x,
42 double p2y) {
43 // End-point gradients are used to calculate timing function results
44 // outside the range [0, 1].
45 //
46 // There are three possibilities for the gradient at each end:
47 // (1) the closest control point is not horizontally coincident with regard to
48 // (0, 0) or (1, 1). In this case the line between the end point and
49 // the control point is tangent to the bezier at the end point.
50 // (2) the closest control point is coincident with the end point. In
51 // this case the line between the end point and the far control
52 // point is tangent to the bezier at the end point.
53 // (3) the closest control point is horizontally coincident with the end
54 // point, but vertically distinct. In this case the gradient at the
55 // end point is Infinite. However, this causes issues when
56 // interpolating. As a result, we break down to a simple case of
57 // 0 gradient under these conditions.
58
59 if (p1x > 0)
60 start_gradient_ = p1y / p1x;
61 else if (!p1y && p2x > 0)
62 start_gradient_ = p2y / p2x;
63 else
64 start_gradient_ = 0;
65
66 if (p2x < 1)
67 end_gradient_ = (p2y - 1) / (p2x - 1);
68 else if (p2x == 1 && p1x < 1)
69 end_gradient_ = (p1y - 1) / (p1x - 1);
70 else
71 end_gradient_ = 0;
72 }
73
74 // This works by taking taking the derivative of the cubic bezier, on the y
75 // axis. We can then solve for where the derivative is zero to find the min
76 // and max distance along the line. We the have to solve those in terms of time
77 // rather than distance on the x-axis
InitRange(double p1y,double p2y)78 void CubicBezier::InitRange(double p1y, double p2y) {
79 range_min_ = 0;
80 range_max_ = 1;
81 if (0 <= p1y && p1y < 1 && 0 <= p2y && p2y <= 1)
82 return;
83
84 const double epsilon = kBezierEpsilon;
85
86 // Represent the function's derivative in the form at^2 + bt + c
87 // as in sampleCurveDerivativeY.
88 // (Technically this is (dy/dt)*(1/3), which is suitable for finding zeros
89 // but does not actually give the slope of the curve.)
90 const double a = 3.0 * ay_;
91 const double b = 2.0 * by_;
92 const double c = cy_;
93
94 // Check if the derivative is constant.
95 if (std::abs(a) < epsilon && std::abs(b) < epsilon)
96 return;
97
98 // Zeros of the function's derivative.
99 double t1 = 0;
100 double t2 = 0;
101
102 if (std::abs(a) < epsilon) {
103 // The function's derivative is linear.
104 t1 = -c / b;
105 } else {
106 // The function's derivative is a quadratic. We find the zeros of this
107 // quadratic using the quadratic formula.
108 double discriminant = b * b - 4 * a * c;
109 if (discriminant < 0)
110 return;
111 double discriminant_sqrt = sqrt(discriminant);
112 t1 = (-b + discriminant_sqrt) / (2 * a);
113 t2 = (-b - discriminant_sqrt) / (2 * a);
114 }
115
116 double sol1 = 0;
117 double sol2 = 0;
118
119 // If the solution is in the range [0,1] then we include it, otherwise we
120 // ignore it.
121
122 // An interesting fact about these beziers is that they are only
123 // actually evaluated in [0,1]. After that we take the tangent at that point
124 // and linearly project it out.
125 if (0 < t1 && t1 < 1)
126 sol1 = SampleCurveY(t1);
127
128 if (0 < t2 && t2 < 1)
129 sol2 = SampleCurveY(t2);
130
131 range_min_ = std::min(std::min(range_min_, sol1), sol2);
132 range_max_ = std::max(std::max(range_max_, sol1), sol2);
133 }
134
GetDefaultEpsilon()135 double CubicBezier::GetDefaultEpsilon() {
136 return kBezierEpsilon;
137 }
138
SolveCurveX(double x,double epsilon) const139 double CubicBezier::SolveCurveX(double x, double epsilon) const {
140 DCHECK_GE(x, 0.0);
141 DCHECK_LE(x, 1.0);
142
143 double t0;
144 double t1;
145 double t2;
146 double x2;
147 double d2;
148 int i;
149
150 // First try a few iterations of Newton's method -- normally very fast.
151 for (t2 = x, i = 0; i < 8; i++) {
152 x2 = SampleCurveX(t2) - x;
153 if (fabs(x2) < epsilon)
154 return t2;
155 d2 = SampleCurveDerivativeX(t2);
156 if (fabs(d2) < 1e-6)
157 break;
158 t2 = t2 - x2 / d2;
159 }
160
161 // Fall back to the bisection method for reliability.
162 t0 = 0.0;
163 t1 = 1.0;
164 t2 = x;
165
166 while (t0 < t1) {
167 x2 = SampleCurveX(t2);
168 if (fabs(x2 - x) < epsilon)
169 return t2;
170 if (x > x2)
171 t0 = t2;
172 else
173 t1 = t2;
174 t2 = (t1 - t0) * .5 + t0;
175 }
176
177 // Failure.
178 return t2;
179 }
180
Solve(double x) const181 double CubicBezier::Solve(double x) const {
182 return SolveWithEpsilon(x, kBezierEpsilon);
183 }
184
SlopeWithEpsilon(double x,double epsilon) const185 double CubicBezier::SlopeWithEpsilon(double x, double epsilon) const {
186 x = std::min(std::max(x, 0.0), 1.0);
187 double t = SolveCurveX(x, epsilon);
188 double dx = SampleCurveDerivativeX(t);
189 double dy = SampleCurveDerivativeY(t);
190 return dy / dx;
191 }
192
Slope(double x) const193 double CubicBezier::Slope(double x) const {
194 return SlopeWithEpsilon(x, kBezierEpsilon);
195 }
196
GetX1() const197 double CubicBezier::GetX1() const {
198 return cx_ / 3.0;
199 }
200
GetY1() const201 double CubicBezier::GetY1() const {
202 return cy_ / 3.0;
203 }
204
GetX2() const205 double CubicBezier::GetX2() const {
206 return (bx_ + cx_) / 3.0 + GetX1();
207 }
208
GetY2() const209 double CubicBezier::GetY2() const {
210 return (by_ + cy_) / 3.0 + GetY1();
211 }
212
213 } // namespace gfx
214