Revert of pathops version two (patchset #16 id:150001 of https://codereview.chromium.org/1002693002/)

Reason for revert:
ASAN investigation

Original issue's description:
> pathops version two
>
> R=reed@google.com
>
> marked 'no commit' to attempt to get trybots to run
>
> TBR=reed@google.com
>
> Committed: https://skia.googlesource.com/skia/+/ccec0f958ffc71a9986d236bc2eb335cb2111119

TBR=caryclark@google.com
NOPRESUBMIT=true
NOTREECHECKS=true
NOTRY=true

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

1 files changed, 694 insertions, 44 deletions

diff --git a/src/pathops/SkOpContour.cpp b/src/pathops/SkOpContour.cpp
index d17b18905b..28c072a3c1 100644
--- a/src/pathops/SkOpContour.cpp
+++ b/src/pathops/SkOpContour.cpp
@@ -4,35 +4,42 @@
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
+#include "SkIntersections.h"
 #include "SkOpContour.h"
-#include "SkOpTAllocator.h"
 #include "SkPathWriter.h"
-#include "SkReduceOrder.h"
 #include "SkTSort.h"
 
-void SkOpContour::addCurve(SkPath::Verb verb, const SkPoint pts[4], SkChunkAlloc* allocator) {
-    switch (verb) {
-        case SkPath::kLine_Verb: {
-            SkPoint* ptStorage = SkOpTAllocator<SkPoint>::AllocateArray(allocator, 2);
-            memcpy(ptStorage, pts, sizeof(SkPoint) * 2);
-            appendSegment(allocator).addLine(ptStorage, this);
-        } break;
-        case SkPath::kQuad_Verb: {
-            SkPoint* ptStorage = SkOpTAllocator<SkPoint>::AllocateArray(allocator, 3);
-            memcpy(ptStorage, pts, sizeof(SkPoint) * 3);
-            appendSegment(allocator).addQuad(ptStorage, this);
-        } break;
-        case SkPath::kCubic_Verb: {
-            SkPoint* ptStorage = SkOpTAllocator<SkPoint>::AllocateArray(allocator, 4);
-            memcpy(ptStorage, pts, sizeof(SkPoint) * 4);
-            appendSegment(allocator).addCubic(ptStorage, this);
-        } break;
-        default:
-            SkASSERT(0);
-    }
-}
-
-SkOpSegment* SkOpContour::nonVerticalSegment(SkOpSpanBase** start, SkOpSpanBase** end) {
+bool SkOpContour::addCoincident(int index, SkOpContour* other, int otherIndex,
+        const SkIntersections& ts, bool swap) {
+    SkPoint pt0 = ts.pt(0).asSkPoint();
+    SkPoint pt1 = ts.pt(1).asSkPoint();
+    if (pt0 == pt1 || ts[0][0] == ts[0][1] || ts[1][0] == ts[1][1]) {
+        // FIXME: one could imagine a case where it would be incorrect to ignore this
+        // suppose two self-intersecting cubics overlap to be coincident --
+        // this needs to check that by some measure the t values are far enough apart
+        // or needs to check to see if the self-intersection bit was set on the cubic segment
+        return false;
+    }
+    SkCoincidence& coincidence = fCoincidences.push_back();
+    coincidence.fOther = other;
+    coincidence.fSegments[0] = index;
+    coincidence.fSegments[1] = otherIndex;
+    coincidence.fTs[swap][0] = ts[0][0];
+    coincidence.fTs[swap][1] = ts[0][1];
+    coincidence.fTs[!swap][0] = ts[1][0];
+    coincidence.fTs[!swap][1] = ts[1][1];
+    coincidence.fPts[swap][0] = pt0;
+    coincidence.fPts[swap][1] = pt1;
+    bool nearStart = ts.nearlySame(0);
+    bool nearEnd = ts.nearlySame(1);
+    coincidence.fPts[!swap][0] = nearStart ? ts.pt2(0).asSkPoint() : pt0;
+    coincidence.fPts[!swap][1] = nearEnd ? ts.pt2(1).asSkPoint() : pt1;
+    coincidence.fNearly[0] = nearStart;
+    coincidence.fNearly[1] = nearEnd;
+    return true;
+}
+
+SkOpSegment* SkOpContour::nonVerticalSegment(int* start, int* end) {
     int segmentCount = fSortedSegments.count();
     SkASSERT(segmentCount > 0);
     for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
@@ -40,27 +47,627 @@ SkOpSegment* SkOpContour::nonVerticalSegment(SkOpSpanBase** start, SkOpSpanBase*
         if (testSegment->done()) {
             continue;
         }
-        SkOpSpanBase* span = testSegment->head();
-        SkOpSpanBase* testS, * testE;
-        while (SkOpSegment::NextCandidate(span, &testS, &testE)) {
-            if (!testSegment->isVertical(testS, testE)) {
-                *start = testS;
-                *end = testE;
+        *start = *end = 0;
+        while (testSegment->nextCandidate(start, end)) {
+            if (!testSegment->isVertical(*start, *end)) {
                 return testSegment;
             }
-            span = span->upCast()->next();
         }
     }
     return NULL;
 }
 
+// if one is very large the smaller may have collapsed to nothing
+static void bump_out_close_span(double* startTPtr, double* endTPtr) {
+    double startT = *startTPtr;
+    double endT = *endTPtr;
+    if (approximately_negative(endT - startT)) {
+        if (endT <= 1 - FLT_EPSILON) {
+            *endTPtr += FLT_EPSILON;
+            SkASSERT(*endTPtr <= 1);
+        } else {
+            *startTPtr -= FLT_EPSILON;
+            SkASSERT(*startTPtr >= 0);
+        }
+    }
+}
+
+// first pass, add missing T values
+// second pass, determine winding values of overlaps
+void SkOpContour::addCoincidentPoints() {
+    int count = fCoincidences.count();
+    for (int index = 0; index < count; ++index) {
+        SkCoincidence& coincidence = fCoincidences[index];
+        int thisIndex = coincidence.fSegments[0];
+        SkOpSegment& thisOne = fSegments[thisIndex];
+        SkOpContour* otherContour = coincidence.fOther;
+        int otherIndex = coincidence.fSegments[1];
+        SkOpSegment& other = otherContour->fSegments[otherIndex];
+        if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
+            // OPTIMIZATION: remove from array
+            continue;
+        }
+    #if DEBUG_CONCIDENT
+        thisOne.debugShowTs("-");
+        other.debugShowTs("o");
+    #endif
+        double startT = coincidence.fTs[0][0];
+        double endT = coincidence.fTs[0][1];
+        bool startSwapped, oStartSwapped, cancelers;
+        if ((cancelers = startSwapped = startT > endT)) {
+            SkTSwap(startT, endT);
+        }
+        bump_out_close_span(&startT, &endT);
+        SkASSERT(!approximately_negative(endT - startT));
+        double oStartT = coincidence.fTs[1][0];
+        double oEndT = coincidence.fTs[1][1];
+        if ((oStartSwapped = oStartT > oEndT)) {
+            SkTSwap(oStartT, oEndT);
+            cancelers ^= true;
+        }
+        bump_out_close_span(&oStartT, &oEndT);
+        SkASSERT(!approximately_negative(oEndT - oStartT));
+        const SkPoint& startPt = coincidence.fPts[0][startSwapped];
+        if (cancelers) {
+            // make sure startT and endT have t entries
+            if (startT > 0 || oEndT < 1
+                    || thisOne.isMissing(startT, startPt) || other.isMissing(oEndT, startPt)) {
+                thisOne.addTPair(startT, &other, oEndT, true, startPt,
+                        coincidence.fPts[1][startSwapped]);
+            }
+            const SkPoint& oStartPt = coincidence.fPts[1][oStartSwapped];
+            if (oStartT > 0 || endT < 1
+                    || thisOne.isMissing(endT, oStartPt) || other.isMissing(oStartT, oStartPt)) {
+                other.addTPair(oStartT, &thisOne, endT, true, oStartPt,
+                        coincidence.fPts[0][oStartSwapped]);
+            }
+        } else {
+            if (startT > 0 || oStartT > 0
+                    || thisOne.isMissing(startT, startPt) || other.isMissing(oStartT, startPt)) {
+                thisOne.addTPair(startT, &other, oStartT, true, startPt,
+                        coincidence.fPts[1][startSwapped]);
+            }
+            const SkPoint& oEndPt = coincidence.fPts[1][!oStartSwapped];
+            if (endT < 1 || oEndT < 1
+                    || thisOne.isMissing(endT, oEndPt) || other.isMissing(oEndT, oEndPt)) {
+                other.addTPair(oEndT, &thisOne, endT, true, oEndPt,
+                        coincidence.fPts[0][!oStartSwapped]);
+            }
+        }
+    #if DEBUG_CONCIDENT
+        thisOne.debugShowTs("+");
+        other.debugShowTs("o");
+    #endif
+    }
+    // if there are multiple pairs of coincidence that share an edge, see if the opposite
+    // are also coincident
+    for (int index = 0; index < count - 1; ++index) {
+        const SkCoincidence& coincidence = fCoincidences[index];
+        int thisIndex = coincidence.fSegments[0];
+        SkOpContour* otherContour = coincidence.fOther;
+        int otherIndex = coincidence.fSegments[1];
+        for (int idx2 = 1; idx2 < count; ++idx2) {
+            const SkCoincidence& innerCoin = fCoincidences[idx2];
+            int innerThisIndex = innerCoin.fSegments[0];
+            if (thisIndex == innerThisIndex) {
+                checkCoincidentPair(coincidence, 1, innerCoin, 1, false);
+            }
+            if (this == otherContour && otherIndex == innerThisIndex) {
+                checkCoincidentPair(coincidence, 0, innerCoin, 1, false);
+            }
+            SkOpContour* innerOtherContour = innerCoin.fOther;
+            innerThisIndex = innerCoin.fSegments[1];
+            if (this == innerOtherContour && thisIndex == innerThisIndex) {
+                checkCoincidentPair(coincidence, 1, innerCoin, 0, false);
+            }
+            if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
+                checkCoincidentPair(coincidence, 0, innerCoin, 0, false);
+            }
+        }
+    }
+}
+
+bool SkOpContour::addPartialCoincident(int index, SkOpContour* other, int otherIndex,
+        const SkIntersections& ts, int ptIndex, bool swap) {
+    SkPoint pt0 = ts.pt(ptIndex).asSkPoint();
+    SkPoint pt1 = ts.pt(ptIndex + 1).asSkPoint();
+    if (SkDPoint::ApproximatelyEqual(pt0, pt1)) {
+        // FIXME: one could imagine a case where it would be incorrect to ignore this
+        // suppose two self-intersecting cubics overlap to form a partial coincidence --
+        // although it isn't clear why the regular coincidence could wouldn't pick this up
+        // this is exceptional enough to ignore for now
+        return false;
+    }
+    SkCoincidence& coincidence = fPartialCoincidences.push_back();
+    coincidence.fOther = other;
+    coincidence.fSegments[0] = index;
+    coincidence.fSegments[1] = otherIndex;
+    coincidence.fTs[swap][0] = ts[0][ptIndex];
+    coincidence.fTs[swap][1] = ts[0][ptIndex + 1];
+    coincidence.fTs[!swap][0] = ts[1][ptIndex];
+    coincidence.fTs[!swap][1] = ts[1][ptIndex + 1];
+    coincidence.fPts[0][0] = coincidence.fPts[1][0] = pt0;
+    coincidence.fPts[0][1] = coincidence.fPts[1][1] = pt1;
+    coincidence.fNearly[0] = 0;
+    coincidence.fNearly[1] = 0;
+    return true;
+}
+
+void SkOpContour::align(const SkOpSegment::AlignedSpan& aligned, bool swap,
+        SkCoincidence* coincidence) {
+    for (int idx2 = 0; idx2 < 2; ++idx2) {
+        if (coincidence->fPts[0][idx2] == aligned.fOldPt
+                && coincidence->fTs[swap][idx2] == aligned.fOldT) {
+            SkASSERT(SkDPoint::RoughlyEqual(coincidence->fPts[0][idx2], aligned.fPt));
+            coincidence->fPts[0][idx2] = aligned.fPt;
+            SkASSERT(way_roughly_equal(coincidence->fTs[swap][idx2], aligned.fT));
+            coincidence->fTs[swap][idx2] = aligned.fT;
+        }
+    }
+}
+
+void SkOpContour::alignCoincidence(const SkOpSegment::AlignedSpan& aligned,
+        SkTArray<SkCoincidence, true>* coincidences) {
+    int count = coincidences->count();
+    for (int index = 0; index < count; ++index) {
+        SkCoincidence& coincidence = (*coincidences)[index];
+        int thisIndex = coincidence.fSegments[0];
+        const SkOpSegment* thisOne = &fSegments[thisIndex];
+        const SkOpContour* otherContour = coincidence.fOther;
+        int otherIndex = coincidence.fSegments[1];
+        const SkOpSegment* other = &otherContour->fSegments[otherIndex];
+        if (thisOne == aligned.fOther1 && other == aligned.fOther2) {
+            align(aligned, false, &coincidence);
+        } else if (thisOne == aligned.fOther2 && other == aligned.fOther1) {
+            align(aligned, true, &coincidence);
+        }
+    }
+}
+
+void SkOpContour::alignTPt(int segmentIndex, const SkOpContour* other, int otherIndex, 
+        bool swap, int tIndex, SkIntersections* ts, SkPoint* point) const {
+    int zeroPt;
+    if ((zeroPt = alignT(swap, tIndex, ts)) >= 0) {
+        alignPt(segmentIndex, point, zeroPt);
+    }
+    if ((zeroPt = other->alignT(!swap, tIndex, ts)) >= 0) {
+        other->alignPt(otherIndex, point, zeroPt);
+    }
+}
+
+void SkOpContour::alignPt(int index, SkPoint* point, int zeroPt) const {
+    const SkOpSegment& segment = fSegments[index];
+    if (0 == zeroPt) {     
+        *point = segment.pts()[0];
+    } else {
+        *point = segment.pts()[SkPathOpsVerbToPoints(segment.verb())];
+    }
+}
+
+int SkOpContour::alignT(bool swap, int tIndex, SkIntersections* ts) const {
+    double tVal = (*ts)[swap][tIndex];
+    if (tVal != 0 && precisely_zero(tVal)) {
+        ts->set(swap, tIndex, 0);
+        return 0;
+    } 
+     if (tVal != 1 && precisely_equal(tVal, 1)) {
+        ts->set(swap, tIndex, 1);
+        return 1;
+    }
+    return -1;
+}
+
+bool SkOpContour::calcAngles() {
+    int segmentCount = fSegments.count();
+    for (int test = 0; test < segmentCount; ++test) {
+        if (!fSegments[test].calcAngles()) {
+            return false;
+        }
+    }
+    return true;
+}
+
+bool SkOpContour::calcCoincidentWinding() {
+    int count = fCoincidences.count();
+#if DEBUG_CONCIDENT
+    if (count > 0) {
+        SkDebugf("%s count=%d\n", __FUNCTION__, count);
+    }
+#endif
+    for (int index = 0; index < count; ++index) {
+        SkCoincidence& coincidence = fCoincidences[index];
+        if (!calcCommonCoincidentWinding(coincidence)) {
+            return false;
+        }
+    }
+    return true;
+}
+
+void SkOpContour::calcPartialCoincidentWinding() {
+    int count = fPartialCoincidences.count();
+#if DEBUG_CONCIDENT
+    if (count > 0) {
+        SkDebugf("%s count=%d\n", __FUNCTION__, count);
+    }
+#endif
+    for (int index = 0; index < count; ++index) {
+        SkCoincidence& coincidence = fPartialCoincidences[index];
+        calcCommonCoincidentWinding(coincidence);
+    }
+    // if there are multiple pairs of partial coincidence that share an edge, see if the opposite
+    // are also coincident
+    for (int index = 0; index < count - 1; ++index) {
+        const SkCoincidence& coincidence = fPartialCoincidences[index];
+        int thisIndex = coincidence.fSegments[0];
+        SkOpContour* otherContour = coincidence.fOther;
+        int otherIndex = coincidence.fSegments[1];
+        for (int idx2 = 1; idx2 < count; ++idx2) {
+            const SkCoincidence& innerCoin = fPartialCoincidences[idx2];
+            int innerThisIndex = innerCoin.fSegments[0];
+            if (thisIndex == innerThisIndex) {
+                checkCoincidentPair(coincidence, 1, innerCoin, 1, true);
+            }
+            if (this == otherContour && otherIndex == innerThisIndex) {
+                checkCoincidentPair(coincidence, 0, innerCoin, 1, true);
+            }
+            SkOpContour* innerOtherContour = innerCoin.fOther;
+            innerThisIndex = innerCoin.fSegments[1];
+            if (this == innerOtherContour && thisIndex == innerThisIndex) {
+                checkCoincidentPair(coincidence, 1, innerCoin, 0, true);
+            }
+            if (otherContour == innerOtherContour && otherIndex == innerThisIndex) {
+                checkCoincidentPair(coincidence, 0, innerCoin, 0, true);
+            }
+        }
+    }
+}
+
+void SkOpContour::checkCoincidentPair(const SkCoincidence& oneCoin, int oneIdx,
+        const SkCoincidence& twoCoin, int twoIdx, bool partial) {
+    SkASSERT((oneIdx ? this : oneCoin.fOther) == (twoIdx ? this : twoCoin.fOther));
+    SkASSERT(oneCoin.fSegments[!oneIdx] == twoCoin.fSegments[!twoIdx]);
+    // look for common overlap
+    double min = SK_ScalarMax;
+    double max = SK_ScalarMin;
+    double min1 = oneCoin.fTs[!oneIdx][0];
+    double max1 = oneCoin.fTs[!oneIdx][1];
+    double min2 = twoCoin.fTs[!twoIdx][0];
+    double max2 = twoCoin.fTs[!twoIdx][1];
+    bool cancelers = (min1 < max1) != (min2 < max2);
+    if (min1 > max1) {
+        SkTSwap(min1, max1);
+    }
+    if (min2 > max2) {
+        SkTSwap(min2, max2);
+    }
+    if (between(min1, min2, max1)) {
+        min = min2;
+    }
+    if (between(min1, max2, max1)) {
+        max = max2;
+    }
+    if (between(min2, min1, max2)) {
+        min = SkTMin(min, min1);
+    }
+    if (between(min2, max1, max2)) {
+        max = SkTMax(max, max1);
+    }
+    if (min >= max) {
+        return;  // no overlap
+    }
+    // look to see if opposite are different segments
+    int seg1Index = oneCoin.fSegments[oneIdx];
+    int seg2Index = twoCoin.fSegments[twoIdx];
+    if (seg1Index == seg2Index) {
+        return;
+    }
+    SkOpContour* contour1 = oneIdx ? oneCoin.fOther : this;
+    SkOpContour* contour2 = twoIdx ? twoCoin.fOther : this;
+    SkOpSegment* segment1 = &contour1->fSegments[seg1Index];
+    SkOpSegment* segment2 = &contour2->fSegments[seg2Index];
+    // find opposite t value ranges corresponding to reference min/max range
+    const SkOpContour* refContour = oneIdx ? this : oneCoin.fOther;
+    const int refSegIndex = oneCoin.fSegments[!oneIdx];
+    const SkOpSegment* refSegment = &refContour->fSegments[refSegIndex];
+    int seg1Start = segment1->findOtherT(min, refSegment);
+    int seg1End = segment1->findOtherT(max, refSegment);
+    int seg2Start = segment2->findOtherT(min, refSegment);
+    int seg2End = segment2->findOtherT(max, refSegment);
+    // if the opposite pairs already contain min/max, we're done
+    if (seg1Start >= 0 && seg1End >= 0 && seg2Start >= 0 && seg2End >= 0) {
+        return;
+    }
+    double loEnd = SkTMin(min1, min2);
+    double hiEnd = SkTMax(max1, max2);
+    // insert the missing coincident point(s)
+    double missingT1 = -1;
+    double otherT1 = -1;
+    if (seg1Start < 0) {
+        if (seg2Start < 0) {
+            return;
+        }
+        missingT1 = segment1->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
+                segment2, seg1End);
+        if (missingT1 < 0) {
+            return;
+        }
+        const SkOpSpan* missingSpan = &segment2->span(seg2Start);
+        otherT1 = missingSpan->fT;
+    } else if (seg2Start < 0) {
+        SkASSERT(seg1Start >= 0);
+        missingT1 = segment2->calcMissingTStart(refSegment, loEnd, min, max, hiEnd,
+                segment1, seg2End);
+        if (missingT1 < 0) {
+            return;
+        }
+        const SkOpSpan* missingSpan = &segment1->span(seg1Start);
+        otherT1 = missingSpan->fT;
+    }
+    SkPoint missingPt1;
+    SkOpSegment* addTo1 = NULL;
+    SkOpSegment* addOther1 = seg1Start < 0 ? segment2 : segment1;
+    int minTIndex = refSegment->findExactT(min, addOther1);
+    SkASSERT(minTIndex >= 0);
+    if (missingT1 >= 0) {
+        missingPt1 = refSegment->span(minTIndex).fPt;
+        addTo1 = seg1Start < 0 ? segment1 : segment2;
+    }
+    double missingT2 = -1;
+    double otherT2 = -1;
+    if (seg1End < 0) {
+        if (seg2End < 0) {
+            return;
+        }
+        missingT2 = segment1->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
+                segment2, seg1Start);
+        if (missingT2 < 0) {
+            return;
+        }
+        const SkOpSpan* missingSpan = &segment2->span(seg2End);
+        otherT2 = missingSpan->fT;
+    } else if (seg2End < 0) {
+        SkASSERT(seg1End >= 0);
+        missingT2 = segment2->calcMissingTEnd(refSegment, loEnd, min, max, hiEnd,
+                segment1, seg2Start);
+        if (missingT2 < 0) {
+            return;
+        }
+        const SkOpSpan* missingSpan = &segment1->span(seg1End);
+        otherT2 = missingSpan->fT;
+    }
+    SkPoint missingPt2;
+    SkOpSegment* addTo2 = NULL;
+    SkOpSegment* addOther2 = seg1End < 0 ? segment2 : segment1;
+    int maxTIndex = refSegment->findExactT(max, addOther2);
+    SkASSERT(maxTIndex >= 0);
+    if (missingT2 >= 0) {
+        missingPt2 = refSegment->span(maxTIndex).fPt;
+        addTo2 = seg1End < 0 ? segment1 : segment2;
+    }
+    if (missingT1 >= 0) {
+        addTo1->pinT(missingPt1, &missingT1);
+        addTo1->addTPair(missingT1, addOther1, otherT1, false, missingPt1);
+    } else {
+        SkASSERT(minTIndex >= 0);
+        missingPt1 = refSegment->span(minTIndex).fPt;
+    }
+    if (missingT2 >= 0) {
+        addTo2->pinT(missingPt2, &missingT2);
+        addTo2->addTPair(missingT2, addOther2, otherT2, false, missingPt2);
+    } else {
+        SkASSERT(minTIndex >= 0);
+        missingPt2 = refSegment->span(maxTIndex).fPt;
+    }
+    if (!partial) {
+        return;
+    }
+    if (cancelers) {
+        if (missingT1 >= 0) {
+            if (addTo1->reversePoints(missingPt1, missingPt2)) {
+                SkTSwap(missingPt1, missingPt2);
+            }
+            addTo1->addTCancel(missingPt1, missingPt2, addOther1);
+        } else {
+            if (addTo2->reversePoints(missingPt1, missingPt2)) {
+                SkTSwap(missingPt1, missingPt2);
+            }
+            addTo2->addTCancel(missingPt1, missingPt2, addOther2);
+        }
+    } else if (missingT1 >= 0) {
+        SkAssertResult(addTo1->addTCoincident(missingPt1, missingPt2,
+                addTo1 == addTo2 ? missingT2 : otherT2, addOther1));
+    } else {
+        SkAssertResult(addTo2->addTCoincident(missingPt2, missingPt1,
+                addTo2 == addTo1 ? missingT1 : otherT1, addOther2));
+    }
+}
+
+void SkOpContour::joinCoincidence(const SkTArray<SkCoincidence, true>& coincidences, bool partial) {
+    int count = coincidences.count();
+#if DEBUG_CONCIDENT
+    if (count > 0) {
+        SkDebugf("%s count=%d\n", __FUNCTION__, count);
+    }
+#endif
+    // look for a lineup where the partial implies another adjoining coincidence
+    for (int index = 0; index < count; ++index) {
+        const SkCoincidence& coincidence = coincidences[index];
+        int thisIndex = coincidence.fSegments[0];
+        SkOpSegment& thisOne = fSegments[thisIndex];
+        if (thisOne.done()) {
+            continue;
+        }
+        SkOpContour* otherContour = coincidence.fOther;
+        int otherIndex = coincidence.fSegments[1];
+        SkOpSegment& other = otherContour->fSegments[otherIndex];
+        if (other.done()) {
+            continue;
+        }
+        double startT = coincidence.fTs[0][0];
+        double endT = coincidence.fTs[0][1];
+        if (startT == endT) {  // this can happen in very large compares
+            continue;
+        }
+        double oStartT = coincidence.fTs[1][0];
+        double oEndT = coincidence.fTs[1][1];
+        if (oStartT == oEndT) {
+            continue;
+        }
+        bool swapStart = startT > endT;
+        bool swapOther = oStartT > oEndT;
+        const SkPoint* startPt = &coincidence.fPts[0][0];
+        const SkPoint* endPt = &coincidence.fPts[0][1];
+        if (swapStart) {
+            SkTSwap(startT, endT);
+            SkTSwap(oStartT, oEndT);
+            SkTSwap(startPt, endPt);
+        }
+        bool cancel = swapOther != swapStart;
+        int step = swapStart ? -1 : 1;
+        int oStep = swapOther ? -1 : 1;
+        double oMatchStart = cancel ? oEndT : oStartT;
+        if (partial ? startT != 0 || oMatchStart != 0 : (startT == 0) != (oMatchStart == 0)) {
+            bool added = false;
+            if (oMatchStart != 0) {
+                const SkPoint& oMatchStartPt = cancel ? *endPt : *startPt;
+                added = thisOne.joinCoincidence(&other, oMatchStart, oMatchStartPt, oStep, cancel);
+            }
+            if (!cancel && startT != 0 && !added) {
+                (void) other.joinCoincidence(&thisOne, startT, *startPt, step, cancel);
+            }
+        }
+        double oMatchEnd = cancel ? oStartT : oEndT;
+        if (partial ? endT != 1 || oMatchEnd != 1 : (endT == 1) != (oMatchEnd == 1)) {
+            bool added = false;
+            if (cancel && endT != 1 && !added) {
+                (void) other.joinCoincidence(&thisOne, endT, *endPt, -step, cancel);
+            }
+        }
+    }
+}
+
+bool SkOpContour::calcCommonCoincidentWinding(const SkCoincidence& coincidence) {
+    if (coincidence.fNearly[0] && coincidence.fNearly[1]) {
+        return true;
+    }
+    int thisIndex = coincidence.fSegments[0];
+    SkOpSegment& thisOne = fSegments[thisIndex];
+    if (thisOne.done()) {
+        return true;
+    }
+    SkOpContour* otherContour = coincidence.fOther;
+    int otherIndex = coincidence.fSegments[1];
+    SkOpSegment& other = otherContour->fSegments[otherIndex];
+    if (other.done()) {
+        return true;
+    }
+    double startT = coincidence.fTs[0][0];
+    double endT = coincidence.fTs[0][1];
+    const SkPoint* startPt = &coincidence.fPts[0][0];
+    const SkPoint* endPt = &coincidence.fPts[0][1];
+    bool cancelers;
+    if ((cancelers = startT > endT)) {
+        SkTSwap<double>(startT, endT);
+        SkTSwap<const SkPoint*>(startPt, endPt);
+    }
+    bump_out_close_span(&startT, &endT);
+    SkASSERT(!approximately_negative(endT - startT));
+    double oStartT = coincidence.fTs[1][0];
+    double oEndT = coincidence.fTs[1][1];
+    if (oStartT > oEndT) {
+        SkTSwap<double>(oStartT, oEndT);
+        cancelers ^= true;
+    }
+    bump_out_close_span(&oStartT, &oEndT);
+    SkASSERT(!approximately_negative(oEndT - oStartT));
+    bool success = true;
+    if (cancelers) {
+        thisOne.addTCancel(*startPt, *endPt, &other);
+    } else {
+        success = thisOne.addTCoincident(*startPt, *endPt, endT, &other);
+    }
+#if DEBUG_CONCIDENT
+    thisOne.debugShowTs("p");
+    other.debugShowTs("o");
+#endif
+    return success;
+}
+
+void SkOpContour::resolveNearCoincidence() {
+    int count = fCoincidences.count();
+    for (int index = 0; index < count; ++index) {
+        SkCoincidence& coincidence = fCoincidences[index];
+        if (!coincidence.fNearly[0] || !coincidence.fNearly[1]) {
+            continue;
+        }
+        int thisIndex = coincidence.fSegments[0];
+        SkOpSegment& thisOne = fSegments[thisIndex];
+        SkOpContour* otherContour = coincidence.fOther;
+        int otherIndex = coincidence.fSegments[1];
+        SkOpSegment& other = otherContour->fSegments[otherIndex];
+        if ((thisOne.done() || other.done()) && thisOne.complete() && other.complete()) {
+            // OPTIMIZATION: remove from coincidence array
+            continue;
+        }
+    #if DEBUG_CONCIDENT
+        thisOne.debugShowTs("-");
+        other.debugShowTs("o");
+    #endif
+        double startT = coincidence.fTs[0][0];
+        double endT = coincidence.fTs[0][1];
+        bool cancelers;
+        if ((cancelers = startT > endT)) {
+            SkTSwap<double>(startT, endT);
+        }
+        if (startT == endT) { // if span is very large, the smaller may have collapsed to nothing
+            if (endT <= 1 - FLT_EPSILON) {
+                endT += FLT_EPSILON;
+                SkASSERT(endT <= 1);
+            } else {
+                startT -= FLT_EPSILON;
+                SkASSERT(startT >= 0);
+            }
+        }
+        SkASSERT(!approximately_negative(endT - startT));
+        double oStartT = coincidence.fTs[1][0];
+        double oEndT = coincidence.fTs[1][1];
+        if (oStartT > oEndT) {
+            SkTSwap<double>(oStartT, oEndT);
+            cancelers ^= true;
+        }
+        SkASSERT(!approximately_negative(oEndT - oStartT));
+        if (cancelers) {
+            thisOne.blindCancel(coincidence, &other);
+        } else {
+            thisOne.blindCoincident(coincidence, &other);
+        }
+    }
+}
+
+void SkOpContour::sortAngles() {
+    int segmentCount = fSegments.count();
+    for (int test = 0; test < segmentCount; ++test) {
+        fSegments[test].sortAngles();
+    }
+}
+
+void SkOpContour::sortSegments() {
+    int segmentCount = fSegments.count();
+    fSortedSegments.push_back_n(segmentCount);
+    for (int test = 0; test < segmentCount; ++test) {
+        fSortedSegments[test] = &fSegments[test];
+    }
+    SkTQSort<SkOpSegment>(fSortedSegments.begin(), fSortedSegments.end() - 1);
+    fFirstSorted = 0;
+}
+
 void SkOpContour::toPath(SkPathWriter* path) const {
-    const SkPoint& pt = fHead.pts()[0];
+    int segmentCount = fSegments.count();
+    const SkPoint& pt = fSegments.front().pts()[0];
     path->deferredMove(pt);
-    const SkOpSegment* segment = &fHead;
-    do {
-        segment->addCurveTo(segment->head(), segment->tail(), path, true);
-    } while ((segment = segment->next()));
+    for (int test = 0; test < segmentCount; ++test) {
+        fSegments[test].addCurveTo(0, 1, path, true);
+    }
     path->close();
 }
 
@@ -99,14 +706,57 @@ void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
     }
 }
 
-SkOpSegment* SkOpContour::undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr) {
-    SkOpSegment* segment = &fHead;
-    do {
-        if (segment->done()) {
+SkOpSegment* SkOpContour::undoneSegment(int* start, int* end) {
+    int segmentCount = fSegments.count();
+    for (int test = 0; test < segmentCount; ++test) {
+        SkOpSegment* testSegment = &fSegments[test];
+        if (testSegment->done()) {
             continue;
         }
-        segment->undoneSpan(startPtr, endPtr);
-        return segment;
-    } while ((segment = segment->next()));
+        testSegment->undoneSpan(start, end);
+        return testSegment;
+    }
     return NULL;
 }
+
+#if DEBUG_SHOW_WINDING
+int SkOpContour::debugShowWindingValues(int totalSegments, int ofInterest) {
+    int count = fSegments.count();
+    int sum = 0;
+    for (int index = 0; index < count; ++index) {
+        sum += fSegments[index].debugShowWindingValues(totalSegments, ofInterest);
+    }
+//      SkDebugf("%s sum=%d\n", __FUNCTION__, sum);
+    return sum;
+}
+
+void SkOpContour::debugShowWindingValues(const SkTArray<SkOpContour*, true>& contourList) {
+//     int ofInterest = 1 << 1 | 1 << 5 | 1 << 9 | 1 << 13;
+//    int ofInterest = 1 << 4 | 1 << 8 | 1 << 12 | 1 << 16;
+    int ofInterest = 1 << 5 | 1 << 8;
+    int total = 0;
+    int index;
+    for (index = 0; index < contourList.count(); ++index) {
+        total += contourList[index]->segments().count();
+    }
+    int sum = 0;
+    for (index = 0; index < contourList.count(); ++index) {
+        sum += contourList[index]->debugShowWindingValues(total, ofInterest);
+    }
+//       SkDebugf("%s total=%d\n", __FUNCTION__, sum);
+}
+#endif
+
+void SkOpContour::setBounds() {
+    int count = fSegments.count();
+    if (count == 0) {
+        SkDebugf("%s empty contour\n", __FUNCTION__);
+        SkASSERT(0);
+        // FIXME: delete empty contour?
+        return;
+    }
+    fBounds = fSegments.front().bounds();
+    for (int index = 1; index < count; ++index) {
+        fBounds.add(fSegments[index].bounds());
+    }
+}