| 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 "SkGeometry.h" | 9 #include "SkGeometry.h" |
| 10 #include "SkIntersections.h" | 10 #include "SkIntersections.h" |
| 11 #include "SkPathOpsRect.h" | 11 #include "SkPathOpsRect.h" |
| 12 #include "SkReduceOrder.h" | 12 #include "SkReduceOrder.h" |
| 13 #include "Test.h" | 13 #include "Test.h" |
| 14 | 14 |
| 15 #include <stdlib.h> | 15 #include <stdlib.h> |
| 16 | 16 |
| 17 const int firstCubicIntersectionTest = 9; | 17 const int firstCubicIntersectionTest = 9; |
| 18 | 18 |
| 19 static void standardTestCases(skiatest::Reporter* reporter) { | 19 static void standardTestCases(skiatest::Reporter* reporter) { |
| 20 for (size_t index = firstCubicIntersectionTest; index < tests_count; ++index
) { | 20 for (size_t index = firstCubicIntersectionTest; index < tests_count; ++index
) { |
| 21 int iIndex = static_cast<int>(index); | 21 int iIndex = static_cast<int>(index); |
| 22 const SkDCubic& cubic1 = tests[index][0]; | 22 const CubicPts& cubic1 = tests[index][0]; |
| 23 const SkDCubic& cubic2 = tests[index][1]; | 23 const CubicPts& cubic2 = tests[index][1]; |
| 24 SkDCubic c1, c2; |
| 25 c1.debugSet(cubic1.fPts); |
| 26 c2.debugSet(cubic2.fPts); |
| 24 SkReduceOrder reduce1, reduce2; | 27 SkReduceOrder reduce1, reduce2; |
| 25 int order1 = reduce1.reduce(cubic1, SkReduceOrder::kNo_Quadratics); | 28 int order1 = reduce1.reduce(c1, SkReduceOrder::kNo_Quadratics); |
| 26 int order2 = reduce2.reduce(cubic2, SkReduceOrder::kNo_Quadratics); | 29 int order2 = reduce2.reduce(c2, SkReduceOrder::kNo_Quadratics); |
| 27 const bool showSkipped = false; | 30 const bool showSkipped = false; |
| 28 if (order1 < 4) { | 31 if (order1 < 4) { |
| 29 if (showSkipped) { | 32 if (showSkipped) { |
| 30 SkDebugf("%s [%d] cubic1 order=%d\n", __FUNCTION__, iIndex, orde
r1); | 33 SkDebugf("%s [%d] cubic1 order=%d\n", __FUNCTION__, iIndex, orde
r1); |
| 31 } | 34 } |
| 32 continue; | 35 continue; |
| 33 } | 36 } |
| 34 if (order2 < 4) { | 37 if (order2 < 4) { |
| 35 if (showSkipped) { | 38 if (showSkipped) { |
| 36 SkDebugf("%s [%d] cubic2 order=%d\n", __FUNCTION__, iIndex, orde
r2); | 39 SkDebugf("%s [%d] cubic2 order=%d\n", __FUNCTION__, iIndex, orde
r2); |
| 37 } | 40 } |
| 38 continue; | 41 continue; |
| 39 } | 42 } |
| 40 SkIntersections tIntersections; | 43 SkIntersections tIntersections; |
| 41 tIntersections.intersect(cubic1, cubic2); | 44 tIntersections.intersect(c1, c2); |
| 42 if (!tIntersections.used()) { | 45 if (!tIntersections.used()) { |
| 43 if (showSkipped) { | 46 if (showSkipped) { |
| 44 SkDebugf("%s [%d] no intersection\n", __FUNCTION__, iIndex); | 47 SkDebugf("%s [%d] no intersection\n", __FUNCTION__, iIndex); |
| 45 } | 48 } |
| 46 continue; | 49 continue; |
| 47 } | 50 } |
| 48 if (tIntersections.isCoincident(0)) { | 51 if (tIntersections.isCoincident(0)) { |
| 49 if (showSkipped) { | 52 if (showSkipped) { |
| 50 SkDebugf("%s [%d] coincident\n", __FUNCTION__, iIndex); | 53 SkDebugf("%s [%d] coincident\n", __FUNCTION__, iIndex); |
| 51 } | 54 } |
| 52 continue; | 55 continue; |
| 53 } | 56 } |
| 54 for (int pt = 0; pt < tIntersections.used(); ++pt) { | 57 for (int pt = 0; pt < tIntersections.used(); ++pt) { |
| 55 double tt1 = tIntersections[0][pt]; | 58 double tt1 = tIntersections[0][pt]; |
| 56 SkDPoint xy1 = cubic1.ptAtT(tt1); | 59 SkDPoint xy1 = c1.ptAtT(tt1); |
| 57 double tt2 = tIntersections[1][pt]; | 60 double tt2 = tIntersections[1][pt]; |
| 58 SkDPoint xy2 = cubic2.ptAtT(tt2); | 61 SkDPoint xy2 = c2.ptAtT(tt2); |
| 59 if (!xy1.approximatelyEqual(xy2)) { | 62 if (!xy1.approximatelyEqual(xy2)) { |
| 60 SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", | 63 SkDebugf("%s [%d,%d] x!= t1=%g (%g,%g) t2=%g (%g,%g)\n", |
| 61 __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.
fX, xy2.fY); | 64 __FUNCTION__, (int)index, pt, tt1, xy1.fX, xy1.fY, tt2, xy2.
fX, xy2.fY); |
| 62 } | 65 } |
| 63 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); | 66 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); |
| 64 } | 67 } |
| 65 reporter->bumpTestCount(); | 68 reporter->bumpTestCount(); |
| 66 } | 69 } |
| 67 } | 70 } |
| 68 | 71 |
| 69 static const SkDCubic testSet[] = { | 72 static const CubicPts testSet[] = { |
| 70 // FIXME: uncommenting these two will cause this to fail | 73 // FIXME: uncommenting these two will cause this to fail |
| 71 // this results in two curves very nearly but not exactly coincident | 74 // this results in two curves very nearly but not exactly coincident |
| 72 #if 0 | 75 #if 0 |
| 73 {{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921
306}, | 76 {{{67.426548091427676, 37.993772624988935}, {23.483695892376684, 90.476863174921
306}, |
| 74 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038
969412}}}, | 77 {35.597065061143162, 79.872482633158796}, {75.38634169631932, 18.244890038
969412}}}, |
| 75 {{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, | 78 {{{67.4265481, 37.9937726}, {23.4836959, 90.4768632}, {35.5970651, 79.8724826}, |
| 76 {75.3863417, 18.24489}}}, | 79 {75.3863417, 18.24489}}}, |
| 77 #endif | 80 #endif |
| 78 | 81 |
| 79 {{{0, 0}, {0, 1}, {1, 1}, {1, 0}}}, | 82 {{{0, 0}, {0, 1}, {1, 1}, {1, 0}}}, |
| (...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 157 {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503
699973002}}}, | 160 {16.815615499771951, 20.049704667203923}, {41.866884958868326, 56.735503
699973002}}}, |
| 158 | 161 |
| 159 {{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945}, | 162 {{{18.1312339, 31.6473732}, {95.5711034, 63.5350219}, {92.3283165, 62.0158945}, |
| 160 {18.5656052, 32.1268808}}}, | 163 {18.5656052, 32.1268808}}}, |
| 161 {{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981}, | 164 {{{97.402018, 35.7169972}, {33.1127443, 25.8935163}, {1.13970027, 54.9424981}, |
| 162 {56.4860195, 60.529264}}}, | 165 {56.4860195, 60.529264}}}, |
| 163 }; | 166 }; |
| 164 | 167 |
| 165 const int testSetCount = (int) SK_ARRAY_COUNT(testSet); | 168 const int testSetCount = (int) SK_ARRAY_COUNT(testSet); |
| 166 | 169 |
| 167 static const SkDCubic newTestSet[] = { | 170 static const CubicPts newTestSet[] = { |
| 168 { { { 130.0427549999999997, 11417.41309999999976 },{ 130.2331240000000037, 11418
.3192999999992 },{ 131.0370790000000056, 11419 },{ 132, 11419 } } }, | 171 { { { 130.0427549999999997, 11417.41309999999976 },{ 130.2331240000000037, 11418
.3192999999992 },{ 131.0370790000000056, 11419 },{ 132, 11419 } } }, |
| 169 { { { 132, 11419 },{ 130.8954319999999996, 11419 },{ 130, 11418.10449999999946 }
,{ 130, 11417 } } }, | 172 { { { 132, 11419 },{ 130.8954319999999996, 11419 },{ 130, 11418.10449999999946 }
,{ 130, 11417 } } }, |
| 170 | 173 |
| 171 {{{1,3}, {-1.0564518,1.79032254}, {1.45265341,0.229448318}, {1.45381773,0.229133
77}}}, | 174 {{{1,3}, {-1.0564518,1.79032254}, {1.45265341,0.229448318}, {1.45381773,0.229133
77}}}, |
| 172 {{{1.45381773,0.22913377}, {1.45425761,0.229014933}, {1.0967741,0.451612949}, {0
,1}}}, | 175 {{{1.45381773,0.22913377}, {1.45425761,0.229014933}, {1.0967741,0.451612949}, {0
,1}}}, |
| 173 | 176 |
| 174 {{{1.64551306f, 3.57876182f}, {0.298127174f, 3.70454836f}, {-0.809808373f, 6.395
24937f}, {-3.66666651f, 13.333334f}}}, | 177 {{{1.64551306f, 3.57876182f}, {0.298127174f, 3.70454836f}, {-0.809808373f, 6.395
24937f}, {-3.66666651f, 13.333334f}}}, |
| 175 {{{1, 2}, {1, 2}, {-3.66666651f, 13.333334f}, {5, 6}}}, | 178 {{{1, 2}, {1, 2}, {-3.66666651f, 13.333334f}, {5, 6}}}, |
| 176 | 179 |
| 177 {{{0.0660428554,1.65340209}, {-0.251940489,1.43560803}, {-0.782382965,-0.1962990
91}, {3.33333325,-0.666666627}}}, | 180 {{{0.0660428554,1.65340209}, {-0.251940489,1.43560803}, {-0.782382965,-0.1962990
91}, {3.33333325,-0.666666627}}}, |
| (...skipping 196 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 374 {{{0, 1}, {0, 1}, {2, 1}, {6, 5}}}, | 377 {{{0, 1}, {0, 1}, {2, 1}, {6, 5}}}, |
| 375 | 378 |
| 376 {{{0, 6}, {1, 2}, {1, 0}, {1, 0}}}, | 379 {{{0, 6}, {1, 2}, {1, 0}, {1, 0}}}, |
| 377 {{{0, 1}, {0, 1}, {6, 0}, {2, 1}}}, | 380 {{{0, 1}, {0, 1}, {6, 0}, {2, 1}}}, |
| 378 | 381 |
| 379 {{{0, 2}, {0, 1}, {3, 0}, {1, 0}}}, | 382 {{{0, 2}, {0, 1}, {3, 0}, {1, 0}}}, |
| 380 {{{0, 3}, {0, 1}, {2, 0}, {1, 0}}}, | 383 {{{0, 3}, {0, 1}, {2, 0}, {1, 0}}}, |
| 381 }; | 384 }; |
| 382 | 385 |
| 383 const int newTestSetCount = (int) SK_ARRAY_COUNT(newTestSet); | 386 const int newTestSetCount = (int) SK_ARRAY_COUNT(newTestSet); |
| 384 static void oneOff(skiatest::Reporter* reporter, const SkDCubic& cubic1, const S
kDCubic& cubic2, | 387 static void oneOff(skiatest::Reporter* reporter, const CubicPts& cubic1, const C
ubicPts& cubic2, |
| 385 bool coin) { | 388 bool coin) { |
| 386 SkASSERT(ValidCubic(cubic1)); | 389 SkDCubic c1, c2; |
| 387 SkASSERT(ValidCubic(cubic2)); | 390 c1.debugSet(cubic1.fPts); |
| 391 c2.debugSet(cubic2.fPts); |
| 392 SkASSERT(ValidCubic(c1)); |
| 393 SkASSERT(ValidCubic(c2)); |
| 388 #if ONE_OFF_DEBUG | 394 #if ONE_OFF_DEBUG |
| 389 SkDebugf("computed quadratics given\n"); | 395 SkDebugf("computed quadratics given\n"); |
| 390 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n"
, | 396 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n"
, |
| 391 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, | 397 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, |
| 392 cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY); | 398 cubic1[2].fX, cubic1[2].fY, cubic1[3].fX, cubic1[3].fY); |
| 393 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n"
, | 399 SkDebugf(" {{%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}, {%1.9g,%1.9g}},\n"
, |
| 394 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, | 400 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, |
| 395 cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY); | 401 cubic2[2].fX, cubic2[2].fY, cubic2[3].fX, cubic2[3].fY); |
| 396 #endif | 402 #endif |
| 397 SkIntersections intersections; | 403 SkIntersections intersections; |
| 398 intersections.intersect(cubic1, cubic2); | 404 intersections.intersect(c1, c2); |
| 399 #if DEBUG_T_SECT_DUMP == 3 | 405 #if DEBUG_T_SECT_DUMP == 3 |
| 400 SkDebugf("</div>\n\n"); | 406 SkDebugf("</div>\n\n"); |
| 401 SkDebugf("<script type=\"text/javascript\">\n\n"); | 407 SkDebugf("<script type=\"text/javascript\">\n\n"); |
| 402 SkDebugf("var testDivs = [\n"); | 408 SkDebugf("var testDivs = [\n"); |
| 403 for (int index = 1; index <= gDumpTSectNum; ++index) { | 409 for (int index = 1; index <= gDumpTSectNum; ++index) { |
| 404 SkDebugf("sect%d,\n", index); | 410 SkDebugf("sect%d,\n", index); |
| 405 } | 411 } |
| 406 #endif | 412 #endif |
| 407 if (coin && intersections.used() < 2) { | 413 if (coin && intersections.used() < 2) { |
| 408 SkDebugf(""); | 414 SkDebugf(""); |
| 409 } | 415 } |
| 410 REPORTER_ASSERT(reporter, !coin || intersections.used() >= 2); | 416 REPORTER_ASSERT(reporter, !coin || intersections.used() >= 2); |
| 411 double tt1, tt2; | 417 double tt1, tt2; |
| 412 SkDPoint xy1, xy2; | 418 SkDPoint xy1, xy2; |
| 413 for (int pt3 = 0; pt3 < intersections.used(); ++pt3) { | 419 for (int pt3 = 0; pt3 < intersections.used(); ++pt3) { |
| 414 tt1 = intersections[0][pt3]; | 420 tt1 = intersections[0][pt3]; |
| 415 xy1 = cubic1.ptAtT(tt1); | 421 xy1 = c1.ptAtT(tt1); |
| 416 tt2 = intersections[1][pt3]; | 422 tt2 = intersections[1][pt3]; |
| 417 xy2 = cubic2.ptAtT(tt2); | 423 xy2 = c2.ptAtT(tt2); |
| 418 const SkDPoint& iPt = intersections.pt(pt3); | 424 const SkDPoint& iPt = intersections.pt(pt3); |
| 419 #if ONE_OFF_DEBUG | 425 #if ONE_OFF_DEBUG |
| 420 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1
.9g\n", | 426 SkDebugf("%s t1=%1.9g (%1.9g, %1.9g) (%1.9g, %1.9g) (%1.9g, %1.9g) t2=%1
.9g\n", |
| 421 __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX, | 427 __FUNCTION__, tt1, xy1.fX, xy1.fY, iPt.fX, |
| 422 iPt.fY, xy2.fX, xy2.fY, tt2); | 428 iPt.fY, xy2.fX, xy2.fY, tt2); |
| 423 #endif | 429 #endif |
| 424 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt)); | 430 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt)); |
| 425 REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt)); | 431 REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt)); |
| 426 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); | 432 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); |
| 427 } | 433 } |
| 428 reporter->bumpTestCount(); | 434 reporter->bumpTestCount(); |
| 429 } | 435 } |
| 430 | 436 |
| 431 static void oneOff(skiatest::Reporter* reporter, int outer, int inner) { | 437 static void oneOff(skiatest::Reporter* reporter, int outer, int inner) { |
| 432 const SkDCubic& cubic1 = testSet[outer]; | 438 const CubicPts& cubic1 = testSet[outer]; |
| 433 const SkDCubic& cubic2 = testSet[inner]; | 439 const CubicPts& cubic2 = testSet[inner]; |
| 434 oneOff(reporter, cubic1, cubic2, false); | 440 oneOff(reporter, cubic1, cubic2, false); |
| 435 } | 441 } |
| 436 | 442 |
| 437 static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) { | 443 static void newOneOff(skiatest::Reporter* reporter, int outer, int inner) { |
| 438 const SkDCubic& cubic1 = newTestSet[outer]; | 444 const CubicPts& cubic1 = newTestSet[outer]; |
| 439 const SkDCubic& cubic2 = newTestSet[inner]; | 445 const CubicPts& cubic2 = newTestSet[inner]; |
| 440 oneOff(reporter, cubic1, cubic2, false); | 446 oneOff(reporter, cubic1, cubic2, false); |
| 441 } | 447 } |
| 442 | 448 |
| 443 static void testsOneOff(skiatest::Reporter* reporter, int index) { | 449 static void testsOneOff(skiatest::Reporter* reporter, int index) { |
| 444 const SkDCubic& cubic1 = tests[index][0]; | 450 const CubicPts& cubic1 = tests[index][0]; |
| 445 const SkDCubic& cubic2 = tests[index][1]; | 451 const CubicPts& cubic2 = tests[index][1]; |
| 446 oneOff(reporter, cubic1, cubic2, false); | 452 oneOff(reporter, cubic1, cubic2, false); |
| 447 } | 453 } |
| 448 | 454 |
| 449 static void oneOffTests(skiatest::Reporter* reporter) { | 455 static void oneOffTests(skiatest::Reporter* reporter) { |
| 450 for (int outer = 0; outer < testSetCount - 1; ++outer) { | 456 for (int outer = 0; outer < testSetCount - 1; ++outer) { |
| 451 for (int inner = outer + 1; inner < testSetCount; ++inner) { | 457 for (int inner = outer + 1; inner < testSetCount; ++inner) { |
| 452 oneOff(reporter, outer, inner); | 458 oneOff(reporter, outer, inner); |
| 453 } | 459 } |
| 454 } | 460 } |
| 455 for (int outer = 0; outer < newTestSetCount - 1; ++outer) { | 461 for (int outer = 0; outer < newTestSetCount - 1; ++outer) { |
| 456 for (int inner = outer + 1; inner < newTestSetCount; ++inner) { | 462 for (int inner = outer + 1; inner < newTestSetCount; ++inner) { |
| 457 newOneOff(reporter, outer, inner); | 463 newOneOff(reporter, outer, inner); |
| 458 } | 464 } |
| 459 } | 465 } |
| 460 } | 466 } |
| 461 | 467 |
| 462 #define DEBUG_CRASH 0 | 468 #define DEBUG_CRASH 0 |
| 463 | 469 |
| 464 static void CubicIntersection_RandTest(skiatest::Reporter* reporter) { | 470 static void CubicIntersection_RandTest(skiatest::Reporter* reporter) { |
| 465 srand(0); | 471 srand(0); |
| 466 const int tests = 10000000; | 472 const int tests = 10000000; |
| 467 #if !defined(SK_BUILD_FOR_WIN) && !defined(SK_BUILD_FOR_ANDROID) | 473 #if !defined(SK_BUILD_FOR_WIN) && !defined(SK_BUILD_FOR_ANDROID) |
| 468 unsigned seed = 0; | 474 unsigned seed = 0; |
| 469 #endif | 475 #endif |
| 470 for (int test = 0; test < tests; ++test) { | 476 for (int test = 0; test < tests; ++test) { |
| 471 SkDCubic cubic1, cubic2; | 477 CubicPts cubic1, cubic2; |
| 472 for (int i = 0; i < 4; ++i) { | 478 for (int i = 0; i < 4; ++i) { |
| 473 cubic1[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100; | 479 cubic1.fPts[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX *
100; |
| 474 cubic1[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100; | 480 cubic1.fPts[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX *
100; |
| 475 cubic2[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100; | 481 cubic2.fPts[i].fX = static_cast<double>(SK_RAND(seed)) / RAND_MAX *
100; |
| 476 cubic2[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX * 100; | 482 cubic2.fPts[i].fY = static_cast<double>(SK_RAND(seed)) / RAND_MAX *
100; |
| 477 } | 483 } |
| 478 #if DEBUG_CRASH | 484 #if DEBUG_CRASH |
| 479 char str[1024]; | 485 char str[1024]; |
| 480 snprintf(str, sizeof(str), | 486 snprintf(str, sizeof(str), |
| 481 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},
\n" | 487 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},
\n" |
| 482 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},
\n", | 488 "{{{%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}, {%1.9g, %1.9g}}},
\n", |
| 483 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, cubic1[
2].fX, cubic1[2].fY, | 489 cubic1[0].fX, cubic1[0].fY, cubic1[1].fX, cubic1[1].fY, cubic1[
2].fX, cubic1[2].fY, |
| 484 cubic1[3].fX, cubic1[3].fY, | 490 cubic1[3].fX, cubic1[3].fY, |
| 485 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, cubic2[
2].fX, cubic2[2].fY, | 491 cubic2[0].fX, cubic2[0].fY, cubic2[1].fX, cubic2[1].fY, cubic2[
2].fX, cubic2[2].fY, |
| 486 cubic2[3].fX, cubic2[3].fY); | 492 cubic2[3].fX, cubic2[3].fY); |
| 487 #endif | 493 #endif |
| 488 SkDRect rect1, rect2; | 494 SkDRect rect1, rect2; |
| 489 rect1.setBounds(cubic1); | 495 SkDCubic c1, c2; |
| 490 rect2.setBounds(cubic2); | 496 c1.debugSet(cubic1.fPts); |
| 497 c2.debugSet(cubic2.fPts); |
| 498 rect1.setBounds(c1); |
| 499 rect2.setBounds(c2); |
| 491 bool boundsIntersect = rect1.fLeft <= rect2.fRight && rect2.fLeft <= rec
t2.fRight | 500 bool boundsIntersect = rect1.fLeft <= rect2.fRight && rect2.fLeft <= rec
t2.fRight |
| 492 && rect1.fTop <= rect2.fBottom && rect2.fTop <= rect1.fBottom; | 501 && rect1.fTop <= rect2.fBottom && rect2.fTop <= rect1.fBottom; |
| 493 if (test == -1) { | 502 if (test == -1) { |
| 494 SkDebugf("ready...\n"); | 503 SkDebugf("ready...\n"); |
| 495 } | 504 } |
| 496 SkIntersections intersections2; | 505 SkIntersections intersections2; |
| 497 int newIntersects = intersections2.intersect(cubic1, cubic2); | 506 int newIntersects = intersections2.intersect(c1, c2); |
| 498 if (!boundsIntersect && newIntersects) { | 507 if (!boundsIntersect && newIntersects) { |
| 499 #if DEBUG_CRASH | 508 #if DEBUG_CRASH |
| 500 SkDebugf("%s %d unexpected intersection boundsIntersect=%d " | 509 SkDebugf("%s %d unexpected intersection boundsIntersect=%d " |
| 501 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsInte
rsect, | 510 " newIntersects=%d\n%s %s\n", __FUNCTION__, test, boundsInte
rsect, |
| 502 newIntersects, __FUNCTION__, str); | 511 newIntersects, __FUNCTION__, str); |
| 503 #endif | 512 #endif |
| 504 REPORTER_ASSERT(reporter, 0); | 513 REPORTER_ASSERT(reporter, 0); |
| 505 } | 514 } |
| 506 for (int pt = 0; pt < intersections2.used(); ++pt) { | 515 for (int pt = 0; pt < intersections2.used(); ++pt) { |
| 507 double tt1 = intersections2[0][pt]; | 516 double tt1 = intersections2[0][pt]; |
| 508 SkDPoint xy1 = cubic1.ptAtT(tt1); | 517 SkDPoint xy1 = c1.ptAtT(tt1); |
| 509 double tt2 = intersections2[1][pt]; | 518 double tt2 = intersections2[1][pt]; |
| 510 SkDPoint xy2 = cubic2.ptAtT(tt2); | 519 SkDPoint xy2 = c2.ptAtT(tt2); |
| 511 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); | 520 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2)); |
| 512 } | 521 } |
| 513 reporter->bumpTestCount(); | 522 reporter->bumpTestCount(); |
| 514 } | 523 } |
| 515 } | 524 } |
| 516 | 525 |
| 517 static void intersectionFinder(int index0, int index1, double t1Seed, double t2S
eed, | 526 static void intersectionFinder(int index0, int index1, double t1Seed, double t2S
eed, |
| 518 double t1Step, double t2Step) { | 527 double t1Step, double t2Step) { |
| 519 const SkDCubic& cubic1 = newTestSet[index0]; | 528 const CubicPts& cubic1 = newTestSet[index0]; |
| 520 const SkDCubic& cubic2 = newTestSet[index1]; | 529 const CubicPts& cubic2 = newTestSet[index1]; |
| 521 SkDPoint t1[3], t2[3]; | 530 SkDPoint t1[3], t2[3]; |
| 522 bool toggle = true; | 531 bool toggle = true; |
| 532 SkDCubic c1, c2; |
| 533 c1.debugSet(cubic1.fPts); |
| 534 c2.debugSet(cubic2.fPts); |
| 523 do { | 535 do { |
| 524 t1[0] = cubic1.ptAtT(t1Seed - t1Step); | 536 t1[0] = c1.ptAtT(t1Seed - t1Step); |
| 525 t1[1] = cubic1.ptAtT(t1Seed); | 537 t1[1] = c1.ptAtT(t1Seed); |
| 526 t1[2] = cubic1.ptAtT(t1Seed + t1Step); | 538 t1[2] = c1.ptAtT(t1Seed + t1Step); |
| 527 t2[0] = cubic2.ptAtT(t2Seed - t2Step); | 539 t2[0] = c2.ptAtT(t2Seed - t2Step); |
| 528 t2[1] = cubic2.ptAtT(t2Seed); | 540 t2[1] = c2.ptAtT(t2Seed); |
| 529 t2[2] = cubic2.ptAtT(t2Seed + t2Step); | 541 t2[2] = c2.ptAtT(t2Seed + t2Step); |
| 530 double dist[3][3]; | 542 double dist[3][3]; |
| 531 dist[1][1] = t1[1].distance(t2[1]); | 543 dist[1][1] = t1[1].distance(t2[1]); |
| 532 int best_i = 1, best_j = 1; | 544 int best_i = 1, best_j = 1; |
| 533 for (int i = 0; i < 3; ++i) { | 545 for (int i = 0; i < 3; ++i) { |
| 534 for (int j = 0; j < 3; ++j) { | 546 for (int j = 0; j < 3; ++j) { |
| 535 if (i == 1 && j == 1) { | 547 if (i == 1 && j == 1) { |
| 536 continue; | 548 continue; |
| 537 } | 549 } |
| 538 dist[i][j] = t1[i].distance(t2[j]); | 550 dist[i][j] = t1[i].distance(t2[j]); |
| 539 if (dist[best_i][best_j] > dist[i][j]) { | 551 if (dist[best_i][best_j] > dist[i][j]) { |
| (...skipping 20 matching lines...) Expand all Loading... |
| 560 } | 572 } |
| 561 } | 573 } |
| 562 } while (!t1[1].approximatelyEqual(t2[1])); | 574 } while (!t1[1].approximatelyEqual(t2[1])); |
| 563 t1Step = t2Step = 0.1; | 575 t1Step = t2Step = 0.1; |
| 564 double t10 = t1Seed - t1Step * 2; | 576 double t10 = t1Seed - t1Step * 2; |
| 565 double t12 = t1Seed + t1Step * 2; | 577 double t12 = t1Seed + t1Step * 2; |
| 566 double t20 = t2Seed - t2Step * 2; | 578 double t20 = t2Seed - t2Step * 2; |
| 567 double t22 = t2Seed + t2Step * 2; | 579 double t22 = t2Seed + t2Step * 2; |
| 568 SkDPoint test; | 580 SkDPoint test; |
| 569 while (!approximately_zero(t1Step)) { | 581 while (!approximately_zero(t1Step)) { |
| 570 test = cubic1.ptAtT(t10); | 582 test = c1.ptAtT(t10); |
| 571 t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; | 583 t10 += t1[1].approximatelyEqual(test) ? -t1Step : t1Step; |
| 572 t1Step /= 2; | 584 t1Step /= 2; |
| 573 } | 585 } |
| 574 t1Step = 0.1; | 586 t1Step = 0.1; |
| 575 while (!approximately_zero(t1Step)) { | 587 while (!approximately_zero(t1Step)) { |
| 576 test = cubic1.ptAtT(t12); | 588 test = c1.ptAtT(t12); |
| 577 t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; | 589 t12 -= t1[1].approximatelyEqual(test) ? -t1Step : t1Step; |
| 578 t1Step /= 2; | 590 t1Step /= 2; |
| 579 } | 591 } |
| 580 while (!approximately_zero(t2Step)) { | 592 while (!approximately_zero(t2Step)) { |
| 581 test = cubic2.ptAtT(t20); | 593 test = c2.ptAtT(t20); |
| 582 t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; | 594 t20 += t2[1].approximatelyEqual(test) ? -t2Step : t2Step; |
| 583 t2Step /= 2; | 595 t2Step /= 2; |
| 584 } | 596 } |
| 585 t2Step = 0.1; | 597 t2Step = 0.1; |
| 586 while (!approximately_zero(t2Step)) { | 598 while (!approximately_zero(t2Step)) { |
| 587 test = cubic2.ptAtT(t22); | 599 test = c2.ptAtT(t22); |
| 588 t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; | 600 t22 -= t2[1].approximatelyEqual(test) ? -t2Step : t2Step; |
| 589 t2Step /= 2; | 601 t2Step /= 2; |
| 590 } | 602 } |
| 591 #if ONE_OFF_DEBUG | 603 #if ONE_OFF_DEBUG |
| 592 SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, | 604 SkDebugf("%s t1=(%1.9g<%1.9g<%1.9g) t2=(%1.9g<%1.9g<%1.9g)\n", __FUNCTION__, |
| 593 t10, t1Seed, t12, t20, t2Seed, t22); | 605 t10, t1Seed, t12, t20, t2Seed, t22); |
| 594 SkDPoint p10 = cubic1.ptAtT(t10); | 606 SkDPoint p10 = c1.ptAtT(t10); |
| 595 SkDPoint p1Seed = cubic1.ptAtT(t1Seed); | 607 SkDPoint p1Seed = c1.ptAtT(t1Seed); |
| 596 SkDPoint p12 = cubic1.ptAtT(t12); | 608 SkDPoint p12 = c1.ptAtT(t12); |
| 597 SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, | 609 SkDebugf("%s p1=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, |
| 598 p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY); | 610 p10.fX, p10.fY, p1Seed.fX, p1Seed.fY, p12.fX, p12.fY); |
| 599 SkDPoint p20 = cubic2.ptAtT(t20); | 611 SkDPoint p20 = c2.ptAtT(t20); |
| 600 SkDPoint p2Seed = cubic2.ptAtT(t2Seed); | 612 SkDPoint p2Seed = c2.ptAtT(t2Seed); |
| 601 SkDPoint p22 = cubic2.ptAtT(t22); | 613 SkDPoint p22 = c2.ptAtT(t22); |
| 602 SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, | 614 SkDebugf("%s p2=(%1.9g,%1.9g)<(%1.9g,%1.9g)<(%1.9g,%1.9g)\n", __FUNCTION__, |
| 603 p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY); | 615 p20.fX, p20.fY, p2Seed.fX, p2Seed.fY, p22.fX, p22.fY); |
| 604 #endif | 616 #endif |
| 605 } | 617 } |
| 606 | 618 |
| 607 static void CubicIntersection_IntersectionFinder() { | 619 static void CubicIntersection_IntersectionFinder() { |
| 608 // double t1Seed = 0.87; | 620 // double t1Seed = 0.87; |
| 609 // double t2Seed = 0.87; | 621 // double t2Seed = 0.87; |
| 610 double t1Step = 0.000001; | 622 double t1Step = 0.000001; |
| 611 double t2Step = 0.000001; | 623 double t2Step = 0.000001; |
| 612 intersectionFinder(0, 1, 0.855895664, 0.864850875, t1Step, t2Step); | 624 intersectionFinder(0, 1, 0.855895664, 0.864850875, t1Step, t2Step); |
| 613 intersectionFinder(0, 1, 0.865207906, 0.865207887, t1Step, t2Step); | 625 intersectionFinder(0, 1, 0.865207906, 0.865207887, t1Step, t2Step); |
| 614 intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step); | 626 intersectionFinder(0, 1, 0.865213351, 0.865208087, t1Step, t2Step); |
| 615 } | 627 } |
| 616 | 628 |
| 617 static const SkDCubic selfSet[] = { | 629 static const CubicPts selfSet[] = { |
| 618 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}}, | 630 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}}, |
| 619 {{{3, 6}, {2, 3}, {4, 0}, {3, 2}}}, | 631 {{{3, 6}, {2, 3}, {4, 0}, {3, 2}}}, |
| 620 {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}}, | 632 {{{0, 2}, {2, 3}, {5, 1}, {3, 2}}}, |
| 621 {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}}, | 633 {{{0, 2}, {3, 5}, {5, 0}, {4, 2}}}, |
| 622 {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}}, | 634 {{{3.34, 8.98}, {1.95, 10.27}, {3.76, 7.65}, {4.96, 10.64}}}, |
| 623 {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}}, | 635 {{{3.13, 2.74}, {1.08, 4.62}, {3.71, 0.94}, {2.01, 3.81}}}, |
| 624 {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}}, | 636 {{{6.71, 3.14}, {7.99, 2.75}, {8.27, 1.96}, {6.35, 3.57}}}, |
| 625 {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}}, | 637 {{{12.81, 7.27}, {7.22, 6.98}, {12.49, 8.97}, {11.42, 6.18}}}, |
| 626 }; | 638 }; |
| 627 | 639 |
| 628 int selfSetCount = (int) SK_ARRAY_COUNT(selfSet); | 640 int selfSetCount = (int) SK_ARRAY_COUNT(selfSet); |
| 629 | 641 |
| 630 static void selfOneOff(skiatest::Reporter* reporter, int index) { | 642 static void selfOneOff(skiatest::Reporter* reporter, int index) { |
| 631 const SkDCubic& cubic = selfSet[index]; | 643 const CubicPts& cubic = selfSet[index]; |
| 632 SkPoint c[4]; | 644 SkPoint c[4]; |
| 633 for (int i = 0; i < 4; ++i) { | 645 for (int i = 0; i < 4; ++i) { |
| 634 c[i] = cubic[i].asSkPoint(); | 646 c[i] = cubic.fPts[i].asSkPoint(); |
| 635 } | 647 } |
| 636 SkScalar loopT; | 648 SkScalar loopT; |
| 637 SkScalar d[3]; | 649 SkScalar d[3]; |
| 638 SkCubicType cubicType = SkClassifyCubic(c, d); | 650 SkCubicType cubicType = SkClassifyCubic(c, d); |
| 639 if (SkDCubic::ComplexBreak(c, &loopT) && cubicType == SkCubicType::kLoop_SkC
ubicType) { | 651 if (SkDCubic::ComplexBreak(c, &loopT) && cubicType == SkCubicType::kLoop_SkC
ubicType) { |
| 640 SkIntersections i; | 652 SkIntersections i; |
| 641 SkPoint twoCubics[7]; | 653 SkPoint twoCubics[7]; |
| 642 SkChopCubicAt(c, twoCubics, loopT); | 654 SkChopCubicAt(c, twoCubics, loopT); |
| 643 SkDCubic chopped[2]; | 655 SkDCubic chopped[2]; |
| 644 chopped[0].set(&twoCubics[0]); | 656 chopped[0].set(&twoCubics[0]); |
| (...skipping 10 matching lines...) Expand all Loading... |
| 655 } | 667 } |
| 656 } | 668 } |
| 657 | 669 |
| 658 static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) { | 670 static void cubicIntersectionSelfTest(skiatest::Reporter* reporter) { |
| 659 int firstFail = 0; | 671 int firstFail = 0; |
| 660 for (int index = firstFail; index < selfSetCount; ++index) { | 672 for (int index = firstFail; index < selfSetCount; ++index) { |
| 661 selfOneOff(reporter, index); | 673 selfOneOff(reporter, index); |
| 662 } | 674 } |
| 663 } | 675 } |
| 664 | 676 |
| 665 static const SkDCubic coinSet[] = { | 677 static const CubicPts coinSet[] = { |
| 666 {{{72.350448608398438, 27.966041564941406}, {72.58441162109375, 27.861515045
166016}, | 678 {{{72.350448608398438, 27.966041564941406}, {72.58441162109375, 27.861515045
166016}, |
| 667 {72.818222045898437, 27.756658554077148}, {73.394996643066406, 27.497999
19128418}}}, | 679 {72.818222045898437, 27.756658554077148}, {73.394996643066406, 27.497999
19128418}}}, |
| 668 {{{73.394996643066406, 27.49799919128418}, {72.818222045898437, 27.756658554
077148}, | 680 {{{73.394996643066406, 27.49799919128418}, {72.818222045898437, 27.756658554
077148}, |
| 669 {72.58441162109375, 27.861515045166016}, {72.350448608398438, 27.9660415
64941406}}}, | 681 {72.58441162109375, 27.861515045166016}, {72.350448608398438, 27.9660415
64941406}}}, |
| 670 | 682 |
| 671 {{{297.04998779296875, 43.928997039794922}, {297.04998779296875, 43.92899703
9794922}, | 683 {{{297.04998779296875, 43.928997039794922}, {297.04998779296875, 43.92899703
9794922}, |
| 672 {300.69699096679688, 45.391998291015625}, {306.92498779296875, 43.085998
53515625}}}, | 684 {300.69699096679688, 45.391998291015625}, {306.92498779296875, 43.085998
53515625}}}, |
| 673 {{{297.04998779296875, 43.928997039794922}, {297.04998779296875, 43.92899703
9794922}, | 685 {{{297.04998779296875, 43.928997039794922}, {297.04998779296875, 43.92899703
9794922}, |
| 674 {300.69699096679688, 45.391998291015625}, {306.92498779296875, 43.085998
53515625}}}, | 686 {300.69699096679688, 45.391998291015625}, {306.92498779296875, 43.085998
53515625}}}, |
| 675 | 687 |
| 676 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}}, | 688 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}}, |
| 677 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}}, | 689 {{{2, 3}, {0, 4}, {3, 2}, {5, 3}}}, |
| 678 | 690 |
| 679 {{{317, 711}, {322.52285766601562, 711}, {327, 715.4771728515625}, {327, 721
}}}, | 691 {{{317, 711}, {322.52285766601562, 711}, {327, 715.4771728515625}, {327, 721
}}}, |
| 680 {{{324.07107543945312, 713.928955078125}, {324.4051513671875, 714.2630004882
8125}, | 692 {{{324.07107543945312, 713.928955078125}, {324.4051513671875, 714.2630004882
8125}, |
| 681 {324.71566772460937, 714.62060546875}, {325, 714.9990234375}}}, | 693 {324.71566772460937, 714.62060546875}, {325, 714.9990234375}}}, |
| 682 }; | 694 }; |
| 683 | 695 |
| 684 static int coinSetCount = (int) SK_ARRAY_COUNT(coinSet); | 696 static int coinSetCount = (int) SK_ARRAY_COUNT(coinSet); |
| 685 | 697 |
| 686 static void coinOneOff(skiatest::Reporter* reporter, int index) { | 698 static void coinOneOff(skiatest::Reporter* reporter, int index) { |
| 687 const SkDCubic& cubic1 = coinSet[index]; | 699 const CubicPts& cubic1 = coinSet[index]; |
| 688 const SkDCubic& cubic2 = coinSet[index + 1]; | 700 const CubicPts& cubic2 = coinSet[index + 1]; |
| 689 oneOff(reporter, cubic1, cubic2, true); | 701 oneOff(reporter, cubic1, cubic2, true); |
| 690 } | 702 } |
| 691 | 703 |
| 692 static void cubicIntersectionCoinTest(skiatest::Reporter* reporter) { | 704 static void cubicIntersectionCoinTest(skiatest::Reporter* reporter) { |
| 693 int firstFail = 0; | 705 int firstFail = 0; |
| 694 for (int index = firstFail; index < coinSetCount; index += 2) { | 706 for (int index = firstFail; index < coinSetCount; index += 2) { |
| 695 coinOneOff(reporter, index); | 707 coinOneOff(reporter, index); |
| 696 } | 708 } |
| 697 } | 709 } |
| 698 | 710 |
| (...skipping 14 matching lines...) Expand all Loading... |
| 713 } | 725 } |
| 714 | 726 |
| 715 DEF_TEST(PathOpsCubicIntersection, reporter) { | 727 DEF_TEST(PathOpsCubicIntersection, reporter) { |
| 716 oneOffTests(reporter); | 728 oneOffTests(reporter); |
| 717 cubicIntersectionSelfTest(reporter); | 729 cubicIntersectionSelfTest(reporter); |
| 718 cubicIntersectionCoinTest(reporter); | 730 cubicIntersectionCoinTest(reporter); |
| 719 standardTestCases(reporter); | 731 standardTestCases(reporter); |
| 720 if (false) CubicIntersection_IntersectionFinder(); | 732 if (false) CubicIntersection_IntersectionFinder(); |
| 721 if (false) CubicIntersection_RandTest(reporter); | 733 if (false) CubicIntersection_RandTest(reporter); |
| 722 } | 734 } |
| OLD | NEW |