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, ¤t, 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, ¤t, 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, ¤t, 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