| /* |
| * Copyright 2015 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| #include "SkOpCoincidence.h" |
| #include "SkOpSegment.h" |
| #include "SkPathOpsTSect.h" |
| |
| bool SkOpCoincidence::extend(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, |
| SkOpPtT* oppPtTEnd) { |
| // if there is an existing pair that overlaps the addition, extend it |
| SkCoincidentSpans* coinRec = fHead; |
| if (coinRec) { |
| do { |
| if (coinRec->fCoinPtTStart->segment() != coinPtTStart->segment()) { |
| continue; |
| } |
| if (coinRec->fOppPtTStart->segment() != oppPtTStart->segment()) { |
| continue; |
| } |
| if (coinRec->fCoinPtTStart->fT > coinPtTEnd->fT) { |
| continue; |
| } |
| if (coinRec->fCoinPtTEnd->fT < coinPtTStart->fT) { |
| continue; |
| } |
| if (coinRec->fCoinPtTStart->fT > coinPtTStart->fT) { |
| coinRec->fCoinPtTStart = coinPtTStart; |
| coinRec->fOppPtTStart = oppPtTStart; |
| } |
| if (coinRec->fCoinPtTEnd->fT < coinPtTEnd->fT) { |
| coinRec->fCoinPtTEnd = coinPtTEnd; |
| coinRec->fOppPtTEnd = oppPtTEnd; |
| } |
| return true; |
| } while ((coinRec = coinRec->fNext)); |
| } |
| return false; |
| } |
| |
| void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, |
| SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) { |
| SkASSERT(coinPtTStart->fT < coinPtTEnd->fT); |
| bool flipped = oppPtTStart->fT > oppPtTEnd->fT; |
| SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator); |
| coinRec->fNext = this->fHead; |
| coinRec->fCoinPtTStart = coinPtTStart; |
| coinRec->fCoinPtTEnd = coinPtTEnd; |
| coinRec->fOppPtTStart = oppPtTStart; |
| coinRec->fOppPtTEnd = oppPtTEnd; |
| coinRec->fFlipped = flipped; |
| this->fHead = coinRec; |
| } |
| |
| static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd, |
| const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) { |
| double denom = overE->fT - overS->fT; |
| double start = 0 < denom ? tStart : tEnd; |
| double end = 0 < denom ? tEnd : tStart; |
| double sRatio = (start - overS->fT) / denom; |
| double eRatio = (end - overS->fT) / denom; |
| *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio; |
| *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio; |
| } |
| |
| bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e, |
| const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd, |
| SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
| SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) { |
| double coinTs, coinTe, oppTs, oppTe; |
| t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe); |
| t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe); |
| SkOpSegment* coinSeg = coinPtTStart->segment(); |
| SkOpSegment* oppSeg = oppPtTStart->segment(); |
| SkASSERT(coinSeg != oppSeg); |
| SkCoincidentSpans* check = this->fHead; |
| do { |
| const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment(); |
| if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) { |
| continue; |
| } |
| const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment(); |
| if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) { |
| continue; |
| } |
| int cTs = coinTs; |
| int cTe = coinTe; |
| int oTs = oppTs; |
| int oTe = oppTe; |
| if (checkCoinSeg != coinSeg) { |
| SkASSERT(checkOppSeg != oppSeg); |
| SkTSwap(cTs, oTs); |
| SkTSwap(cTe, oTe); |
| } |
| int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT) |
| + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT) |
| + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT) |
| + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT); |
| // SkASSERT(tweenCount == 0 || tweenCount == 4); |
| if (tweenCount) { |
| return true; |
| } |
| } while ((check = check->fNext)); |
| if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) { |
| SkTSwap(oppTs, oppTe); |
| } |
| if (coinTs > coinTe) { |
| SkTSwap(coinTs, coinTe); |
| SkTSwap(oppTs, oppTe); |
| } |
| SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator); |
| SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator); |
| if (cs == ce) { |
| return false; |
| } |
| SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator); |
| SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator); |
| SkASSERT(os != oe); |
| cs->addOpp(os); |
| ce->addOpp(oe); |
| this->add(cs, ce, os, oe, allocator); |
| return true; |
| } |
| |
| bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) { |
| SkCoincidentSpans* outer = this->fHead; |
| if (!outer) { |
| return true; |
| } |
| do { |
| SkCoincidentSpans* inner = outer; |
| while ((inner = inner->fNext)) { |
| double overS, overE; |
| if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
| inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { |
| if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
| inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, |
| outer->fOppPtTStart, outer->fOppPtTEnd, |
| inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { |
| return false; |
| } |
| } else if (this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
| inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { |
| if (!this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd, |
| inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, |
| outer->fOppPtTStart, outer->fOppPtTEnd, |
| inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { |
| return false; |
| } |
| } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, |
| inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) { |
| if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, |
| inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE, |
| outer->fCoinPtTStart, outer->fCoinPtTEnd, |
| inner->fOppPtTStart, inner->fOppPtTEnd, allocator)) { |
| return false; |
| } |
| } else if (this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd, |
| inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) { |
| if (!this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd, |
| inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE, |
| outer->fCoinPtTStart, outer->fCoinPtTEnd, |
| inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator)) { |
| return false; |
| } |
| } |
| } |
| |
| } while ((outer = outer->fNext)); |
| return true; |
| } |
| |
| bool SkOpCoincidence::contains(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, |
| SkOpPtT* oppPtTEnd, bool flipped) { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return false; |
| } |
| do { |
| if (coin->fCoinPtTStart == coinPtTStart && coin->fCoinPtTEnd == coinPtTEnd |
| && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd |
| && coin->fFlipped == flipped) { |
| return true; |
| } |
| } while ((coin = coin->fNext)); |
| return false; |
| } |
| |
| // walk span sets in parallel, moving winding from one to the other |
| bool SkOpCoincidence::apply() { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return true; |
| } |
| do { |
| SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); |
| if (start->deleted()) { |
| continue; |
| } |
| SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
| SkASSERT(start == start->starter(end)); |
| bool flipped = coin->fFlipped; |
| SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast(); |
| if (oStart->deleted()) { |
| continue; |
| } |
| SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span(); |
| SkASSERT(oStart == oStart->starter(oEnd)); |
| SkOpSegment* segment = start->segment(); |
| SkOpSegment* oSegment = oStart->segment(); |
| bool operandSwap = segment->operand() != oSegment->operand(); |
| if (flipped) { |
| do { |
| SkOpSpanBase* oNext = oStart->next(); |
| if (oNext == oEnd) { |
| break; |
| } |
| oStart = oNext->upCast(); |
| } while (true); |
| } |
| do { |
| int windValue = start->windValue(); |
| int oppValue = start->oppValue(); |
| int oWindValue = oStart->windValue(); |
| int oOppValue = oStart->oppValue(); |
| // winding values are added or subtracted depending on direction and wind type |
| // same or opposite values are summed depending on the operand value |
| int windDiff = operandSwap ? oOppValue : oWindValue; |
| int oWindDiff = operandSwap ? oppValue : windValue; |
| if (!flipped) { |
| windDiff = -windDiff; |
| oWindDiff = -oWindDiff; |
| } |
| if (windValue && (windValue > windDiff || (windValue == windDiff |
| && oWindValue <= oWindDiff))) { |
| if (operandSwap) { |
| SkTSwap(oWindValue, oOppValue); |
| } |
| if (flipped) { |
| windValue -= oWindValue; |
| oppValue -= oOppValue; |
| } else { |
| windValue += oWindValue; |
| oppValue += oOppValue; |
| } |
| if (segment->isXor()) { |
| windValue &= 1; |
| } |
| if (segment->oppXor()) { |
| oppValue &= 1; |
| } |
| oWindValue = oOppValue = 0; |
| } else { |
| if (operandSwap) { |
| SkTSwap(windValue, oppValue); |
| } |
| if (flipped) { |
| oWindValue -= windValue; |
| oOppValue -= oppValue; |
| } else { |
| oWindValue += windValue; |
| oOppValue += oppValue; |
| } |
| if (oSegment->isXor()) { |
| oWindValue &= 1; |
| } |
| if (oSegment->oppXor()) { |
| oOppValue &= 1; |
| } |
| windValue = oppValue = 0; |
| } |
| start->setWindValue(windValue); |
| start->setOppValue(oppValue); |
| oStart->setWindValue(oWindValue); |
| oStart->setOppValue(oOppValue); |
| if (!windValue && !oppValue) { |
| segment->markDone(start); |
| } |
| if (!oWindValue && !oOppValue) { |
| oSegment->markDone(oStart); |
| } |
| SkOpSpanBase* next = start->next(); |
| SkOpSpanBase* oNext = flipped ? oStart->prev() : oStart->next(); |
| if (next == end) { |
| break; |
| } |
| start = next->upCast(); |
| // if the opposite ran out too soon, just reuse the last span |
| if (!oNext || !oNext->upCastable()) { |
| oNext = oStart; |
| } |
| oStart = oNext->upCast(); |
| } while (true); |
| } while ((coin = coin->fNext)); |
| return true; |
| } |
| |
| void SkOpCoincidence::detach(SkCoincidentSpans* remove) { |
| SkCoincidentSpans* coin = fHead; |
| SkCoincidentSpans* prev = NULL; |
| SkCoincidentSpans* next; |
| do { |
| next = coin->fNext; |
| if (coin == remove) { |
| if (prev) { |
| prev->fNext = next; |
| } else { |
| fHead = next; |
| } |
| break; |
| } |
| prev = coin; |
| } while ((coin = next)); |
| SkASSERT(coin); |
| } |
| |
| void SkOpCoincidence::expand() { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return; |
| } |
| do { |
| SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); |
| SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
| SkOpSegment* segment = coin->fCoinPtTStart->segment(); |
| SkOpSegment* oppSegment = coin->fOppPtTStart->segment(); |
| SkOpSpan* prev = start->prev(); |
| SkOpPtT* oppPtT; |
| if (prev && (oppPtT = prev->contains(oppSegment))) { |
| double midT = (prev->t() + start->t()) / 2; |
| if (segment->isClose(midT, oppSegment)) { |
| coin->fCoinPtTStart = prev->ptT(); |
| coin->fOppPtTStart = oppPtT; |
| } |
| } |
| SkOpSpanBase* next = end->final() ? NULL : end->upCast()->next(); |
| if (next && (oppPtT = next->contains(oppSegment))) { |
| double midT = (end->t() + next->t()) / 2; |
| if (segment->isClose(midT, oppSegment)) { |
| coin->fCoinPtTEnd = next->ptT(); |
| coin->fOppPtTEnd = oppPtT; |
| } |
| } |
| } while ((coin = coin->fNext)); |
| } |
| |
| void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return; |
| } |
| do { |
| if (coin->fCoinPtTStart == deleted) { |
| if (coin->fCoinPtTEnd->span() == kept->span()) { |
| return this->detach(coin); |
| } |
| coin->fCoinPtTStart = kept; |
| } |
| if (coin->fCoinPtTEnd == deleted) { |
| if (coin->fCoinPtTStart->span() == kept->span()) { |
| return this->detach(coin); |
| } |
| coin->fCoinPtTEnd = kept; |
| } |
| if (coin->fOppPtTStart == deleted) { |
| if (coin->fOppPtTEnd->span() == kept->span()) { |
| return this->detach(coin); |
| } |
| coin->fOppPtTStart = kept; |
| } |
| if (coin->fOppPtTEnd == deleted) { |
| if (coin->fOppPtTStart->span() == kept->span()) { |
| return this->detach(coin); |
| } |
| coin->fOppPtTEnd = kept; |
| } |
| } while ((coin = coin->fNext)); |
| } |
| |
| void SkOpCoincidence::mark() { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return; |
| } |
| do { |
| SkOpSpanBase* end = coin->fCoinPtTEnd->span(); |
| SkOpSpanBase* oldEnd = end; |
| SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end); |
| SkOpSpanBase* oEnd = coin->fOppPtTEnd->span(); |
| SkOpSpanBase* oOldEnd = oEnd; |
| SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd); |
| bool flipped = (end == oldEnd) != (oEnd == oOldEnd); |
| if (flipped) { |
| SkTSwap(oStart, oEnd); |
| } |
| SkOpSpanBase* next = start; |
| SkOpSpanBase* oNext = oStart; |
| // check to see if coincident span could be bigger |
| |
| do { |
| next = next->upCast()->next(); |
| oNext = flipped ? oNext->prev() : oNext->upCast()->next(); |
| if (next == end || oNext == oEnd) { |
| break; |
| } |
| if (!next->containsCoinEnd(oNext)) { |
| next->insertCoinEnd(oNext); |
| } |
| SkOpSpan* nextSpan = next->upCast(); |
| SkOpSpan* oNextSpan = oNext->upCast(); |
| if (!nextSpan->containsCoincidence(oNextSpan)) { |
| nextSpan->insertCoincidence(oNextSpan); |
| } |
| } while (true); |
| } while ((coin = coin->fNext)); |
| } |
| |
| bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, |
| const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { |
| if (coin1s->segment() != coin2s->segment()) { |
| return false; |
| } |
| *overS = SkTMax(SkTMin(coin1s->fT, coin1e->fT), SkTMin(coin2s->fT, coin2e->fT)); |
| *overE = SkTMin(SkTMax(coin1s->fT, coin1e->fT), SkTMax(coin2s->fT, coin2e->fT)); |
| return *overS < *overE; |
| } |
