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