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