Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(392)

Side by Side Diff: tests/PathOpsCubicIntersectionTest.cpp

Issue 2426173002: fix fuzzers (Closed)
Patch Set: fix dm Created 4 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « tests/PathOpsCubicConicIntersectionTest.cpp ('k') | tests/PathOpsCubicIntersectionTestData.h » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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 }
OLDNEW
« no previous file with comments | « tests/PathOpsCubicConicIntersectionTest.cpp ('k') | tests/PathOpsCubicIntersectionTestData.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698