1/* 2 * Copyright 2015 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 "SkOpSegment.h" 9#include "SkPathOpsTSect.h" 10 11// returns true if coincident span's start and end are the same 12bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const { 13 return (fCoinPtTStart == test && fCoinPtTEnd->contains(test)) 14 || (fCoinPtTEnd == test && fCoinPtTStart->contains(test)) 15 || (fOppPtTStart == test && fOppPtTEnd->contains(test)) 16 || (fOppPtTEnd == test && fOppPtTStart->contains(test)); 17} 18 19// out of line since this function is referenced by address 20const SkOpPtT* SkCoincidentSpans::coinPtTEnd() const { 21 return fCoinPtTEnd; 22} 23 24// out of line since this function is referenced by address 25const SkOpPtT* SkCoincidentSpans::coinPtTStart() const { 26 return fCoinPtTStart; 27} 28 29// sets the span's end to the ptT referenced by the previous-next 30void SkCoincidentSpans::correctOneEnd( 31 const SkOpPtT* (SkCoincidentSpans::* getEnd)() const, 32 void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) { 33 const SkOpPtT* origPtT = (this->*getEnd)(); 34 const SkOpSpanBase* origSpan = origPtT->span(); 35 const SkOpSpan* prev = origSpan->prev(); 36 const SkOpPtT* testPtT = prev ? prev->next()->ptT() 37 : origSpan->upCast()->next()->prev()->ptT(); 38 if (origPtT != testPtT) { 39 (this->*setEnd)(testPtT); 40 } 41} 42 43/* Please keep this in sync with debugCorrectEnds */ 44// FIXME: member pointers have fallen out of favor and can be replaced with 45// an alternative approach. 46// makes all span ends agree with the segment's spans that define them 47void SkCoincidentSpans::correctEnds() { 48 this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart); 49 this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd); 50 this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart); 51 this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd); 52} 53 54/* Please keep this in sync with debugExpand */ 55// expand the range by checking adjacent spans for coincidence 56bool SkCoincidentSpans::expand() { 57 bool expanded = false; 58 const SkOpSegment* segment = coinPtTStart()->segment(); 59 const SkOpSegment* oppSegment = oppPtTStart()->segment(); 60 do { 61 const SkOpSpan* start = coinPtTStart()->span()->upCast(); 62 const SkOpSpan* prev = start->prev(); 63 const SkOpPtT* oppPtT; 64 if (!prev || !(oppPtT = prev->contains(oppSegment))) { 65 break; 66 } 67 double midT = (prev->t() + start->t()) / 2; 68 if (!segment->isClose(midT, oppSegment)) { 69 break; 70 } 71 setStarts(prev->ptT(), oppPtT); 72 expanded = true; 73 } while (true); 74 do { 75 const SkOpSpanBase* end = coinPtTEnd()->span(); 76 SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); 77 if (next && next->deleted()) { 78 break; 79 } 80 const SkOpPtT* oppPtT; 81 if (!next || !(oppPtT = next->contains(oppSegment))) { 82 break; 83 } 84 double midT = (end->t() + next->t()) / 2; 85 if (!segment->isClose(midT, oppSegment)) { 86 break; 87 } 88 setEnds(next->ptT(), oppPtT); 89 expanded = true; 90 } while (true); 91 return expanded; 92} 93 94// increase the range of this span 95bool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 96 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 97 bool result = false; 98 if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped() 99 ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) { 100 this->setStarts(coinPtTStart, oppPtTStart); 101 result = true; 102 } 103 if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped() 104 ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) { 105 this->setEnds(coinPtTEnd, oppPtTEnd); 106 result = true; 107 } 108 return result; 109} 110 111// set the range of this span 112void SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, 113 const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 114 SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart)); 115 fNext = next; 116 this->setStarts(coinPtTStart, oppPtTStart); 117 this->setEnds(coinPtTEnd, oppPtTEnd); 118} 119 120// returns true if both points are inside this 121bool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const { 122 if (s->fT > e->fT) { 123 SkTSwap(s, e); 124 } 125 if (s->segment() == fCoinPtTStart->segment()) { 126 return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT; 127 } else { 128 SkASSERT(s->segment() == fOppPtTStart->segment()); 129 double oppTs = fOppPtTStart->fT; 130 double oppTe = fOppPtTEnd->fT; 131 if (oppTs > oppTe) { 132 SkTSwap(oppTs, oppTe); 133 } 134 return oppTs <= s->fT && e->fT <= oppTe; 135 } 136} 137 138// out of line since this function is referenced by address 139const SkOpPtT* SkCoincidentSpans::oppPtTStart() const { 140 return fOppPtTStart; 141} 142 143// out of line since this function is referenced by address 144const SkOpPtT* SkCoincidentSpans::oppPtTEnd() const { 145 return fOppPtTEnd; 146} 147 148// A coincident span is unordered if the pairs of points in the main and opposite curves' 149// t values do not ascend or descend. For instance, if a tightly arced quadratic is 150// coincident with another curve, it may intersect it out of order. 151bool SkCoincidentSpans::ordered(bool* result) const { 152 const SkOpSpanBase* start = this->coinPtTStart()->span(); 153 const SkOpSpanBase* end = this->coinPtTEnd()->span(); 154 const SkOpSpanBase* next = start->upCast()->next(); 155 if (next == end) { 156 *result = true; 157 return true; 158 } 159 bool flipped = this->flipped(); 160 const SkOpSegment* oppSeg = this->oppPtTStart()->segment(); 161 double oppLastT = fOppPtTStart->fT; 162 do { 163 const SkOpPtT* opp = next->contains(oppSeg); 164 if (!opp) { 165// SkOPOBJASSERT(start, 0); // may assert if coincident span isn't fully processed 166 return false; 167 } 168 if ((oppLastT > opp->fT) != flipped) { 169 *result = false; 170 return true; 171 } 172 oppLastT = opp->fT; 173 if (next == end) { 174 break; 175 } 176 if (!next->upCastable()) { 177 *result = false; 178 return true; 179 } 180 next = next->upCast()->next(); 181 } while (true); 182 *result = true; 183 return true; 184} 185 186// if there is an existing pair that overlaps the addition, extend it 187bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 188 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 189 SkCoincidentSpans* test = fHead; 190 if (!test) { 191 return false; 192 } 193 const SkOpSegment* coinSeg = coinPtTStart->segment(); 194 const SkOpSegment* oppSeg = oppPtTStart->segment(); 195 if (!Ordered(coinPtTStart, oppPtTStart)) { 196 SkTSwap(coinSeg, oppSeg); 197 SkTSwap(coinPtTStart, oppPtTStart); 198 SkTSwap(coinPtTEnd, oppPtTEnd); 199 if (coinPtTStart->fT > coinPtTEnd->fT) { 200 SkTSwap(coinPtTStart, coinPtTEnd); 201 SkTSwap(oppPtTStart, oppPtTEnd); 202 } 203 } 204 double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); 205 SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT)); 206 do { 207 if (coinSeg != test->coinPtTStart()->segment()) { 208 continue; 209 } 210 if (oppSeg != test->oppPtTStart()->segment()) { 211 continue; 212 } 213 double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); 214 double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); 215 // if debug check triggers, caller failed to check if extended already exists 216 SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT 217 || coinPtTEnd->fT > test->coinPtTEnd()->fT 218 || oTestMinT > oppMinT || oppMaxT > oTestMaxT); 219 if ((test->coinPtTStart()->fT <= coinPtTEnd->fT 220 && coinPtTStart->fT <= test->coinPtTEnd()->fT) 221 || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) { 222 test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 223 return true; 224 } 225 } while ((test = test->next())); 226 return false; 227} 228 229// verifies that the coincidence hasn't already been added 230static void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart, 231 const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { 232#if DEBUG_COINCIDENCE 233 while (check) { 234 SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd 235 || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd); 236 SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd 237 || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd); 238 check = check->next(); 239 } 240#endif 241} 242 243// adds a new coincident pair 244void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, 245 SkOpPtT* oppPtTEnd) { 246 // OPTIMIZE: caller should have already sorted 247 if (!Ordered(coinPtTStart, oppPtTStart)) { 248 if (oppPtTStart->fT < oppPtTEnd->fT) { 249 this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd); 250 } else { 251 this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart); 252 } 253 return; 254 } 255 SkASSERT(Ordered(coinPtTStart, oppPtTStart)); 256 // choose the ptT at the front of the list to track 257 coinPtTStart = coinPtTStart->span()->ptT(); 258 coinPtTEnd = coinPtTEnd->span()->ptT(); 259 oppPtTStart = oppPtTStart->span()->ptT(); 260 oppPtTEnd = oppPtTEnd->span()->ptT(); 261 SkOPASSERT(coinPtTStart->fT < coinPtTEnd->fT); 262 SkOPASSERT(oppPtTStart->fT != oppPtTEnd->fT); 263 SkOPASSERT(!coinPtTStart->deleted()); 264 SkOPASSERT(!coinPtTEnd->deleted()); 265 SkOPASSERT(!oppPtTStart->deleted()); 266 SkOPASSERT(!oppPtTEnd->deleted()); 267 DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 268 DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 269 SkCoincidentSpans* coinRec = this->globalState()->allocator()->make<SkCoincidentSpans>(); 270 coinRec->init(SkDEBUGCODE(fGlobalState)); 271 coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); 272 fHead = coinRec; 273} 274 275// description below 276bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) { 277 const SkOpPtT* testPtT = testSpan->ptT(); 278 const SkOpPtT* stopPtT = testPtT; 279 const SkOpSegment* baseSeg = base->segment(); 280 int escapeHatch = 100000; // this is 100 times larger than the debugLoopLimit test 281 while ((testPtT = testPtT->next()) != stopPtT) { 282 if (--escapeHatch <= 0) { 283 return false; // if triggered (likely by a fuzz-generated test) too complex to succeed 284 } 285 const SkOpSegment* testSeg = testPtT->segment(); 286 if (testPtT->deleted()) { 287 continue; 288 } 289 if (testSeg == baseSeg) { 290 continue; 291 } 292 if (testPtT->span()->ptT() != testPtT) { 293 continue; 294 } 295 if (this->contains(baseSeg, testSeg, testPtT->fT)) { 296 continue; 297 } 298 // intersect perp with base->ptT() with testPtT->segment() 299 SkDVector dxdy = baseSeg->dSlopeAtT(base->t()); 300 const SkPoint& pt = base->pt(); 301 SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}}; 302 SkIntersections i SkDEBUGCODE((this->globalState())); 303 (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i); 304 for (int index = 0; index < i.used(); ++index) { 305 double t = i[0][index]; 306 if (!between(0, t, 1)) { 307 continue; 308 } 309 SkDPoint oppPt = i.pt(index); 310 if (!oppPt.approximatelyEqual(pt)) { 311 continue; 312 } 313 SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg); 314 SkOpPtT* oppStart = writableSeg->addT(t); 315 if (oppStart == testPtT) { 316 continue; 317 } 318 SkOpSpan* writableBase = const_cast<SkOpSpan*>(base); 319 oppStart->span()->addOpp(writableBase); 320 if (oppStart->deleted()) { 321 continue; 322 } 323 SkOpSegment* coinSeg = base->segment(); 324 SkOpSegment* oppSeg = oppStart->segment(); 325 double coinTs, coinTe, oppTs, oppTe; 326 if (Ordered(coinSeg, oppSeg)) { 327 coinTs = base->t(); 328 coinTe = testSpan->t(); 329 oppTs = oppStart->fT; 330 oppTe = testPtT->fT; 331 } else { 332 SkTSwap(coinSeg, oppSeg); 333 coinTs = oppStart->fT; 334 coinTe = testPtT->fT; 335 oppTs = base->t(); 336 oppTe = testSpan->t(); 337 } 338 if (coinTs > coinTe) { 339 SkTSwap(coinTs, coinTe); 340 SkTSwap(oppTs, oppTe); 341 } 342 bool added; 343 if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) { 344 return false; 345 } 346 } 347 } 348 return true; 349} 350 351// description below 352bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) { 353 FAIL_IF(!ptT->span()->upCastable()); 354 const SkOpSpan* base = ptT->span()->upCast(); 355 const SkOpSpan* prev = base->prev(); 356 FAIL_IF(!prev); 357 if (!prev->isCanceled()) { 358 if (!this->addEndMovedSpans(base, base->prev())) { 359 return false; 360 } 361 } 362 if (!base->isCanceled()) { 363 if (!this->addEndMovedSpans(base, base->next())) { 364 return false; 365 } 366 } 367 return true; 368} 369 370/* If A is coincident with B and B includes an endpoint, and A's matching point 371 is not the endpoint (i.e., there's an implied line connecting B-end and A) 372 then assume that the same implied line may intersect another curve close to B. 373 Since we only care about coincidence that was undetected, look at the 374 ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but 375 next door) and see if the A matching point is close enough to form another 376 coincident pair. If so, check for a new coincident span between B-end/A ptT loop 377 and the adjacent ptT loop. 378*/ 379bool SkOpCoincidence::addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 380 DEBUG_SET_PHASE(); 381 SkCoincidentSpans* span = fHead; 382 if (!span) { 383 return true; 384 } 385 fTop = span; 386 fHead = nullptr; 387 do { 388 if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) { 389 FAIL_IF(1 == span->coinPtTStart()->fT); 390 bool onEnd = span->coinPtTStart()->fT == 0; 391 bool oOnEnd = zero_or_one(span->oppPtTStart()->fT); 392 if (onEnd) { 393 if (!oOnEnd) { // if both are on end, any nearby intersect was already found 394 if (!this->addEndMovedSpans(span->oppPtTStart())) { 395 return false; 396 } 397 } 398 } else if (oOnEnd) { 399 if (!this->addEndMovedSpans(span->coinPtTStart())) { 400 return false; 401 } 402 } 403 } 404 if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) { 405 bool onEnd = span->coinPtTEnd()->fT == 1; 406 bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT); 407 if (onEnd) { 408 if (!oOnEnd) { 409 if (!this->addEndMovedSpans(span->oppPtTEnd())) { 410 return false; 411 } 412 } 413 } else if (oOnEnd) { 414 if (!this->addEndMovedSpans(span->coinPtTEnd())) { 415 return false; 416 } 417 } 418 } 419 } while ((span = span->next())); 420 this->restoreHead(); 421 return true; 422} 423 424/* Please keep this in sync with debugAddExpanded */ 425// for each coincident pair, match the spans 426// if the spans don't match, add the missing pt to the segment and loop it in the opposite span 427bool SkOpCoincidence::addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 428 DEBUG_SET_PHASE(); 429 SkCoincidentSpans* coin = this->fHead; 430 if (!coin) { 431 return true; 432 } 433 do { 434 const SkOpPtT* startPtT = coin->coinPtTStart(); 435 const SkOpPtT* oStartPtT = coin->oppPtTStart(); 436 double priorT = startPtT->fT; 437 double oPriorT = oStartPtT->fT; 438 FAIL_IF(!startPtT->contains(oStartPtT)); 439 SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd())); 440 const SkOpSpanBase* start = startPtT->span(); 441 const SkOpSpanBase* oStart = oStartPtT->span(); 442 const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 443 const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span(); 444 FAIL_IF(oEnd->deleted()); 445 FAIL_IF(!start->upCastable()); 446 const SkOpSpanBase* test = start->upCast()->next(); 447 FAIL_IF(!coin->flipped() && !oStart->upCastable()); 448 const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next(); 449 FAIL_IF(!oTest); 450 SkOpSegment* seg = start->segment(); 451 SkOpSegment* oSeg = oStart->segment(); 452 while (test != end || oTest != oEnd) { 453 const SkOpPtT* containedOpp = test->ptT()->contains(oSeg); 454 const SkOpPtT* containedThis = oTest->ptT()->contains(seg); 455 if (!containedOpp || !containedThis) { 456 // choose the ends, or the first common pt-t list shared by both 457 double nextT, oNextT; 458 if (containedOpp) { 459 nextT = test->t(); 460 oNextT = containedOpp->fT; 461 } else if (containedThis) { 462 nextT = containedThis->fT; 463 oNextT = oTest->t(); 464 } else { 465 // iterate through until a pt-t list found that contains the other 466 const SkOpSpanBase* walk = test; 467 const SkOpPtT* walkOpp; 468 do { 469 FAIL_IF(!walk->upCastable()); 470 walk = walk->upCast()->next(); 471 } while (!(walkOpp = walk->ptT()->contains(oSeg)) 472 && walk != coin->coinPtTEnd()->span()); 473 FAIL_IF(!walkOpp); 474 nextT = walk->t(); 475 oNextT = walkOpp->fT; 476 } 477 // use t ranges to guess which one is missing 478 double startRange = nextT - priorT; 479 FAIL_IF(!startRange); 480 double startPart = (test->t() - priorT) / startRange; 481 double oStartRange = oNextT - oPriorT; 482 FAIL_IF(!oStartRange); 483 double oStartPart = (oTest->t() - oPriorT) / oStartRange; 484 FAIL_IF(startPart == oStartPart); 485 bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart 486 : !!containedThis; 487 bool startOver = false; 488 bool success = addToOpp ? oSeg->addExpanded( 489 oPriorT + oStartRange * startPart, test, &startOver) 490 : seg->addExpanded( 491 priorT + startRange * oStartPart, oTest, &startOver); 492 FAIL_IF(!success); 493 if (startOver) { 494 test = start; 495 oTest = oStart; 496 } 497 end = coin->coinPtTEnd()->span(); 498 oEnd = coin->oppPtTEnd()->span(); 499 } 500 if (test != end) { 501 FAIL_IF(!test->upCastable()); 502 priorT = test->t(); 503 test = test->upCast()->next(); 504 } 505 if (oTest != oEnd) { 506 oPriorT = oTest->t(); 507 if (coin->flipped()) { 508 oTest = oTest->prev(); 509 } else { 510 FAIL_IF(!oTest->upCastable()); 511 oTest = oTest->upCast()->next(); 512 } 513 FAIL_IF(!oTest); 514 } 515 516 } 517 } while ((coin = coin->next())); 518 return true; 519} 520 521// given a t span, map the same range on the coincident span 522/* 523the curves may not scale linearly, so interpolation may only happen within known points 524remap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s 525then repeat to capture over1e 526*/ 527double SkOpCoincidence::TRange(const SkOpPtT* overS, double t, 528 const SkOpSegment* coinSeg SkDEBUGPARAMS(const SkOpPtT* overE)) { 529 const SkOpSpanBase* work = overS->span(); 530 const SkOpPtT* foundStart = nullptr; 531 const SkOpPtT* foundEnd = nullptr; 532 const SkOpPtT* coinStart = nullptr; 533 const SkOpPtT* coinEnd = nullptr; 534 do { 535 const SkOpPtT* contained = work->contains(coinSeg); 536 if (!contained) { 537 if (work->final()) { 538 break; 539 } 540 continue; 541 } 542 if (work->t() <= t) { 543 coinStart = contained; 544 foundStart = work->ptT(); 545 } 546 if (work->t() >= t) { 547 coinEnd = contained; 548 foundEnd = work->ptT(); 549 break; 550 } 551 SkASSERT(work->ptT() != overE); 552 } while ((work = work->upCast()->next())); 553 if (!coinStart || !coinEnd) { 554 return 1; 555 } 556 // while overS->fT <=t and overS contains coinSeg 557 double denom = foundEnd->fT - foundStart->fT; 558 double sRatio = denom ? (t - foundStart->fT) / denom : 1; 559 return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio; 560} 561 562// return true if span overlaps existing and needs to adjust the coincident list 563bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check, 564 const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, 565 double coinTs, double coinTe, double oppTs, double oppTe, 566 SkTDArray<SkCoincidentSpans*>* overlaps) const { 567 if (!Ordered(coinSeg, oppSeg)) { 568 if (oppTs < oppTe) { 569 return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe, 570 overlaps); 571 } 572 return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps); 573 } 574 bool swapOpp = oppTs > oppTe; 575 if (swapOpp) { 576 SkTSwap(oppTs, oppTe); 577 } 578 do { 579 if (check->coinPtTStart()->segment() != coinSeg) { 580 continue; 581 } 582 if (check->oppPtTStart()->segment() != oppSeg) { 583 continue; 584 } 585 double checkTs = check->coinPtTStart()->fT; 586 double checkTe = check->coinPtTEnd()->fT; 587 bool coinOutside = coinTe < checkTs || coinTs > checkTe; 588 double oCheckTs = check->oppPtTStart()->fT; 589 double oCheckTe = check->oppPtTEnd()->fT; 590 if (swapOpp) { 591 if (oCheckTs <= oCheckTe) { 592 return false; 593 } 594 SkTSwap(oCheckTs, oCheckTe); 595 } 596 bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe; 597 if (coinOutside && oppOutside) { 598 continue; 599 } 600 bool coinInside = coinTe <= checkTe && coinTs >= checkTs; 601 bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs; 602 if (coinInside && oppInside) { // already included, do nothing 603 return false; 604 } 605 *overlaps->append() = check; // partial overlap, extend existing entry 606 } while ((check = check->next())); 607 return true; 608} 609 610/* Please keep this in sync with debugAddIfMissing() */ 611// note that over1s, over1e, over2s, over2e are ordered 612bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s, 613 double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added 614 SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) { 615 SkASSERT(tStart < tEnd); 616 SkASSERT(over1s->fT < over1e->fT); 617 SkASSERT(between(over1s->fT, tStart, over1e->fT)); 618 SkASSERT(between(over1s->fT, tEnd, over1e->fT)); 619 SkASSERT(over2s->fT < over2e->fT); 620 SkASSERT(between(over2s->fT, tStart, over2e->fT)); 621 SkASSERT(between(over2s->fT, tEnd, over2e->fT)); 622 SkASSERT(over1s->segment() == over1e->segment()); 623 SkASSERT(over2s->segment() == over2e->segment()); 624 SkASSERT(over1s->segment() == over2s->segment()); 625 SkASSERT(over1s->segment() != coinSeg); 626 SkASSERT(over1s->segment() != oppSeg); 627 SkASSERT(coinSeg != oppSeg); 628 double coinTs, coinTe, oppTs, oppTe; 629 coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e)); 630 coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e)); 631 if (coinSeg->collapsed(coinTs, coinTe)) { 632 return true; 633 } 634 oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e)); 635 oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e)); 636 if (oppSeg->collapsed(oppTs, oppTe)) { 637 return true; 638 } 639 if (coinTs > coinTe) { 640 SkTSwap(coinTs, coinTe); 641 SkTSwap(oppTs, oppTe); 642 } 643 return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added); 644} 645 646/* Please keep this in sync with debugAddOrOverlap() */ 647// If this is called by addEndMovedSpans(), a returned false propogates out to an abort. 648// If this is called by AddIfMissing(), a returned false indicates there was nothing to add 649bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, 650 double coinTs, double coinTe, double oppTs, double oppTe, bool* added) { 651 SkTDArray<SkCoincidentSpans*> overlaps; 652 FAIL_IF(!fTop); 653 if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { 654 return true; 655 } 656 if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, 657 coinTe, oppTs, oppTe, &overlaps)) { 658 return true; 659 } 660 SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; 661 for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing 662 SkCoincidentSpans* test = overlaps[index]; 663 if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) { 664 overlap->setCoinPtTStart(test->coinPtTStart()); 665 } 666 if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) { 667 overlap->setCoinPtTEnd(test->coinPtTEnd()); 668 } 669 if (overlap->flipped() 670 ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT 671 : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) { 672 overlap->setOppPtTStart(test->oppPtTStart()); 673 } 674 if (overlap->flipped() 675 ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT 676 : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) { 677 overlap->setOppPtTEnd(test->oppPtTEnd()); 678 } 679 if (!fHead || !this->release(fHead, test)) { 680 SkAssertResult(this->release(fTop, test)); 681 } 682 } 683 const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg); 684 const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg); 685 if (overlap && cs && ce && overlap->contains(cs, ce)) { 686 return true; 687 } 688 FAIL_IF(cs == ce && cs); 689 const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); 690 const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); 691 if (overlap && os && oe && overlap->contains(os, oe)) { 692 return true; 693 } 694 SkASSERT(!cs || !cs->deleted()); 695 SkASSERT(!os || !os->deleted()); 696 SkASSERT(!ce || !ce->deleted()); 697 SkASSERT(!oe || !oe->deleted()); 698 const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr; 699 const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr; 700 FAIL_IF(csExisting && csExisting == ceExisting); 701// FAIL_IF(csExisting && (csExisting == ce || 702// csExisting->contains(ceExisting ? ceExisting : ce))); 703 FAIL_IF(ceExisting && (ceExisting == cs || 704 ceExisting->contains(csExisting ? csExisting : cs))); 705 const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr; 706 const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr; 707 FAIL_IF(osExisting && osExisting == oeExisting); 708 FAIL_IF(osExisting && (osExisting == oe || 709 osExisting->contains(oeExisting ? oeExisting : oe))); 710 FAIL_IF(oeExisting && (oeExisting == os || 711 oeExisting->contains(osExisting ? osExisting : os))); 712 // extra line in debug code 713 this->debugValidate(); 714 if (!cs || !os) { 715 SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs) 716 : coinSeg->addT(coinTs); 717 if (csWritable == ce) { 718 return true; 719 } 720 SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) 721 : oppSeg->addT(oppTs); 722 FAIL_IF(!csWritable || !osWritable); 723 csWritable->span()->addOpp(osWritable->span()); 724 cs = csWritable; 725 os = osWritable->active(); 726 FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted())); 727 } 728 if (!ce || !oe) { 729 SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce) 730 : coinSeg->addT(coinTe); 731 SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe) 732 : oppSeg->addT(oppTe); 733 ceWritable->span()->addOpp(oeWritable->span()); 734 ce = ceWritable; 735 oe = oeWritable; 736 } 737 this->debugValidate(); 738 FAIL_IF(cs->deleted()); 739 FAIL_IF(os->deleted()); 740 FAIL_IF(ce->deleted()); 741 FAIL_IF(oe->deleted()); 742 FAIL_IF(cs->contains(ce) || os->contains(oe)); 743 bool result = true; 744 if (overlap) { 745 if (overlap->coinPtTStart()->segment() == coinSeg) { 746 result = overlap->extend(cs, ce, os, oe); 747 } else { 748 if (os->fT > oe->fT) { 749 SkTSwap(cs, ce); 750 SkTSwap(os, oe); 751 } 752 result = overlap->extend(os, oe, cs, ce); 753 } 754#if DEBUG_COINCIDENCE_VERBOSE 755 if (result) { 756 overlaps[0]->debugShow(); 757 } 758#endif 759 } else { 760 this->add(cs, ce, os, oe); 761#if DEBUG_COINCIDENCE_VERBOSE 762 fHead->debugShow(); 763#endif 764 } 765 this->debugValidate(); 766 if (result) { 767 *added = true; 768 } 769 return true; 770} 771 772// Please keep this in sync with debugAddMissing() 773/* detects overlaps of different coincident runs on same segment */ 774/* does not detect overlaps for pairs without any segments in common */ 775// returns true if caller should loop again 776bool SkOpCoincidence::addMissing(bool* added DEBUG_COIN_DECLARE_PARAMS()) { 777 SkCoincidentSpans* outer = fHead; 778 *added = false; 779 if (!outer) { 780 return true; 781 } 782 fTop = outer; 783 fHead = nullptr; 784 do { 785 // addifmissing can modify the list that this is walking 786 // save head so that walker can iterate over old data unperturbed 787 // addifmissing adds to head freely then add saved head in the end 788 const SkOpPtT* ocs = outer->coinPtTStart(); 789 FAIL_IF(ocs->deleted()); 790 const SkOpSegment* outerCoin = ocs->segment(); 791 SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list 792 const SkOpPtT* oos = outer->oppPtTStart(); 793 if (oos->deleted()) { 794 return true; 795 } 796 const SkOpSegment* outerOpp = oos->segment(); 797 SkOPASSERT(!outerOpp->done()); 798 SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin); 799 SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp); 800 SkCoincidentSpans* inner = outer; 801 while ((inner = inner->next())) { 802 this->debugValidate(); 803 double overS, overE; 804 const SkOpPtT* ics = inner->coinPtTStart(); 805 FAIL_IF(ics->deleted()); 806 const SkOpSegment* innerCoin = ics->segment(); 807 FAIL_IF(innerCoin->done()); 808 const SkOpPtT* ios = inner->oppPtTStart(); 809 FAIL_IF(ios->deleted()); 810 const SkOpSegment* innerOpp = ios->segment(); 811 SkOPASSERT(!innerOpp->done()); 812 SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin); 813 SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp); 814 if (outerCoin == innerCoin) { 815 const SkOpPtT* oce = outer->coinPtTEnd(); 816 if (oce->deleted()) { 817 return true; 818 } 819 const SkOpPtT* ice = inner->coinPtTEnd(); 820 FAIL_IF(ice->deleted()); 821 if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) { 822 (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice), 823 overS, overE, outerOppWritable, innerOppWritable, added 824 SkDEBUGPARAMS(ocs->debugEnder(oce)) 825 SkDEBUGPARAMS(ics->debugEnder(ice))); 826 } 827 } else if (outerCoin == innerOpp) { 828 const SkOpPtT* oce = outer->coinPtTEnd(); 829 SkASSERT(!oce->deleted()); 830 const SkOpPtT* ioe = inner->oppPtTEnd(); 831 SkASSERT(!ioe->deleted()); 832 if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) { 833 (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe), 834 overS, overE, outerOppWritable, innerCoinWritable, added 835 SkDEBUGPARAMS(ocs->debugEnder(oce)) 836 SkDEBUGPARAMS(ios->debugEnder(ioe))); 837 } 838 } else if (outerOpp == innerCoin) { 839 const SkOpPtT* ooe = outer->oppPtTEnd(); 840 SkASSERT(!ooe->deleted()); 841 const SkOpPtT* ice = inner->coinPtTEnd(); 842 SkASSERT(!ice->deleted()); 843 SkASSERT(outerCoin != innerOpp); 844 if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) { 845 (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice), 846 overS, overE, outerCoinWritable, innerOppWritable, added 847 SkDEBUGPARAMS(oos->debugEnder(ooe)) 848 SkDEBUGPARAMS(ics->debugEnder(ice))); 849 } 850 } else if (outerOpp == innerOpp) { 851 const SkOpPtT* ooe = outer->oppPtTEnd(); 852 SkASSERT(!ooe->deleted()); 853 const SkOpPtT* ioe = inner->oppPtTEnd(); 854 if (ioe->deleted()) { 855 return true; 856 } 857 SkASSERT(outerCoin != innerCoin); 858 if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) { 859 (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe), 860 overS, overE, outerCoinWritable, innerCoinWritable, added 861 SkDEBUGPARAMS(oos->debugEnder(ooe)) 862 SkDEBUGPARAMS(ios->debugEnder(ioe))); 863 } 864 } 865 this->debugValidate(); 866 } 867 } while ((outer = outer->next())); 868 this->restoreHead(); 869 return true; 870} 871 872bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o, 873 const SkOpSegment* seg2, const SkOpSegment* seg2o, 874 const SkOpPtT* overS, const SkOpPtT* overE) { 875 const SkOpPtT* s1 = overS->find(seg1); 876 const SkOpPtT* e1 = overE->find(seg1); 877 FAIL_IF(!s1); 878 FAIL_IF(!e1); 879 if (!s1->starter(e1)->span()->upCast()->windValue()) { 880 s1 = overS->find(seg1o); 881 e1 = overE->find(seg1o); 882 FAIL_IF(!s1); 883 FAIL_IF(!e1); 884 if (!s1->starter(e1)->span()->upCast()->windValue()) { 885 return true; 886 } 887 } 888 const SkOpPtT* s2 = overS->find(seg2); 889 const SkOpPtT* e2 = overE->find(seg2); 890 FAIL_IF(!s2); 891 FAIL_IF(!e2); 892 if (!s2->starter(e2)->span()->upCast()->windValue()) { 893 s2 = overS->find(seg2o); 894 e2 = overE->find(seg2o); 895 FAIL_IF(!s2); 896 FAIL_IF(!e2); 897 if (!s2->starter(e2)->span()->upCast()->windValue()) { 898 return true; 899 } 900 } 901 if (s1->segment() == s2->segment()) { 902 return true; 903 } 904 if (s1->fT > e1->fT) { 905 SkTSwap(s1, e1); 906 SkTSwap(s2, e2); 907 } 908 this->add(s1, e1, s2, e2); 909 return true; 910} 911 912bool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const { 913 if (this->contains(fHead, seg, opp, oppT)) { 914 return true; 915 } 916 if (this->contains(fTop, seg, opp, oppT)) { 917 return true; 918 } 919 return false; 920} 921 922bool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg, 923 const SkOpSegment* opp, double oppT) const { 924 if (!coin) { 925 return false; 926 } 927 do { 928 if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp 929 && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) { 930 return true; 931 } 932 if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp 933 && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) { 934 return true; 935 } 936 } while ((coin = coin->next())); 937 return false; 938} 939 940bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 941 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const { 942 const SkCoincidentSpans* test = fHead; 943 if (!test) { 944 return false; 945 } 946 const SkOpSegment* coinSeg = coinPtTStart->segment(); 947 const SkOpSegment* oppSeg = oppPtTStart->segment(); 948 if (!Ordered(coinPtTStart, oppPtTStart)) { 949 SkTSwap(coinSeg, oppSeg); 950 SkTSwap(coinPtTStart, oppPtTStart); 951 SkTSwap(coinPtTEnd, oppPtTEnd); 952 if (coinPtTStart->fT > coinPtTEnd->fT) { 953 SkTSwap(coinPtTStart, coinPtTEnd); 954 SkTSwap(oppPtTStart, oppPtTEnd); 955 } 956 } 957 double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); 958 double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT); 959 do { 960 if (coinSeg != test->coinPtTStart()->segment()) { 961 continue; 962 } 963 if (coinPtTStart->fT < test->coinPtTStart()->fT) { 964 continue; 965 } 966 if (coinPtTEnd->fT > test->coinPtTEnd()->fT) { 967 continue; 968 } 969 if (oppSeg != test->oppPtTStart()->segment()) { 970 continue; 971 } 972 if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { 973 continue; 974 } 975 if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { 976 continue; 977 } 978 return true; 979 } while ((test = test->next())); 980 return false; 981} 982 983void SkOpCoincidence::correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 984 DEBUG_SET_PHASE(); 985 SkCoincidentSpans* coin = fHead; 986 if (!coin) { 987 return; 988 } 989 do { 990 coin->correctEnds(); 991 } while ((coin = coin->next())); 992} 993 994// walk span sets in parallel, moving winding from one to the other 995bool SkOpCoincidence::apply(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 996 DEBUG_SET_PHASE(); 997 SkCoincidentSpans* coin = fHead; 998 if (!coin) { 999 return true; 1000 } 1001 do { 1002 SkOpSpanBase* startSpan = coin->coinPtTStartWritable()->span(); 1003 FAIL_IF(!startSpan->upCastable()); 1004 SkOpSpan* start = startSpan->upCast(); 1005 if (start->deleted()) { 1006 continue; 1007 } 1008 const SkOpSpanBase* end = coin->coinPtTEnd()->span(); 1009 SkASSERT(start == start->starter(end)); 1010 bool flipped = coin->flipped(); 1011 SkOpSpanBase* oStartBase = (flipped ? coin->oppPtTEndWritable() 1012 : coin->oppPtTStartWritable())->span(); 1013 FAIL_IF(!oStartBase->upCastable()); 1014 SkOpSpan* oStart = oStartBase->upCast(); 1015 if (oStart->deleted()) { 1016 continue; 1017 } 1018 const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span(); 1019 SkASSERT(oStart == oStart->starter(oEnd)); 1020 SkOpSegment* segment = start->segment(); 1021 SkOpSegment* oSegment = oStart->segment(); 1022 bool operandSwap = segment->operand() != oSegment->operand(); 1023 if (flipped) { 1024 if (oEnd->deleted()) { 1025 continue; 1026 } 1027 do { 1028 SkOpSpanBase* oNext = oStart->next(); 1029 if (oNext == oEnd) { 1030 break; 1031 } 1032 FAIL_IF(!oNext->upCastable()); 1033 oStart = oNext->upCast(); 1034 } while (true); 1035 } 1036 do { 1037 int windValue = start->windValue(); 1038 int oppValue = start->oppValue(); 1039 int oWindValue = oStart->windValue(); 1040 int oOppValue = oStart->oppValue(); 1041 // winding values are added or subtracted depending on direction and wind type 1042 // same or opposite values are summed depending on the operand value 1043 int windDiff = operandSwap ? oOppValue : oWindValue; 1044 int oWindDiff = operandSwap ? oppValue : windValue; 1045 if (!flipped) { 1046 windDiff = -windDiff; 1047 oWindDiff = -oWindDiff; 1048 } 1049 bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff 1050 && oWindValue <= oWindDiff)); 1051 if (addToStart ? start->done() : oStart->done()) { 1052 addToStart ^= true; 1053 } 1054 if (addToStart) { 1055 if (operandSwap) { 1056 SkTSwap(oWindValue, oOppValue); 1057 } 1058 if (flipped) { 1059 windValue -= oWindValue; 1060 oppValue -= oOppValue; 1061 } else { 1062 windValue += oWindValue; 1063 oppValue += oOppValue; 1064 } 1065 if (segment->isXor()) { 1066 windValue &= 1; 1067 } 1068 if (segment->oppXor()) { 1069 oppValue &= 1; 1070 } 1071 oWindValue = oOppValue = 0; 1072 } else { 1073 if (operandSwap) { 1074 SkTSwap(windValue, oppValue); 1075 } 1076 if (flipped) { 1077 oWindValue -= windValue; 1078 oOppValue -= oppValue; 1079 } else { 1080 oWindValue += windValue; 1081 oOppValue += oppValue; 1082 } 1083 if (oSegment->isXor()) { 1084 oWindValue &= 1; 1085 } 1086 if (oSegment->oppXor()) { 1087 oOppValue &= 1; 1088 } 1089 windValue = oppValue = 0; 1090 } 1091#if 0 && DEBUG_COINCIDENCE 1092 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(), 1093 start->debugID(), windValue, oppValue); 1094 SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(), 1095 oStart->debugID(), oWindValue, oOppValue); 1096#endif 1097 start->setWindValue(windValue); 1098 start->setOppValue(oppValue); 1099 FAIL_IF(oWindValue == -1); 1100 oStart->setWindValue(oWindValue); 1101 oStart->setOppValue(oOppValue); 1102 if (!windValue && !oppValue) { 1103 segment->markDone(start); 1104 } 1105 if (!oWindValue && !oOppValue) { 1106 oSegment->markDone(oStart); 1107 } 1108 SkOpSpanBase* next = start->next(); 1109 SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); 1110 if (next == end) { 1111 break; 1112 } 1113 FAIL_IF(!next->upCastable()); 1114 start = next->upCast(); 1115 // if the opposite ran out too soon, just reuse the last span 1116 if (!oNext || !oNext->upCastable()) { 1117 oNext = oStart; 1118 } 1119 oStart = oNext->upCast(); 1120 } while (true); 1121 } while ((coin = coin->next())); 1122 return true; 1123} 1124 1125// Please keep this in sync with debugRelease() 1126bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove) { 1127 SkCoincidentSpans* head = coin; 1128 SkCoincidentSpans* prev = nullptr; 1129 SkCoincidentSpans* next; 1130 do { 1131 next = coin->next(); 1132 if (coin == remove) { 1133 if (prev) { 1134 prev->setNext(next); 1135 } else if (head == fHead) { 1136 fHead = next; 1137 } else { 1138 fTop = next; 1139 } 1140 break; 1141 } 1142 prev = coin; 1143 } while ((coin = next)); 1144 return coin != nullptr; 1145} 1146 1147void SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) { 1148 if (!coin) { 1149 return; 1150 } 1151 SkCoincidentSpans* head = coin; 1152 SkCoincidentSpans* prev = nullptr; 1153 SkCoincidentSpans* next; 1154 do { 1155 next = coin->next(); 1156 if (coin->coinPtTStart()->deleted()) { 1157 SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() : 1158 coin->oppPtTStart()->deleted()); 1159 if (prev) { 1160 prev->setNext(next); 1161 } else if (head == fHead) { 1162 fHead = next; 1163 } else { 1164 fTop = next; 1165 } 1166 } else { 1167 SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() : 1168 !coin->oppPtTStart()->deleted()); 1169 prev = coin; 1170 } 1171 } while ((coin = next)); 1172} 1173 1174void SkOpCoincidence::releaseDeleted() { 1175 this->releaseDeleted(fHead); 1176 this->releaseDeleted(fTop); 1177} 1178 1179void SkOpCoincidence::restoreHead() { 1180 SkCoincidentSpans** headPtr = &fHead; 1181 while (*headPtr) { 1182 headPtr = (*headPtr)->nextPtr(); 1183 } 1184 *headPtr = fTop; 1185 fTop = nullptr; 1186 // segments may have collapsed in the meantime; remove empty referenced segments 1187 headPtr = &fHead; 1188 while (*headPtr) { 1189 SkCoincidentSpans* test = *headPtr; 1190 if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) { 1191 *headPtr = test->next(); 1192 continue; 1193 } 1194 headPtr = (*headPtr)->nextPtr(); 1195 } 1196} 1197 1198// Please keep this in sync with debugExpand() 1199// expand the range by checking adjacent spans for coincidence 1200bool SkOpCoincidence::expand(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 1201 DEBUG_SET_PHASE(); 1202 SkCoincidentSpans* coin = fHead; 1203 if (!coin) { 1204 return false; 1205 } 1206 bool expanded = false; 1207 do { 1208 if (coin->expand()) { 1209 // check to see if multiple spans expanded so they are now identical 1210 SkCoincidentSpans* test = fHead; 1211 do { 1212 if (coin == test) { 1213 continue; 1214 } 1215 if (coin->coinPtTStart() == test->coinPtTStart() 1216 && coin->oppPtTStart() == test->oppPtTStart()) { 1217 this->release(fHead, test); 1218 break; 1219 } 1220 } while ((test = test->next())); 1221 expanded = true; 1222 } 1223 } while ((coin = coin->next())); 1224 return expanded; 1225} 1226 1227bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps DEBUG_COIN_DECLARE_PARAMS()) const { 1228 DEBUG_SET_PHASE(); 1229 overlaps->fHead = overlaps->fTop = nullptr; 1230 SkCoincidentSpans* outer = fHead; 1231 while (outer) { 1232 const SkOpSegment* outerCoin = outer->coinPtTStart()->segment(); 1233 const SkOpSegment* outerOpp = outer->oppPtTStart()->segment(); 1234 SkCoincidentSpans* inner = outer; 1235 while ((inner = inner->next())) { 1236 const SkOpSegment* innerCoin = inner->coinPtTStart()->segment(); 1237 if (outerCoin == innerCoin) { 1238 continue; // both winners are the same segment, so there's no additional overlap 1239 } 1240 const SkOpSegment* innerOpp = inner->oppPtTStart()->segment(); 1241 const SkOpPtT* overlapS; 1242 const SkOpPtT* overlapE; 1243 if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(), 1244 outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS, 1245 &overlapE)) 1246 || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(), 1247 outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), 1248 &overlapS, &overlapE)) 1249 || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(), 1250 outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), 1251 &overlapS, &overlapE))) { 1252 if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp, 1253 overlapS, overlapE)) { 1254 return false; 1255 } 1256 } 1257 } 1258 outer = outer->next(); 1259 } 1260 return true; 1261} 1262 1263void SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) { 1264 SkOPASSERT(deleted != kept); 1265 if (fHead) { 1266 this->fixUp(fHead, deleted, kept); 1267 } 1268 if (fTop) { 1269 this->fixUp(fTop, deleted, kept); 1270 } 1271} 1272 1273void SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) { 1274 SkCoincidentSpans* head = coin; 1275 do { 1276 if (coin->coinPtTStart() == deleted) { 1277 if (coin->coinPtTEnd()->span() == kept->span()) { 1278 this->release(head, coin); 1279 continue; 1280 } 1281 coin->setCoinPtTStart(kept); 1282 } 1283 if (coin->coinPtTEnd() == deleted) { 1284 if (coin->coinPtTStart()->span() == kept->span()) { 1285 this->release(head, coin); 1286 continue; 1287 } 1288 coin->setCoinPtTEnd(kept); 1289 } 1290 if (coin->oppPtTStart() == deleted) { 1291 if (coin->oppPtTEnd()->span() == kept->span()) { 1292 this->release(head, coin); 1293 continue; 1294 } 1295 coin->setOppPtTStart(kept); 1296 } 1297 if (coin->oppPtTEnd() == deleted) { 1298 if (coin->oppPtTStart()->span() == kept->span()) { 1299 this->release(head, coin); 1300 continue; 1301 } 1302 coin->setOppPtTEnd(kept); 1303 } 1304 } while ((coin = coin->next())); 1305} 1306 1307// Please keep this in sync with debugMark() 1308/* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */ 1309bool SkOpCoincidence::mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()) { 1310 DEBUG_SET_PHASE(); 1311 SkCoincidentSpans* coin = fHead; 1312 if (!coin) { 1313 return true; 1314 } 1315 do { 1316 SkOpSpanBase* startBase = coin->coinPtTStartWritable()->span(); 1317 FAIL_IF(!startBase->upCastable()); 1318 SkOpSpan* start = startBase->upCast(); 1319 FAIL_IF(start->deleted()); 1320 SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); 1321 SkOPASSERT(!end->deleted()); 1322 SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); 1323 SkOPASSERT(!oStart->deleted()); 1324 SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span(); 1325 SkASSERT(!oEnd->deleted()); 1326 bool flipped = coin->flipped(); 1327 if (flipped) { 1328 SkTSwap(oStart, oEnd); 1329 } 1330 /* coin and opp spans may not match up. Mark the ends, and then let the interior 1331 get marked as many times as the spans allow */ 1332 FAIL_IF(!oStart->upCastable()); 1333 start->insertCoincidence(oStart->upCast()); 1334 end->insertCoinEnd(oEnd); 1335 const SkOpSegment* segment = start->segment(); 1336 const SkOpSegment* oSegment = oStart->segment(); 1337 SkOpSpanBase* next = start; 1338 SkOpSpanBase* oNext = oStart; 1339 bool ordered; 1340 FAIL_IF(!coin->ordered(&ordered)); 1341 while ((next = next->upCast()->next()) != end) { 1342 FAIL_IF(!next->upCastable()); 1343 FAIL_IF(!next->upCast()->insertCoincidence(oSegment, flipped, ordered)); 1344 } 1345 while ((oNext = oNext->upCast()->next()) != oEnd) { 1346 FAIL_IF(!oNext->upCastable()); 1347 FAIL_IF(!oNext->upCast()->insertCoincidence(segment, flipped, ordered)); 1348 } 1349 } while ((coin = coin->next())); 1350 return true; 1351} 1352 1353// Please keep in sync with debugMarkCollapsed() 1354void SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) { 1355 SkCoincidentSpans* head = coin; 1356 while (coin) { 1357 if (coin->collapsed(test)) { 1358 if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) { 1359 coin->coinPtTStartWritable()->segment()->markAllDone(); 1360 } 1361 if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) { 1362 coin->oppPtTStartWritable()->segment()->markAllDone(); 1363 } 1364 this->release(head, coin); 1365 } 1366 coin = coin->next(); 1367 } 1368} 1369 1370// Please keep in sync with debugMarkCollapsed() 1371void SkOpCoincidence::markCollapsed(SkOpPtT* test) { 1372 markCollapsed(fHead, test); 1373 markCollapsed(fTop, test); 1374} 1375 1376bool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) { 1377 if (coinSeg->verb() < oppSeg->verb()) { 1378 return true; 1379 } 1380 if (coinSeg->verb() > oppSeg->verb()) { 1381 return false; 1382 } 1383 int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2; 1384 const SkScalar* cPt = &coinSeg->pts()[0].fX; 1385 const SkScalar* oPt = &oppSeg->pts()[0].fX; 1386 for (int index = 0; index < count; ++index) { 1387 if (*cPt < *oPt) { 1388 return true; 1389 } 1390 if (*cPt > *oPt) { 1391 return false; 1392 } 1393 ++cPt; 1394 ++oPt; 1395 } 1396 return true; 1397} 1398 1399bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, 1400 const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { 1401 SkASSERT(coin1s->segment() == coin2s->segment()); 1402 *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT)); 1403 *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT)); 1404 return *overS < *overE; 1405} 1406 1407// Commented-out lines keep this in sync with debugRelease() 1408void SkOpCoincidence::release(const SkOpSegment* deleted) { 1409 SkCoincidentSpans* coin = fHead; 1410 if (!coin) { 1411 return; 1412 } 1413 do { 1414 if (coin->coinPtTStart()->segment() == deleted 1415 || coin->coinPtTEnd()->segment() == deleted 1416 || coin->oppPtTStart()->segment() == deleted 1417 || coin->oppPtTEnd()->segment() == deleted) { 1418 this->release(fHead, coin); 1419 } 1420 } while ((coin = coin->next())); 1421} 1422