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