1 /*
2 * Copyright 2011 Google Inc.
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 "SkGeometry.h"
9 #include "SkPointPriv.h"
10 #include "SkRandom.h"
11 #include "Test.h"
12 #include <array>
13 #include <numeric>
14
nearly_equal(const SkPoint & a,const SkPoint & b)15 static bool nearly_equal(const SkPoint& a, const SkPoint& b) {
16 return SkScalarNearlyEqual(a.fX, b.fX) && SkScalarNearlyEqual(a.fY, b.fY);
17 }
18
testChopCubic(skiatest::Reporter * reporter)19 static void testChopCubic(skiatest::Reporter* reporter) {
20 /*
21 Inspired by this test, which used to assert that the tValues had dups
22
23 <path stroke="#202020" d="M0,0 C0,0 1,1 2190,5130 C2190,5070 2220,5010 2205,4980" />
24 */
25 const SkPoint src[] = {
26 { SkIntToScalar(2190), SkIntToScalar(5130) },
27 { SkIntToScalar(2190), SkIntToScalar(5070) },
28 { SkIntToScalar(2220), SkIntToScalar(5010) },
29 { SkIntToScalar(2205), SkIntToScalar(4980) },
30 };
31 SkPoint dst[13];
32 SkScalar tValues[3];
33 // make sure we don't assert internally
34 int count = SkChopCubicAtMaxCurvature(src, dst, tValues);
35 if (false) { // avoid bit rot, suppress warning
36 REPORTER_ASSERT(reporter, count);
37 }
38 }
39
check_pairs(skiatest::Reporter * reporter,int index,SkScalar t,const char name[],SkScalar x0,SkScalar y0,SkScalar x1,SkScalar y1)40 static void check_pairs(skiatest::Reporter* reporter, int index, SkScalar t, const char name[],
41 SkScalar x0, SkScalar y0, SkScalar x1, SkScalar y1) {
42 bool eq = SkScalarNearlyEqual(x0, x1) && SkScalarNearlyEqual(y0, y1);
43 if (!eq) {
44 SkDebugf("%s [%d %g] p0 [%10.8f %10.8f] p1 [%10.8f %10.8f]\n",
45 name, index, t, x0, y0, x1, y1);
46 REPORTER_ASSERT(reporter, eq);
47 }
48 }
49
test_evalquadat(skiatest::Reporter * reporter)50 static void test_evalquadat(skiatest::Reporter* reporter) {
51 SkRandom rand;
52 for (int i = 0; i < 1000; ++i) {
53 SkPoint pts[3];
54 for (int j = 0; j < 3; ++j) {
55 pts[j].set(rand.nextSScalar1() * 100, rand.nextSScalar1() * 100);
56 }
57 const SkScalar dt = SK_Scalar1 / 128;
58 SkScalar t = dt;
59 for (int j = 1; j < 128; ++j) {
60 SkPoint r0;
61 SkEvalQuadAt(pts, t, &r0);
62 SkPoint r1 = SkEvalQuadAt(pts, t);
63 check_pairs(reporter, i, t, "quad-pos", r0.fX, r0.fY, r1.fX, r1.fY);
64
65 SkVector v0;
66 SkEvalQuadAt(pts, t, nullptr, &v0);
67 SkVector v1 = SkEvalQuadTangentAt(pts, t);
68 check_pairs(reporter, i, t, "quad-tan", v0.fX, v0.fY, v1.fX, v1.fY);
69
70 t += dt;
71 }
72 }
73 }
74
test_conic_eval_pos(skiatest::Reporter * reporter,const SkConic & conic,SkScalar t)75 static void test_conic_eval_pos(skiatest::Reporter* reporter, const SkConic& conic, SkScalar t) {
76 SkPoint p0, p1;
77 conic.evalAt(t, &p0, nullptr);
78 p1 = conic.evalAt(t);
79 check_pairs(reporter, 0, t, "conic-pos", p0.fX, p0.fY, p1.fX, p1.fY);
80 }
81
test_conic_eval_tan(skiatest::Reporter * reporter,const SkConic & conic,SkScalar t)82 static void test_conic_eval_tan(skiatest::Reporter* reporter, const SkConic& conic, SkScalar t) {
83 SkVector v0, v1;
84 conic.evalAt(t, nullptr, &v0);
85 v1 = conic.evalTangentAt(t);
86 check_pairs(reporter, 0, t, "conic-tan", v0.fX, v0.fY, v1.fX, v1.fY);
87 }
88
test_conic(skiatest::Reporter * reporter)89 static void test_conic(skiatest::Reporter* reporter) {
90 SkRandom rand;
91 for (int i = 0; i < 1000; ++i) {
92 SkPoint pts[3];
93 for (int j = 0; j < 3; ++j) {
94 pts[j].set(rand.nextSScalar1() * 100, rand.nextSScalar1() * 100);
95 }
96 for (int k = 0; k < 10; ++k) {
97 SkScalar w = rand.nextUScalar1() * 2;
98 SkConic conic(pts, w);
99
100 const SkScalar dt = SK_Scalar1 / 128;
101 SkScalar t = dt;
102 for (int j = 1; j < 128; ++j) {
103 test_conic_eval_pos(reporter, conic, t);
104 test_conic_eval_tan(reporter, conic, t);
105 t += dt;
106 }
107 }
108 }
109 }
110
test_quad_tangents(skiatest::Reporter * reporter)111 static void test_quad_tangents(skiatest::Reporter* reporter) {
112 SkPoint pts[] = {
113 {10, 20}, {10, 20}, {20, 30},
114 {10, 20}, {15, 25}, {20, 30},
115 {10, 20}, {20, 30}, {20, 30},
116 };
117 int count = (int) SK_ARRAY_COUNT(pts) / 3;
118 for (int index = 0; index < count; ++index) {
119 SkConic conic(&pts[index * 3], 0.707f);
120 SkVector start = SkEvalQuadTangentAt(&pts[index * 3], 0);
121 SkVector mid = SkEvalQuadTangentAt(&pts[index * 3], .5f);
122 SkVector end = SkEvalQuadTangentAt(&pts[index * 3], 1);
123 REPORTER_ASSERT(reporter, start.fX && start.fY);
124 REPORTER_ASSERT(reporter, mid.fX && mid.fY);
125 REPORTER_ASSERT(reporter, end.fX && end.fY);
126 REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid)));
127 REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end)));
128 }
129 }
130
test_conic_tangents(skiatest::Reporter * reporter)131 static void test_conic_tangents(skiatest::Reporter* reporter) {
132 SkPoint pts[] = {
133 { 10, 20}, {10, 20}, {20, 30},
134 { 10, 20}, {15, 25}, {20, 30},
135 { 10, 20}, {20, 30}, {20, 30}
136 };
137 int count = (int) SK_ARRAY_COUNT(pts) / 3;
138 for (int index = 0; index < count; ++index) {
139 SkConic conic(&pts[index * 3], 0.707f);
140 SkVector start = conic.evalTangentAt(0);
141 SkVector mid = conic.evalTangentAt(.5f);
142 SkVector end = conic.evalTangentAt(1);
143 REPORTER_ASSERT(reporter, start.fX && start.fY);
144 REPORTER_ASSERT(reporter, mid.fX && mid.fY);
145 REPORTER_ASSERT(reporter, end.fX && end.fY);
146 REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid)));
147 REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end)));
148 }
149 }
150
test_this_conic_to_quad(skiatest::Reporter * r,const SkPoint pts[3],SkScalar w)151 static void test_this_conic_to_quad(skiatest::Reporter* r, const SkPoint pts[3], SkScalar w) {
152 SkAutoConicToQuads quadder;
153 const SkPoint* qpts = quadder.computeQuads(pts, w, 0.25);
154 const int qcount = quadder.countQuads();
155 const int pcount = qcount * 2 + 1;
156
157 REPORTER_ASSERT(r, SkPointPriv::AreFinite(qpts, pcount));
158 }
159
160 /**
161 * We need to ensure that when a conic is approximated by quads, that we always return finite
162 * values in the quads.
163 *
164 * Inspired by crbug_627414
165 */
test_conic_to_quads(skiatest::Reporter * reporter)166 static void test_conic_to_quads(skiatest::Reporter* reporter) {
167 const SkPoint triples[] = {
168 { 0, 0 }, { 1, 0 }, { 1, 1 },
169 { 0, 0 }, { 3.58732e-43f, 2.72084f }, { 3.00392f, 3.00392f },
170 { 0, 0 }, { 100000, 0 }, { 100000, 100000 },
171 { 0, 0 }, { 1e30f, 0 }, { 1e30f, 1e30f },
172 };
173 const int N = sizeof(triples) / sizeof(SkPoint);
174
175 for (int i = 0; i < N; i += 3) {
176 const SkPoint* pts = &triples[i];
177
178 SkRect bounds;
179 bounds.set(pts, 3);
180
181 SkScalar w = 1e30f;
182 do {
183 w *= 2;
184 test_this_conic_to_quad(reporter, pts, w);
185 } while (SkScalarIsFinite(w));
186 test_this_conic_to_quad(reporter, pts, SK_ScalarNaN);
187 }
188 }
189
test_cubic_tangents(skiatest::Reporter * reporter)190 static void test_cubic_tangents(skiatest::Reporter* reporter) {
191 SkPoint pts[] = {
192 { 10, 20}, {10, 20}, {20, 30}, {30, 40},
193 { 10, 20}, {15, 25}, {20, 30}, {30, 40},
194 { 10, 20}, {20, 30}, {30, 40}, {30, 40},
195 };
196 int count = (int) SK_ARRAY_COUNT(pts) / 4;
197 for (int index = 0; index < count; ++index) {
198 SkConic conic(&pts[index * 3], 0.707f);
199 SkVector start, mid, end;
200 SkEvalCubicAt(&pts[index * 4], 0, nullptr, &start, nullptr);
201 SkEvalCubicAt(&pts[index * 4], .5f, nullptr, &mid, nullptr);
202 SkEvalCubicAt(&pts[index * 4], 1, nullptr, &end, nullptr);
203 REPORTER_ASSERT(reporter, start.fX && start.fY);
204 REPORTER_ASSERT(reporter, mid.fX && mid.fY);
205 REPORTER_ASSERT(reporter, end.fX && end.fY);
206 REPORTER_ASSERT(reporter, SkScalarNearlyZero(start.cross(mid)));
207 REPORTER_ASSERT(reporter, SkScalarNearlyZero(mid.cross(end)));
208 }
209 }
210
check_cubic_type(skiatest::Reporter * reporter,const std::array<SkPoint,4> & bezierPoints,SkCubicType expectedType,bool undefined=false)211 static void check_cubic_type(skiatest::Reporter* reporter,
212 const std::array<SkPoint, 4>& bezierPoints, SkCubicType expectedType,
213 bool undefined = false) {
214 // Classify the cubic even if the results will be undefined: check for crashes and asserts.
215 SkCubicType actualType = SkClassifyCubic(bezierPoints.data());
216 if (!undefined) {
217 REPORTER_ASSERT(reporter, actualType == expectedType);
218 }
219 }
220
check_cubic_around_rect(skiatest::Reporter * reporter,float x1,float y1,float x2,float y2,bool undefined=false)221 static void check_cubic_around_rect(skiatest::Reporter* reporter,
222 float x1, float y1, float x2, float y2,
223 bool undefined = false) {
224 static constexpr SkCubicType expectations[24] = {
225 SkCubicType::kLoop,
226 SkCubicType::kCuspAtInfinity,
227 SkCubicType::kLocalCusp,
228 SkCubicType::kLocalCusp,
229 SkCubicType::kCuspAtInfinity,
230 SkCubicType::kLoop,
231 SkCubicType::kCuspAtInfinity,
232 SkCubicType::kLoop,
233 SkCubicType::kCuspAtInfinity,
234 SkCubicType::kLoop,
235 SkCubicType::kLocalCusp,
236 SkCubicType::kLocalCusp,
237 SkCubicType::kLocalCusp,
238 SkCubicType::kLocalCusp,
239 SkCubicType::kLoop,
240 SkCubicType::kCuspAtInfinity,
241 SkCubicType::kLoop,
242 SkCubicType::kCuspAtInfinity,
243 SkCubicType::kLoop,
244 SkCubicType::kCuspAtInfinity,
245 SkCubicType::kLocalCusp,
246 SkCubicType::kLocalCusp,
247 SkCubicType::kCuspAtInfinity,
248 SkCubicType::kLoop,
249 };
250 SkPoint points[] = {{x1, y1}, {x2, y1}, {x2, y2}, {x1, y2}};
251 std::array<SkPoint, 4> bezier;
252 for (int i=0; i < 4; ++i) {
253 bezier[0] = points[i];
254 for (int j=0; j < 3; ++j) {
255 int jidx = (j < i) ? j : j+1;
256 bezier[1] = points[jidx];
257 for (int k=0, kidx=0; k < 2; ++k, ++kidx) {
258 for (int n = 0; n < 2; ++n) {
259 kidx = (kidx == i || kidx == jidx) ? kidx+1 : kidx;
260 }
261 bezier[2] = points[kidx];
262 for (int l = 0; l < 4; ++l) {
263 if (l != i && l != jidx && l != kidx) {
264 bezier[3] = points[l];
265 break;
266 }
267 }
268 check_cubic_type(reporter, bezier, expectations[i*6 + j*2 + k], undefined);
269 }
270 }
271 }
272 for (int i=0; i < 4; ++i) {
273 bezier[0] = points[i];
274 for (int j=0; j < 3; ++j) {
275 int jidx = (j < i) ? j : j+1;
276 bezier[1] = points[jidx];
277 bezier[2] = points[jidx];
278 for (int k=0, kidx=0; k < 2; ++k, ++kidx) {
279 for (int n = 0; n < 2; ++n) {
280 kidx = (kidx == i || kidx == jidx) ? kidx+1 : kidx;
281 }
282 bezier[3] = points[kidx];
283 check_cubic_type(reporter, bezier, SkCubicType::kSerpentine, undefined);
284 }
285 }
286 }
287 }
288
test_classify_cubic(skiatest::Reporter * reporter)289 static void test_classify_cubic(skiatest::Reporter* reporter) {
290 check_cubic_type(reporter, {{{149.325f, 107.705f}, {149.325f, 103.783f},
291 {151.638f, 100.127f}, {156.263f, 96.736f}}},
292 SkCubicType::kSerpentine);
293 check_cubic_type(reporter, {{{225.694f, 223.15f}, {209.831f, 224.837f},
294 {195.994f, 230.237f}, {184.181f, 239.35f}}},
295 SkCubicType::kSerpentine);
296 check_cubic_type(reporter, {{{4.873f, 5.581f}, {5.083f, 5.2783f},
297 {5.182f, 4.8593f}, {5.177f, 4.3242f}}},
298 SkCubicType::kSerpentine);
299 check_cubic_around_rect(reporter, 0, 0, 1, 1);
300 check_cubic_around_rect(reporter,
301 -std::numeric_limits<float>::max(),
302 -std::numeric_limits<float>::max(),
303 +std::numeric_limits<float>::max(),
304 +std::numeric_limits<float>::max());
305 check_cubic_around_rect(reporter, 1, 1,
306 +std::numeric_limits<float>::min(),
307 +std::numeric_limits<float>::max());
308 check_cubic_around_rect(reporter,
309 -std::numeric_limits<float>::min(),
310 -std::numeric_limits<float>::min(),
311 +std::numeric_limits<float>::min(),
312 +std::numeric_limits<float>::min());
313 check_cubic_around_rect(reporter, +1, -std::numeric_limits<float>::min(), -1, -1);
314 check_cubic_around_rect(reporter,
315 -std::numeric_limits<float>::infinity(),
316 -std::numeric_limits<float>::infinity(),
317 +std::numeric_limits<float>::infinity(),
318 +std::numeric_limits<float>::infinity(),
319 true);
320 check_cubic_around_rect(reporter, 0, 0, 1, +std::numeric_limits<float>::infinity(), true);
321 check_cubic_around_rect(reporter,
322 -std::numeric_limits<float>::quiet_NaN(),
323 -std::numeric_limits<float>::quiet_NaN(),
324 +std::numeric_limits<float>::quiet_NaN(),
325 +std::numeric_limits<float>::quiet_NaN(),
326 true);
327 check_cubic_around_rect(reporter, 0, 0, 1, +std::numeric_limits<float>::quiet_NaN(), true);
328 }
329
DEF_TEST(Geometry,reporter)330 DEF_TEST(Geometry, reporter) {
331 SkPoint pts[3], dst[5];
332
333 pts[0].set(0, 0);
334 pts[1].set(100, 50);
335 pts[2].set(0, 100);
336
337 int count = SkChopQuadAtMaxCurvature(pts, dst);
338 REPORTER_ASSERT(reporter, count == 1 || count == 2);
339
340 pts[0].set(0, 0);
341 pts[1].set(3, 0);
342 pts[2].set(3, 3);
343 SkConvertQuadToCubic(pts, dst);
344 const SkPoint cubic[] = {
345 { 0, 0, }, { 2, 0, }, { 3, 1, }, { 3, 3 },
346 };
347 for (int i = 0; i < 4; ++i) {
348 REPORTER_ASSERT(reporter, nearly_equal(cubic[i], dst[i]));
349 }
350
351 testChopCubic(reporter);
352 test_evalquadat(reporter);
353 test_conic(reporter);
354 test_cubic_tangents(reporter);
355 test_quad_tangents(reporter);
356 test_conic_tangents(reporter);
357 test_conic_to_quads(reporter);
358 test_classify_cubic(reporter);
359 }
360