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