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 bool SkOpCoincidence::extend(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, 12 SkOpPtT* oppPtTEnd) { 13 // if there is an existing pair that overlaps the addition, extend it 14 SkCoincidentSpans* coinRec = fHead; 15 if (coinRec) { 16 do { 17 if (coinRec->fCoinPtTStart->segment() != coinPtTStart->segment()) { 18 continue; 19 } 20 if (coinRec->fOppPtTStart->segment() != oppPtTStart->segment()) { 21 continue; 22 } 23 if (coinRec->fCoinPtTStart->fT > coinPtTEnd->fT) { 24 continue; 25 } 26 if (coinRec->fCoinPtTEnd->fT < coinPtTStart->fT) { 27 continue; 28 } 29 if (coinRec->fCoinPtTStart->fT > coinPtTStart->fT) { 30 coinRec->fCoinPtTStart = coinPtTStart; 31 coinRec->fOppPtTStart = oppPtTStart; 32 } 33 if (coinRec->fCoinPtTEnd->fT < coinPtTEnd->fT) { 34 coinRec->fCoinPtTEnd = coinPtTEnd; 35 coinRec->fOppPtTEnd = oppPtTEnd; 36 } 37 return true; 38 } while ((coinRec = coinRec->fNext)); 39 } 40 return false; 41 } 42 43 void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, 44 SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) { 45 SkASSERT(coinPtTStart->fT < coinPtTEnd->fT); 46 bool flipped = oppPtTStart->fT > oppPtTEnd->fT; 47 SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator); 48 coinRec->fNext = this->fHead; 49 coinRec->fCoinPtTStart = coinPtTStart; 50 coinRec->fCoinPtTEnd = coinPtTEnd; 51 coinRec->fOppPtTStart = oppPtTStart; 52 coinRec->fOppPtTEnd = oppPtTEnd; 53 coinRec->fFlipped = flipped; 54 SkDEBUGCODE(coinRec->fID = fDebugState->nextCoinID()); 55 56 this->fHead = coinRec; 57 } 58 59 static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd, 60 const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) { 61 double denom = overE->fT - overS->fT; 62 double start = 0 < denom ? tStart : tEnd; 63 double end = 0 < denom ? tEnd : tStart; 64 double sRatio = (start - overS->fT) / denom; 65 double eRatio = (end - overS->fT) / denom; 66 *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio; 67 *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; 68 } 69 70 bool SkOpCoincidence::addExpanded(SkChunkAlloc* allocator 71 PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* globalState)) { 72 #if DEBUG_VALIDATE 73 globalState->setPhase(SkOpGlobalState::kIntersecting); 74 #endif 75 // for each coincident pair, match the spans 76 // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span 77 SkCoincidentSpans* coin = this->fHead; 78 SkASSERT(coin); 79 do { 80 SkOpPtT* startPtT = coin->fCoinPtTStart; 81 SkOpPtT* oStartPtT = coin->fOppPtTStart; 82 SkASSERT(startPtT->contains(oStartPtT)); 83 SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd)); 84 SkOpSpanBase* start = startPtT->span(); 85 SkOpSpanBase* oStart = oStartPtT->span(); 86 const SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 87 const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); 88 if (oEnd->deleted()) { 89 return false; 90 } 91 SkOpSpanBase* test = start->upCast()->next(); 92 SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next(); 93 while (test != end || oTest != oEnd) { 94 if (!test->ptT()->contains(oTest->ptT())) { 95 // use t ranges to guess which one is missing 96 double startRange = coin->fCoinPtTEnd->fT - startPtT->fT; 97 if (!startRange) { 98 return false; 99 } 100 double startPart = (test->t() - startPtT->fT) / startRange; 101 double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT; 102 if (!oStartRange) { 103 return false; 104 } 105 double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange; 106 if (startPart == oStartPart) { 107 return false; 108 } 109 SkOpPtT* newPt; 110 if (startPart < oStartPart) { 111 double newT = oStartPtT->fT + oStartRange * startPart; 112 newPt = oStart->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator); 113 if (!newPt) { 114 return false; 115 } 116 newPt->fPt = test->pt(); 117 test->ptT()->addOpp(newPt); 118 } else { 119 double newT = startPtT->fT + startRange * oStartPart; 120 newPt = start->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator); 121 if (!newPt) { 122 return false; 123 } 124 newPt->fPt = oTest->pt(); 125 oTest->ptT()->addOpp(newPt); 126 } 127 // start over 128 test = start; 129 oTest = oStart; 130 } 131 if (test != end) { 132 test = test->upCast()->next(); 133 } 134 if (oTest != oEnd) { 135 oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next(); 136 } 137 } 138 } while ((coin = coin->fNext)); 139 #if DEBUG_VALIDATE 140 globalState->setPhase(SkOpGlobalState::kWalking); 141 #endif 142 return true; 143 } 144 145 bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s, 146 SkOpPtT* over1e, SkChunkAlloc* allocator) { 147 SkCoincidentSpans* check = this->fTop; 148 do { 149 if (check->fCoinPtTStart->span() == over1s->span() 150 && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) { 151 SkASSERT(check->fCoinPtTEnd->span() == over1e->span() 152 || !fDebugState->debugRunFail()); 153 SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span() 154 || !fDebugState->debugRunFail()); 155 return false; 156 } 157 if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span() 158 && check->fOppPtTStart->span() == over1s->span()) { 159 SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span() 160 || !fDebugState->debugRunFail()); 161 SkASSERT(check->fOppPtTEnd->span() == over1e->span() 162 || !fDebugState->debugRunFail()); 163 return false; 164 } 165 } while ((check = check->fNext)); 166 this->add(outer->fCoinPtTStart, outer->fCoinPtTEnd, over1s, over1e, allocator); 167 #if 0 168 // FIXME: up to four flavors could be added -- do we need only one? 169 #endif 170 return true; 171 } 172 173 bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, 174 const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd, 175 SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 176 SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) { 177 double coinTs, coinTe, oppTs, oppTe; 178 t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe); 179 t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe); 180 SkOpSegment* coinSeg = coinPtTStart->segment(); 181 SkOpSegment* oppSeg = oppPtTStart->segment(); 182 SkASSERT(coinSeg != oppSeg); 183 SkCoincidentSpans* check = this->fTop; 184 do { 185 const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment(); 186 if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) { 187 continue; 188 } 189 const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment(); 190 if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) { 191 continue; 192 } 193 int cTs = coinTs; 194 int cTe = coinTe; 195 int oTs = oppTs; 196 int oTe = oppTe; 197 if (checkCoinSeg != coinSeg) { 198 SkASSERT(checkOppSeg != oppSeg); 199 SkTSwap(cTs, oTs); 200 SkTSwap(cTe, oTe); 201 } 202 int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT) 203 + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT) 204 + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT) 205 + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT); 206 // SkASSERT(tweenCount == 0 || tweenCount == 4); 207 if (tweenCount) { 208 return false; 209 } 210 } while ((check = check->fNext)); 211 if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) { 212 SkTSwap(oppTs, oppTe); 213 } 214 if (coinTs > coinTe) { 215 SkTSwap(coinTs, coinTe); 216 SkTSwap(oppTs, oppTe); 217 } 218 SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator); 219 SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator); 220 SkASSERT(cs != ce); 221 SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator); 222 SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator); 223 // SkASSERT(os != oe); 224 cs->addOpp(os); 225 ce->addOpp(oe); 226 this->add(cs, ce, os, oe, allocator); 227 return true; 228 } 229 230 /* detects overlaps of different coincident runs on same segment */ 231 /* does not detect overlaps for pairs without any segments in common */ 232 bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) { 233 SkCoincidentSpans* outer = fHead; 234 if (!outer) { 235 return true; 236 } 237 bool added = false; 238 fTop = outer; 239 fHead = nullptr; 240 do { 241 // addifmissing can modify the list that this is walking 242 // save head so that walker can iterate over old data unperturbed 243 // addifmissing adds to head freely then add saved head in the end 244 const SkOpSegment* outerCoin = outer->fCoinPtTStart->segment(); 245 SkASSERT(outerCoin == outer->fCoinPtTEnd->segment()); 246 const SkOpSegment* outerOpp = outer->fOppPtTStart->segment(); 247 SkASSERT(outerOpp == outer->fOppPtTEnd->segment()); 248 SkCoincidentSpans* inner = outer; 249 while ((inner = inner->fNext)) { 250 double overS, overE; 251 const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment(); 252 SkASSERT(innerCoin == inner->fCoinPtTEnd->segment()); 253 const SkOpSegment* innerOpp = inner->fOppPtTStart->segment(); 254 SkASSERT(innerOpp == inner->fOppPtTEnd->segment()); 255 if (outerCoin == innerCoin 256 && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, 257 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { 258 added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, 259 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, 260 outer->fOppPtTStart, outer->fOppPtTEnd, 261 inner->fOppPtTStart, inner->fOppPtTEnd, allocator); 262 } else if (outerCoin == innerOpp 263 && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, 264 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { 265 added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, 266 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, 267 outer->fOppPtTStart, outer->fOppPtTEnd, 268 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator); 269 } else if (outerOpp == innerCoin 270 && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, 271 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { 272 added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, 273 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, 274 outer->fCoinPtTStart, outer->fCoinPtTEnd, 275 inner->fOppPtTStart, inner->fOppPtTEnd, allocator); 276 } else if (outerOpp == innerOpp 277 && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, 278 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { 279 added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, 280 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, 281 outer->fCoinPtTStart, outer->fCoinPtTEnd, 282 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator); 283 } else if (outerCoin != innerCoin) { 284 // check to see if outer span overlaps the inner span 285 // look for inner segment in pt-t list 286 // if present, and if t values are in coincident range 287 // add two pairs of new coincidence 288 SkOpPtT* testS = outer->fCoinPtTStart->contains(innerCoin); 289 SkOpPtT* testE = outer->fCoinPtTEnd->contains(innerCoin); 290 if (testS && testS->fT >= inner->fCoinPtTStart->fT 291 && testE && testE->fT <= inner->fCoinPtTEnd->fT 292 && this->testForCoincidence(outer, testS, testE)) { 293 added |= this->addIfMissing(outer, testS, testE, allocator); 294 } else { 295 testS = inner->fCoinPtTStart->contains(outerCoin); 296 testE = inner->fCoinPtTEnd->contains(outerCoin); 297 if (testS && testS->fT >= outer->fCoinPtTStart->fT 298 && testE && testE->fT <= outer->fCoinPtTEnd->fT 299 && this->testForCoincidence(inner, testS, testE)) { 300 added |= this->addIfMissing(inner, testS, testE, allocator); 301 } 302 } 303 } 304 #if 0 && DEBUG_COINCIDENCE 305 SkString miss; 306 miss.printf("addMissing inner=%d outer=%d", inner->debugID(), outer->debugID()); 307 DEBUG_COINCIDENCE_HEALTH(fDebugState->contourHead(), miss.c_str()); 308 #endif 309 } 310 } while ((outer = outer->fNext)); 311 SkCoincidentSpans** headPtr = &fHead; 312 while (*headPtr) { 313 SkCoincidentSpans** headNext = &(*headPtr)->fNext; 314 if (*headNext) { 315 break; 316 } 317 headPtr = headNext; 318 } 319 *headPtr = fTop; 320 return added; 321 } 322 323 void SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegment* seg2, 324 SkOpSegment* seg2o, SkOpPtT* overS, SkOpPtT* overE, SkChunkAlloc* allocator) { 325 SkOpPtT* s1 = overS->find(seg1); 326 SkOpPtT* e1 = overE->find(seg1); 327 if (!s1->starter(e1)->span()->upCast()->windValue()) { 328 s1 = overS->find(seg1o); 329 e1 = overE->find(seg1o); 330 if (!s1->starter(e1)->span()->upCast()->windValue()) { 331 return; 332 } 333 } 334 SkOpPtT* s2 = overS->find(seg2); 335 SkOpPtT* e2 = overE->find(seg2); 336 if (!s2->starter(e2)->span()->upCast()->windValue()) { 337 s2 = overS->find(seg2o); 338 e2 = overE->find(seg2o); 339 if (!s2->starter(e2)->span()->upCast()->windValue()) { 340 return; 341 } 342 } 343 if (s1->segment() == s2->segment()) { 344 return; 345 } 346 if (s1->fT > e1->fT) { 347 SkTSwap(s1, e1); 348 SkTSwap(s2, e2); 349 } 350 this->add(s1, e1, s2, e2, allocator); 351 } 352 353 bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 354 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, bool flipped) const { 355 const SkCoincidentSpans* coin = fHead; 356 if (!coin) { 357 return false; 358 } 359 do { 360 if (coin->fCoinPtTStart == coinPtTStart && coin->fCoinPtTEnd == coinPtTEnd 361 && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd 362 && coin->fFlipped == flipped) { 363 return true; 364 } 365 } while ((coin = coin->fNext)); 366 return false; 367 } 368 369 // walk span sets in parallel, moving winding from one to the other 370 bool SkOpCoincidence::apply() { 371 SkCoincidentSpans* coin = fHead; 372 if (!coin) { 373 return true; 374 } 375 do { 376 SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); 377 if (start->deleted()) { 378 continue; 379 } 380 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 381 SkASSERT(start == start->starter(end)); 382 bool flipped = coin->fFlipped; 383 SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast(); 384 if (oStart->deleted()) { 385 continue; 386 } 387 SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span(); 388 SkASSERT(oStart == oStart->starter(oEnd)); 389 SkOpSegment* segment = start->segment(); 390 SkOpSegment* oSegment = oStart->segment(); 391 bool operandSwap = segment->operand() != oSegment->operand(); 392 if (flipped) { 393 if (oEnd->deleted()) { 394 continue; 395 } 396 do { 397 SkOpSpanBase* oNext = oStart->next(); 398 if (oNext == oEnd) { 399 break; 400 } 401 oStart = oNext->upCast(); 402 } while (true); 403 } 404 do { 405 int windValue = start->windValue(); 406 int oppValue = start->oppValue(); 407 int oWindValue = oStart->windValue(); 408 int oOppValue = oStart->oppValue(); 409 // winding values are added or subtracted depending on direction and wind type 410 // same or opposite values are summed depending on the operand value 411 int windDiff = operandSwap ? oOppValue : oWindValue; 412 int oWindDiff = operandSwap ? oppValue : windValue; 413 if (!flipped) { 414 windDiff = -windDiff; 415 oWindDiff = -oWindDiff; 416 } 417 if (windValue && (windValue > windDiff || (windValue == windDiff 418 && oWindValue <= oWindDiff))) { 419 if (operandSwap) { 420 SkTSwap(oWindValue, oOppValue); 421 } 422 if (flipped) { 423 windValue -= oWindValue; 424 oppValue -= oOppValue; 425 } else { 426 windValue += oWindValue; 427 oppValue += oOppValue; 428 } 429 if (segment->isXor()) { 430 windValue &= 1; 431 } 432 if (segment->oppXor()) { 433 oppValue &= 1; 434 } 435 oWindValue = oOppValue = 0; 436 } else { 437 if (operandSwap) { 438 SkTSwap(windValue, oppValue); 439 } 440 if (flipped) { 441 oWindValue -= windValue; 442 oOppValue -= oppValue; 443 } else { 444 oWindValue += windValue; 445 oOppValue += oppValue; 446 } 447 if (oSegment->isXor()) { 448 oWindValue &= 1; 449 } 450 if (oSegment->oppXor()) { 451 oOppValue &= 1; 452 } 453 windValue = oppValue = 0; 454 } 455 start->setWindValue(windValue); 456 start->setOppValue(oppValue); 457 oStart->setWindValue(oWindValue); 458 oStart->setOppValue(oOppValue); 459 if (!windValue && !oppValue) { 460 segment->markDone(start); 461 } 462 if (!oWindValue && !oOppValue) { 463 oSegment->markDone(oStart); 464 } 465 SkOpSpanBase* next = start->next(); 466 SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); 467 if (next == end) { 468 break; 469 } 470 if (!next->upCastable()) { 471 return false; 472 } 473 start = next->upCast(); 474 // if the opposite ran out too soon, just reuse the last span 475 if (!oNext || !oNext->upCastable()) { 476 oNext = oStart; 477 } 478 oStart = oNext->upCast(); 479 } while (true); 480 } while ((coin = coin->fNext)); 481 return true; 482 } 483 484 void SkOpCoincidence::detach(SkCoincidentSpans* remove) { 485 SkCoincidentSpans* coin = fHead; 486 SkCoincidentSpans* prev = nullptr; 487 SkCoincidentSpans* next; 488 do { 489 next = coin->fNext; 490 if (coin == remove) { 491 if (prev) { 492 prev->fNext = next; 493 } else { 494 fHead = next; 495 } 496 break; 497 } 498 prev = coin; 499 } while ((coin = next)); 500 SkASSERT(coin); 501 } 502 503 bool SkOpCoincidence::expand() { 504 SkCoincidentSpans* coin = fHead; 505 if (!coin) { 506 return false; 507 } 508 bool expanded = false; 509 do { 510 SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); 511 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 512 SkOpSegment* segment = coin->fCoinPtTStart->segment(); 513 SkOpSegment* oppSegment = coin->fOppPtTStart->segment(); 514 SkOpSpan* prev = start->prev(); 515 SkOpPtT* oppPtT; 516 if (prev && (oppPtT = prev->contains(oppSegment))) { 517 double midT = (prev->t() + start->t()) / 2; 518 if (segment->isClose(midT, oppSegment)) { 519 coin->fCoinPtTStart = prev->ptT(); 520 coin->fOppPtTStart = oppPtT; 521 expanded = true; 522 } 523 } 524 SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); 525 if (next && (oppPtT = next->contains(oppSegment))) { 526 double midT = (end->t() + next->t()) / 2; 527 if (segment->isClose(midT, oppSegment)) { 528 coin->fCoinPtTEnd = next->ptT(); 529 coin->fOppPtTEnd = oppPtT; 530 expanded = true; 531 } 532 } 533 } while ((coin = coin->fNext)); 534 return expanded; 535 } 536 537 void SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps, SkChunkAlloc* allocator) const { 538 overlaps->fHead = overlaps->fTop = nullptr; 539 SkDEBUGCODE_(overlaps->debugSetGlobalState(fDebugState)); 540 SkCoincidentSpans* outer = fHead; 541 while (outer) { 542 SkOpSegment* outerCoin = outer->fCoinPtTStart->segment(); 543 SkOpSegment* outerOpp = outer->fOppPtTStart->segment(); 544 SkCoincidentSpans* inner = outer; 545 while ((inner = inner->fNext)) { 546 SkOpSegment* innerCoin = inner->fCoinPtTStart->segment(); 547 if (outerCoin == innerCoin) { 548 continue; // both winners are the same segment, so there's no additional overlap 549 } 550 SkOpSegment* innerOpp = inner->fOppPtTStart->segment(); 551 SkOpPtT* overlapS, * overlapE; 552 if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->fOppPtTStart, outer->fOppPtTEnd, 553 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overlapS, &overlapE)) 554 || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->fCoinPtTStart, 555 outer->fCoinPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, 556 &overlapS, &overlapE)) 557 || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->fOppPtTStart, 558 outer->fOppPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd, 559 &overlapS, &overlapE))) { 560 overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp, 561 overlapS, overlapE, allocator); 562 } 563 } 564 outer = outer->fNext; 565 } 566 } 567 568 void SkOpCoincidence::fixAligned() { 569 SkCoincidentSpans* coin = fHead; 570 if (!coin) { 571 return; 572 } 573 do { 574 if (coin->fCoinPtTStart->deleted()) { 575 coin->fCoinPtTStart = coin->fCoinPtTStart->doppelganger(); 576 } 577 if (coin->fCoinPtTEnd->deleted()) { 578 coin->fCoinPtTEnd = coin->fCoinPtTEnd->doppelganger(); 579 } 580 if (coin->fOppPtTStart->deleted()) { 581 coin->fOppPtTStart = coin->fOppPtTStart->doppelganger(); 582 } 583 if (coin->fOppPtTEnd->deleted()) { 584 coin->fOppPtTEnd = coin->fOppPtTEnd->doppelganger(); 585 } 586 } while ((coin = coin->fNext)); 587 coin = fHead; 588 SkCoincidentSpans** priorPtr = &fHead; 589 do { 590 if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd) 591 || coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) { 592 *priorPtr = coin->fNext; 593 continue; 594 } 595 priorPtr = &coin->fNext; 596 } while ((coin = coin->fNext)); 597 } 598 599 void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) { 600 SkCoincidentSpans* coin = fHead; 601 if (!coin) { 602 return; 603 } 604 do { 605 if (coin->fCoinPtTStart == deleted) { 606 if (coin->fCoinPtTEnd->span() == kept->span()) { 607 this->detach(coin); 608 continue; 609 } 610 coin->fCoinPtTStart = kept; 611 } 612 if (coin->fCoinPtTEnd == deleted) { 613 if (coin->fCoinPtTStart->span() == kept->span()) { 614 this->detach(coin); 615 continue; 616 } 617 coin->fCoinPtTEnd = kept; 618 } 619 if (coin->fOppPtTStart == deleted) { 620 if (coin->fOppPtTEnd->span() == kept->span()) { 621 this->detach(coin); 622 continue; 623 } 624 coin->fOppPtTStart = kept; 625 } 626 if (coin->fOppPtTEnd == deleted) { 627 if (coin->fOppPtTStart->span() == kept->span()) { 628 this->detach(coin); 629 continue; 630 } 631 coin->fOppPtTEnd = kept; 632 } 633 } while ((coin = coin->fNext)); 634 } 635 636 /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */ 637 bool SkOpCoincidence::mark() { 638 SkCoincidentSpans* coin = fHead; 639 if (!coin) { 640 return true; 641 } 642 do { 643 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 644 if (end->deleted()) { 645 return false; 646 } 647 SkOpSpanBase* oldEnd = end; 648 SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end); 649 SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); 650 if (oEnd->deleted()) { 651 return false; 652 } 653 SkOpSpanBase* oOldEnd = oEnd; 654 SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd); 655 bool flipped = (end == oldEnd) != (oEnd == oOldEnd); 656 if (flipped) { 657 SkTSwap(oStart, oEnd); 658 } 659 SkOpSpanBase* next = start; 660 SkOpSpanBase* oNext = oStart; 661 do { 662 next = next->upCast()->next(); 663 oNext = flipped ? oNext->prev() : oNext->upCast()->next(); 664 if (next == end || oNext == oEnd) { 665 break; 666 } 667 if (!next->containsCoinEnd(oNext)) { 668 next->insertCoinEnd(oNext); 669 } 670 SkOpSpan* nextSpan = next->upCast(); 671 SkOpSpan* oNextSpan = oNext->upCast(); 672 if (!nextSpan->containsCoincidence(oNextSpan)) { 673 nextSpan->insertCoincidence(oNextSpan); 674 } 675 } while (true); 676 } while ((coin = coin->fNext)); 677 return true; 678 } 679 680 bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, 681 const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { 682 SkASSERT(coin1s->segment() == coin2s->segment()); 683 *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT)); 684 *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT)); 685 return *overS < *overE; 686 } 687 688 bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS, 689 const SkOpPtT* testE) const { 690 return testS->segment()->testForCoincidence(testS, testE, testS->span(), 691 testE->span(), outer->fCoinPtTStart->segment(), 120000); // FIXME: replace with tuned 692 } 693
