cubic_bezier.cc 7.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275
  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. #include "ui/gfx/geometry/cubic_bezier.h"
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <limits>
  8. #include "base/check_op.h"
  9. #include "base/cxx17_backports.h"
  10. namespace gfx {
  11. namespace {
  12. const int kMaxNewtonIterations = 4;
  13. } // namespace
  14. static const double kBezierEpsilon = 1e-7;
  15. double CubicBezier::ToFinite(double value) {
  16. // TODO(crbug.com/1275541): We can clamp this in numeric operation helper
  17. // function like ClampedNumeric.
  18. if (std::isinf(value)) {
  19. if (value > 0)
  20. return std::numeric_limits<double>::max();
  21. return std::numeric_limits<double>::lowest();
  22. }
  23. return value;
  24. }
  25. CubicBezier::CubicBezier(double p1x, double p1y, double p2x, double p2y) {
  26. InitCoefficients(p1x, p1y, p2x, p2y);
  27. InitGradients(p1x, p1y, p2x, p2y);
  28. InitRange(p1y, p2y);
  29. InitSpline();
  30. }
  31. CubicBezier::CubicBezier(const CubicBezier& other) = default;
  32. void CubicBezier::InitCoefficients(double p1x,
  33. double p1y,
  34. double p2x,
  35. double p2y) {
  36. // Calculate the polynomial coefficients, implicit first and last control
  37. // points are (0,0) and (1,1).
  38. cx_ = 3.0 * p1x;
  39. bx_ = 3.0 * (p2x - p1x) - cx_;
  40. ax_ = 1.0 - cx_ - bx_;
  41. cy_ = ToFinite(3.0 * p1y);
  42. by_ = ToFinite(3.0 * (p2y - p1y) - cy_);
  43. ay_ = ToFinite(1.0 - cy_ - by_);
  44. #ifndef NDEBUG
  45. // Bezier curves with x-coordinates outside the range [0,1] for internal
  46. // control points may have multiple values for t for a given value of x.
  47. // In this case, calls to SolveCurveX may produce ambiguous results.
  48. monotonically_increasing_ = p1x >= 0 && p1x <= 1 && p2x >= 0 && p2x <= 1;
  49. #endif
  50. }
  51. void CubicBezier::InitGradients(double p1x,
  52. double p1y,
  53. double p2x,
  54. double p2y) {
  55. // End-point gradients are used to calculate timing function results
  56. // outside the range [0, 1].
  57. //
  58. // There are four possibilities for the gradient at each end:
  59. // (1) the closest control point is not horizontally coincident with regard to
  60. // (0, 0) or (1, 1). In this case the line between the end point and
  61. // the control point is tangent to the bezier at the end point.
  62. // (2) the closest control point is coincident with the end point. In
  63. // this case the line between the end point and the far control
  64. // point is tangent to the bezier at the end point.
  65. // (3) both internal control points are coincident with an endpoint. There
  66. // are two special case that fall into this category:
  67. // CubicBezier(0, 0, 0, 0) and CubicBezier(1, 1, 1, 1). Both are
  68. // equivalent to linear.
  69. // (4) the closest control point is horizontally coincident with the end
  70. // point, but vertically distinct. In this case the gradient at the
  71. // end point is Infinite. However, this causes issues when
  72. // interpolating. As a result, we break down to a simple case of
  73. // 0 gradient under these conditions.
  74. if (p1x > 0)
  75. start_gradient_ = p1y / p1x;
  76. else if (!p1y && p2x > 0)
  77. start_gradient_ = p2y / p2x;
  78. else if (!p1y && !p2y)
  79. start_gradient_ = 1;
  80. else
  81. start_gradient_ = 0;
  82. if (p2x < 1)
  83. end_gradient_ = (p2y - 1) / (p2x - 1);
  84. else if (p2y == 1 && p1x < 1)
  85. end_gradient_ = (p1y - 1) / (p1x - 1);
  86. else if (p2y == 1 && p1y == 1)
  87. end_gradient_ = 1;
  88. else
  89. end_gradient_ = 0;
  90. }
  91. // This works by taking taking the derivative of the cubic bezier, on the y
  92. // axis. We can then solve for where the derivative is zero to find the min
  93. // and max distance along the line. We the have to solve those in terms of time
  94. // rather than distance on the x-axis
  95. void CubicBezier::InitRange(double p1y, double p2y) {
  96. range_min_ = 0;
  97. range_max_ = 1;
  98. if (0 <= p1y && p1y < 1 && 0 <= p2y && p2y <= 1)
  99. return;
  100. const double epsilon = kBezierEpsilon;
  101. // Represent the function's derivative in the form at^2 + bt + c
  102. // as in sampleCurveDerivativeY.
  103. // (Technically this is (dy/dt)*(1/3), which is suitable for finding zeros
  104. // but does not actually give the slope of the curve.)
  105. const double a = 3.0 * ay_;
  106. const double b = 2.0 * by_;
  107. const double c = cy_;
  108. // Check if the derivative is constant.
  109. if (std::abs(a) < epsilon && std::abs(b) < epsilon)
  110. return;
  111. // Zeros of the function's derivative.
  112. double t1 = 0;
  113. double t2 = 0;
  114. if (std::abs(a) < epsilon) {
  115. // The function's derivative is linear.
  116. t1 = -c / b;
  117. } else {
  118. // The function's derivative is a quadratic. We find the zeros of this
  119. // quadratic using the quadratic formula.
  120. double discriminant = b * b - 4 * a * c;
  121. if (discriminant < 0)
  122. return;
  123. double discriminant_sqrt = sqrt(discriminant);
  124. t1 = (-b + discriminant_sqrt) / (2 * a);
  125. t2 = (-b - discriminant_sqrt) / (2 * a);
  126. }
  127. double sol1 = 0;
  128. double sol2 = 0;
  129. // If the solution is in the range [0,1] then we include it, otherwise we
  130. // ignore it.
  131. // An interesting fact about these beziers is that they are only
  132. // actually evaluated in [0,1]. After that we take the tangent at that point
  133. // and linearly project it out.
  134. if (0 < t1 && t1 < 1)
  135. sol1 = SampleCurveY(t1);
  136. if (0 < t2 && t2 < 1)
  137. sol2 = SampleCurveY(t2);
  138. range_min_ = std::min({range_min_, sol1, sol2});
  139. range_max_ = std::max({range_max_, sol1, sol2});
  140. }
  141. void CubicBezier::InitSpline() {
  142. double delta_t = 1.0 / (CUBIC_BEZIER_SPLINE_SAMPLES - 1);
  143. for (int i = 0; i < CUBIC_BEZIER_SPLINE_SAMPLES; i++) {
  144. spline_samples_[i] = SampleCurveX(i * delta_t);
  145. }
  146. }
  147. double CubicBezier::GetDefaultEpsilon() {
  148. return kBezierEpsilon;
  149. }
  150. double CubicBezier::SolveCurveX(double x, double epsilon) const {
  151. DCHECK_GE(x, 0.0);
  152. DCHECK_LE(x, 1.0);
  153. double t0;
  154. double t1;
  155. double t2 = x;
  156. double x2;
  157. double d2;
  158. int i;
  159. #ifndef NDEBUG
  160. DCHECK(monotonically_increasing_);
  161. #endif
  162. // Linear interpolation of spline curve for initial guess.
  163. double delta_t = 1.0 / (CUBIC_BEZIER_SPLINE_SAMPLES - 1);
  164. for (i = 1; i < CUBIC_BEZIER_SPLINE_SAMPLES; i++) {
  165. if (x <= spline_samples_[i]) {
  166. t1 = delta_t * i;
  167. t0 = t1 - delta_t;
  168. t2 = t0 + (t1 - t0) * (x - spline_samples_[i - 1]) /
  169. (spline_samples_[i] - spline_samples_[i - 1]);
  170. break;
  171. }
  172. }
  173. // Perform a few iterations of Newton's method -- normally very fast.
  174. // See https://en.wikipedia.org/wiki/Newton%27s_method.
  175. double newton_epsilon = std::min(kBezierEpsilon, epsilon);
  176. for (i = 0; i < kMaxNewtonIterations; i++) {
  177. x2 = SampleCurveX(t2) - x;
  178. if (fabs(x2) < newton_epsilon)
  179. return t2;
  180. d2 = SampleCurveDerivativeX(t2);
  181. if (fabs(d2) < kBezierEpsilon)
  182. break;
  183. t2 = t2 - x2 / d2;
  184. }
  185. if (fabs(x2) < epsilon)
  186. return t2;
  187. // Fall back to the bisection method for reliability.
  188. while (t0 < t1) {
  189. x2 = SampleCurveX(t2);
  190. if (fabs(x2 - x) < epsilon)
  191. return t2;
  192. if (x > x2)
  193. t0 = t2;
  194. else
  195. t1 = t2;
  196. t2 = (t1 + t0) * .5;
  197. }
  198. // Failure.
  199. return t2;
  200. }
  201. double CubicBezier::Solve(double x) const {
  202. return SolveWithEpsilon(x, kBezierEpsilon);
  203. }
  204. double CubicBezier::SlopeWithEpsilon(double x, double epsilon) const {
  205. x = base::clamp(x, 0.0, 1.0);
  206. double t = SolveCurveX(x, epsilon);
  207. double dx = SampleCurveDerivativeX(t);
  208. double dy = SampleCurveDerivativeY(t);
  209. // TODO(crbug.com/1275534): We should clamp NaN to a proper value.
  210. // Please see the issue for detail.
  211. if (!dx && !dy)
  212. return 0;
  213. return ToFinite(dy / dx);
  214. }
  215. double CubicBezier::Slope(double x) const {
  216. return SlopeWithEpsilon(x, kBezierEpsilon);
  217. }
  218. double CubicBezier::GetX1() const {
  219. return cx_ / 3.0;
  220. }
  221. double CubicBezier::GetY1() const {
  222. return cy_ / 3.0;
  223. }
  224. double CubicBezier::GetX2() const {
  225. return (bx_ + cx_) / 3.0 + GetX1();
  226. }
  227. double CubicBezier::GetY2() const {
  228. return (by_ + cy_) / 3.0 + GetY1();
  229. }
  230. } // namespace gfx