SkPathOpsCommon.cpp revision 6f726addf3178b01949bb389ef83cf14a1d7b6b2
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 13static 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 24static 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 36static 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 } 102abortContours: 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 124SkOpSegment* 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 137SkOpSegment* 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 wind sum 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 // allowed to do nothing 212 (void) segment->markAndChaseWinding(angle, maxWinding, 0, NULL); 213 break; 214 } 215 } 216 *chase->insert(0) = span; 217 return segment; 218 } 219 return NULL; 220} 221 222#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY 223void DebugShowActiveSpans(SkTArray<SkOpContour*, true>& contourList) { 224 int index; 225 for (index = 0; index < contourList.count(); ++ index) { 226 contourList[index]->debugShowActiveSpans(); 227 } 228} 229#endif 230 231static SkOpSegment* findTopSegment(const SkTArray<SkOpContour*, true>& contourList, int* index, 232 int* endIndex, SkPoint* topLeft, bool* unsortable, bool* done, bool firstPass) { 233 SkOpSegment* result; 234 const SkOpSegment* lastTopStart = NULL; 235 int lastIndex = -1, lastEndIndex = -1; 236 do { 237 SkPoint bestXY = {SK_ScalarMax, SK_ScalarMax}; 238 int contourCount = contourList.count(); 239 SkOpSegment* topStart = NULL; 240 *done = true; 241 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 242 SkOpContour* contour = contourList[cIndex]; 243 if (contour->done()) { 244 continue; 245 } 246 const SkPathOpsBounds& bounds = contour->bounds(); 247 if (bounds.fBottom < topLeft->fY) { 248 *done = false; 249 continue; 250 } 251 if (bounds.fBottom == topLeft->fY && bounds.fRight < topLeft->fX) { 252 *done = false; 253 continue; 254 } 255 contour->topSortableSegment(*topLeft, &bestXY, &topStart); 256 if (!contour->done()) { 257 *done = false; 258 } 259 } 260 if (!topStart) { 261 return NULL; 262 } 263 *topLeft = bestXY; 264 result = topStart->findTop(index, endIndex, unsortable, firstPass); 265 if (!result) { 266 if (lastTopStart == topStart && lastIndex == *index && lastEndIndex == *endIndex) { 267 *done = true; 268 return NULL; 269 } 270 lastTopStart = topStart; 271 lastIndex = *index; 272 lastEndIndex = *endIndex; 273 } 274 } while (!result); 275 return result; 276} 277 278static int rightAngleWinding(const SkTArray<SkOpContour*, true>& contourList, 279 SkOpSegment** currentPtr, int* indexPtr, int* endIndexPtr, double* tHit, 280 SkScalar* hitDx, bool* tryAgain, bool* onlyVertical, bool opp) { 281 double test = 0.9; 282 int contourWinding; 283 do { 284 contourWinding = contourRangeCheckY(contourList, currentPtr, indexPtr, endIndexPtr, 285 tHit, hitDx, tryAgain, &test, opp); 286 if (contourWinding != SK_MinS32 || *tryAgain) { 287 return contourWinding; 288 } 289 if (*currentPtr && (*currentPtr)->isVertical()) { 290 *onlyVertical = true; 291 return contourWinding; 292 } 293 test /= 2; 294 } while (!approximately_negative(test)); 295 SkASSERT(0); // FIXME: incomplete functionality 296 return contourWinding; 297} 298 299static void skipVertical(const SkTArray<SkOpContour*, true>& contourList, 300 SkOpSegment** current, int* index, int* endIndex) { 301 if (!(*current)->isVertical(*index, *endIndex)) { 302 return; 303 } 304 int contourCount = contourList.count(); 305 for (int cIndex = 0; cIndex < contourCount; ++cIndex) { 306 SkOpContour* contour = contourList[cIndex]; 307 if (contour->done()) { 308 continue; 309 } 310 SkOpSegment* nonVertical = contour->nonVerticalSegment(index, endIndex); 311 if (nonVertical) { 312 *current = nonVertical; 313 return; 314 } 315 } 316 return; 317} 318 319struct SortableTop { // error if local in pre-C++11 320 SkOpSegment* fSegment; 321 int fIndex; 322 int fEndIndex; 323}; 324 325SkOpSegment* FindSortableTop(const SkTArray<SkOpContour*, true>& contourList, 326 SkOpAngle::IncludeType angleIncludeType, bool* firstContour, int* indexPtr, 327 int* endIndexPtr, SkPoint* topLeft, bool* unsortable, bool* done, bool* onlyVertical, 328 bool firstPass) { 329 SkOpSegment* current = findTopSegment(contourList, indexPtr, endIndexPtr, topLeft, unsortable, 330 done, firstPass); 331 if (!current) { 332 return NULL; 333 } 334 const int startIndex = *indexPtr; 335 const int endIndex = *endIndexPtr; 336 if (*firstContour) { 337 current->initWinding(startIndex, endIndex, angleIncludeType); 338 *firstContour = false; 339 return current; 340 } 341 int minIndex = SkMin32(startIndex, endIndex); 342 int sumWinding = current->windSum(minIndex); 343 if (sumWinding == SK_MinS32) { 344 int index = endIndex; 345 int oIndex = startIndex; 346 do { 347 const SkOpSpan& span = current->span(index); 348 if ((oIndex < index ? span.fFromAngle : span.fToAngle) == NULL) { 349 current->addSimpleAngle(index); 350 } 351 sumWinding = current->computeSum(oIndex, index, angleIncludeType); 352 SkTSwap(index, oIndex); 353 } while (sumWinding == SK_MinS32 && index == startIndex); 354 } 355 if (sumWinding != SK_MinS32 && sumWinding != SK_NaN32) { 356 return current; 357 } 358 int contourWinding; 359 int oppContourWinding = 0; 360 // the simple upward projection of the unresolved points hit unsortable angles 361 // shoot rays at right angles to the segment to find its winding, ignoring angle cases 362 bool tryAgain; 363 double tHit; 364 SkScalar hitDx = 0; 365 SkScalar hitOppDx = 0; 366 // keep track of subsequent returns to detect infinite loops 367 SkTDArray<SortableTop> sortableTops; 368 do { 369 // if current is vertical, find another candidate which is not 370 // if only remaining candidates are vertical, then they can be marked done 371 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0); 372 skipVertical(contourList, ¤t, indexPtr, endIndexPtr); 373 SkASSERT(current); // FIXME: if null, all remaining are vertical 374 SkASSERT(*indexPtr != *endIndexPtr && *indexPtr >= 0 && *endIndexPtr >= 0); 375 tryAgain = false; 376 contourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit, 377 &hitDx, &tryAgain, onlyVertical, false); 378 if (tryAgain) { 379 bool giveUp = false; 380 int count = sortableTops.count(); 381 for (int index = 0; index < count; ++index) { 382 const SortableTop& prev = sortableTops[index]; 383 if (giveUp) { 384 prev.fSegment->markDoneFinal(prev.fIndex); 385 } else if (prev.fSegment == current 386 && (prev.fIndex == *indexPtr || prev.fEndIndex == *endIndexPtr)) { 387 // remaining edges are non-vertical and cannot have their winding computed 388 // mark them as done and return, and hope that assembly can fill the holes 389 giveUp = true; 390 index = -1; 391 } 392 } 393 if (giveUp) { 394 *done = true; 395 return NULL; 396 } 397 } 398 SortableTop* sortableTop = sortableTops.append(); 399 sortableTop->fSegment = current; 400 sortableTop->fIndex = *indexPtr; 401 sortableTop->fEndIndex = *endIndexPtr; 402#if DEBUG_SORT 403 SkDebugf("%s current=%d index=%d endIndex=%d tHit=%1.9g hitDx=%1.9g try=%d vert=%d\n", 404 __FUNCTION__, current->debugID(), *indexPtr, *endIndexPtr, tHit, hitDx, tryAgain, 405 *onlyVertical); 406#endif 407 if (*onlyVertical) { 408 return current; 409 } 410 if (tryAgain) { 411 continue; 412 } 413 if (angleIncludeType < SkOpAngle::kBinarySingle) { 414 break; 415 } 416 oppContourWinding = rightAngleWinding(contourList, ¤t, indexPtr, endIndexPtr, &tHit, 417 &hitOppDx, &tryAgain, NULL, true); 418 } while (tryAgain); 419 bool success = current->initWinding(*indexPtr, *endIndexPtr, tHit, contourWinding, hitDx, 420 oppContourWinding, hitOppDx); 421 if (current->done()) { 422 return NULL; 423 } else if (!success) { // check if the span has a valid winding 424 int min = SkTMin(*indexPtr, *endIndexPtr); 425 const SkOpSpan& span = current->span(min); 426 if (span.fWindSum == SK_MinS32) { 427 return NULL; 428 } 429 } 430 return current; 431} 432 433static bool calcAngles(SkTArray<SkOpContour*, true>* contourList) { 434 int contourCount = (*contourList).count(); 435 for (int cTest = 0; cTest < contourCount; ++cTest) { 436 SkOpContour* contour = (*contourList)[cTest]; 437 if (!contour->calcAngles()) { 438 return false; 439 } 440 } 441 return true; 442} 443 444static void checkDuplicates(SkTArray<SkOpContour*, true>* contourList) { 445 int contourCount = (*contourList).count(); 446 for (int cTest = 0; cTest < contourCount; ++cTest) { 447 SkOpContour* contour = (*contourList)[cTest]; 448 contour->checkDuplicates(); 449 } 450} 451 452static bool checkEnds(SkTArray<SkOpContour*, true>* contourList) { 453 // it's hard to determine if the end of a cubic or conic nearly intersects another curve. 454 // instead, look to see if the connecting curve intersected at that same end. 455 int contourCount = (*contourList).count(); 456 for (int cTest = 0; cTest < contourCount; ++cTest) { 457 SkOpContour* contour = (*contourList)[cTest]; 458 if (!contour->checkEnds()) { 459 return false; 460 } 461 } 462 return true; 463} 464 465static bool checkMultiples(SkTArray<SkOpContour*, true>* contourList) { 466 bool hasMultiples = false; 467 int contourCount = (*contourList).count(); 468 for (int cTest = 0; cTest < contourCount; ++cTest) { 469 SkOpContour* contour = (*contourList)[cTest]; 470 contour->checkMultiples(); 471 hasMultiples |= contour->hasMultiples(); 472 } 473 return hasMultiples; 474} 475 476// A small interval of a pair of curves may collapse to lines for each, triggering coincidence 477static void checkSmall(SkTArray<SkOpContour*, true>* contourList) { 478 int contourCount = (*contourList).count(); 479 for (int cTest = 0; cTest < contourCount; ++cTest) { 480 SkOpContour* contour = (*contourList)[cTest]; 481 contour->checkSmall(); 482 } 483} 484 485// A tiny interval may indicate an undiscovered coincidence. Find and fix. 486static void checkTiny(SkTArray<SkOpContour*, true>* contourList) { 487 int contourCount = (*contourList).count(); 488 for (int cTest = 0; cTest < contourCount; ++cTest) { 489 SkOpContour* contour = (*contourList)[cTest]; 490 contour->checkTiny(); 491 } 492} 493 494static void fixOtherTIndex(SkTArray<SkOpContour*, true>* contourList) { 495 int contourCount = (*contourList).count(); 496 for (int cTest = 0; cTest < contourCount; ++cTest) { 497 SkOpContour* contour = (*contourList)[cTest]; 498 contour->fixOtherTIndex(); 499 } 500} 501 502static void joinCoincidence(SkTArray<SkOpContour*, true>* contourList) { 503 int contourCount = (*contourList).count(); 504 for (int cTest = 0; cTest < contourCount; ++cTest) { 505 SkOpContour* contour = (*contourList)[cTest]; 506 contour->joinCoincidence(); 507 } 508} 509 510static void sortAngles(SkTArray<SkOpContour*, true>* contourList) { 511 int contourCount = (*contourList).count(); 512 for (int cTest = 0; cTest < contourCount; ++cTest) { 513 SkOpContour* contour = (*contourList)[cTest]; 514 contour->sortAngles(); 515 } 516} 517 518static void sortSegments(SkTArray<SkOpContour*, true>* contourList) { 519 int contourCount = (*contourList).count(); 520 for (int cTest = 0; cTest < contourCount; ++cTest) { 521 SkOpContour* contour = (*contourList)[cTest]; 522 contour->sortSegments(); 523 } 524} 525 526void MakeContourList(SkTArray<SkOpContour>& contours, SkTArray<SkOpContour*, true>& list, 527 bool evenOdd, bool oppEvenOdd) { 528 int count = contours.count(); 529 if (count == 0) { 530 return; 531 } 532 for (int index = 0; index < count; ++index) { 533 SkOpContour& contour = contours[index]; 534 contour.setOppXor(contour.operand() ? evenOdd : oppEvenOdd); 535 list.push_back(&contour); 536 } 537 SkTQSort<SkOpContour>(list.begin(), list.end() - 1); 538} 539 540class DistanceLessThan { 541public: 542 DistanceLessThan(double* distances) : fDistances(distances) { } 543 double* fDistances; 544 bool operator()(const int one, const int two) { 545 return fDistances[one] < fDistances[two]; 546 } 547}; 548 549 /* 550 check start and end of each contour 551 if not the same, record them 552 match them up 553 connect closest 554 reassemble contour pieces into new path 555 */ 556void Assemble(const SkPathWriter& path, SkPathWriter* simple) { 557#if DEBUG_PATH_CONSTRUCTION 558 SkDebugf("%s\n", __FUNCTION__); 559#endif 560 SkTArray<SkOpContour> contours; 561 SkOpEdgeBuilder builder(path, contours); 562 builder.finish(); 563 int count = contours.count(); 564 int outer; 565 SkTArray<int, true> runs(count); // indices of partial contours 566 for (outer = 0; outer < count; ++outer) { 567 const SkOpContour& eContour = contours[outer]; 568 const SkPoint& eStart = eContour.start(); 569 const SkPoint& eEnd = eContour.end(); 570#if DEBUG_ASSEMBLE 571 SkDebugf("%s contour", __FUNCTION__); 572 if (!SkDPoint::ApproximatelyEqual(eStart, eEnd)) { 573 SkDebugf("[%d]", runs.count()); 574 } else { 575 SkDebugf(" "); 576 } 577 SkDebugf(" start=(%1.9g,%1.9g) end=(%1.9g,%1.9g)\n", 578 eStart.fX, eStart.fY, eEnd.fX, eEnd.fY); 579#endif 580 if (SkDPoint::ApproximatelyEqual(eStart, eEnd)) { 581 eContour.toPath(simple); 582 continue; 583 } 584 runs.push_back(outer); 585 } 586 count = runs.count(); 587 if (count == 0) { 588 return; 589 } 590 SkTArray<int, true> sLink, eLink; 591 sLink.push_back_n(count); 592 eLink.push_back_n(count); 593 int rIndex, iIndex; 594 for (rIndex = 0; rIndex < count; ++rIndex) { 595 sLink[rIndex] = eLink[rIndex] = SK_MaxS32; 596 } 597 const int ends = count * 2; // all starts and ends 598 const int entries = (ends - 1) * count; // folded triangle : n * (n - 1) / 2 599 SkTArray<double, true> distances; 600 distances.push_back_n(entries); 601 for (rIndex = 0; rIndex < ends - 1; ++rIndex) { 602 outer = runs[rIndex >> 1]; 603 const SkOpContour& oContour = contours[outer]; 604 const SkPoint& oPt = rIndex & 1 ? oContour.end() : oContour.start(); 605 const int row = rIndex < count - 1 ? rIndex * ends : (ends - rIndex - 2) 606 * ends - rIndex - 1; 607 for (iIndex = rIndex + 1; iIndex < ends; ++iIndex) { 608 int inner = runs[iIndex >> 1]; 609 const SkOpContour& iContour = contours[inner]; 610 const SkPoint& iPt = iIndex & 1 ? iContour.end() : iContour.start(); 611 double dx = iPt.fX - oPt.fX; 612 double dy = iPt.fY - oPt.fY; 613 double dist = dx * dx + dy * dy; 614 distances[row + iIndex] = dist; // oStart distance from iStart 615 } 616 } 617 SkTArray<int, true> sortedDist; 618 sortedDist.push_back_n(entries); 619 for (rIndex = 0; rIndex < entries; ++rIndex) { 620 sortedDist[rIndex] = rIndex; 621 } 622 SkTQSort<int>(sortedDist.begin(), sortedDist.end() - 1, DistanceLessThan(distances.begin())); 623 int remaining = count; // number of start/end pairs 624 for (rIndex = 0; rIndex < entries; ++rIndex) { 625 int pair = sortedDist[rIndex]; 626 int row = pair / ends; 627 int col = pair - row * ends; 628 int thingOne = row < col ? row : ends - row - 2; 629 int ndxOne = thingOne >> 1; 630 bool endOne = thingOne & 1; 631 int* linkOne = endOne ? eLink.begin() : sLink.begin(); 632 if (linkOne[ndxOne] != SK_MaxS32) { 633 continue; 634 } 635 int thingTwo = row < col ? col : ends - row + col - 1; 636 int ndxTwo = thingTwo >> 1; 637 bool endTwo = thingTwo & 1; 638 int* linkTwo = endTwo ? eLink.begin() : sLink.begin(); 639 if (linkTwo[ndxTwo] != SK_MaxS32) { 640 continue; 641 } 642 SkASSERT(&linkOne[ndxOne] != &linkTwo[ndxTwo]); 643 bool flip = endOne == endTwo; 644 linkOne[ndxOne] = flip ? ~ndxTwo : ndxTwo; 645 linkTwo[ndxTwo] = flip ? ~ndxOne : ndxOne; 646 if (!--remaining) { 647 break; 648 } 649 } 650 SkASSERT(!remaining); 651#if DEBUG_ASSEMBLE 652 for (rIndex = 0; rIndex < count; ++rIndex) { 653 int s = sLink[rIndex]; 654 int e = eLink[rIndex]; 655 SkDebugf("%s %c%d <- s%d - e%d -> %c%d\n", __FUNCTION__, s < 0 ? 's' : 'e', 656 s < 0 ? ~s : s, rIndex, rIndex, e < 0 ? 'e' : 's', e < 0 ? ~e : e); 657 } 658#endif 659 rIndex = 0; 660 do { 661 bool forward = true; 662 bool first = true; 663 int sIndex = sLink[rIndex]; 664 SkASSERT(sIndex != SK_MaxS32); 665 sLink[rIndex] = SK_MaxS32; 666 int eIndex; 667 if (sIndex < 0) { 668 eIndex = sLink[~sIndex]; 669 sLink[~sIndex] = SK_MaxS32; 670 } else { 671 eIndex = eLink[sIndex]; 672 eLink[sIndex] = SK_MaxS32; 673 } 674 SkASSERT(eIndex != SK_MaxS32); 675#if DEBUG_ASSEMBLE 676 SkDebugf("%s sIndex=%c%d eIndex=%c%d\n", __FUNCTION__, sIndex < 0 ? 's' : 'e', 677 sIndex < 0 ? ~sIndex : sIndex, eIndex < 0 ? 's' : 'e', 678 eIndex < 0 ? ~eIndex : eIndex); 679#endif 680 do { 681 outer = runs[rIndex]; 682 const SkOpContour& contour = contours[outer]; 683 if (first) { 684 first = false; 685 const SkPoint* startPtr = &contour.start(); 686 simple->deferredMove(startPtr[0]); 687 } 688 if (forward) { 689 contour.toPartialForward(simple); 690 } else { 691 contour.toPartialBackward(simple); 692 } 693#if DEBUG_ASSEMBLE 694 SkDebugf("%s rIndex=%d eIndex=%s%d close=%d\n", __FUNCTION__, rIndex, 695 eIndex < 0 ? "~" : "", eIndex < 0 ? ~eIndex : eIndex, 696 sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)); 697#endif 698 if (sIndex == ((rIndex != eIndex) ^ forward ? eIndex : ~eIndex)) { 699 simple->close(); 700 break; 701 } 702 if (forward) { 703 eIndex = eLink[rIndex]; 704 SkASSERT(eIndex != SK_MaxS32); 705 eLink[rIndex] = SK_MaxS32; 706 if (eIndex >= 0) { 707 SkASSERT(sLink[eIndex] == rIndex); 708 sLink[eIndex] = SK_MaxS32; 709 } else { 710 SkASSERT(eLink[~eIndex] == ~rIndex); 711 eLink[~eIndex] = SK_MaxS32; 712 } 713 } else { 714 eIndex = sLink[rIndex]; 715 SkASSERT(eIndex != SK_MaxS32); 716 sLink[rIndex] = SK_MaxS32; 717 if (eIndex >= 0) { 718 SkASSERT(eLink[eIndex] == rIndex); 719 eLink[eIndex] = SK_MaxS32; 720 } else { 721 SkASSERT(sLink[~eIndex] == ~rIndex); 722 sLink[~eIndex] = SK_MaxS32; 723 } 724 } 725 rIndex = eIndex; 726 if (rIndex < 0) { 727 forward ^= 1; 728 rIndex = ~rIndex; 729 } 730 } while (true); 731 for (rIndex = 0; rIndex < count; ++rIndex) { 732 if (sLink[rIndex] != SK_MaxS32) { 733 break; 734 } 735 } 736 } while (rIndex < count); 737#if DEBUG_ASSEMBLE 738 for (rIndex = 0; rIndex < count; ++rIndex) { 739 SkASSERT(sLink[rIndex] == SK_MaxS32); 740 SkASSERT(eLink[rIndex] == SK_MaxS32); 741 } 742#endif 743} 744 745bool HandleCoincidence(SkTArray<SkOpContour*, true>* contourList, int total) { 746#if DEBUG_SHOW_WINDING 747 SkOpContour::debugShowWindingValues(contourList); 748#endif 749 if (!CoincidenceCheck(contourList, total)) { 750 return false; 751 } 752#if DEBUG_SHOW_WINDING 753 SkOpContour::debugShowWindingValues(contourList); 754#endif 755 fixOtherTIndex(contourList); 756 if (!checkEnds(contourList)) { // check if connecting curve intersected at the same end 757 return false; 758 } 759 bool hasM = checkMultiples(contourList); // check if intersections agree on t and point values 760 SkTDArray<SkOpSegment::AlignedSpan> aligned; 761 if (hasM) { 762 alignMultiples(contourList, &aligned); // align pairs of identical points 763 alignCoincidence(contourList, aligned); 764 } 765 checkDuplicates(contourList); // check if spans have the same number on the other end 766 checkTiny(contourList); // if pair have the same end points, mark them as parallel 767 checkSmall(contourList); // a pair of curves with a small span may turn into coincident lines 768 joinCoincidence(contourList); // join curves that connect to a coincident pair 769 sortSegments(contourList); 770 if (!calcAngles(contourList)) { 771 return false; 772 } 773 sortAngles(contourList); 774#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY 775 DebugShowActiveSpans(*contourList); 776#endif 777 return true; 778} 779