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