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