path: root/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 "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;
    const double mid = *midPtr;
    const SkOpSegment* current = *currentPtr;
    double tAtMid = current->tAtMid(index, endIndex, mid);
    SkPoint basePt = current->ptAtT(tAtMid);
    int contourCount = contourList.count();
    SkScalar bestY = SK_ScalarMin;
    SkOpSegment* bestSeg = NULL;
    int bestTIndex = 0;
    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];
            SkScalar testY = bestY;
            double testHit;
            int testTIndex = testSeg->crossedSpanY(basePt, &testY, &testHit, &hitSomething, tAtMid,
                    testOpp, testSeg == current);
            if (testTIndex < 0) {
                if (testTIndex == SK_MinS32) {
                    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);
                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);
                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 + mid * (endT - baseT), midXY.fX, midXY.fY,
                        baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,
                        endT, current->xAtT(endIndex), current->yAtT(endIndex));
#endif
                *midPtr = newMid * 2;  // calling loop with divide by 2 before continuing
                return SK_MinS32;
            }
            bestSeg = testSeg;
            *bestHit = testHit;
            bestOpp = testOpp;
            bestTIndex = testTIndex;
            bestY = testY;
        }
    }
abortContours:
    int result;
    if (!bestSeg) {
        result = hitSomething ? SK_MinS32 : 0;
    } else {
        if (bestSeg->windSum(bestTIndex) == SK_MinS32) {
            *currentPtr = bestSeg;
            *indexPtr = bestTIndex;
            *endIndexPtr = bestSeg->nextSpan(bestTIndex, 1);
            SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
            *tryAgain = true;
            return 0;
        }
        result = bestSeg->windingAtT(*bestHit, bestTIndex, bestOpp, bestDx);
        SkASSERT(result == SK_MinS32 || *bestDx);
    }
    double baseT = current->t(index);
    double endT = current->t(endIndex);
    *bestHit = baseT + mid * (endT - baseT);
    return result;
}

SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end) {
    int contourCount = contourList.count();
    SkOpSegment* result;
    for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
        SkOpContour* contour = contourList[cIndex];
        result = contour->undoneSegment(start, end);
        if (result) {
            return result;
        }
    }
    return NULL;
}

SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex) {
    while (chase->count()) {
        SkOpSpan* span;
        chase->pop(&span);
        const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
        SkOpSegment* segment = backPtr.fOther;
        *tIndex = backPtr.fOtherIndex;
        bool sortable = true;
        bool done = true;
        *endIndex = -1;
        if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
                &sortable)) {
            *tIndex = last->start();
            *endIndex = 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;
        do {
            angle = angle->next();
            SkASSERT(angle != firstAngle || !loop);
            SkDEBUGCODE(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)
        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;
                }
                // allowed to do nothing
                (void) segment->markAndChaseWinding(angle, maxWinding, 0, NULL);
                break;
            }
        }
        *chase->insert(0) = span;
        return segment;
    }
    return NULL;
}

#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& 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) {
    SkOpSegment* result;
    const SkOpSegment* lastTopStart = NULL;
    int lastIndex = -1, lastEndIndex = -1;
    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);
        if (!result) {
            if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) {
                *done = true;
                return NULL;
            }
            lastTopStart = topStart;
            lastIndex = *index;
            lastEndIndex = *endIndex;
        }
    } while (!result);
    return result;
}

static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList,
        SkOpSegment** currentPtr, int* indexPtr, int* endIndexPtr, double* tHit,
        SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) {
    double test = 0.9;
    int contourWinding;
    do {
        contourWinding = contourRangeCheckY(contourList, currentPtr, indexPtr, endIndexPtr,
                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)) {
        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);
        if (nonVertical) {
            *current = nonVertical;
            return;
        }
    }
    return;
}

struct SortableTop {  // error if local in pre-C++11
    SkOpSegment* fSegment;
    int fIndex;
    int fEndIndex;
};

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);
    if (!current) {
        return NULL;
    }
    const int startIndex = *indexPtr;
    const int endIndex = *endIndexPtr;
    if (*firstContour) {
        current->initWinding(startIndex, endIndex, angleIncludeType);
        *firstContour = false;
        return current;
    }
    int minIndex = SkMin32(startIndex, endIndex);
    int sumWinding = current->windSum(minIndex);
    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);
            }
            sumWinding = current->computeSum(oIndex, index, angleIncludeType);
            SkTSwap(index, oIndex);
        } while (sumWinding == SK_MinS32 && index == startIndex);
    }
    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;
    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(current);  // FIXME: if null, all remaining are vertical
        SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
        tryAgain = false;
        contourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
                &hitDx, &tryAgain, onlyVertical, false);
        if (tryAgain) {
            bool giveUp = false;
            int count = sortableTops.count();
            for (int index = 0; index < count; ++index) {
                const SortableTop& prev = sortableTops[index];
                if (giveUp) {
                    prev.fSegment->markDoneFinal(prev.fIndex);
                } else if (prev.fSegment == current
                        && (prev.fIndex == *indexPtr || prev.fEndIndex == *endIndexPtr)) {
                    // 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;
#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);
#endif
        if (*onlyVertical) {
            return current;
        }
        if (tryAgain) {
            continue;
        }
        if (angleIncludeType < SkOpAngle::kBinarySingle) {
            break;
        }
        oppContourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
                &hitOppDx, &tryAgain, NULL, true);
    } while (tryAgain);
    bool success = current->initWinding(*indexPtr, *endIndexPtr, 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) {
            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,
                     bool evenOdd, bool oppEvenOdd) {
    int count = contours.count();
    if (count == 0) {
        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) {
#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();
#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);
            continue;
        }
        runs.push_back(outer);
    }
    count = runs.count();
    if (count == 0) {
        return;
    }
    SkTArray<int, true> sLink, eLink;
    sLink.push_back_n(count);
    eLink.push_back_n(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);
    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 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();
            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);
    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;
        int ndxOne = thingOne >> 1;
        bool endOne = thingOne & 1;
        int* linkOne = endOne ? eLink.begin() : sLink.begin();
        if (linkOne[ndxOne] != SK_MaxS32) {
            continue;
        }
        int thingTwo = row < col ? col : ends - row + col - 1;
        int ndxTwo = thingTwo >> 1;
        bool endTwo = thingTwo & 1;
        int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
        if (linkTwo[ndxTwo] != SK_MaxS32) {
            continue;
        }
        SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
        bool flip = endOne == endTwo;
        linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
        linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
        if (!--remaining) {
            break;
        }
    }
    SkASSERT(!remaining);
#if DEBUG_ASSEMBLE
    for (rIndex = 0; rIndex < count; ++rIndex) {
        int s = sLink[rIndex];
        int e = eLink[rIndex];
        SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
                s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
    }
#endif
    rIndex = 0;
    do {
        bool forward = true;
        bool first = true;
        int sIndex = sLink[rIndex];
        SkASSERT(sIndex != SK_MaxS32);
        sLink[rIndex] = SK_MaxS32;
        int eIndex;
        if (sIndex < 0) {
            eIndex = sLink[~sIndex];
            sLink[~sIndex] = SK_MaxS32;
        } else {
            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];
            if (first) {
                first = false;
                const SkPoint* startPtr = &contour.start();
                simple->deferredMove(startPtr[0]);
            }
            if (forward) {
                contour.toPartialForward(simple);
            } else {
                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;
            }
            if (forward) {
                eIndex = eLink[rIndex];
                SkASSERT(eIndex != SK_MaxS32);
                eLink[rIndex] = SK_MaxS32;
                if (eIndex >= 0) {
                    SkASSERT(sLink[eIndex] == rIndex);
                    sLink[eIndex] = SK_MaxS32;
                } else {
                    SkASSERT(eLink[~eIndex] == ~rIndex);
                    eLink[~eIndex] = SK_MaxS32;
                }
            } else {
                eIndex = sLink[rIndex];
                SkASSERT(eIndex != SK_MaxS32);
                sLink[rIndex] = SK_MaxS32;
                if (eIndex >= 0) {
                    SkASSERT(eLink[eIndex] == rIndex);
                    eLink[eIndex] = SK_MaxS32;
                } else {
                    SkASSERT(sLink[~eIndex] == ~rIndex);
                    sLink[~eIndex] = SK_MaxS32;
                }
            }
            rIndex = eIndex;
            if (rIndex < 0) {
                forward ^= 1;
                rIndex = ~rIndex;
            }
        } while (true);
        for (rIndex = 0; rIndex < count; ++rIndex) {
            if (sLink[rIndex] != SK_MaxS32) {
                break;
            }
        }
    } 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)) {
        return false;
    }
#if DEBUG_SHOW_WINDING
    SkOpContour::debugShowWindingValues(contourList);
#endif
    fixOtherTIndex(contourList);
    if (!checkEnds(contourList)) {  // check if connecting curve intersected at the same end
        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;
    }
    sortAngles(contourList);
#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
    DebugShowActiveSpans(*contourList);
#endif
    return true;
}