SkPathOpsCommon.cpp revision 54359294a7c9dc54802d512a5d891a35c1663392
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 "SkOpCoincidence.h" 9#include "SkOpEdgeBuilder.h" 10#include "SkPathOpsCommon.h" 11#include "SkPathWriter.h" 12#include "SkTSort.h" 13 14static int contourRangeCheckY(const SkTDArray<SkOpContour* >& contourList, 15 SkOpSegment** currentPtr, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr, 16 double* bestHit, SkScalar* bestDx, bool* tryAgain, double* midPtr, bool opp) { 17 SkOpSpanBase* start = *startPtr; 18 SkOpSpanBase* end = *endPtr; 19 const double mid = *midPtr; 20 const SkOpSegment* current = *currentPtr; 21 double tAtMid = SkOpSegment::TAtMid(start, end, mid); 22 SkPoint basePt = current->ptAtT(tAtMid); 23 int contourCount = contourList.count(); 24 SkScalar bestY = SK_ScalarMin; 25 SkOpSegment* bestSeg = NULL; 26 SkOpSpan* bestTSpan = NULL; 27 bool bestOpp; 28 bool hitSomething = false; 29 for (int cTest = 0; cTest < contourCount; ++cTest) { 30 SkOpContour* contour = contourList[cTest]; 31 bool testOpp = contour->operand() ^ current->operand() ^ opp; 32 if (basePt.fY < contour->bounds().fTop) { 33 continue; 34 } 35 if (bestY > contour->bounds().fBottom) { 36 continue; 37 } 38 SkOpSegment* testSeg = contour->first(); 39 SkASSERT(testSeg); 40 do { 41 SkScalar testY = bestY; 42 double testHit; 43 bool vertical; 44 SkOpSpan* testTSpan = testSeg->crossedSpanY(basePt, tAtMid, testOpp, 45 testSeg == current, &testY, &testHit, &hitSomething, &vertical); 46 if (!testTSpan) { 47 if (vertical) { 48 hitSomething = true; 49 bestSeg = NULL; 50 goto abortContours; // vertical encountered, return and try different point 51 } 52 continue; 53 } 54 if (testSeg == current && SkOpSegment::BetweenTs(start, testHit, end)) { 55 double baseT = start->t(); 56 double endT = end->t(); 57 double newMid = (testHit - baseT) / (endT - baseT); 58#if DEBUG_WINDING 59 double midT = SkOpSegment::TAtMid(start, end, mid); 60 SkPoint midXY = current->ptAtT(midT); 61 double newMidT = SkOpSegment::TAtMid(start, end, newMid); 62 SkPoint newXY = current->ptAtT(newMidT); 63 SkDebugf("%s [%d] mid=%1.9g->%1.9g s=%1.9g (%1.9g,%1.9g) m=%1.9g (%1.9g,%1.9g)" 64 " n=%1.9g (%1.9g,%1.9g) e=%1.9g (%1.9g,%1.9g)\n", __FUNCTION__, 65 current->debugID(), mid, newMid, 66 baseT, start->pt().fX, start->pt().fY, 67 baseT + mid * (endT - baseT), midXY.fX, midXY.fY, 68 baseT + newMid * (endT - baseT), newXY.fX, newXY.fY, 69 endT, end->pt().fX, end->pt().fY); 70#endif 71 *midPtr = newMid * 2; // calling loop with divide by 2 before continuing 72 return SK_MinS32; 73 } 74 bestSeg = testSeg; 75 *bestHit = testHit; 76 bestOpp = testOpp; 77 bestTSpan = testTSpan; 78 bestY = testY; 79 } while ((testSeg = testSeg->next())); 80 } 81abortContours: 82 int result; 83 if (!bestSeg) { 84 result = hitSomething ? SK_MinS32 : 0; 85 } else { 86 if (bestTSpan->windSum() == SK_MinS32) { 87 *currentPtr = bestSeg; 88 *startPtr = bestTSpan; 89 *endPtr = bestTSpan->next(); 90 SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); 91 *tryAgain = true; 92 return 0; 93 } 94 result = bestSeg->windingAtT(*bestHit, bestTSpan, bestOpp, bestDx); 95 SkASSERT(result == SK_MinS32 || *bestDx); 96 } 97 double baseT = (*startPtr)->t(); 98 double endT = (*endPtr)->t(); 99 *bestHit = baseT + mid * (endT - baseT); 100 return result; 101} 102 103SkOpSegment* FindUndone(SkTDArray<SkOpContour* >& contourList, SkOpSpanBase** startPtr, 104 SkOpSpanBase** endPtr) { 105 int contourCount = contourList.count(); 106 SkOpSegment* result; 107 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 108 SkOpContour* contour = contourList[cIndex]; 109 result = contour->undoneSegment(startPtr, endPtr); 110 if (result) { 111 return result; 112 } 113 } 114 return NULL; 115} 116 117SkOpSegment* FindChase(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** startPtr, 118 SkOpSpanBase** endPtr) { 119 while (chase->count()) { 120 SkOpSpanBase* span; 121 chase->pop(&span); 122 SkOpSegment* segment = span->segment(); 123 *startPtr = span->ptT()->next()->span(); 124 bool sortable = true; 125 bool done = true; 126 *endPtr = NULL; 127 if (SkOpAngle* last = segment->activeAngle(*startPtr, startPtr, endPtr, &done, 128 &sortable)) { 129 if (last->unorderable()) { 130 continue; 131 } 132 *startPtr = last->start(); 133 *endPtr = last->end(); 134 #if TRY_ROTATE 135 *chase->insert(0) = span; 136 #else 137 *chase->append() = span; 138 #endif 139 return last->segment(); 140 } 141 if (done) { 142 continue; 143 } 144 if (!sortable) { 145 continue; 146 } 147 // find first angle, initialize winding to computed wind sum 148 const SkOpAngle* angle = segment->spanToAngle(*startPtr, *endPtr); 149 if (!angle) { 150 continue; 151 } 152 const SkOpAngle* firstAngle = angle; 153 bool loop = false; 154 int winding = SK_MinS32; 155 do { 156 angle = angle->next(); 157 if (angle == firstAngle && loop) { 158 break; // if we get here, there's no winding, loop is unorderable 159 } 160 loop |= angle == firstAngle; 161 segment = angle->segment(); 162 winding = segment->windSum(angle); 163 } while (winding == SK_MinS32); 164 if (winding == SK_MinS32) { 165 continue; 166 } 167 int sumWinding = segment->updateWindingReverse(angle); 168 SkOpSegment* first = NULL; 169 firstAngle = angle; 170 while ((angle = angle->next()) != firstAngle) { 171 segment = angle->segment(); 172 SkOpSpanBase* start = angle->start(); 173 SkOpSpanBase* end = angle->end(); 174 int maxWinding; 175 segment->setUpWinding(start, end, &maxWinding, &sumWinding); 176 if (!segment->done(angle)) { 177 if (!first) { 178 first = segment; 179 *startPtr = start; 180 *endPtr = end; 181 } 182 // OPTIMIZATION: should this also add to the chase? 183 (void) segment->markAngle(maxWinding, sumWinding, angle); 184 } 185 } 186 if (first) { 187 #if TRY_ROTATE 188 *chase->insert(0) = span; 189 #else 190 *chase->append() = span; 191 #endif 192 return first; 193 } 194 } 195 return NULL; 196} 197 198#if DEBUG_ACTIVE_SPANS 199void DebugShowActiveSpans(SkTDArray<SkOpContour* >& contourList) { 200 int index; 201 for (index = 0; index < contourList.count(); ++ index) { 202 contourList[index]->debugShowActiveSpans(); 203 } 204} 205#endif 206 207static SkOpSegment* findTopSegment(const SkTDArray<SkOpContour* >& contourList, 208 bool firstPass, SkOpSpanBase** start, SkOpSpanBase** end, SkPoint* topLeft, 209 bool* unsortable, bool* done, SkChunkAlloc* allocator) { 210 SkOpSegment* result; 211 const SkOpSegment* lastTopStart = NULL; 212 SkOpSpanBase* lastStart = NULL, * lastEnd = NULL; 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(firstPass, start, end, unsortable, allocator); 242 if (!result) { 243 if (lastTopStart == topStart && lastStart == *start && lastEnd == *end) { 244 *done = true; 245 return NULL; 246 } 247 lastTopStart = topStart; 248 lastStart = *start; 249 lastEnd = *end; 250 } 251 } while (!result); 252 return result; 253} 254 255static int rightAngleWinding(const SkTDArray<SkOpContour* >& contourList, 256 SkOpSegment** currentPtr, SkOpSpanBase** start, SkOpSpanBase** end, double* tHit, 257 SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) { 258 double test = 0.9; 259 int contourWinding; 260 do { 261 contourWinding = contourRangeCheckY(contourList, currentPtr, start, end, 262 tHit, hitDx, tryAgain, &test, opp); 263 if (contourWinding != SK_MinS32 || *tryAgain) { 264 return contourWinding; 265 } 266 if (*currentPtr && (*currentPtr)->isVertical()) { 267 *onlyVertical = true; 268 return contourWinding; 269 } 270 test /= 2; 271 } while (!approximately_negative(test)); 272 SkASSERT(0); // FIXME: incomplete functionality 273 return contourWinding; 274} 275 276static void skipVertical(const SkTDArray<SkOpContour* >& contourList, 277 SkOpSegment** current, SkOpSpanBase** start, SkOpSpanBase** end) { 278 if (!(*current)->isVertical(*start, *end)) { 279 return; 280 } 281 int contourCount = contourList.count(); 282 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 283 SkOpContour* contour = contourList[cIndex]; 284 if (contour->done()) { 285 continue; 286 } 287 SkOpSegment* nonVertical = contour->nonVerticalSegment(start, end); 288 if (nonVertical) { 289 *current = nonVertical; 290 return; 291 } 292 } 293 return; 294} 295 296struct SortableTop2 { // error if local in pre-C++11 297 SkOpSpanBase* fStart; 298 SkOpSpanBase* fEnd; 299}; 300 301SkOpSegment* FindSortableTop(const SkTDArray<SkOpContour* >& contourList, bool firstPass, 302 SkOpAngle::IncludeType angleIncludeType, bool* firstContour, SkOpSpanBase** startPtr, 303 SkOpSpanBase** endPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical, 304 SkChunkAlloc* allocator) { 305 SkOpSegment* current = findTopSegment(contourList, firstPass, startPtr, endPtr, topLeft, 306 unsortable, done, allocator); 307 if (!current) { 308 return NULL; 309 } 310 SkOpSpanBase* start = *startPtr; 311 SkOpSpanBase* end = *endPtr; 312 SkASSERT(current == start->segment()); 313 if (*firstContour) { 314 current->initWinding(start, end, angleIncludeType); 315 *firstContour = false; 316 return current; 317 } 318 SkOpSpan* minSpan = start->starter(end); 319 int sumWinding = minSpan->windSum(); 320 if (sumWinding == SK_MinS32) { 321 SkOpSpanBase* iSpan = end; 322 SkOpSpanBase* oSpan = start; 323 do { 324 bool checkFrom = oSpan->t() < iSpan->t(); 325 if ((checkFrom ? iSpan->fromAngle() : iSpan->upCast()->toAngle()) == NULL) { 326 iSpan->addSimpleAngle(checkFrom, allocator); 327 } 328 sumWinding = current->computeSum(oSpan, iSpan, angleIncludeType); 329 SkTSwap(iSpan, oSpan); 330 } while (sumWinding == SK_MinS32 && iSpan == start); 331 } 332 if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) { 333 return current; 334 } 335 int contourWinding; 336 int oppContourWinding = 0; 337 // the simple upward projection of the unresolved points hit unsortable angles 338 // shoot rays at right angles to the segment to find its winding, ignoring angle cases 339 bool tryAgain; 340 double tHit; 341 SkScalar hitDx = 0; 342 SkScalar hitOppDx = 0; 343 // keep track of subsequent returns to detect infinite loops 344 SkTDArray<SortableTop2> sortableTops; 345 do { 346 // if current is vertical, find another candidate which is not 347 // if only remaining candidates are vertical, then they can be marked done 348 SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); 349 SkASSERT(current == (*startPtr)->segment()); 350 skipVertical(contourList, ¤t, startPtr, endPtr); 351 SkASSERT(current); // FIXME: if null, all remaining are vertical 352 SkASSERT(*startPtr != *endPtr && *startPtr && *endPtr); 353 SkASSERT(current == (*startPtr)->segment()); 354 tryAgain = false; 355 contourWinding = rightAngleWinding(contourList, ¤t, startPtr, endPtr, &tHit, 356 &hitDx, &tryAgain, onlyVertical, false); 357 SkASSERT(current == (*startPtr)->segment()); 358 if (tryAgain) { 359 bool giveUp = false; 360 int count = sortableTops.count(); 361 for (int index = 0; index < count; ++index) { 362 const SortableTop2& prev = sortableTops[index]; 363 if (giveUp) { 364 prev.fStart->segment()->markDone(prev.fStart->starter(prev.fEnd)); 365 } else if (prev.fStart == *startPtr || prev.fEnd == *endPtr) { 366 // remaining edges are non-vertical and cannot have their winding computed 367 // mark them as done and return, and hope that assembly can fill the holes 368 giveUp = true; 369 index = -1; 370 } 371 } 372 if (giveUp) { 373 *done = true; 374 return NULL; 375 } 376 } 377 SortableTop2* sortableTop = sortableTops.append(); 378 sortableTop->fStart = *startPtr; 379 sortableTop->fEnd = *endPtr; 380#if DEBUG_SORT 381 SkDebugf("%s current=%d index=%d endIndex=%d tHit=%1.9g hitDx=%1.9g try=%d vert=%d\n", 382 __FUNCTION__, current->debugID(), (*startPtr)->debugID(), (*endPtr)->debugID(), 383 tHit, hitDx, tryAgain, *onlyVertical); 384#endif 385 if (*onlyVertical) { 386 return current; 387 } 388 if (tryAgain) { 389 continue; 390 } 391 if (angleIncludeType < SkOpAngle::kBinarySingle) { 392 break; 393 } 394 oppContourWinding = rightAngleWinding(contourList, ¤t, startPtr, endPtr, &tHit, 395 &hitOppDx, &tryAgain, NULL, true); 396 SkASSERT(current == (*startPtr)->segment()); 397 } while (tryAgain); 398 bool success = current->initWinding(*startPtr, *endPtr, tHit, contourWinding, hitDx, 399 oppContourWinding, hitOppDx); 400 if (current->done()) { 401 return NULL; 402 } else if (!success) { // check if the span has a valid winding 403 SkOpSpan* minSpan = (*startPtr)->t() < (*endPtr)->t() ? (*startPtr)->upCast() 404 : (*endPtr)->upCast(); 405 if (minSpan->windSum() == SK_MinS32) { 406 return NULL; 407 } 408 } 409 return current; 410} 411 412void MakeContourList(SkOpContour* contour, SkTDArray<SkOpContour* >& list, 413 bool evenOdd, bool oppEvenOdd) { 414 do { 415 if (contour->count()) { 416 contour->setOppXor(contour->operand() ? evenOdd : oppEvenOdd); 417 *list.append() = contour; 418 } 419 } while ((contour = contour->next())); 420 if (list.count() < 2) { 421 return; 422 } 423 SkTQSort<SkOpContour>(list.begin(), list.end() - 1); 424} 425 426class DistanceLessThan { 427public: 428 DistanceLessThan(double* distances) : fDistances(distances) { } 429 double* fDistances; 430 bool operator()(const int one, const int two) { 431 return fDistances[one] < fDistances[two]; 432 } 433}; 434 435 /* 436 check start and end of each contour 437 if not the same, record them 438 match them up 439 connect closest 440 reassemble contour pieces into new path 441 */ 442void Assemble(const SkPathWriter& path, SkPathWriter* simple) { 443 SkChunkAlloc allocator(4096); // FIXME: constant-ize, tune 444 SkOpContour contour; 445 SkOpGlobalState globalState(NULL PATH_OPS_DEBUG_PARAMS(&contour)); 446#if DEBUG_PATH_CONSTRUCTION 447 SkDebugf("%s\n", __FUNCTION__); 448#endif 449 SkOpEdgeBuilder builder(path, &contour, &allocator, &globalState); 450 builder.finish(&allocator); 451 SkTDArray<const SkOpContour* > runs; // indices of partial contours 452 const SkOpContour* eContour = builder.head(); 453 do { 454 if (!eContour->count()) { 455 continue; 456 } 457 const SkPoint& eStart = eContour->start(); 458 const SkPoint& eEnd = eContour->end(); 459#if DEBUG_ASSEMBLE 460 SkDebugf("%s contour", __FUNCTION__); 461 if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) { 462 SkDebugf("[%d]", runs.count()); 463 } else { 464 SkDebugf(" "); 465 } 466 SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", 467 eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); 468#endif 469 if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) { 470 eContour->toPath(simple); 471 continue; 472 } 473 *runs.append() = eContour; 474 } while ((eContour = eContour->next())); 475 int count = runs.count(); 476 if (count == 0) { 477 return; 478 } 479 SkTDArray<int> sLink, eLink; 480 sLink.append(count); 481 eLink.append(count); 482 int rIndex, iIndex; 483 for (rIndex = 0; rIndex < count; ++rIndex) { 484 sLink[rIndex] = eLink[rIndex] = SK_MaxS32; 485 } 486 const int ends = count * 2; // all starts and ends 487 const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2 488 SkTDArray<double> distances; 489 distances.append(entries); 490 for (rIndex = 0; rIndex < ends - 1; ++rIndex) { 491 const SkOpContour* oContour = runs[rIndex >> 1]; 492 const SkPoint& oPt = rIndex & 1 ? oContour->end() : oContour->start(); 493 const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2) 494 * ends - rIndex - 1; 495 for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) { 496 const SkOpContour* iContour = runs[iIndex >> 1]; 497 const SkPoint& iPt = iIndex & 1 ? iContour->end() : iContour->start(); 498 double dx = iPt.fX - oPt.fX; 499 double dy = iPt.fY - oPt.fY; 500 double dist = dx * dx + dy * dy; 501 distances[row + iIndex] = dist; // oStart distance from iStart 502 } 503 } 504 SkTDArray<int> sortedDist; 505 sortedDist.append(entries); 506 for (rIndex = 0; rIndex < entries; ++rIndex) { 507 sortedDist[rIndex] = rIndex; 508 } 509 SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin())); 510 int remaining = count; // number of start/end pairs 511 for (rIndex = 0; rIndex < entries; ++rIndex) { 512 int pair = sortedDist[rIndex]; 513 int row = pair / ends; 514 int col = pair - row * ends; 515 int thingOne = row < col ? row : ends - row - 2; 516 int ndxOne = thingOne >> 1; 517 bool endOne = thingOne & 1; 518 int* linkOne = endOne ? eLink.begin() : sLink.begin(); 519 if (linkOne[ndxOne] != SK_MaxS32) { 520 continue; 521 } 522 int thingTwo = row < col ? col : ends - row + col - 1; 523 int ndxTwo = thingTwo >> 1; 524 bool endTwo = thingTwo & 1; 525 int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); 526 if (linkTwo[ndxTwo] != SK_MaxS32) { 527 continue; 528 } 529 SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); 530 bool flip = endOne == endTwo; 531 linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; 532 linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; 533 if (!--remaining) { 534 break; 535 } 536 } 537 SkASSERT(!remaining); 538#if DEBUG_ASSEMBLE 539 for (rIndex = 0; rIndex < count; ++rIndex) { 540 int s = sLink[rIndex]; 541 int e = eLink[rIndex]; 542 SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', 543 s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); 544 } 545#endif 546 rIndex = 0; 547 do { 548 bool forward = true; 549 bool first = true; 550 int sIndex = sLink[rIndex]; 551 SkASSERT(sIndex != SK_MaxS32); 552 sLink[rIndex] = SK_MaxS32; 553 int eIndex; 554 if (sIndex < 0) { 555 eIndex = sLink[~sIndex]; 556 sLink[~sIndex] = SK_MaxS32; 557 } else { 558 eIndex = eLink[sIndex]; 559 eLink[sIndex] = SK_MaxS32; 560 } 561 SkASSERT(eIndex != SK_MaxS32); 562#if DEBUG_ASSEMBLE 563 SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', 564 sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', 565 eIndex < 0 ? ~eIndex : eIndex); 566#endif 567 do { 568 const SkOpContour* contour = runs[rIndex]; 569 if (first) { 570 first = false; 571 const SkPoint* startPtr = &contour->start(); 572 simple->deferredMove(startPtr[0]); 573 } 574 if (forward) { 575 contour->toPartialForward(simple); 576 } else { 577 contour->toPartialBackward(simple); 578 } 579#if DEBUG_ASSEMBLE 580 SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, 581 eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, 582 sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); 583#endif 584 if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { 585 simple->close(); 586 break; 587 } 588 if (forward) { 589 eIndex = eLink[rIndex]; 590 SkASSERT(eIndex != SK_MaxS32); 591 eLink[rIndex] = SK_MaxS32; 592 if (eIndex >= 0) { 593 SkASSERT(sLink[eIndex] == rIndex); 594 sLink[eIndex] = SK_MaxS32; 595 } else { 596 SkASSERT(eLink[~eIndex] == ~rIndex); 597 eLink[~eIndex] = SK_MaxS32; 598 } 599 } else { 600 eIndex = sLink[rIndex]; 601 SkASSERT(eIndex != SK_MaxS32); 602 sLink[rIndex] = SK_MaxS32; 603 if (eIndex >= 0) { 604 SkASSERT(eLink[eIndex] == rIndex); 605 eLink[eIndex] = SK_MaxS32; 606 } else { 607 SkASSERT(sLink[~eIndex] == ~rIndex); 608 sLink[~eIndex] = SK_MaxS32; 609 } 610 } 611 rIndex = eIndex; 612 if (rIndex < 0) { 613 forward ^= 1; 614 rIndex = ~rIndex; 615 } 616 } while (true); 617 for (rIndex = 0; rIndex < count; ++rIndex) { 618 if (sLink[rIndex] != SK_MaxS32) { 619 break; 620 } 621 } 622 } while (rIndex < count); 623#if DEBUG_ASSEMBLE 624 for (rIndex = 0; rIndex < count; ++rIndex) { 625 SkASSERT(sLink[rIndex] == SK_MaxS32); 626 SkASSERT(eLink[rIndex] == SK_MaxS32); 627 } 628#endif 629} 630 631static void align(SkTDArray<SkOpContour* >* contourList) { 632 int contourCount = (*contourList).count(); 633 for (int cTest = 0; cTest < contourCount; ++cTest) { 634 SkOpContour* contour = (*contourList)[cTest]; 635 contour->align(); 636 } 637} 638 639static void calcAngles(SkTDArray<SkOpContour* >* contourList, SkChunkAlloc* allocator) { 640 int contourCount = (*contourList).count(); 641 for (int cTest = 0; cTest < contourCount; ++cTest) { 642 SkOpContour* contour = (*contourList)[cTest]; 643 contour->calcAngles(allocator); 644 } 645} 646 647static void missingCoincidence(SkTDArray<SkOpContour* >* contourList, 648 SkOpCoincidence* coincidence, SkChunkAlloc* allocator) { 649 int contourCount = (*contourList).count(); 650 for (int cTest = 0; cTest < contourCount; ++cTest) { 651 SkOpContour* contour = (*contourList)[cTest]; 652 contour->missingCoincidence(coincidence, allocator); 653 } 654} 655 656static bool moveNearby(SkTDArray<SkOpContour* >* contourList) { 657 int contourCount = (*contourList).count(); 658 for (int cTest = 0; cTest < contourCount; ++cTest) { 659 SkOpContour* contour = (*contourList)[cTest]; 660 if (!contour->moveNearby()) { 661 return false; 662 } 663 } 664 return true; 665} 666 667static void sortAngles(SkTDArray<SkOpContour* >* contourList) { 668 int contourCount = (*contourList).count(); 669 for (int cTest = 0; cTest < contourCount; ++cTest) { 670 SkOpContour* contour = (*contourList)[cTest]; 671 contour->sortAngles(); 672 } 673} 674 675static void sortSegments(SkTDArray<SkOpContour* >* contourList) { 676 int contourCount = (*contourList).count(); 677 for (int cTest = 0; cTest < contourCount; ++cTest) { 678 SkOpContour* contour = (*contourList)[cTest]; 679 contour->sortSegments(); 680 } 681} 682 683bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* coincidence, 684 SkChunkAlloc* allocator, SkOpGlobalState* globalState) { 685 // move t values and points together to eliminate small/tiny gaps 686 if (!moveNearby(contourList)) { 687 return false; 688 } 689 align(contourList); // give all span members common values 690#if DEBUG_VALIDATE 691 globalState->setPhase(SkOpGlobalState::kIntersecting); 692#endif 693 coincidence->addMissing(allocator); 694#if DEBUG_VALIDATE 695 globalState->setPhase(SkOpGlobalState::kWalking); 696#endif 697 coincidence->expand(); // check to see if, loosely, coincident ranges may be expanded 698 coincidence->mark(); // mark spans of coincident segments as coincident 699 missingCoincidence(contourList, coincidence, allocator); // look for coincidence missed earlier 700 if (!coincidence->apply()) { // adjust the winding value to account for coincident edges 701 return false; 702 } 703 sortSegments(contourList); 704 calcAngles(contourList, allocator); 705 sortAngles(contourList); 706 if (globalState->angleCoincidence()) { 707 missingCoincidence(contourList, coincidence, allocator); 708 if (!coincidence->apply()) { 709 return false; 710 } 711 } 712#if DEBUG_ACTIVE_SPANS 713 DebugShowActiveSpans(*contourList); 714#endif 715 return true; 716} 717