From e4097e3a0b10bb0047a45b6949ca01826f0807a7 Mon Sep 17 00:00:00 2001 From: caryclark Date: Wed, 18 Jun 2014 07:24:19 -0700 Subject: [PATCH] Fix last pathops skp bug This fixes the last bug discovered by iterating through the 800K skp corpus representing the top 1M websites. For every clip on the stack, the paths are replaced with the pathop intersection. The resulting draw is compared with the original draw for pixel errors. At least two prominent bugs remain. In one, the winding value is confused by a cubic with an inflection. In the other, a quad/cubic pair, nearly coincident, fails to find an intersection. These minor changes include ignoring very tiny self-intersections of cubics, and processing degenerate edges that don't connect to anything else. R=reed@android.com TBR=reed Author: caryclark@google.com Review URL: https://codereview.chromium.org/340103002 --- src/pathops/SkDCubicIntersection.cpp | 12 +- src/pathops/SkOpSegment.cpp | 59 ++- src/pathops/SkOpSegment.h | 2 +- src/pathops/SkPathOpsDebug.cpp | 7 +- tests/PathOpsCubicQuadIntersectionTest.cpp | 2 +- tests/PathOpsDebug.cpp | 3 +- tests/PathOpsOpTest.cpp | 54 +-- tests/PathOpsSkpTest.cpp | 6 - tests/PathOpsTestCommon.cpp | 88 ++++ tests/PathOpsTestCommon.h | 2 + tools/pathops_sorter.htm | 6 + tools/pathops_visualizer.htm | 755 +++-------------------------- 12 files changed, 273 insertions(+), 723 deletions(-) diff --git a/src/pathops/SkDCubicIntersection.cpp b/src/pathops/SkDCubicIntersection.cpp index 1c237d9..9d83242 100644 --- a/src/pathops/SkDCubicIntersection.cpp +++ b/src/pathops/SkDCubicIntersection.cpp @@ -681,11 +681,17 @@ int SkIntersections::intersect(const SkDCubic& c) { if (c.endsAreExtremaInXOrY()) { return false; } + // OPTIMIZATION: could quick reject if neither end point tangent ray intersected the line + // segment formed by the opposite end point to the control point (void) intersect(c, c); if (used() > 0) { - SkASSERT(used() == 1); - if (fT[0][0] > fT[1][0]) { - swapPts(); + if (approximately_equal_double(fT[0][0], fT[1][0])) { + fUsed = 0; + } else { + SkASSERT(used() == 1); + if (fT[0][0] > fT[1][0]) { + swapPts(); + } } } return used(); diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index 090173f..4e8b5d2 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -3090,7 +3090,8 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort markAngle = addSingletonAngles(step); } markAngle->markStops(); - const SkOpAngle* baseAngle = markAngle->findFirst(); + const SkOpAngle* baseAngle = markAngle->next() == markAngle && !isVertical() ? markAngle + : markAngle->findFirst(); if (!baseAngle) { return NULL; // nothing to do } @@ -3137,9 +3138,8 @@ SkOpSegment* SkOpSegment::findTop(int* tIndexPtr, int* endIndexPtr, bool* unsort if (leftSegment->verb() >= SkPath::kQuad_Verb) { const int tIndex = *tIndexPtr; const int endIndex = *endIndexPtr; - if (!leftSegment->clockwise(tIndex, endIndex)) { - bool swap = !leftSegment->monotonicInY(tIndex, endIndex) - && !leftSegment->serpentine(tIndex, endIndex); + bool swap; + if (!leftSegment->clockwise(tIndex, endIndex, &swap)) { #if DEBUG_SWAP_TOP SkDebugf("%s swap=%d inflections=%d serpentine=%d controlledbyends=%d monotonic=%d\n", __FUNCTION__, @@ -3621,13 +3621,45 @@ SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int windi } // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order -bool SkOpSegment::clockwise(int tStart, int tEnd) const { +bool SkOpSegment::clockwise(int tStart, int tEnd, bool* swap) const { SkASSERT(fVerb != SkPath::kLine_Verb); SkPoint edge[4]; subDivide(tStart, tEnd, edge); int points = SkPathOpsVerbToPoints(fVerb); double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY); + bool sumSet = false; if (fVerb == SkPath::kCubic_Verb) { + SkDCubic cubic; + cubic.set(edge); + double inflectionTs[2]; + int inflections = cubic.findInflections(inflectionTs); + // FIXME: this fixes cubicOp114 and breaks cubicOp58d + // the trouble is that cubics with inflections confuse whether the curve breaks towards + // or away, which in turn is used to determine if it is on the far right or left. + // Probably a totally different approach is in order. At one time I tried to project a + // horizontal ray to determine winding, but was confused by how to map the vertically + // oriented winding computation over. + if (0 && inflections) { + double tLo = this->span(tStart).fT; + double tHi = this->span(tEnd).fT; + double tLoStart = tLo; + for (int index = 0; index < inflections; ++index) { + if (between(tLo, inflectionTs[index], tHi)) { + tLo = inflectionTs[index]; + } + } + if (tLo != tLoStart && tLo != tHi) { + SkDPoint sub[2]; + sub[0] = cubic.ptAtT(tLo); + sub[1].set(edge[3]); + SkDPoint ctrl[2]; + SkDCubic::SubDivide(fPts, sub[0], sub[1], tLo, tHi, ctrl); + edge[0] = sub[0].asSkPoint(); + edge[1] = ctrl[0].asSkPoint(); + edge[2] = ctrl[1].asSkPoint(); + sum = (edge[0].fX - edge[3].fX) * (edge[0].fY + edge[3].fY); + } + } SkScalar lesser = SkTMin(edge[0].fY, edge[3].fY); if (edge[1].fY < lesser && edge[2].fY < lesser) { SkDLine tangent1 = {{ {edge[0].fX, edge[0].fY}, {edge[1].fX, edge[1].fY} }}; @@ -3636,12 +3668,23 @@ bool SkOpSegment::clockwise(int tStart, int tEnd) const { SkPoint topPt = cubic_top(fPts, fTs[tStart].fT, fTs[tEnd].fT); sum += (topPt.fX - edge[0].fX) * (topPt.fY + edge[0].fY); sum += (edge[3].fX - topPt.fX) * (edge[3].fY + topPt.fY); - return sum <= 0; + sumSet = true; } } } - for (int idx = 0; idx < points; ++idx){ - sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY); + if (!sumSet) { + for (int idx = 0; idx < points; ++idx){ + sum += (edge[idx + 1].fX - edge[idx].fX) * (edge[idx + 1].fY + edge[idx].fY); + } + } + if (fVerb == SkPath::kCubic_Verb) { + SkDCubic cubic; + cubic.set(edge); + *swap = sum > 0 && !cubic.monotonicInY() && !cubic.serpentine(); + } else { + SkDQuad quad; + quad.set(edge); + *swap = sum > 0 && !quad.monotonicInY(); } return sum <= 0; } diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 90ed553..d191e88 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -423,7 +423,7 @@ private: int checkSetAngle(int tIndex) const; void checkSmallCoincidence(const SkOpSpan& span, SkTArray* ); bool coincidentSmall(const SkPoint& pt, double t, const SkOpSegment* other) const; - bool clockwise(int tStart, int tEnd) const; + bool clockwise(int tStart, int tEnd, bool* swap) const; static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, SkOpAngle::IncludeType ); static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 9d82dff..96029b3 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -104,7 +104,12 @@ void SkPathOpsDebug::ShowPath(const SkPath& one, const SkPath& two, SkPathOp op, #if DEBUG_SORT void SkOpAngle::debugLoop() const { - dumpLoop(); + const SkOpAngle* first = this; + const SkOpAngle* next = this; + do { + next->dumpOne(true); + next = next->fNext; + } while (next && next != first); } #endif diff --git a/tests/PathOpsCubicQuadIntersectionTest.cpp b/tests/PathOpsCubicQuadIntersectionTest.cpp index db895d4..967dfc7 100644 --- a/tests/PathOpsCubicQuadIntersectionTest.cpp +++ b/tests/PathOpsCubicQuadIntersectionTest.cpp @@ -12,7 +12,7 @@ #include "SkReduceOrder.h" #include "Test.h" -static struct lineCubic { +static struct quadCubic { SkDCubic cubic; SkDQuad quad; int answerCount; diff --git a/tests/PathOpsDebug.cpp b/tests/PathOpsDebug.cpp index a2b48ac..af60318 100755 --- a/tests/PathOpsDebug.cpp +++ b/tests/PathOpsDebug.cpp @@ -110,7 +110,8 @@ void SkOpAngle::dumpLoop() const { const SkOpAngle* first = this; const SkOpAngle* next = this; do { - next->dump(); + next->dumpOne(false); + SkDebugf("\n"); next = next->fNext; } while (next && next != first); } diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index 5317792..1d63bd7 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -5,6 +5,7 @@ * found in the LICENSE file. */ #include "PathOpsExtendedTest.h" +#include "PathOpsTestCommon.h" #define TEST(name) { name, #name } @@ -1832,8 +1833,6 @@ static void skpkkiste_to98(skiatest::Reporter* reporter, const char* filename) { testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#define ISSUE_1417_WORKING_ON_LINUX_32 0 // fails only in release linux skia_arch_width=32 -#if ISSUE_1417_WORKING_ON_LINUX_32 static void issue1417(skiatest::Reporter* reporter, const char* filename) { SkPath path1; path1.moveTo(122.58908843994140625f, 82.2836456298828125f); @@ -1945,7 +1944,6 @@ static void issue1417(skiatest::Reporter* reporter, const char* filename) { testPathOp(reporter, path1, path2, kUnion_PathOp, filename); } -#endif static void issue1418(skiatest::Reporter* reporter, const char* filename) { SkPath path1; @@ -2065,8 +2063,6 @@ static void rectOp3x(skiatest::Reporter* reporter, const char* filename) { testPathOp(reporter, path, pathB, kXOR_PathOp, filename); } -#define ISSUE_1435_FIXED 0 -#if ISSUE_1435_FIXED // this fails to generate two interior line segments // an earlier pathops succeeded, but still failed to generate one interior line segment // (but was saved by assemble, which works around a single line missing segment) @@ -2120,7 +2116,6 @@ static void issue1435(skiatest::Reporter* reporter, const char* filename) { path2.setFillType(SkPath::kEvenOdd_FillType); testPathOp(reporter, path1, path2, kIntersect_PathOp, filename); } -#endif static void skpkkiste_to716(skiatest::Reporter* reporter, const char* filename) { SkPath path; @@ -2736,8 +2731,8 @@ static void skpcarpetplanet_ru22(skiatest::Reporter* reporter, const char* filen testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#define SKPS_WORKING 0 -#if SKPS_WORKING +#define QUAD_CUBIC_FAILS_TO_FIND_INTERSECTION 0 +#if QUAD_CUBIC_FAILS_TO_FIND_INTERSECTION // this fails because cubic/quad misses an intersection (failure is isolated in c/q int test) static void skpcarrot_is24(skiatest::Reporter* reporter, const char* filename) { SkPath path; @@ -3277,8 +3272,6 @@ static void cubicOp112(skiatest::Reporter* reporter, const char* filename) { testPathOp(reporter, path, pathB, kDifference_PathOp, filename); } -// triggers untested calcLoopSpanCount code path -#if 0 static void cubicOp113(skiatest::Reporter* reporter, const char* filename) { SkPath path, pathB; path.moveTo(2,4); @@ -3289,8 +3282,9 @@ static void cubicOp113(skiatest::Reporter* reporter, const char* filename) { pathB.close(); testPathOp(reporter, path, pathB, kDifference_PathOp, filename); } -#endif +#define CUBIC_OP_114 0 +#if CUBIC_OP_114 static void cubicOp114(skiatest::Reporter* reporter, const char* filename) { SkPath path, pathB; path.setFillType(SkPath::kWinding_FillType); @@ -3303,6 +3297,23 @@ static void cubicOp114(skiatest::Reporter* reporter, const char* filename) { pathB.close(); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } +#endif + +static void cubicOp114asQuad(skiatest::Reporter* reporter, const char* filename) { + SkPath path, pathB; + path.setFillType(SkPath::kWinding_FillType); + path.moveTo(0, 1); + path.cubicTo(1, 3, -1, 2, 3.5f, 1.33333337f); + path.close(); + pathB.setFillType(SkPath::kWinding_FillType); + pathB.moveTo(1, 3); + pathB.cubicTo(-1, 2, 3.5f, 1.33333337f, 0, 1); + pathB.close(); + SkPath qPath, qPathB; + CubicPathToQuads(path, &qPath); + CubicPathToQuads(pathB, &qPathB); + testPathOp(reporter, qPath, qPathB, kIntersect_PathOp, filename); +} static void quadOp10i(skiatest::Reporter* reporter, const char* filename) { SkPath path, pathB; @@ -3354,8 +3365,6 @@ static void issue2504(skiatest::Reporter* reporter, const char* filename) { testPathOp(reporter, path1, path2, kUnion_PathOp, filename); } -#define TEST_2540 0 -#if TEST_2540 // FIXME: extends cubic arm for sorting, marks extension with wrong winding? static void issue2540(skiatest::Reporter* reporter, const char* filename) { SkPath path1; path1.moveTo(26.5054988861083984375, 85.73960113525390625); @@ -3375,7 +3384,6 @@ static void issue2540(skiatest::Reporter* reporter, const char* filename) { path2.close(); testPathOp(reporter, path1, path2, kUnion_PathOp, filename); } -#endif static void rects1(skiatest::Reporter* reporter, const char* filename) { SkPath path, pathB; @@ -3457,30 +3465,25 @@ static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0; static void (*stopTest)(skiatest::Reporter* , const char* filename) = 0; static struct TestDesc tests[] = { +#if CUBIC_OP_114 // FIXME: curve with inflection is ordered the wrong way + TEST(cubicOp114), +#endif + TEST(cubicOp114asQuad), TEST(rects4), TEST(rects3), TEST(rects2), TEST(rects1), -#if TEST_2540 // FIXME: extends cubic arm for sorting, marks extension with wrong winding? TEST(issue2540), -#endif TEST(issue2504), TEST(kari1), TEST(quadOp10i), -#if 0 // FIXME: serpentine curve is ordered the wrong way - TEST(cubicOp114), -#endif -#if 0 // FIXME: currently failing TEST(cubicOp113), -#endif -#if SKPS_WORKING +#if QUAD_CUBIC_FAILS_TO_FIND_INTERSECTION // fails because a cubic/quadratic intersection is missed // the internal quad/quad is far enough away from the real cubic/quad that it is rejected TEST(skpcarrot_is24), #endif -#if ISSUE_1417_WORKING_ON_LINUX_32 TEST(issue1417), -#endif TEST(cubicOp112), TEST(skpadspert_net23), TEST(skpadspert_de11), @@ -3502,9 +3505,7 @@ static struct TestDesc tests[] = { TEST(cubicOp101), TEST(cubicOp100), TEST(cubicOp99), -#if ISSUE_1435_FIXED TEST(issue1435), -#endif TEST(cubicOp98x), TEST(cubicOp97x), TEST(skpcarpetplanet_ru22), // cubic/cubic intersect detects unwanted coincidence @@ -3682,7 +3683,6 @@ static struct TestDesc tests[] = { static const size_t testCount = SK_ARRAY_COUNT(tests); static struct TestDesc subTests[] = { - TEST(cubicOp114), TEST(cubicOp58d), TEST(cubicOp53d), }; diff --git a/tests/PathOpsSkpTest.cpp b/tests/PathOpsSkpTest.cpp index 3cfe4e2..d62e326 100755 --- a/tests/PathOpsSkpTest.cpp +++ b/tests/PathOpsSkpTest.cpp @@ -8,8 +8,6 @@ #define TEST(name) { name, #name } -#define TRY_NEW_TESTS 0 - static void skpcheeseandburger_com225(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -1808,7 +1806,6 @@ static void skpwww_heartiste_wordpress_com_86(skiatest::Reporter* reporter, cons testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#if TRY_NEW_TESTS static void skpwww_argus_presse_fr_41(skiatest::Reporter* reporter, const char* filename) { SkPath path; path.setFillType(SkPath::kEvenOdd_FillType); @@ -1827,7 +1824,6 @@ static void skpwww_argus_presse_fr_41(skiatest::Reporter* reporter, const char* pathB.close(); testPathOp(reporter, path, pathB, kIntersect_PathOp, filename); } -#endif // SkOpSegment::checkSmallCoincidence; line 1958 SkASSERT(span.fWindValue); static void skpwww_320kbps_net_2231(skiatest::Reporter* reporter, const char* filename) { @@ -3557,9 +3553,7 @@ static struct TestDesc tests[] = { TEST(skpwww_wartepop_blogspot_com_br_6), TEST(skpwww_wartepop_blogspot_com_br_6a), TEST(skpwww_cooksnaps_com_32a), -#if TRY_NEW_TESTS TEST(skpwww_argus_presse_fr_41), -#endif TEST(skpwww_cooksnaps_com_17), TEST(skpwww_cooksnaps_com_32), TEST(skpwww_kitcheninspirations_wordpress_com_66), diff --git a/tests/PathOpsTestCommon.cpp b/tests/PathOpsTestCommon.cpp index f89598a..60a12ee 100644 --- a/tests/PathOpsTestCommon.cpp +++ b/tests/PathOpsTestCommon.cpp @@ -29,6 +29,94 @@ void CubicToQuads(const SkDCubic& cubic, double precision, SkTArrayreset(); + SkDCubic cubic; + SkTArray quads; + SkPath::RawIter iter(cubicPath); + uint8_t verb; + SkPoint pts[4]; + while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { + switch (verb) { + case SkPath::kMove_Verb: + quadPath->moveTo(pts[0].fX, pts[0].fY); + continue; + case SkPath::kLine_Verb: + quadPath->lineTo(pts[1].fX, pts[1].fY); + break; + case SkPath::kQuad_Verb: + quadPath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); + break; + case SkPath::kCubic_Verb: + quads.reset(); + cubic.set(pts); + CubicToQuads(cubic, cubic.calcPrecision(), quads); + for (int index = 0; index < quads.count(); ++index) { + SkPoint qPts[2] = { + quads[index][1].asSkPoint(), + quads[index][2].asSkPoint() + }; + quadPath->quadTo(qPts[0].fX, qPts[0].fY, qPts[1].fX, qPts[1].fY); + } + break; + case SkPath::kClose_Verb: + quadPath->close(); + break; + default: + SkDEBUGFAIL("bad verb"); + return; + } + } +} + +void CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath) { + simplePath->reset(); + SkDCubic cubic; + SkPath::RawIter iter(cubicPath); + uint8_t verb; + SkPoint pts[4]; + while ((verb = iter.next(pts)) != SkPath::kDone_Verb) { + switch (verb) { + case SkPath::kMove_Verb: + simplePath->moveTo(pts[0].fX, pts[0].fY); + continue; + case SkPath::kLine_Verb: + simplePath->lineTo(pts[1].fX, pts[1].fY); + break; + case SkPath::kQuad_Verb: + simplePath->quadTo(pts[1].fX, pts[1].fY, pts[2].fX, pts[2].fY); + break; + case SkPath::kCubic_Verb: { + cubic.set(pts); + double tInflects[2]; + int inflections = cubic.findInflections(tInflects); + if (inflections > 1 && tInflects[0] > tInflects[1]) { + SkTSwap(tInflects[0], tInflects[1]); + } + double lo = 0; + for (int index = 0; index <= inflections; ++index) { + double hi = index < inflections ? tInflects[index] : 1; + SkDCubic part = cubic.subDivide(lo, hi); + SkPoint cPts[3]; + cPts[0] = part[1].asSkPoint(); + cPts[1] = part[2].asSkPoint(); + cPts[2] = part[3].asSkPoint(); + simplePath->cubicTo(cPts[0].fX, cPts[0].fY, cPts[1].fX, cPts[1].fY, + cPts[2].fX, cPts[2].fY); + lo = hi; + } + break; + } + case SkPath::kClose_Verb: + simplePath->close(); + break; + default: + SkDEBUGFAIL("bad verb"); + return; + } + } +} + static bool SkDoubleIsNaN(double x) { return x != x; } diff --git a/tests/PathOpsTestCommon.h b/tests/PathOpsTestCommon.h index 78f2e90..0c42bfb 100644 --- a/tests/PathOpsTestCommon.h +++ b/tests/PathOpsTestCommon.h @@ -12,6 +12,8 @@ struct SkPathOpsBounds; +void CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath); +void CubicPathToSimple(const SkPath& cubicPath, SkPath* simplePath); void CubicToQuads(const SkDCubic& cubic, double precision, SkTArray& quads); bool ValidBounds(const SkPathOpsBounds&); bool ValidCubic(const SkDCubic& cubic); diff --git a/tools/pathops_sorter.htm b/tools/pathops_sorter.htm index 865cbbf..aac151a 100644 --- a/tools/pathops_sorter.htm +++ b/tools/pathops_sorter.htm @@ -948,11 +948,17 @@ op intersect {{fX=124.66667175292969 fY=152.33334350585937 }, {fX=127.02368927001953 fY=153.30966186523437 }} } +
+{{{1020.08099, 672.16198699999995}, {1020.08002, 630.73999000000003}, {986.50201400000003, 597.16198699999995}, {945.08099400000003, 597.16198699999995}}} +{{{1020, 672}, {1020, 640.93395999999996}, {998.03301999999996, 618.96698000000004}}} +
+