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 |