pathops version two

src/pathops/SkOpContour.cpp

 /*
 * Copyright 2013 Google Inc.
 *
 * 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"
 
-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;
+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);
     }
-    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) {
+SkOpSegment* SkOpContour::nonVerticalSegment(SkOpSpanBase** start, SkOpSpanBase** end) {
     int segmentCount = fSortedSegments.count();
     SkASSERT(segmentCount > 0);
     for (int sortedIndex = fFirstSorted; sortedIndex < segmentCount; ++sortedIndex) {
         SkOpSegment* testSegment = fSortedSegments[sortedIndex];
         if (testSegment->done()) {
             continue;
         }
-        *start = *end = 0;
-        while (testSegment->nextCandidate(start, end)) {
-            if (!testSegment->isVertical(*start, *end)) {
+        SkOpSpanBase* span = testSegment->head();
+        SkOpSpanBase* testS, * testE;
+        while (SkOpSegment::NextCandidate(span, &testS, &testE)) {
+            if (!testSegment->isVertical(testS, testE)) {
+                *start = testS;
+                *end = testE;
                 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 {
-    int segmentCount = fSegments.count();
-    const SkPoint& pt = fSegments.front().pts()[0];
+    const SkPoint& pt = fHead.pts()[0];
     path->deferredMove(pt);
-    for (int test = 0; test < segmentCount; ++test) {
-        fSegments[test].addCurveTo(0, 1, path, true);
-    }
+    const SkOpSegment* segment = &fHead;
+    do {
+        segment->addCurveTo(segment->head(), segment->tail(), path, true);
+    } while ((segment = segment->next()));
     path->close();
 }
 
 void SkOpContour::topSortableSegment(const SkPoint& topLeft, SkPoint* bestXY,
         SkOpSegment** topStart) {
     int segmentCount = fSortedSegments.count();
     SkASSERT(segmentCount > 0);
     int sortedIndex = fFirstSorted;
     fDone = true;  // may be cleared below
     for ( ; sortedIndex < segmentCount; ++sortedIndex) {
@@ skipping 18 matching lines @@
             }
             if (bestXY->fY == testXY.fY && bestXY->fX < testXY.fX) {
                 continue;
             }
         }
         *topStart = testSegment;
         *bestXY = testXY;
     }
 }
 
-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()) {
+SkOpSegment* SkOpContour::undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr) {
+    SkOpSegment* segment = &fHead;
+    do {
+        if (segment->done()) {
             continue;
         }
-        testSegment->undoneSpan(start, end);
-        return testSegment;
-    }
+        segment->undoneSpan(startPtr, endPtr);
+        return segment;
+    } while ((segment = segment->next()));
     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());
-    }
-}