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/core/SkSpan.h"
9 #include "include/core/SkTypes.h"
10 #include "include/private/base/SkFloatingPoint.h"
11 #include "src/base/SkBezierCurves.h"
12 #include "src/pathops/SkPathOpsCubic.h"
13 #include "src/pathops/SkPathOpsPoint.h"
14 #include "src/pathops/SkPathOpsTypes.h"
15 #include "tests/Test.h"
16
17 #include <algorithm>
18 #include <array>
19 #include <cstring>
20 #include <iterator>
21 #include <string>
22
23 // Grouping the test inputs into DoublePoints makes the test cases easier to read.
24 struct DoublePoint {
25 double x;
26 double y;
27 };
28
nearly_equal(double expected,double actual)29 static bool nearly_equal(double expected, double actual) {
30 if (sk_double_nearly_zero(expected)) {
31 return sk_double_nearly_zero(actual);
32 }
33 return sk_doubles_nearly_equal_ulps(expected, actual, 64);
34 }
35
testChopCubicAtT(skiatest::Reporter * reporter,const std::string & name,SkSpan<const DoublePoint> curveInputs,double t,SkSpan<const DoublePoint> expectedOutputs)36 static void testChopCubicAtT(skiatest::Reporter* reporter, const std::string& name,
37 SkSpan<const DoublePoint> curveInputs, double t,
38 SkSpan<const DoublePoint> expectedOutputs) {
39 skiatest::ReporterContext subtest(reporter, name);
40 REPORTER_ASSERT(reporter, curveInputs.size() == 4,
41 "Invalid test case. Should have 4 input points.");
42 REPORTER_ASSERT(reporter, t >= 0.0 && t <= 1.0,
43 "Invalid test case. t %f should be in [0, 1]", t);
44 // Two cubic curves, sharing an input point
45 REPORTER_ASSERT(reporter, expectedOutputs.size() == 7,
46 "Invalid test case. Should have 7 output points.");
47
48
49 {
50 skiatest::ReporterContext subsubtest(reporter, "Pathops Implementation");
51 SkDCubic input;
52 std::memcpy(&input.fPts[0], curveInputs.begin(), 8 * sizeof(double));
53 SkDCubicPair output = input.chopAt(t);
54
55 for (int i = 0; i < 7; ++i) {
56 REPORTER_ASSERT(reporter,
57 nearly_equal(expectedOutputs[i].x, output.pts[i].fX) &&
58 nearly_equal(expectedOutputs[i].y, output.pts[i].fY),
59 "(%.16f, %.16f) != (%.16f, %.16f) at index %d",
60 expectedOutputs[i].x, expectedOutputs[i].y,
61 output.pts[i].fX, output.pts[i].fY, i);
62 }
63 }
64 {
65 skiatest::ReporterContext subsubtest(reporter, "SkBezier Implementation");
66 double input[8];
67 double output[14];
68 std::memcpy(input, curveInputs.begin(), 8 * sizeof(double));
69 SkBezierCubic::Subdivide(input, t, output);
70
71 for (int i = 0; i < 7; ++i) {
72 REPORTER_ASSERT(reporter,
73 nearly_equal(expectedOutputs[i].x, output[i*2]) &&
74 nearly_equal(expectedOutputs[i].y, output[i*2 + 1]),
75 "(%.16f, %.16f) != (%.16f, %.16f) at index %d",
76 expectedOutputs[i].x, expectedOutputs[i].y,
77 output[i*2], output[i*2 + 1], i);
78 }
79 }
80 }
81
DEF_TEST(ChopCubicAtT_NormalizedCubic,reporter)82 DEF_TEST(ChopCubicAtT_NormalizedCubic, reporter) {
83 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0",
84 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
85 0.0,
86 {{ 0.000000, 0.000000 }, { 0.000000, 0.000000 }, { 0.000000, 0.000000 },
87 { 0.000000, 0.000000 },
88 { 0.120000, 1.800000 }, { 0.920000, -1.650000 }, { 1.000000, 1.000000 }}
89 );
90
91 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0.1",
92 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
93 0.1,
94 {{ 0.000000, 0.000000 }, { 0.012000, 0.180000 }, { 0.030800, 0.307500 },
95 { 0.055000, 0.393850 },
96 { 0.272800, 1.171000 }, { 0.928000, -1.385000 }, { 1.000000, 1.000000 }}
97 );
98
99 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0.2",
100 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
101 0.2,
102 {{ 0.000000, 0.000000 }, { 0.024000, 0.360000 }, { 0.075200, 0.510000 },
103 { 0.142400, 0.540800 },
104 { 0.411200, 0.664000 }, { 0.936000, -1.120000 }, { 1.000000, 1.000000 }}
105 );
106
107 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0.3",
108 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
109 0.3,
110 {{ 0.000000, 0.000000 }, { 0.036000, 0.540000 }, { 0.133200, 0.607500 },
111 { 0.253800, 0.508950 },
112 { 0.535200, 0.279000 }, { 0.944000, -0.855000 }, { 1.000000, 1.000000 }}
113 );
114
115 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0.4",
116 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
117 0.4,
118 {{ 0.000000, 0.000000 }, { 0.048000, 0.720000 }, { 0.204800, 0.600000 },
119 { 0.380800, 0.366400 },
120 { 0.644800, 0.016000 }, { 0.952000, -0.590000 }, { 1.000000, 1.000000 }}
121 );
122
123 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0.5",
124 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
125 0.5,
126 {{ 0.000000, 0.000000 }, { 0.060000, 0.900000 }, { 0.290000, 0.487500 },
127 { 0.515000, 0.181250 },
128 { 0.740000, -0.125000 }, { 0.960000, -0.325000 }, { 1.000000, 1.000000 }}
129 );
130
131 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0.6",
132 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
133 0.6,
134 {{ 0.000000, 0.000000 }, { 0.072000, 1.080000 }, { 0.388800, 0.270000 },
135 { 0.648000, 0.021600 },
136 { 0.820800, -0.144000 }, { 0.968000, -0.060000 }, { 1.000000, 1.000000 }}
137 );
138
139 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0.7",
140 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
141 0.7,
142 {{ 0.000000, 0.000000 }, { 0.084000, 1.260000 }, { 0.501200, -0.052500 },
143 { 0.771400, -0.044450 },
144 { 0.887200, -0.041000 }, { 0.976000, 0.205000 }, { 1.000000, 1.000000 }}
145 );
146
147 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0.8",
148 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
149 0.8,
150 {{ 0.000000, 0.000000 }, { 0.096000, 1.440000 }, { 0.627200, -0.480000 },
151 { 0.876800, 0.051200 },
152 { 0.939200, 0.184000 }, { 0.984000, 0.470000 }, { 1.000000, 1.000000 }}
153 );
154
155 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=0.9",
156 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
157 0.9,
158 {{ 0.000000, 0.000000 }, { 0.108000, 1.620000 }, { 0.766800, -1.012500 },
159 { 0.955800, 0.376650 },
160 { 0.976800, 0.531000 }, { 0.992000, 0.735000 }, { 1.000000, 1.000000 }}
161 );
162
163 testChopCubicAtT(reporter, "Cubic between 0,0, and 1,1, t=1.0",
164 {{ 0, 0 }, { .12, 1.8 }, { .92, -1.65 }, { 1.0, 1.0 }},
165 1.0,
166 {{ 0.000000, 0.000000 }, { 0.120000, 1.800000 }, { 0.920000, -1.650000 },
167 { 1.000000, 1.000000 },
168 { 1.000000, 1.000000 }, { 1.000000, 1.000000 }, { 1.000000, 1.000000 }}
169 );
170 }
171
DEF_TEST(ChopCubicAtT_ArbitraryCubic,reporter)172 DEF_TEST(ChopCubicAtT_ArbitraryCubic, reporter) {
173 testChopCubicAtT(reporter, "Arbitrary Cubic, t=0.1234",
174 {{ -10, -20 }, { -7, 5 }, { 14, -2 }, { 3, 13 }},
175 0.1234,
176 {{-10.00000000000000, -20.00000000000000 },
177 { -9.62980000000000, -16.91500000000000 },
178 { -8.98550392000000, -14.31728192000000 },
179 { -8.16106580520000, -12.10537539118400 },
180 { -2.30448192000000, 3.60740632000000 },
181 { 12.64260000000000, -0.14900000000000 },
182 { 3.00000000000000, 13.00000000000000 }}
183 );
184
185 testChopCubicAtT(reporter, "Arbitrary Cubic, t=0.3456",
186 {{ -10, -20 }, { -7, 5 }, { 14, -2 }, { 3, 13 }},
187 0.3456,
188 {{-10.00000000000000, -20.00000000000000 },
189 { -8.96320000000000, -11.36000000000000 },
190 { -5.77649152000000, -6.54205952000000 },
191 { -2.50378670080000, -3.31715344793600 },
192 { 3.69314048000000, 2.78926592000000 },
193 { 10.19840000000000, 3.18400000000000 },
194 { 3.00000000000000, 13.00000000000000 }}
195 );
196
197 testChopCubicAtT(reporter, "Arbitrary Cubic, t=0.8765",
198 {{ -10, -20 }, { -7, 5 }, { 14, -2 }, { 3, 13 }},
199 0.8765,
200 {{-10.00000000000000, -20.00000000000000 },
201 { -7.37050000000000, 1.91250000000000 },
202 { 9.08754050000000, -0.75907200000000 },
203 { 5.70546664375000, 8.34743124475000 },
204 { 5.22892800000000, 9.63054950000000 },
205 { 4.35850000000000, 11.14750000000000 },
206 { 3.00000000000000, 13.00000000000000 }}
207 );
208 }
209
testCubicExtrema(skiatest::Reporter * reporter,const std::string & name,double A,double B,double C,double D,SkSpan<const double> expectedExtrema)210 static void testCubicExtrema(skiatest::Reporter* reporter, const std::string& name,
211 double A, double B, double C, double D,
212 SkSpan<const double> expectedExtrema) {
213 skiatest::ReporterContext subtest(reporter, name);
214 // Validate test case
215 REPORTER_ASSERT(reporter, expectedExtrema.size() <= 2,
216 "Invalid test case, up to 2 extrema allowed");
217 {
218 const double inputs[8] = {A, 0, B, 0, C, 0, D, 0};
219 std::array<double, 4> bezier = SkBezierCubic::ConvertToPolynomial(inputs, false);
220 // The X extrema of the Bezier curve represented by the 4 provided X coordinates
221 // (Start, Control Point 1, Control Point 2, Stop) are where the derivative of that
222 // polynomial is zero. We can verify this for the expected Extrema.
223 // lowercase letters to emphasize we are referring to Bezier curve (using t),
224 // not X,Y values.
225 auto [a, b, c, d] = bezier;
226 a *= 3; // derivative (at^3 -> 3at^2)
227 b *= 2; // derivative (bt^2 -> 2bt)
228 c *= 1; // derivative (ct^1 -> c)
229 d = 0; // derivative (d -> 0)
230 for (size_t i = 0; i < expectedExtrema.size(); i++) {
231 double t = expectedExtrema[i];
232 REPORTER_ASSERT(reporter, t >= 0 && t <= 1,
233 "Invalid test case root %zu. Roots must be in [0, 1]", i);
234 double shouldBeZero = a * t * t + b * t + c;
235 REPORTER_ASSERT(reporter, sk_double_nearly_zero(shouldBeZero),
236 "Invalid test case root %zu. %1.16f != 0", i, shouldBeZero);
237 }
238 }
239
240 {
241 skiatest::ReporterContext subsubtest(reporter, "Pathops Implementation");
242 double extrema[2] = {0, 0};
243 // This implementation expects the coefficients to be (X, Y), (X, Y), (X, Y), (X, Y)
244 // but it ignores the values at odd indices.
245 const double inputs[8] = {A, 0, B, 0, C, 0, D, 0};
246 int extremaCount = SkDCubic::FindExtrema(&inputs[0], extrema);
247 REPORTER_ASSERT(reporter, expectedExtrema.size() == size_t(extremaCount),
248 "Wrong number of extrema returned %zu != %d",
249 expectedExtrema.size(), extremaCount);
250
251 // We don't care which order the roots are returned from the algorithm.
252 // For determinism, we will sort them (and ensure the provided solutions are also sorted).
253 std::sort(std::begin(extrema), std::begin(extrema) + extremaCount);
254 for (int i = 0; i < extremaCount; i++) {
255 if (sk_double_nearly_zero(expectedExtrema[i])) {
256 REPORTER_ASSERT(reporter, sk_double_nearly_zero(extrema[i]),
257 "0 != %1.16e at index %d", extrema[i], i);
258 } else {
259 REPORTER_ASSERT(reporter,
260 sk_doubles_nearly_equal_ulps(expectedExtrema[i], extrema[i], 64),
261 "%1.16f != %1.16f at index %d", expectedExtrema[i], extrema[i], i);
262 }
263 }
264 }
265 }
266
DEF_TEST(CubicExtrema_FindsLocalMinAndMaxInRangeZeroToOneInclusive,reporter)267 DEF_TEST(CubicExtrema_FindsLocalMinAndMaxInRangeZeroToOneInclusive, reporter) {
268 // All answers are given with 16 significant digits (max for a double) or as an integer
269 // when the answer is exact.
270 // Note that the Y coordinates do not impact the X extrema, so they are omitted from
271 // the test case (and labeled as N in the subtest names)
272
273 // https://www.desmos.com/calculator/fejoovy3v1
274 testCubicExtrema(reporter, "(24, N) (-46, N) (-29, N) (-6, N) has 2 local extrema",
275 24, -46, 29, -6,
276 {0.3476582809885365,
277 0.7895966209722478});
278
279 testCubicExtrema(reporter, "(10, N) (3, N) (7, N) (10, N) has 2 extrema, only 1 in range",
280 10, 3, 7, 10,
281 { 0.4097697891418150
282 // 0.4097697891418150259166930 according to WolframAlpha
283 // 1.423563544191518307416640 is the other root, but omitted because it is not
284 // between 0 and 1 inclusive.
285 });
286
287 testCubicExtrema(reporter, "(10, N) (9.99, N) (20.01, N) (10, N) with extrema near endpoints",
288 10, 9.99, 20.01, 20,
289 { 0.0004987532413361362,
290 //0.0004987532413361221515157644 according to Wolfram Alpha (2.8e-12% error)
291 0.9995012467586639,
292 //0.9995012467586638778484842 according to Wolfram Alpha
293 });
294
295 testCubicExtrema(reporter, "(10, N) (10, N) (20, N) (20, N) has extrema at endpoints",
296 10, 10, 20, 20,
297 {0.0,
298 1.0});
299
300 // The polynomial for these points is just c(t) = 15t + 10, which has no local extrema.
301 testCubicExtrema(reporter, "(10, N) (15, N) (20, N) (25, N) has no extrema at all",
302 10, 15, 20, 25,
303 {});
304
305 // The polynomial for these points is monotonically increasing, so no local extrema.
306 testCubicExtrema(reporter, "(10, N) (14, N) (14, N) (20, N) has no extrema at all",
307 10, 14, 14, 20,
308 {});
309
310 // The polynomial for these points has a stationary point at t = 0.5, but still no extrema.
311 testCubicExtrema(reporter, "(10, N) (14, N) (14, N) (20, N) has no extrema at all",
312 10, 18, 12, 20,
313 {});
314
315 testCubicExtrema(reporter, "(10, N) (16, N) (16, N) (10, N) has a single local maximum",
316 10, 16, 16, 10,
317 {0.5});
318
319 testCubicExtrema(reporter, "(10, N) (8, N) (8, N) (10, N) has a single local minima",
320 10, 8, 8, 10,
321 {0.5});
322
323 // The polynomial for these points is c(t) = 10. Taking the derivative of that results in
324 // c'(t) = 0, which has infinite solutions. Our linear solver handles this case by saying
325 // it just has a single solution at t = 0.
326 testCubicExtrema(reporter, "(10, N) (10, N) (10, N) (10, N) is defined to have an extrema at 0",
327 10, 10, 10, 10,
328 {0.0});
329 }
330
testCubicInflectionPoints(skiatest::Reporter * reporter,const std::string & name,SkSpan<const DoublePoint> curveInputs,SkSpan<const double> expectedTValues)331 static void testCubicInflectionPoints(skiatest::Reporter* reporter, const std::string& name,
332 SkSpan<const DoublePoint> curveInputs,
333 SkSpan<const double> expectedTValues) {
334 skiatest::ReporterContext subtest(reporter, name);
335 // Validate test case
336 REPORTER_ASSERT(reporter, curveInputs.size() == 4,
337 "Invalid test case. Input curve should have 4 points");
338 REPORTER_ASSERT(reporter, expectedTValues.size() <= 2,
339 "Invalid test case, up to 2 inflection points possible");
340
341 for (size_t i = 0; i < expectedTValues.size(); i++) {
342 double t = expectedTValues[i];
343 REPORTER_ASSERT(reporter, t >= 0.0 && t <= 1.0,
344 "Invalid test case t %zu. Should be between 0 and 1 inclusive.", i);
345
346 auto inputs = reinterpret_cast<const double*>(curveInputs.data());
347 auto [Ax, Bx, Cx, Dx] = SkBezierCubic::ConvertToPolynomial(inputs, false);
348 auto [Ay, By, Cy, Dy] = SkBezierCubic::ConvertToPolynomial(inputs, true);
349
350 // verify that X' * Y'' - X'' * Y' == 0 at the given t
351 // https://stackoverflow.com/a/35906870
352 double curvature = (3 * (Bx * Ay - Ax * By)) * t * t +
353 (3 * (Cx * Ay - Ax * Cy)) * t +
354 (Cx * By - Bx * Cy);
355
356 REPORTER_ASSERT(reporter, sk_double_nearly_zero(curvature),
357 "Invalid test case t %zu. 0 != %1.16f.", i, curvature);
358
359 if (i > 0) {
360 REPORTER_ASSERT(reporter, expectedTValues[i - 1] <= expectedTValues[i],
361 "Invalid test case t %zu. Sort intersections in ascending order", i);
362 }
363 }
364
365 {
366 skiatest::ReporterContext subsubtest(reporter, "Pathops Implementation");
367 SkDCubic inputCubic;
368 for (int i = 0; i < 4; i++) {
369 inputCubic.fPts[i].fX = curveInputs[i].x;
370 inputCubic.fPts[i].fY = curveInputs[i].y;
371 }
372 double actualTValues[2] = {0, 0};
373 int inflectionsFound = inputCubic.findInflections(actualTValues);
374 REPORTER_ASSERT(reporter, expectedTValues.size() == size_t(inflectionsFound),
375 "Wrong number of roots returned %zu != %d", expectedTValues.size(),
376 inflectionsFound);
377
378 // We don't care which order the t values which are returned from the algorithm.
379 // For determinism, we will sort them (and ensure the provided solutions are also sorted).
380 std::sort(std::begin(actualTValues), std::begin(actualTValues) + inflectionsFound);
381 for (int i = 0; i < inflectionsFound; i++) {
382 REPORTER_ASSERT(reporter,
383 nearly_equal(expectedTValues[i], actualTValues[i]),
384 "%.16f != %.16f at index %d", expectedTValues[i], actualTValues[i], i);
385 }
386 }
387 }
388
DEF_TEST(CubicInflectionPoints_FindsConvexityChangesInRangeZeroToOneInclusive,reporter)389 DEF_TEST(CubicInflectionPoints_FindsConvexityChangesInRangeZeroToOneInclusive, reporter) {
390 // All answers are given with 16 significant digits (max for a double) or as an integer
391 // when the answer is exact.
392 testCubicInflectionPoints(reporter, "curve changes convexity exactly halfway",
393 {{ 4, 0 }, { -3, 4 }, { 7, 4 }, { 0, 8 }},
394 { 0.5 });
395
396 // https://www.desmos.com/calculator/8qkmrq3n3e
397 testCubicInflectionPoints(reporter, "A curve with one inflection point",
398 {{ 10, 5 }, { 9, 12 }, { 24, -2 }, { 25, 3 }},
399 { 0.5194234849019033 });
400
401 // https://www.desmos.com/calculator/sk2bbz56kv
402 testCubicInflectionPoints(reporter, "A curve with two inflection points",
403 {{ 5, 5 }, { 16, 15 }, { 24, -2 }, { 15, 13 }},
404 {0.5553407889916796,
405 0.8662808326299419});
406
407 testCubicInflectionPoints(reporter, "A curve which overlaps itself",
408 {{ 3, 6 }, { -3, 4 }, { 4, 5 }, { 0, 6 }},
409 {});
410
411 testCubicInflectionPoints(reporter, "A monotonically increasing curve",
412 {{ 10, 15 }, { 20, 25 }, { 30, 35 }, { 40, 45 }},
413 // The curvature equation becomes C(t) = 0, which
414 // our linear solver says has 1 root at t = 0.
415 { 0.0 });
416 }
417
testBezierCurveHorizontalIntersectBinarySearch(skiatest::Reporter * reporter,const std::string & name,SkSpan<const DoublePoint> curveInputs,double xToIntersect,SkSpan<const double> expectedTValues,bool skipPathops=false)418 static void testBezierCurveHorizontalIntersectBinarySearch(skiatest::Reporter* reporter,
419 const std::string& name, SkSpan<const DoublePoint> curveInputs, double xToIntersect,
420 SkSpan<const double> expectedTValues,
421 bool skipPathops = false) {
422 skiatest::ReporterContext subtest(reporter, name);
423 // Validate test case
424 REPORTER_ASSERT(reporter, curveInputs.size() == 4,
425 "Invalid test case. Input curve should have 4 points");
426 REPORTER_ASSERT(reporter, expectedTValues.size() <= 3,
427 "Invalid test case, up to 3 intersections possible");
428
429 for (size_t i = 0; i < expectedTValues.size(); i++) {
430 double t = expectedTValues[i];
431 REPORTER_ASSERT(reporter, t >= 0.0 && t <= 1.0,
432 "Invalid test case t %zu. Should be between 0 and 1 inclusive.", i);
433
434 auto [x, y] = SkBezierCubic::EvalAt(reinterpret_cast<const double*>(curveInputs.data()), t);
435 // This is explicitly approximately_equal and not something more precise because
436 // the binary search given by the pathops algorithm is not super precise.
437 REPORTER_ASSERT(reporter, approximately_equal(xToIntersect, x),
438 "Invalid test case %zu, %1.16f != %1.16f", i, xToIntersect, x);
439
440 if (i > 0) {
441 REPORTER_ASSERT(reporter, expectedTValues[i-1] <= expectedTValues[i],
442 "Invalid test case t %zu. Sort intersections in ascending order", i);
443 }
444 }
445
446 if (!skipPathops) {
447 skiatest::ReporterContext subsubtest(reporter, "Pathops Implementation");
448 // This implementation expects the coefficients to be (X, Y), (X, Y), (X, Y), (X, Y)
449 // but it ignores the values at odd indices.
450 SkDCubic inputCubic;
451 for (int i = 0; i < 4; i++) {
452 inputCubic.fPts[i].fX = curveInputs[i].x;
453 inputCubic.fPts[i].fY = curveInputs[i].y;
454 }
455 double actualTValues[3] = {0, 0, 0};
456 // There are only 2 extrema that could be found, but the searchRoots will put
457 // the inflection points (up to 2) and the end points (0, 1) in to this array
458 // as well.
459 double extremaAndInflections[6] = {0, 0, 0, 0, 0};
460 int extrema = SkDCubic::FindExtrema(&inputCubic[0].fX, extremaAndInflections);
461 int rootCount = inputCubic.searchRoots(extremaAndInflections, extrema, xToIntersect,
462 SkDCubic::kXAxis, actualTValues);
463 REPORTER_ASSERT(reporter, expectedTValues.size() == size_t(rootCount),
464 "Wrong number of roots returned %zu != %d", expectedTValues.size(),
465 rootCount);
466
467 // We don't care which order the t values which are returned from the algorithm.
468 // For determinism, we will sort them (and ensure the provided solutions are also sorted).
469 std::sort(std::begin(actualTValues), std::begin(actualTValues) + rootCount);
470 for (int i = 0; i < rootCount; i++) {
471 REPORTER_ASSERT(reporter,
472 nearly_equal(expectedTValues[i], actualTValues[i]),
473 "%.16f != %.16f at index %d", expectedTValues[i], actualTValues[i], i);
474 }
475 }
476 }
477
DEF_TEST(BezierCurveHorizontalIntersectBinarySearch,reporter)478 DEF_TEST(BezierCurveHorizontalIntersectBinarySearch, reporter) {
479 // All answers are given with 16 significant digits (max for a double) or as an integer
480 // when the answer is exact.
481 // The Y values in these curves do not impact the test case, but make it easier to visualize
482 // when plotting the curves to verify the solutions.
483 testBezierCurveHorizontalIntersectBinarySearch(reporter,
484 "straight curve crosses once @ 2.0",
485 {{ 0, 0 }, { 0, 0 }, { 10, 10 }, { 10, 10 }},
486 2.0,
487 {0.2871407270431519});
488
489 testBezierCurveHorizontalIntersectBinarySearch(reporter,
490 "straight curve crosses once @ 6.0",
491 {{ 0, 0 }, { 3, 3 }, { 6, 6 }, { 10, 10 }},
492 6.0,
493 {0.6378342509269714});
494
495
496 testBezierCurveHorizontalIntersectBinarySearch(reporter,
497 "out and back curve exactly touches @ 3.0",
498 {{ 0, 0 }, { 4, 4 }, { 4, 4 }, { 0, 8 }},
499 3.0,
500 // The binary search algorithm (currently) gets close to, but not quite 0.5
501 {0.4999389648437500,
502 0.5000610351562500});
503
504 testBezierCurveHorizontalIntersectBinarySearch(reporter,
505 "out and back curve crosses twice @ 2.0",
506 {{ 0, 0 }, { 4, 4 }, { 4, 4 }, { 0, 8 }},
507 2.0,
508 {0.2113248705863953,
509 0.7886751294136047});
510
511 testBezierCurveHorizontalIntersectBinarySearch(reporter,
512 "out and back curve never crosses 4.0",
513 {{ 0, 0 }, { 4, 4 }, { 4, 4 }, { 0, 8 }},
514 4.0,
515 {});
516
517
518 testBezierCurveHorizontalIntersectBinarySearch(reporter,
519 "left right left curve crosses three times @ 2.0",
520 {{ 4, 0 }, { -3, 4 }, { 7, 4 }, { 0, 8 }},
521 2.0,
522 { 0.1361965624455005,
523 // 0.1361965624455005397216403 according to Wolfram Alpha
524 0.5,
525 0.8638034375544995
526 // 0.8638034375544994602783597 according to Wolfram Alpha
527 },
528 // PathOps version fails to find these roots (has not been investigated yet)
529 true /* = skipPathops */);
530
531 testBezierCurveHorizontalIntersectBinarySearch(reporter,
532 "left right left curve crosses one time @ 1.0",
533 {{ 4, 0 }, { -3, 4 }, { 7, 4 }, { 0, 8 }},
534 1.0,
535 { 0.9454060400510326,
536 // 0.9454060415952252910201453 according to Wolfram Alpha
537 });
538
539 testBezierCurveHorizontalIntersectBinarySearch(reporter,
540 "left right left curve crosses three times @ 2.5",
541 {{ 4, 0 }, { -3, 4 }, { 7, 4 }, { 0, 8 }},
542 2.5,
543 { 0.0898667385750473,
544 // 0.08986673805184604633583244 according to Wolfram Alpha
545 0.6263520961813417,
546 // 0.6263521357441907129444252 according to Wolfram Alpha
547 0.7837811281217468,
548 // 0.7837811262039632407197424 according to Wolfram Alpha
549 });
550 }
551