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

6 files changed, 120 insertions, 35 deletions

diff --git a/tests/PathOpsCubicQuadIntersectionTest.cpp b/tests/PathOpsCubicQuadIntersectionTest.cpp
index db895d400d..967dfc7f4e 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 a2b48acddc..af60318532 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 5317792922..1d63bd7ab6 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 3cfe4e2f7a..d62e326278 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 f89598ad47..60a12ee56e 100644
--- a/tests/PathOpsTestCommon.cpp
+++ b/tests/PathOpsTestCommon.cpp
@@ -29,6 +29,94 @@ void CubicToQuads(const SkDCubic& cubic, double precision, SkTArray<SkDQuad, tru
     }
 }
 
+void CubicPathToQuads(const SkPath& cubicPath, SkPath* quadPath) {
+    quadPath->reset();
+    SkDCubic cubic;
+    SkTArray<SkDQuad, true> 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 78f2e9092c..0c42bfbb05 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<SkDQuad, true>& quads);
 bool ValidBounds(const SkPathOpsBounds&);
 bool ValidCubic(const SkDCubic& cubic);