pathops version two

src/pathops/SkPathOpsCommon.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * 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) {
         SkOpContour* contour = contourList[cTest];
         bool testOpp = contour->operand() ^ current->operand() ^ opp;
         if (basePt.fY < contour->bounds().fTop) {
             continue;
         }
         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;
             }
             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;
         }
     }
     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
             *chase->append() = span;
     #endif
             return last->segment();
         }
         if (done) {
             continue;
         }
         if (!sortable) {
             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;
+        if (winding == SK_MinS32) {
+            continue;
         }
-        // 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)
+        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();
     }
 }
 #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();
         SkOpSegment* topStart = NULL;
         *done = true;
         for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
             SkOpContour* contour = contourList[cIndex];
             if (contour->done()) {
                 continue;
             }
             const SkPathOpsBounds& bounds = contour->bounds();
             if (bounds.fBottom < topLeft->fY) {
                 *done = false;
                 continue;
             }
             if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) {
                 *done = false;
                 continue;
             }
             contour->topSortableSegment(*topLeft, &bestXY, &topStart);
             if (!contour->done()) {
                 *done = false;
             }
         }
         if (!topStart) {
             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;
         }
         if (*currentPtr && (*currentPtr)->isVertical()) {
             *onlyVertical = true;
             return contourWinding;
         }
         test /= 2;
     } while (!approximately_negative(test));
     SkASSERT(0);  // FIXME: incomplete functionality
     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();
     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
         SkOpContour* contour = contourList[cIndex];
         if (contour->done()) {
             continue;
         }
-        SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex);
+        SkOpSegment* nonVertical = contour->nonVerticalSegment(start, end);
         if (nonVertical) {
             *current = nonVertical;
             return;
         }
     }
     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;
     }
     int contourWinding;
     int oppContourWinding = 0;
     // the simple upward projection of the unresolved points hit unsortable angles
     // shoot rays at right angles to the segment to find its winding, ignoring angle cases
     bool tryAgain;
     double tHit;
     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;
                     index = -1;
                 }
             }
             if (giveUp) {
                 *done = true;
                 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;
         }
         if (tryAgain) {
             continue;
         }
         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;
+void MakeContourList(SkOpContour* contour, SkTDArray<SkOpContour* >& list,
+                     bool evenOdd, bool oppEvenOdd) {
+    do {
+        if (contour->count()) {
+            contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd);
+            *list.append() = contour;
         }
-    }
-    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,
-                     bool evenOdd, bool oppEvenOdd) {
-    int count = contours.count();
-    if (count == 0) {
+    } 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);
 }
 
 class DistanceLessThan {
 public:
     DistanceLessThan(double* distances) : fDistances(distances) { }
     double* fDistances;
     bool operator()(const int one, const int two) {
         return fDistances[one] < fDistances[two];
     }
 };
 
     /*
         check start and end of each contour
         if not the same, record them
         match them up
         connect closest
         reassemble contour pieces into new path
     */
 void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
+    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();
+    SkChunkAlloc allocator(4096);  // FIXME: constant-ize, tune
+    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)) {
             SkDebugf("[%d]", runs.count());
         } else {
             SkDebugf("   ");
         }
         SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
                 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;
     }
     SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
     int remaining = count;  // number of start/end pairs
     for (rIndex = 0; rIndex < entries; ++rIndex) {
         int pair = sortedDist[rIndex];
         int row = pair / ends;
         int col = pair - row * ends;
         int thingOne = row < col ? row : ends - row - 2;
@@ skipping 42 matching lines @@
             eIndex = eLink[sIndex];
             eLink[sIndex] = SK_MaxS32;
         }
         SkASSERT(eIndex != SK_MaxS32);
 #if DEBUG_ASSEMBLE
         SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
                     sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
                     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,
                 eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
                 sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
 #endif
             if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
                 simple->close();
                 break;
             }
@@ skipping 33 matching lines @@
         }
     } while (rIndex < count);
 #if DEBUG_ASSEMBLE
     for (rIndex = 0; rIndex < count; ++rIndex) {
        SkASSERT(sLink[rIndex] == SK_MaxS32);
        SkASSERT(eLink[rIndex] == SK_MaxS32);
     }
 #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
-    fixOtherTIndex(contourList);
-    if (!checkEnds(contourList)) {  // check if connecting curve intersected at the same end
+    coincidence->addMissing(allocator);
+#if DEBUG_VALIDATE
+    globalState->setPhase(SkOpGlobalState::kWalking);
+#endif
+    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);
+    sortSegments(contourList);
+    calcAngles(contourList, allocator);
+    sortAngles(contourList);
+    if (globalState->angleCoincidence()) {
+        missingCoincidence(contourList, coincidence, allocator);
+        if (!coincidence->apply()) {
+            return false;
+        }
     }
-    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;
-    }
-    sortAngles(contourList);
-#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
+#if DEBUG_ACTIVE_SPANS
     DebugShowActiveSpans(*contourList);
 #endif
     return true;
 }