1 /*
2 * Copyright 2012 Google LLC
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "src/base/SkBezierCurves.h"
9
10 #include "include/private/base/SkAssert.h"
11
12 #include <cstddef>
13
interpolate(double A,double B,double t)14 static inline double interpolate(double A, double B, double t) {
15 return A + (B - A) * t;
16 }
17
EvalAt(const double curve[8],double t)18 std::array<double, 2> SkBezierCubic::EvalAt(const double curve[8], double t) {
19 const auto in_X = [&curve](size_t n) { return curve[2*n]; };
20 const auto in_Y = [&curve](size_t n) { return curve[2*n + 1]; };
21
22 // Two semi-common fast paths
23 if (t == 0) {
24 return {in_X(0), in_Y(0)};
25 }
26 if (t == 1) {
27 return {in_X(3), in_Y(3)};
28 }
29 // X(t) = X_0*(1-t)^3 + 3*X_1*t(1-t)^2 + 3*X_2*t^2(1-t) + X_3*t^3
30 // Y(t) = Y_0*(1-t)^3 + 3*Y_1*t(1-t)^2 + 3*Y_2*t^2(1-t) + Y_3*t^3
31 // Some compilers are smart enough and have sufficient registers/intrinsics to write optimal
32 // code from
33 // double one_minus_t = 1 - t;
34 // double a = one_minus_t * one_minus_t * one_minus_t;
35 // double b = 3 * one_minus_t * one_minus_t * t;
36 // double c = 3 * one_minus_t * t * t;
37 // double d = t * t * t;
38 // However, some (e.g. when compiling for ARM) fail to do so, so we use this form
39 // to help more compilers generate smaller/faster ASM. https://godbolt.org/z/M6jG9x45c
40 double one_minus_t = 1 - t;
41 double one_minus_t_squared = one_minus_t * one_minus_t;
42 double a = (one_minus_t_squared * one_minus_t);
43 double b = 3 * one_minus_t_squared * t;
44 double t_squared = t * t;
45 double c = 3 * one_minus_t * t_squared;
46 double d = t_squared * t;
47
48 return {a * in_X(0) + b * in_X(1) + c * in_X(2) + d * in_X(3),
49 a * in_Y(0) + b * in_Y(1) + c * in_Y(2) + d * in_Y(3)};
50 }
51
52 // Perform subdivision using De Casteljau's algorithm, that is, repeated linear
53 // interpolation between adjacent points.
Subdivide(const double curve[8],double t,double twoCurves[14])54 void SkBezierCubic::Subdivide(const double curve[8], double t,
55 double twoCurves[14]) {
56 SkASSERT(0.0 <= t && t <= 1.0);
57 // We split the curve "in" into two curves "alpha" and "beta"
58 const auto in_X = [&curve](size_t n) { return curve[2*n]; };
59 const auto in_Y = [&curve](size_t n) { return curve[2*n + 1]; };
60 const auto alpha_X = [&twoCurves](size_t n) -> double& { return twoCurves[2*n]; };
61 const auto alpha_Y = [&twoCurves](size_t n) -> double& { return twoCurves[2*n + 1]; };
62 const auto beta_X = [&twoCurves](size_t n) -> double& { return twoCurves[2*n + 6]; };
63 const auto beta_Y = [&twoCurves](size_t n) -> double& { return twoCurves[2*n + 7]; };
64
65 alpha_X(0) = in_X(0);
66 alpha_Y(0) = in_Y(0);
67
68 beta_X(3) = in_X(3);
69 beta_Y(3) = in_Y(3);
70
71 double x01 = interpolate(in_X(0), in_X(1), t);
72 double y01 = interpolate(in_Y(0), in_Y(1), t);
73 double x12 = interpolate(in_X(1), in_X(2), t);
74 double y12 = interpolate(in_Y(1), in_Y(2), t);
75 double x23 = interpolate(in_X(2), in_X(3), t);
76 double y23 = interpolate(in_Y(2), in_Y(3), t);
77
78 alpha_X(1) = x01;
79 alpha_Y(1) = y01;
80
81 beta_X(2) = x23;
82 beta_Y(2) = y23;
83
84 alpha_X(2) = interpolate(x01, x12, t);
85 alpha_Y(2) = interpolate(y01, y12, t);
86
87 beta_X(1) = interpolate(x12, x23, t);
88 beta_Y(1) = interpolate(y12, y23, t);
89
90 alpha_X(3) /*= beta_X(0) */ = interpolate(alpha_X(2), beta_X(1), t);
91 alpha_Y(3) /*= beta_Y(0) */ = interpolate(alpha_Y(2), beta_Y(1), t);
92 }
93
ConvertToPolynomial(const double curve[8],bool yValues)94 std::array<double, 4> SkBezierCubic::ConvertToPolynomial(const double curve[8], bool yValues) {
95 const double* offset_curve = yValues ? curve + 1 : curve;
96 const auto P = [&offset_curve](size_t n) { return offset_curve[2*n]; };
97 // A cubic Bézier curve is interpolated as follows:
98 // c(t) = (1 - t)^3 P_0 + 3t(1 - t)^2 P_1 + 3t^2 (1 - t) P_2 + t^3 P_3
99 // = (-P_0 + 3P_1 + -3P_2 + P_3) t^3 + (3P_0 - 6P_1 + 3P_2) t^2 +
100 // (-3P_0 + 3P_1) t + P_0
101 // Where P_N is the Nth point. The second step expands the polynomial and groups
102 // by powers of t. The desired output is a cubic formula, so we just need to
103 // combine the appropriate points to make the coefficients.
104 std::array<double, 4> results;
105 results[0] = -P(0) + 3*P(1) - 3*P(2) + P(3);
106 results[1] = 3*P(0) - 6*P(1) + 3*P(2);
107 results[2] = -3*P(0) + 3*P(1);
108 results[3] = P(0);
109 return results;
110 }
111
112