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

8 files changed, 157 insertions, 27 deletions

diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h
index c86f27b22e..3d26ae84c8 100644
--- a/src/pathops/SkOpContour.h
+++ b/src/pathops/SkOpContour.h
@@ -211,17 +211,23 @@ public:
         } while ((segment = segment->next()));
     }
 
-    bool moveNearby() {
+    bool moveMultiples() {
         SkASSERT(fCount > 0);
         SkOpSegment* segment = &fHead;
         do {
-            if (!segment->moveNearby()) {
-                return false;
-            }
+            segment->moveMultiples();
         } while ((segment = segment->next()));
         return true;
     }
 
+    void moveNearby() {
+        SkASSERT(fCount > 0);
+        SkOpSegment* segment = &fHead;
+        do {
+            segment->moveNearby();
+        } while ((segment = segment->next()));
+    }
+
     SkOpContour* next() {
         return fNext;
     }
diff --git a/src/pathops/SkOpCubicHull.cpp b/src/pathops/SkOpCubicHull.cpp
index f3e0a7fc3f..6b17608e84 100644
--- a/src/pathops/SkOpCubicHull.cpp
+++ b/src/pathops/SkOpCubicHull.cpp
@@ -104,9 +104,10 @@ int SkDCubic::convexHull(char order[4]) const {
                     double dist2_3 = fPts[2].distanceSquared(fPts[3]);
                     double smallest1distSq = SkTMin(dist1_0, dist1_3);
                     double smallest2distSq = SkTMin(dist2_0, dist2_3);
-                    SkASSERT(approximately_zero(SkTMin(smallest1distSq, smallest2distSq)));
-                    order[2] = smallest1distSq < smallest2distSq ? 2 : 1;
-                    return 3;
+                    if (approximately_zero(SkTMin(smallest1distSq, smallest2distSq))) {
+                        order[2] = smallest1distSq < smallest2distSq ? 2 : 1;
+                        return 3;
+                    }
                 }
                 midX = index;
             } else if (sides == 0) { // '0' means both to one side or the other
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index b14be78d06..a571609f53 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -365,22 +365,26 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
     SkOpSpanBase* span = &fHead;
     do {
         SkOpPtT* result = span->ptT();
+        SkOpPtT* loop;
+        bool duplicatePt;
         if (t == result->fT) {
-            return result;
+            goto bumpSpan;
         }
         if (this->match(result, this, t, pt)) {
             // see if any existing alias matches segment, pt, and t
-            SkOpPtT* loop = result->next();
-            bool duplicatePt = false;
+           loop = result->next();
+            duplicatePt = false;
             while (loop != result) {
                 bool ptMatch = loop->fPt == pt;
                 if (loop->segment() == this && loop->fT == t && ptMatch) {
-                    return result;
+                    goto bumpSpan;
                 }
                 duplicatePt |= ptMatch;
                 loop = loop->next();
             }
             if (kNoAlias == allowAlias) {
+    bumpSpan:
+                span->bumpSpanAdds();
                 return result;
             }
             SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator);
@@ -392,6 +396,7 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
             SkDebugf("%s alias t=%1.9g segID=%d spanID=%d\n",  __FUNCTION__, t,
                     alias->segment()->debugID(), alias->span()->debugID());
 #endif
+            span->bumpSpanAdds();
             return alias;
         }
         if (t < result->fT) {
@@ -403,6 +408,7 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
             SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t,
                     span->segment()->debugID(), span->debugID());
 #endif
+            span->bumpSpanAdds();
             return span->ptT();
         }
         SkASSERT(span != &fTail);
@@ -725,9 +731,10 @@ SkOpSpan* SkOpSegment::crossedSpanY(const SkPoint& basePt, double mid, bool opp,
 
 void SkOpSegment::detach(const SkOpSpan* span) {
     if (span->done()) {
-        --this->fDoneCount;
+        --fDoneCount;
     }
-    --this->fCount;
+    --fCount;
+    SkASSERT(fCount >= fDoneCount);
 }
 
 double SkOpSegment::distSq(double t, SkOpAngle* oppAngle) {
@@ -1423,7 +1430,7 @@ bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, doub
     if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) {
         return false;
     }
-    return !ptsDisjoint(base->fT, base->fPt, testT, testPt);
+    return !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
 }
 
 static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) {
@@ -1639,8 +1646,107 @@ void SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
     clear_visited(&fHead);
 }
 
+// if a span has more than one intersection, merge the other segments' span as needed
+void SkOpSegment::moveMultiples() {
+    debugValidate();
+    SkOpSpanBase* test = &fHead;
+    do {
+        int addCount = test->spanAddsCount();
+        SkASSERT(addCount >= 1);
+        if (addCount == 1) {
+            continue;
+        }
+        SkOpPtT* startPtT = test->ptT();
+        SkOpPtT* testPtT = startPtT;
+        do {  // iterate through all spans associated with start
+            SkOpSpanBase* oppSpan = testPtT->span();
+            if (oppSpan->spanAddsCount() == addCount) {
+                continue;
+            }
+            if (oppSpan->deleted()) {
+                continue;
+            }
+            SkOpSegment* oppSegment = oppSpan->segment();
+            if (oppSegment == this) {
+                continue;
+            }
+            // find range of spans to consider merging
+            SkOpSpanBase* oppPrev = oppSpan;
+            SkOpSpanBase* oppFirst = oppSpan;
+            while ((oppPrev = oppPrev->prev())) {
+                if (!roughly_equal(oppPrev->t(), oppSpan->t())) {
+                    break;
+                }
+                if (oppPrev->spanAddsCount() == addCount) {
+                    continue;
+                }
+                if (oppPrev->deleted()) {
+                    continue;
+                }
+                oppFirst = oppPrev;
+            }
+            SkOpSpanBase* oppNext = oppSpan;
+            SkOpSpanBase* oppLast = oppSpan;
+            while ((oppNext = oppNext->final() ? NULL : oppNext->upCast()->next())) {
+                if (!roughly_equal(oppNext->t(), oppSpan->t())) {
+                    break;
+                }
+                if (oppNext->spanAddsCount() == addCount) {
+                    continue;
+                }
+                if (oppNext->deleted()) {
+                    continue;
+                }
+                oppLast = oppNext;
+            }
+            if (oppFirst == oppLast) {
+                continue;
+            }
+            SkOpSpanBase* oppTest = oppFirst;
+            do {
+                if (oppTest == oppSpan) {
+                    continue;
+                }
+                // check to see if the candidate meets specific criteria:
+                // it contains spans of segments in test's loop but not including 'this'
+                SkOpPtT* oppStartPtT = oppTest->ptT();
+                SkOpPtT* oppPtT = oppStartPtT;
+                while ((oppPtT = oppPtT->next()) != oppStartPtT) {
+                    SkOpSegment* oppPtTSegment = oppPtT->segment();
+                    if (oppPtTSegment == this) {
+                        goto tryNextSpan;
+                    }
+                    SkOpPtT* matchPtT = startPtT;
+                    do {
+                        if (matchPtT->segment() == oppPtTSegment) {
+                            goto foundMatch;
+                        }
+                    } while ((matchPtT = matchPtT->next()) != startPtT);
+                    goto tryNextSpan;
+            foundMatch:  // merge oppTest and oppSpan
+                    oppSegment->debugValidate();
+                    if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) {
+                        SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse
+                        SkASSERT(oppSpan != &oppSegment->fTail);
+                        oppTest->merge(oppSpan->upCast());
+                    } else {
+                        oppSpan->merge(oppTest->upCast());
+                    }
+                    oppSegment->debugValidate();
+                    goto checkNextSpan;
+                }
+        tryNextSpan: 
+                ;
+            } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
+        } while ((testPtT = testPtT->next()) != startPtT);
+checkNextSpan: 
+        ;
+    } while ((test = test->final() ? NULL : test->upCast()->next()));
+    debugValidate();
+}
+
 // Move nearby t values and pts so they all hang off the same span. Alignment happens later.
-bool SkOpSegment::moveNearby() {
+void SkOpSegment::moveNearby() {
     debugValidate();
     SkOpSpanBase* spanS = &fHead;
     do {
@@ -1672,11 +1778,11 @@ bool SkOpSegment::moveNearby() {
                         if (test == &this->fTail) {
                             if (spanS == &fHead) {
                                 debugValidate();
-                                return true;  // if this span has collapsed, remove it from parent
+                                return;  // if this span has collapsed, remove it from parent
                             }
                             this->fTail.merge(spanS->upCast());
                             debugValidate();
-                            return true;
+                            return;
                         }
                         spanS->merge(test->upCast());
                         spanS->upCast()->setNext(next);
@@ -1690,7 +1796,6 @@ bool SkOpSegment::moveNearby() {
         spanS = spanS->upCast()->next();
     } while (!spanS->final());
     debugValidate();
-    return true;
 }
 
 bool SkOpSegment::operand() const {
diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h
index f878f5e64e..1e9e1c44be 100644
--- a/src/pathops/SkOpSegment.h
+++ b/src/pathops/SkOpSegment.h
@@ -254,7 +254,8 @@ public:
     bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const;
     void missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator);
     bool monotonicInY(const SkOpSpanBase* start, const SkOpSpanBase* end) const;
-    bool moveNearby();
+    void moveMultiples();
+    void moveNearby();
 
     SkOpSegment* next() const {
         return fNext;
diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp
index 32d2376a0f..b75a692f74 100755
--- a/src/pathops/SkOpSpan.cpp
+++ b/src/pathops/SkOpSpan.cpp
@@ -275,6 +275,7 @@ void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, cons
     fCoinEnd = this;
     fFromAngle = NULL;
     fPrev = prev;
+    fSpanAdds = 0;
     fAligned = true;
     fChased = false;
     SkDEBUGCODE(fCount = 1);
@@ -304,6 +305,7 @@ void SkOpSpanBase::merge(SkOpSpan* span) {
 tryNextRemainder:
         remainder = next;
     }
+    fSpanAdds += span->fSpanAdds;
 }
 
 void SkOpSpan::applyCoincidence(SkOpSpan* opp) {
diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h
index bf03f4d5f6..ee2f332440 100644
--- a/src/pathops/SkOpSpan.h
+++ b/src/pathops/SkOpSpan.h
@@ -133,6 +133,10 @@ public:
 
     void alignEnd(double t, const SkPoint& pt);
 
+    void bumpSpanAdds() {
+        ++fSpanAdds;
+    }
+
     bool chased() const {
         return fChased;
     }
@@ -253,6 +257,10 @@ public:
         return fPtT.next()->next() == &fPtT; 
     }
 
+    int spanAddsCount() const {
+        return fSpanAdds;
+    }
+
     const SkOpSpan* starter(const SkOpSpanBase* end) const {
         const SkOpSpanBase* result = t() < end->t() ? this : end;
         return result->upCast();
@@ -316,6 +324,7 @@ protected:  // no direct access to internals to avoid treating a span base as a
     SkOpSpanBase* fCoinEnd;  // linked list of coincident spans that end here (may point to itself)
     SkOpAngle* fFromAngle;  // points to next angle from span start to end
     SkOpSpan* fPrev;  // previous intersection point
+    int fSpanAdds;  // number of times intersections have been added to span
     bool fAligned;
     bool fChased;  // set after span has been added to chase array
     SkDEBUGCODE(int fCount);  // number of pt/t pairs added
diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index e766f5abe2..3496179e65 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -659,15 +659,20 @@ static void missingCoincidence(SkTDArray<SkOpContour* >* contourList,
     }
 }
 
-static bool moveNearby(SkTDArray<SkOpContour* >* contourList) {
+static void moveMultiples(SkTDArray<SkOpContour* >* contourList) {
     int contourCount = (*contourList).count();
     for (int cTest = 0; cTest < contourCount; ++cTest) {
         SkOpContour* contour = (*contourList)[cTest];
-        if (!contour->moveNearby()) {
-            return false;
-        }
+        contour->moveMultiples();
+    }
+}
+
+static void moveNearby(SkTDArray<SkOpContour* >* contourList) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->moveNearby();
     }
-    return true;
 }
 
 static void sortAngles(SkTDArray<SkOpContour* >* contourList) {
@@ -688,10 +693,10 @@ static void sortSegments(SkTDArray<SkOpContour* >* contourList) {
 
 bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* coincidence,
         SkChunkAlloc* allocator, SkOpGlobalState* globalState) {
+    // combine t values when multiple intersections occur on some segments but not others
+    moveMultiples(contourList);
     // move t values and points together to eliminate small/tiny gaps
-    if (!moveNearby(contourList)) {
-        return false;
-    }
+    moveNearby(contourList);
     align(contourList);  // give all span members common values
 #if DEBUG_VALIDATE
     globalState->setPhase(SkOpGlobalState::kIntersecting);
diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp
index 36f459935d..a9f8fe6acc 100644
--- a/src/pathops/SkPathOpsDebug.cpp
+++ b/src/pathops/SkPathOpsDebug.cpp
@@ -400,6 +400,7 @@ void SkOpSegment::debugValidate() const {
     } while (!span->final() && (span = span->upCast()->next()));
     SkASSERT(count == fCount);
     SkASSERT(done == fDoneCount);
+    SkASSERT(count >= fDoneCount);
     SkASSERT(span->final());
     span->debugValidate();
 #endif