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 "SkOpCoincidence.h" 8#include "SkOpContour.h" 9#include "SkOpSegment.h" 10#include "SkPathWriter.h" 11#include "SkPointPriv.h" 12 13/* 14After computing raw intersections, post process all segments to: 15- find small collections of points that can be collapsed to a single point 16- find missing intersections to resolve differences caused by different algorithms 17 18Consider segments containing tiny or small intervals. Consider coincident segments 19because coincidence finds intersections through distance measurement that non-coincident 20intersection tests cannot. 21 */ 22 23#define F (false) // discard the edge 24#define T (true) // keep the edge 25 26static const bool gUnaryActiveEdge[2][2] = { 27// from=0 from=1 28// to=0,1 to=0,1 29 {F, T}, {T, F}, 30}; 31 32static const bool gActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = { 33// miFrom=0 miFrom=1 34// miTo=0 miTo=1 miTo=0 miTo=1 35// suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 36// suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 37 {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su 38 {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su 39 {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su 40 {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su 41}; 42 43#undef F 44#undef T 45 46SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, 47 SkOpSpanBase** endPtr, bool* done) { 48 if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) { 49 return result; 50 } 51 if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) { 52 return result; 53 } 54 return nullptr; 55} 56 57SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr, 58 SkOpSpanBase** endPtr, bool* done) { 59 SkOpSpan* upSpan = start->upCastable(); 60 if (upSpan) { 61 if (upSpan->windValue() || upSpan->oppValue()) { 62 SkOpSpanBase* next = upSpan->next(); 63 if (!*endPtr) { 64 *startPtr = start; 65 *endPtr = next; 66 } 67 if (!upSpan->done()) { 68 if (upSpan->windSum() != SK_MinS32) { 69 return spanToAngle(start, next); 70 } 71 *done = false; 72 } 73 } else { 74 SkASSERT(upSpan->done()); 75 } 76 } 77 SkOpSpan* downSpan = start->prev(); 78 // edge leading into junction 79 if (downSpan) { 80 if (downSpan->windValue() || downSpan->oppValue()) { 81 if (!*endPtr) { 82 *startPtr = start; 83 *endPtr = downSpan; 84 } 85 if (!downSpan->done()) { 86 if (downSpan->windSum() != SK_MinS32) { 87 return spanToAngle(start, downSpan); 88 } 89 *done = false; 90 } 91 } else { 92 SkASSERT(downSpan->done()); 93 } 94 } 95 return nullptr; 96} 97 98SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr, 99 SkOpSpanBase** endPtr, bool* done) { 100 SkOpPtT* oPtT = start->ptT()->next(); 101 SkOpSegment* other = oPtT->segment(); 102 SkOpSpanBase* oSpan = oPtT->span(); 103 return other->activeAngleInner(oSpan, startPtr, endPtr, done); 104} 105 106bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask, 107 SkPathOp op) { 108 int sumMiWinding = this->updateWinding(end, start); 109 int sumSuWinding = this->updateOppWinding(end, start); 110#if DEBUG_LIMIT_WIND_SUM 111 SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM); 112 SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM); 113#endif 114 if (this->operand()) { 115 SkTSwap<int>(sumMiWinding, sumSuWinding); 116 } 117 return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding); 118} 119 120bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, 121 SkPathOp op, int* sumMiWinding, int* sumSuWinding) { 122 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 123 this->setUpWindings(start, end, sumMiWinding, sumSuWinding, 124 &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 125 bool miFrom; 126 bool miTo; 127 bool suFrom; 128 bool suTo; 129 if (operand()) { 130 miFrom = (oppMaxWinding & xorMiMask) != 0; 131 miTo = (oppSumWinding & xorMiMask) != 0; 132 suFrom = (maxWinding & xorSuMask) != 0; 133 suTo = (sumWinding & xorSuMask) != 0; 134 } else { 135 miFrom = (maxWinding & xorMiMask) != 0; 136 miTo = (sumWinding & xorMiMask) != 0; 137 suFrom = (oppMaxWinding & xorSuMask) != 0; 138 suTo = (oppSumWinding & xorSuMask) != 0; 139 } 140 bool result = gActiveEdge[op][miFrom][miTo][suFrom][suTo]; 141#if DEBUG_ACTIVE_OP 142 SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", 143 __FUNCTION__, debugID(), start->t(), end->t(), 144 SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); 145#endif 146 return result; 147} 148 149bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 150 int sumWinding = updateWinding(end, start); 151 return activeWinding(start, end, &sumWinding); 152} 153 154bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) { 155 int maxWinding; 156 setUpWinding(start, end, &maxWinding, sumWinding); 157 bool from = maxWinding != 0; 158 bool to = *sumWinding != 0; 159 bool result = gUnaryActiveEdge[from][to]; 160 return result; 161} 162 163bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, 164 SkPathWriter* path) const { 165 FAIL_IF(start->starter(end)->alreadyAdded()); 166 SkDCurveSweep curvePart; 167 start->segment()->subDivide(start, end, &curvePart.fCurve); 168 curvePart.setCurveHullSweep(fVerb); 169 SkPath::Verb verb = curvePart.isCurve() ? fVerb : SkPath::kLine_Verb; 170 path->deferredMove(start->ptT()); 171 switch (verb) { 172 case SkPath::kLine_Verb: 173 FAIL_IF(!path->deferredLine(end->ptT())); 174 break; 175 case SkPath::kQuad_Verb: 176 path->quadTo(curvePart.fCurve.fQuad[1].asSkPoint(), end->ptT()); 177 break; 178 case SkPath::kConic_Verb: 179 path->conicTo(curvePart.fCurve.fConic[1].asSkPoint(), end->ptT(), 180 curvePart.fCurve.fConic.fWeight); 181 break; 182 case SkPath::kCubic_Verb: 183 path->cubicTo(curvePart.fCurve.fCubic[1].asSkPoint(), 184 curvePart.fCurve.fCubic[2].asSkPoint(), end->ptT()); 185 break; 186 default: 187 SkASSERT(0); 188 } 189 return true; 190} 191 192const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const { 193 const SkOpSpanBase* test = &fHead; 194 const SkOpPtT* testPtT; 195 SkPoint pt = this->ptAtT(t); 196 do { 197 testPtT = test->ptT(); 198 if (testPtT->fT == t) { 199 break; 200 } 201 if (!this->match(testPtT, this, t, pt)) { 202 if (t < testPtT->fT) { 203 return nullptr; 204 } 205 continue; 206 } 207 if (!opp) { 208 return testPtT; 209 } 210 const SkOpPtT* loop = testPtT->next(); 211 while (loop != testPtT) { 212 if (loop->segment() == this && loop->fT == t && loop->fPt == pt) { 213 goto foundMatch; 214 } 215 loop = loop->next(); 216 } 217 return nullptr; 218 } while ((test = test->upCast()->next())); 219foundMatch: 220 return opp && !test->contains(opp) ? nullptr : testPtT; 221} 222 223// break the span so that the coincident part does not change the angle of the remainder 224bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) { 225 if (this->contains(newT)) { 226 return true; 227 } 228 this->globalState()->resetAllocatedOpSpan(); 229 FAIL_IF(!between(0, newT, 1)); 230 SkOpPtT* newPtT = this->addT(newT); 231 *startOver |= this->globalState()->allocatedOpSpan(); 232 if (!newPtT) { 233 return false; 234 } 235 newPtT->fPt = this->ptAtT(newT); 236 SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT); 237 if (oppPrev) { 238 // const cast away to change linked list; pt/t values stays unchanged 239 SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test); 240 writableTest->mergeMatches(newPtT->span()); 241 writableTest->ptT()->addOpp(newPtT, oppPrev); 242 writableTest->checkForCollapsedCoincidence(); 243 } 244 return true; 245} 246 247// Please keep this in sync with debugAddT() 248SkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) { 249 debugValidate(); 250 SkOpSpanBase* spanBase = &fHead; 251 do { 252 SkOpPtT* result = spanBase->ptT(); 253 if (t == result->fT || (!zero_or_one(t) && this->match(result, this, t, pt))) { 254 spanBase->bumpSpanAdds(); 255 return result; 256 } 257 if (t < result->fT) { 258 SkOpSpan* prev = result->span()->prev(); 259 FAIL_WITH_NULL_IF(!prev); 260 // marks in global state that new op span has been allocated 261 SkOpSpan* span = this->insert(prev); 262 span->init(this, prev, t, pt); 263 this->debugValidate(); 264#if DEBUG_ADD_T 265 SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, 266 span->segment()->debugID(), span->debugID()); 267#endif 268 span->bumpSpanAdds(); 269 return span->ptT(); 270 } 271 FAIL_WITH_NULL_IF(spanBase == &fTail); 272 } while ((spanBase = spanBase->upCast()->next())); 273 SkASSERT(0); 274 return nullptr; // we never get here, but need this to satisfy compiler 275} 276 277SkOpPtT* SkOpSegment::addT(double t) { 278 return addT(t, this->ptAtT(t)); 279} 280 281void SkOpSegment::calcAngles() { 282 bool activePrior = !fHead.isCanceled(); 283 if (activePrior && !fHead.simple()) { 284 addStartSpan(); 285 } 286 SkOpSpan* prior = &fHead; 287 SkOpSpanBase* spanBase = fHead.next(); 288 while (spanBase != &fTail) { 289 if (activePrior) { 290 SkOpAngle* priorAngle = this->globalState()->allocator()->make<SkOpAngle>(); 291 priorAngle->set(spanBase, prior); 292 spanBase->setFromAngle(priorAngle); 293 } 294 SkOpSpan* span = spanBase->upCast(); 295 bool active = !span->isCanceled(); 296 SkOpSpanBase* next = span->next(); 297 if (active) { 298 SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>(); 299 angle->set(span, next); 300 span->setToAngle(angle); 301 } 302 activePrior = active; 303 prior = span; 304 spanBase = next; 305 } 306 if (activePrior && !fTail.simple()) { 307 addEndSpan(); 308 } 309} 310 311// Please keep this in sync with debugClearAll() 312void SkOpSegment::clearAll() { 313 SkOpSpan* span = &fHead; 314 do { 315 this->clearOne(span); 316 } while ((span = span->next()->upCastable())); 317 this->globalState()->coincidence()->release(this); 318} 319 320// Please keep this in sync with debugClearOne() 321void SkOpSegment::clearOne(SkOpSpan* span) { 322 span->setWindValue(0); 323 span->setOppValue(0); 324 this->markDone(span); 325} 326 327bool SkOpSegment::collapsed(double s, double e) const { 328 const SkOpSpanBase* span = &fHead; 329 do { 330 if (span->collapsed(s, e)) { 331 return true; 332 } 333 } while (span->upCastable() && (span = span->upCast()->next())); 334 return false; 335} 336 337void SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 338 SkOpAngle::IncludeType includeType) { 339 SkOpSegment* baseSegment = baseAngle->segment(); 340 int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); 341 int sumSuWinding; 342 bool binary = includeType >= SkOpAngle::kBinarySingle; 343 if (binary) { 344 sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle); 345 if (baseSegment->operand()) { 346 SkTSwap<int>(sumMiWinding, sumSuWinding); 347 } 348 } 349 SkOpSegment* nextSegment = nextAngle->segment(); 350 int maxWinding, sumWinding; 351 SkOpSpanBase* last; 352 if (binary) { 353 int oppMaxWinding, oppSumWinding; 354 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 355 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 356 last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 357 nextAngle); 358 } else { 359 nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, 360 &maxWinding, &sumWinding); 361 last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 362 } 363 nextAngle->setLastMarked(last); 364} 365 366void SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, 367 SkOpAngle::IncludeType includeType) { 368 SkOpSegment* baseSegment = baseAngle->segment(); 369 int sumMiWinding = baseSegment->updateWinding(baseAngle); 370 int sumSuWinding; 371 bool binary = includeType >= SkOpAngle::kBinarySingle; 372 if (binary) { 373 sumSuWinding = baseSegment->updateOppWinding(baseAngle); 374 if (baseSegment->operand()) { 375 SkTSwap<int>(sumMiWinding, sumSuWinding); 376 } 377 } 378 SkOpSegment* nextSegment = nextAngle->segment(); 379 int maxWinding, sumWinding; 380 SkOpSpanBase* last; 381 if (binary) { 382 int oppMaxWinding, oppSumWinding; 383 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 384 &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); 385 last = nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, 386 nextAngle); 387 } else { 388 nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, 389 &maxWinding, &sumWinding); 390 last = nextSegment->markAngle(maxWinding, sumWinding, nextAngle); 391 } 392 nextAngle->setLastMarked(last); 393} 394 395// at this point, the span is already ordered, or unorderable 396int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end, 397 SkOpAngle::IncludeType includeType) { 398 SkASSERT(includeType != SkOpAngle::kUnaryXor); 399 SkOpAngle* firstAngle = this->spanToAngle(end, start); 400 if (nullptr == firstAngle || nullptr == firstAngle->next()) { 401 return SK_NaN32; 402 } 403 // if all angles have a computed winding, 404 // or if no adjacent angles are orderable, 405 // or if adjacent orderable angles have no computed winding, 406 // there's nothing to do 407 // if two orderable angles are adjacent, and both are next to orderable angles, 408 // and one has winding computed, transfer to the other 409 SkOpAngle* baseAngle = nullptr; 410 bool tryReverse = false; 411 // look for counterclockwise transfers 412 SkOpAngle* angle = firstAngle->previous(); 413 SkOpAngle* next = angle->next(); 414 firstAngle = next; 415 do { 416 SkOpAngle* prior = angle; 417 angle = next; 418 next = angle->next(); 419 SkASSERT(prior->next() == angle); 420 SkASSERT(angle->next() == next); 421 if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 422 baseAngle = nullptr; 423 continue; 424 } 425 int testWinding = angle->starter()->windSum(); 426 if (SK_MinS32 != testWinding) { 427 baseAngle = angle; 428 tryReverse = true; 429 continue; 430 } 431 if (baseAngle) { 432 ComputeOneSum(baseAngle, angle, includeType); 433 baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 434 } 435 } while (next != firstAngle); 436 if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) { 437 firstAngle = baseAngle; 438 tryReverse = true; 439 } 440 if (tryReverse) { 441 baseAngle = nullptr; 442 SkOpAngle* prior = firstAngle; 443 do { 444 angle = prior; 445 prior = angle->previous(); 446 SkASSERT(prior->next() == angle); 447 next = angle->next(); 448 if (prior->unorderable() || angle->unorderable() || next->unorderable()) { 449 baseAngle = nullptr; 450 continue; 451 } 452 int testWinding = angle->starter()->windSum(); 453 if (SK_MinS32 != testWinding) { 454 baseAngle = angle; 455 continue; 456 } 457 if (baseAngle) { 458 ComputeOneSumReverse(baseAngle, angle, includeType); 459 baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; 460 } 461 } while (prior != firstAngle); 462 } 463 return start->starter(end)->windSum(); 464} 465 466bool SkOpSegment::contains(double newT) const { 467 const SkOpSpanBase* spanBase = &fHead; 468 do { 469 if (spanBase->ptT()->contains(this, newT)) { 470 return true; 471 } 472 if (spanBase == &fTail) { 473 break; 474 } 475 spanBase = spanBase->upCast()->next(); 476 } while (true); 477 return false; 478} 479 480void SkOpSegment::release(const SkOpSpan* span) { 481 if (span->done()) { 482 --fDoneCount; 483 } 484 --fCount; 485 SkOPASSERT(fCount >= fDoneCount); 486} 487 488#if DEBUG_ANGLE 489// called only by debugCheckNearCoincidence 490double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const { 491 SkDPoint testPt = this->dPtAtT(t); 492 SkDLine testPerp = {{ testPt, testPt }}; 493 SkDVector slope = this->dSlopeAtT(t); 494 testPerp[1].fX += slope.fY; 495 testPerp[1].fY -= slope.fX; 496 SkIntersections i; 497 const SkOpSegment* oppSegment = oppAngle->segment(); 498 (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i); 499 double closestDistSq = SK_ScalarInfinity; 500 for (int index = 0; index < i.used(); ++index) { 501 if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) { 502 continue; 503 } 504 double testDistSq = testPt.distanceSquared(i.pt(index)); 505 if (closestDistSq > testDistSq) { 506 closestDistSq = testDistSq; 507 } 508 } 509 return closestDistSq; 510} 511#endif 512 513/* 514 The M and S variable name parts stand for the operators. 515 Mi stands for Minuend (see wiki subtraction, analogous to difference) 516 Su stands for Subtrahend 517 The Opp variable name part designates that the value is for the Opposite operator. 518 Opposite values result from combining coincident spans. 519 */ 520SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 521 SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask) { 522 SkOpSpanBase* start = *nextStart; 523 SkOpSpanBase* end = *nextEnd; 524 SkASSERT(start != end); 525 int step = start->step(end); 526 SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 527 if (other) { 528 // mark the smaller of startIndex, endIndex done, and all adjacent 529 // spans with the same T value (but not 'other' spans) 530#if DEBUG_WINDING 531 SkDebugf("%s simple\n", __FUNCTION__); 532#endif 533 SkOpSpan* startSpan = start->starter(end); 534 if (startSpan->done()) { 535 return nullptr; 536 } 537 markDone(startSpan); 538 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 539 return other; 540 } 541 SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 542 SkASSERT(endNear == end); // is this ever not end? 543 SkASSERT(endNear); 544 SkASSERT(start != endNear); 545 SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 546 // more than one viable candidate -- measure angles to find best 547 int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp); 548 bool sortable = calcWinding != SK_NaN32; 549 if (!sortable) { 550 *unsortable = true; 551 markDone(start->starter(end)); 552 return nullptr; 553 } 554 SkOpAngle* angle = this->spanToAngle(end, start); 555 if (angle->unorderable()) { 556 *unsortable = true; 557 markDone(start->starter(end)); 558 return nullptr; 559 } 560#if DEBUG_SORT 561 SkDebugf("%s\n", __FUNCTION__); 562 angle->debugLoop(); 563#endif 564 int sumMiWinding = updateWinding(end, start); 565 if (sumMiWinding == SK_MinS32) { 566 *unsortable = true; 567 markDone(start->starter(end)); 568 return nullptr; 569 } 570 int sumSuWinding = updateOppWinding(end, start); 571 if (operand()) { 572 SkTSwap<int>(sumMiWinding, sumSuWinding); 573 } 574 SkOpAngle* nextAngle = angle->next(); 575 const SkOpAngle* foundAngle = nullptr; 576 bool foundDone = false; 577 // iterate through the angle, and compute everyone's winding 578 SkOpSegment* nextSegment; 579 int activeCount = 0; 580 do { 581 nextSegment = nextAngle->segment(); 582 bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), 583 nextAngle->end(), op, &sumMiWinding, &sumSuWinding); 584 if (activeAngle) { 585 ++activeCount; 586 if (!foundAngle || (foundDone && activeCount & 1)) { 587 foundAngle = nextAngle; 588 foundDone = nextSegment->done(nextAngle); 589 } 590 } 591 if (nextSegment->done()) { 592 continue; 593 } 594 if (!activeAngle) { 595 (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 596 } 597 SkOpSpanBase* last = nextAngle->lastMarked(); 598 if (last) { 599 SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 600 *chase->append() = last; 601#if DEBUG_WINDING 602 SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 603 last->segment()->debugID(), last->debugID()); 604 if (!last->final()) { 605 SkDebugf(" windSum=%d", last->upCast()->windSum()); 606 } 607 SkDebugf("\n"); 608#endif 609 } 610 } while ((nextAngle = nextAngle->next()) != angle); 611 start->segment()->markDone(start->starter(end)); 612 if (!foundAngle) { 613 return nullptr; 614 } 615 *nextStart = foundAngle->start(); 616 *nextEnd = foundAngle->end(); 617 nextSegment = foundAngle->segment(); 618#if DEBUG_WINDING 619 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 620 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 621 #endif 622 return nextSegment; 623} 624 625SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase, 626 SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) { 627 SkOpSpanBase* start = *nextStart; 628 SkOpSpanBase* end = *nextEnd; 629 SkASSERT(start != end); 630 int step = start->step(end); 631 SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 632 if (other) { 633 // mark the smaller of startIndex, endIndex done, and all adjacent 634 // spans with the same T value (but not 'other' spans) 635#if DEBUG_WINDING 636 SkDebugf("%s simple\n", __FUNCTION__); 637#endif 638 SkOpSpan* startSpan = start->starter(end); 639 if (startSpan->done()) { 640 return nullptr; 641 } 642 markDone(startSpan); 643 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 644 return other; 645 } 646 SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 647 SkASSERT(endNear == end); // is this ever not end? 648 SkASSERT(endNear); 649 SkASSERT(start != endNear); 650 SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 651 // more than one viable candidate -- measure angles to find best 652 int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding); 653 bool sortable = calcWinding != SK_NaN32; 654 if (!sortable) { 655 *unsortable = true; 656 markDone(start->starter(end)); 657 return nullptr; 658 } 659 SkOpAngle* angle = this->spanToAngle(end, start); 660 if (angle->unorderable()) { 661 *unsortable = true; 662 markDone(start->starter(end)); 663 return nullptr; 664 } 665#if DEBUG_SORT 666 SkDebugf("%s\n", __FUNCTION__); 667 angle->debugLoop(); 668#endif 669 int sumWinding = updateWinding(end, start); 670 SkOpAngle* nextAngle = angle->next(); 671 const SkOpAngle* foundAngle = nullptr; 672 bool foundDone = false; 673 // iterate through the angle, and compute everyone's winding 674 SkOpSegment* nextSegment; 675 int activeCount = 0; 676 do { 677 nextSegment = nextAngle->segment(); 678 bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), 679 &sumWinding); 680 if (activeAngle) { 681 ++activeCount; 682 if (!foundAngle || (foundDone && activeCount & 1)) { 683 foundAngle = nextAngle; 684 foundDone = nextSegment->done(nextAngle); 685 } 686 } 687 if (nextSegment->done()) { 688 continue; 689 } 690 if (!activeAngle) { 691 (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end()); 692 } 693 SkOpSpanBase* last = nextAngle->lastMarked(); 694 if (last) { 695 SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); 696 *chase->append() = last; 697#if DEBUG_WINDING 698 SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, 699 last->segment()->debugID(), last->debugID()); 700 if (!last->final()) { 701 SkDebugf(" windSum=%d", last->upCast()->windSum()); 702 } 703 SkDebugf("\n"); 704#endif 705 } 706 } while ((nextAngle = nextAngle->next()) != angle); 707 start->segment()->markDone(start->starter(end)); 708 if (!foundAngle) { 709 return nullptr; 710 } 711 *nextStart = foundAngle->start(); 712 *nextEnd = foundAngle->end(); 713 nextSegment = foundAngle->segment(); 714#if DEBUG_WINDING 715 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 716 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 717 #endif 718 return nextSegment; 719} 720 721SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, 722 bool* unsortable) { 723 SkOpSpanBase* start = *nextStart; 724 SkOpSpanBase* end = *nextEnd; 725 SkASSERT(start != end); 726 int step = start->step(end); 727 SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart 728 if (other) { 729 // mark the smaller of startIndex, endIndex done, and all adjacent 730 // spans with the same T value (but not 'other' spans) 731#if DEBUG_WINDING 732 SkDebugf("%s simple\n", __FUNCTION__); 733#endif 734 SkOpSpan* startSpan = start->starter(end); 735 if (startSpan->done()) { 736 return nullptr; 737 } 738 markDone(startSpan); 739 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); 740 return other; 741 } 742 SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \ 743 : (*nextStart)->prev()); 744 SkASSERT(endNear == end); // is this ever not end? 745 SkASSERT(endNear); 746 SkASSERT(start != endNear); 747 SkASSERT((start->t() < endNear->t()) ^ (step < 0)); 748 SkOpAngle* angle = this->spanToAngle(end, start); 749 if (!angle || angle->unorderable()) { 750 *unsortable = true; 751 markDone(start->starter(end)); 752 return nullptr; 753 } 754#if DEBUG_SORT 755 SkDebugf("%s\n", __FUNCTION__); 756 angle->debugLoop(); 757#endif 758 SkOpAngle* nextAngle = angle->next(); 759 const SkOpAngle* foundAngle = nullptr; 760 bool foundDone = false; 761 // iterate through the angle, and compute everyone's winding 762 SkOpSegment* nextSegment; 763 int activeCount = 0; 764 do { 765 nextSegment = nextAngle->segment(); 766 ++activeCount; 767 if (!foundAngle || (foundDone && activeCount & 1)) { 768 foundAngle = nextAngle; 769 if (!(foundDone = nextSegment->done(nextAngle))) { 770 break; 771 } 772 } 773 nextAngle = nextAngle->next(); 774 } while (nextAngle != angle); 775 start->segment()->markDone(start->starter(end)); 776 if (!foundAngle) { 777 return nullptr; 778 } 779 *nextStart = foundAngle->start(); 780 *nextEnd = foundAngle->end(); 781 nextSegment = foundAngle->segment(); 782#if DEBUG_WINDING 783 SkDebugf("%s from:[%d] to:[%d] start=%d end=%d\n", 784 __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); 785 #endif 786 return nextSegment; 787} 788 789SkOpGlobalState* SkOpSegment::globalState() const { 790 return contour()->globalState(); 791} 792 793void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) { 794 fContour = contour; 795 fNext = nullptr; 796 fPts = pts; 797 fWeight = weight; 798 fVerb = verb; 799 fCount = 0; 800 fDoneCount = 0; 801 fVisited = false; 802 SkOpSpan* zeroSpan = &fHead; 803 zeroSpan->init(this, nullptr, 0, fPts[0]); 804 SkOpSpanBase* oneSpan = &fTail; 805 zeroSpan->setNext(oneSpan); 806 oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]); 807 SkDEBUGCODE(fID = globalState()->nextSegmentID()); 808} 809 810bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { 811 SkDPoint cPt = this->dPtAtT(t); 812 SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t); 813 SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 814 SkIntersections i; 815 (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i); 816 int used = i.used(); 817 for (int index = 0; index < used; ++index) { 818 if (cPt.roughlyEqual(i.pt(index))) { 819 return true; 820 } 821 } 822 return false; 823} 824 825bool SkOpSegment::isXor() const { 826 return fContour->isXor(); 827} 828 829void SkOpSegment::markAllDone() { 830 SkOpSpan* span = this->head(); 831 do { 832 this->markDone(span); 833 } while ((span = span->next()->upCastable())); 834} 835 836SkOpSpanBase* SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end) { 837 int step = start->step(end); 838 SkOpSpan* minSpan = start->starter(end); 839 markDone(minSpan); 840 SkOpSpanBase* last = nullptr; 841 SkOpSegment* other = this; 842 SkOpSpan* priorDone = nullptr; 843 SkOpSpan* lastDone = nullptr; 844 while ((other = other->nextChase(&start, &step, &minSpan, &last))) { 845 if (other->done()) { 846 SkASSERT(!last); 847 break; 848 } 849 if (lastDone == minSpan || priorDone == minSpan) { 850 return nullptr; 851 } 852 other->markDone(minSpan); 853 priorDone = lastDone; 854 lastDone = minSpan; 855 } 856 return last; 857} 858 859bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 860 SkOpSpanBase** lastPtr) { 861 SkOpSpan* spanStart = start->starter(end); 862 int step = start->step(end); 863 bool success = markWinding(spanStart, winding); 864 SkOpSpanBase* last = nullptr; 865 SkOpSegment* other = this; 866 while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 867 if (spanStart->windSum() != SK_MinS32) { 868// SkASSERT(spanStart->windSum() == winding); // FIXME: is this assert too aggressive? 869 SkASSERT(!last); 870 break; 871 } 872 (void) other->markWinding(spanStart, winding); 873 } 874 if (lastPtr) { 875 *lastPtr = last; 876 } 877 return success; 878} 879 880bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, 881 int winding, int oppWinding, SkOpSpanBase** lastPtr) { 882 SkOpSpan* spanStart = start->starter(end); 883 int step = start->step(end); 884 bool success = markWinding(spanStart, winding, oppWinding); 885 SkOpSpanBase* last = nullptr; 886 SkOpSegment* other = this; 887 while ((other = other->nextChase(&start, &step, &spanStart, &last))) { 888 if (spanStart->windSum() != SK_MinS32) { 889 if (this->operand() == other->operand()) { 890 if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) { 891 this->globalState()->setWindingFailed(); 892 return false; 893 } 894 } else { 895 SkASSERT(spanStart->windSum() == oppWinding); 896 SkASSERT(spanStart->oppSum() == winding); 897 } 898 SkASSERT(!last); 899 break; 900 } 901 if (this->operand() == other->operand()) { 902 (void) other->markWinding(spanStart, winding, oppWinding); 903 } else { 904 (void) other->markWinding(spanStart, oppWinding, winding); 905 } 906 } 907 if (lastPtr) { 908 *lastPtr = last; 909 } 910 return success; 911} 912 913SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle) { 914 SkASSERT(angle->segment() == this); 915 if (UseInnerWinding(maxWinding, sumWinding)) { 916 maxWinding = sumWinding; 917 } 918 SkOpSpanBase* last; 919 (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, &last); 920#if DEBUG_WINDING 921 if (last) { 922 SkDebugf("%s last seg=%d span=%d", __FUNCTION__, 923 last->segment()->debugID(), last->debugID()); 924 if (!last->final()) { 925 SkDebugf(" windSum="); 926 SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 927 } 928 SkDebugf("\n"); 929 } 930#endif 931 return last; 932} 933 934SkOpSpanBase* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding, 935 int oppSumWinding, const SkOpAngle* angle) { 936 SkASSERT(angle->segment() == this); 937 if (UseInnerWinding(maxWinding, sumWinding)) { 938 maxWinding = sumWinding; 939 } 940 if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) { 941 oppMaxWinding = oppSumWinding; 942 } 943 SkOpSpanBase* last = nullptr; 944 // caller doesn't require that this marks anything 945 (void) markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, &last); 946#if DEBUG_WINDING 947 if (last) { 948 SkDebugf("%s last segment=%d span=%d", __FUNCTION__, 949 last->segment()->debugID(), last->debugID()); 950 if (!last->final()) { 951 SkDebugf(" windSum="); 952 SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); 953 } 954 SkDebugf(" \n"); 955 } 956#endif 957 return last; 958} 959 960void SkOpSegment::markDone(SkOpSpan* span) { 961 SkASSERT(this == span->segment()); 962 if (span->done()) { 963 return; 964 } 965#if DEBUG_MARK_DONE 966 debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum()); 967#endif 968 span->setDone(true); 969 ++fDoneCount; 970 debugValidate(); 971} 972 973bool SkOpSegment::markWinding(SkOpSpan* span, int winding) { 974 SkASSERT(this == span->segment()); 975 SkASSERT(winding); 976 if (span->done()) { 977 return false; 978 } 979#if DEBUG_MARK_DONE 980 debugShowNewWinding(__FUNCTION__, span, winding); 981#endif 982 span->setWindSum(winding); 983 debugValidate(); 984 return true; 985} 986 987bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { 988 SkASSERT(this == span->segment()); 989 SkASSERT(winding || oppWinding); 990 if (span->done()) { 991 return false; 992 } 993#if DEBUG_MARK_DONE 994 debugShowNewWinding(__FUNCTION__, span, winding, oppWinding); 995#endif 996 span->setWindSum(winding); 997 span->setOppSum(oppWinding); 998 debugValidate(); 999 return true; 1000} 1001 1002bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT, 1003 const SkPoint& testPt) const { 1004 SkASSERT(this == base->segment()); 1005 if (this == testParent) { 1006 if (precisely_equal(base->fT, testT)) { 1007 return true; 1008 } 1009 } 1010 if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) { 1011 return false; 1012 } 1013 return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt); 1014} 1015 1016static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { 1017 if (last) { 1018 *last = endSpan; 1019 } 1020 return nullptr; 1021} 1022 1023SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr, 1024 SkOpSpanBase** last) const { 1025 SkOpSpanBase* origStart = *startPtr; 1026 int step = *stepPtr; 1027 SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev(); 1028 SkASSERT(endSpan); 1029 SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle(); 1030 SkOpSpanBase* foundSpan; 1031 SkOpSpanBase* otherEnd; 1032 SkOpSegment* other; 1033 if (angle == nullptr) { 1034 if (endSpan->t() != 0 && endSpan->t() != 1) { 1035 return nullptr; 1036 } 1037 SkOpPtT* otherPtT = endSpan->ptT()->next(); 1038 other = otherPtT->segment(); 1039 foundSpan = otherPtT->span(); 1040 otherEnd = step > 0 1041 ? foundSpan->upCastable() ? foundSpan->upCast()->next() : nullptr 1042 : foundSpan->prev(); 1043 } else { 1044 int loopCount = angle->loopCount(); 1045 if (loopCount > 2) { 1046 return set_last(last, endSpan); 1047 } 1048 const SkOpAngle* next = angle->next(); 1049 if (nullptr == next) { 1050 return nullptr; 1051 } 1052#if DEBUG_WINDING 1053 if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor() 1054 && !next->segment()->contour()->isXor()) { 1055 SkDebugf("%s mismatched signs\n", __FUNCTION__); 1056 } 1057#endif 1058 other = next->segment(); 1059 foundSpan = endSpan = next->start(); 1060 otherEnd = next->end(); 1061 } 1062 if (!otherEnd) { 1063 return nullptr; 1064 } 1065 int foundStep = foundSpan->step(otherEnd); 1066 if (*stepPtr != foundStep) { 1067 return set_last(last, endSpan); 1068 } 1069 SkASSERT(*startPtr); 1070// SkASSERT(otherEnd >= 0); 1071 SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast(); 1072 SkOpSpan* foundMin = foundSpan->starter(otherEnd); 1073 if (foundMin->windValue() != origMin->windValue() 1074 || foundMin->oppValue() != origMin->oppValue()) { 1075 return set_last(last, endSpan); 1076 } 1077 *startPtr = foundSpan; 1078 *stepPtr = foundStep; 1079 if (minPtr) { 1080 *minPtr = foundMin; 1081 } 1082 return other; 1083} 1084 1085// Please keep this in sync with DebugClearVisited() 1086void SkOpSegment::ClearVisited(SkOpSpanBase* span) { 1087 // reset visited flag back to false 1088 do { 1089 SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 1090 while ((ptT = ptT->next()) != stopPtT) { 1091 SkOpSegment* opp = ptT->segment(); 1092 opp->resetVisited(); 1093 } 1094 } while (!span->final() && (span = span->upCast()->next())); 1095} 1096 1097// Please keep this in sync with debugMissingCoincidence() 1098// look for pairs of undetected coincident curves 1099// assumes that segments going in have visited flag clear 1100// Even though pairs of curves correct detect coincident runs, a run may be missed 1101// if the coincidence is a product of multiple intersections. For instance, given 1102// curves A, B, and C: 1103// A-B intersect at a point 1; A-C and B-C intersect at point 2, so near 1104// the end of C that the intersection is replaced with the end of C. 1105// Even though A-B correctly do not detect an intersection at point 2, 1106// the resulting run from point 1 to point 2 is coincident on A and B. 1107bool SkOpSegment::missingCoincidence() { 1108 if (this->done()) { 1109 return false; 1110 } 1111 SkOpSpan* prior = nullptr; 1112 SkOpSpanBase* spanBase = &fHead; 1113 bool result = false; 1114 do { 1115 SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; 1116 SkOPASSERT(ptT->span() == spanBase); 1117 while ((ptT = ptT->next()) != spanStopPtT) { 1118 if (ptT->deleted()) { 1119 continue; 1120 } 1121 SkOpSegment* opp = ptT->span()->segment(); 1122 if (opp->done()) { 1123 continue; 1124 } 1125 // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence 1126 if (!opp->visited()) { 1127 continue; 1128 } 1129 if (spanBase == &fHead) { 1130 continue; 1131 } 1132 if (ptT->segment() == this) { 1133 continue; 1134 } 1135 SkOpSpan* span = spanBase->upCastable(); 1136 // FIXME?: this assumes that if the opposite segment is coincident then no more 1137 // coincidence needs to be detected. This may not be true. 1138 if (span && span->containsCoincidence(opp)) { 1139 continue; 1140 } 1141 if (spanBase->containsCoinEnd(opp)) { 1142 continue; 1143 } 1144 SkOpPtT* priorPtT = nullptr, * priorStopPtT; 1145 // find prior span containing opp segment 1146 SkOpSegment* priorOpp = nullptr; 1147 SkOpSpan* priorTest = spanBase->prev(); 1148 while (!priorOpp && priorTest) { 1149 priorStopPtT = priorPtT = priorTest->ptT(); 1150 while ((priorPtT = priorPtT->next()) != priorStopPtT) { 1151 if (priorPtT->deleted()) { 1152 continue; 1153 } 1154 SkOpSegment* segment = priorPtT->span()->segment(); 1155 if (segment == opp) { 1156 prior = priorTest; 1157 priorOpp = opp; 1158 break; 1159 } 1160 } 1161 priorTest = priorTest->prev(); 1162 } 1163 if (!priorOpp) { 1164 continue; 1165 } 1166 if (priorPtT == ptT) { 1167 continue; 1168 } 1169 SkOpPtT* oppStart = prior->ptT(); 1170 SkOpPtT* oppEnd = spanBase->ptT(); 1171 bool swapped = priorPtT->fT > ptT->fT; 1172 if (swapped) { 1173 SkTSwap(priorPtT, ptT); 1174 SkTSwap(oppStart, oppEnd); 1175 } 1176 SkOpCoincidence* coincidences = this->globalState()->coincidence(); 1177 SkOpPtT* rootPriorPtT = priorPtT->span()->ptT(); 1178 SkOpPtT* rootPtT = ptT->span()->ptT(); 1179 SkOpPtT* rootOppStart = oppStart->span()->ptT(); 1180 SkOpPtT* rootOppEnd = oppEnd->span()->ptT(); 1181 if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { 1182 goto swapBack; 1183 } 1184 if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) { 1185 // mark coincidence 1186#if DEBUG_COINCIDENCE_VERBOSE 1187 SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__, 1188 rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(), 1189 rootOppEnd->debugID()); 1190#endif 1191 if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { 1192 coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd); 1193 } 1194#if DEBUG_COINCIDENCE 1195 SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)); 1196#endif 1197 result = true; 1198 } 1199 swapBack: 1200 if (swapped) { 1201 SkTSwap(priorPtT, ptT); 1202 } 1203 } 1204 } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); 1205 ClearVisited(&fHead); 1206 return result; 1207} 1208 1209// please keep this in sync with debugMoveMultiples() 1210// if a span has more than one intersection, merge the other segments' span as needed 1211bool SkOpSegment::moveMultiples() { 1212 debugValidate(); 1213 SkOpSpanBase* test = &fHead; 1214 do { 1215 int addCount = test->spanAddsCount(); 1216// FAIL_IF(addCount < 1); 1217 if (addCount <= 1) { 1218 continue; 1219 } 1220 SkOpPtT* startPtT = test->ptT(); 1221 SkOpPtT* testPtT = startPtT; 1222 do { // iterate through all spans associated with start 1223 SkOpSpanBase* oppSpan = testPtT->span(); 1224 if (oppSpan->spanAddsCount() == addCount) { 1225 continue; 1226 } 1227 if (oppSpan->deleted()) { 1228 continue; 1229 } 1230 SkOpSegment* oppSegment = oppSpan->segment(); 1231 if (oppSegment == this) { 1232 continue; 1233 } 1234 // find range of spans to consider merging 1235 SkOpSpanBase* oppPrev = oppSpan; 1236 SkOpSpanBase* oppFirst = oppSpan; 1237 while ((oppPrev = oppPrev->prev())) { 1238 if (!roughly_equal(oppPrev->t(), oppSpan->t())) { 1239 break; 1240 } 1241 if (oppPrev->spanAddsCount() == addCount) { 1242 continue; 1243 } 1244 if (oppPrev->deleted()) { 1245 continue; 1246 } 1247 oppFirst = oppPrev; 1248 } 1249 SkOpSpanBase* oppNext = oppSpan; 1250 SkOpSpanBase* oppLast = oppSpan; 1251 while ((oppNext = oppNext->final() ? nullptr : oppNext->upCast()->next())) { 1252 if (!roughly_equal(oppNext->t(), oppSpan->t())) { 1253 break; 1254 } 1255 if (oppNext->spanAddsCount() == addCount) { 1256 continue; 1257 } 1258 if (oppNext->deleted()) { 1259 continue; 1260 } 1261 oppLast = oppNext; 1262 } 1263 if (oppFirst == oppLast) { 1264 continue; 1265 } 1266 SkOpSpanBase* oppTest = oppFirst; 1267 do { 1268 if (oppTest == oppSpan) { 1269 continue; 1270 } 1271 // check to see if the candidate meets specific criteria: 1272 // it contains spans of segments in test's loop but not including 'this' 1273 SkOpPtT* oppStartPtT = oppTest->ptT(); 1274 SkOpPtT* oppPtT = oppStartPtT; 1275 while ((oppPtT = oppPtT->next()) != oppStartPtT) { 1276 SkOpSegment* oppPtTSegment = oppPtT->segment(); 1277 if (oppPtTSegment == this) { 1278 goto tryNextSpan; 1279 } 1280 SkOpPtT* matchPtT = startPtT; 1281 do { 1282 if (matchPtT->segment() == oppPtTSegment) { 1283 goto foundMatch; 1284 } 1285 } while ((matchPtT = matchPtT->next()) != startPtT); 1286 goto tryNextSpan; 1287 foundMatch: // merge oppTest and oppSpan 1288 oppSegment->debugValidate(); 1289 oppTest->mergeMatches(oppSpan); 1290 oppTest->addOpp(oppSpan); 1291 oppSegment->debugValidate(); 1292 goto checkNextSpan; 1293 } 1294 tryNextSpan: 1295 ; 1296 } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); 1297 } while ((testPtT = testPtT->next()) != startPtT); 1298checkNextSpan: 1299 ; 1300 } while ((test = test->final() ? nullptr : test->upCast()->next())); 1301 debugValidate(); 1302 return true; 1303} 1304 1305// adjacent spans may have points close by 1306bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan, 1307 bool* found) const { 1308 const SkOpPtT* refHead = refSpan->ptT(); 1309 const SkOpPtT* checkHead = checkSpan->ptT(); 1310// if the first pt pair from adjacent spans are far apart, assume that all are far enough apart 1311 if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) { 1312#if DEBUG_COINCIDENCE 1313 // verify that no combination of points are close 1314 const SkOpPtT* dBugRef = refHead; 1315 do { 1316 const SkOpPtT* dBugCheck = checkHead; 1317 do { 1318 SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt)); 1319 dBugCheck = dBugCheck->next(); 1320 } while (dBugCheck != checkHead); 1321 dBugRef = dBugRef->next(); 1322 } while (dBugRef != refHead); 1323#endif 1324 *found = false; 1325 return true; 1326 } 1327 // check only unique points 1328 SkScalar distSqBest = SK_ScalarMax; 1329 const SkOpPtT* refBest = nullptr; 1330 const SkOpPtT* checkBest = nullptr; 1331 const SkOpPtT* ref = refHead; 1332 do { 1333 if (ref->deleted()) { 1334 continue; 1335 } 1336 while (ref->ptAlreadySeen(refHead)) { 1337 ref = ref->next(); 1338 if (ref == refHead) { 1339 goto doneCheckingDistance; 1340 } 1341 } 1342 const SkOpPtT* check = checkHead; 1343 const SkOpSegment* refSeg = ref->segment(); 1344 int escapeHatch = 100000; // defend against infinite loops 1345 do { 1346 if (check->deleted()) { 1347 continue; 1348 } 1349 while (check->ptAlreadySeen(checkHead)) { 1350 check = check->next(); 1351 if (check == checkHead) { 1352 goto nextRef; 1353 } 1354 } 1355 SkScalar distSq = SkPointPriv::DistanceToSqd(ref->fPt, check->fPt); 1356 if (distSqBest > distSq && (refSeg != check->segment() 1357 || !refSeg->ptsDisjoint(*ref, *check))) { 1358 distSqBest = distSq; 1359 refBest = ref; 1360 checkBest = check; 1361 } 1362 if (--escapeHatch <= 0) { 1363 return false; 1364 } 1365 } while ((check = check->next()) != checkHead); 1366 nextRef: 1367 ; 1368 } while ((ref = ref->next()) != refHead); 1369doneCheckingDistance: 1370 *found = checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT, 1371 checkBest->fPt); 1372 return true; 1373} 1374 1375// Please keep this function in sync with debugMoveNearby() 1376// Move nearby t values and pts so they all hang off the same span. Alignment happens later. 1377bool SkOpSegment::moveNearby() { 1378 debugValidate(); 1379 // release undeleted spans pointing to this seg that are linked to the primary span 1380 SkOpSpanBase* spanBase = &fHead; 1381 int escapeHatch = 9999; // the largest count for a regular test is 50; for a fuzzer, 500 1382 do { 1383 SkOpPtT* ptT = spanBase->ptT(); 1384 const SkOpPtT* headPtT = ptT; 1385 while ((ptT = ptT->next()) != headPtT) { 1386 if (!--escapeHatch) { 1387 return false; 1388 } 1389 SkOpSpanBase* test = ptT->span(); 1390 if (ptT->segment() == this && !ptT->deleted() && test != spanBase 1391 && test->ptT() == ptT) { 1392 if (test->final()) { 1393 if (spanBase == &fHead) { 1394 this->clearAll(); 1395 return true; 1396 } 1397 spanBase->upCast()->release(ptT); 1398 } else if (test->prev()) { 1399 test->upCast()->release(headPtT); 1400 } 1401 break; 1402 } 1403 } 1404 spanBase = spanBase->upCast()->next(); 1405 } while (!spanBase->final()); 1406 // This loop looks for adjacent spans which are near by 1407 spanBase = &fHead; 1408 do { // iterate through all spans associated with start 1409 SkOpSpanBase* test = spanBase->upCast()->next(); 1410 bool found; 1411 if (!this->spansNearby(spanBase, test, &found)) { 1412 return false; 1413 } 1414 if (found) { 1415 if (test->final()) { 1416 if (spanBase->prev()) { 1417 test->merge(spanBase->upCast()); 1418 } else { 1419 this->clearAll(); 1420 return true; 1421 } 1422 } else { 1423 spanBase->merge(test->upCast()); 1424 } 1425 } 1426 spanBase = test; 1427 } while (!spanBase->final()); 1428 debugValidate(); 1429 return true; 1430} 1431 1432bool SkOpSegment::operand() const { 1433 return fContour->operand(); 1434} 1435 1436bool SkOpSegment::oppXor() const { 1437 return fContour->oppXor(); 1438} 1439 1440bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const { 1441 if (fVerb == SkPath::kLine_Verb) { 1442 return false; 1443 } 1444 // quads (and cubics) can loop back to nearly a line so that an opposite curve 1445 // hits in two places with very different t values. 1446 // OPTIMIZATION: curves could be preflighted so that, for example, something like 1447 // 'controls contained by ends' could avoid this check for common curves 1448 // 'ends are extremes in x or y' is cheaper to compute and real-world common 1449 // on the other hand, the below check is relatively inexpensive 1450 double midT = (t1 + t2) / 2; 1451 SkPoint midPt = this->ptAtT(midT); 1452 double seDistSq = SkTMax(SkPointPriv::DistanceToSqd(pt1, pt2) * 2, FLT_EPSILON * 2); 1453 return SkPointPriv::DistanceToSqd(midPt, pt1) > seDistSq || 1454 SkPointPriv::DistanceToSqd(midPt, pt2) > seDistSq; 1455} 1456 1457void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 1458 int* maxWinding, int* sumWinding) { 1459 int deltaSum = SpanSign(start, end); 1460 *maxWinding = *sumMiWinding; 1461 *sumWinding = *sumMiWinding -= deltaSum; 1462 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 1463} 1464 1465void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 1466 int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, 1467 int* oppSumWinding) { 1468 int deltaSum = SpanSign(start, end); 1469 int oppDeltaSum = OppSign(start, end); 1470 if (operand()) { 1471 *maxWinding = *sumSuWinding; 1472 *sumWinding = *sumSuWinding -= deltaSum; 1473 *oppMaxWinding = *sumMiWinding; 1474 *oppSumWinding = *sumMiWinding -= oppDeltaSum; 1475 } else { 1476 *maxWinding = *sumMiWinding; 1477 *sumWinding = *sumMiWinding -= deltaSum; 1478 *oppMaxWinding = *sumSuWinding; 1479 *oppSumWinding = *sumSuWinding -= oppDeltaSum; 1480 } 1481 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); 1482 SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM); 1483} 1484 1485bool SkOpSegment::sortAngles() { 1486 SkOpSpanBase* span = &this->fHead; 1487 do { 1488 SkOpAngle* fromAngle = span->fromAngle(); 1489 SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle(); 1490 if (!fromAngle && !toAngle) { 1491 continue; 1492 } 1493#if DEBUG_ANGLE 1494 bool wroteAfterHeader = false; 1495#endif 1496 SkOpAngle* baseAngle = fromAngle; 1497 if (fromAngle && toAngle) { 1498#if DEBUG_ANGLE 1499 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(), 1500 span->debugID()); 1501 wroteAfterHeader = true; 1502#endif 1503 FAIL_IF(!fromAngle->insert(toAngle)); 1504 } else if (!fromAngle) { 1505 baseAngle = toAngle; 1506 } 1507 SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; 1508 do { 1509 SkOpSpanBase* oSpan = ptT->span(); 1510 if (oSpan == span) { 1511 continue; 1512 } 1513 SkOpAngle* oAngle = oSpan->fromAngle(); 1514 if (oAngle) { 1515#if DEBUG_ANGLE 1516 if (!wroteAfterHeader) { 1517 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 1518 span->t(), span->debugID()); 1519 wroteAfterHeader = true; 1520 } 1521#endif 1522 if (!oAngle->loopContains(baseAngle)) { 1523 baseAngle->insert(oAngle); 1524 } 1525 } 1526 if (!oSpan->final()) { 1527 oAngle = oSpan->upCast()->toAngle(); 1528 if (oAngle) { 1529#if DEBUG_ANGLE 1530 if (!wroteAfterHeader) { 1531 SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), 1532 span->t(), span->debugID()); 1533 wroteAfterHeader = true; 1534 } 1535#endif 1536 if (!oAngle->loopContains(baseAngle)) { 1537 baseAngle->insert(oAngle); 1538 } 1539 } 1540 } 1541 } while ((ptT = ptT->next()) != stopPtT); 1542 if (baseAngle->loopCount() == 1) { 1543 span->setFromAngle(nullptr); 1544 if (toAngle) { 1545 span->upCast()->setToAngle(nullptr); 1546 } 1547 baseAngle = nullptr; 1548 } 1549#if DEBUG_SORT 1550 SkASSERT(!baseAngle || baseAngle->loopCount() > 1); 1551#endif 1552 } while (!span->final() && (span = span->upCast()->next())); 1553 return true; 1554} 1555 1556bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, 1557 SkDCurve* edge) const { 1558 SkASSERT(start != end); 1559 const SkOpPtT& startPtT = *start->ptT(); 1560 const SkOpPtT& endPtT = *end->ptT(); 1561 SkDEBUGCODE(edge->fVerb = fVerb); 1562 edge->fCubic[0].set(startPtT.fPt); 1563 int points = SkPathOpsVerbToPoints(fVerb); 1564 edge->fCubic[points].set(endPtT.fPt); 1565 if (fVerb == SkPath::kLine_Verb) { 1566 return false; 1567 } 1568 double startT = startPtT.fT; 1569 double endT = endPtT.fT; 1570 if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { 1571 // don't compute midpoints if we already have them 1572 if (fVerb == SkPath::kQuad_Verb) { 1573 edge->fLine[1].set(fPts[1]); 1574 return false; 1575 } 1576 if (fVerb == SkPath::kConic_Verb) { 1577 edge->fConic[1].set(fPts[1]); 1578 edge->fConic.fWeight = fWeight; 1579 return false; 1580 } 1581 SkASSERT(fVerb == SkPath::kCubic_Verb); 1582 if (startT == 0) { 1583 edge->fCubic[1].set(fPts[1]); 1584 edge->fCubic[2].set(fPts[2]); 1585 return false; 1586 } 1587 edge->fCubic[1].set(fPts[2]); 1588 edge->fCubic[2].set(fPts[1]); 1589 return false; 1590 } 1591 if (fVerb == SkPath::kQuad_Verb) { 1592 edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT); 1593 } else if (fVerb == SkPath::kConic_Verb) { 1594 edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2], 1595 startT, endT, &edge->fConic.fWeight); 1596 } else { 1597 SkASSERT(fVerb == SkPath::kCubic_Verb); 1598 SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]); 1599 } 1600 return true; 1601} 1602 1603bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, 1604 const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const { 1605 // average t, find mid pt 1606 double midT = (prior->t() + spanBase->t()) / 2; 1607 SkPoint midPt = this->ptAtT(midT); 1608 bool coincident = true; 1609 // if the mid pt is not near either end pt, project perpendicular through opp seg 1610 if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) 1611 && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { 1612 if (priorPtT->span() == ptT->span()) { 1613 return false; 1614 } 1615 coincident = false; 1616 SkIntersections i; 1617 SkDCurve curvePart; 1618 this->subDivide(prior, spanBase, &curvePart); 1619 SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f); 1620 SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f); 1621 SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}}; 1622 SkDCurve oppPart; 1623 opp->subDivide(priorPtT->span(), ptT->span(), &oppPart); 1624 (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i); 1625 // measure distance and see if it's small enough to denote coincidence 1626 for (int index = 0; index < i.used(); ++index) { 1627 if (!between(0, i[0][index], 1)) { 1628 continue; 1629 } 1630 SkDPoint oppPt = i.pt(index); 1631 if (oppPt.approximatelyDEqual(midPt)) { 1632 // the coincidence can occur at almost any angle 1633 coincident = true; 1634 } 1635 } 1636 } 1637 return coincident; 1638} 1639 1640SkOpSpan* SkOpSegment::undoneSpan() { 1641 SkOpSpan* span = &fHead; 1642 SkOpSpanBase* next; 1643 do { 1644 next = span->next(); 1645 if (!span->done()) { 1646 return span; 1647 } 1648 } while (!next->final() && (span = next->upCast())); 1649 return nullptr; 1650} 1651 1652int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { 1653 const SkOpSpan* lesser = start->starter(end); 1654 int oppWinding = lesser->oppSum(); 1655 int oppSpanWinding = SkOpSegment::OppSign(start, end); 1656 if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding) 1657 && oppWinding != SK_MaxS32) { 1658 oppWinding -= oppSpanWinding; 1659 } 1660 return oppWinding; 1661} 1662 1663int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { 1664 const SkOpSpanBase* startSpan = angle->start(); 1665 const SkOpSpanBase* endSpan = angle->end(); 1666 return updateOppWinding(endSpan, startSpan); 1667} 1668 1669int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { 1670 const SkOpSpanBase* startSpan = angle->start(); 1671 const SkOpSpanBase* endSpan = angle->end(); 1672 return updateOppWinding(startSpan, endSpan); 1673} 1674 1675int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { 1676 SkOpSpan* lesser = start->starter(end); 1677 int winding = lesser->windSum(); 1678 if (winding == SK_MinS32) { 1679 winding = lesser->computeWindSum(); 1680 } 1681 if (winding == SK_MinS32) { 1682 return winding; 1683 } 1684 int spanWinding = SkOpSegment::SpanSign(start, end); 1685 if (winding && UseInnerWinding(winding - spanWinding, winding) 1686 && winding != SK_MaxS32) { 1687 winding -= spanWinding; 1688 } 1689 return winding; 1690} 1691 1692int SkOpSegment::updateWinding(SkOpAngle* angle) { 1693 SkOpSpanBase* startSpan = angle->start(); 1694 SkOpSpanBase* endSpan = angle->end(); 1695 return updateWinding(endSpan, startSpan); 1696} 1697 1698int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { 1699 SkOpSpanBase* startSpan = angle->start(); 1700 SkOpSpanBase* endSpan = angle->end(); 1701 return updateWinding(startSpan, endSpan); 1702} 1703 1704// OPTIMIZATION: does the following also work, and is it any faster? 1705// return outerWinding * innerWinding > 0 1706// || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) 1707bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { 1708 SkASSERT(outerWinding != SK_MaxS32); 1709 SkASSERT(innerWinding != SK_MaxS32); 1710 int absOut = SkTAbs(outerWinding); 1711 int absIn = SkTAbs(innerWinding); 1712 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; 1713 return result; 1714} 1715 1716int SkOpSegment::windSum(const SkOpAngle* angle) const { 1717 const SkOpSpan* minSpan = angle->start()->starter(angle->end()); 1718 return minSpan->windSum(); 1719} 1720