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/SkQuads.h"
12 #include "src/pathops/SkPathOpsQuad.h"
13 #include "tests/Test.h"
14
15 #include <algorithm>
16 #include <cstddef>
17 #include <cfloat>
18 #include <cmath>
19 #include <iterator>
20 #include <string>
21
testQuadRootsReal(skiatest::Reporter * reporter,std::string name,double A,double B,double C,SkSpan<const double> expectedRoots)22 static void testQuadRootsReal(skiatest::Reporter* reporter, std::string name,
23 double A, double B, double C,
24 SkSpan<const double> expectedRoots) {
25 skiatest::ReporterContext subtest(reporter, name);
26 // Validate test case
27 REPORTER_ASSERT(reporter, expectedRoots.size() <= 2,
28 "Invalid test case, up to 2 roots allowed");
29
30 for (size_t i = 0; i < expectedRoots.size(); i++) {
31 double x = expectedRoots[i];
32 // A*x^2 + B*x + C should equal 0
33 double y = A * x * x + B * x + C;
34 REPORTER_ASSERT(reporter, sk_double_nearly_zero(y),
35 "Invalid test case root %zu. %.16f != 0", i, y);
36
37 if (i > 0) {
38 REPORTER_ASSERT(reporter, expectedRoots[i-1] <= expectedRoots[i],
39 "Invalid test case root %zu. Roots should be sorted in ascending order", i);
40 }
41 }
42
43 {
44 skiatest::ReporterContext subsubtest(reporter, "Pathops Implementation");
45 double roots[2] = {0, 0};
46 int rootCount = SkDQuad::RootsReal(A, B, C, roots);
47 REPORTER_ASSERT(reporter, expectedRoots.size() == size_t(rootCount),
48 "Wrong number of roots returned %zu != %d", expectedRoots.size(),
49 rootCount);
50
51 // We don't care which order the roots are returned from the algorithm.
52 // For determinism, we will sort them (and ensure the provided solutions are also sorted).
53 std::sort(std::begin(roots), std::begin(roots) + rootCount);
54 for (int i = 0; i < rootCount; i++) {
55 if (sk_double_nearly_zero(expectedRoots[i])) {
56 REPORTER_ASSERT(reporter, sk_double_nearly_zero(roots[i]),
57 "0 != %.16f at index %d", roots[i], i);
58 } else {
59 REPORTER_ASSERT(reporter,
60 sk_doubles_nearly_equal_ulps(expectedRoots[i], roots[i], 64),
61 "%.16f != %.16f at index %d", expectedRoots[i], roots[i], i);
62 }
63 }
64 }
65 {
66 skiatest::ReporterContext subsubtest(reporter, "SkQuads Implementation");
67 double roots[2] = {0, 0};
68 int rootCount = SkQuads::RootsReal(A, B, C, roots);
69 REPORTER_ASSERT(reporter, expectedRoots.size() == size_t(rootCount),
70 "Wrong number of roots returned %zu != %d", expectedRoots.size(),
71 rootCount);
72
73 // We don't care which order the roots are returned from the algorithm.
74 // For determinism, we will sort them (and ensure the provided solutions are also sorted).
75 std::sort(std::begin(roots), std::begin(roots) + rootCount);
76 for (int i = 0; i < rootCount; i++) {
77 if (sk_double_nearly_zero(expectedRoots[i])) {
78 REPORTER_ASSERT(reporter, sk_double_nearly_zero(roots[i]),
79 "0 != %.16f at index %d", roots[i], i);
80 } else {
81 REPORTER_ASSERT(reporter,
82 sk_doubles_nearly_equal_ulps(expectedRoots[i], roots[i], 64),
83 "%.16f != %.16f at index %d", expectedRoots[i], roots[i], i);
84 }
85 }
86 }
87 }
88
DEF_TEST(QuadRootsReal_ActualQuadratics,reporter)89 DEF_TEST(QuadRootsReal_ActualQuadratics, reporter) {
90 // All answers are given with 16 significant digits (max for a double) or as an integer
91 // when the answer is exact.
92 testQuadRootsReal(reporter, "two roots 3x^2 - 20x - 40",
93 3, -20, -40,
94 {-1.610798991397109,
95 //-1.610798991397108632474265 from Wolfram Alpha
96 8.277465658063775,
97 // 8.277465658063775299140932 from Wolfram Alpha
98 });
99
100 // (2x - 4)(x + 17)
101 testQuadRootsReal(reporter, "two roots 2x^2 + 30x - 68",
102 2, 30, -68,
103 {-17, 2});
104
105 testQuadRootsReal(reporter, "two roots x^2 - 5",
106 1, 0, -5,
107 {-2.236067977499790,
108 //-2.236067977499789696409174 from Wolfram Alpha
109 2.236067977499790,
110 // 2.236067977499789696409174 from Wolfram Alpha
111 });
112
113 testQuadRootsReal(reporter, "one root x^2 - 2x + 1",
114 1, -2, 1,
115 {1});
116
117 testQuadRootsReal(reporter, "no roots 5x^2 + 6x + 7",
118 5, 6, 7,
119 {});
120
121 testQuadRootsReal(reporter, "no roots 4x^2 + 1",
122 4, 0, 1,
123 {});
124
125 testQuadRootsReal(reporter, "one root is zero, another is big",
126 14, -13, 0,
127 {0,
128 0.9285714285714286
129 //0.9285714285714285714285714 from Wolfram Alpha
130 });
131
132 // Values from a failing test case observed during testing.
133 testQuadRootsReal(reporter, "one root is zero, another is small",
134 0.2929016490705016, 0.0000030451558069, 0,
135 {-0.00001039651301576329, 0});
136
137 testQuadRootsReal(reporter, "b and c are zero, a is positive 4x^2",
138 4, 0, 0,
139 {0});
140
141 testQuadRootsReal(reporter, "b and c are zero, a is negative -4x^2",
142 -4, 0, 0,
143 {0});
144
145 testQuadRootsReal(reporter, "a and b are huge, c is zero",
146 4.3719914983870202e+291, 1.0269509510194551e+152, 0,
147 // One solution is 0, the other is so close to zero it returns
148 // true for sk_double_nearly_zero, so it is collapsed into one.
149 {0});
150 }
151
DEF_TEST(QuadRootsReal_Linear,reporter)152 DEF_TEST(QuadRootsReal_Linear, reporter) {
153 testQuadRootsReal(reporter, "positive slope 5x + 6",
154 0, 5, 6,
155 {-1.2});
156
157 testQuadRootsReal(reporter, "negative slope -3x - 9",
158 0, -3, -9,
159 {-3.});
160 }
161
DEF_TEST(QuadRootsReal_Constant,reporter)162 DEF_TEST(QuadRootsReal_Constant, reporter) {
163 testQuadRootsReal(reporter, "No intersections y = -10",
164 0, 0, -10,
165 {});
166
167 testQuadRootsReal(reporter, "Infinite solutions y = 0",
168 0, 0, 0,
169 {0.});
170 }
171
DEF_TEST(QuadRootsReal_NonFiniteNumbers,reporter)172 DEF_TEST(QuadRootsReal_NonFiniteNumbers, reporter) {
173 // The Pathops implementation does not check for infinities nor nans in all cases.
174 double roots[2];
175 REPORTER_ASSERT(reporter,
176 SkQuads::RootsReal(DBL_MAX, 0, DBL_MAX, roots) == 0,
177 "Discriminant is negative infinity"
178 );
179 REPORTER_ASSERT(reporter,
180 SkQuads::RootsReal(DBL_MAX, DBL_MAX, DBL_MAX, roots) == 0,
181 "Double Overflow"
182 );
183
184 REPORTER_ASSERT(reporter,
185 SkQuads::RootsReal(1, NAN, -3, roots) == 0,
186 "Nan quadratic"
187 );
188 REPORTER_ASSERT(reporter,
189 SkQuads::RootsReal(0, NAN, 3, roots) == 0,
190 "Nan linear"
191 );
192 REPORTER_ASSERT(reporter,
193 SkQuads::RootsReal(0, 0, NAN, roots) == 0,
194 "Nan constant"
195 );
196 }
197