cumulative pathops patch

Replace the implicit curve intersection with a geometric curve intersection. The implicit intersection proved mathematically unstable and took a long time to zero in on an answer.

Use pointers instead of indices to refer to parts of curves. Indices required awkward renumbering.

Unify t and point values so that small intervals can be eliminated in one pass.

Break cubics up front to eliminate loops and cusps.

Make the Simplify and Op code more regular and eliminate arbitrary differences.

Add a builder that takes an array of paths and operators.

Delete unused code.

BUG=skia:3588
R=reed@google.com

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

1 files changed, 262 insertions, 324 deletions

diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp
index 1a5bfc1889..1dc171caf3 100644
--- a/src/pathops/SkPathOpsCommon.cpp
+++ b/src/pathops/SkPathOpsCommon.cpp
@@ -5,47 +5,25 @@
  * found in the LICENSE file.
  */
 #include "SkAddIntersections.h"
+#include "SkOpCoincidence.h"
 #include "SkOpEdgeBuilder.h"
 #include "SkPathOpsCommon.h"
 #include "SkPathWriter.h"
 #include "SkTSort.h"
 
-static void alignMultiples(SkTArray<SkOpContour*, true>* contourList,
-        SkTDArray<SkOpSegment::AlignedSpan>* aligned) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        if (contour->hasMultiples()) {
-            contour->alignMultiples(aligned);
-        }
-    }
-}
-
-static void alignCoincidence(SkTArray<SkOpContour*, true>* contourList,
-        const SkTDArray<SkOpSegment::AlignedSpan>& aligned) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        int count = aligned.count();
-        for (int index = 0; index < count; ++index) {
-            contour->alignCoincidence(aligned[index]);
-        }
-    }    
-}
-
-static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, SkOpSegment** currentPtr,
-                              int* indexPtr, int* endIndexPtr, double* bestHit, SkScalar* bestDx,
-                              bool* tryAgain, double* midPtr, bool opp) {
-    const int index = *indexPtr;
-    const int endIndex = *endIndexPtr;
+static int contourRangeCheckY(const SkTDArray<SkOpContour* >& contourList,
+        SkOpSegment** currentPtr, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr,
+        double* bestHit, SkScalar* bestDx, bool* tryAgain, double* midPtr, bool opp) {
+    SkOpSpanBase* start = *startPtr;
+    SkOpSpanBase* end = *endPtr;
     const double mid = *midPtr;
     const SkOpSegment* current = *currentPtr;
-    double tAtMid = current->tAtMid(index, endIndex, mid);
+    double tAtMid = SkOpSegment::TAtMid(start, end, mid);
     SkPoint basePt = current->ptAtT(tAtMid);
     int contourCount = contourList.count();
     SkScalar bestY = SK_ScalarMin;
     SkOpSegment* bestSeg = NULL;
-    int bestTIndex = 0;
+    SkOpSpan* bestTSpan = NULL;
     bool bestOpp;
     bool hitSomething = false;
     for (int cTest = 0; cTest < contourCount; ++cTest) {
@@ -57,37 +35,38 @@ static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, S
         if (bestY > contour->bounds().fBottom) {
             continue;
         }
-        int segmentCount = contour->segments().count();
-        for (int test = 0; test < segmentCount; ++test) {
-            SkOpSegment* testSeg = &contour->segments()[test];
+        SkOpSegment* testSeg = contour->first();
+        SkASSERT(testSeg);
+        do {
             SkScalar testY = bestY;
             double testHit;
-            int testTIndex = testSeg->crossedSpanY(basePt, &testY, &testHit, &hitSomething, tAtMid,
-                    testOpp, testSeg == current);
-            if (testTIndex < 0) {
-                if (testTIndex == SK_MinS32) {
+            bool vertical;
+            SkOpSpan* testTSpan = testSeg->crossedSpanY(basePt, tAtMid, testOpp,
+                    testSeg == current, &testY, &testHit, &hitSomething, &vertical);
+            if (!testTSpan) {
+                if (vertical) {
                     hitSomething = true;
                     bestSeg = NULL;
                     goto abortContours;  // vertical encountered, return and try different point
                 }
                 continue;
             }
-            if (testSeg == current && current->betweenTs(index, testHit, endIndex)) {
-                double baseT = current->t(index);
-                double endT = current->t(endIndex);
+            if (testSeg == current && SkOpSegment::BetweenTs(start, testHit, end)) {
+                double baseT = start->t();
+                double endT = end->t();
                 double newMid = (testHit - baseT) / (endT - baseT);
 #if DEBUG_WINDING
-                double midT = current->tAtMid(index, endIndex, mid);
-                SkPoint midXY = current->xyAtT(midT);
-                double newMidT = current->tAtMid(index, endIndex, newMid);
-                SkPoint newXY = current->xyAtT(newMidT);
+                double midT = SkOpSegment::TAtMid(start, end, mid);
+                SkPoint midXY = current->ptAtT(midT);
+                double newMidT = SkOpSegment::TAtMid(start, end, newMid);
+                SkPoint newXY = current->ptAtT(newMidT);
                 SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)"
                         " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__,
                         current->debugID(), mid, newMid,
-                        baseT, current->xAtT(index), current->yAtT(index),
+                        baseT, start->pt().fX, start->pt().fY,
                         baseT + mid * (endT - baseT), midXY.fX, midXY.fY,
                         baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,
-                        endT, current->xAtT(endIndex), current->yAtT(endIndex));
+                        endT, end->pt().fX, end->pt().fY);
 #endif
                 *midPtr = newMid * 2;  // calling loop with divide by 2 before continuing
                 return SK_MinS32;
@@ -95,38 +74,39 @@ static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, S
             bestSeg = testSeg;
             *bestHit = testHit;
             bestOpp = testOpp;
-            bestTIndex = testTIndex;
+            bestTSpan = testTSpan;
             bestY = testY;
-        }
+        } while ((testSeg = testSeg->next()));
     }
 abortContours:
     int result;
     if (!bestSeg) {
         result = hitSomething ? SK_MinS32 : 0;
     } else {
-        if (bestSeg->windSum(bestTIndex) == SK_MinS32) {
+        if (bestTSpan->windSum() == SK_MinS32) {
             *currentPtr = bestSeg;
-            *indexPtr = bestTIndex;
-            *endIndexPtr = bestSeg->nextSpan(bestTIndex, 1);
-            SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
+            *startPtr = bestTSpan;
+            *endPtr = bestTSpan->next();
+            SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr);
             *tryAgain = true;
             return 0;
         }
-        result = bestSeg->windingAtT(*bestHit, bestTIndex, bestOpp, bestDx);
+        result = bestSeg->windingAtT(*bestHit, bestTSpan, bestOpp, bestDx);
         SkASSERT(result == SK_MinS32 || *bestDx);
     }
-    double baseT = current->t(index);
-    double endT = current->t(endIndex);
+    double baseT = (*startPtr)->t();
+    double endT = (*endPtr)->t();
     *bestHit = baseT + mid * (endT - baseT);
     return result;
 }
 
-SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end) {
+SkOpSegment* FindUndone(SkTDArray<SkOpContour* >& contourList, SkOpSpanBase** startPtr,
+         SkOpSpanBase** endPtr) {
     int contourCount = contourList.count();
     SkOpSegment* result;
     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
         SkOpContour* contour = contourList[cIndex];
-        result = contour->undoneSegment(start, end);
+        result = contour->undoneSegment(startPtr, endPtr);
         if (result) {
             return result;
         }
@@ -134,20 +114,23 @@ SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, i
     return NULL;
 }
 
-SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex) {
+SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr,
+        SkOpSpanBase** endPtr) {
     while (chase->count()) {
-        SkOpSpan* span;
+        SkOpSpanBase* span;
         chase->pop(&span);
-        const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
-        SkOpSegment* segment = backPtr.fOther;
-        *tIndex = backPtr.fOtherIndex;
+        SkOpSegment* segment = span->segment();
+        *startPtr = span->ptT()->next()->span();
         bool sortable = true;
         bool done = true;
-        *endIndex = -1;
-        if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
+        *endPtr = NULL;
+        if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done,
                 &sortable)) {
-            *tIndex = last->start();
-            *endIndex = last->end();
+            if (last->unorderable()) {
+                continue;
+            }
+            *startPtr = last->start();
+            *endPtr = last->end();
     #if TRY_ROTATE
             *chase->insert(0) = span;
     #else
@@ -162,65 +145,58 @@ SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex)
             continue;
         }
         // find first angle, initialize winding to computed wind sum
-        const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
-        const SkOpAngle* firstAngle;
-        SkDEBUGCODE(firstAngle = angle);
-        SkDEBUGCODE(bool loop = false);
-        int winding;
+        const SkOpAngle* angle = segment->spanToAngle(*startPtr, *endPtr);
+        if (!angle) {
+            continue;
+        }
+        const SkOpAngle* firstAngle = angle;
+        bool loop = false;
+        int winding = SK_MinS32;
         do {
             angle = angle->next();
-            SkASSERT(angle != firstAngle || !loop);
-            SkDEBUGCODE(loop |= angle == firstAngle);
+            if (angle == firstAngle && loop) {
+                break;    // if we get here, there's no winding, loop is unorderable
+            }
+            loop |= angle == firstAngle;
             segment = angle->segment();
             winding = segment->windSum(angle);
         } while (winding == SK_MinS32);
-        int spanWinding = segment->spanSign(angle->start(), angle->end());
-    #if DEBUG_WINDING
-        SkDebugf("%s winding=%d spanWinding=%d\n", __FUNCTION__, winding, spanWinding);
-    #endif
-        // turn span winding into contour winding
-        if (spanWinding * winding < 0) {
-            winding += spanWinding;
-        }
-        // we care about first sign and whether wind sum indicates this
-        // edge is inside or outside. Maybe need to pass span winding
-        // or first winding or something into this function?
-        // advance to first undone angle, then return it and winding
-        // (to set whether edges are active or not)
+        if (winding == SK_MinS32) {
+            continue;
+        }
+        int sumWinding = segment->updateWindingReverse(angle);
+        SkOpSegment* first = NULL;
         firstAngle = angle;
-        winding -= firstAngle->segment()->spanSign(firstAngle);
         while ((angle = angle->next()) != firstAngle) {
             segment = angle->segment();
-            int maxWinding = winding;
-            winding -= segment->spanSign(angle);
-    #if DEBUG_SORT
-            SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
-                    segment->debugID(), maxWinding, winding, angle->sign());
-    #endif
-            *tIndex = angle->start();
-            *endIndex = angle->end();
-            int lesser = SkMin32(*tIndex, *endIndex);
-            const SkOpSpan& nextSpan = segment->span(lesser);
-            if (!nextSpan.fDone) {
-            // FIXME: this be wrong? assign startWinding if edge is in
-            // same direction. If the direction is opposite, winding to
-            // assign is flipped sign or +/- 1?
-                if (SkOpSegment::UseInnerWinding(maxWinding, winding)) {
-                    maxWinding = winding;
+            SkOpSpanBase* start = angle->start();
+            SkOpSpanBase* end = angle->end();
+            int maxWinding;
+            segment->setUpWinding(start, end, &maxWinding, &sumWinding);
+            if (!segment->done(angle)) {
+                if (!first) {
+                    first = segment;
+                    *startPtr = start;
+                    *endPtr = end;
                 }
-                // allowed to do nothing
-                (void) segment->markAndChaseWinding(angle, maxWinding, 0, NULL);
-                break;
+                // OPTIMIZATION: should this also add to the chase?
+                (void) segment->markAngle(maxWinding, sumWinding, angle);
             }
         }
-        *chase->insert(0) = span;
-        return segment;
+        if (first) {
+       #if TRY_ROTATE
+            *chase->insert(0) = span;
+       #else
+            *chase->append() = span;
+       #endif
+            return first;
+        }
     }
     return NULL;
 }
 
-#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
-void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) {
+#if DEBUG_ACTIVE_SPANS
+void DebugShowActiveSpans(SkTDArray<SkOpContour* >& contourList) {
     int index;
     for (index = 0; index < contourList.count(); ++ index) {
         contourList[index]->debugShowActiveSpans();
@@ -228,11 +204,12 @@ void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) {
 }
 #endif
 
-static SkOpSegment* findTopSegment(const SkTArray<SkOpContour*, true>& contourList, int* index,
-        int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) {
+static SkOpSegment* findTopSegment(const SkTDArray<SkOpContour* >& contourList,
+        bool firstPass, SkOpSpanBase** start, SkOpSpanBase** end, SkPoint* topLeft,
+        bool* unsortable, bool* done, SkChunkAlloc* allocator) {
     SkOpSegment* result;
     const SkOpSegment* lastTopStart = NULL;
-    int lastIndex = -1, lastEndIndex = -1;
+    SkOpSpanBase* lastStart = NULL, * lastEnd = NULL;
     do {
         SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
         int contourCount = contourList.count();
@@ -261,27 +238,27 @@ static SkOpSegment* findTopSegment(const SkTArray<SkOpContour*, true>& contourLi
             return NULL;
         }
         *topLeft = bestXY;
-        result = topStart->findTop(index, endIndex, unsortable, firstPass);
+        result = topStart->findTop(firstPass, start, end, unsortable, allocator);
         if (!result) {
-            if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) {
+            if (lastTopStart == topStart && lastStart == *start && lastEnd == *end) {
                 *done = true;
                 return NULL;
             }
             lastTopStart = topStart;
-            lastIndex = *index;
-            lastEndIndex = *endIndex;
+            lastStart = *start;
+            lastEnd = *end;
         }
     } while (!result);
     return result;
 }
 
-static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList,
-        SkOpSegment** currentPtr, int* indexPtr, int* endIndexPtr, double* tHit,
+static int rightAngleWinding(const SkTDArray<SkOpContour* >& contourList,
+        SkOpSegment** currentPtr, SkOpSpanBase** start, SkOpSpanBase** end, double* tHit,
         SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) {
     double test = 0.9;
     int contourWinding;
     do {
-        contourWinding = contourRangeCheckY(contourList, currentPtr, indexPtr, endIndexPtr,
+        contourWinding = contourRangeCheckY(contourList, currentPtr, start, end,
                 tHit, hitDx, tryAgain, &test, opp);
         if (contourWinding != SK_MinS32 || *tryAgain) {
             return contourWinding;
@@ -296,9 +273,9 @@ static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList,
     return contourWinding;
 }
 
-static void skipVertical(const SkTArray<SkOpContour*, true>& contourList,
-        SkOpSegment** current, int* index, int* endIndex) {
-    if (!(*current)->isVertical(*index, *endIndex)) {
+static void skipVertical(const SkTDArray<SkOpContour* >& contourList,
+        SkOpSegment** current, SkOpSpanBase** start, SkOpSpanBase** end) {
+    if (!(*current)->isVertical(*start, *end)) {
         return;
     }
     int contourCount = contourList.count();
@@ -307,7 +284,7 @@ static void skipVertical(const SkTArray<SkOpContour*, true>& contourList,
         if (contour->done()) {
             continue;
         }
-        SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex);
+        SkOpSegment* nonVertical = contour->nonVerticalSegment(start, end);
         if (nonVertical) {
             *current = nonVertical;
             return;
@@ -316,41 +293,41 @@ static void skipVertical(const SkTArray<SkOpContour*, true>& contourList,
     return;
 }
 
-struct SortableTop {  // error if local in pre-C++11
-    SkOpSegment* fSegment;
-    int fIndex;
-    int fEndIndex;
+struct SortableTop2 {  // error if local in pre-C++11
+    SkOpSpanBase* fStart;
+    SkOpSpanBase* fEnd;
 };
 
-SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
-        SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
-        int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical,
-        bool firstPass) {
-    SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
-            done, firstPass);
+SkOpSegment* FindSortableTop(const SkTDArray<SkOpContour* >& contourList, bool firstPass,
+        SkOpAngle::IncludeType angleIncludeType, bool* firstContour, SkOpSpanBase** startPtr,
+        SkOpSpanBase** endPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical,
+        SkChunkAlloc* allocator) {
+    SkOpSegment* current = findTopSegment(contourList, firstPass, startPtr, endPtr, topLeft,
+            unsortable, done, allocator);
     if (!current) {
         return NULL;
     }
-    const int startIndex = *indexPtr;
-    const int endIndex = *endIndexPtr;
+    SkOpSpanBase* start = *startPtr;
+    SkOpSpanBase* end = *endPtr;
+    SkASSERT(current == start->segment());
     if (*firstContour) {
-        current->initWinding(startIndex, endIndex, angleIncludeType);
+        current->initWinding(start, end, angleIncludeType);
         *firstContour = false;
         return current;
     }
-    int minIndex = SkMin32(startIndex, endIndex);
-    int sumWinding = current->windSum(minIndex);
+    SkOpSpan* minSpan = start->starter(end);
+    int sumWinding = minSpan->windSum();
     if (sumWinding == SK_MinS32) {
-        int index = endIndex;
-        int oIndex = startIndex;
-        do { 
-            const SkOpSpan& span = current->span(index);
-            if ((oIndex < index ? span.fFromAngle : span.fToAngle) == NULL) {
-                current->addSimpleAngle(index);
+        SkOpSpanBase* iSpan = end;
+        SkOpSpanBase* oSpan = start;
+        do {
+            bool checkFrom = oSpan->t() < iSpan->t();
+            if ((checkFrom ? iSpan->fromAngle() : iSpan->upCast()->toAngle()) == NULL) {
+                iSpan->addSimpleAngle(checkFrom, allocator);
             }
-            sumWinding = current->computeSum(oIndex, index, angleIncludeType);
-            SkTSwap(index, oIndex);
-        } while (sumWinding == SK_MinS32 && index == startIndex);
+            sumWinding = current->computeSum(oSpan, iSpan, angleIncludeType);
+            SkTSwap(iSpan, oSpan);
+        } while (sumWinding == SK_MinS32 && iSpan == start);
     }
     if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) {
         return current;
@@ -364,26 +341,28 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
     SkScalar hitDx = 0;
     SkScalar hitOppDx = 0;
     // keep track of subsequent returns to detect infinite loops
-    SkTDArray<SortableTop> sortableTops;
+    SkTDArray<SortableTop2> sortableTops;
     do {
         // if current is vertical, find another candidate which is not
         // if only remaining candidates are vertical, then they can be marked done
-        SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
-        skipVertical(contourList, &current, indexPtr, endIndexPtr);
+        SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr);
+        SkASSERT(current == (*startPtr)->segment());
+        skipVertical(contourList, &current, startPtr, endPtr);
         SkASSERT(current);  // FIXME: if null, all remaining are vertical
-        SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
+        SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr);
+        SkASSERT(current == (*startPtr)->segment());
         tryAgain = false;
-        contourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
+        contourWinding = rightAngleWinding(contourList, &current, startPtr, endPtr, &tHit,
                 &hitDx, &tryAgain, onlyVertical, false);
+        SkASSERT(current == (*startPtr)->segment());
         if (tryAgain) {
             bool giveUp = false;
             int count = sortableTops.count();
             for (int index = 0; index < count; ++index) {
-                const SortableTop& prev = sortableTops[index];
+                const SortableTop2& prev = sortableTops[index];
                 if (giveUp) {
-                    prev.fSegment->markDoneFinal(prev.fIndex);
-                } else if (prev.fSegment == current
-                        && (prev.fIndex == *indexPtr || prev.fEndIndex == *endIndexPtr)) {
+                    prev.fStart->segment()->markDone(prev.fStart->starter(prev.fEnd));
+                } else if (prev.fStart == *startPtr || prev.fEnd == *endPtr) {
                     // remaining edges are non-vertical and cannot have their winding computed
                     // mark them as done and return, and hope that assembly can fill the holes
                     giveUp = true;
@@ -395,14 +374,13 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
                 return NULL;
             }
         }
-        SortableTop* sortableTop = sortableTops.append();
-        sortableTop->fSegment = current;
-        sortableTop->fIndex = *indexPtr;
-        sortableTop->fEndIndex = *endIndexPtr;
+        SortableTop2* sortableTop = sortableTops.append();
+        sortableTop->fStart = *startPtr;
+        sortableTop->fEnd = *endPtr;
 #if DEBUG_SORT
         SkDebugf("%s current=%d index=%d endIndex=%d tHit=%1.9g hitDx=%1.9g try=%d vert=%d\n",
-                __FUNCTION__, current->debugID(), *indexPtr, *endIndexPtr, tHit, hitDx, tryAgain,
-                *onlyVertical);
+                __FUNCTION__, current->debugID(), (*startPtr)->debugID(), (*endPtr)->debugID(),
+                tHit, hitDx, tryAgain, *onlyVertical);
 #endif
         if (*onlyVertical) {
             return current;
@@ -413,127 +391,35 @@ SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
         if (angleIncludeType < SkOpAngle::kBinarySingle) {
             break;
         }
-        oppContourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
+        oppContourWinding = rightAngleWinding(contourList, &current, startPtr, endPtr, &tHit,
                 &hitOppDx, &tryAgain, NULL, true);
+        SkASSERT(current == (*startPtr)->segment());
     } while (tryAgain);
-    bool success = current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx,
+    bool success = current->initWinding(*startPtr, *endPtr, tHit, contourWinding, hitDx,
             oppContourWinding, hitOppDx);
     if (current->done()) {
         return NULL;
     } else if (!success) {  // check if the span has a valid winding
-        int min = SkTMin(*indexPtr, *endIndexPtr);
-        const SkOpSpan& span = current->span(min);
-        if (span.fWindSum == SK_MinS32) {
+        SkOpSpan* minSpan = (*startPtr)->t() < (*endPtr)->t() ? (*startPtr)->upCast()
+            : (*endPtr)->upCast();
+        if (minSpan->windSum() == SK_MinS32) {
             return NULL;
         }
     }
     return current;
 }
 
-static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        if (!contour->calcAngles()) {
-            return false;
-        }
-    }
-    return true;
-}
-
-static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        contour->checkDuplicates();
-    }
-}
-
-static bool checkEnds(SkTArray<SkOpContour*, true>* contourList) {
-    // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
-    // instead, look to see if the connecting curve intersected at that same end.
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        if (!contour->checkEnds()) {
-            return false;
-        }
-    }
-    return true;
-}
-
-static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) {
-    bool hasMultiples = false;
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        contour->checkMultiples();
-        hasMultiples |= contour->hasMultiples();
-    }
-    return hasMultiples;
-}
-
-// A small interval of a pair of curves may collapse to lines for each, triggering coincidence
-static void checkSmall(SkTArray<SkOpContour*, true>* contourList) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        contour->checkSmall();
-    }
-}
-
-// A tiny interval may indicate an undiscovered coincidence. Find and fix.
-static void checkTiny(SkTArray<SkOpContour*, true>* contourList) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        contour->checkTiny();
-    }
-}
-
-static void fixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        contour->fixOtherTIndex();
-    }
-}
-
-static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        contour->joinCoincidence();
-    }
-}
-
-static void sortAngles(SkTArray<SkOpContour*, true>* contourList) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        contour->sortAngles();
-    }
-}
-
-static void sortSegments(SkTArray<SkOpContour*, true>* contourList) {
-    int contourCount = (*contourList).count();
-    for (int cTest = 0; cTest < contourCount; ++cTest) {
-        SkOpContour* contour = (*contourList)[cTest];
-        contour->sortSegments();
-    }
-}
-
-void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list,
+void MakeContourList(SkOpContour* contour, SkTDArray<SkOpContour* >& list,
                      bool evenOdd, bool oppEvenOdd) {
-    int count = contours.count();
-    if (count == 0) {
+    do {
+        if (contour->count()) {
+            contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
+            *list.append() = contour;
+        }
+    } while ((contour = contour->next()));
+    if (list.count() < 2) {
         return;
     }
-    for (int index = 0; index < count; ++index) {
-        SkOpContour& contour = contours[index];
-        contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd);
-        list.push_back(&contour);
-    }
     SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
 }
 
@@ -554,19 +440,22 @@ public:
         reassemble contour pieces into new path
     */
 void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
+    SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
+    SkOpContour contour;
+    SkOpGlobalState globalState(NULL  PATH_OPS_DEBUG_PARAMS(&contour));
 #if DEBUG_PATH_CONSTRUCTION
     SkDebugf("%s\n", __FUNCTION__);
 #endif
-    SkTArray<SkOpContour> contours;
-    SkOpEdgeBuilder builder(path, contours);
-    builder.finish();
-    int count = contours.count();
-    int outer;
-    SkTArray<int, true> runs(count);  // indices of partial contours
-    for (outer = 0; outer < count; ++outer) {
-        const SkOpContour& eContour = contours[outer];
-        const SkPoint& eStart = eContour.start();
-        const SkPoint& eEnd = eContour.end();
+    SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState);
+    builder.finish(&allocator);
+    SkTDArray<const SkOpContour* > runs;  // indices of partial contours
+    const SkOpContour* eContour = builder.head();
+    do {
+        if (!eContour->count()) {
+            continue;
+        }
+        const SkPoint& eStart = eContour->start();
+        const SkPoint& eEnd = eContour->end();
 #if DEBUG_ASSEMBLE
         SkDebugf("%s contour", __FUNCTION__);
         if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
@@ -578,44 +467,42 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
                 eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
 #endif
         if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
-            eContour.toPath(simple);
+            eContour->toPath(simple);
             continue;
         }
-        runs.push_back(outer);
-    }
-    count = runs.count();
+        *runs.append() = eContour;
+    } while ((eContour = eContour->next()));
+    int count = runs.count();
     if (count == 0) {
         return;
     }
-    SkTArray<int, true> sLink, eLink;
-    sLink.push_back_n(count);
-    eLink.push_back_n(count);
+    SkTDArray<int> sLink, eLink;
+    sLink.append(count);
+    eLink.append(count);
     int rIndex, iIndex;
     for (rIndex = 0; rIndex < count; ++rIndex) {
         sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
     }
     const int ends = count * 2;  // all starts and ends
     const int entries = (ends - 1) * count;  // folded triangle : n * (n - 1) / 2
-    SkTArray<double, true> distances;
-    distances.push_back_n(entries);
+    SkTDArray<double> distances;
+    distances.append(entries);
     for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
-        outer = runs[rIndex >> 1];
-        const SkOpContour& oContour = contours[outer];
-        const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start();
+        const SkOpContour* oContour = runs[rIndex >> 1];
+        const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start();
         const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
                 * ends - rIndex - 1;
         for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
-            int inner = runs[iIndex >> 1];
-            const SkOpContour& iContour = contours[inner];
-            const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start();
+            const SkOpContour* iContour = runs[iIndex >> 1];
+            const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start();
             double dx = iPt.fX - oPt.fX;
             double dy = iPt.fY - oPt.fY;
             double dist = dx * dx + dy * dy;
             distances[row + iIndex] = dist;  // oStart distance from iStart
         }
     }
-    SkTArray<int, true> sortedDist;
-    sortedDist.push_back_n(entries);
+    SkTDArray<int> sortedDist;
+    sortedDist.append(entries);
     for (rIndex = 0; rIndex < entries; ++rIndex) {
         sortedDist[rIndex] = rIndex;
     }
@@ -678,17 +565,16 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
                     eIndex < 0 ? ~eIndex : eIndex);
 #endif
         do {
-            outer = runs[rIndex];
-            const SkOpContour& contour = contours[outer];
+            const SkOpContour* contour = runs[rIndex];
             if (first) {
                 first = false;
-                const SkPoint* startPtr = &contour.start();
+                const SkPoint* startPtr = &contour->start();
                 simple->deferredMove(startPtr[0]);
             }
             if (forward) {
-                contour.toPartialForward(simple);
+                contour->toPartialForward(simple);
             } else {
-                contour.toPartialBackward(simple);
+                contour->toPartialBackward(simple);
             }
 #if DEBUG_ASSEMBLE
             SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
@@ -742,36 +628,88 @@ void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
 #endif
 }
 
-bool HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
-#if DEBUG_SHOW_WINDING
-    SkOpContour::debugShowWindingValues(contourList);
-#endif
-    if (!CoincidenceCheck(contourList, total)) {
+static void align(SkTDArray<SkOpContour* >* contourList) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->align();
+    }
+}
+
+static void calcAngles(SkTDArray<SkOpContour* >* contourList, SkChunkAlloc* allocator) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->calcAngles(allocator);
+    }
+}
+
+static void missingCoincidence(SkTDArray<SkOpContour* >* contourList,
+        SkOpCoincidence* coincidence, SkChunkAlloc* allocator) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->missingCoincidence(coincidence, allocator);
+    }
+}
+
+static bool moveNearby(SkTDArray<SkOpContour* >* contourList) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        if (!contour->moveNearby()) {
+            return false;
+        }
+    }
+    return true;
+}
+
+static void sortAngles(SkTDArray<SkOpContour* >* contourList) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->sortAngles();
+    }
+}
+
+static void sortSegments(SkTDArray<SkOpContour* >* contourList) {
+    int contourCount = (*contourList).count();
+    for (int cTest = 0; cTest < contourCount; ++cTest) {
+        SkOpContour* contour = (*contourList)[cTest];
+        contour->sortSegments();
+    }
+}
+
+bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* coincidence,
+        SkChunkAlloc* allocator, SkOpGlobalState* globalState) {
+    // move t values and points together to eliminate small/tiny gaps
+    if (!moveNearby(contourList)) {
         return false;
     }
-#if DEBUG_SHOW_WINDING
-    SkOpContour::debugShowWindingValues(contourList);
+    align(contourList);  // give all span members common values
+#if DEBUG_VALIDATE
+    globalState->setPhase(SkOpGlobalState::kIntersecting);
+#endif
+    coincidence->addMissing(allocator);
+#if DEBUG_VALIDATE
+    globalState->setPhase(SkOpGlobalState::kWalking);
 #endif
-    fixOtherTIndex(contourList);
-    if (!checkEnds(contourList)) {  // check if connecting curve intersected at the same end
+    coincidence->expand();  // check to see if, loosely, coincident ranges may be expanded
+    coincidence->mark();  // mark spans of coincident segments as coincident
+    missingCoincidence(contourList, coincidence, allocator);  // look for coincidence missed earlier
+    if (!coincidence->apply()) {  // adjust the winding value to account for coincident edges
         return false;
     }
-    bool hasM = checkMultiples(contourList);  // check if intersections agree on t and point values
-    SkTDArray<SkOpSegment::AlignedSpan> aligned;
-    if (hasM) {
-        alignMultiples(contourList, &aligned);  // align pairs of identical points
-        alignCoincidence(contourList, aligned);
-    }
-    checkDuplicates(contourList);  // check if spans have the same number on the other end
-    checkTiny(contourList);  // if pair have the same end points, mark them as parallel
-    checkSmall(contourList);  // a pair of curves with a small span may turn into coincident lines
-    joinCoincidence(contourList);  // join curves that connect to a coincident pair
     sortSegments(contourList);
-    if (!calcAngles(contourList)) {
-        return false;
-    }
+    calcAngles(contourList, allocator);
     sortAngles(contourList);
-#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
+    if (globalState->angleCoincidence()) {
+        missingCoincidence(contourList, coincidence, allocator);
+        if (!coincidence->apply()) {
+            return false;
+        }
+    }
+#if DEBUG_ACTIVE_SPANS
     DebugShowActiveSpans(*contourList);
 #endif
     return true;