1 /*
2 * Copyright 2014 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 "include/core/SkPaint.h"
9 #include "include/core/SkPath.h"
10 #include "include/core/SkPathUtils.h"
11 #include "include/core/SkPoint.h"
12 #include "include/core/SkScalar.h"
13 #include "include/core/SkTypes.h"
14 #include "include/private/base/SkDebug.h"
15 #include "src/base/SkFloatBits.h"
16 #include "src/base/SkRandom.h"
17 #include "src/core/SkPointPriv.h"
18 #include "src/core/SkStrokerPriv.h"
19 #include "src/pathops/SkPathOpsCubic.h"
20 #include "src/pathops/SkPathOpsPoint.h"
21 #include "src/pathops/SkPathOpsQuad.h"
22 #include "tests/PathOpsCubicIntersectionTestData.h"
23 #include "tests/PathOpsQuadIntersectionTestData.h"
24 #include "tests/PathOpsTestCommon.h"
25 #include "tests/Test.h"
26 #include "tools/flags/CommandLineFlags.h"
27
28 #include <array>
29 #include <cfloat>
30 #include <cstddef>
31 #include <cstdint>
32
33 using namespace PathOpsCubicIntersectionTestData;
34
35 static DEFINE_bool(timeout, true, "run until alloted time expires");
36
37 #define MS_TEST_DURATION 10
38
39 const SkScalar widths[] = {-FLT_MAX, -1, -0.1f, -FLT_EPSILON, 0, FLT_EPSILON,
40 0.0000001f, 0.000001f, 0.00001f, 0.0001f, 0.001f, 0.01f,
41 0.1f, 0.2f, 0.3f, 0.4f, 0.5f, 1, 1.1f, 2, 10, 10e2f, 10e3f, 10e4f, 10e5f, 10e6f, 10e7f,
42 10e8f, 10e9f, 10e10f, 10e20f, FLT_MAX };
43 size_t widths_count = std::size(widths);
44
pathTest(const SkPath & path)45 static void pathTest(const SkPath& path) {
46 SkPaint p;
47 SkPath fill;
48 p.setStyle(SkPaint::kStroke_Style);
49 for (size_t index = 0; index < widths_count; ++index) {
50 p.setStrokeWidth(widths[index]);
51 skpathutils::FillPathWithPaint(path, p, &fill);
52 }
53 }
54
cubicTest(const SkPoint c[4])55 static void cubicTest(const SkPoint c[4]) {
56 SkPath path;
57 path.moveTo(c[0].fX, c[0].fY);
58 path.cubicTo(c[1].fX, c[1].fY, c[2].fX, c[2].fY, c[3].fX, c[3].fY);
59 pathTest(path);
60 }
61
quadTest(const SkPoint c[3])62 static void quadTest(const SkPoint c[3]) {
63 SkPath path;
64 path.moveTo(c[0].fX, c[0].fY);
65 path.quadTo(c[1].fX, c[1].fY, c[2].fX, c[2].fY);
66 pathTest(path);
67 }
68
cubicSetTest(const CubicPts * dCubic,size_t count)69 static void cubicSetTest(const CubicPts* dCubic, size_t count) {
70 skiatest::Timer timer;
71 for (size_t index = 0; index < count; ++index) {
72 const CubicPts& dPts = dCubic[index];
73 SkDCubic d;
74 d.debugSet(dPts.fPts);
75 SkPoint c[4] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
76 {(float) d[2].fX, (float) d[2].fY}, {(float) d[3].fX, (float) d[3].fY} };
77 cubicTest(c);
78 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
79 return;
80 }
81 }
82 }
83
cubicPairSetTest(const CubicPts dCubic[][2],size_t count)84 static void cubicPairSetTest(const CubicPts dCubic[][2], size_t count) {
85 skiatest::Timer timer;
86 for (size_t index = 0; index < count; ++index) {
87 for (int pair = 0; pair < 2; ++pair) {
88 const CubicPts& dPts = dCubic[index][pair];
89 SkDCubic d;
90 d.debugSet(dPts.fPts);
91 SkPoint c[4] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
92 {(float) d[2].fX, (float) d[2].fY}, {(float) d[3].fX, (float) d[3].fY} };
93 cubicTest(c);
94 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
95 return;
96 }
97 }
98 }
99 }
100
quadSetTest(const QuadPts * dQuad,size_t count)101 static void quadSetTest(const QuadPts* dQuad, size_t count) {
102 skiatest::Timer timer;
103 for (size_t index = 0; index < count; ++index) {
104 const QuadPts& dPts = dQuad[index];
105 SkDQuad d;
106 d.debugSet(dPts.fPts);
107 SkPoint c[3] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
108 {(float) d[2].fX, (float) d[2].fY} };
109 quadTest(c);
110 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
111 return;
112 }
113 }
114 }
115
quadPairSetTest(const QuadPts dQuad[][2],size_t count)116 static void quadPairSetTest(const QuadPts dQuad[][2], size_t count) {
117 skiatest::Timer timer;
118 for (size_t index = 0; index < count; ++index) {
119 for (int pair = 0; pair < 2; ++pair) {
120 const QuadPts& dPts = dQuad[index][pair];
121 SkDQuad d;
122 d.debugSet(dPts.fPts);
123 SkPoint c[3] = { {(float) d[0].fX, (float) d[0].fY}, {(float) d[1].fX, (float) d[1].fY},
124 {(float) d[2].fX, (float) d[2].fY} };
125 quadTest(c);
126 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
127 return;
128 }
129 }
130 }
131 }
132
DEF_TEST(QuadStrokerSet,reporter)133 DEF_TEST(QuadStrokerSet, reporter) {
134 quadSetTest(quadraticLines, quadraticLines_count);
135 quadSetTest(quadraticPoints, quadraticPoints_count);
136 quadSetTest(quadraticModEpsilonLines, quadraticModEpsilonLines_count);
137 quadPairSetTest(quadraticTests, quadraticTests_count);
138 }
139
DEF_TEST(CubicStrokerSet,reporter)140 DEF_TEST(CubicStrokerSet, reporter) {
141 cubicSetTest(pointDegenerates, pointDegenerates_count);
142 cubicSetTest(notPointDegenerates, notPointDegenerates_count);
143 cubicSetTest(lines, lines_count);
144 cubicSetTest(notLines, notLines_count);
145 cubicSetTest(modEpsilonLines, modEpsilonLines_count);
146 cubicSetTest(lessEpsilonLines, lessEpsilonLines_count);
147 cubicSetTest(negEpsilonLines, negEpsilonLines_count);
148 cubicPairSetTest(tests, tests_count);
149 }
150
unbounded(SkRandom & r)151 static SkScalar unbounded(SkRandom& r) {
152 uint32_t val = r.nextU();
153 return SkBits2Float(val);
154 }
155
unboundedPos(SkRandom & r)156 static SkScalar unboundedPos(SkRandom& r) {
157 uint32_t val = r.nextU() & 0x7fffffff;
158 return SkBits2Float(val);
159 }
160
DEF_TEST(QuadStrokerUnbounded,reporter)161 DEF_TEST(QuadStrokerUnbounded, reporter) {
162 SkRandom r;
163 SkPaint p;
164 p.setStyle(SkPaint::kStroke_Style);
165 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
166 int best = 0;
167 sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
168 #endif
169 skiatest::Timer timer;
170 for (int i = 0; i < 1000000; ++i) {
171 SkPath path, fill;
172 path.moveTo(unbounded(r), unbounded(r));
173 path.quadTo(unbounded(r), unbounded(r), unbounded(r), unbounded(r));
174 p.setStrokeWidth(unboundedPos(r));
175 skpathutils::FillPathWithPaint(path, p, &fill);
176 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
177 if (best < gMaxRecursion[2]) {
178 if (reporter->verbose()) {
179 SkDebugf("\n%s quad=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[2],
180 p.getStrokeWidth());
181 path.dumpHex();
182 SkDebugf("fill:\n");
183 fill.dumpHex();
184 }
185 best = gMaxRecursion[2];
186 }
187 #endif
188 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
189 return;
190 }
191 }
192 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
193 if (reporter->verbose()) {
194 SkDebugf("\n%s max quad=%d\n", __FUNCTION__, best);
195 }
196 #endif
197 }
198
DEF_TEST(CubicStrokerUnbounded,reporter)199 DEF_TEST(CubicStrokerUnbounded, reporter) {
200 SkRandom r;
201 SkPaint p;
202 p.setStyle(SkPaint::kStroke_Style);
203 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
204 int bestTan = 0;
205 int bestCubic = 0;
206 sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
207 #endif
208 skiatest::Timer timer;
209 for (int i = 0; i < 1000000; ++i) {
210 SkPath path, fill;
211 path.moveTo(unbounded(r), unbounded(r));
212 path.cubicTo(unbounded(r), unbounded(r), unbounded(r), unbounded(r),
213 unbounded(r), unbounded(r));
214 p.setStrokeWidth(unboundedPos(r));
215 skpathutils::FillPathWithPaint(path, p, &fill);
216 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
217 if (bestTan < gMaxRecursion[0] || bestCubic < gMaxRecursion[1]) {
218 if (reporter->verbose()) {
219 SkDebugf("\n%s tan=%d cubic=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[0],
220 gMaxRecursion[1], p.getStrokeWidth());
221 path.dumpHex();
222 SkDebugf("fill:\n");
223 fill.dumpHex();
224 }
225 bestTan = std::max(bestTan, gMaxRecursion[0]);
226 bestCubic = std::max(bestCubic, gMaxRecursion[1]);
227 }
228 #endif
229 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
230 return;
231 }
232 }
233 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
234 if (reporter->verbose()) {
235 SkDebugf("\n%s max tan=%d cubic=%d\n", __FUNCTION__, bestTan, bestCubic);
236 }
237 #endif
238 }
239
DEF_TEST(QuadStrokerConstrained,reporter)240 DEF_TEST(QuadStrokerConstrained, reporter) {
241 SkRandom r;
242 SkPaint p;
243 p.setStyle(SkPaint::kStroke_Style);
244 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
245 int best = 0;
246 sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
247 #endif
248 skiatest::Timer timer;
249 for (int i = 0; i < 1000000; ++i) {
250 SkPath path, fill;
251 SkPoint quad[3];
252 quad[0].fX = r.nextRangeF(0, 500);
253 quad[0].fY = r.nextRangeF(0, 500);
254 const SkScalar halfSquared = 0.5f * 0.5f;
255 do {
256 quad[1].fX = r.nextRangeF(0, 500);
257 quad[1].fY = r.nextRangeF(0, 500);
258 } while (SkPointPriv::DistanceToSqd(quad[0], quad[1]) < halfSquared);
259 do {
260 quad[2].fX = r.nextRangeF(0, 500);
261 quad[2].fY = r.nextRangeF(0, 500);
262 } while (SkPointPriv::DistanceToSqd(quad[0], quad[2]) < halfSquared
263 || SkPointPriv::DistanceToSqd(quad[1], quad[2]) < halfSquared);
264 path.moveTo(quad[0].fX, quad[0].fY);
265 path.quadTo(quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
266 p.setStrokeWidth(r.nextRangeF(0, 500));
267 skpathutils::FillPathWithPaint(path, p, &fill);
268 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
269 if (best < gMaxRecursion[2]) {
270 if (reporter->verbose()) {
271 SkDebugf("\n%s quad=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[2],
272 p.getStrokeWidth());
273 path.dumpHex();
274 SkDebugf("fill:\n");
275 fill.dumpHex();
276 }
277 best = gMaxRecursion[2];
278 }
279 #endif
280 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
281 return;
282 }
283 }
284 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
285 if (reporter->verbose()) {
286 SkDebugf("\n%s max quad=%d\n", __FUNCTION__, best);
287 }
288 #endif
289 }
290
DEF_TEST(CubicStrokerConstrained,reporter)291 DEF_TEST(CubicStrokerConstrained, reporter) {
292 SkRandom r;
293 SkPaint p;
294 p.setStyle(SkPaint::kStroke_Style);
295 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
296 int bestTan = 0;
297 int bestCubic = 0;
298 sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
299 #endif
300 skiatest::Timer timer;
301 for (int i = 0; i < 1000000; ++i) {
302 SkPath path, fill;
303 SkPoint cubic[4];
304 cubic[0].fX = r.nextRangeF(0, 500);
305 cubic[0].fY = r.nextRangeF(0, 500);
306 const SkScalar halfSquared = 0.5f * 0.5f;
307 do {
308 cubic[1].fX = r.nextRangeF(0, 500);
309 cubic[1].fY = r.nextRangeF(0, 500);
310 } while (SkPointPriv::DistanceToSqd(cubic[0], cubic[1]) < halfSquared);
311 do {
312 cubic[2].fX = r.nextRangeF(0, 500);
313 cubic[2].fY = r.nextRangeF(0, 500);
314 } while ( SkPointPriv::DistanceToSqd(cubic[0], cubic[2]) < halfSquared
315 || SkPointPriv::DistanceToSqd(cubic[1], cubic[2]) < halfSquared);
316 do {
317 cubic[3].fX = r.nextRangeF(0, 500);
318 cubic[3].fY = r.nextRangeF(0, 500);
319 } while ( SkPointPriv::DistanceToSqd(cubic[0], cubic[3]) < halfSquared
320 || SkPointPriv::DistanceToSqd(cubic[1], cubic[3]) < halfSquared
321 || SkPointPriv::DistanceToSqd(cubic[2], cubic[3]) < halfSquared);
322 path.moveTo(cubic[0].fX, cubic[0].fY);
323 path.cubicTo(cubic[1].fX, cubic[1].fY, cubic[2].fX, cubic[2].fY, cubic[3].fX, cubic[3].fY);
324 p.setStrokeWidth(r.nextRangeF(0, 500));
325 skpathutils::FillPathWithPaint(path, p, &fill);
326 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
327 if (bestTan < gMaxRecursion[0] || bestCubic < gMaxRecursion[1]) {
328 if (reporter->verbose()) {
329 SkDebugf("\n%s tan=%d cubic=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[0],
330 gMaxRecursion[1], p.getStrokeWidth());
331 path.dumpHex();
332 SkDebugf("fill:\n");
333 fill.dumpHex();
334 }
335 bestTan = std::max(bestTan, gMaxRecursion[0]);
336 bestCubic = std::max(bestCubic, gMaxRecursion[1]);
337 }
338 #endif
339 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
340 return;
341 }
342 }
343 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
344 if (reporter->verbose()) {
345 SkDebugf("\n%s max tan=%d cubic=%d\n", __FUNCTION__, bestTan, bestCubic);
346 }
347 #endif
348 }
349
DEF_TEST(QuadStrokerRange,reporter)350 DEF_TEST(QuadStrokerRange, reporter) {
351 SkRandom r;
352 SkPaint p;
353 p.setStyle(SkPaint::kStroke_Style);
354 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
355 int best = 0;
356 sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
357 #endif
358 skiatest::Timer timer;
359 for (int i = 0; i < 1000000; ++i) {
360 SkPath path, fill;
361 SkPoint quad[3];
362 quad[0].fX = r.nextRangeF(0, 500);
363 quad[0].fY = r.nextRangeF(0, 500);
364 quad[1].fX = r.nextRangeF(0, 500);
365 quad[1].fY = r.nextRangeF(0, 500);
366 quad[2].fX = r.nextRangeF(0, 500);
367 quad[2].fY = r.nextRangeF(0, 500);
368 path.moveTo(quad[0].fX, quad[0].fY);
369 path.quadTo(quad[1].fX, quad[1].fY, quad[2].fX, quad[2].fY);
370 p.setStrokeWidth(r.nextRangeF(0, 500));
371 skpathutils::FillPathWithPaint(path, p, &fill);
372 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
373 if (best < gMaxRecursion[2]) {
374 if (reporter->verbose()) {
375 SkDebugf("\n%s quad=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[2],
376 p.getStrokeWidth());
377 path.dumpHex();
378 SkDebugf("fill:\n");
379 fill.dumpHex();
380 }
381 best = gMaxRecursion[2];
382 }
383 #endif
384 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
385 return;
386 }
387 }
388 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
389 if (reporter->verbose()) {
390 SkDebugf("\n%s max quad=%d\n", __FUNCTION__, best);
391 }
392 #endif
393 }
394
DEF_TEST(CubicStrokerRange,reporter)395 DEF_TEST(CubicStrokerRange, reporter) {
396 SkRandom r;
397 SkPaint p;
398 p.setStyle(SkPaint::kStroke_Style);
399 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
400 int best[2] = { 0 };
401 sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
402 #endif
403 skiatest::Timer timer;
404 for (int i = 0; i < 1000000; ++i) {
405 SkPath path, fill;
406 path.moveTo(r.nextRangeF(0, 500), r.nextRangeF(0, 500));
407 path.cubicTo(r.nextRangeF(0, 500), r.nextRangeF(0, 500), r.nextRangeF(0, 500),
408 r.nextRangeF(0, 500), r.nextRangeF(0, 500), r.nextRangeF(0, 500));
409 p.setStrokeWidth(r.nextRangeF(0, 100));
410 skpathutils::FillPathWithPaint(path, p, &fill);
411 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
412 if (best[0] < gMaxRecursion[0] || best[1] < gMaxRecursion[1]) {
413 if (reporter->verbose()) {
414 SkDebugf("\n%s tan=%d cubic=%d width=%1.9g\n", __FUNCTION__, gMaxRecursion[0],
415 gMaxRecursion[1], p.getStrokeWidth());
416 path.dumpHex();
417 SkDebugf("fill:\n");
418 fill.dumpHex();
419 }
420 best[0] = std::max(best[0], gMaxRecursion[0]);
421 best[1] = std::max(best[1], gMaxRecursion[1]);
422 }
423 #endif
424 if (FLAGS_timeout && timer.elapsedMs() > MS_TEST_DURATION) {
425 return;
426 }
427 }
428 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
429 if (reporter->verbose()) {
430 SkDebugf("\n%s max tan=%d cubic=%d\n", __FUNCTION__, best[0], best[1]);
431 }
432 #endif
433 }
434
435
DEF_TEST(QuadStrokerOneOff,reporter)436 DEF_TEST(QuadStrokerOneOff, reporter) {
437 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
438 sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
439 #endif
440 SkPaint p;
441 p.setStyle(SkPaint::kStroke_Style);
442 p.setStrokeWidth(SkDoubleToScalar(164.683548));
443
444 SkPath path, fill;
445 path.moveTo(SkBits2Float(0x43c99223), SkBits2Float(0x42b7417e));
446 path.quadTo(SkBits2Float(0x4285d839), SkBits2Float(0x43ed6645), SkBits2Float(0x43c941c8), SkBits2Float(0x42b3ace3));
447 skpathutils::FillPathWithPaint(path, p, &fill);
448 if (reporter->verbose()) {
449 SkDebugf("\n%s path\n", __FUNCTION__);
450 path.dump();
451 SkDebugf("fill:\n");
452 fill.dump();
453 }
454 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
455 if (reporter->verbose()) {
456 SkDebugf("max quad=%d\n", gMaxRecursion[2]);
457 }
458 #endif
459 }
460
DEF_TEST(CubicStrokerOneOff,reporter)461 DEF_TEST(CubicStrokerOneOff, reporter) {
462 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
463 sk_bzero(gMaxRecursion, sizeof(gMaxRecursion[0]) * 3);
464 #endif
465 SkPaint p;
466 p.setStyle(SkPaint::kStroke_Style);
467 p.setStrokeWidth(SkDoubleToScalar(42.835968));
468
469 SkPath path, fill;
470 path.moveTo(SkBits2Float(0x433f5370), SkBits2Float(0x43d1f4b3));
471 path.cubicTo(SkBits2Float(0x4331cb76), SkBits2Float(0x43ea3340), SkBits2Float(0x4388f498), SkBits2Float(0x42f7f08d), SkBits2Float(0x43f1cd32), SkBits2Float(0x42802ec1));
472 skpathutils::FillPathWithPaint(path, p, &fill);
473 if (reporter->verbose()) {
474 SkDebugf("\n%s path\n", __FUNCTION__);
475 path.dump();
476 SkDebugf("fill:\n");
477 fill.dump();
478 }
479 #if defined(SK_DEBUG) && QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
480 if (reporter->verbose()) {
481 SkDebugf("max tan=%d cubic=%d\n", gMaxRecursion[0], gMaxRecursion[1]);
482 }
483 #endif
484 }
485