1 /*
2 * Copyright 2023 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 "include/private/base/SkFloatingPoint.h"
9 #include "include/private/base/SkSpan_impl.h"
10 #include "src/base/SkBezierCurves.h"
11 #include "src/base/SkQuads.h"
12 #include "tests/Test.h"
13
14 #include <algorithm>
15 #include <cmath>
16 #include <cstddef>
17 #include <initializer_list>
18 #include <limits>
19 #include <set>
20 #include <string>
21
22 // Grouping the test inputs into DoublePoints makes the test cases easier to read.
23 struct DoublePoint {
24 double x;
25 double y;
26 };
27
nearly_equal(double expected,double actual)28 static bool nearly_equal(double expected, double actual) {
29 if (sk_double_nearly_zero(expected)) {
30 return sk_double_nearly_zero(actual);
31 }
32 return sk_doubles_nearly_equal_ulps(expected, actual, 64);
33 }
34
testCubicEvalAtT(skiatest::Reporter * reporter,const std::string & name,SkSpan<const DoublePoint> curveInputs,double t,const DoublePoint & expectedXY)35 static void testCubicEvalAtT(skiatest::Reporter* reporter, const std::string& name,
36 SkSpan<const DoublePoint> curveInputs, double t,
37 const DoublePoint& expectedXY) {
38 skiatest::ReporterContext subtest(reporter, name);
39 REPORTER_ASSERT(reporter, curveInputs.size() == 4,
40 "Invalid test case. Should have 4 input points.");
41 REPORTER_ASSERT(reporter, t >= 0.0 && t <= 1.0,
42 "Invalid test case. t %f should be in [0, 1]", t);
43
44 auto [x, y] = SkBezierCubic::EvalAt(reinterpret_cast<const double*>(curveInputs.data()), t);
45
46 REPORTER_ASSERT(reporter, nearly_equal(expectedXY.x, x),
47 "X wrong %1.16f != %1.16f", expectedXY.x, x);
48 REPORTER_ASSERT(reporter, nearly_equal(expectedXY.y, y),
49 "Y wrong %1.16f != %1.16f", expectedXY.y, y);
50 }
51
DEF_TEST(BezierCubicEvalAt,reporter)52 DEF_TEST(BezierCubicEvalAt, reporter) {
53 testCubicEvalAtT(reporter, "linear curve @0.1234",
54 {{ 0, 0 }, { 0, 0 }, { 10, 10 }, { 10, 10 }},
55 0.1234,
56 { 0.4192451819200000, 0.4192451819200000 });
57
58 testCubicEvalAtT(reporter, "linear curve @0.2345",
59 {{ 0, 0 }, { 5, 5 }, { 5, 5 }, { 10, 10 }},
60 0.2345,
61 { 2.8215983862500000, 2.8215983862500000 });
62
63 testCubicEvalAtT(reporter, "Arbitrary Cubic, t=0.0",
64 {{ -10, -20 }, { -7, 5 }, { 14, -2 }, { 3, 13 }},
65 0.0,
66 { -10, -20 });
67
68 testCubicEvalAtT(reporter, "Arbitrary Cubic, t=0.3456",
69 {{ -10, -20 }, { -7, 5 }, { 14, -2 }, { 3, 13 }},
70 0.3456,
71 { -2.503786700800000, -3.31715344793600 });
72
73 testCubicEvalAtT(reporter, "Arbitrary Cubic, t=0.5",
74 {{ -10, -20 }, { -7, 5 }, { 14, -2 }, { 3, 13 }},
75 0.5,
76 { 1.75, 0.25 });
77
78 testCubicEvalAtT(reporter, "Arbitrary Cubic, t=0.7891",
79 {{ -10, -20 }, { -7, 5 }, { 14, -2 }, { 3, 13 }},
80 0.7891,
81 { 6.158763291450000, 5.938550084434000 });
82
83 testCubicEvalAtT(reporter, "Arbitrary Cubic, t=1.0",
84 {{ -10, -20 }, { -7, 5 }, { 14, -2 }, { 3, 13 }},
85 1.0,
86 { 3, 13 });
87 }
88
testCubicConvertToPolynomial(skiatest::Reporter * reporter,const std::string & name,SkSpan<const DoublePoint> curveInputs,bool yValues,double expectedA,double expectedB,double expectedC,double expectedD)89 static void testCubicConvertToPolynomial(skiatest::Reporter* reporter, const std::string& name,
90 SkSpan<const DoublePoint> curveInputs, bool yValues,
91 double expectedA, double expectedB,
92 double expectedC, double expectedD) {
93 skiatest::ReporterContext subtest(reporter, name);
94 REPORTER_ASSERT(reporter, curveInputs.size() == 4,
95 "Invalid test case. Need 4 points (start, control, control, end)");
96
97 skiatest::ReporterContext subsubtest(reporter, "SkBezierCurve Implementation");
98 const double* input = &curveInputs[0].x;
99 auto [A, B, C, D] = SkBezierCubic::ConvertToPolynomial(input, yValues);
100
101 REPORTER_ASSERT(reporter, nearly_equal(expectedA, A), "%f != %f", expectedA, A);
102 REPORTER_ASSERT(reporter, nearly_equal(expectedB, B), "%f != %f", expectedB, B);
103 REPORTER_ASSERT(reporter, nearly_equal(expectedC, C), "%f != %f", expectedC, C);
104 REPORTER_ASSERT(reporter, nearly_equal(expectedD, D), "%f != %f", expectedD, D);
105 }
106
DEF_TEST(BezierCubicToPolynomials,reporter)107 DEF_TEST(BezierCubicToPolynomials, reporter) {
108 // See also tests/PathOpsDCubicTest.cpp->SkDCubicPolynomialCoefficients
109 testCubicConvertToPolynomial(reporter, "Arbitrary control points X direction",
110 {{1, 2}, {-3, 4}, {5, -6}, {7, 8}}, false, /*=yValues*/
111 -18, 36, -12, 1
112 );
113 testCubicConvertToPolynomial(reporter, "Arbitrary control points Y direction",
114 {{1, 2}, {-3, 4}, {5, -6}, {7, 8}}, true, /*=yValues*/
115 36, -36, 6, 2
116 );
117 }
118
119 // Since, Roots and EvalAt are separately unit tested, make sure that the parametric pramater t
120 // is correctly in range, and checked.
DEF_TEST(QuadRoots_CheckTRange,reporter)121 DEF_TEST(QuadRoots_CheckTRange, reporter) {
122 // Pick interesting numbers around 0 and 1.
123 const double interestingRoots[] =
124 {-1000, -10, -1, -0.1, -0.0001, 0, 0.0001, 0.1, 0.9, 0.9999, 1, 1.0001, 1.1, 10, 1000};
125
126 // Interesting scales to make the quadratic.
127 const double interestingScales[] =
128 {-1000, -10, -1, -0.1, -0.0001, 0.0001, 0.1, 1, 10, 1000};
129
130 auto outsideTRange = [](double r) {
131 return r < 0 || 1 < r;
132 };
133
134 auto insideTRange = [&] (double r) {
135 return !outsideTRange(r);
136 };
137
138 // The original test for AddValidTs (which quad intersect was based on) used 1 float ulp of
139 // leeway for comparison. Tighten this up to half a float ulp.
140 auto equalAsFloat = [] (double a, double b) {
141 // When converted to float, a double will be rounded up to half a float ulp for a double
142 // value between two float values.
143 return sk_double_to_float(a) == sk_double_to_float(b);
144 };
145
146 for (double r1 : interestingRoots) {
147 for (double r0 : interestingRoots) {
148 for (double s : interestingScales) {
149 // Create a quadratic using the roots r0 and r1.
150 // s(x-r0)(x-r1) = s(x^2 - r0*x - r1*x + r0*r1)
151 const double A = s;
152 // Normally B = -(r0 + r1) but this needs the modified B' = (r0 + r1) / 2.
153 const double B = s * 0.5 * (r0 + r1);
154 const double C = s*r0*r1;
155
156 float storage[2];
157 // The X coefficients are set to return t's generated by root intersection.
158 // The offset is set to 0, because an arbitrary offset is essentially encoded in C.
159 auto intersections = SkBezierQuad::Intersect(0, -0.5, 0, A, B, C, 0, storage);
160
161 if (intersections.empty()) {
162 // Either imaginary or both roots are outside [0, 1].
163 REPORTER_ASSERT(reporter,
164 SkQuads::Discriminant(A, B, C) < 0
165 || (outsideTRange(r0) && outsideTRange(r1)));
166 } else if (intersections.size() == 1) {
167 // One of the roots is outside [0, 1]
168 REPORTER_ASSERT(reporter, insideTRange(r0) || insideTRange(r1));
169 const double insideRoot = insideTRange(r0) ? r0 : r1;
170 REPORTER_ASSERT(reporter, equalAsFloat(insideRoot, intersections[0]));
171 } else {
172 REPORTER_ASSERT(reporter, intersections.size() == 2);
173 REPORTER_ASSERT(reporter, insideTRange(r0) && insideTRange(r1));
174 auto [smaller, bigger] = std::minmax(intersections[0], intersections[1]);
175 auto [smallerRoot, biggerRoot] = std::minmax(r0, r1);
176 REPORTER_ASSERT(reporter, equalAsFloat(smaller, smallerRoot));
177 REPORTER_ASSERT(reporter, equalAsFloat(bigger, biggerRoot));
178 }
179 }
180 }
181 }
182
183 // Check when A == 0.
184 {
185 const double A = 0;
186
187 // We need M = 4, so that will be a Kahan style B of -0.5 * M = -2.
188 const double B = -2;
189 const double C = -1;
190 float storage[2];
191
192 // Assume the offset is already encoded in C.
193 auto intersections = SkBezierQuad::Intersect(0, -0.5, 0, A, B, C, 0, storage);
194 REPORTER_ASSERT(reporter, intersections.size() == 1);
195 REPORTER_ASSERT(reporter, intersections[0] == 0.25);
196 }
197 }
198
199 // Since, Roots and EvalAt are separately unit tested, make sure that the parametric pramater t
200 // is correctly in range, and checked.
DEF_TEST(SkBezierCubic_CheckTRange,reporter)201 DEF_TEST(SkBezierCubic_CheckTRange, reporter) {
202 // Pick interesting numbers around 0 and 1.
203 const double interestingRoots[] =
204 {-10, -5, -2, -1, 0, 0.5, 1, 2, 5, 10};
205
206 // Interesting scales to make the quadratic.
207 const double interestingScales[] =
208 {-1000, -10, -1, -0.1, -0.0001, 0.0001, 0.1, 1, 10, 1000};
209
210 auto outsideTRange = [](double r) {
211 return r < 0 || 1 < r;
212 };
213
214 auto insideTRange = [&] (double r) {
215 return !outsideTRange(r);
216 };
217
218 auto specialEqual = [] (double actual, double test) {
219 // At least a floats worth of digits are correct.
220 const double errorFactor = std::numeric_limits<float>::epsilon();
221 return std::abs(test - actual) <= errorFactor * std::max(std::abs(test), std::abs(actual));
222 };
223
224 for (double r2 : interestingRoots) {
225 for (double r1 : interestingRoots) {
226 for (double r0 : interestingRoots) {
227 for (double s : interestingScales) {
228 // Create a cubic using the roots r0, r1, and r2.
229 // s(x-r0)(x-r1)(x-r2) = s(x^3 - (r0+r1+r2)x^2 + (r0r1+r1r2+r0r2)x - r0r1r2)
230 const double A = s,
231 B = -s * (r0+r1+r2),
232 C = s * (r0*r1 + r1*r2 + r0*r2),
233 D = -s * r0 * r1 * r2;
234
235 // Accumulate all the valid t's.
236 std::set<double> inRangeRoots;
237 for (auto r : {r0, r1, r2}) {
238 if (insideTRange(r)) {
239 inRangeRoots.insert(r);
240 }
241 }
242
243 float storage[3];
244 // The X coefficients are set to return t's generated by root intersection.
245 // The offset is set to 0, because an arbitrary offset is essentially encoded
246 // in C.
247 auto intersections =
248 SkBezierCubic::Intersect(0, 0, 1, 0, A, B, C, D, 0, storage);
249
250 size_t correct = 0;
251 for (auto candidate : intersections) {
252 for (auto answer : inRangeRoots) {
253 if (specialEqual(candidate, answer)) {
254 correct += 1;
255 break;
256 }
257 }
258 }
259 REPORTER_ASSERT(reporter, correct == intersections.size());
260 }
261 }
262 }
263 }
264 }
265
266