fix multiple intersection logic

When three or more curves intersect at the same point, ensure that
each curve records the intersections of the others. This fixes a
number of cubic tests.

TBR=reed@google.com
BUG=skia:3588

Review URL: https://codereview.chromium.org/1105943002

5 files changed, 255 insertions, 15 deletions

diff --git a/tests/PathOpsDebug.cpp b/tests/PathOpsDebug.cpp
index f5708ebb06..d2e8bd0867 100755
--- a/tests/PathOpsDebug.cpp
+++ b/tests/PathOpsDebug.cpp
@@ -945,6 +945,7 @@ void SkOpSpanBase::dumpBase() const {
         const SkOpPtT* oPt = this->ptT()->next();
         SkDebugf(" seg/span=%d/%d", oPt->segment()->debugID(), oPt->span()->debugID());
     }
+    SkDebugf(" adds=%d", fSpanAdds);
 }
 
 void SkOpSpanBase::dumpCoin() const {
@@ -1319,23 +1320,23 @@ const SkOpSpanBase* SkOpGlobalState::debugSpan(int id) const {
 }
 #endif
 
-const SkOpAngle* DebugAngle(const SkTArray<SkOpContour*, true>* contours, int id) {
+const SkOpAngle* DebugAngle(const SkTDArray<SkOpContour* >* contours, int id) {
     return (*contours)[0]->debugAngle(id);
 }
 
-SkOpContour* DumpContour(const SkTArray<SkOpContour*, true>* contours, int id) {
+SkOpContour* DumpContour(const SkTDArray<SkOpContour* >* contours, int id) {
     return (*contours)[0]->debugContour(id);
 }
 
-const SkOpPtT* DebugPtT(const SkTArray<SkOpContour*, true>* contours, int id) {
+const SkOpPtT* DebugPtT(const SkTDArray<SkOpContour* >* contours, int id) {
     return (*contours)[0]->debugPtT(id);
 }
 
-const SkOpSegment* DebugSegment(const SkTArray<SkOpContour*, true>* contours, int id) {
+const SkOpSegment* DebugSegment(const SkTDArray<SkOpContour* >* contours, int id) {
     return (*contours)[0]->debugSegment(id);
 }
 
-const SkOpSpanBase* DebugSpan(const SkTArray<SkOpContour*, true>* contours, int id) {
+const SkOpSpanBase* DebugSpan(const SkTDArray<SkOpContour* >* contours, int id) {
     return (*contours)[0]->debugSpan(id);
 }
 
diff --git a/tests/PathOpsExtendedTest.cpp b/tests/PathOpsExtendedTest.cpp
index c316242f75..92b0e87465 100644
--- a/tests/PathOpsExtendedTest.cpp
+++ b/tests/PathOpsExtendedTest.cpp
@@ -289,7 +289,7 @@ int comparePaths(skiatest::Reporter* reporter, const char* filename, const SkPat
     return errors2x2 > MAX_ERRORS ? errors2x2 : 0;
 }
 
-const int gTestFirst = 6;
+const int gTestFirst = 20;
 static int gTestNo = gTestFirst;
 static SkTDArray<SkPathOp> gTestOp;
 
diff --git a/tests/PathOpsIssue3651.cpp b/tests/PathOpsIssue3651.cpp
index 349e04d9ce..cb4c7e81f3 100644
--- a/tests/PathOpsIssue3651.cpp
+++ b/tests/PathOpsIssue3651.cpp
@@ -1347,11 +1347,26 @@ path.close();
     testPathOpCheck(reporter, pathA, path, SkPathOp::kUnion_SkPathOp, filename, FLAGS_runFail);
 }
 
+static void issue3651_6(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path;
+path.cubicTo(SkBits2Float(0x41c1999a), SkBits2Float(0x4380423d), SkBits2Float(0x41ca6666), SkBits2Float(0x4380789f), SkBits2Float(0x41d33333), SkBits2Float(0x43808db9));  // 24.2f, 256.517f, 25.3f, 256.942f, 26.4f, 257.107f
+path.cubicTo(SkBits2Float(0x41dc0000), SkBits2Float(0x4380a2d3), SkBits2Float(0x41e4cccd), SkBits2Float(0x4380b36f), SkBits2Float(0x41ed999a), SkBits2Float(0x4380b333));  // 27.5f, 257.272f, 28.6f, 257.402f, 29.7f, 257.4f
+path.lineTo(SkBits2Float(0x411e6666), SkBits2Float(0x4380b333));  // 9.9f, 257.4f
+path.close();
+SkPath pathA = path;
+path.reset();
+path.cubicTo(SkBits2Float(0x41c1999a), SkBits2Float(0x43812429), SkBits2Float(0x41ca6666), SkBits2Float(0x4380edc7), SkBits2Float(0x41d33333), SkBits2Float(0x4380d8ad));  // 24.2f, 258.283f, 25.3f, 257.858f, 26.4f, 257.693f
+path.cubicTo(SkBits2Float(0x41dc0000), SkBits2Float(0x4380c393), SkBits2Float(0x41e4cccd), SkBits2Float(0x4380b2f7), SkBits2Float(0x41ed999a), SkBits2Float(0x4380b333));  // 27.5f, 257.528f, 28.6f, 257.398f, 29.7f, 257.4f
+    testPathOp(reporter, pathA, path, SkPathOp::kUnion_SkPathOp, filename);
+}
+
+
 static void (*skipTest)(skiatest::Reporter* , const char* filename) = 0;
 static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0;
 static void (*stopTest)(skiatest::Reporter* , const char* filename) = 0;
 
 static struct TestDesc tests[] = {
+    TEST(issue3651_6),
     TEST(issue3651_5),
     TEST(issue3651_4),
     TEST(issue3651_1),
diff --git a/tests/PathOpsOpCubicThreadedTest.cpp b/tests/PathOpsOpCubicThreadedTest.cpp
index 0d905c6e23..26617b885f 100644
--- a/tests/PathOpsOpCubicThreadedTest.cpp
+++ b/tests/PathOpsOpCubicThreadedTest.cpp
@@ -7,7 +7,7 @@
 #include "PathOpsExtendedTest.h"
 #include "PathOpsThreadedCommon.h"
 
-static int loopNo = 132;
+static int loopNo = 158;
 
 static void testOpCubicsMain(PathOpsThreadState* data) {
 #if DEBUG_SHOW_TEST_NAME
@@ -15,7 +15,7 @@ static void testOpCubicsMain(PathOpsThreadState* data) {
 #endif
     SkASSERT(data);
     PathOpsThreadState& state = *data;
-    char pathStr[1024];  // gdb: set print elements 400
+    char pathStr[1024];
     bool progress = state.fReporter->verbose(); // FIXME: break out into its own parameter?
     if (progress) {
         sk_bzero(pathStr, sizeof(pathStr));
diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp
index 54f7576f13..993fdd9a23 100644
--- a/tests/PathOpsOpTest.cpp
+++ b/tests/PathOpsOpTest.cpp
@@ -4155,7 +4155,7 @@ static void cubicOp139(skiatest::Reporter* reporter, const char* filename) {
     pathB.moveTo(1,3);
     pathB.cubicTo(1,5, 2,0, 4,0);
     pathB.close();
-    testPathOpCheck(reporter, path, pathB, kDifference_SkPathOp, filename, FLAGS_runFail);
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
 }
 
 static void cubicOp140(skiatest::Reporter* reporter, const char* filename) {
@@ -4270,11 +4270,235 @@ static void loops5i(skiatest::Reporter* reporter, const char* filename) {
     testPathOp(reporter, path, pathB, kIntersect_SkPathOp, filename);
 }
 
+static void cubicOp142(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(5,6);
+    path.cubicTo(2,5, 2,1, 1,0);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(1,2);
+    pathB.cubicTo(0,1, 6,5, 5,2);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics6d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(3, 5);
+    path.cubicTo(1, 5, 4, 2, 4, 0);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(2, 4);
+    pathB.cubicTo(0, 4, 5, 3, 5, 1);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics7d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(2, 6);
+    path.cubicTo(2, 4, 5, 1, 3, 1);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(1, 5);
+    pathB.cubicTo(1, 3, 6, 2, 4, 2);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics8d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(2, 5);
+    path.cubicTo(2, 4, 5, 1, 3, 2);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(1, 5);
+    pathB.cubicTo(2, 3, 5, 2, 4, 2);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics9d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(2, 4);
+    path.cubicTo(2, 6, 3, 1, 5, 1);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(1, 3);
+    pathB.cubicTo(1, 5, 4, 2, 6, 2);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics10u(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(2, 4);
+    path.cubicTo(1, 6, 4, 1, 5, 1);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(1, 4);
+    pathB.cubicTo(1, 5, 4, 2, 6, 1);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kUnion_SkPathOp, filename);
+}
+
+static void cubics11i(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(2, 4);
+    path.cubicTo(2, 5, 3, 2, 5, 1);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(2, 3);
+    pathB.cubicTo(1, 5, 4, 2, 5, 2);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kIntersect_SkPathOp, filename);
+}
+
+static void cubics12d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(2, 4);
+    path.cubicTo(0, 4, 5, 3, 5, 1);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(3, 5);
+    pathB.cubicTo(1, 5, 4, 2, 4, 0);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics13d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(2, 3);
+    path.cubicTo(1, 5, 4, 2, 5, 2);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(2, 4);
+    pathB.cubicTo(2, 5, 3, 2, 5, 1);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics14d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(2, 3);
+    path.cubicTo(0, 4, 3, 1, 3, 0);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(1, 3);
+    pathB.cubicTo(0, 3, 3, 2, 4, 0);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics15d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(1, 5);
+    path.cubicTo(3, 5, 4, 0, 4, 2);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(0, 4);
+    pathB.cubicTo(2, 4, 5, 1, 5, 3);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics16i(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(1, 5);
+    path.cubicTo(2, 5, 5, 0, 4, 2);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(0, 5);
+    pathB.cubicTo(2, 4, 5, 1, 5, 2);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kIntersect_SkPathOp, filename);
+}
+
+static void cubics17d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(1, 5);
+    path.cubicTo(3, 4, 4, 1, 4, 2);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(1, 4);
+    pathB.cubicTo(2, 4, 5, 1, 4, 3);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics18d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(1, 5);
+    path.cubicTo(1, 3, 4, 0, 2, 0);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(0, 4);
+    pathB.cubicTo(0, 2, 5, 1, 3, 1);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubics19d(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(1, 5);
+    path.cubicTo(2, 3, 5, 2, 4, 2);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(2, 5);
+    pathB.cubicTo(2, 4, 5, 1, 3, 2);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
+static void cubicOp157(skiatest::Reporter* reporter, const char* filename) {
+    SkPath path, pathB;
+    path.setFillType(SkPath::kWinding_FillType);
+    path.moveTo(1,5);
+    path.cubicTo(1,3, 6,2, 4,2);
+    path.close();
+    pathB.setFillType(SkPath::kWinding_FillType);
+    pathB.moveTo(2,6);
+    pathB.cubicTo(2,4, 5,1, 3,1);
+    pathB.close();
+    testPathOp(reporter, path, pathB, kDifference_SkPathOp, filename);
+}
+
 static void (*skipTest)(skiatest::Reporter* , const char* filename) = 0;
-static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0;
+static void (*firstTest)(skiatest::Reporter* , const char* filename) = cubicOp90u;
 static void (*stopTest)(skiatest::Reporter* , const char* filename) = 0;
 
 static struct TestDesc tests[] = {
+    TEST(cubics6d),
+    TEST(cubics7d),
+    TEST(cubics8d),
+    TEST(cubics9d),
+    TEST(cubics10u),
+    TEST(cubics11i),
+    TEST(cubics12d),
+    TEST(cubics13d),
+    TEST(cubics14d),
+    TEST(cubics15d),
+    TEST(cubics16i),
+    TEST(cubics17d),
+    TEST(cubics18d),
+    TEST(cubics19d),
+    TEST(cubicOp157),
+    TEST(cubicOp142),
     TEST(loops4i),
     TEST(quadRect1),
     TEST(quadRect2),
@@ -4799,8 +5023,8 @@ static void fuzz714(skiatest::Reporter* reporter, const char* filename) {
 path.moveTo(SkBits2Float(0x430c0000), SkBits2Float(0x42200000));
 path.lineTo(SkBits2Float(0x43480000), SkBits2Float(0x43520000));
 path.lineTo(SkBits2Float(0x42200000), SkBits2Float(0x42c80000));
-path.lineTo(SkBits2Float(0x64969569), SkBits2Float(0x42c80000));
-path.lineTo(SkBits2Float(0x64969569), SkBits2Float(0x43520000));
+path.lineTo(SkBits2Float(0x64969569), SkBits2Float(0x42c80000));  // 2.22222e+022f
+path.lineTo(SkBits2Float(0x64969569), SkBits2Float(0x43520000));  // 2.22222e+022f
 path.lineTo(SkBits2Float(0x430c0000), SkBits2Float(0x42200000));
 path.close();
 
@@ -4810,8 +5034,8 @@ path.close();
 path.moveTo(SkBits2Float(0x43200000), SkBits2Float(0x42700000));
 path.lineTo(SkBits2Float(0x435c0000), SkBits2Float(0x43660000));
 path.lineTo(SkBits2Float(0x42700000), SkBits2Float(0x42f00000));
-path.lineTo(SkBits2Float(0x64969569), SkBits2Float(0x42f00000));
-path.lineTo(SkBits2Float(0x64969569), SkBits2Float(0x43660000));
+path.lineTo(SkBits2Float(0x64969569), SkBits2Float(0x42f00000));  // 2.22222e+022f
+path.lineTo(SkBits2Float(0x64969569), SkBits2Float(0x43660000));  // 2.22222e+022f
 path.lineTo(SkBits2Float(0x43200000), SkBits2Float(0x42700000));
 path.close();
 
@@ -4842,12 +5066,12 @@ path.close();
 }
 
 static struct TestDesc failTests[] = {
+    TEST(fuzz433),
     TEST(fuzz1),
     TEST(fuzz714),
     TEST(fuzz487a),
     TEST(fuzz487b),
     TEST(fuzz433b),
-    TEST(fuzz433),
     TEST(bufferOverflow),
 };