The path ops builder code needs to determine the winding of each contour added, and reverse windings if the contours are nested in other contours.

Cheap (one contour) paths can be evaluated and reversed as needed with a minimum of checking, but multi-contour paths invoke the regular path ops machinery to determine who is contained by whom.

More tests need to be added to verify that all corner cases are considered, but this fixes the cases in the bug thus far.

R=fmalita@chromium.org
TBR=reed@google.com
BUG=skia:3838

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

10 files changed, 158 insertions, 23 deletions

diff --git a/src/pathops/SkOpBuilder.cpp b/src/pathops/SkOpBuilder.cpp
index 1a446f15b6..39da2efbce 100644
--- a/src/pathops/SkOpBuilder.cpp
+++ b/src/pathops/SkOpBuilder.cpp
@@ -6,8 +6,80 @@
  */
 
 #include "SkMatrix.h"
+#include "SkOpEdgeBuilder.h"
 #include "SkPath.h"
 #include "SkPathOps.h"
+#include "SkPathOpsCommon.h"
+
+static bool one_contour(const SkPath& path) {
+    SkChunkAlloc allocator(256);
+    int verbCount = path.countVerbs();
+    uint8_t* verbs = (uint8_t*) allocator.alloc(sizeof(uint8_t) * verbCount,
+            SkChunkAlloc::kThrow_AllocFailType);
+    (void) path.getVerbs(verbs, verbCount);
+    for (int index = 1; index < verbCount; ++index) {
+        if (verbs[index] == SkPath::kMove_Verb) {
+            return false;
+        }
+    }
+    return true;
+}
+
+void FixWinding(SkPath* path) {
+    SkPath::FillType fillType = path->getFillType();
+    if (fillType == SkPath::kInverseEvenOdd_FillType) {
+        fillType = SkPath::kInverseWinding_FillType;
+    } else if (fillType == SkPath::kEvenOdd_FillType) {
+        fillType = SkPath::kWinding_FillType;
+    }
+    SkPath::Direction dir;
+    if (one_contour(*path) && path->cheapComputeDirection(&dir)) {
+        if (dir != SkPath::kCCW_Direction) {
+            SkPath temp;
+            temp.reverseAddPath(*path);
+            *path = temp;
+        }
+        path->setFillType(fillType);
+        return;
+    }
+    SkChunkAlloc allocator(4096);
+    SkOpContourHead contourHead;
+    SkOpGlobalState globalState(NULL, &contourHead);
+    SkOpEdgeBuilder builder(*path, &contourHead, &allocator, &globalState);
+    builder.finish(&allocator);
+    SkASSERT(contourHead.next());
+    contourHead.resetReverse();
+    bool writePath = false;
+    SkOpSpan* topSpan;
+    globalState.setPhase(SkOpGlobalState::kFixWinding);
+    while ((topSpan = FindSortableTop(&contourHead))) {
+        SkOpSegment* topSegment = topSpan->segment();
+        SkOpContour* topContour = topSegment->contour();
+        bool active = topSegment->activeWinding(topSpan, topSpan->next());
+        SkASSERT(topContour->isCcw() >= 0);
+        if (active != SkToBool(topContour->isCcw())) {
+            topContour->setReverse();
+            writePath = true;
+        }
+        topContour->markDone();
+    }
+    if (!writePath) {
+        path->setFillType(fillType);
+        return;
+    }
+    SkPath empty;
+    SkPathWriter woundPath(empty);
+    SkOpContour* test = &contourHead;
+    do {
+        if (test->reversed()) {
+            test->toReversePath(&woundPath);
+        } else {
+            test->toPath(&woundPath);
+        }
+    } while ((test = test->next()));
+    *path = *woundPath.nativePath();
+    path->setFillType(fillType);
+}
 
 void SkOpBuilder::add(const SkPath& path, SkPathOp op) {
     if (0 == fOps.count() && op != kUnion_SkPathOp) {
@@ -82,10 +154,11 @@ bool SkOpBuilder::resolve(SkPath* result) {
             *result = original;
             return false;
         }
+        // convert the even odd result back to winding form before accumulating it
+        FixWinding(&fPathRefs[index]);
         sum.addPath(fPathRefs[index]);
     }
     reset();
-    sum.setFillType(SkPath::kEvenOdd_FillType);
     bool success = Simplify(sum, result);
     if (!success) {
         *result = original;
diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index 178ba3e89c..18b6328a7e 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -47,6 +47,16 @@ void SkOpContour::toPath(SkPathWriter* path) const {
     path->close();
 }
 
+void SkOpContour::toReversePath(SkPathWriter* path) const {
+    const SkPoint& pt = fTail->pts()[0];
+    path->deferredMove(pt);
+    const SkOpSegment* segment = fTail;
+    do {
+        segment->addCurveTo(segment->tail(), segment->head(), path, true);
+    } while ((segment = segment->prev()));
+    path->close();
+}
+
 SkOpSegment* SkOpContour::undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr) {
     SkOpSegment* segment = &fHead;
     do {
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index dd5dbb40ca..f8143cf555 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -207,10 +207,21 @@ public:
         SkDEBUGCODE(fID = globalState->nextContourID());
     }
 
+    int isCcw() const {
+        return fCcw;
+    }
+
     bool isXor() const {
         return fXor;
     }
 
+    void markDone() {
+        SkOpSegment* segment = &fHead;
+        do {
+            segment->markAllDone();
+        } while ((segment = segment->next()));
+    }
+
     void missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
         SkASSERT(fCount > 0);
         SkOpSegment* segment = &fHead;
@@ -289,6 +300,18 @@ public:
         SkDEBUGCODE(fDebugIndent = 0);
     }
 
+    void resetReverse() {
+        SkOpContour* next = this;
+        do {
+            next->fCcw = -1;
+            next->fReverse = false;
+        } while ((next = next->next()));
+    }
+
+    bool reversed() const {
+        return fReverse;
+    }
+
     void setBounds() {
         SkASSERT(fCount > 0);
         const SkOpSegment* segment = &fHead;
@@ -298,6 +321,10 @@ public:
         }
     }
 
+    void setCcw(int ccw) {
+        fCcw = ccw;
+    }
+
     void setGlobalState(SkOpGlobalState* state) {
         fState = state;
     }
@@ -315,6 +342,10 @@ public:
         fOppXor = isOppXor;
     }
 
+    void setReverse() {
+        fReverse = true;
+    }
+
     void setXor(bool isXor) {
         fXor = isXor;
     }
@@ -347,6 +378,7 @@ public:
         } while ((segment = segment->next()));
     }
 
+    void toReversePath(SkPathWriter* path) const;
     void toPath(SkPathWriter* path) const;
     SkOpSegment* undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr);
 
@@ -356,11 +388,13 @@ private:
     SkOpSegment* fTail;
     SkOpContour* fNext;
     SkPathOpsBounds fBounds;
+    int fCcw;
     int fCount;
     int fFirstSorted;
     bool fDone;  // set by find top segment
     bool fTopsFound;
     bool fOperand;  // true for the second argument to a binary operator
+    bool fReverse;  // true if contour should be reverse written to path (used only by fix winding)
     bool fXor;  // set if original path had even-odd fill
     bool fOppXor;  // set if opposite path had even-odd fill
     SkDEBUGCODE(int fID);
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 8bd0f03518..462cff60cf 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -852,6 +852,13 @@ bool SkOpSegment::isXor() const {
     return fContour->isXor();
 }
 
+void SkOpSegment::markAllDone() {
+    SkOpSpan* span = this->head();
+    do {
+        this->markDone(span);
+    } while ((span = span->next()->upCastable()));
+}
+
 SkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) {
     int step = start->step(end);
     SkOpSpan* minSpan = start->starter(end);
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index 1162c2cfaf..38de40617a 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -231,6 +231,7 @@ public:
         return fPts[SkPathOpsVerbToPoints(fVerb)];
     }
 
+    void markAllDone();
     SkOpSpanBase* markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end);
     bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding,
             SkOpSpanBase** lastPtr);
diff --git a/src/pathops/SkPathOpsCommon.h b/src/pathops/SkPathOpsCommon.h
index b7fbf38b3d..f76d57c83b 100644
--- a/src/pathops/SkPathOpsCommon.h
+++ b/src/pathops/SkPathOpsCommon.h
@@ -22,6 +22,7 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
 SkOpSpan* FindSortableTop(SkOpContourHead* );
 SkOpSegment* FindUndone(SkOpContourHead* , SkOpSpanBase** startPtr,
                         SkOpSpanBase** endPtr);
+void FixWinding(SkPath* path);
 bool SortContourList(SkOpContourHead** , bool evenOdd, bool oppEvenOdd);
 bool HandleCoincidence(SkOpContourHead* , SkOpCoincidence* , SkChunkAlloc* );
 bool OpDebug(const SkPath& one, const SkPath& two, SkPathOp op, SkPath* result, bool expectSuccess);
diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp
index d37998b448..11b6833a73 100644
--- a/src/pathops/SkPathOpsSimplify.cpp
+++ b/src/pathops/SkPathOpsSimplify.cpp
@@ -212,3 +212,4 @@ bool Simplify(const SkPath& path, SkPath* result) {
     }
     return true;
 }
+
diff --git a/src/pathops/SkPathOpsTypes.h b/src/pathops/SkPathOpsTypes.h
index 845288f609..a780a88c6d 100644
--- a/src/pathops/SkPathOpsTypes.h
+++ b/src/pathops/SkPathOpsTypes.h
@@ -33,9 +33,7 @@ public:
         , fContourHead(head)
         , fWindingFailed(false)
         , fAngleCoincidence(false)
-#if DEBUG_VALIDATE
         , fPhase(kIntersecting)
-#endif
         SkDEBUGPARAMS(fAngleID(0))
         SkDEBUGPARAMS(fContourID(0))
         SkDEBUGPARAMS(fPtTID(0))
@@ -43,12 +41,11 @@ public:
         SkDEBUGPARAMS(fSpanID(0)) {
     }
 
-#if DEBUG_VALIDATE
     enum Phase {
         kIntersecting,
-        kWalking
+        kWalking,
+        kFixWinding,
     };
-#endif
 
     enum {
         kMaxWindingTries = 10
@@ -93,11 +90,9 @@ public:
     }
 #endif
 
-#if DEBUG_VALIDATE
     Phase phase() const {
         return fPhase;
     }
-#endif
 
     void setAngleCoincidence() {
         fAngleCoincidence = true;
@@ -107,12 +102,10 @@ public:
         fContourHead = contourHead;
     }
 
-#if DEBUG_VALIDATE
     void setPhase(Phase phase) {
         SkASSERT(fPhase != phase);
         fPhase = phase;
     }
-#endif
 
     // called in very rare cases where angles are sorted incorrectly -- signfies op will fail
     void setWindingFailed() {
@@ -128,9 +121,7 @@ private:
     SkOpContourHead* fContourHead;
     bool fWindingFailed;
     bool fAngleCoincidence;
-#if DEBUG_VALIDATE
     Phase fPhase;
-#endif
 #ifdef SK_DEBUG
     int fAngleID;
     int fContourID;
diff --git a/src/pathops/SkPathOpsWinding.cpp b/src/pathops/SkPathOpsWinding.cpp
index 53083e484e..4a7b1bc3eb 100644
--- a/src/pathops/SkPathOpsWinding.cpp
+++ b/src/pathops/SkPathOpsWinding.cpp
@@ -342,8 +342,12 @@ bool SkOpSpan::sortableTop(SkOpContour* contourHead) {
 #endif
         }
         if (sumSet) {
-            (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, NULL);
-            (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, NULL);
+            if (this->globalState()->phase() == SkOpGlobalState::kFixWinding) {
+                hitSegment->contour()->setCcw(ccw);
+            } else {
+                (void) hitSegment->markAndChaseWinding(span, span->next(), windSum, oppSum, NULL);
+                (void) hitSegment->markAndChaseWinding(span->next(), span, windSum, oppSum, NULL);
+            }
         }
         if (operand) {
             SkTSwap(wind, oppWind);
diff --git a/tests/PathOpsBuilderTest.cpp b/tests/PathOpsBuilderTest.cpp
index 8ab92c3124..ea4c567e62 100644
--- a/tests/PathOpsBuilderTest.cpp
+++ b/tests/PathOpsBuilderTest.cpp
@@ -33,8 +33,10 @@ DEF_TEST(PathOpsBuilder, reporter) {
     SkPath::Direction dir;
     REPORTER_ASSERT(reporter, result.isRect(NULL, &closed, &dir));
     REPORTER_ASSERT(reporter, closed);
-    REPORTER_ASSERT(reporter, dir == SkPath::kCW_Direction);
-    REPORTER_ASSERT(reporter, rectPath == result);
+    REPORTER_ASSERT(reporter, dir == SkPath::kCCW_Direction);
+    SkBitmap bitmap;
+    int pixelDiff = comparePaths(reporter, __FUNCTION__, rectPath, result, bitmap);
+    REPORTER_ASSERT(reporter, pixelDiff == 0);
 
     rectPath.reset();
     rectPath.setFillType(SkPath::kEvenOdd_FillType);
@@ -44,7 +46,7 @@ DEF_TEST(PathOpsBuilder, reporter) {
     REPORTER_ASSERT(reporter, result.isRect(NULL, &closed, &dir));
     REPORTER_ASSERT(reporter, closed);
     REPORTER_ASSERT(reporter, dir == SkPath::kCCW_Direction);
-     REPORTER_ASSERT(reporter, rectPath == result);
+    REPORTER_ASSERT(reporter, rectPath == result);
 
     builder.add(rectPath, kDifference_SkPathOp);
     REPORTER_ASSERT(reporter, builder.resolve(&result));
@@ -74,12 +76,11 @@ DEF_TEST(PathOpsBuilder, reporter) {
     builder.add(circle2, kUnion_SkPathOp);
     builder.add(circle3, kDifference_SkPathOp);
     REPORTER_ASSERT(reporter, builder.resolve(&result));
-    SkBitmap bitmap;
-    int pixelDiff = comparePaths(reporter, __FUNCTION__, opCompare, result, bitmap);
+    pixelDiff = comparePaths(reporter, __FUNCTION__, opCompare, result, bitmap);
     REPORTER_ASSERT(reporter, pixelDiff == 0);
 }
 
-DEF_TEST(Issue3838, reporter) {
+DEF_TEST(BuilderIssue3838, reporter) {
     SkPath path;
     path.moveTo(200, 170);
     path.lineTo(220, 170);
@@ -93,9 +94,6 @@ DEF_TEST(Issue3838, reporter) {
     path.lineTo(200, 250);
     path.lineTo(200, 170);
     path.close();
-    testSimplify(reporter, path, __FUNCTION__);
-    SkPath path3;
-    Simplify(path, &path3);
     SkPath path2;
     SkOpBuilder builder;
     builder.add(path, kUnion_SkPathOp);
@@ -104,3 +102,18 @@ DEF_TEST(Issue3838, reporter) {
     int pixelDiff = comparePaths(reporter, __FUNCTION__, path, path2, bitmap);
     REPORTER_ASSERT(reporter, pixelDiff == 0);
 }
+
+DEF_TEST(BuilderIssue3838_2, reporter) {
+    SkPath path;
+    path.addCircle(100, 100, 50);
+
+    SkOpBuilder builder;
+    builder.add(path, kUnion_SkPathOp);
+    builder.add(path, kUnion_SkPathOp);
+
+    SkPath result;
+    SkBitmap bitmap;
+    builder.resolve(&result);
+    int pixelDiff = comparePaths(reporter, __FUNCTION__, path, result, bitmap);
+    REPORTER_ASSERT(reporter, pixelDiff == 0);
+}