• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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