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