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