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

Side by Side Diff: tests/PathOpsAngleIdeas.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 | « src/pathops/SkPathWriter.cpp ('k') | tests/PathOpsAngleTest.cpp » ('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 2013 Google Inc. 2 * Copyright 2013 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 "PathOpsTestCommon.h" 7 #include "PathOpsTestCommon.h"
8 #include "SkIntersections.h" 8 #include "SkIntersections.h"
9 #include "SkOpContour.h" 9 #include "SkOpContour.h"
10 #include "SkOpSegment.h" 10 #include "SkOpSegment.h"
(...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after
70 REPORTER_ASSERT(reporter, t >= 0 && t <= 1); 70 REPORTER_ASSERT(reporter, t >= 0 && t <= 1);
71 return i[1][smallest]; 71 return i[1][smallest];
72 } 72 }
73 73
74 static void orderQuads(skiatest::Reporter* reporter, const SkDQuad& quad, double radius, 74 static void orderQuads(skiatest::Reporter* reporter, const SkDQuad& quad, double radius,
75 SkTArray<double, false>* tArray) { 75 SkTArray<double, false>* tArray) {
76 double r = radius; 76 double r = radius;
77 double s = r * SK_ScalarTanPIOver8; 77 double s = r * SK_ScalarTanPIOver8;
78 double m = r * SK_ScalarRoot2Over2; 78 double m = r * SK_ScalarRoot2Over2;
79 // construct circle from quads 79 // construct circle from quads
80 const SkDQuad circle[8] = {{{{ r, 0}, { r, -s}, { m, -m}}}, 80 const QuadPts circle[8] = {{{{ r, 0}, { r, -s}, { m, -m}}},
81 {{{ m, -m}, { s, -r}, { 0, -r}}}, 81 {{{ m, -m}, { s, -r}, { 0, -r}}},
82 {{{ 0, -r}, {-s, -r}, {-m, -m}}}, 82 {{{ 0, -r}, {-s, -r}, {-m, -m}}},
83 {{{-m, -m}, {-r, -s}, {-r, 0}}}, 83 {{{-m, -m}, {-r, -s}, {-r, 0}}},
84 {{{-r, 0}, {-r, s}, {-m, m}}}, 84 {{{-r, 0}, {-r, s}, {-m, m}}},
85 {{{-m, m}, {-s, r}, { 0, r}}}, 85 {{{-m, m}, {-s, r}, { 0, r}}},
86 {{{ 0, r}, { s, r}, { m, m}}}, 86 {{{ 0, r}, { s, r}, { m, m}}},
87 {{{ m, m}, { r, s}, { r, 0}}}}; 87 {{{ m, m}, { r, s}, { r, 0}}}};
88 for (int octant = 0; octant < 8; ++octant) { 88 for (int octant = 0; octant < 8; ++octant) {
89 double t = testArc(reporter, quad, circle[octant], octant); 89 SkDQuad cQuad;
90 cQuad.debugSet(circle[octant].fPts);
91 double t = testArc(reporter, quad, cQuad, octant);
90 if (t < 0) { 92 if (t < 0) {
91 continue; 93 continue;
92 } 94 }
93 for (int index = 0; index < tArray->count(); ++index) { 95 for (int index = 0; index < tArray->count(); ++index) {
94 double matchT = (*tArray)[index]; 96 double matchT = (*tArray)[index];
95 if (approximately_equal(t, matchT)) { 97 if (approximately_equal(t, matchT)) {
96 goto next; 98 goto next;
97 } 99 }
98 } 100 }
99 tArray->push_back(t); 101 tArray->push_back(t);
(...skipping 225 matching lines...) Expand 10 before | Expand all | Expand 10 after
325 *upperRange = tRange; 327 *upperRange = tRange;
326 } 328 }
327 if (lowerRange->tMin > tRange.tMin) { 329 if (lowerRange->tMin > tRange.tMin) {
328 *lowerRange = tRange; 330 *lowerRange = tRange;
329 } 331 }
330 } 332 }
331 r += stepUp ? rStep : -rStep; 333 r += stepUp ? rStep : -rStep;
332 rStep /= 2; 334 rStep /= 2;
333 } while (rStep > FLT_EPSILON); 335 } while (rStep > FLT_EPSILON);
334 if (bestCCW < 0) { 336 if (bestCCW < 0) {
337 if (bestR >= maxRadius) {
338 SkDebugf("");
339 }
335 REPORTER_ASSERT(reporter, bestR < maxRadius); 340 REPORTER_ASSERT(reporter, bestR < maxRadius);
336 return false; 341 return false;
337 } 342 }
338 double lastHighR = bestR; 343 double lastHighR = bestR;
339 r = bestR / 2; 344 r = bestR / 2;
340 rStep = r / 2; 345 rStep = r / 2;
341 do { // find lower bounds of single result 346 do { // find lower bounds of single result
342 TRange tRange; 347 TRange tRange;
343 bool success = orderTRange(reporter, quad1, quad2, r, &tRange); 348 bool success = orderTRange(reporter, quad1, quad2, r, &tRange);
344 if (success) { 349 if (success) {
(...skipping 203 matching lines...) Expand 10 before | Expand all | Expand 10 after
548 PathOpsAngleTester::EndsIntersect(*seg1->debugLastAngle(), 553 PathOpsAngleTester::EndsIntersect(*seg1->debugLastAngle(),
549 *seg2->debugLastAngle()); 554 *seg2->debugLastAngle());
550 SkASSERT(realEnds == (firstInside ? 1 : 0)); 555 SkASSERT(realEnds == (firstInside ? 1 : 0));
551 } 556 }
552 bruteForce(reporter, quad1, quad2, firstInside); 557 bruteForce(reporter, quad1, quad2, firstInside);
553 } 558 }
554 559
555 DEF_TEST(PathOpsAngleOverlapHullsOne, reporter) { 560 DEF_TEST(PathOpsAngleOverlapHullsOne, reporter) {
556 SkChunkAlloc allocator(4096); 561 SkChunkAlloc allocator(4096);
557 // gPathOpsAngleIdeasVerbose = true; 562 // gPathOpsAngleIdeasVerbose = true;
558 const SkDQuad quads[] = { 563 const QuadPts quads[] = {
559 {{{939.4808349609375, 914.355224609375}, {-357.7921142578125, 590.842529296875}, {736.8936767578125, -350.717529296875}}}, 564 {{{939.4808349609375, 914.355224609375}, {-357.7921142578125, 590.842529296875}, {736.8936767578125, -350.717529296875}}},
560 {{{939.4808349609375, 914.355224609375}, {-182.85418701171875, 634.4552001953125 }, {-509.62615966796875, 576.1182861328125}}} 565 {{{939.4808349609375, 914.355224609375}, {-182.85418701171875, 634.4552001953125 }, {-509.62615966796875, 576.1182861328125}}}
561 }; 566 };
562 for (int index = 0; index < (int) SK_ARRAY_COUNT(quads); index += 2) { 567 for (int index = 0; index < (int) SK_ARRAY_COUNT(quads); index += 2) {
563 testQuadAngles(reporter, quads[index], quads[index + 1], 0, &allocator); 568 SkDQuad quad0, quad1;
569 quad0.debugSet(quads[index].fPts);
570 quad1.debugSet(quads[index + 1].fPts);
571 testQuadAngles(reporter, quad0, quad1, 0, &allocator);
564 } 572 }
565 } 573 }
566 574
567 DEF_TEST(PathOpsAngleOverlapHulls, reporter) { 575 DEF_TEST(PathOpsAngleOverlapHulls, reporter) {
568 SkChunkAlloc allocator(4096); 576 SkChunkAlloc allocator(4096);
569 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default 577 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default
570 return; 578 return;
571 } 579 }
572 SkRandom ran; 580 SkRandom ran;
573 for (int index = 0; index < 100000; ++index) { 581 for (int index = 0; index < 100000; ++index) {
574 if (index % 1000 == 999) SkDebugf("."); 582 if (index % 1000 == 999) SkDebugf(".");
575 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 10 00)}; 583 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 10 00)};
576 SkDQuad quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(- 1000, 1000)}, 584 QuadPts quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(- 1000, 1000)},
577 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 585 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
578 if (quad1[0] == quad1[2]) { 586 if (quad1.fPts[0] == quad1.fPts[2]) {
579 continue; 587 continue;
580 } 588 }
581 SkDQuad quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(- 1000, 1000)}, 589 QuadPts quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(- 1000, 1000)},
582 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 590 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
583 if (quad2[0] == quad2[2]) { 591 if (quad2.fPts[0] == quad2.fPts[2]) {
584 continue; 592 continue;
585 } 593 }
586 SkIntersections i; 594 SkIntersections i;
587 i.intersect(quad1, quad2); 595 SkDQuad q1, q2;
596 q1.debugSet(quad1.fPts);
597 q2.debugSet(quad2.fPts);
598 i.intersect(q1, q2);
588 REPORTER_ASSERT(reporter, i.used() >= 1); 599 REPORTER_ASSERT(reporter, i.used() >= 1);
589 if (i.used() > 1) { 600 if (i.used() > 1) {
590 continue; 601 continue;
591 } 602 }
592 testQuadAngles(reporter, quad1, quad2, index, &allocator); 603 testQuadAngles(reporter, q1, q2, index, &allocator);
593 } 604 }
594 } 605 }
595 606
596 DEF_TEST(PathOpsAngleBruteT, reporter) { 607 DEF_TEST(PathOpsAngleBruteT, reporter) {
597 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default 608 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default
598 return; 609 return;
599 } 610 }
600 SkRandom ran; 611 SkRandom ran;
601 double smaller = SK_Scalar1; 612 double smaller = SK_Scalar1;
602 SkDQuad small[2]; 613 SkDQuad small[2];
603 SkDEBUGCODE(int smallIndex); 614 SkDEBUGCODE(int smallIndex);
604 for (int index = 0; index < 100000; ++index) { 615 for (int index = 0; index < 100000; ++index) {
605 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 10 00)}; 616 SkDPoint origin = {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 10 00)};
606 SkDQuad quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(- 1000, 1000)}, 617 QuadPts quad1 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(- 1000, 1000)},
607 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 618 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
608 if (quad1[0] == quad1[2]) { 619 if (quad1.fPts[0] == quad1.fPts[2]) {
609 continue; 620 continue;
610 } 621 }
611 SkDQuad quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(- 1000, 1000)}, 622 QuadPts quad2 = {{origin, {ran.nextRangeF(-1000, 1000), ran.nextRangeF(- 1000, 1000)},
612 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}}; 623 {ran.nextRangeF(-1000, 1000), ran.nextRangeF(-1000, 1000)}}};
613 if (quad2[0] == quad2[2]) { 624 if (quad2.fPts[0] == quad2.fPts[2]) {
614 continue; 625 continue;
615 } 626 }
627 SkDQuad q1, q2;
628 q1.debugSet(quad1.fPts);
629 q2.debugSet(quad2.fPts);
616 SkIntersections i; 630 SkIntersections i;
617 i.intersect(quad1, quad2); 631 i.intersect(q1, q2);
618 REPORTER_ASSERT(reporter, i.used() >= 1); 632 REPORTER_ASSERT(reporter, i.used() >= 1);
619 if (i.used() > 1) { 633 if (i.used() > 1) {
620 continue; 634 continue;
621 } 635 }
622 TRange lowerRange, upperRange; 636 TRange lowerRange, upperRange;
623 bool result = bruteMinT(reporter, quad1, quad2, &lowerRange, &upperRange ); 637 bool result = bruteMinT(reporter, q1, q2, &lowerRange, &upperRange);
624 REPORTER_ASSERT(reporter, result); 638 REPORTER_ASSERT(reporter, result);
625 double min = SkTMin(upperRange.t1, upperRange.t2); 639 double min = SkTMin(upperRange.t1, upperRange.t2);
626 if (smaller > min) { 640 if (smaller > min) {
627 small[0] = quad1; 641 small[0] = q1;
628 small[1] = quad2; 642 small[1] = q2;
629 SkDEBUGCODE(smallIndex = index); 643 SkDEBUGCODE(smallIndex = index);
630 smaller = min; 644 smaller = min;
631 } 645 }
632 } 646 }
633 #ifdef SK_DEBUG 647 #ifdef SK_DEBUG
634 DumpQ(small[0], small[1], smallIndex); 648 DumpQ(small[0], small[1], smallIndex);
635 #endif 649 #endif
636 } 650 }
637 651
638 DEF_TEST(PathOpsAngleBruteTOne, reporter) { 652 DEF_TEST(PathOpsAngleBruteTOne, reporter) {
639 // gPathOpsAngleIdeasVerbose = true; 653 // gPathOpsAngleIdeasVerbose = true;
640 const SkDQuad quads[] = { 654 const QuadPts qPts[] = {
641 {{{-770.8492431640625, 948.2369384765625}, {-853.37066650390625, 972.03015136718 75}, {-200.62042236328125, -26.7174072265625}}}, 655 {{{-770.8492431640625, 948.2369384765625}, {-853.37066650390625, 972.03015136718 75}, {-200.62042236328125, -26.7174072265625}}},
642 {{{-770.8492431640625, 948.2369384765625}, {513.602783203125, 578.8681640625}, { 960.641357421875, -813.69757080078125}}}, 656 {{{-770.8492431640625, 948.2369384765625}, {513.602783203125, 578.8681640625}, { 960.641357421875, -813.69757080078125}}},
643 {{{563.8267822265625, -107.4566650390625}, {-44.67724609375, -136.57452392578125 }, {492.3856201171875, -268.79644775390625}}}, 657 {{{563.8267822265625, -107.4566650390625}, {-44.67724609375, -136.57452392578125 }, {492.3856201171875, -268.79644775390625}}},
644 {{{563.8267822265625, -107.4566650390625}, {708.049072265625, -100.7778930664062 5}, {-48.88226318359375, 967.9022216796875}}}, 658 {{{563.8267822265625, -107.4566650390625}, {708.049072265625, -100.7778930664062 5}, {-48.88226318359375, 967.9022216796875}}},
645 {{{598.857421875, 846.345458984375}, {-644.095703125, -316.12921142578125}, {-97 .64599609375, 20.6158447265625}}}, 659 {{{598.857421875, 846.345458984375}, {-644.095703125, -316.12921142578125}, {-97 .64599609375, 20.6158447265625}}},
646 {{{598.857421875, 846.345458984375}, {715.7142333984375, 955.3599853515625}, {-9 19.9478759765625, 691.611328125}}}, 660 {{{598.857421875, 846.345458984375}, {715.7142333984375, 955.3599853515625}, {-9 19.9478759765625, 691.611328125}}},
647 }; 661 };
648 TRange lowerRange, upperRange; 662 TRange lowerRange, upperRange;
663 SkDQuad quads[SK_ARRAY_COUNT(qPts)];
664 for (int index = 0; index < (int) SK_ARRAY_COUNT(qPts); ++index) {
665 quads[index].debugSet(qPts[index].fPts);
666 }
649 bruteMinT(reporter, quads[0], quads[1], &lowerRange, &upperRange); 667 bruteMinT(reporter, quads[0], quads[1], &lowerRange, &upperRange);
650 bruteMinT(reporter, quads[2], quads[3], &lowerRange, &upperRange); 668 bruteMinT(reporter, quads[2], quads[3], &lowerRange, &upperRange);
651 bruteMinT(reporter, quads[4], quads[5], &lowerRange, &upperRange); 669 bruteMinT(reporter, quads[4], quads[5], &lowerRange, &upperRange);
652 } 670 }
653 671
654 /* 672 /*
655 The sorting problem happens when the inital tangents are not a true indicator of the curve direction 673 The sorting problem happens when the inital tangents are not a true indicator of the curve direction
656 Nearly always, the initial tangents do give the right answer, 674 Nearly always, the initial tangents do give the right answer,
657 so the trick is to figure out when the initial tangent cannot be trusted. 675 so the trick is to figure out when the initial tangent cannot be trusted.
658 If the convex hulls of both curves are in the same half plane, and not overlappi ng, sorting the 676 If the convex hulls of both curves are in the same half plane, and not overlappi ng, sorting the
659 hulls is enough. 677 hulls is enough.
660 If the hulls overlap, and have the same general direction, then intersect the sh orter end point ray 678 If the hulls overlap, and have the same general direction, then intersect the sh orter end point ray
661 with the opposing curve, and see on which side of the shorter curve the opposing intersection lies. 679 with the opposing curve, and see on which side of the shorter curve the opposing intersection lies.
662 Otherwise, if the control vector is extremely short, likely the point on curve m ust be computed 680 Otherwise, if the control vector is extremely short, likely the point on curve m ust be computed
663 If moving the control point slightly can change the sign of the cross product, e ither answer could 681 If moving the control point slightly can change the sign of the cross product, e ither answer could
664 be "right". 682 be "right".
665 We need to determine how short is extremely short. Move the control point a set percentage of 683 We need to determine how short is extremely short. Move the control point a set percentage of
666 the largest length to determine how stable the curve is vis-a-vis the initial ta ngent. 684 the largest length to determine how stable the curve is vis-a-vis the initial ta ngent.
667 */ 685 */
668 686
669 static const SkDQuad extremeTests[][2] = { 687 static const QuadPts extremeTests[][2] = {
670 { 688 {
671 {{{-708.0077926931004,-154.61669472244046}, 689 {{{-708.0077926931004,-154.61669472244046},
672 {-707.9234268635319,-154.30459999551294}, 690 {-707.9234268635319,-154.30459999551294},
673 {505.58447265625,-504.9130859375}}}, 691 {505.58447265625,-504.9130859375}}},
674 {{{-708.0077926931004,-154.61669472244046}, 692 {{{-708.0077926931004,-154.61669472244046},
675 {-711.127526325141,-163.9446090624656}, 693 {-711.127526325141,-163.9446090624656},
676 {-32.39227294921875,-906.3277587890625}}}, 694 {-32.39227294921875,-906.3277587890625}}},
677 }, { 695 }, {
678 {{{-708.0077926931004,-154.61669472244046}, 696 {{{-708.0077926931004,-154.61669472244046},
679 {-708.2875337527566,-154.36676458635623}, 697 {-708.2875337527566,-154.36676458635623},
(...skipping 106 matching lines...) Expand 10 before | Expand all | Expand 10 after
786 SkDVector m2 = mid2 - q2[0]; 804 SkDVector m2 = mid2 - q2[0];
787 REPORTER_ASSERT(reporter, ccw ? m1.crossCheck(m2) < 0 : m1.crossCheck(m2) > 0); 805 REPORTER_ASSERT(reporter, ccw ? m1.crossCheck(m2) < 0 : m1.crossCheck(m2) > 0);
788 } 806 }
789 807
790 DEF_TEST(PathOpsAngleExtreme, reporter) { 808 DEF_TEST(PathOpsAngleExtreme, reporter) {
791 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default 809 if (!gPathOpsAngleIdeasVerbose) { // takes a while to run -- so exclude it by default
792 return; 810 return;
793 } 811 }
794 double maxR = SK_ScalarMax; 812 double maxR = SK_ScalarMax;
795 for (int index = 0; index < (int) SK_ARRAY_COUNT(extremeTests); ++index) { 813 for (int index = 0; index < (int) SK_ARRAY_COUNT(extremeTests); ++index) {
796 const SkDQuad& quad1 = extremeTests[index][0]; 814 const QuadPts& qu1 = extremeTests[index][0];
797 const SkDQuad& quad2 = extremeTests[index][1]; 815 const QuadPts& qu2 = extremeTests[index][1];
816 SkDQuad quad1, quad2;
817 quad1.debugSet(qu1.fPts);
818 quad2.debugSet(qu2.fPts);
798 if (gPathOpsAngleIdeasVerbose) { 819 if (gPathOpsAngleIdeasVerbose) {
799 SkDebugf("%s %d\n", __FUNCTION__, index); 820 SkDebugf("%s %d\n", __FUNCTION__, index);
800 } 821 }
801 REPORTER_ASSERT(reporter, quad1[0] == quad2[0]); 822 REPORTER_ASSERT(reporter, quad1[0] == quad2[0]);
802 SkIntersections i; 823 SkIntersections i;
803 i.intersect(quad1, quad2); 824 i.intersect(quad1, quad2);
804 REPORTER_ASSERT(reporter, i.used() == 1); 825 REPORTER_ASSERT(reporter, i.used() == 1);
805 REPORTER_ASSERT(reporter, i.pt(0) == quad1[0]); 826 REPORTER_ASSERT(reporter, i.pt(0) == quad1[0]);
806 int overlap = quadHullsOverlap(reporter, quad1, quad2); 827 int overlap = quadHullsOverlap(reporter, quad1, quad2);
807 REPORTER_ASSERT(reporter, overlap >= 0); 828 REPORTER_ASSERT(reporter, overlap >= 0);
(...skipping 45 matching lines...) Expand 10 before | Expand all | Expand 10 after
853 step /= 2; 874 step /= 2;
854 } 875 }
855 #ifdef SK_DEBUG 876 #ifdef SK_DEBUG
856 // DumpQ(q1, q2, 999); 877 // DumpQ(q1, q2, 999);
857 #endif 878 #endif
858 } 879 }
859 if (gPathOpsAngleIdeasVerbose) { 880 if (gPathOpsAngleIdeasVerbose) {
860 SkDebugf("maxR=%1.9g\n", maxR); 881 SkDebugf("maxR=%1.9g\n", maxR);
861 } 882 }
862 } 883 }
OLDNEW
« no previous file with comments | « src/pathops/SkPathWriter.cpp ('k') | tests/PathOpsAngleTest.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698