src/third_party/skia/src/pathops/SkPathOpsCommon.cpp

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