| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 #include "PathOpsCubicIntersectionTestData.h" | 7 #include "PathOpsCubicIntersectionTestData.h" |
| 8 #include "PathOpsTestCommon.h" | 8 #include "PathOpsTestCommon.h" |
| 9 #include "SkIntersections.h" | 9 #include "SkIntersections.h" |
| 10 #include "SkPathOpsRect.h" | 10 #include "SkPathOpsRect.h" |
| (...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 45 continue; | 45 continue; |
| 46 } | 46 } |
| 47 if (tIntersections.isCoincident(0)) { | 47 if (tIntersections.isCoincident(0)) { |
| 48 if (showSkipped) { | 48 if (showSkipped) { |
| 49 SkDebugf("%s [%d] coincident\n", __FUNCTION__, iIndex); | 49 SkDebugf("%s [%d] coincident\n", __FUNCTION__, iIndex); |
| 50 } | 50 } |
| 51 continue; | 51 continue; |
| 52 } | 52 } |
| 53 for (int pt = 0; pt < tIntersections.used(); ++pt) { | 53 for (int pt = 0; pt < tIntersections.used(); ++pt) { |
| 54 double tt1 = tIntersections[0][pt]; | 54 double tt1 = tIntersections[0][pt]; |
| 55 SkDPoint xy1 = cubic1.xyAtT(tt1); | 55 SkDPoint xy1 = cubic1.ptAtT(tt1); |
| 56 double tt2 = tIntersections[1][pt]; | 56 double tt2 = tIntersections[1][pt]; |
| 57 SkDPoint xy2 = cubic2.xyAtT(tt2); | 57 SkDPoint xy2 = cubic2.ptAtT(tt2); |
| 58 if (!xy1.approximatelyEqual(xy2)) { | 58 if (!xy1.approximatelyEqual(xy2)) { |
| 59 SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", | 59 SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", |
| 60 __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.
fX, xy2.fY); | 60 __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.
fX, xy2.fY); |
| 61 } | 61 } |
| 62 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); | 62 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); |
| 63 } | 63 } |
| 64 } | 64 } |
| 65 } | 65 } |
| 66 | 66 |
| 67 static const SkDCubic testSet[] = { | 67 static const SkDCubic testSet[] = { |
| (...skipping 230 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 298 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX,
q[0].fY, | 298 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n", q[0].fX,
q[0].fY, |
| 299 q[1].fX, q[1].fY, q[2].fX, q[2].fY); | 299 q[1].fX, q[1].fY, q[2].fX, q[2].fY); |
| 300 } | 300 } |
| 301 #endif | 301 #endif |
| 302 SkIntersections intersections; | 302 SkIntersections intersections; |
| 303 intersections.intersect(cubic1, cubic2); | 303 intersections.intersect(cubic1, cubic2); |
| 304 double tt1, tt2; | 304 double tt1, tt2; |
| 305 SkDPoint xy1, xy2; | 305 SkDPoint xy1, xy2; |
| 306 for (int pt3 = 0; pt3 < intersections.used(); ++pt3) { | 306 for (int pt3 = 0; pt3 < intersections.used(); ++pt3) { |
| 307 tt1 = intersections[0][pt3]; | 307 tt1 = intersections[0][pt3]; |
| 308 xy1 = cubic1.xyAtT(tt1); | 308 xy1 = cubic1.ptAtT(tt1); |
| 309 tt2 = intersections[1][pt3]; | 309 tt2 = intersections[1][pt3]; |
| 310 xy2 = cubic2.xyAtT(tt2); | 310 xy2 = cubic2.ptAtT(tt2); |
| 311 const SkDPoint& iPt = intersections.pt(pt3); | 311 const SkDPoint& iPt = intersections.pt(pt3); |
| 312 #if ONE_OFF_DEBUG | 312 #if ONE_OFF_DEBUG |
| 313 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1
.9g\n", | 313 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1
.9g\n", |
| 314 __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX, | 314 __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX, |
| 315 iPt.fY, xy2.fX, xy2.fY, tt2); | 315 iPt.fY, xy2.fX, xy2.fY, tt2); |
| 316 #endif | 316 #endif |
| 317 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt)); | 317 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt)); |
| 318 REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt)); | 318 REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt)); |
| 319 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); | 319 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); |
| 320 } | 320 } |
| (...skipping 63 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 384 if (!boundsIntersect && newIntersects) { | 384 if (!boundsIntersect && newIntersects) { |
| 385 #if DEBUG_CRASH | 385 #if DEBUG_CRASH |
| 386 SkDebugf("%s %d unexpected intersection boundsIntersect=%d " | 386 SkDebugf("%s %d unexpected intersection boundsIntersect=%d " |
| 387 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsInte
rsect, | 387 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsInte
rsect, |
| 388 newIntersects, __FUNCTION__, str); | 388 newIntersects, __FUNCTION__, str); |
| 389 #endif | 389 #endif |
| 390 REPORTER_ASSERT(reporter, 0); | 390 REPORTER_ASSERT(reporter, 0); |
| 391 } | 391 } |
| 392 for (int pt = 0; pt < intersections2.used(); ++pt) { | 392 for (int pt = 0; pt < intersections2.used(); ++pt) { |
| 393 double tt1 = intersections2[0][pt]; | 393 double tt1 = intersections2[0][pt]; |
| 394 SkDPoint xy1 = cubic1.xyAtT(tt1); | 394 SkDPoint xy1 = cubic1.ptAtT(tt1); |
| 395 double tt2 = intersections2[1][pt]; | 395 double tt2 = intersections2[1][pt]; |
| 396 SkDPoint xy2 = cubic2.xyAtT(tt2); | 396 SkDPoint xy2 = cubic2.ptAtT(tt2); |
| 397 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); | 397 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); |
| 398 } | 398 } |
| 399 } | 399 } |
| 400 } | 400 } |
| 401 | 401 |
| 402 static void intersectionFinder(int index0, int index1, double t1Seed, double t2S
eed, | 402 static void intersectionFinder(int index0, int index1, double t1Seed, double t2S
eed, |
| 403 double t1Step, double t2Step) { | 403 double t1Step, double t2Step) { |
| 404 const SkDCubic& cubic1 = newTestSet[index0]; | 404 const SkDCubic& cubic1 = newTestSet[index0]; |
| 405 const SkDCubic& cubic2 = newTestSet[index1]; | 405 const SkDCubic& cubic2 = newTestSet[index1]; |
| 406 SkDPoint t1[3], t2[3]; | 406 SkDPoint t1[3], t2[3]; |
| 407 bool toggle = true; | 407 bool toggle = true; |
| 408 do { | 408 do { |
| 409 t1[0] = cubic1.xyAtT(t1Seed - t1Step); | 409 t1[0] = cubic1.ptAtT(t1Seed - t1Step); |
| 410 t1[1] = cubic1.xyAtT(t1Seed); | 410 t1[1] = cubic1.ptAtT(t1Seed); |
| 411 t1[2] = cubic1.xyAtT(t1Seed + t1Step); | 411 t1[2] = cubic1.ptAtT(t1Seed + t1Step); |
| 412 t2[0] = cubic2.xyAtT(t2Seed - t2Step); | 412 t2[0] = cubic2.ptAtT(t2Seed - t2Step); |
| 413 t2[1] = cubic2.xyAtT(t2Seed); | 413 t2[1] = cubic2.ptAtT(t2Seed); |
| 414 t2[2] = cubic2.xyAtT(t2Seed + t2Step); | 414 t2[2] = cubic2.ptAtT(t2Seed + t2Step); |
| 415 double dist[3][3]; | 415 double dist[3][3]; |
| 416 dist[1][1] = t1[1].distance(t2[1]); | 416 dist[1][1] = t1[1].distance(t2[1]); |
| 417 int best_i = 1, best_j = 1; | 417 int best_i = 1, best_j = 1; |
| 418 for (int i = 0; i < 3; ++i) { | 418 for (int i = 0; i < 3; ++i) { |
| 419 for (int j = 0; j < 3; ++j) { | 419 for (int j = 0; j < 3; ++j) { |
| 420 if (i == 1 && j == 1) { | 420 if (i == 1 && j == 1) { |
| 421 continue; | 421 continue; |
| 422 } | 422 } |
| 423 dist[i][j] = t1[i].distance(t2[j]); | 423 dist[i][j] = t1[i].distance(t2[j]); |
| 424 if (dist[best_i][best_j] > dist[i][j]) { | 424 if (dist[best_i][best_j] > dist[i][j]) { |
| (...skipping 20 matching lines...) Expand all Loading... |
| 445 } | 445 } |
| 446 } | 446 } |
| 447 } while (!t1[1].approximatelyEqual(t2[1])); | 447 } while (!t1[1].approximatelyEqual(t2[1])); |
| 448 t1Step = t2Step = 0.1; | 448 t1Step = t2Step = 0.1; |
| 449 double t10 = t1Seed - t1Step * 2; | 449 double t10 = t1Seed - t1Step * 2; |
| 450 double t12 = t1Seed + t1Step * 2; | 450 double t12 = t1Seed + t1Step * 2; |
| 451 double t20 = t2Seed - t2Step * 2; | 451 double t20 = t2Seed - t2Step * 2; |
| 452 double t22 = t2Seed + t2Step * 2; | 452 double t22 = t2Seed + t2Step * 2; |
| 453 SkDPoint test; | 453 SkDPoint test; |
| 454 while (!approximately_zero(t1Step)) { | 454 while (!approximately_zero(t1Step)) { |
| 455 test = cubic1.xyAtT(t10); | 455 test = cubic1.ptAtT(t10); |
| 456 t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; | 456 t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; |
| 457 t1Step /= 2; | 457 t1Step /= 2; |
| 458 } | 458 } |
| 459 t1Step = 0.1; | 459 t1Step = 0.1; |
| 460 while (!approximately_zero(t1Step)) { | 460 while (!approximately_zero(t1Step)) { |
| 461 test = cubic1.xyAtT(t12); | 461 test = cubic1.ptAtT(t12); |
| 462 t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; | 462 t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; |
| 463 t1Step /= 2; | 463 t1Step /= 2; |
| 464 } | 464 } |
| 465 while (!approximately_zero(t2Step)) { | 465 while (!approximately_zero(t2Step)) { |
| 466 test = cubic2.xyAtT(t20); | 466 test = cubic2.ptAtT(t20); |
| 467 t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; | 467 t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; |
| 468 t2Step /= 2; | 468 t2Step /= 2; |
| 469 } | 469 } |
| 470 t2Step = 0.1; | 470 t2Step = 0.1; |
| 471 while (!approximately_zero(t2Step)) { | 471 while (!approximately_zero(t2Step)) { |
| 472 test = cubic2.xyAtT(t22); | 472 test = cubic2.ptAtT(t22); |
| 473 t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; | 473 t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; |
| 474 t2Step /= 2; | 474 t2Step /= 2; |
| 475 } | 475 } |
| 476 #if ONE_OFF_DEBUG | 476 #if ONE_OFF_DEBUG |
| 477 SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, | 477 SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, |
| 478 t10, t1Seed, t12, t20, t2Seed, t22); | 478 t10, t1Seed, t12, t20, t2Seed, t22); |
| 479 SkDPoint p10 = cubic1.xyAtT(t10); | 479 SkDPoint p10 = cubic1.ptAtT(t10); |
| 480 SkDPoint p1Seed = cubic1.xyAtT(t1Seed); | 480 SkDPoint p1Seed = cubic1.ptAtT(t1Seed); |
| 481 SkDPoint p12 = cubic1.xyAtT(t12); | 481 SkDPoint p12 = cubic1.ptAtT(t12); |
| 482 SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, | 482 SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, |
| 483 p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY); | 483 p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY); |
| 484 SkDPoint p20 = cubic2.xyAtT(t20); | 484 SkDPoint p20 = cubic2.ptAtT(t20); |
| 485 SkDPoint p2Seed = cubic2.xyAtT(t2Seed); | 485 SkDPoint p2Seed = cubic2.ptAtT(t2Seed); |
| 486 SkDPoint p22 = cubic2.xyAtT(t22); | 486 SkDPoint p22 = cubic2.ptAtT(t22); |
| 487 SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, | 487 SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, |
| 488 p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY); | 488 p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY); |
| 489 #endif | 489 #endif |
| 490 } | 490 } |
| 491 | 491 |
| 492 static void CubicIntersection_IntersectionFinder() { | 492 static void CubicIntersection_IntersectionFinder() { |
| 493 // double t1Seed = 0.87; | 493 // double t1Seed = 0.87; |
| 494 // double t2Seed = 0.87; | 494 // double t2Seed = 0.87; |
| 495 double t1Step = 0.000001; | 495 double t1Step = 0.000001; |
| 496 double t2Step = 0.000001; | 496 double t2Step = 0.000001; |
| (...skipping 14 matching lines...) Expand all Loading... |
| 511 size_t selfSetCount = SK_ARRAY_COUNT(selfSet); | 511 size_t selfSetCount = SK_ARRAY_COUNT(selfSet); |
| 512 size_t firstFail = 1; | 512 size_t firstFail = 1; |
| 513 for (size_t index = firstFail; index < selfSetCount; ++index) { | 513 for (size_t index = firstFail; index < selfSetCount; ++index) { |
| 514 const SkDCubic& cubic = selfSet[index]; | 514 const SkDCubic& cubic = selfSet[index]; |
| 515 #if ONE_OFF_DEBUG | 515 #if ONE_OFF_DEBUG |
| 516 int idx2; | 516 int idx2; |
| 517 double max[3]; | 517 double max[3]; |
| 518 int ts = cubic.findMaxCurvature(max); | 518 int ts = cubic.findMaxCurvature(max); |
| 519 for (idx2 = 0; idx2 < ts; ++idx2) { | 519 for (idx2 = 0; idx2 < ts; ++idx2) { |
| 520 SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2, | 520 SkDebugf("%s max[%d]=%1.9g (%1.9g, %1.9g)\n", __FUNCTION__, idx2, |
| 521 max[idx2], cubic.xyAtT(max[idx2]).fX, cubic.xyAtT(max[idx2])
.fY); | 521 max[idx2], cubic.ptAtT(max[idx2]).fX, cubic.ptAtT(max[idx2])
.fY); |
| 522 } | 522 } |
| 523 SkTArray<double, true> ts1; | 523 SkTArray<double, true> ts1; |
| 524 SkTArray<SkDQuad, true> quads1; | 524 SkTArray<SkDQuad, true> quads1; |
| 525 cubic.toQuadraticTs(cubic.calcPrecision(), &ts1); | 525 cubic.toQuadraticTs(cubic.calcPrecision(), &ts1); |
| 526 for (idx2 = 0; idx2 < ts1.count(); ++idx2) { | 526 for (idx2 = 0; idx2 < ts1.count(); ++idx2) { |
| 527 SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]); | 527 SkDebugf("%s t[%d]=%1.9g\n", __FUNCTION__, idx2, ts1[idx2]); |
| 528 } | 528 } |
| 529 CubicToQuads(cubic, cubic.calcPrecision(), quads1); | 529 CubicToQuads(cubic, cubic.calcPrecision(), quads1); |
| 530 for (idx2 = 0; idx2 < quads1.count(); ++idx2) { | 530 for (idx2 = 0; idx2 < quads1.count(); ++idx2) { |
| 531 const SkDQuad& q = quads1[idx2]; | 531 const SkDQuad& q = quads1[idx2]; |
| 532 SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", | 532 SkDebugf(" {{{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}}},\n", |
| 533 q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY); | 533 q[0].fX, q[0].fY, q[1].fX, q[1].fY, q[2].fX, q[2].fY); |
| 534 } | 534 } |
| 535 SkDebugf("\n"); | 535 SkDebugf("\n"); |
| 536 #endif | 536 #endif |
| 537 SkIntersections i; | 537 SkIntersections i; |
| 538 int result = i.intersect(cubic); | 538 int result = i.intersect(cubic); |
| 539 REPORTER_ASSERT(reporter, result == 1); | 539 REPORTER_ASSERT(reporter, result == 1); |
| 540 REPORTER_ASSERT(reporter, i.used() == 1); | 540 REPORTER_ASSERT(reporter, i.used() == 1); |
| 541 REPORTER_ASSERT(reporter, !approximately_equal(i[0][0], i[1][0])); | 541 REPORTER_ASSERT(reporter, !approximately_equal(i[0][0], i[1][0])); |
| 542 SkDPoint pt1 = cubic.xyAtT(i[0][0]); | 542 SkDPoint pt1 = cubic.ptAtT(i[0][0]); |
| 543 SkDPoint pt2 = cubic.xyAtT(i[1][0]); | 543 SkDPoint pt2 = cubic.ptAtT(i[1][0]); |
| 544 REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2)); | 544 REPORTER_ASSERT(reporter, pt1.approximatelyEqual(pt2)); |
| 545 } | 545 } |
| 546 } | 546 } |
| 547 | 547 |
| 548 static void PathOpsCubicIntersectionOneOffTest(skiatest::Reporter* reporter) { | 548 static void PathOpsCubicIntersectionOneOffTest(skiatest::Reporter* reporter) { |
| 549 newOneOff(reporter, 6, 7); | 549 newOneOff(reporter, 6, 7); |
| 550 } | 550 } |
| 551 | 551 |
| 552 static void PathOpsCubicIntersectionTest(skiatest::Reporter* reporter) { | 552 static void PathOpsCubicIntersectionTest(skiatest::Reporter* reporter) { |
| 553 oneOffTests(reporter); | 553 oneOffTests(reporter); |
| 554 cubicIntersectionSelfTest(reporter); | 554 cubicIntersectionSelfTest(reporter); |
| 555 standardTestCases(reporter); | 555 standardTestCases(reporter); |
| 556 if (false) CubicIntersection_IntersectionFinder(); | 556 if (false) CubicIntersection_IntersectionFinder(); |
| 557 if (false) CubicIntersection_RandTest(reporter); | 557 if (false) CubicIntersection_RandTest(reporter); |
| 558 } | 558 } |
| 559 | 559 |
| 560 #include "TestClassDef.h" | 560 #include "TestClassDef.h" |
| 561 DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionTest) | 561 DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionTest) |
| 562 | 562 |
| 563 DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionOneOffTest) | 563 DEFINE_TESTCLASS_SHORT(PathOpsCubicIntersectionOneOffTest) |
| OLD | NEW |