Path ops formerly found the topmost unprocessed edge and determined its angle sort order to initialize the winding. This never worked correctly with cubics and was flaky with paths consisting mostly of vertical edges.

This replacement shoots axis-aligned rays through all intersecting edges to find the outermost one either horizontally or vertically. The resulting code is smaller and twice as fast.

To support this, most of the horizontal / vertical intersection code was rewritten and standardized, and old code supporting the top-directed winding was deleted.

Contours were pointed to by an SkTDArray. Instead, put them in a linked list, and designate the list head with its own class to ensure that methods that take lists of contours start at the top. This change removed a large percentage of memory allocations used by path ops.

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

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

1 files changed, 24 insertions, 54 deletions

diff --git a/src/pathops/SkPathOpsOp.cpp b/src/pathops/SkPathOpsOp.cpp
index 1105af5d70..f9a4fa3ca6 100644
--- a/src/pathops/SkPathOpsOp.cpp
+++ b/src/pathops/SkPathOpsOp.cpp
@@ -98,41 +98,17 @@ static SkOpSegment* findChaseOp(SkTDArray<SkOpSpanBase*>& chase, SkOpSpanBase**
     return NULL;
 }
 
-static bool bridgeOp(SkTDArray<SkOpContour* >& contourList, const SkPathOp op,
+static bool bridgeOp(SkOpContourHead* contourList, const SkPathOp op,
         const int xorMask, const int xorOpMask, SkPathWriter* simple, SkChunkAlloc* allocator) {
-    bool firstContour = true;
     bool unsortable = false;
-    bool topUnsortable = false;
-    bool firstPass = true;
-    SkDPoint lastTopLeft;
-    SkDPoint topLeft = {SK_ScalarMin, SK_ScalarMin};
     do {
-        SkOpSpanBase* start = NULL;
-        SkOpSpanBase* end = NULL;
-        bool topDone;
-        bool onlyVertical = false;
-        lastTopLeft = topLeft;
-        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);
-                if (lastTopLeft.fX == SK_ScalarMin && lastTopLeft.fY == SK_ScalarMin) {
-                    if (firstPass) {
-                        firstPass = false;
-                    } else {
-                        break;
-                    }
-                }
-                topLeft.fX = topLeft.fY = SK_ScalarMin;
-                continue;
-            }
-            break;
-        } else if (onlyVertical) {
+        SkOpSpan* span = FindSortableTop(contourList);
+        if (!span) {
             break;
         }
-        firstPass = !topUnsortable || lastTopLeft != topLeft;
+        SkOpSegment* current = span->segment();
+        SkOpSpanBase* start = span->next();
+        SkOpSpanBase* end = span;
         SkTDArray<SkOpSpanBase*> chase;
         do {
             if (current->activeOp(start, end, xorMask, xorOpMask, op)) {
@@ -260,11 +236,13 @@ static void dump_op(const SkPath& one, const SkPath& two, SkPathOp op) {
 }
 #endif
 
-bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
+bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result,
+        bool expectSuccess) {
     SkChunkAlloc allocator(4096);  // FIXME: add a constant expression here, tune
     SkOpContour contour;
+    SkOpContourHead* contourList = static_cast<SkOpContourHead*>(&contour);
     SkOpCoincidence coincidence;
-    SkOpGlobalState globalState(&coincidence  SkDEBUGPARAMS(&contour));
+    SkOpGlobalState globalState(&coincidence, contourList);
 #if DEBUGGING_PATHOPS_FROM_HOST
     dump_op(one, two, op);
 #endif    
@@ -285,7 +263,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
         subtrahend = &one;
         op = kDifference_SkPathOp;
     }
-#if DEBUG_SORT || DEBUG_SWAP_TOP
+#if DEBUG_SORT
     SkPathOpsDebug::gSortCount = SkPathOpsDebug::gSortCountDefault;
 #endif
     // turn path into list of segments
@@ -303,36 +281,24 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
 #endif
 
     const int xorOpMask = builder.xorMask();
-    SkTDArray<SkOpContour* > contourList;
-    MakeContourList(&contour, contourList, xorMask == kEvenOdd_PathOpsMask,
-            xorOpMask == kEvenOdd_PathOpsMask);
-    SkOpContour** currentPtr = contourList.begin();
-    if (!currentPtr) {
+    if (!SortContourList(&contourList, xorMask == kEvenOdd_PathOpsMask,
+            xorOpMask == kEvenOdd_PathOpsMask)) {
         result->reset();
         result->setFillType(fillType);
         return true;
     }
-    if ((*currentPtr)->count() == 0) {
-        SkASSERT((*currentPtr)->next() == NULL);
-        result->reset();
-        result->setFillType(fillType);
-        return true;
-    }
-    SkOpContour** listEnd = contourList.end();
     // find all intersections between segments
+    SkOpContour* current = contourList;
     do {
-        SkOpContour** nextPtr = currentPtr;
-        SkOpContour* current = *currentPtr++;
-        SkOpContour* next;
-        do {
-            next = *nextPtr++;
-        } while (AddIntersectTs(current, next, &coincidence, &allocator) && nextPtr != listEnd);
-    } while (currentPtr != listEnd);
+        SkOpContour* next = current;
+        while (AddIntersectTs(current, next, &coincidence, &allocator)
+                && (next = next->next()))
+            ;
+    } while ((current = current->next()));
 #if DEBUG_VALIDATE
     globalState.setPhase(SkOpGlobalState::kWalking);
 #endif
-    // eat through coincident edges
-    if (!HandleCoincidence(&contourList, &coincidence, &allocator, &globalState)) {
+    if (!HandleCoincidence(contourList, &coincidence, &allocator)) {
         return false;
     }
     // construct closed contours
@@ -350,3 +316,7 @@ bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
     }
     return true;
 }
+
+bool Op(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result) {
+    return OpDebug(one, two, op, result, true);
+}