caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 "SkOpEdgeBuilder.h" |
| 8 | #include "SkPathOpsCommon.h" |
| 9 | #include "SkPathWriter.h" |
| 10 | #include "TSearch.h" |
| 11 | |
| 12 | static int contourRangeCheckY(const SkTDArray<SkOpContour*>& contourList, SkOpSegment** currentPtr, |
| 13 | int* indexPtr, int* endIndexPtr, double* bestHit, SkScalar* bestDx, |
| 14 | bool* tryAgain, double* midPtr, bool opp) { |
| 15 | const int index = *indexPtr; |
| 16 | const int endIndex = *endIndexPtr; |
| 17 | const double mid = *midPtr; |
| 18 | const SkOpSegment* current = *currentPtr; |
| 19 | double tAtMid = current->tAtMid(index, endIndex, mid); |
| 20 | SkPoint basePt = current->xyAtT(tAtMid); |
| 21 | int contourCount = contourList.count(); |
| 22 | SkScalar bestY = SK_ScalarMin; |
| 23 | SkOpSegment* bestSeg = NULL; |
| 24 | int bestTIndex; |
| 25 | bool bestOpp; |
| 26 | bool hitSomething = false; |
| 27 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 28 | SkOpContour* contour = contourList[cTest]; |
| 29 | bool testOpp = contour->operand() ^ current->operand() ^ opp; |
| 30 | if (basePt.fY < contour->bounds().fTop) { |
| 31 | continue; |
| 32 | } |
| 33 | if (bestY > contour->bounds().fBottom) { |
| 34 | continue; |
| 35 | } |
| 36 | int segmentCount = contour->segments().count(); |
| 37 | for (int test = 0; test < segmentCount; ++test) { |
| 38 | SkOpSegment* testSeg = &contour->segments()[test]; |
| 39 | SkScalar testY = bestY; |
| 40 | double testHit; |
| 41 | int testTIndex = testSeg->crossedSpanY(basePt, &testY, &testHit, &hitSomething, tAtMid, |
| 42 | testOpp, testSeg == current); |
| 43 | if (testTIndex < 0) { |
| 44 | if (testTIndex == SK_MinS32) { |
| 45 | hitSomething = true; |
| 46 | bestSeg = NULL; |
| 47 | goto abortContours; // vertical encountered, return and try different point |
| 48 | } |
| 49 | continue; |
| 50 | } |
| 51 | if (testSeg == current && current->betweenTs(index, testHit, endIndex)) { |
| 52 | double baseT = current->t(index); |
| 53 | double endT = current->t(endIndex); |
| 54 | double newMid = (testHit - baseT) / (endT - baseT); |
| 55 | #if DEBUG_WINDING |
| 56 | double midT = current->tAtMid(index, endIndex, mid); |
| 57 | SkPoint midXY = current->xyAtT(midT); |
| 58 | double newMidT = current->tAtMid(index, endIndex, newMid); |
| 59 | SkPoint newXY = current->xyAtT(newMidT); |
| 60 | SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)" |
| 61 | " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__, |
| 62 | current->debugID(), mid, newMid, |
| 63 | baseT, current->xAtT(index), current->yAtT(index), |
| 64 | baseT + mid * (endT - baseT), midXY.fX, midXY.fY, |
| 65 | baseT + newMid * (endT - baseT), newXY.fX, newXY.fY, |
| 66 | endT, current->xAtT(endIndex), current->yAtT(endIndex)); |
| 67 | #endif |
| 68 | *midPtr = newMid * 2; // calling loop with divide by 2 before continuing |
| 69 | return SK_MinS32; |
| 70 | } |
| 71 | bestSeg = testSeg; |
| 72 | *bestHit = testHit; |
| 73 | bestOpp = testOpp; |
| 74 | bestTIndex = testTIndex; |
| 75 | bestY = testY; |
| 76 | } |
| 77 | } |
| 78 | abortContours: |
| 79 | int result; |
| 80 | if (!bestSeg) { |
| 81 | result = hitSomething ? SK_MinS32 : 0; |
| 82 | } else { |
| 83 | if (bestSeg->windSum(bestTIndex) == SK_MinS32) { |
| 84 | *currentPtr = bestSeg; |
| 85 | *indexPtr = bestTIndex; |
| 86 | *endIndexPtr = bestSeg->nextSpan(bestTIndex, 1); |
| 87 | SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0); |
| 88 | *tryAgain = true; |
| 89 | return 0; |
| 90 | } |
| 91 | result = bestSeg->windingAtT(*bestHit, bestTIndex, bestOpp, bestDx); |
caryclark@google.com | f11a5af | 2013-04-10 18:55:11 +0000 | [diff] [blame^] | 92 | SkASSERT(result == SK_MinS32 || *bestDx); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 93 | } |
| 94 | double baseT = current->t(index); |
| 95 | double endT = current->t(endIndex); |
| 96 | *bestHit = baseT + mid * (endT - baseT); |
| 97 | return result; |
| 98 | } |
| 99 | |
| 100 | SkOpSegment* FindUndone(SkTDArray<SkOpContour*>& contourList, int* start, int* end) { |
| 101 | int contourCount = contourList.count(); |
| 102 | SkOpSegment* result; |
| 103 | for (int cIndex = 0; cIndex < contourCount; ++cIndex) { |
| 104 | SkOpContour* contour = contourList[cIndex]; |
| 105 | result = contour->undoneSegment(start, end); |
| 106 | if (result) { |
| 107 | return result; |
| 108 | } |
| 109 | } |
| 110 | return NULL; |
| 111 | } |
| 112 | |
| 113 | SkOpSegment* FindChase(SkTDArray<SkOpSpan*>& chase, int& tIndex, int& endIndex) { |
| 114 | while (chase.count()) { |
| 115 | SkOpSpan* span; |
| 116 | chase.pop(&span); |
| 117 | const SkOpSpan& backPtr = span->fOther->span(span->fOtherIndex); |
| 118 | SkOpSegment* segment = backPtr.fOther; |
| 119 | tIndex = backPtr.fOtherIndex; |
| 120 | SkTDArray<SkOpAngle> angles; |
| 121 | int done = 0; |
| 122 | if (segment->activeAngle(tIndex, &done, &angles)) { |
| 123 | SkOpAngle* last = angles.end() - 1; |
| 124 | tIndex = last->start(); |
| 125 | endIndex = last->end(); |
| 126 | #if TRY_ROTATE |
| 127 | *chase.insert(0) = span; |
| 128 | #else |
| 129 | *chase.append() = span; |
| 130 | #endif |
| 131 | return last->segment(); |
| 132 | } |
| 133 | if (done == angles.count()) { |
| 134 | continue; |
| 135 | } |
| 136 | SkTDArray<SkOpAngle*> sorted; |
| 137 | bool sortable = SkOpSegment::SortAngles(angles, &sorted); |
| 138 | int angleCount = sorted.count(); |
| 139 | #if DEBUG_SORT |
| 140 | sorted[0]->segment()->debugShowSort(__FUNCTION__, sorted, 0, 0, 0); |
| 141 | #endif |
| 142 | if (!sortable) { |
| 143 | continue; |
| 144 | } |
| 145 | // find first angle, initialize winding to computed fWindSum |
| 146 | int firstIndex = -1; |
| 147 | const SkOpAngle* angle; |
| 148 | int winding; |
| 149 | do { |
| 150 | angle = sorted[++firstIndex]; |
| 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", |
| 157 | __FUNCTION__, winding, spanWinding); |
| 158 | #endif |
| 159 | // turn span winding into contour winding |
| 160 | if (spanWinding * winding < 0) { |
| 161 | winding += spanWinding; |
| 162 | } |
| 163 | #if DEBUG_SORT |
| 164 | segment->debugShowSort(__FUNCTION__, sorted, firstIndex, winding, 0); |
| 165 | #endif |
| 166 | // we care about first sign and whether wind sum indicates this |
| 167 | // edge is inside or outside. Maybe need to pass span winding |
| 168 | // or first winding or something into this function? |
| 169 | // advance to first undone angle, then return it and winding |
| 170 | // (to set whether edges are active or not) |
| 171 | int nextIndex = firstIndex + 1; |
| 172 | int lastIndex = firstIndex != 0 ? firstIndex : angleCount; |
| 173 | angle = sorted[firstIndex]; |
| 174 | winding -= angle->segment()->spanSign(angle); |
| 175 | do { |
| 176 | SkASSERT(nextIndex != firstIndex); |
| 177 | if (nextIndex == angleCount) { |
| 178 | nextIndex = 0; |
| 179 | } |
| 180 | angle = sorted[nextIndex]; |
| 181 | segment = angle->segment(); |
| 182 | int maxWinding = winding; |
| 183 | winding -= segment->spanSign(angle); |
| 184 | #if DEBUG_SORT |
| 185 | SkDebugf("%s id=%d maxWinding=%d winding=%d sign=%d\n", __FUNCTION__, |
| 186 | segment->debugID(), maxWinding, winding, angle->sign()); |
| 187 | #endif |
| 188 | tIndex = angle->start(); |
| 189 | endIndex = angle->end(); |
| 190 | int lesser = SkMin32(tIndex, endIndex); |
| 191 | const SkOpSpan& nextSpan = segment->span(lesser); |
| 192 | if (!nextSpan.fDone) { |
| 193 | // FIXME: this be wrong? assign startWinding if edge is in |
| 194 | // same direction. If the direction is opposite, winding to |
| 195 | // assign is flipped sign or +/- 1? |
| 196 | if (SkOpSegment::UseInnerWinding(maxWinding, winding)) { |
| 197 | maxWinding = winding; |
| 198 | } |
| 199 | segment->markAndChaseWinding(angle, maxWinding, 0); |
| 200 | break; |
| 201 | } |
| 202 | } while (++nextIndex != lastIndex); |
| 203 | *chase.insert(0) = span; |
| 204 | return segment; |
| 205 | } |
| 206 | return NULL; |
| 207 | } |
| 208 | |
| 209 | #if DEBUG_ACTIVE_SPANS |
| 210 | void DebugShowActiveSpans(SkTDArray<SkOpContour*>& contourList) { |
| 211 | int index; |
| 212 | for (index = 0; index < contourList.count(); ++ index) { |
| 213 | contourList[index]->debugShowActiveSpans(); |
| 214 | } |
| 215 | } |
| 216 | #endif |
| 217 | |
| 218 | static SkOpSegment* findSortableTop(const SkTDArray<SkOpContour*>& contourList, |
| 219 | int* index, int* endIndex, SkPoint* topLeft, bool* unsortable, |
| 220 | bool* done, bool onlySortable) { |
| 221 | SkOpSegment* result; |
| 222 | do { |
| 223 | SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; |
| 224 | int contourCount = contourList.count(); |
| 225 | SkOpSegment* topStart = NULL; |
| 226 | *done = true; |
| 227 | for (int cIndex = 0; cIndex < contourCount; ++cIndex) { |
| 228 | SkOpContour* contour = contourList[cIndex]; |
| 229 | if (contour->done()) { |
| 230 | continue; |
| 231 | } |
| 232 | const SkPathOpsBounds& bounds = contour->bounds(); |
| 233 | if (bounds.fBottom < topLeft->fY) { |
| 234 | *done = false; |
| 235 | continue; |
| 236 | } |
| 237 | if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) { |
| 238 | *done = false; |
| 239 | continue; |
| 240 | } |
| 241 | contour->topSortableSegment(*topLeft, &bestXY, &topStart); |
| 242 | if (!contour->done()) { |
| 243 | *done = false; |
| 244 | } |
| 245 | } |
| 246 | if (!topStart) { |
| 247 | return NULL; |
| 248 | } |
| 249 | *topLeft = bestXY; |
| 250 | result = topStart->findTop(index, endIndex, unsortable, onlySortable); |
| 251 | } while (!result); |
| 252 | return result; |
| 253 | } |
| 254 | |
| 255 | static int rightAngleWinding(const SkTDArray<SkOpContour*>& contourList, |
| 256 | SkOpSegment** current, int* index, int* endIndex, double* tHit, |
| 257 | SkScalar* hitDx, bool* tryAgain, bool opp) { |
| 258 | double test = 0.9; |
| 259 | int contourWinding; |
| 260 | do { |
| 261 | contourWinding = contourRangeCheckY(contourList, current, index, endIndex, tHit, hitDx, |
| 262 | tryAgain, &test, opp); |
| 263 | if (contourWinding != SK_MinS32 || *tryAgain) { |
| 264 | return contourWinding; |
| 265 | } |
| 266 | test /= 2; |
| 267 | } while (!approximately_negative(test)); |
| 268 | SkASSERT(0); // should be OK to comment out, but interested when this hits |
| 269 | return contourWinding; |
| 270 | } |
| 271 | |
| 272 | static void skipVertical(const SkTDArray<SkOpContour*>& contourList, |
| 273 | SkOpSegment** current, int* index, int* endIndex) { |
| 274 | if (!(*current)->isVertical(*index, *endIndex)) { |
| 275 | return; |
| 276 | } |
| 277 | int contourCount = contourList.count(); |
| 278 | for (int cIndex = 0; cIndex < contourCount; ++cIndex) { |
| 279 | SkOpContour* contour = contourList[cIndex]; |
| 280 | if (contour->done()) { |
| 281 | continue; |
| 282 | } |
| 283 | *current = contour->nonVerticalSegment(index, endIndex); |
| 284 | if (*current) { |
| 285 | return; |
| 286 | } |
| 287 | } |
| 288 | } |
| 289 | |
| 290 | SkOpSegment* FindSortableTop(const SkTDArray<SkOpContour*>& contourList, bool* firstContour, |
| 291 | int* indexPtr, int* endIndexPtr, SkPoint* topLeft, bool* unsortable, |
| 292 | bool* done, bool binary) { |
| 293 | SkOpSegment* current = findSortableTop(contourList, indexPtr, endIndexPtr, topLeft, unsortable, |
| 294 | done, true); |
| 295 | if (!current) { |
| 296 | return NULL; |
| 297 | } |
| 298 | const int index = *indexPtr; |
| 299 | const int endIndex = *endIndexPtr; |
| 300 | if (*firstContour) { |
| 301 | current->initWinding(index, endIndex); |
| 302 | *firstContour = false; |
| 303 | return current; |
| 304 | } |
| 305 | int minIndex = SkMin32(index, endIndex); |
| 306 | int sumWinding = current->windSum(minIndex); |
| 307 | if (sumWinding != SK_MinS32) { |
| 308 | return current; |
| 309 | } |
| 310 | sumWinding = current->computeSum(index, endIndex, binary); |
| 311 | if (sumWinding != SK_MinS32) { |
| 312 | return current; |
| 313 | } |
| 314 | int contourWinding; |
| 315 | int oppContourWinding = 0; |
| 316 | // the simple upward projection of the unresolved points hit unsortable angles |
| 317 | // shoot rays at right angles to the segment to find its winding, ignoring angle cases |
| 318 | bool tryAgain; |
| 319 | double tHit; |
| 320 | SkScalar hitDx = 0; |
| 321 | SkScalar hitOppDx = 0; |
| 322 | do { |
| 323 | // if current is vertical, find another candidate which is not |
| 324 | // if only remaining candidates are vertical, then they can be marked done |
| 325 | SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0); |
| 326 | skipVertical(contourList, ¤t, indexPtr, endIndexPtr); |
skia.committer@gmail.com | 3284017 | 2013-04-09 07:01:27 +0000 | [diff] [blame] | 327 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 328 | SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0); |
| 329 | tryAgain = false; |
| 330 | contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit, |
| 331 | &hitDx, &tryAgain, false); |
| 332 | if (tryAgain) { |
| 333 | continue; |
| 334 | } |
| 335 | if (!binary) { |
| 336 | break; |
| 337 | } |
| 338 | oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit, |
| 339 | &hitOppDx, &tryAgain, true); |
| 340 | } while (tryAgain); |
| 341 | current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, oppContourWinding, |
| 342 | hitOppDx); |
| 343 | return current; |
| 344 | } |
| 345 | |
| 346 | void FixOtherTIndex(SkTDArray<SkOpContour*>* contourList) { |
| 347 | int contourCount = (*contourList).count(); |
| 348 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 349 | SkOpContour* contour = (*contourList)[cTest]; |
| 350 | contour->fixOtherTIndex(); |
| 351 | } |
| 352 | } |
| 353 | |
| 354 | void SortSegments(SkTDArray<SkOpContour*>* contourList) { |
| 355 | int contourCount = (*contourList).count(); |
| 356 | for (int cTest = 0; cTest < contourCount; ++cTest) { |
| 357 | SkOpContour* contour = (*contourList)[cTest]; |
| 358 | contour->sortSegments(); |
| 359 | } |
| 360 | } |
| 361 | |
| 362 | void MakeContourList(SkTArray<SkOpContour>& contours, SkTDArray<SkOpContour*>& list, |
| 363 | bool evenOdd, bool oppEvenOdd) { |
| 364 | int count = contours.count(); |
| 365 | if (count == 0) { |
| 366 | return; |
| 367 | } |
| 368 | for (int index = 0; index < count; ++index) { |
| 369 | SkOpContour& contour = contours[index]; |
| 370 | contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd); |
| 371 | *list.append() = &contour; |
| 372 | } |
| 373 | QSort<SkOpContour>(list.begin(), list.end() - 1); |
| 374 | } |
| 375 | |
| 376 | static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) { |
| 377 | return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY); |
| 378 | } |
| 379 | |
| 380 | static bool lessThan(SkTDArray<double>& distances, const int one, const int two) { |
| 381 | return distances[one] < distances[two]; |
| 382 | } |
| 383 | /* |
| 384 | check start and end of each contour |
| 385 | if not the same, record them |
| 386 | match them up |
| 387 | connect closest |
| 388 | reassemble contour pieces into new path |
| 389 | */ |
| 390 | void Assemble(const SkPathWriter& path, SkPathWriter* simple) { |
| 391 | #if DEBUG_PATH_CONSTRUCTION |
| 392 | SkDebugf("%s\n", __FUNCTION__); |
| 393 | #endif |
| 394 | SkTArray<SkOpContour> contours; |
| 395 | SkOpEdgeBuilder builder(path, contours); |
| 396 | builder.finish(); |
| 397 | int count = contours.count(); |
| 398 | int outer; |
| 399 | SkTDArray<int> runs; // indices of partial contours |
| 400 | for (outer = 0; outer < count; ++outer) { |
| 401 | const SkOpContour& eContour = contours[outer]; |
| 402 | const SkPoint& eStart = eContour.start(); |
| 403 | const SkPoint& eEnd = eContour.end(); |
| 404 | #if DEBUG_ASSEMBLE |
| 405 | SkDebugf("%s contour", __FUNCTION__); |
| 406 | if (!approximatelyEqual(eStart, eEnd)) { |
| 407 | SkDebugf("[%d]", runs.count()); |
| 408 | } else { |
| 409 | SkDebugf(" "); |
| 410 | } |
| 411 | SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", |
| 412 | eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); |
| 413 | #endif |
| 414 | if (approximatelyEqual(eStart, eEnd)) { |
| 415 | eContour.toPath(simple); |
| 416 | continue; |
| 417 | } |
| 418 | *runs.append() = outer; |
| 419 | } |
| 420 | count = runs.count(); |
| 421 | if (count == 0) { |
| 422 | return; |
| 423 | } |
| 424 | SkTDArray<int> sLink, eLink; |
| 425 | sLink.setCount(count); |
| 426 | eLink.setCount(count); |
| 427 | int rIndex, iIndex; |
| 428 | for (rIndex = 0; rIndex < count; ++rIndex) { |
| 429 | sLink[rIndex] = eLink[rIndex] = SK_MaxS32; |
| 430 | } |
| 431 | SkTDArray<double> distances; |
| 432 | const int ends = count * 2; // all starts and ends |
| 433 | const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2 |
| 434 | distances.setCount(entries); |
| 435 | for (rIndex = 0; rIndex < ends - 1; ++rIndex) { |
| 436 | outer = runs[rIndex >> 1]; |
| 437 | const SkOpContour& oContour = contours[outer]; |
| 438 | const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start(); |
| 439 | const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2) |
| 440 | * ends - rIndex - 1; |
| 441 | for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) { |
| 442 | int inner = runs[iIndex >> 1]; |
| 443 | const SkOpContour& iContour = contours[inner]; |
| 444 | const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start(); |
| 445 | double dx = iPt.fX - oPt.fX; |
| 446 | double dy = iPt.fY - oPt.fY; |
| 447 | double dist = dx * dx + dy * dy; |
| 448 | distances[row + iIndex] = dist; // oStart distance from iStart |
| 449 | } |
| 450 | } |
| 451 | SkTDArray<int> sortedDist; |
| 452 | sortedDist.setCount(entries); |
| 453 | for (rIndex = 0; rIndex < entries; ++rIndex) { |
| 454 | sortedDist[rIndex] = rIndex; |
| 455 | } |
| 456 | QSort<SkTDArray<double>, int>(distances, sortedDist.begin(), sortedDist.end() - 1, lessThan); |
| 457 | int remaining = count; // number of start/end pairs |
| 458 | for (rIndex = 0; rIndex < entries; ++rIndex) { |
| 459 | int pair = sortedDist[rIndex]; |
| 460 | int row = pair / ends; |
| 461 | int col = pair - row * ends; |
| 462 | int thingOne = row < col ? row : ends - row - 2; |
| 463 | int ndxOne = thingOne >> 1; |
| 464 | bool endOne = thingOne & 1; |
| 465 | int* linkOne = endOne ? eLink.begin() : sLink.begin(); |
| 466 | if (linkOne[ndxOne] != SK_MaxS32) { |
| 467 | continue; |
| 468 | } |
| 469 | int thingTwo = row < col ? col : ends - row + col - 1; |
| 470 | int ndxTwo = thingTwo >> 1; |
| 471 | bool endTwo = thingTwo & 1; |
| 472 | int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); |
| 473 | if (linkTwo[ndxTwo] != SK_MaxS32) { |
| 474 | continue; |
| 475 | } |
| 476 | SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); |
| 477 | bool flip = endOne == endTwo; |
| 478 | linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; |
| 479 | linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; |
| 480 | if (!--remaining) { |
| 481 | break; |
| 482 | } |
| 483 | } |
| 484 | SkASSERT(!remaining); |
| 485 | #if DEBUG_ASSEMBLE |
| 486 | for (rIndex = 0; rIndex < count; ++rIndex) { |
| 487 | int s = sLink[rIndex]; |
| 488 | int e = eLink[rIndex]; |
| 489 | SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', |
| 490 | s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); |
| 491 | } |
| 492 | #endif |
| 493 | rIndex = 0; |
| 494 | do { |
| 495 | bool forward = true; |
| 496 | bool first = true; |
| 497 | int sIndex = sLink[rIndex]; |
| 498 | SkASSERT(sIndex != SK_MaxS32); |
| 499 | sLink[rIndex] = SK_MaxS32; |
| 500 | int eIndex; |
| 501 | if (sIndex < 0) { |
| 502 | eIndex = sLink[~sIndex]; |
| 503 | sLink[~sIndex] = SK_MaxS32; |
| 504 | } else { |
| 505 | eIndex = eLink[sIndex]; |
| 506 | eLink[sIndex] = SK_MaxS32; |
| 507 | } |
| 508 | SkASSERT(eIndex != SK_MaxS32); |
| 509 | #if DEBUG_ASSEMBLE |
| 510 | SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', |
| 511 | sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', |
| 512 | eIndex < 0 ? ~eIndex : eIndex); |
| 513 | #endif |
| 514 | do { |
| 515 | outer = runs[rIndex]; |
| 516 | const SkOpContour& contour = contours[outer]; |
| 517 | if (first) { |
| 518 | first = false; |
| 519 | const SkPoint* startPtr = &contour.start(); |
| 520 | simple->deferredMove(startPtr[0]); |
| 521 | } |
| 522 | if (forward) { |
| 523 | contour.toPartialForward(simple); |
| 524 | } else { |
| 525 | contour.toPartialBackward(simple); |
| 526 | } |
| 527 | #if DEBUG_ASSEMBLE |
| 528 | SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, |
| 529 | eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, |
| 530 | sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); |
| 531 | #endif |
| 532 | if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { |
| 533 | simple->close(); |
| 534 | break; |
| 535 | } |
| 536 | if (forward) { |
| 537 | eIndex = eLink[rIndex]; |
| 538 | SkASSERT(eIndex != SK_MaxS32); |
| 539 | eLink[rIndex] = SK_MaxS32; |
| 540 | if (eIndex >= 0) { |
| 541 | SkASSERT(sLink[eIndex] == rIndex); |
| 542 | sLink[eIndex] = SK_MaxS32; |
| 543 | } else { |
| 544 | SkASSERT(eLink[~eIndex] == ~rIndex); |
| 545 | eLink[~eIndex] = SK_MaxS32; |
| 546 | } |
| 547 | } else { |
| 548 | eIndex = sLink[rIndex]; |
| 549 | SkASSERT(eIndex != SK_MaxS32); |
| 550 | sLink[rIndex] = SK_MaxS32; |
| 551 | if (eIndex >= 0) { |
| 552 | SkASSERT(eLink[eIndex] == rIndex); |
| 553 | eLink[eIndex] = SK_MaxS32; |
| 554 | } else { |
| 555 | SkASSERT(sLink[~eIndex] == ~rIndex); |
| 556 | sLink[~eIndex] = SK_MaxS32; |
| 557 | } |
| 558 | } |
| 559 | rIndex = eIndex; |
| 560 | if (rIndex < 0) { |
| 561 | forward ^= 1; |
| 562 | rIndex = ~rIndex; |
| 563 | } |
| 564 | } while (true); |
| 565 | for (rIndex = 0; rIndex < count; ++rIndex) { |
| 566 | if (sLink[rIndex] != SK_MaxS32) { |
| 567 | break; |
| 568 | } |
| 569 | } |
| 570 | } while (rIndex < count); |
| 571 | #if DEBUG_ASSEMBLE |
| 572 | for (rIndex = 0; rIndex < count; ++rIndex) { |
| 573 | SkASSERT(sLink[rIndex] == SK_MaxS32); |
| 574 | SkASSERT(eLink[rIndex] == SK_MaxS32); |
| 575 | } |
| 576 | #endif |
| 577 | } |