SkPathOpsCommon.cpp revision 3e475dc8d0a156521bd9963edb80b10398a14160
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 12static 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 = 0; 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 } 78abortContours: 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); 92 SkASSERT(result == SK_MinS32 || *bestDx); 93 } 94 double baseT = current->t(index); 95 double endT = current->t(endIndex); 96 *bestHit = baseT + mid * (endT - baseT); 97 return result; 98} 99 100SkOpSegment* 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 113SkOpSegment* 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 210void DebugShowActiveSpans(SkTDArray<SkOpContour*>& contourList) { 211 int index; 212 for (index = 0; index < contourList.count(); ++ index) { 213 contourList[index]->debugShowActiveSpans(); 214 } 215} 216#endif 217 218static 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 255static 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 272static 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 290SkOpSegment* 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); 327 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 346void 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 354void 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 362void 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 376static bool approximatelyEqual(const SkPoint& a, const SkPoint& b) { 377 return AlmostEqualUlps(a.fX, b.fX) && AlmostEqualUlps(a.fY, b.fY); 378} 379 380static 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 */ 390void 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} 578