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