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 this->fHead = coinRec; 55 } 56 57 static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd, 58 const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) { 59 double denom = overE->fT - overS->fT; 60 double start = 0 < denom ? tStart : tEnd; 61 double end = 0 < denom ? tEnd : tStart; 62 double sRatio = (start - overS->fT) / denom; 63 double eRatio = (end - overS->fT) / denom; 64 *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio; 65 *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; 66 } 67 68 bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, 69 const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd, 70 SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, 71 SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) { 72 double coinTs, coinTe, oppTs, oppTe; 73 t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe); 74 t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe); 75 SkOpSegment* coinSeg = coinPtTStart->segment(); 76 SkOpSegment* oppSeg = oppPtTStart->segment(); 77 SkASSERT(coinSeg != oppSeg); 78 SkCoincidentSpans* check = this->fHead; 79 do { 80 const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment(); 81 if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) { 82 continue; 83 } 84 const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment(); 85 if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) { 86 continue; 87 } 88 int cTs = coinTs; 89 int cTe = coinTe; 90 int oTs = oppTs; 91 int oTe = oppTe; 92 if (checkCoinSeg != coinSeg) { 93 SkASSERT(checkOppSeg != oppSeg); 94 SkTSwap(cTs, oTs); 95 SkTSwap(cTe, oTe); 96 } 97 int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT) 98 + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT) 99 + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT) 100 + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT); 101 // SkASSERT(tweenCount == 0 || tweenCount == 4); 102 if (tweenCount) { 103 return true; 104 } 105 } while ((check = check->fNext)); 106 if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) { 107 SkTSwap(oppTs, oppTe); 108 } 109 if (coinTs > coinTe) { 110 SkTSwap(coinTs, coinTe); 111 SkTSwap(oppTs, oppTe); 112 } 113 SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator); 114 SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator); 115 if (cs == ce) { 116 return false; 117 } 118 SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator); 119 SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator); 120 SkASSERT(os != oe); 121 cs->addOpp(os); 122 ce->addOpp(oe); 123 this->add(cs, ce, os, oe, allocator); 124 return true; 125 } 126 127 bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) { 128 SkCoincidentSpans* outer = this->fHead; 129 if (!outer) { 130 return true; 131 } 132 do { 133 SkCoincidentSpans* inner = outer; 134 while ((inner = inner->fNext)) { 135 double overS, overE; 136 if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, 137 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { 138 if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, 139 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, 140 outer->fOppPtTStart, outer->fOppPtTEnd, 141 inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { 142 return false; 143 } 144 } else if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, 145 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { 146 if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, 147 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, 148 outer->fOppPtTStart, outer->fOppPtTEnd, 149 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { 150 return false; 151 } 152 } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, 153 inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { 154 if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, 155 inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, 156 outer->fCoinPtTStart, outer->fCoinPtTEnd, 157 inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { 158 return false; 159 } 160 } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, 161 inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { 162 if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, 163 inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, 164 outer->fCoinPtTStart, outer->fCoinPtTEnd, 165 inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { 166 return false; 167 } 168 } 169 } 170 171 } while ((outer = outer->fNext)); 172 return true; 173 } 174 175 bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, 176 SkOpPtT* oppPtTEnd, bool flipped) { 177 SkCoincidentSpans* coin = fHead; 178 if (!coin) { 179 return false; 180 } 181 do { 182 if (coin->fCoinPtTStart == coinPtTStart && coin->fCoinPtTEnd == coinPtTEnd 183 && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd 184 && coin->fFlipped == flipped) { 185 return true; 186 } 187 } while ((coin = coin->fNext)); 188 return false; 189 } 190 191 // walk span sets in parallel, moving winding from one to the other 192 bool SkOpCoincidence::apply() { 193 SkCoincidentSpans* coin = fHead; 194 if (!coin) { 195 return true; 196 } 197 do { 198 SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); 199 if (start->deleted()) { 200 continue; 201 } 202 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 203 SkASSERT(start == start->starter(end)); 204 bool flipped = coin->fFlipped; 205 SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast(); 206 if (oStart->deleted()) { 207 continue; 208 } 209 SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span(); 210 SkASSERT(oStart == oStart->starter(oEnd)); 211 SkOpSegment* segment = start->segment(); 212 SkOpSegment* oSegment = oStart->segment(); 213 bool operandSwap = segment->operand() != oSegment->operand(); 214 if (flipped) { 215 do { 216 SkOpSpanBase* oNext = oStart->next(); 217 if (oNext == oEnd) { 218 break; 219 } 220 oStart = oNext->upCast(); 221 } while (true); 222 } 223 do { 224 int windValue = start->windValue(); 225 int oppValue = start->oppValue(); 226 int oWindValue = oStart->windValue(); 227 int oOppValue = oStart->oppValue(); 228 // winding values are added or subtracted depending on direction and wind type 229 // same or opposite values are summed depending on the operand value 230 int windDiff = operandSwap ? oOppValue : oWindValue; 231 int oWindDiff = operandSwap ? oppValue : windValue; 232 if (!flipped) { 233 windDiff = -windDiff; 234 oWindDiff = -oWindDiff; 235 } 236 if (windValue && (windValue > windDiff || (windValue == windDiff 237 && oWindValue <= oWindDiff))) { 238 if (operandSwap) { 239 SkTSwap(oWindValue, oOppValue); 240 } 241 if (flipped) { 242 windValue -= oWindValue; 243 oppValue -= oOppValue; 244 } else { 245 windValue += oWindValue; 246 oppValue += oOppValue; 247 } 248 if (segment->isXor()) { 249 windValue &= 1; 250 } 251 if (segment->oppXor()) { 252 oppValue &= 1; 253 } 254 oWindValue = oOppValue = 0; 255 } else { 256 if (operandSwap) { 257 SkTSwap(windValue, oppValue); 258 } 259 if (flipped) { 260 oWindValue -= windValue; 261 oOppValue -= oppValue; 262 } else { 263 oWindValue += windValue; 264 oOppValue += oppValue; 265 } 266 if (oSegment->isXor()) { 267 oWindValue &= 1; 268 } 269 if (oSegment->oppXor()) { 270 oOppValue &= 1; 271 } 272 windValue = oppValue = 0; 273 } 274 start->setWindValue(windValue); 275 start->setOppValue(oppValue); 276 oStart->setWindValue(oWindValue); 277 oStart->setOppValue(oOppValue); 278 if (!windValue && !oppValue) { 279 segment->markDone(start); 280 } 281 if (!oWindValue && !oOppValue) { 282 oSegment->markDone(oStart); 283 } 284 SkOpSpanBase* next = start->next(); 285 SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); 286 if (next == end) { 287 break; 288 } 289 start = next->upCast(); 290 // if the opposite ran out too soon, just reuse the last span 291 if (!oNext || !oNext->upCastable()) { 292 oNext = oStart; 293 } 294 oStart = oNext->upCast(); 295 } while (true); 296 } while ((coin = coin->fNext)); 297 return true; 298 } 299 300 void SkOpCoincidence::detach(SkCoincidentSpans* remove) { 301 SkCoincidentSpans* coin = fHead; 302 SkCoincidentSpans* prev = NULL; 303 SkCoincidentSpans* next; 304 do { 305 next = coin->fNext; 306 if (coin == remove) { 307 if (prev) { 308 prev->fNext = next; 309 } else { 310 fHead = next; 311 } 312 break; 313 } 314 prev = coin; 315 } while ((coin = next)); 316 SkASSERT(coin); 317 } 318 319 void SkOpCoincidence::expand() { 320 SkCoincidentSpans* coin = fHead; 321 if (!coin) { 322 return; 323 } 324 do { 325 SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); 326 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 327 SkOpSegment* segment = coin->fCoinPtTStart->segment(); 328 SkOpSegment* oppSegment = coin->fOppPtTStart->segment(); 329 SkOpSpan* prev = start->prev(); 330 SkOpPtT* oppPtT; 331 if (prev && (oppPtT = prev->contains(oppSegment))) { 332 double midT = (prev->t() + start->t()) / 2; 333 if (segment->isClose(midT, oppSegment)) { 334 coin->fCoinPtTStart = prev->ptT(); 335 coin->fOppPtTStart = oppPtT; 336 } 337 } 338 SkOpSpanBase* next = end->final() ? NULL : end->upCast()->next(); 339 if (next && (oppPtT = next->contains(oppSegment))) { 340 double midT = (end->t() + next->t()) / 2; 341 if (segment->isClose(midT, oppSegment)) { 342 coin->fCoinPtTEnd = next->ptT(); 343 coin->fOppPtTEnd = oppPtT; 344 } 345 } 346 } while ((coin = coin->fNext)); 347 } 348 349 void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) { 350 SkCoincidentSpans* coin = fHead; 351 if (!coin) { 352 return; 353 } 354 do { 355 if (coin->fCoinPtTStart == deleted) { 356 if (coin->fCoinPtTEnd->span() == kept->span()) { 357 return this->detach(coin); 358 } 359 coin->fCoinPtTStart = kept; 360 } 361 if (coin->fCoinPtTEnd == deleted) { 362 if (coin->fCoinPtTStart->span() == kept->span()) { 363 return this->detach(coin); 364 } 365 coin->fCoinPtTEnd = kept; 366 } 367 if (coin->fOppPtTStart == deleted) { 368 if (coin->fOppPtTEnd->span() == kept->span()) { 369 return this->detach(coin); 370 } 371 coin->fOppPtTStart = kept; 372 } 373 if (coin->fOppPtTEnd == deleted) { 374 if (coin->fOppPtTStart->span() == kept->span()) { 375 return this->detach(coin); 376 } 377 coin->fOppPtTEnd = kept; 378 } 379 } while ((coin = coin->fNext)); 380 } 381 382 void SkOpCoincidence::mark() { 383 SkCoincidentSpans* coin = fHead; 384 if (!coin) { 385 return; 386 } 387 do { 388 SkOpSpanBase* end = coin->fCoinPtTEnd->span(); 389 SkOpSpanBase* oldEnd = end; 390 SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end); 391 SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); 392 SkOpSpanBase* oOldEnd = oEnd; 393 SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd); 394 bool flipped = (end == oldEnd) != (oEnd == oOldEnd); 395 if (flipped) { 396 SkTSwap(oStart, oEnd); 397 } 398 SkOpSpanBase* next = start; 399 SkOpSpanBase* oNext = oStart; 400 // check to see if coincident span could be bigger 401 402 do { 403 next = next->upCast()->next(); 404 oNext = flipped ? oNext->prev() : oNext->upCast()->next(); 405 if (next == end || oNext == oEnd) { 406 break; 407 } 408 if (!next->containsCoinEnd(oNext)) { 409 next->insertCoinEnd(oNext); 410 } 411 SkOpSpan* nextSpan = next->upCast(); 412 SkOpSpan* oNextSpan = oNext->upCast(); 413 if (!nextSpan->containsCoincidence(oNextSpan)) { 414 nextSpan->insertCoincidence(oNextSpan); 415 } 416 } while (true); 417 } while ((coin = coin->fNext)); 418 } 419 420 bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, 421 const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { 422 if (coin1s->segment() != coin2s->segment()) { 423 return false; 424 } 425 *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT)); 426 *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT)); 427 return *overS < *overE; 428 } 429
