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, 85 insertions, 117 deletions

diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index f2b25c04ec..25ddb7dec6 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -5,27 +5,29 @@
  * found in the LICENSE file.
  */
 #include "SkAddIntersections.h"
+#include "SkOpCoincidence.h"
 #include "SkOpEdgeBuilder.h"
 #include "SkPathOpsCommon.h"
 #include "SkPathWriter.h"
 
-static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* endIndex) {
+static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase** startPtr,
+        SkOpSpanBase** endPtr) {
     while (chase.count()) {
-        SkOpSpan* span;
+        SkOpSpanBase* span;
         chase.pop(&span);
-        const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
-        SkOpSegment* segment = backPtr.fOther;
-        *tIndex = backPtr.fOtherIndex;
+        // OPTIMIZE: prev makes this compatible with old code -- but is it necessary?
+        *startPtr = span->ptT()->prev()->span();
+        SkOpSegment* segment = (*startPtr)->segment();
         bool sortable = true;
         bool done = true;
-        *endIndex = -1;
-        if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
+        *endPtr = NULL;
+        if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done,
                 &sortable)) {
             if (last->unorderable()) {
                 continue;
             }
-            *tIndex = last->start();
-            *endIndex = last->end();
+            *startPtr = last->start();
+            *endPtr = last->end();
    #if TRY_ROTATE
             *chase.insert(0) = span;
    #else
@@ -40,7 +42,7 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* e
             continue;
         }
         // find first angle, initialize winding to computed fWindSum
-        const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
+        const SkOpAngle* angle = segment->spanToAngle(*startPtr, *endPtr);
         if (!angle) {
             continue;
         }
@@ -65,33 +67,25 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* e
             SkTSwap<int>(sumMiWinding, sumSuWinding);
         }
         SkOpSegment* first = NULL;
-        bool badData = false;
-        while ((angle = angle->next()) != firstAngle && !badData) {
+        firstAngle = angle;
+        while ((angle = angle->next()) != firstAngle) {
             segment = angle->segment();
-            int start = angle->start();
-            int end = angle->end();
+            SkOpSpanBase* start = angle->start();
+            SkOpSpanBase* end = angle->end();
             int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
             segment->setUpWindings(start, end, &sumMiWinding, &sumSuWinding,
                     &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding);
             if (!segment->done(angle)) {
                 if (!first) {
                     first = segment;
-                    *tIndex = start;
-                    *endIndex = end;
-                }
-                if (segment->inconsistentAngle(maxWinding, sumWinding, oppMaxWinding,
-                        oppSumWinding, angle)) {
-                    badData = true;
-                    break;
+                    *startPtr = start;
+                    *endPtr = end;
                 }
                 // OPTIMIZATION: should this also add to the chase?
                 (void) segment->markAngle(maxWinding, sumWinding, oppMaxWinding,
                     oppSumWinding, angle);
             }
         }
-        if (badData) {
-            continue;
-        }
         if (first) {
        #if TRY_ROTATE
             *chase.insert(0) = span;
@@ -104,36 +98,8 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpan*>& chase, int* tIndex, int* e
     return NULL;
 }
 
-/*
-static bool windingIsActive(int winding, int oppWinding, int spanWinding, int oppSpanWinding,
-        bool windingIsOp, PathOp op) {
-    bool active = windingIsActive(winding, spanWinding);
-    if (!active) {
-        return false;
-    }
-    if (oppSpanWinding && windingIsActive(oppWinding, oppSpanWinding)) {
-        switch (op) {
-            case kIntersect_Op:
-            case kUnion_Op:
-                return true;
-            case kDifference_Op: {
-                int absSpan = abs(spanWinding);
-                int absOpp = abs(oppSpanWinding);
-                return windingIsOp ? absSpan < absOpp : absSpan > absOpp;
-            }
-            case kXor_Op:
-                return spanWinding != oppSpanWinding;
-            default:
-                SkASSERT(0);
-        }
-    }
-    bool opActive = oppWinding != 0;
-    return gOpLookup[op][opActive][windingIsOp];
-}
-*/
-
-static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp op,
-        const int xorMask, const int xorOpMask, SkPathWriter* simple) {
+static bool bridgeOp(SkTDArray<SkOpContour* >& contourList, const SkPathOp op,
+        const int xorMask, const int xorOpMask, SkPathWriter* simple, SkChunkAlloc* allocator) {
     bool firstContour = true;
     bool unsortable = false;
     bool topUnsortable = false;
@@ -141,12 +107,14 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o
     SkPoint lastTopLeft;
     SkPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
     do {
-        int index, endIndex;
+        SkOpSpanBase* start;
+        SkOpSpanBase* end;
         bool topDone;
         bool onlyVertical = false;
         lastTopLeft = topLeft;
-        SkOpSegment* current = FindSortableTop(contourList, SkOpAngle::kBinarySingle, &firstContour,
-                &index, &endIndex, &topLeft, &topUnsortable, &topDone, &onlyVertical, firstPass);
+        SkOpSegment* current = FindSortableTop(contourList, firstPass, SkOpAngle::kBinarySingle,
+                &firstContour, &start, &end, &topLeft, &topUnsortable, &topDone, &onlyVertical,
+                allocator);
         if (!current) {
             if ((!topUnsortable || firstPass) && !topDone) {
                 SkASSERT(topLeft.fX != SK_ScalarMin && topLeft.fY != SK_ScalarMin);
@@ -165,69 +133,65 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o
             break;
         }
         firstPass = !topUnsortable || lastTopLeft != topLeft;
-        SkTDArray<SkOpSpan*> chase;
+        SkTDArray<SkOpSpanBase*> chase;
         do {
-            if (current->activeOp(index, endIndex, xorMask, xorOpMask, op)) {
+            if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
                 do {
                     if (!unsortable && current->done()) {
                         break;
                     }
                     SkASSERT(unsortable || !current->done());
-                    int nextStart = index;
-                    int nextEnd = endIndex;
+                    SkOpSpanBase* nextStart = start;
+                    SkOpSpanBase* nextEnd = end;
                     SkOpSegment* next = current->findNextOp(&chase, &nextStart, &nextEnd,
                             &unsortable, op, xorMask, xorOpMask);
                     if (!next) {
                         if (!unsortable && simple->hasMove()
                                 && current->verb() != SkPath::kLine_Verb
                                 && !simple->isClosed()) {
-                            current->addCurveTo(index, endIndex, simple, true);
+                            current->addCurveTo(start, end, simple, true);
                     #if DEBUG_ACTIVE_SPANS
                             if (!simple->isClosed()) {
                                 DebugShowActiveSpans(contourList);
                             }
                     #endif
-//                            SkASSERT(simple->isClosed());
                         }
                         break;
                     }
         #if DEBUG_FLOW
-            SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
-                    current->debugID(), current->xyAtT(index).fX, current->xyAtT(index).fY,
-                    current->xyAtT(endIndex).fX, current->xyAtT(endIndex).fY);
+                    SkDebugf("%s current id=%d from=(%1.9g,%1.9g) to=(%1.9g,%1.9g)\n", __FUNCTION__,
+                            current->debugID(), start->pt().fX, start->pt().fY,
+                            end->pt().fX, end->pt().fY);
         #endif
-                    current->addCurveTo(index, endIndex, simple, true);
+                    current->addCurveTo(start, end, simple, true);
                     current = next;
-                    index = nextStart;
-                    endIndex = nextEnd;
-                } while (!simple->isClosed() && (!unsortable
-                        || !current->done(SkMin32(index, endIndex))));
-                if (current->activeWinding(index, endIndex) && !simple->isClosed()) {
-                    // FIXME : add to simplify, xor cpaths
-                    int min = SkMin32(index, endIndex);
-                    if (!unsortable && !simple->isEmpty()) {
-                        unsortable = current->checkSmall(min);
-                    }
-                    if (!current->done(min)) {
-                        current->addCurveTo(index, endIndex, simple, true);
-                        current->markDoneBinary(min);
+                    start = nextStart;
+                    end = nextEnd;
+                } while (!simple->isClosed() && (!unsortable || !start->starter(end)->done()));
+                if (current->activeWinding(start, end) && !simple->isClosed()) {
+                    SkOpSpan* spanStart = start->starter(end);
+                    if (!spanStart->done()) {
+                        current->addCurveTo(start, end, simple, true);
+                        current->markDone(spanStart);
                     }
                 }
                 simple->close();
             } else {
-                SkOpSpan* last = current->markAndChaseDoneBinary(index, endIndex);
-                if (last && !last->fChased && !last->fLoop) {
-                    last->fChased = true;
+                SkOpSpanBase* last = current->markAndChaseDone(start, end);
+                if (last && !last->chased()) {
+                    last->setChased(true);
                     SkASSERT(!SkPathOpsDebug::ChaseContains(chase, last));
                     *chase.append() = last;
 #if DEBUG_WINDING
-                    SkDebugf("%s chase.append id=%d windSum=%d small=%d\n", __FUNCTION__,
-                            last->fOther->span(last->fOtherIndex).fOther->debugID(), last->fWindSum,
-                            last->fSmall);
+                    SkDebugf("%s chase.append id=%d", __FUNCTION__, last->segment()->debugID());
+                    if (!last->final()) {
+                         SkDebugf(" windSum=%d", last->upCast()->windSum());
+                    }
+                    SkDebugf("\n");
 #endif
                 }
             }
-            current = findChaseOp(chase, &index, &endIndex);
+            current = findChaseOp(chase, &start, &end);
         #if DEBUG_ACTIVE_SPANS
             DebugShowActiveSpans(contourList);
         #endif
@@ -241,17 +205,17 @@ static bool bridgeOp(SkTArray<SkOpContour*, true>& contourList, const SkPathOp o
 
 // pretty picture:
 // https://docs.google.com/a/google.com/drawings/d/1sPV8rPfpEFXymBp3iSbDRWAycp1b-7vD9JP2V-kn9Ss/edit?usp=sharing
-static const SkPathOp gOpInverse[kReverseDifference_PathOp + 1][2][2] = {
+static const SkPathOp gOpInverse[kReverseDifference_SkPathOp + 1][2][2] = {
 //                  inside minuend                               outside minuend
 //     inside subtrahend     outside subtrahend      inside subtrahend     outside subtrahend
-    {{ kDifference_PathOp,    kIntersect_PathOp }, { kUnion_PathOp, kReverseDifference_PathOp }},
-    {{ kIntersect_PathOp,    kDifference_PathOp }, { kReverseDifference_PathOp, kUnion_PathOp }},
-    {{ kUnion_PathOp, kReverseDifference_PathOp }, { kDifference_PathOp,    kIntersect_PathOp }},
-    {{ kXOR_PathOp,                 kXOR_PathOp }, { kXOR_PathOp,                 kXOR_PathOp }},
-    {{ kReverseDifference_PathOp, kUnion_PathOp }, { kIntersect_PathOp,    kDifference_PathOp }},
+{{ kDifference_SkPathOp,   kIntersect_SkPathOp }, { kUnion_SkPathOp, kReverseDifference_SkPathOp }},
+{{ kIntersect_SkPathOp,   kDifference_SkPathOp }, { kReverseDifference_SkPathOp, kUnion_SkPathOp }},
+{{ kUnion_SkPathOp, kReverseDifference_SkPathOp }, { kDifference_SkPathOp,   kIntersect_SkPathOp }},
+{{ kXOR_SkPathOp,                 kXOR_SkPathOp }, { kXOR_SkPathOp,                kXOR_SkPathOp }},
+{{ kReverseDifference_SkPathOp, kUnion_SkPathOp }, { kIntersect_SkPathOp,   kDifference_SkPathOp }},
 };
 
-static const bool gOutInverse[kReverseDifference_PathOp + 1][2][2] = {
+static const bool gOutInverse[kReverseDifference_SkPathOp + 1][2][2] = {
     {{ false, false }, { true, false }},  // diff
     {{ false, false }, { false, true }},  // sect
     {{ false, true }, { true, true }},    // union
@@ -291,16 +255,20 @@ static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) {
     dump_path(file, two, false, true);
     fprintf(file, "    SkPath path2(path);\n");
     fprintf(file, "    testPathOp(reporter, path1, path2, (SkPathOp) %d, filename);\n", op);
-    fprintf(file, "}\n");	
+    fprintf(file, "}\n");    
     fclose(file);
 }
 #endif
 
 bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
+    SkChunkAlloc allocator(4096);  // FIXME: add a constant expression here, tune
+    SkOpContour contour;
+    SkOpCoincidence coincidence;
+    SkOpGlobalState globalState(&coincidence  PATH_OPS_DEBUG_PARAMS(&contour));
 #if DEBUGGING_PATHOPS_FROM_HOST
     dump_op(one, two, op);
-#endif	
-#if DEBUG_SHOW_TEST_NAME
+#endif    
+#if 0 && DEBUG_SHOW_TEST_NAME
     char* debugName = DEBUG_FILENAME_STRING;
     if (debugName && debugName[0]) {
         SkPathOpsDebug::BumpTestName(debugName);
@@ -312,62 +280,62 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
             ? SkPath::kInverseEvenOdd_FillType : SkPath::kEvenOdd_FillType;
     const SkPath* minuend = &one;
     const SkPath* subtrahend = &two;
-    if (op == kReverseDifference_PathOp) {
+    if (op == kReverseDifference_SkPathOp) {
         minuend = &two;
         subtrahend = &one;
-        op = kDifference_PathOp;
+        op = kDifference_SkPathOp;
     }
 #if DEBUG_SORT || DEBUG_SWAP_TOP
     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
 #endif
     // turn path into list of segments
-    SkTArray<SkOpContour> contours;
-    // FIXME: add self-intersecting cubics' T values to segment
-    SkOpEdgeBuilder builder(*minuend, contours);
+    SkOpEdgeBuilder builder(*minuend, &contour, &allocator, &globalState);
     if (builder.unparseable()) {
         return false;
     }
     const int xorMask = builder.xorMask();
     builder.addOperand(*subtrahend);
-    if (!builder.finish()) {
+    if (!builder.finish(&allocator)) {
         return false;
     }
+#if !FORCE_RELEASE
+    contour.dumpSegments(op);
+#endif
+
     result->reset();
     result->setFillType(fillType);
     const int xorOpMask = builder.xorMask();
-    SkTArray<SkOpContour*, true> contourList;
-    MakeContourList(contours, contourList, xorMask == kEvenOdd_PathOpsMask,
+    SkTDArray<SkOpContour* > contourList;
+    MakeContourList(&contour, contourList, xorMask == kEvenOdd_PathOpsMask,
             xorOpMask == kEvenOdd_PathOpsMask);
     SkOpContour** currentPtr = contourList.begin();
     if (!currentPtr) {
         return true;
     }
+    if ((*currentPtr)->count() == 0) {
+        SkASSERT((*currentPtr)->next() == NULL);
+        return true;
+    }
     SkOpContour** listEnd = contourList.end();
     // find all intersections between segments
     do {
         SkOpContour** nextPtr = currentPtr;
         SkOpContour* current = *currentPtr++;
-        if (current->containsCubics()) {
-            AddSelfIntersectTs(current);
-        }
         SkOpContour* next;
         do {
             next = *nextPtr++;
-        } while (AddIntersectTs(current, next) && nextPtr != listEnd);
+        } while (AddIntersectTs(current, next, &coincidence, &allocator) && nextPtr != listEnd);
     } while (currentPtr != listEnd);
+#if DEBUG_VALIDATE
+    globalState.setPhase(SkOpGlobalState::kWalking);
+#endif
     // eat through coincident edges
-
-    int total = 0;
-    int index;
-    for (index = 0; index < contourList.count(); ++index) {
-        total += contourList[index]->segments().count();
-    }
-    if (!HandleCoincidence(&contourList, total)) {
+    if (!HandleCoincidence(&contourList, &coincidence, &allocator, &globalState)) {
         return false;
     }
     // construct closed contours
     SkPathWriter wrapper(*result);
-    bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper);
+    bridgeOp(contourList, op, xorMask, xorOpMask, &wrapper, &allocator);
     {  // if some edges could not be resolved, assemble remaining fragments
         SkPath temp;
         temp.setFillType(fillType);