diff options
Diffstat (limited to 'src/pathops/SkOpCoincidence.cpp')
-rwxr-xr-x | src/pathops/SkOpCoincidence.cpp | 388 |
1 files changed, 388 insertions, 0 deletions
diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp new file mode 100755 index 0000000000..45eee0a38e --- /dev/null +++ b/src/pathops/SkOpCoincidence.cpp @@ -0,0 +1,388 @@ +/* + * 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" + +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 tRange(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; + tRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe); + tRange(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 (!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 (!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 (!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 (!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 { + SkOpSpanBase* end = coin->fCoinPtTEnd->span(); + SkOpSpan* start = coin->fCoinPtTStart->span()->upCast(); + SkASSERT(start == start->starter(end)); + bool flipped = coin->fFlipped; + SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span(); + SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast(); + 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); + } + bool isXor = segment->isXor(); + bool oppXor = oSegment->isXor(); + do { + int windValue = start->windValue(); + int oWindValue = oStart->windValue(); + int oppValue = start->oppValue(); + 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 + if (windValue >= oWindValue) { + if (operandSwap) { + SkTSwap(oWindValue, oOppValue); + } + if (flipped) { + windValue -= oWindValue; + oppValue -= oOppValue; + } else { + windValue += oWindValue; + oppValue += oOppValue; + } + if (isXor) { + windValue &= 1; + } + if (oppXor) { + oppValue &= 1; + } + oWindValue = oOppValue = 0; + } else { + if (operandSwap) { + SkTSwap(windValue, oppValue); + } + if (flipped) { + oWindValue -= windValue; + oOppValue -= oppValue; + } else { + oWindValue += windValue; + oOppValue += oppValue; + } + if (isXor) { + oOppValue &= 1; + } + if (oppXor) { + oWindValue &= 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 (!oNext) { + return false; + } + if (!oNext->upCastable()) { + return false; + } + 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; +} |