Home | History | Annotate | Download | only in pathops
      1 /*
      2  * Copyright 2012 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 #include "SkAddIntersections.h"
      8 #include "SkOpEdgeBuilder.h"
      9 #include "SkPathOpsCommon.h"
     10 #include "SkPathWriter.h"
     11 #include "SkTSort.h"
     12 
     13 static void alignMultiples(SkTArray<SkOpContour*, true>* contourList,
     14         SkTDArray<SkOpSegment::AlignedSpan>* aligned) {
     15     int contourCount = (*contourList).count();
     16     for (int cTest = 0; cTest < contourCount; ++cTest) {
     17         SkOpContour* contour = (*contourList)[cTest];
     18         if (contour->hasMultiples()) {
     19             contour->alignMultiples(aligned);
     20         }
     21     }
     22 }
     23 
     24 static void alignCoincidence(SkTArray<SkOpContour*, true>* contourList,
     25         const SkTDArray<SkOpSegment::AlignedSpan>& aligned) {
     26     int contourCount = (*contourList).count();
     27     for (int cTest = 0; cTest < contourCount; ++cTest) {
     28         SkOpContour* contour = (*contourList)[cTest];
     29         int count = aligned.count();
     30         for (int index = 0; index < count; ++index) {
     31             contour->alignCoincidence(aligned[index]);
     32         }
     33     }
     34 }
     35 
     36 static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, SkOpSegment** currentPtr,
     37                               int* indexPtr, int* endIndexPtr, double* bestHit, SkScalar* bestDx,
     38                               bool* tryAgain, double* midPtr, bool opp) {
     39     const int index = *indexPtr;
     40     const int endIndex = *endIndexPtr;
     41     const double mid = *midPtr;
     42     const SkOpSegment* current = *currentPtr;
     43     double tAtMid = current->tAtMid(index, endIndex, mid);
     44     SkPoint basePt = current->ptAtT(tAtMid);
     45     int contourCount = contourList.count();
     46     SkScalar bestY = SK_ScalarMin;
     47     SkOpSegment* bestSeg = NULL;
     48     int bestTIndex = 0;
     49     bool bestOpp;
     50     bool hitSomething = false;
     51     for (int cTest = 0; cTest < contourCount; ++cTest) {
     52         SkOpContour* contour = contourList[cTest];
     53         bool testOpp = contour->operand() ^ current->operand() ^ opp;
     54         if (basePt.fY < contour->bounds().fTop) {
     55             continue;
     56         }
     57         if (bestY > contour->bounds().fBottom) {
     58             continue;
     59         }
     60         int segmentCount = contour->segments().count();
     61         for (int test = 0; test < segmentCount; ++test) {
     62             SkOpSegment* testSeg = &contour->segments()[test];
     63             SkScalar testY = bestY;
     64             double testHit;
     65             int testTIndex = testSeg->crossedSpanY(basePt, &testY, &testHit, &hitSomething, tAtMid,
     66                     testOpp, testSeg == current);
     67             if (testTIndex < 0) {
     68                 if (testTIndex == SK_MinS32) {
     69                     hitSomething = true;
     70                     bestSeg = NULL;
     71                     goto abortContours;  // vertical encountered, return and try different point
     72                 }
     73                 continue;
     74             }
     75             if (testSeg == current && current->betweenTs(index, testHit, endIndex)) {
     76                 double baseT = current->t(index);
     77                 double endT = current->t(endIndex);
     78                 double newMid = (testHit - baseT) / (endT - baseT);
     79 #if DEBUG_WINDING
     80                 double midT = current->tAtMid(index, endIndex, mid);
     81                 SkPoint midXY = current->xyAtT(midT);
     82                 double newMidT = current->tAtMid(index, endIndex, newMid);
     83                 SkPoint newXY = current->xyAtT(newMidT);
     84                 SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)"
     85                         " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__,
     86                         current->debugID(), mid, newMid,
     87                         baseT, current->xAtT(index), current->yAtT(index),
     88                         baseT + mid * (endT - baseT), midXY.fX, midXY.fY,
     89                         baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,
     90                         endT, current->xAtT(endIndex), current->yAtT(endIndex));
     91 #endif
     92                 *midPtr = newMid * 2;  // calling loop with divide by 2 before continuing
     93                 return SK_MinS32;
     94             }
     95             bestSeg = testSeg;
     96             *bestHit = testHit;
     97             bestOpp = testOpp;
     98             bestTIndex = testTIndex;
     99             bestY = testY;
    100         }
    101     }
    102 abortContours:
    103     int result;
    104     if (!bestSeg) {
    105         result = hitSomething ? SK_MinS32 : 0;
    106     } else {
    107         if (bestSeg->windSum(bestTIndex) == SK_MinS32) {
    108             *currentPtr = bestSeg;
    109             *indexPtr = bestTIndex;
    110             *endIndexPtr = bestSeg->nextSpan(bestTIndex, 1);
    111             SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
    112             *tryAgain = true;
    113             return 0;
    114         }
    115         result = bestSeg->windingAtT(*bestHit, bestTIndex, bestOpp, bestDx);
    116         SkASSERT(result == SK_MinS32 || *bestDx);
    117     }
    118     double baseT = current->t(index);
    119     double endT = current->t(endIndex);
    120     *bestHit = baseT + mid * (endT - baseT);
    121     return result;
    122 }
    123 
    124 SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end) {
    125     int contourCount = contourList.count();
    126     SkOpSegment* result;
    127     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
    128         SkOpContour* contour = contourList[cIndex];
    129         result = contour->undoneSegment(start, end);
    130         if (result) {
    131             return result;
    132         }
    133     }
    134     return NULL;
    135 }
    136 
    137 SkOpSegment* FindChase(SkTDArray<SkOpSpan*>* chase, int* tIndex, int* endIndex) {
    138     while (chase->count()) {
    139         SkOpSpan* span;
    140         chase->pop(&span);
    141         const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
    142         SkOpSegment* segment = backPtr.fOther;
    143         *tIndex = backPtr.fOtherIndex;
    144         bool sortable = true;
    145         bool done = true;
    146         *endIndex = -1;
    147         if (const SkOpAngle* last = segment->activeAngle(*tIndex, tIndex, endIndex, &done,
    148                 &sortable)) {
    149             *tIndex = last->start();
    150             *endIndex = last->end();
    151     #if TRY_ROTATE
    152             *chase->insert(0) = span;
    153     #else
    154             *chase->append() = span;
    155     #endif
    156             return last->segment();
    157         }
    158         if (done) {
    159             continue;
    160         }
    161         if (!sortable) {
    162             continue;
    163         }
    164         // find first angle, initialize winding to computed fWindSum
    165         const SkOpAngle* angle = segment->spanToAngle(*tIndex, *endIndex);
    166         const SkOpAngle* firstAngle;
    167         SkDEBUGCODE(firstAngle = angle);
    168         SkDEBUGCODE(bool loop = false);
    169         int winding;
    170         do {
    171             angle = angle->next();
    172             SkASSERT(angle != firstAngle || !loop);
    173             SkDEBUGCODE(loop |= angle == firstAngle);
    174             segment = angle->segment();
    175             winding = segment->windSum(angle);
    176         } while (winding == SK_MinS32);
    177         int spanWinding = segment->spanSign(angle->start(), angle->end());
    178     #if DEBUG_WINDING
    179         SkDebugf("%s winding=%d spanWinding=%d\n", __FUNCTION__, winding, spanWinding);
    180     #endif
    181         // turn span winding into contour winding
    182         if (spanWinding * winding < 0) {
    183             winding += spanWinding;
    184         }
    185         // we care about first sign and whether wind sum indicates this
    186         // edge is inside or outside. Maybe need to pass span winding
    187         // or first winding or something into this function?
    188         // advance to first undone angle, then return it and winding
    189         // (to set whether edges are active or not)
    190         firstAngle = angle;
    191         winding -= firstAngle->segment()->spanSign(firstAngle);
    192         while ((angle = angle->next()) != firstAngle) {
    193             segment = angle->segment();
    194             int maxWinding = winding;
    195             winding -= segment->spanSign(angle);
    196     #if DEBUG_SORT
    197             SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
    198                     segment->debugID(), maxWinding, winding, angle->sign());
    199     #endif
    200             *tIndex = angle->start();
    201             *endIndex = angle->end();
    202             int lesser = SkMin32(*tIndex, *endIndex);
    203             const SkOpSpan& nextSpan = segment->span(lesser);
    204             if (!nextSpan.fDone) {
    205             // FIXME: this be wrong? assign startWinding if edge is in
    206             // same direction. If the direction is opposite, winding to
    207             // assign is flipped sign or +/- 1?
    208                 if (SkOpSegment::UseInnerWinding(maxWinding, winding)) {
    209                     maxWinding = winding;
    210                 }
    211                 (void) segment->markAndChaseWinding(angle, maxWinding, 0);
    212                 break;
    213             }
    214         }
    215         *chase->insert(0) = span;
    216         return segment;
    217     }
    218     return NULL;
    219 }
    220 
    221 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
    222 void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) {
    223     int index;
    224     for (index = 0; index < contourList.count(); ++ index) {
    225         contourList[index]->debugShowActiveSpans();
    226     }
    227 }
    228 #endif
    229 
    230 static SkOpSegment* findTopSegment(const SkTArray<SkOpContour*, true>& contourList, int* index,
    231         int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) {
    232     SkOpSegment* result;
    233     const SkOpSegment* lastTopStart = NULL;
    234     int lastIndex = -1, lastEndIndex = -1;
    235     do {
    236         SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
    237         int contourCount = contourList.count();
    238         SkOpSegment* topStart = NULL;
    239         *done = true;
    240         for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
    241             SkOpContour* contour = contourList[cIndex];
    242             if (contour->done()) {
    243                 continue;
    244             }
    245             const SkPathOpsBounds& bounds = contour->bounds();
    246             if (bounds.fBottom < topLeft->fY) {
    247                 *done = false;
    248                 continue;
    249             }
    250             if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) {
    251                 *done = false;
    252                 continue;
    253             }
    254             contour->topSortableSegment(*topLeft, &bestXY, &topStart);
    255             if (!contour->done()) {
    256                 *done = false;
    257             }
    258         }
    259         if (!topStart) {
    260             return NULL;
    261         }
    262         *topLeft = bestXY;
    263         result = topStart->findTop(index, endIndex, unsortable, firstPass);
    264         if (!result) {
    265             if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) {
    266                 *done = true;
    267                 return NULL;
    268             }
    269             lastTopStart = topStart;
    270             lastIndex = *index;
    271             lastEndIndex = *endIndex;
    272         }
    273     } while (!result);
    274     return result;
    275 }
    276 
    277 static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList,
    278         SkOpSegment** currentPtr, int* indexPtr, int* endIndexPtr, double* tHit,
    279         SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) {
    280     double test = 0.9;
    281     int contourWinding;
    282     do {
    283         contourWinding = contourRangeCheckY(contourList, currentPtr, indexPtr, endIndexPtr,
    284                 tHit, hitDx, tryAgain, &test, opp);
    285         if (contourWinding != SK_MinS32 || *tryAgain) {
    286             return contourWinding;
    287         }
    288         if (*currentPtr && (*currentPtr)->isVertical()) {
    289             *onlyVertical = true;
    290             return contourWinding;
    291         }
    292         test /= 2;
    293     } while (!approximately_negative(test));
    294     SkASSERT(0);  // FIXME: incomplete functionality
    295     return contourWinding;
    296 }
    297 
    298 static void skipVertical(const SkTArray<SkOpContour*, true>& contourList,
    299         SkOpSegment** current, int* index, int* endIndex) {
    300     if (!(*current)->isVertical(*index, *endIndex)) {
    301         return;
    302     }
    303     int contourCount = contourList.count();
    304     for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
    305         SkOpContour* contour = contourList[cIndex];
    306         if (contour->done()) {
    307             continue;
    308         }
    309         SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex);
    310         if (nonVertical) {
    311             *current = nonVertical;
    312             return;
    313         }
    314     }
    315     return;
    316 }
    317 
    318 SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
    319         SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
    320         int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical,
    321         bool firstPass) {
    322     SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
    323             done, firstPass);
    324     if (!current) {
    325         return NULL;
    326     }
    327     const int startIndex = *indexPtr;
    328     const int endIndex = *endIndexPtr;
    329     if (*firstContour) {
    330         current->initWinding(startIndex, endIndex, angleIncludeType);
    331         *firstContour = false;
    332         return current;
    333     }
    334     int minIndex = SkMin32(startIndex, endIndex);
    335     int sumWinding = current->windSum(minIndex);
    336     if (sumWinding == SK_MinS32) {
    337         int index = endIndex;
    338         int oIndex = startIndex;
    339         do {
    340             const SkOpSpan& span = current->span(index);
    341             if ((oIndex < index ? span.fFromAngle : span.fToAngle) == NULL) {
    342                 current->addSimpleAngle(index);
    343             }
    344             sumWinding = current->computeSum(oIndex, index, angleIncludeType);
    345             SkTSwap(index, oIndex);
    346         } while (sumWinding == SK_MinS32 && index == startIndex);
    347     }
    348     if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) {
    349         return current;
    350     }
    351     int contourWinding;
    352     int oppContourWinding = 0;
    353     // the simple upward projection of the unresolved points hit unsortable angles
    354     // shoot rays at right angles to the segment to find its winding, ignoring angle cases
    355     bool tryAgain;
    356     double tHit;
    357     SkScalar hitDx = 0;
    358     SkScalar hitOppDx = 0;
    359     do {
    360         // if current is vertical, find another candidate which is not
    361         // if only remaining candidates are vertical, then they can be marked done
    362         SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
    363         skipVertical(contourList, &current, indexPtr, endIndexPtr);
    364         SkASSERT(current);  // FIXME: if null, all remaining are vertical
    365         SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
    366         tryAgain = false;
    367         contourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
    368                 &hitDx, &tryAgain, onlyVertical, false);
    369         if (*onlyVertical) {
    370             return current;
    371         }
    372         if (tryAgain) {
    373             continue;
    374         }
    375         if (angleIncludeType < SkOpAngle::kBinarySingle) {
    376             break;
    377         }
    378         oppContourWinding = rightAngleWinding(contourList, &current, indexPtr, endIndexPtr, &tHit,
    379                 &hitOppDx, &tryAgain, NULL, true);
    380     } while (tryAgain);
    381     current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding,
    382             hitOppDx);
    383     if (current->done()) {
    384         return NULL;
    385     }
    386     return current;
    387 }
    388 
    389 static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) {
    390     int contourCount = (*contourList).count();
    391     for (int cTest = 0; cTest < contourCount; ++cTest) {
    392         SkOpContour* contour = (*contourList)[cTest];
    393         if (!contour->calcAngles()) {
    394             return false;
    395         }
    396     }
    397     return true;
    398 }
    399 
    400 static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) {
    401     int contourCount = (*contourList).count();
    402     for (int cTest = 0; cTest < contourCount; ++cTest) {
    403         SkOpContour* contour = (*contourList)[cTest];
    404         contour->checkDuplicates();
    405     }
    406 }
    407 
    408 static void checkEnds(SkTArray<SkOpContour*, true>* contourList) {
    409     // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
    410     // instead, look to see if the connecting curve intersected at that same end.
    411     int contourCount = (*contourList).count();
    412     for (int cTest = 0; cTest < contourCount; ++cTest) {
    413         SkOpContour* contour = (*contourList)[cTest];
    414         contour->checkEnds();
    415     }
    416 }
    417 
    418 static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) {
    419     bool hasMultiples = false;
    420     int contourCount = (*contourList).count();
    421     for (int cTest = 0; cTest < contourCount; ++cTest) {
    422         SkOpContour* contour = (*contourList)[cTest];
    423         contour->checkMultiples();
    424         hasMultiples |= contour->hasMultiples();
    425     }
    426     return hasMultiples;
    427 }
    428 
    429 // A small interval of a pair of curves may collapse to lines for each, triggering coincidence
    430 static void checkSmall(SkTArray<SkOpContour*, true>* contourList) {
    431     int contourCount = (*contourList).count();
    432     for (int cTest = 0; cTest < contourCount; ++cTest) {
    433         SkOpContour* contour = (*contourList)[cTest];
    434         contour->checkSmall();
    435     }
    436 }
    437 
    438 // A tiny interval may indicate an undiscovered coincidence. Find and fix.
    439 static void checkTiny(SkTArray<SkOpContour*, true>* contourList) {
    440     int contourCount = (*contourList).count();
    441     for (int cTest = 0; cTest < contourCount; ++cTest) {
    442         SkOpContour* contour = (*contourList)[cTest];
    443         contour->checkTiny();
    444     }
    445 }
    446 
    447 static void fixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
    448     int contourCount = (*contourList).count();
    449     for (int cTest = 0; cTest < contourCount; ++cTest) {
    450         SkOpContour* contour = (*contourList)[cTest];
    451         contour->fixOtherTIndex();
    452     }
    453 }
    454 
    455 static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) {
    456     int contourCount = (*contourList).count();
    457     for (int cTest = 0; cTest < contourCount; ++cTest) {
    458         SkOpContour* contour = (*contourList)[cTest];
    459         contour->joinCoincidence();
    460     }
    461 }
    462 
    463 static void sortAngles(SkTArray<SkOpContour*, true>* contourList) {
    464     int contourCount = (*contourList).count();
    465     for (int cTest = 0; cTest < contourCount; ++cTest) {
    466         SkOpContour* contour = (*contourList)[cTest];
    467         contour->sortAngles();
    468     }
    469 }
    470 
    471 static void sortSegments(SkTArray<SkOpContour*, true>* contourList) {
    472     int contourCount = (*contourList).count();
    473     for (int cTest = 0; cTest < contourCount; ++cTest) {
    474         SkOpContour* contour = (*contourList)[cTest];
    475         contour->sortSegments();
    476     }
    477 }
    478 
    479 void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list,
    480                      bool evenOdd, bool oppEvenOdd) {
    481     int count = contours.count();
    482     if (count == 0) {
    483         return;
    484     }
    485     for (int index = 0; index < count; ++index) {
    486         SkOpContour& contour = contours[index];
    487         contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd);
    488         list.push_back(&contour);
    489     }
    490     SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
    491 }
    492 
    493 class DistanceLessThan {
    494 public:
    495     DistanceLessThan(double* distances) : fDistances(distances) { }
    496     double* fDistances;
    497     bool operator()(const int one, const int two) {
    498         return fDistances[one] < fDistances[two];
    499     }
    500 };
    501 
    502     /*
    503         check start and end of each contour
    504         if not the same, record them
    505         match them up
    506         connect closest
    507         reassemble contour pieces into new path
    508     */
    509 void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
    510 #if DEBUG_PATH_CONSTRUCTION
    511     SkDebugf("%s\n", __FUNCTION__);
    512 #endif
    513     SkTArray<SkOpContour> contours;
    514     SkOpEdgeBuilder builder(path, contours);
    515     builder.finish();
    516     int count = contours.count();
    517     int outer;
    518     SkTArray<int, true> runs(count);  // indices of partial contours
    519     for (outer = 0; outer < count; ++outer) {
    520         const SkOpContour& eContour = contours[outer];
    521         const SkPoint& eStart = eContour.start();
    522         const SkPoint& eEnd = eContour.end();
    523 #if DEBUG_ASSEMBLE
    524         SkDebugf("%s contour", __FUNCTION__);
    525         if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
    526             SkDebugf("[%d]", runs.count());
    527         } else {
    528             SkDebugf("   ");
    529         }
    530         SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
    531                 eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
    532 #endif
    533         if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
    534             eContour.toPath(simple);
    535             continue;
    536         }
    537         runs.push_back(outer);
    538     }
    539     count = runs.count();
    540     if (count == 0) {
    541         return;
    542     }
    543     SkTArray<int, true> sLink, eLink;
    544     sLink.push_back_n(count);
    545     eLink.push_back_n(count);
    546     int rIndex, iIndex;
    547     for (rIndex = 0; rIndex < count; ++rIndex) {
    548         sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
    549     }
    550     const int ends = count * 2;  // all starts and ends
    551     const int entries = (ends - 1) * count;  // folded triangle : n * (n - 1) / 2
    552     SkTArray<double, true> distances;
    553     distances.push_back_n(entries);
    554     for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
    555         outer = runs[rIndex >> 1];
    556         const SkOpContour& oContour = contours[outer];
    557         const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start();
    558         const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
    559                 * ends - rIndex - 1;
    560         for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
    561             int inner = runs[iIndex >> 1];
    562             const SkOpContour& iContour = contours[inner];
    563             const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start();
    564             double dx = iPt.fX - oPt.fX;
    565             double dy = iPt.fY - oPt.fY;
    566             double dist = dx * dx + dy * dy;
    567             distances[row + iIndex] = dist;  // oStart distance from iStart
    568         }
    569     }
    570     SkTArray<int, true> sortedDist;
    571     sortedDist.push_back_n(entries);
    572     for (rIndex = 0; rIndex < entries; ++rIndex) {
    573         sortedDist[rIndex] = rIndex;
    574     }
    575     SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
    576     int remaining = count;  // number of start/end pairs
    577     for (rIndex = 0; rIndex < entries; ++rIndex) {
    578         int pair = sortedDist[rIndex];
    579         int row = pair / ends;
    580         int col = pair - row * ends;
    581         int thingOne = row < col ? row : ends - row - 2;
    582         int ndxOne = thingOne >> 1;
    583         bool endOne = thingOne & 1;
    584         int* linkOne = endOne ? eLink.begin() : sLink.begin();
    585         if (linkOne[ndxOne] != SK_MaxS32) {
    586             continue;
    587         }
    588         int thingTwo = row < col ? col : ends - row + col - 1;
    589         int ndxTwo = thingTwo >> 1;
    590         bool endTwo = thingTwo & 1;
    591         int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
    592         if (linkTwo[ndxTwo] != SK_MaxS32) {
    593             continue;
    594         }
    595         SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
    596         bool flip = endOne == endTwo;
    597         linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
    598         linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
    599         if (!--remaining) {
    600             break;
    601         }
    602     }
    603     SkASSERT(!remaining);
    604 #if DEBUG_ASSEMBLE
    605     for (rIndex = 0; rIndex < count; ++rIndex) {
    606         int s = sLink[rIndex];
    607         int e = eLink[rIndex];
    608         SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
    609                 s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
    610     }
    611 #endif
    612     rIndex = 0;
    613     do {
    614         bool forward = true;
    615         bool first = true;
    616         int sIndex = sLink[rIndex];
    617         SkASSERT(sIndex != SK_MaxS32);
    618         sLink[rIndex] = SK_MaxS32;
    619         int eIndex;
    620         if (sIndex < 0) {
    621             eIndex = sLink[~sIndex];
    622             sLink[~sIndex] = SK_MaxS32;
    623         } else {
    624             eIndex = eLink[sIndex];
    625             eLink[sIndex] = SK_MaxS32;
    626         }
    627         SkASSERT(eIndex != SK_MaxS32);
    628 #if DEBUG_ASSEMBLE
    629         SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
    630                     sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
    631                     eIndex < 0 ? ~eIndex : eIndex);
    632 #endif
    633         do {
    634             outer = runs[rIndex];
    635             const SkOpContour& contour = contours[outer];
    636             if (first) {
    637                 first = false;
    638                 const SkPoint* startPtr = &contour.start();
    639                 simple->deferredMove(startPtr[0]);
    640             }
    641             if (forward) {
    642                 contour.toPartialForward(simple);
    643             } else {
    644                 contour.toPartialBackward(simple);
    645             }
    646 #if DEBUG_ASSEMBLE
    647             SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
    648                 eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
    649                 sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
    650 #endif
    651             if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
    652                 simple->close();
    653                 break;
    654             }
    655             if (forward) {
    656                 eIndex = eLink[rIndex];
    657                 SkASSERT(eIndex != SK_MaxS32);
    658                 eLink[rIndex] = SK_MaxS32;
    659                 if (eIndex >= 0) {
    660                     SkASSERT(sLink[eIndex] == rIndex);
    661                     sLink[eIndex] = SK_MaxS32;
    662                 } else {
    663                     SkASSERT(eLink[~eIndex] == ~rIndex);
    664                     eLink[~eIndex] = SK_MaxS32;
    665                 }
    666             } else {
    667                 eIndex = sLink[rIndex];
    668                 SkASSERT(eIndex != SK_MaxS32);
    669                 sLink[rIndex] = SK_MaxS32;
    670                 if (eIndex >= 0) {
    671                     SkASSERT(eLink[eIndex] == rIndex);
    672                     eLink[eIndex] = SK_MaxS32;
    673                 } else {
    674                     SkASSERT(sLink[~eIndex] == ~rIndex);
    675                     sLink[~eIndex] = SK_MaxS32;
    676                 }
    677             }
    678             rIndex = eIndex;
    679             if (rIndex < 0) {
    680                 forward ^= 1;
    681                 rIndex = ~rIndex;
    682             }
    683         } while (true);
    684         for (rIndex = 0; rIndex < count; ++rIndex) {
    685             if (sLink[rIndex] != SK_MaxS32) {
    686                 break;
    687             }
    688         }
    689     } while (rIndex < count);
    690 #if DEBUG_ASSEMBLE
    691     for (rIndex = 0; rIndex < count; ++rIndex) {
    692        SkASSERT(sLink[rIndex] == SK_MaxS32);
    693        SkASSERT(eLink[rIndex] == SK_MaxS32);
    694     }
    695 #endif
    696 }
    697 
    698 bool HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
    699 #if DEBUG_SHOW_WINDING
    700     SkOpContour::debugShowWindingValues(contourList);
    701 #endif
    702     CoincidenceCheck(contourList, total);
    703 #if DEBUG_SHOW_WINDING
    704     SkOpContour::debugShowWindingValues(contourList);
    705 #endif
    706     fixOtherTIndex(contourList);
    707     checkEnds(contourList);  // check if connecting curve intersected at the same end
    708     bool hasM = checkMultiples(contourList);  // check if intersections agree on t and point values
    709     SkTDArray<SkOpSegment::AlignedSpan> aligned;
    710     if (hasM) {
    711         alignMultiples(contourList, &aligned);  // align pairs of identical points
    712         alignCoincidence(contourList, aligned);
    713     }
    714     checkDuplicates(contourList);  // check if spans have the same number on the other end
    715     checkTiny(contourList);  // if pair have the same end points, mark them as parallel
    716     checkSmall(contourList);  // a pair of curves with a small span may turn into coincident lines
    717     joinCoincidence(contourList);  // join curves that connect to a coincident pair
    718     sortSegments(contourList);
    719     if (!calcAngles(contourList)) {
    720         return false;
    721     }
    722     sortAngles(contourList);
    723 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
    724     DebugShowActiveSpans(*contourList);
    725 #endif
    726     return true;
    727 }
    728