pathops coincidence and security rewrite

src/pathops/SkOpSegment.cpp

Index: src/pathops/SkOpSegment.cpp
diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp
index 41d62369b644dfe12363173375bba0ab47ae0d9c..e4e00bbfab6fb46585aef89bb3845b24baa512b2 100644
--- a/src/pathops/SkOpSegment.cpp
+++ b/src/pathops/SkOpSegment.cpp
@@ -9,6 +9,8 @@
 #include "SkOpSegment.h"
 #include "SkPathWriter.h"
 
+#define FAIL_IF(cond) do { if (cond) return false; } while (false)
+
 /*
 After computing raw intersections, post process all segments to:
 - find small collections of points that can be collapsed to a single point
@@ -159,90 +161,10 @@ bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sum
     return result;
 }
 
-void SkOpSegment::addAlignIntersection(SkOpPtT& endPtT, SkPoint& oldPt,
-        SkOpContourHead* contourList, SkChunkAlloc* allocator) {
-    const SkPoint& newPt = endPtT.fPt;
-    if (newPt == oldPt) {
-        return;
-    }
-    SkPoint line[2] = { newPt, oldPt };
-    SkPathOpsBounds lineBounds;
-    lineBounds.setBounds(line, 2);
-    SkDLine aLine;
-    aLine.set(line);
-    SkOpContour* current = contourList;
-    do {
-        if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) {
-            continue;
-        }
-        SkOpSegment* segment = current->first();
-        do {
-            if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) {
-                continue;
-            }
-            if (newPt == segment->fPts[0]) {
-                continue;
-            }
-            if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
-                continue;
-            }
-            if (oldPt == segment->fPts[0]) {
-                continue;
-            }
-            if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) {
-                continue;
-            }
-            if (endPtT.contains(segment)) {
-                continue;
-            }
-            SkIntersections i;
-            switch (segment->fVerb) {
-                case SkPath::kLine_Verb: {
-                    SkDLine bLine;
-                    bLine.set(segment->fPts);
-                    i.intersect(bLine, aLine);
-                    } break;
-                case SkPath::kQuad_Verb: {
-                    SkDQuad bQuad;
-                    bQuad.set(segment->fPts);
-                    i.intersect(bQuad, aLine);
-                    } break;
-                case SkPath::kConic_Verb: {
-                    SkDConic bConic;
-                    bConic.set(segment->fPts, segment->fWeight);
-                    i.intersect(bConic, aLine);
-                    } break;
-                case SkPath::kCubic_Verb: {
-                    SkDCubic bCubic;
-                    bCubic.set(segment->fPts);
-                    i.intersect(bCubic, aLine);
-                    } break;
-                default:
-                    SkASSERT(0);
-            }
-            if (i.used()) {
-                SkASSERT(i.used() == 1);
-                SkASSERT(!zero_or_one(i[0][0]));
-                SkOpSpanBase* checkSpan = fHead.next();
-                while (!checkSpan->final()) {
-                    if (checkSpan->contains(segment)) {
-                        goto nextSegment;
-                    }
-                    checkSpan = checkSpan->upCast()->next();
-                }
-                SkOpPtT* ptT = segment->addT(i[0][0], SkOpSegment::kAllowAlias, allocator);
-                ptT->fPt = newPt;
-                endPtT.addOpp(ptT);
-            }
-    nextSegment:
-            ;
-        } while ((segment = segment->next()));
-    } while ((current = current->next()));
-}
-
 bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
         SkPathWriter* path) const {
     if (start->starter(end)->alreadyAdded()) {
+        SkDEBUGF(("same curve added twice aborted pathops\n"));
         return false;
     }
     SkOpCurve edge;
@@ -298,29 +220,57 @@ bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end,
     return true;
 }
 
-SkOpPtT* SkOpSegment::addMissing(double t, SkOpSegment* opp, SkChunkAlloc* allocator) {
-    SkOpSpanBase* existing = nullptr;
-    SkOpSpanBase* test = &fHead;
-    double testT;
+const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const {
+    const SkOpSpanBase* test = &fHead;
+    const SkOpPtT* testPtT;
+    SkPoint pt = this->ptAtT(t);
     do {
-        if ((testT = test->ptT()->fT) >= t) {
-            if (testT == t) {
-                existing = test;
-            }
+        testPtT = test->ptT();
+        if (testPtT->fT == t) {
             break;
         }
+        if (!this->match(testPtT, this, t, pt, opp ? kAllowAliasMatch : kNoAliasMatch)) {
+            if (t < testPtT->fT) {
+                return nullptr;
+            }
+            continue;
+        }
+        if (!opp) {
+            return testPtT;
+        }
+        const SkOpPtT* loop = testPtT->next();
+        while (loop != testPtT) {
+            if (loop->segment() == this && loop->fT == t && loop->fPt == pt) {
+                goto foundMatch;
+            }
+            loop = loop->next();
+        }
+        return nullptr;
     } while ((test = test->upCast()->next()));
-    SkOpPtT* result;
-    if (existing && existing->contains(opp)) {
-        result = existing->ptT();
-    } else {
-        result = this->addT(t, SkOpSegment::kNoAlias, allocator);
+foundMatch:
+    return opp && !test->contains(opp) ? nullptr : testPtT;
+}
+
+// break the span so that the coincident part does not change the angle of the remainder
+bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) {
+    if (this->contains(newT)) {
+        return true;
     }
-    SkASSERT(result);
-    return result;
+    SkOpPtT* newPtT = this->addT(newT, kAllowAliasMatch, startOver);
+    if (!newPtT) {
+        return false;
+    }
+    newPtT->fPt = this->ptAtT(newT);
+    // const cast away to change linked list; pt/t values stays unchanged
+    SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test);
+    if (writableTest->ptT()->addOpp(newPtT)) {
+        writableTest->checkForCollapsedCoincidence();
+    }
+    return true;
 }
 
-SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* allocator) {
+// Please keep this in sync with debugAddT()
+SkOpPtT* SkOpSegment::addT(double t, AliasMatch allowAlias, bool* allocated) {
     debugValidate();
     SkPoint pt = this->ptAtT(t);
     SkOpSpanBase* span = &fHead;
@@ -331,9 +281,9 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
         if (t == result->fT) {
             goto bumpSpan;
         }
-        if (this->match(result, this, t, pt)) {
+        if (this->match(result, this, t, pt, allowAlias)) {
             // see if any existing alias matches segment, pt, and t
-           loop = result->next();
+            loop = result->next();
             duplicatePt = false;
             while (loop != result) {
                 bool ptMatch = loop->fPt == pt;
@@ -343,12 +293,12 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
                 duplicatePt |= ptMatch;
                 loop = loop->next();
             }
-            if (kNoAlias == allowAlias) {
+            if (kNoAliasMatch == allowAlias) {
     bumpSpan:
                 span->bumpSpanAdds();
                 return result;
             }
-            SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator);
+            SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(this->globalState()->allocator());
             alias->init(result->span(), t, pt, duplicatePt);
             result->insert(alias);
             result->span()->unaligned();
@@ -358,6 +308,9 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
                     alias->segment()->debugID(), alias->span()->debugID());
 #endif
             span->bumpSpanAdds();
+            if (allocated) {
+                *allocated = true;
+            }
             return alias;
         }
         if (t < result->fT) {
@@ -365,7 +318,7 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
             if (!prev) {
                 return nullptr;
             }
-            SkOpSpan* span = insert(prev, allocator);
+            SkOpSpan* span = insert(prev);
             span->init(this, prev, t, pt);
             this->debugValidate();
 #if DEBUG_ADD_T
@@ -373,6 +326,9 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
                     span->segment()->debugID(), span->debugID());
 #endif
             span->bumpSpanAdds();
+            if (allocated) {
+                *allocated = true;
+            }
             return span->ptT();
         }
         SkASSERT(span != &fTail);
@@ -381,43 +337,17 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca
     return nullptr;
 }
 
-// choose a solitary t and pt value; remove aliases; align the opposite ends
-void SkOpSegment::align() {
-    debugValidate();
-    SkOpSpanBase* span = &fHead;
-    if (!span->aligned()) {
-        span->alignEnd(0, fPts[0]);
-    }
-    while ((span = span->upCast()->next())) {
-        if (span == &fTail) {
-            break;
-        }
-        span->align();
-    }
-    if (!span->aligned()) {
-        span->alignEnd(1, fPts[SkPathOpsVerbToPoints(fVerb)]);
-    }
-    if (this->collapsed()) {
-        SkOpSpan* span = &fHead;
-        do {
-            span->setWindValue(0);
-            span->setOppValue(0);
-            this->markDone(span);
-        } while ((span = span->next()->upCastable()));
-    }
-    debugValidate();
-}
-
-void SkOpSegment::calcAngles(SkChunkAlloc* allocator) {
+void SkOpSegment::calcAngles() {
     bool activePrior = !fHead.isCanceled();
     if (activePrior && !fHead.simple()) {
-        addStartSpan(allocator);
+        addStartSpan();
     }
     SkOpSpan* prior = &fHead;
     SkOpSpanBase* spanBase = fHead.next();
     while (spanBase != &fTail) {
         if (activePrior) {
-            SkOpAngle* priorAngle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+            SkOpAngle* priorAngle = SkOpTAllocator<SkOpAngle>::Allocate(
+                    this->globalState()->allocator());
             priorAngle->set(spanBase, prior);
             spanBase->setFromAngle(priorAngle);
         }
@@ -425,7 +355,8 @@ void SkOpSegment::calcAngles(SkChunkAlloc* allocator) {
         bool active = !span->isCanceled();
         SkOpSpanBase* next = span->next();
         if (active) {
-            SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator);
+            SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(
+                    this->globalState()->allocator());
             angle->set(span, next);
             span->setToAngle(angle);
         }
@@ -434,12 +365,32 @@ void SkOpSegment::calcAngles(SkChunkAlloc* allocator) {
         spanBase = next;
     }
     if (activePrior && !fTail.simple()) {
-        addEndSpan(allocator);
+        addEndSpan();
     }
 }
 
+// Please keep this in sync with debugClearAll()
+void SkOpSegment::clearAll() {
+    SkOpSpan* span = &fHead;
+    do {
+        this->clearOne(span);
+    } while ((span = span->next()->upCastable()));
+    this->globalState()->coincidence()->release(this);
+}
+
+// Please keep this in sync with debugClearOne()
+void SkOpSegment::clearOne(SkOpSpan* span) {
+    span->setWindValue(0);
+    span->setOppValue(0);
+    this->markDone(span);
+}
+
+// Quads and conics collapse if the end points are the same, because
+// the curve doesn't enclose an area.
 bool SkOpSegment::collapsed() const {
-    return fVerb == SkPath::kLine_Verb && fHead.pt() == fTail.pt();
+    // FIXME: cubics can have also collapsed -- need to check if the
+    // control points are on a line with the end points
+    return fVerb < SkPath::kCubic_Verb && fHead.pt() == fTail.pt();
 }
 
 void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle,
@@ -571,12 +522,26 @@ int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end,
     return start->starter(end)->windSum();
 }
 
+bool SkOpSegment::contains(double newT) const {
+    const SkOpSpanBase* spanBase = &fHead;
+    do {
+        if (spanBase->ptT()->contains(this, newT)) {
+            return true;
+        }
+        if (spanBase == &fTail) {
+            break;
+        }
+        spanBase = spanBase->upCast()->next();
+    } while (true);
+    return false;
+}
+
 void SkOpSegment::release(const SkOpSpan* span) {
     if (span->done()) {
         --fDoneCount;
     }
     --fCount;
-    SkASSERT(fCount >= fDoneCount);
+    SkASSERT(this->globalState()->debugSkipAssert() || fCount >= fDoneCount);
 }
 
 double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const {
@@ -601,15 +566,6 @@ double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const {
     return closestDistSq;
 }
 
-void SkOpSegment::findCollapsed() {
-    if (fHead.contains(&fTail)) {
-        markAllDone();
-        // move start and end to the same point
-        fHead.alignEnd(0, fHead.pt());
-        fTail.setAligned();
-    }
-}
-
 /*
  The M and S variable name parts stand for the operators.
    Mi stands for Minuend (see wiki subtraction, analogous to difference)
@@ -887,14 +843,12 @@ SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** n
 }
 
 SkOpGlobalState* SkOpSegment::globalState() const {
-    return contour()->globalState(); 
+    return contour()->globalState();
 }
 
 void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) {
     fContour = contour;
     fNext = nullptr;
-    fOriginal[0] = pts[0];
-    fOriginal[1] = pts[SkPathOpsVerbToPoints(verb)];
     fPts = pts;
     fWeight = weight;
     fVerb = verb;
@@ -1095,15 +1049,17 @@ bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) {
 }
 
 bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT,
-        const SkPoint& testPt) const {
-    const SkOpSegment* baseParent = base->segment();
-    if (this == baseParent && this == testParent && precisely_equal(base->fT, testT)) {
-        return true;
+        const SkPoint& testPt, AliasMatch aliasMatch) const {
+    SkASSERT(this == base->segment());
+    if (this == testParent) {
+        if (precisely_equal(base->fT, testT)) {
+            return true;
+        }
     }
     if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) {
         return false;
     }
-    return !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
+    return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt);
 }
 
 static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) {
@@ -1178,7 +1134,8 @@ SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpS
     return other;
 }
 
-static void clear_visited(SkOpSpanBase* span) {
+// Please keep this in sync with DebugClearVisited()
+void SkOpSegment::ClearVisited(SkOpSpanBase* span) {
     // reset visited flag back to false
     do {
         SkOpPtT* ptT = span->ptT(), * stopPtT = ptT;
@@ -1189,20 +1146,23 @@ static void clear_visited(SkOpSpanBase* span) {
     } while (!span->final() && (span = span->upCast()->next()));
 }
 
+// Please keep this in sync with debugMissingCoincidence()
 // look for pairs of undetected coincident curves
 // assumes that segments going in have visited flag clear
-// curve/curve intersection should now do a pretty good job of finding coincident runs so 
-// this may be only be necessary for line/curve pairs -- so skip unless this is a line and the
-// the opp is not a line
-bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator) {
-    if (this->verb() != SkPath::kLine_Verb) {
-        return false;
-    }
+// Even though pairs of curves correct detect coincident runs, a run may be missed
+// if the coincidence is a product of multiple intersections. For instance, given
+// curves A, B, and C:
+// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near
+// the end of C that the intersection is replaced with the end of C.
+// Even though A-B correctly do not detect an intersection at point 2,
+// the resulting run from point 1 to point 2 is coincident on A and B.
+bool SkOpSegment::missingCoincidence() {
     if (this->done()) {
         return false;
     }
     SkOpSpan* prior = nullptr;
     SkOpSpanBase* spanBase = &fHead;
+    bool result = false;
     do {
         SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT;
         SkASSERT(ptT->span() == spanBase);
@@ -1211,9 +1171,6 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
                 continue;
             }
             SkOpSegment* opp = ptT->span()->segment();
-//            if (opp->verb() == SkPath::kLine_Verb) {
-//                continue;
-//            }
             if (opp->done()) {
                 continue;
             }
@@ -1224,18 +1181,18 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
             if (spanBase == &fHead) {
                 continue;
             }
+            if (ptT->segment() == this) {
+                continue;
+            }
             SkOpSpan* span = spanBase->upCastable();
             // FIXME?: this assumes that if the opposite segment is coincident then no more
             // coincidence needs to be detected. This may not be true.
-            if (span && span->containsCoincidence(opp)) { 
-                continue;
-            }
-            if (spanBase->segment() == opp) {
+            if (span && span->containsCoincidence(opp)) {
                 continue;
             }
             if (spanBase->containsCoinEnd(opp)) {
                 continue;
-            } 
+            }
             SkOpPtT* priorPtT = nullptr, * priorStopPtT;
             // find prior span containing opp segment
             SkOpSegment* priorOpp = nullptr;
@@ -1268,28 +1225,28 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
                 SkTSwap(priorPtT, ptT);
                 SkTSwap(oppStart, oppEnd);
             }
-            bool flipped = oppStart->fT > oppEnd->fT;
-            bool coincident = false;
-            if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)) {
+            SkOpCoincidence* coincidences = this->globalState()->coincidence();
+            SkOpPtT* rootPriorPtT = priorPtT->span()->ptT();
+            SkOpPtT* rootPtT = ptT->span()->ptT();
+            SkOpPtT* rootOppStart = oppStart->span()->ptT();
+            SkOpPtT* rootOppEnd = oppEnd->span()->ptT();
+            if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
                 goto swapBack;
             }
-            if (opp->verb() == SkPath::kLine_Verb) {
-                coincident = (SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppStart->fPt) ||
-                        SkDPoint::ApproximatelyEqual(priorPtT->fPt, oppEnd->fPt)) &&
-                        (SkDPoint::ApproximatelyEqual(ptT->fPt, oppStart->fPt) ||
-                        SkDPoint::ApproximatelyEqual(ptT->fPt, oppEnd->fPt));
-            }
-            if (!coincident) {
-                coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp, 5000);
-            }
-            if (coincident) {
+            if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) {
             // mark coincidence
-                if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd)
-                        && !coincidences->extend(oppStart, oppEnd, priorPtT, ptT)) {
-                    coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator);
+#if DEBUG_COINCIDENCE_VERBOSE
+                SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__,
+                        rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(),
+                        rootOppEnd->debugID());
+#endif
+                if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) {
+                    coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd);
                 }
-                clear_visited(&fHead);
-                return true;
+#if DEBUG_COINCIDENCE
+                SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd));
+#endif
+                result = true;
             }
     swapBack:
             if (swapped) {
@@ -1297,19 +1254,18 @@ bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
             }
         }
     } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next()));
-    clear_visited(&fHead);
-    return false;
+    ClearVisited(&fHead);
+    return result;
 }
 
+// please keep this in sync with debugMoveMultiples()
 // if a span has more than one intersection, merge the other segments' span as needed
 bool SkOpSegment::moveMultiples() {
     debugValidate();
     SkOpSpanBase* test = &fHead;
     do {
         int addCount = test->spanAddsCount();
-        if (addCount < 1) {
-            return false;
-        }
+        FAIL_IF(addCount < 1);
         if (addCount == 1) {
             continue;
         }
@@ -1392,66 +1348,126 @@ bool SkOpSegment::moveMultiples() {
                     oppSegment->debugValidate();
                     goto checkNextSpan;
                 }
-        tryNextSpan: 
+        tryNextSpan:
                 ;
             } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next()));
         } while ((testPtT = testPtT->next()) != startPtT);
-checkNextSpan: 
+checkNextSpan:
         ;
     } while ((test = test->final() ? nullptr : test->upCast()->next()));
     debugValidate();
     return true;
 }
 
+// adjacent spans may have points close by
+bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan) const {
+    const SkOpPtT* refHead = refSpan->ptT();
+    const SkOpPtT* checkHead = checkSpan->ptT();
+// if the first pt pair from adjacent spans are far apart, assume that all are far enough apart
+    if (!SkDPoint::RoughlyEqual(refHead->fPt, checkHead->fPt)) {
+#if DEBUG_COINCIDENCE
+        // verify that no combination of points are close
+        const SkOpPtT* dBugRef = refHead;
+        do {
+            const SkOpPtT* dBugCheck = checkHead;
+            do {
+                SkASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt));
+                dBugCheck = dBugCheck->next();
+            } while (dBugCheck != checkHead);
+            dBugRef = dBugRef->next();
+        } while (dBugRef != refHead);
+#endif
+        return false;
+    }
+    // check only unique points
+    SkScalar distSqBest = SK_ScalarMax;
+    const SkOpPtT* refBest = nullptr;
+    const SkOpPtT* checkBest = nullptr;
+    const SkOpPtT* ref = refHead;
+    do {
+        if (ref->deleted()) {
+            continue;
+        }
+        while (ref->ptAlreadySeen(refHead)) {
+            ref = ref->next();
+            if (ref == refHead) {
+                goto doneCheckingDistance;
+            }
+        }
+        const SkOpPtT* check = checkHead;
+        const SkOpSegment* refSeg = ref->segment();
+        do {
+            if (check->deleted()) {
+                continue;
+            }
+            while (check->ptAlreadySeen(checkHead)) {
+                check = check->next();
+                if (check == checkHead) {
+                    goto nextRef;
+                }
+            }
+            SkScalar distSq = ref->fPt.distanceToSqd(check->fPt);
+            if (distSqBest > distSq && (refSeg != check->segment()
+                    || !refSeg->ptsDisjoint(*ref, *check))) {
+                distSqBest = distSq;
+                refBest = ref;
+                checkBest = check;
+            }
+        } while ((check = check->next()) != checkHead);
+nextRef:
+        ;
+   } while ((ref = ref->next()) != refHead);
+doneCheckingDistance:
+    return checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT,
+            checkBest->fPt, kAllowAliasMatch);
+}
+
+// Please keep this function in sync with debugMoveNearby()
 // Move nearby t values and pts so they all hang off the same span. Alignment happens later.
 void SkOpSegment::moveNearby() {
     debugValidate();
-    SkOpSpanBase* spanS = &fHead;
+    // release undeleted spans pointing to this seg that are linked to the primary span
+    SkOpSpanBase* spanBase = &fHead;
     do {
-        SkOpSpanBase* test = spanS->upCast()->next();
-        SkOpSpanBase* next;
-        if (spanS->contains(test)) {
-            if (!test->final()) {
-                test->upCast()->release(spanS->ptT());
-                continue;
-            } else if (spanS != &fHead) {
-                spanS->upCast()->release(test->ptT());
-                spanS = test;
-                continue;
+        SkOpPtT* ptT = spanBase->ptT();
+        const SkOpPtT* headPtT = ptT;
+        while ((ptT = ptT->next()) != headPtT) {
+            SkOpSpanBase* test = ptT->span();
+            if (ptT->segment() == this && !ptT->deleted() && test != spanBase
+                    && test->ptT() == ptT) {
+                if (test->final()) {
+                    if (spanBase == &fHead) {
+                        this->clearAll();
+                        return;
+                    }
+                    spanBase->upCast()->release(ptT);
+                } else if (test->prev()) {
+                    test->upCast()->release(headPtT);
+                }
+                break;
             }
         }
-        do {  // iterate through all spans associated with start
-            SkOpPtT* startBase = spanS->ptT();
-            next = test->final() ? nullptr : test->upCast()->next();
-            do {
-                SkOpPtT* testBase = test->ptT();
-                do {
-                    if (startBase == testBase) {
-                        goto checkNextSpan;
-                    }
-                    if (testBase->duplicate()) {
-                        continue;
-                    }
-                    if (this->match(startBase, testBase->segment(), testBase->fT, testBase->fPt)) {
-                        if (test == &this->fTail) {
-                            if (spanS == &fHead) {
-                                debugValidate();
-                                return;  // if this span has collapsed, remove it from parent
-                            }
-                            this->fTail.merge(spanS->upCast());
-                            debugValidate();
-                            return;
-                        }
-                        spanS->merge(test->upCast());
-                        goto checkNextSpan;
-                    }
-                } while ((testBase = testBase->next()) != test->ptT());
-            } while ((startBase = startBase->next()) != spanS->ptT());
-    checkNextSpan:
-            ;
-        } while ((test = next));
-        spanS = spanS->upCast()->next();
-    } while (!spanS->final());
+        spanBase = spanBase->upCast()->next();
+    } while (!spanBase->final());
+
+    // This loop looks for adjacent spans which are near by
+    spanBase = &fHead;
+    do {  // iterate through all spans associated with start
+        SkOpSpanBase* test = spanBase->upCast()->next();
+        if (this->spansNearby(spanBase, test)) {
+            if (test->final()) {
+                if (spanBase->prev()) {
+                    test->merge(spanBase->upCast());
+                } else {
+                    this->clearAll();
+                    return;
+                }
+            } else {
+                spanBase->merge(test->upCast());
+            }
+        }
+        spanBase = test;
+    } while (!spanBase->final());
     debugValidate();
 }
 
@@ -1679,8 +1695,7 @@ bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end,
 }
 
 bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT,
-        const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp,
-        SkScalar flatnessLimit) const {
+        const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const {
     // average t, find mid pt
     double midT = (prior->t() + spanBase->t()) / 2;
     SkPoint midPt = this->ptAtT(midT);
@@ -1688,22 +1703,28 @@ bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT
     // if the mid pt is not near either end pt, project perpendicular through opp seg
     if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt)
             && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) {
+        if (priorPtT->span() == ptT->span()) {
+          return false;
+        }
         coincident = false;
         SkIntersections i;
-        SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), midT);
-        SkDLine ray = {{{midPt.fX, midPt.fY},
-                {(double) midPt.fX + dxdy.fY, (double) midPt.fY - dxdy.fX}}};
-        (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i);
+        SkDCurve curvePart;
+        this->subDivide(prior, spanBase, &curvePart);
+        SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f);
+        SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f);
+        SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}};
+        SkDCurve oppPart;
+        opp->subDivide(priorPtT->span(), ptT->span(), &oppPart);
+        (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i);
         // measure distance and see if it's small enough to denote coincidence
         for (int index = 0; index < i.used(); ++index) {
+            if (!between(0, i[0][index], 1)) {
+                continue;
+            }
             SkDPoint oppPt = i.pt(index);
             if (oppPt.approximatelyEqual(midPt)) {
-                SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(),
-                        opp->weight(), i[index][0]);
-                oppDxdy.normalize();
-                dxdy.normalize();
-                SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILON);
-                coincident |= flatness < flatnessLimit;
+                // the coincidence can occur at almost any angle
+                coincident = true;
             }
         }
     }