cumulative pathops patch

Replace the implicit curve intersection with a geometric curve intersection. The implicit intersection proved mathematically unstable and took a long time to zero in on an answer.

Use pointers instead of indices to refer to parts of curves. Indices required awkward renumbering.

Unify t and point values so that small intervals can be eliminated in one pass.

Break cubics up front to eliminate loops and cusps.

Make the Simplify and Op code more regular and eliminate arbitrary differences.

Add a builder that takes an array of paths and operators.

Delete unused code.

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

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

1 files changed, 96 insertions, 84 deletions

diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp
index faf61584e6..62ebc10139 100644
--- a/tests/PathOpsAngleTest.cpp
+++ b/tests/PathOpsAngleTest.cpp
@@ -6,10 +6,9 @@
  */
 #include "PathOpsTestCommon.h"
 #include "SkIntersections.h"
+#include "SkOpContour.h"
 #include "SkOpSegment.h"
-#include "SkPathOpsTriangle.h"
 #include "SkRandom.h"
-#include "SkTArray.h"
 #include "SkTSort.h"
 #include "Test.h"
 
@@ -191,20 +190,20 @@ DEF_TEST(PathOpsAngleFindSlop, reporter) {
 
 class PathOpsAngleTester {
 public:
-    static int After(const SkOpAngle& lh, const SkOpAngle& rh) {
+    static int After(SkOpAngle& lh, SkOpAngle& rh) {
         return lh.after(&rh);
     }
 
-    static int ConvexHullOverlaps(const SkOpAngle& lh, const SkOpAngle& rh) {
-        return lh.convexHullOverlaps(rh);
+    static int ConvexHullOverlaps(SkOpAngle& lh, SkOpAngle& rh) {
+        return lh.convexHullOverlaps(&rh);
     }
 
-    static int Orderable(const SkOpAngle& lh, const SkOpAngle& rh) {
-        return lh.orderable(rh);
+    static int Orderable(SkOpAngle& lh, SkOpAngle& rh) {
+        return lh.orderable(&rh);
     }
 
-    static int EndsIntersect(const SkOpAngle& lh, const SkOpAngle& rh) {
-        return lh.endsIntersect(rh);
+    static int EndsIntersect(SkOpAngle& lh, SkOpAngle& rh) {
+        return lh.endsIntersect(&rh);
     }
 
     static void SetNext(SkOpAngle& lh, SkOpAngle& rh) {
@@ -214,18 +213,6 @@ public:
 
 class PathOpsSegmentTester {
 public:
-    static void ConstructCubic(SkOpSegment* segment, SkPoint shortCubic[4]) {
-        segment->debugConstructCubic(shortCubic);
-    }
-
-    static void ConstructLine(SkOpSegment* segment, SkPoint shortLine[2]) {
-        segment->debugConstructLine(shortLine);
-    }
-
-    static void ConstructQuad(SkOpSegment* segment, SkPoint shortQuad[3]) {
-        segment->debugConstructQuad(shortQuad);
-    }
-
     static void DebugReset(SkOpSegment* segment) {
         segment->debugReset();
     }
@@ -246,7 +233,10 @@ static CircleData circleDataSet[] = {
 static const int circleDataSetSize = (int) SK_ARRAY_COUNT(circleDataSet);
 
 DEF_TEST(PathOpsAngleCircle, reporter) {
-    SkOpSegment segment[2];
+    SkChunkAlloc allocator(4096);
+    SkOpContour contour;
+    SkOpGlobalState state(NULL  PATH_OPS_DEBUG_PARAMS(&contour));
+    contour.init(&state, false, false);
     for (int index = 0; index < circleDataSetSize; ++index) {
         CircleData& data = circleDataSet[index];
         for (int idx2 = 0; idx2 < data.fPtCount; ++idx2) {
@@ -254,17 +244,21 @@ DEF_TEST(PathOpsAngleCircle, reporter) {
         }
         switch (data.fPtCount) {
             case 2:
-                PathOpsSegmentTester::ConstructLine(&segment[index], data.fShortPts);
+                contour.addLine(data.fShortPts, &allocator);
                 break;
             case 3:
-                PathOpsSegmentTester::ConstructQuad(&segment[index], data.fShortPts);
+                contour.addQuad(data.fShortPts, &allocator);
                 break;
             case 4:
-                PathOpsSegmentTester::ConstructCubic(&segment[index], data.fShortPts);
+                contour.addCubic(data.fShortPts, &allocator);
                 break;
         }
     }
-    PathOpsAngleTester::Orderable(*segment[0].debugLastAngle(), *segment[1].debugLastAngle());
+    SkOpSegment* first = contour.first();
+    first->debugAddAngle(0, 1, &allocator);
+    SkOpSegment* next = first->next();
+    next->debugAddAngle(0, 1, &allocator);
+    PathOpsAngleTester::Orderable(*first->debugLastAngle(), *next->debugLastAngle());
 }
 
 struct IntersectData {
@@ -379,11 +373,39 @@ static IntersectData intersectDataSet16[] = { // pathops_visualizer.htm:7419
     { {{{5.000,4.000}, {2.000,3.000}}}, 2, 0.5, 0, {} }, // pathops_visualizer.htm:7377
 }; //
 
+// from skpi_gino_com_16
+static IntersectData intersectDataSet17[] = {
+    { /*seg=7*/ {{{270.974121f, 770.025879f}, {234.948273f, 734}, {184, 734}}}
+        , 3, 0.74590454, 0.547660352, {} },
+    { /*seg=8*/ {{{185, 734}, {252.93103f, 734}, {308, 789.06897f}, {308, 857}}}
+        , 4, 0.12052623, 0, {} },
+    { /*seg=7*/ {{{270.974121f, 770.025879f}, {234.948273f, 734}, {184, 734}}}
+        , 3, 0.74590454, 1, {} },
+};
+
+static IntersectData intersectDataSet18[] = {
+    { /*seg=7*/ {{{270.974121f, 770.025879f}, {234.948273f, 734}, {184, 734}}}
+        , 3, 0.74590454, 1, {} },
+    { /*seg=8*/ {{{185, 734}, {252.93103f, 734}, {308, 789.06897f}, {308, 857}}}
+        , 4, 0.12052623, 0.217351928, {} },
+    { /*seg=7*/ {{{270.974121f, 770.025879f}, {234.948273f, 734}, {184, 734}}}
+        , 3, 0.74590454, 0.547660352, {} },
+};
+
+static IntersectData intersectDataSet19[] = {
+    { /*seg=1*/ {{{0, 1}, {3, 5}, {2, 1}, {3, 1}}}
+        , 4, 0.135148995, 0.134791946, {} },
+    { /*seg=3*/ {{{1, 2}, {1, 2.15061641f}, {1, 2.21049166f}, {1.01366711f, 2.21379328f}}}
+        , 4, 0.956740456, 0.894913214, {} },
+    { /*seg=1*/ {{{0, 1}, {3, 5}, {2, 1}, {3, 1}}}
+        , 4, 0.135148995, 0.551812363, {} },
+};
+
 #define I(x) intersectDataSet##x
 
 static IntersectData* intersectDataSets[] = {
     I(1), I(2), I(3), I(4), I(5), I(6), I(7), I(8), I(9), I(10),
-    I(11), I(12), I(13), I(14), I(15), I(16),
+    I(11), I(12), I(13), I(14), I(15), I(16), I(17), I(18), I(19),
 };
 
 #undef I
@@ -391,56 +413,55 @@ static IntersectData* intersectDataSets[] = {
 
 static const int intersectDataSetSizes[] = {
     I(1), I(2), I(3), I(4), I(5), I(6), I(7), I(8), I(9), I(10),
-    I(11), I(12), I(13), I(14), I(15), I(16),
+    I(11), I(12), I(13), I(14), I(15), I(16), I(17), I(18), I(19),
 };
 
 #undef I
 
 static const int intersectDataSetsSize = (int) SK_ARRAY_COUNT(intersectDataSetSizes);
 
+struct FourPoints {
+    SkPoint pts[4];
+};
+
 DEF_TEST(PathOpsAngleAfter, reporter) {
+    SkChunkAlloc allocator(4096);
+    SkOpContour contour;
+    SkOpGlobalState state(NULL  PATH_OPS_DEBUG_PARAMS(&contour));
+    contour.init(&state, false, false);
     for (int index = intersectDataSetsSize - 1; index >= 0; --index) {
         IntersectData* dataArray = intersectDataSets[index];
         const int dataSize = intersectDataSetSizes[index];
-        SkOpSegment segment[3];
         for (int index2 = 0; index2 < dataSize - 2; ++index2) {
-            for (int temp = 0; temp < (int) SK_ARRAY_COUNT(segment); ++temp) {
-                PathOpsSegmentTester::DebugReset(&segment[temp]);
-            }
-            for (int index3 = 0; index3 < (int) SK_ARRAY_COUNT(segment); ++index3) {
+            allocator.reset();
+            contour.reset();
+            for (int index3 = 0; index3 < 3; ++index3) {
                 IntersectData& data = dataArray[index2 + index3];
-                SkPoint temp[4];
+                SkPoint* temp = (SkPoint*) SkOpTAllocator<FourPoints>::Allocate(&allocator);
                 for (int idx2 = 0; idx2 < data.fPtCount; ++idx2) {
                     temp[idx2] = data.fPts.fPts[idx2].asSkPoint();
                 }
                 switch (data.fPtCount) {
                     case 2: {
-                        SkDLine seg = SkDLine::SubDivide(temp, data.fTStart,
-                                data.fTStart < data.fTEnd ? 1 : 0);
-                        data.fShortPts[0] = seg[0].asSkPoint();
-                        data.fShortPts[1] = seg[1].asSkPoint();
-                        PathOpsSegmentTester::ConstructLine(&segment[index3], data.fShortPts);
+                        contour.addLine(temp, &allocator);
                         } break;
                     case 3: {
-                        SkDQuad seg = SkDQuad::SubDivide(temp, data.fTStart, data.fTEnd);
-                        data.fShortPts[0] = seg[0].asSkPoint();
-                        data.fShortPts[1] = seg[1].asSkPoint();
-                        data.fShortPts[2] = seg[2].asSkPoint();
-                        PathOpsSegmentTester::ConstructQuad(&segment[index3], data.fShortPts);
+                        contour.addQuad(temp, &allocator);
                         } break;
                     case 4: {
-                        SkDCubic seg = SkDCubic::SubDivide(temp, data.fTStart, data.fTEnd);
-                        data.fShortPts[0] = seg[0].asSkPoint();
-                        data.fShortPts[1] = seg[1].asSkPoint();
-                        data.fShortPts[2] = seg[2].asSkPoint();
-                        data.fShortPts[3] = seg[3].asSkPoint();
-                        PathOpsSegmentTester::ConstructCubic(&segment[index3], data.fShortPts);
+                        contour.addCubic(temp, &allocator);
                         } break;
                 }
             }
-            SkOpAngle& angle1 = *const_cast<SkOpAngle*>(segment[0].debugLastAngle());
-            SkOpAngle& angle2 = *const_cast<SkOpAngle*>(segment[1].debugLastAngle());
-            SkOpAngle& angle3 = *const_cast<SkOpAngle*>(segment[2].debugLastAngle());
+            SkOpSegment* seg1 = contour.first();
+            seg1->debugAddAngle(dataArray[index2 + 0].fTStart, dataArray[index2 + 0].fTEnd, &allocator);
+            SkOpSegment* seg2 = seg1->next();
+            seg2->debugAddAngle(dataArray[index2 + 1].fTStart, dataArray[index2 + 1].fTEnd, &allocator);
+            SkOpSegment* seg3 = seg2->next();
+            seg3->debugAddAngle(dataArray[index2 + 2].fTStart, dataArray[index2 + 2].fTEnd, &allocator);
+            SkOpAngle& angle1 = *seg1->debugLastAngle();
+            SkOpAngle& angle2 = *seg2->debugLastAngle();
+            SkOpAngle& angle3 = *seg3->debugLastAngle();
             PathOpsAngleTester::SetNext(angle1, angle3);
        // These data sets are seeded when the set itself fails, so likely the dataset does not
        // match the expected result. The tests above return 1 when first added, but
@@ -451,35 +472,26 @@ DEF_TEST(PathOpsAngleAfter, reporter) {
     }
 }
 
-void SkOpSegment::debugConstruct() {
-    addStartSpan(1);
-    addEndSpan(1);
-    debugAddAngle(0, 1);
-}
-
-void SkOpSegment::debugAddAngle(int start, int end) {
-    SkASSERT(start != end);
-    SkOpAngle& angle = fAngles.push_back();
-    angle.set(this, start, end);
-}
-
-void SkOpSegment::debugConstructCubic(SkPoint shortQuad[4]) {
-    addCubic(shortQuad, false, false);
-    addT(NULL, shortQuad[0], 0);
-    addT(NULL, shortQuad[3], 1);
-    debugConstruct();
-}
-
-void SkOpSegment::debugConstructLine(SkPoint shortQuad[2]) {
-    addLine(shortQuad, false, false);
-    addT(NULL, shortQuad[0], 0);
-    addT(NULL, shortQuad[1], 1);
-    debugConstruct();
-}
-
-void SkOpSegment::debugConstructQuad(SkPoint shortQuad[3]) {
-    addQuad(shortQuad, false, false);
-    addT(NULL, shortQuad[0], 0);
-    addT(NULL, shortQuad[2], 1);
-    debugConstruct();
+void SkOpSegment::debugAddAngle(double startT, double endT, SkChunkAlloc* allocator) {
+    SkOpPtT* startPtT = startT == 0 ? fHead.ptT() : startT == 1 ? fTail.ptT()
+            : this->addT(startT, kNoAlias, allocator);
+    SkOpPtT* endPtT = endT == 0 ? fHead.ptT() : endT == 1 ? fTail.ptT()
+            : this->addT(endT, kNoAlias, allocator);
+    SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+    SkOpSpanBase* startSpan = &fHead;
+    while (startSpan->ptT() != startPtT) {
+        startSpan = startSpan->upCast()->next();
+    }
+    SkOpSpanBase* endSpan = &fHead;
+    while (endSpan->ptT() != endPtT) {
+        endSpan = endSpan->upCast()->next();
+    }
+    angle->set(startSpan, endSpan);
+    if (startT < endT) {
+        startSpan->upCast()->setToAngle(angle);
+        endSpan->setFromAngle(angle);
+    } else {
+        endSpan->upCast()->setToAngle(angle);
+        startSpan->setFromAngle(angle);
+    }
 }