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 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 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 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 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 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 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 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 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 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 135 static SkScalar unbounded(SkRandom& r) { 136 uint32_t val = r.nextU(); 137 return SkBits2Float(val); 138 } 139 140 static SkScalar unboundedPos(SkRandom& r) { 141 uint32_t val = r.nextU() & 0x7fffffff; 142 return SkBits2Float(val); 143 } 144 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 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 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 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 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 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 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 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
