1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkPathOpsCommon.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,632 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +#include "SkAddIntersections.h"
1.11 +#include "SkOpEdgeBuilder.h"
1.12 +#include "SkPathOpsCommon.h"
1.13 +#include "SkPathWriter.h"
1.14 +#include "SkTSort.h"
1.15 +
1.16 +static int contourRangeCheckY(const SkTArray<SkOpContour*, true>& contourList, SkOpSegment** currentPtr,
1.17 + int* indexPtr, int* endIndexPtr, double* bestHit, SkScalar* bestDx,
1.18 + bool* tryAgain, double* midPtr, bool opp) {
1.19 + const int index = *indexPtr;
1.20 + const int endIndex = *endIndexPtr;
1.21 + const double mid = *midPtr;
1.22 + const SkOpSegment* current = *currentPtr;
1.23 + double tAtMid = current->tAtMid(index, endIndex, mid);
1.24 + SkPoint basePt = current->ptAtT(tAtMid);
1.25 + int contourCount = contourList.count();
1.26 + SkScalar bestY = SK_ScalarMin;
1.27 + SkOpSegment* bestSeg = NULL;
1.28 + int bestTIndex = 0;
1.29 + bool bestOpp;
1.30 + bool hitSomething = false;
1.31 + for (int cTest = 0; cTest < contourCount; ++cTest) {
1.32 + SkOpContour* contour = contourList[cTest];
1.33 + bool testOpp = contour->operand() ^ current->operand() ^ opp;
1.34 + if (basePt.fY < contour->bounds().fTop) {
1.35 + continue;
1.36 + }
1.37 + if (bestY > contour->bounds().fBottom) {
1.38 + continue;
1.39 + }
1.40 + int segmentCount = contour->segments().count();
1.41 + for (int test = 0; test < segmentCount; ++test) {
1.42 + SkOpSegment* testSeg = &contour->segments()[test];
1.43 + SkScalar testY = bestY;
1.44 + double testHit;
1.45 + int testTIndex = testSeg->crossedSpanY(basePt, &testY, &testHit, &hitSomething, tAtMid,
1.46 + testOpp, testSeg == current);
1.47 + if (testTIndex < 0) {
1.48 + if (testTIndex == SK_MinS32) {
1.49 + hitSomething = true;
1.50 + bestSeg = NULL;
1.51 + goto abortContours; // vertical encountered, return and try different point
1.52 + }
1.53 + continue;
1.54 + }
1.55 + if (testSeg == current && current->betweenTs(index, testHit, endIndex)) {
1.56 + double baseT = current->t(index);
1.57 + double endT = current->t(endIndex);
1.58 + double newMid = (testHit - baseT) / (endT - baseT);
1.59 +#if DEBUG_WINDING
1.60 + double midT = current->tAtMid(index, endIndex, mid);
1.61 + SkPoint midXY = current->xyAtT(midT);
1.62 + double newMidT = current->tAtMid(index, endIndex, newMid);
1.63 + SkPoint newXY = current->xyAtT(newMidT);
1.64 + SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)"
1.65 + " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__,
1.66 + current->debugID(), mid, newMid,
1.67 + baseT, current->xAtT(index), current->yAtT(index),
1.68 + baseT + mid * (endT - baseT), midXY.fX, midXY.fY,
1.69 + baseT + newMid * (endT - baseT), newXY.fX, newXY.fY,
1.70 + endT, current->xAtT(endIndex), current->yAtT(endIndex));
1.71 +#endif
1.72 + *midPtr = newMid * 2; // calling loop with divide by 2 before continuing
1.73 + return SK_MinS32;
1.74 + }
1.75 + bestSeg = testSeg;
1.76 + *bestHit = testHit;
1.77 + bestOpp = testOpp;
1.78 + bestTIndex = testTIndex;
1.79 + bestY = testY;
1.80 + }
1.81 + }
1.82 +abortContours:
1.83 + int result;
1.84 + if (!bestSeg) {
1.85 + result = hitSomething ? SK_MinS32 : 0;
1.86 + } else {
1.87 + if (bestSeg->windSum(bestTIndex) == SK_MinS32) {
1.88 + *currentPtr = bestSeg;
1.89 + *indexPtr = bestTIndex;
1.90 + *endIndexPtr = bestSeg->nextSpan(bestTIndex, 1);
1.91 + SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
1.92 + *tryAgain = true;
1.93 + return 0;
1.94 + }
1.95 + result = bestSeg->windingAtT(*bestHit, bestTIndex, bestOpp, bestDx);
1.96 + SkASSERT(result == SK_MinS32 || *bestDx);
1.97 + }
1.98 + double baseT = current->t(index);
1.99 + double endT = current->t(endIndex);
1.100 + *bestHit = baseT + mid * (endT - baseT);
1.101 + return result;
1.102 +}
1.103 +
1.104 +SkOpSegment* FindUndone(SkTArray<SkOpContour*, true>& contourList, int* start, int* end) {
1.105 + int contourCount = contourList.count();
1.106 + SkOpSegment* result;
1.107 + for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
1.108 + SkOpContour* contour = contourList[cIndex];
1.109 + result = contour->undoneSegment(start, end);
1.110 + if (result) {
1.111 + return result;
1.112 + }
1.113 + }
1.114 + return NULL;
1.115 +}
1.116 +
1.117 +SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) {
1.118 + while (chase.count()) {
1.119 + SkOpSpan* span;
1.120 + chase.pop(&span);
1.121 + const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex);
1.122 + SkOpSegment* segment = backPtr.fOther;
1.123 + tIndex = backPtr.fOtherIndex;
1.124 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1.125 + int done = 0;
1.126 + if (segment->activeAngle(tIndex, &done, &angles)) {
1.127 + SkOpAngle* last = angles.end() - 1;
1.128 + tIndex = last->start();
1.129 + endIndex = last->end();
1.130 + #if TRY_ROTATE
1.131 + *chase.insert(0) = span;
1.132 + #else
1.133 + *chase.append() = span;
1.134 + #endif
1.135 + return last->segment();
1.136 + }
1.137 + if (done == angles.count()) {
1.138 + continue;
1.139 + }
1.140 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1.141 + bool sortable = SkOpSegment::SortAngles(angles, &sorted,
1.142 + SkOpSegment::kMayBeUnordered_SortAngleKind);
1.143 + int angleCount = sorted.count();
1.144 +#if DEBUG_SORT
1.145 + sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0, sortable);
1.146 +#endif
1.147 + if (!sortable) {
1.148 + continue;
1.149 + }
1.150 + // find first angle, initialize winding to computed fWindSum
1.151 + int firstIndex = -1;
1.152 + const SkOpAngle* angle;
1.153 + int winding;
1.154 + do {
1.155 + angle = sorted[++firstIndex];
1.156 + segment = angle->segment();
1.157 + winding = segment->windSum(angle);
1.158 + } while (winding == SK_MinS32);
1.159 + int spanWinding = segment->spanSign(angle->start(), angle->end());
1.160 + #if DEBUG_WINDING
1.161 + SkDebugf("%s winding=%d spanWinding=%d\n",
1.162 + __FUNCTION__, winding, spanWinding);
1.163 + #endif
1.164 + // turn span winding into contour winding
1.165 + if (spanWinding * winding < 0) {
1.166 + winding += spanWinding;
1.167 + }
1.168 + #if DEBUG_SORT
1.169 + segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0, sortable);
1.170 + #endif
1.171 + // we care about first sign and whether wind sum indicates this
1.172 + // edge is inside or outside. Maybe need to pass span winding
1.173 + // or first winding or something into this function?
1.174 + // advance to first undone angle, then return it and winding
1.175 + // (to set whether edges are active or not)
1.176 + int nextIndex = firstIndex + 1;
1.177 + int lastIndex = firstIndex != 0 ? firstIndex : angleCount;
1.178 + angle = sorted[firstIndex];
1.179 + winding -= angle->segment()->spanSign(angle);
1.180 + do {
1.181 + SkASSERT(nextIndex != firstIndex);
1.182 + if (nextIndex == angleCount) {
1.183 + nextIndex = 0;
1.184 + }
1.185 + angle = sorted[nextIndex];
1.186 + segment = angle->segment();
1.187 + int maxWinding = winding;
1.188 + winding -= segment->spanSign(angle);
1.189 + #if DEBUG_SORT
1.190 + SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__,
1.191 + segment->debugID(), maxWinding, winding, angle->sign());
1.192 + #endif
1.193 + tIndex = angle->start();
1.194 + endIndex = angle->end();
1.195 + int lesser = SkMin32(tIndex, endIndex);
1.196 + const SkOpSpan& nextSpan = segment->span(lesser);
1.197 + if (!nextSpan.fDone) {
1.198 + // FIXME: this be wrong? assign startWinding if edge is in
1.199 + // same direction. If the direction is opposite, winding to
1.200 + // assign is flipped sign or +/- 1?
1.201 + if (SkOpSegment::UseInnerWinding(maxWinding, winding)) {
1.202 + maxWinding = winding;
1.203 + }
1.204 + segment->markAndChaseWinding(angle, maxWinding, 0);
1.205 + break;
1.206 + }
1.207 + } while (++nextIndex != lastIndex);
1.208 + *chase.insert(0) = span;
1.209 + return segment;
1.210 + }
1.211 + return NULL;
1.212 +}
1.213 +
1.214 +#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
1.215 +void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) {
1.216 + int index;
1.217 + for (index = 0; index < contourList.count(); ++ index) {
1.218 + contourList[index]->debugShowActiveSpans();
1.219 + }
1.220 +}
1.221 +#endif
1.222 +
1.223 +static SkOpSegment* findSortableTop(const SkTArray<SkOpContour*, true>& contourList,
1.224 + int* index, int* endIndex, SkPoint* topLeft, bool* unsortable,
1.225 + bool* done, bool onlySortable) {
1.226 + SkOpSegment* result;
1.227 + do {
1.228 + SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax};
1.229 + int contourCount = contourList.count();
1.230 + SkOpSegment* topStart = NULL;
1.231 + *done = true;
1.232 + for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
1.233 + SkOpContour* contour = contourList[cIndex];
1.234 + if (contour->done()) {
1.235 + continue;
1.236 + }
1.237 + const SkPathOpsBounds& bounds = contour->bounds();
1.238 + if (bounds.fBottom < topLeft->fY) {
1.239 + *done = false;
1.240 + continue;
1.241 + }
1.242 + if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) {
1.243 + *done = false;
1.244 + continue;
1.245 + }
1.246 + contour->topSortableSegment(*topLeft, &bestXY, &topStart);
1.247 + if (!contour->done()) {
1.248 + *done = false;
1.249 + }
1.250 + }
1.251 + if (!topStart) {
1.252 + return NULL;
1.253 + }
1.254 + *topLeft = bestXY;
1.255 + result = topStart->findTop(index, endIndex, unsortable, onlySortable);
1.256 + } while (!result);
1.257 + if (result) {
1.258 + *unsortable = false;
1.259 + }
1.260 + return result;
1.261 +}
1.262 +
1.263 +static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList,
1.264 + SkOpSegment** current, int* index, int* endIndex, double* tHit,
1.265 + SkScalar* hitDx, bool* tryAgain, bool opp) {
1.266 + double test = 0.9;
1.267 + int contourWinding;
1.268 + do {
1.269 + contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx,
1.270 + tryAgain, &test, opp);
1.271 + if (contourWinding != SK_MinS32 || *tryAgain) {
1.272 + return contourWinding;
1.273 + }
1.274 + test /= 2;
1.275 + } while (!approximately_negative(test));
1.276 + SkASSERT(0); // should be OK to comment out, but interested when this hits
1.277 + return contourWinding;
1.278 +}
1.279 +
1.280 +static void skipVertical(const SkTArray<SkOpContour*, true>& contourList,
1.281 + SkOpSegment** current, int* index, int* endIndex) {
1.282 + if (!(*current)->isVertical(*index, *endIndex)) {
1.283 + return;
1.284 + }
1.285 + int contourCount = contourList.count();
1.286 + for (int cIndex = 0; cIndex < contourCount; ++cIndex) {
1.287 + SkOpContour* contour = contourList[cIndex];
1.288 + if (contour->done()) {
1.289 + continue;
1.290 + }
1.291 + *current = contour->nonVerticalSegment(index, endIndex);
1.292 + if (*current) {
1.293 + return;
1.294 + }
1.295 + }
1.296 +}
1.297 +
1.298 +SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList,
1.299 + SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr,
1.300 + int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done) {
1.301 + SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable,
1.302 + done, true);
1.303 + if (!current) {
1.304 + return NULL;
1.305 + }
1.306 + const int index = *indexPtr;
1.307 + const int endIndex = *endIndexPtr;
1.308 + if (*firstContour) {
1.309 + current->initWinding(index, endIndex);
1.310 + *firstContour = false;
1.311 + return current;
1.312 + }
1.313 + int minIndex = SkMin32(index, endIndex);
1.314 + int sumWinding = current->windSum(minIndex);
1.315 + if (sumWinding != SK_MinS32) {
1.316 + return current;
1.317 + }
1.318 + SkASSERT(current->windSum(SkMin32(index, endIndex)) == SK_MinS32);
1.319 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle, true> angles;
1.320 + SkSTArray<SkOpAngle::kStackBasedCount, SkOpAngle*, true> sorted;
1.321 + sumWinding = current->computeSum(index, endIndex, angleIncludeType, &angles, &sorted);
1.322 + if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) {
1.323 + return current;
1.324 + }
1.325 + int contourWinding;
1.326 + int oppContourWinding = 0;
1.327 + // the simple upward projection of the unresolved points hit unsortable angles
1.328 + // shoot rays at right angles to the segment to find its winding, ignoring angle cases
1.329 + bool tryAgain;
1.330 + double tHit;
1.331 + SkScalar hitDx = 0;
1.332 + SkScalar hitOppDx = 0;
1.333 + do {
1.334 + // if current is vertical, find another candidate which is not
1.335 + // if only remaining candidates are vertical, then they can be marked done
1.336 + SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
1.337 + skipVertical(contourList, ¤t, indexPtr, endIndexPtr);
1.338 +
1.339 + SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0);
1.340 + tryAgain = false;
1.341 + contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit,
1.342 + &hitDx, &tryAgain, false);
1.343 + if (tryAgain) {
1.344 + continue;
1.345 + }
1.346 + if (angleIncludeType < SkOpAngle::kBinarySingle) {
1.347 + break;
1.348 + }
1.349 + oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit,
1.350 + &hitOppDx, &tryAgain, true);
1.351 + } while (tryAgain);
1.352 + current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding,
1.353 + hitOppDx);
1.354 + return current;
1.355 +}
1.356 +
1.357 +static void checkEnds(SkTArray<SkOpContour*, true>* contourList) {
1.358 + // it's hard to determine if the end of a cubic or conic nearly intersects another curve.
1.359 + // instead, look to see if the connecting curve intersected at that same end.
1.360 + int contourCount = (*contourList).count();
1.361 + for (int cTest = 0; cTest < contourCount; ++cTest) {
1.362 + SkOpContour* contour = (*contourList)[cTest];
1.363 + contour->checkEnds();
1.364 + }
1.365 +}
1.366 +
1.367 +// A tiny interval may indicate an undiscovered coincidence. Find and fix.
1.368 +static void checkTiny(SkTArray<SkOpContour*, true>* contourList) {
1.369 + int contourCount = (*contourList).count();
1.370 + for (int cTest = 0; cTest < contourCount; ++cTest) {
1.371 + SkOpContour* contour = (*contourList)[cTest];
1.372 + contour->checkTiny();
1.373 + }
1.374 +}
1.375 +
1.376 +static void fixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) {
1.377 + int contourCount = (*contourList).count();
1.378 + for (int cTest = 0; cTest < contourCount; ++cTest) {
1.379 + SkOpContour* contour = (*contourList)[cTest];
1.380 + contour->fixOtherTIndex();
1.381 + }
1.382 +}
1.383 +
1.384 +static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) {
1.385 + int contourCount = (*contourList).count();
1.386 + for (int cTest = 0; cTest < contourCount; ++cTest) {
1.387 + SkOpContour* contour = (*contourList)[cTest];
1.388 + contour->joinCoincidence();
1.389 + }
1.390 +}
1.391 +
1.392 +static void sortSegments(SkTArray<SkOpContour*, true>* contourList) {
1.393 + int contourCount = (*contourList).count();
1.394 + for (int cTest = 0; cTest < contourCount; ++cTest) {
1.395 + SkOpContour* contour = (*contourList)[cTest];
1.396 + contour->sortSegments();
1.397 + }
1.398 +}
1.399 +
1.400 +void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list,
1.401 + bool evenOdd, bool oppEvenOdd) {
1.402 + int count = contours.count();
1.403 + if (count == 0) {
1.404 + return;
1.405 + }
1.406 + for (int index = 0; index < count; ++index) {
1.407 + SkOpContour& contour = contours[index];
1.408 + contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd);
1.409 + list.push_back(&contour);
1.410 + }
1.411 + SkTQSort<SkOpContour>(list.begin(), list.end() - 1);
1.412 +}
1.413 +
1.414 +class DistanceLessThan {
1.415 +public:
1.416 + DistanceLessThan(double* distances) : fDistances(distances) { }
1.417 + double* fDistances;
1.418 + bool operator()(const int one, const int two) {
1.419 + return fDistances[one] < fDistances[two];
1.420 + }
1.421 +};
1.422 +
1.423 + /*
1.424 + check start and end of each contour
1.425 + if not the same, record them
1.426 + match them up
1.427 + connect closest
1.428 + reassemble contour pieces into new path
1.429 + */
1.430 +void Assemble(const SkPathWriter& path, SkPathWriter* simple) {
1.431 +#if DEBUG_PATH_CONSTRUCTION
1.432 + SkDebugf("%s\n", __FUNCTION__);
1.433 +#endif
1.434 + SkTArray<SkOpContour> contours;
1.435 + SkOpEdgeBuilder builder(path, contours);
1.436 + builder.finish();
1.437 + int count = contours.count();
1.438 + int outer;
1.439 + SkTArray<int, true> runs(count); // indices of partial contours
1.440 + for (outer = 0; outer < count; ++outer) {
1.441 + const SkOpContour& eContour = contours[outer];
1.442 + const SkPoint& eStart = eContour.start();
1.443 + const SkPoint& eEnd = eContour.end();
1.444 +#if DEBUG_ASSEMBLE
1.445 + SkDebugf("%s contour", __FUNCTION__);
1.446 + if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
1.447 + SkDebugf("[%d]", runs.count());
1.448 + } else {
1.449 + SkDebugf(" ");
1.450 + }
1.451 + SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n",
1.452 + eStart.fX, eStart.fY, eEnd.fX, eEnd.fY);
1.453 +#endif
1.454 + if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) {
1.455 + eContour.toPath(simple);
1.456 + continue;
1.457 + }
1.458 + runs.push_back(outer);
1.459 + }
1.460 + count = runs.count();
1.461 + if (count == 0) {
1.462 + return;
1.463 + }
1.464 + SkTArray<int, true> sLink, eLink;
1.465 + sLink.push_back_n(count);
1.466 + eLink.push_back_n(count);
1.467 + int rIndex, iIndex;
1.468 + for (rIndex = 0; rIndex < count; ++rIndex) {
1.469 + sLink[rIndex] = eLink[rIndex] = SK_MaxS32;
1.470 + }
1.471 + const int ends = count * 2; // all starts and ends
1.472 + const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2
1.473 + SkTArray<double, true> distances;
1.474 + distances.push_back_n(entries);
1.475 + for (rIndex = 0; rIndex < ends - 1; ++rIndex) {
1.476 + outer = runs[rIndex >> 1];
1.477 + const SkOpContour& oContour = contours[outer];
1.478 + const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start();
1.479 + const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2)
1.480 + * ends - rIndex - 1;
1.481 + for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) {
1.482 + int inner = runs[iIndex >> 1];
1.483 + const SkOpContour& iContour = contours[inner];
1.484 + const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start();
1.485 + double dx = iPt.fX - oPt.fX;
1.486 + double dy = iPt.fY - oPt.fY;
1.487 + double dist = dx * dx + dy * dy;
1.488 + distances[row + iIndex] = dist; // oStart distance from iStart
1.489 + }
1.490 + }
1.491 + SkTArray<int, true> sortedDist;
1.492 + sortedDist.push_back_n(entries);
1.493 + for (rIndex = 0; rIndex < entries; ++rIndex) {
1.494 + sortedDist[rIndex] = rIndex;
1.495 + }
1.496 + SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin()));
1.497 + int remaining = count; // number of start/end pairs
1.498 + for (rIndex = 0; rIndex < entries; ++rIndex) {
1.499 + int pair = sortedDist[rIndex];
1.500 + int row = pair / ends;
1.501 + int col = pair - row * ends;
1.502 + int thingOne = row < col ? row : ends - row - 2;
1.503 + int ndxOne = thingOne >> 1;
1.504 + bool endOne = thingOne & 1;
1.505 + int* linkOne = endOne ? eLink.begin() : sLink.begin();
1.506 + if (linkOne[ndxOne] != SK_MaxS32) {
1.507 + continue;
1.508 + }
1.509 + int thingTwo = row < col ? col : ends - row + col - 1;
1.510 + int ndxTwo = thingTwo >> 1;
1.511 + bool endTwo = thingTwo & 1;
1.512 + int* linkTwo = endTwo ? eLink.begin() : sLink.begin();
1.513 + if (linkTwo[ndxTwo] != SK_MaxS32) {
1.514 + continue;
1.515 + }
1.516 + SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]);
1.517 + bool flip = endOne == endTwo;
1.518 + linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo;
1.519 + linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne;
1.520 + if (!--remaining) {
1.521 + break;
1.522 + }
1.523 + }
1.524 + SkASSERT(!remaining);
1.525 +#if DEBUG_ASSEMBLE
1.526 + for (rIndex = 0; rIndex < count; ++rIndex) {
1.527 + int s = sLink[rIndex];
1.528 + int e = eLink[rIndex];
1.529 + SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e',
1.530 + s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e);
1.531 + }
1.532 +#endif
1.533 + rIndex = 0;
1.534 + do {
1.535 + bool forward = true;
1.536 + bool first = true;
1.537 + int sIndex = sLink[rIndex];
1.538 + SkASSERT(sIndex != SK_MaxS32);
1.539 + sLink[rIndex] = SK_MaxS32;
1.540 + int eIndex;
1.541 + if (sIndex < 0) {
1.542 + eIndex = sLink[~sIndex];
1.543 + sLink[~sIndex] = SK_MaxS32;
1.544 + } else {
1.545 + eIndex = eLink[sIndex];
1.546 + eLink[sIndex] = SK_MaxS32;
1.547 + }
1.548 + SkASSERT(eIndex != SK_MaxS32);
1.549 +#if DEBUG_ASSEMBLE
1.550 + SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e',
1.551 + sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e',
1.552 + eIndex < 0 ? ~eIndex : eIndex);
1.553 +#endif
1.554 + do {
1.555 + outer = runs[rIndex];
1.556 + const SkOpContour& contour = contours[outer];
1.557 + if (first) {
1.558 + first = false;
1.559 + const SkPoint* startPtr = &contour.start();
1.560 + simple->deferredMove(startPtr[0]);
1.561 + }
1.562 + if (forward) {
1.563 + contour.toPartialForward(simple);
1.564 + } else {
1.565 + contour.toPartialBackward(simple);
1.566 + }
1.567 +#if DEBUG_ASSEMBLE
1.568 + SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex,
1.569 + eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex,
1.570 + sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex));
1.571 +#endif
1.572 + if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) {
1.573 + simple->close();
1.574 + break;
1.575 + }
1.576 + if (forward) {
1.577 + eIndex = eLink[rIndex];
1.578 + SkASSERT(eIndex != SK_MaxS32);
1.579 + eLink[rIndex] = SK_MaxS32;
1.580 + if (eIndex >= 0) {
1.581 + SkASSERT(sLink[eIndex] == rIndex);
1.582 + sLink[eIndex] = SK_MaxS32;
1.583 + } else {
1.584 + SkASSERT(eLink[~eIndex] == ~rIndex);
1.585 + eLink[~eIndex] = SK_MaxS32;
1.586 + }
1.587 + } else {
1.588 + eIndex = sLink[rIndex];
1.589 + SkASSERT(eIndex != SK_MaxS32);
1.590 + sLink[rIndex] = SK_MaxS32;
1.591 + if (eIndex >= 0) {
1.592 + SkASSERT(eLink[eIndex] == rIndex);
1.593 + eLink[eIndex] = SK_MaxS32;
1.594 + } else {
1.595 + SkASSERT(sLink[~eIndex] == ~rIndex);
1.596 + sLink[~eIndex] = SK_MaxS32;
1.597 + }
1.598 + }
1.599 + rIndex = eIndex;
1.600 + if (rIndex < 0) {
1.601 + forward ^= 1;
1.602 + rIndex = ~rIndex;
1.603 + }
1.604 + } while (true);
1.605 + for (rIndex = 0; rIndex < count; ++rIndex) {
1.606 + if (sLink[rIndex] != SK_MaxS32) {
1.607 + break;
1.608 + }
1.609 + }
1.610 + } while (rIndex < count);
1.611 +#if DEBUG_ASSEMBLE
1.612 + for (rIndex = 0; rIndex < count; ++rIndex) {
1.613 + SkASSERT(sLink[rIndex] == SK_MaxS32);
1.614 + SkASSERT(eLink[rIndex] == SK_MaxS32);
1.615 + }
1.616 +#endif
1.617 +}
1.618 +
1.619 +void HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) {
1.620 +#if DEBUG_SHOW_WINDING
1.621 + SkOpContour::debugShowWindingValues(contourList);
1.622 +#endif
1.623 + CoincidenceCheck(contourList, total);
1.624 +#if DEBUG_SHOW_WINDING
1.625 + SkOpContour::debugShowWindingValues(contourList);
1.626 +#endif
1.627 + fixOtherTIndex(contourList);
1.628 + checkEnds(contourList);
1.629 + checkTiny(contourList);
1.630 + joinCoincidence(contourList);
1.631 + sortSegments(contourList);
1.632 +#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY
1.633 + DebugShowActiveSpans(*contourList);
1.634 +#endif
1.635 +}
