| /* |
| * 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" |
| |
| // returns true if coincident span's start and end are the same |
| bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const { |
| return (fCoinPtTStart == test && fCoinPtTEnd->contains(test)) |
| || (fCoinPtTEnd == test && fCoinPtTStart->contains(test)) |
| || (fOppPtTStart == test && fOppPtTEnd->contains(test)) |
| || (fOppPtTEnd == test && fOppPtTStart->contains(test)); |
| } |
| |
| // sets the span's end to the ptT referenced by the previous-next |
| void SkCoincidentSpans::correctOneEnd( |
| const SkOpPtT* (SkCoincidentSpans::* getEnd)() const, |
| void (SkCoincidentSpans::*setEnd)(const SkOpPtT* ptT) ) { |
| const SkOpPtT* origPtT = (this->*getEnd)(); |
| const SkOpSpanBase* origSpan = origPtT->span(); |
| const SkOpSpan* prev = origSpan->prev(); |
| const SkOpPtT* testPtT = prev ? prev->next()->ptT() |
| : origSpan->upCast()->next()->prev()->ptT(); |
| if (origPtT != testPtT) { |
| (this->*setEnd)(testPtT); |
| } |
| } |
| |
| // FIXME: member pointers have fallen out of favor and can be replaced with |
| // an alternative approach. |
| // makes all span ends agree with the segment's spans that define them |
| void SkCoincidentSpans::correctEnds() { |
| this->correctOneEnd(&SkCoincidentSpans::coinPtTStart, &SkCoincidentSpans::setCoinPtTStart); |
| this->correctOneEnd(&SkCoincidentSpans::coinPtTEnd, &SkCoincidentSpans::setCoinPtTEnd); |
| this->correctOneEnd(&SkCoincidentSpans::oppPtTStart, &SkCoincidentSpans::setOppPtTStart); |
| this->correctOneEnd(&SkCoincidentSpans::oppPtTEnd, &SkCoincidentSpans::setOppPtTEnd); |
| } |
| |
| /* Please keep this in sync with debugExpand */ |
| // expand the range by checking adjacent spans for coincidence |
| bool SkCoincidentSpans::expand() { |
| bool expanded = false; |
| const SkOpSegment* segment = coinPtTStart()->segment(); |
| const SkOpSegment* oppSegment = oppPtTStart()->segment(); |
| do { |
| const SkOpSpan* start = coinPtTStart()->span()->upCast(); |
| const SkOpSpan* prev = start->prev(); |
| const SkOpPtT* oppPtT; |
| if (!prev || !(oppPtT = prev->contains(oppSegment))) { |
| break; |
| } |
| double midT = (prev->t() + start->t()) / 2; |
| if (!segment->isClose(midT, oppSegment)) { |
| break; |
| } |
| setStarts(prev->ptT(), oppPtT); |
| expanded = true; |
| } while (true); |
| do { |
| const SkOpSpanBase* end = coinPtTEnd()->span(); |
| SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next(); |
| if (next && next->deleted()) { |
| break; |
| } |
| const SkOpPtT* oppPtT; |
| if (!next || !(oppPtT = next->contains(oppSegment))) { |
| break; |
| } |
| double midT = (end->t() + next->t()) / 2; |
| if (!segment->isClose(midT, oppSegment)) { |
| break; |
| } |
| setEnds(next->ptT(), oppPtT); |
| expanded = true; |
| } while (true); |
| return expanded; |
| } |
| |
| // increase the range of this span |
| bool SkCoincidentSpans::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
| const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { |
| bool result = false; |
| if (fCoinPtTStart->fT > coinPtTStart->fT || (this->flipped() |
| ? fOppPtTStart->fT < oppPtTStart->fT : fOppPtTStart->fT > oppPtTStart->fT)) { |
| this->setStarts(coinPtTStart, oppPtTStart); |
| result = true; |
| } |
| if (fCoinPtTEnd->fT < coinPtTEnd->fT || (this->flipped() |
| ? fOppPtTEnd->fT > oppPtTEnd->fT : fOppPtTEnd->fT < oppPtTEnd->fT)) { |
| this->setEnds(coinPtTEnd, oppPtTEnd); |
| result = true; |
| } |
| return result; |
| } |
| |
| // set the range of this span |
| void SkCoincidentSpans::set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, |
| const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd |
| SkDEBUGPARAMS(int id)) { |
| SkASSERT(SkOpCoincidence::Ordered(coinPtTStart, oppPtTStart)); |
| fNext = next; |
| this->setStarts(coinPtTStart, oppPtTStart); |
| this->setEnds(coinPtTEnd, oppPtTEnd); |
| SkDEBUGCODE(fID = id); |
| } |
| |
| // returns true if both points are inside this |
| bool SkCoincidentSpans::contains(const SkOpPtT* s, const SkOpPtT* e) const { |
| if (s->fT > e->fT) { |
| SkTSwap(s, e); |
| } |
| if (s->segment() == fCoinPtTStart->segment()) { |
| return fCoinPtTStart->fT <= s->fT && e->fT <= fCoinPtTEnd->fT; |
| } else { |
| SkASSERT(s->segment() == fOppPtTStart->segment()); |
| double oppTs = fOppPtTStart->fT; |
| double oppTe = fOppPtTEnd->fT; |
| if (oppTs > oppTe) { |
| SkTSwap(oppTs, oppTe); |
| } |
| return oppTs <= s->fT && e->fT <= oppTe; |
| } |
| } |
| |
| // returns the number of segment span's contained by this, or -1 if inconsistent |
| int SkCoincidentSpans::spanCount() const { |
| // most commonly, concidence are one span long; check for that first |
| const SkOpSpanBase* start = coinPtTStart()->span(); |
| const SkOpSpanBase* end = coinPtTEnd()->span(); |
| int coinIntervals = 0; |
| while (start != end) { |
| coinIntervals++; |
| start = start->upCast()->next(); |
| } |
| const SkOpSpanBase* oppStart = (flipped() ? oppPtTEnd() : oppPtTStart())->span(); |
| const SkOpSpanBase* oppEnd = (flipped() ? oppPtTStart() : oppPtTEnd())->span(); |
| int oppIntervals = 0; |
| while (oppStart != oppEnd) { |
| oppIntervals++; |
| oppStart = oppStart->upCast()->next(); |
| } |
| return coinIntervals == oppIntervals ? coinIntervals : -1; |
| } |
| |
| // A coincident span is unordered if the pairs of points in the main and opposite curves' |
| // t values do not ascend or descend. For instance, if a tightly arced quadratic is |
| // coincident with another curve, it may intersect it out of order. |
| bool SkCoincidentSpans::ordered() const { |
| const SkOpSpanBase* start = this->coinPtTStart()->span(); |
| const SkOpSpanBase* end = this->coinPtTEnd()->span(); |
| const SkOpSpanBase* next = start->upCast()->next(); |
| if (next == end) { |
| return true; |
| } |
| bool flipped = this->flipped(); |
| const SkOpSegment* oppSeg = this->oppPtTStart()->segment(); |
| double oppLastT = fOppPtTStart->fT; |
| do { |
| const SkOpPtT* opp = next->contains(oppSeg); |
| if (!opp) { |
| SkASSERT(0); // may assert if coincident span isn't fully processed |
| continue; |
| } |
| if ((oppLastT > opp->fT) != flipped) { |
| return false; |
| } |
| oppLastT = opp->fT; |
| if (next == end) { |
| break; |
| } |
| if (!next->upCastable()) { |
| return false; |
| } |
| next = next->upCast()->next(); |
| } while (true); |
| return true; |
| } |
| |
| // returns true if the point is on a coincident edge, and if it is the start of that edge |
| bool SkOpCoincidence::edge(const SkOpPtT* test, bool* start) const { |
| SkCoincidentSpans* coinRec = fHead; |
| if (!coinRec) { |
| return false; |
| } |
| do { |
| if (coinRec->coinPtTStart() == test) { |
| *start = true; |
| return true; |
| } |
| if (coinRec->coinPtTEnd() == test) { |
| *start = false; |
| return true; |
| } |
| if (coinRec->oppPtTStart() == test) { |
| *start = !coinRec->flipped(); |
| return true; |
| } |
| if (coinRec->coinPtTEnd() == test) { |
| *start = coinRec->flipped(); |
| return true; |
| } |
| } while ((coinRec = coinRec->next())); |
| return false; |
| } |
| |
| // if there is an existing pair that overlaps the addition, extend it |
| bool SkOpCoincidence::extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
| const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { |
| SkCoincidentSpans* test = fHead; |
| if (!test) { |
| return false; |
| } |
| const SkOpSegment* coinSeg = coinPtTStart->segment(); |
| const SkOpSegment* oppSeg = oppPtTStart->segment(); |
| if (!Ordered(coinPtTStart, oppPtTStart)) { |
| SkTSwap(coinSeg, oppSeg); |
| SkTSwap(coinPtTStart, oppPtTStart); |
| SkTSwap(coinPtTEnd, oppPtTEnd); |
| if (coinPtTStart->fT > coinPtTEnd->fT) { |
| SkTSwap(coinPtTStart, coinPtTEnd); |
| SkTSwap(oppPtTStart, oppPtTEnd); |
| } |
| } |
| double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); |
| SkDEBUGCODE(double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT)); |
| do { |
| if (coinSeg != test->coinPtTStart()->segment()) { |
| continue; |
| } |
| if (oppSeg != test->oppPtTStart()->segment()) { |
| continue; |
| } |
| double oTestMinT = SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); |
| double oTestMaxT = SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT); |
| // if debug check triggers, caller failed to check if extended already exists |
| SkASSERT(test->coinPtTStart()->fT > coinPtTStart->fT |
| || coinPtTEnd->fT > test->coinPtTEnd()->fT |
| || oTestMinT > oppMinT || oppMaxT > oTestMaxT); |
| if ((test->coinPtTStart()->fT <= coinPtTEnd->fT |
| && coinPtTStart->fT <= test->coinPtTEnd()->fT) |
| || (oTestMinT <= oTestMaxT && oppMinT <= oTestMaxT)) { |
| test->extend(coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); |
| return true; |
| } |
| } while ((test = test->next())); |
| return false; |
| } |
| |
| // verifies that the coincidence hasn't already been added |
| static void DebugCheckAdd(const SkCoincidentSpans* check, const SkOpPtT* coinPtTStart, |
| const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) { |
| #if DEBUG_COINCIDENCE |
| while (check) { |
| SkASSERT(check->coinPtTStart() != coinPtTStart || check->coinPtTEnd() != coinPtTEnd |
| || check->oppPtTStart() != oppPtTStart || check->oppPtTEnd() != oppPtTEnd); |
| SkASSERT(check->coinPtTStart() != oppPtTStart || check->coinPtTEnd() != oppPtTEnd |
| || check->oppPtTStart() != coinPtTStart || check->oppPtTEnd() != coinPtTEnd); |
| check = check->next(); |
| } |
| #endif |
| } |
| |
| // adds a new coincident pair |
| void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart, |
| SkOpPtT* oppPtTEnd) { |
| // OPTIMIZE: caller should have already sorted |
| if (!Ordered(coinPtTStart, oppPtTStart)) { |
| if (oppPtTStart->fT < oppPtTEnd->fT) { |
| this->add(oppPtTStart, oppPtTEnd, coinPtTStart, coinPtTEnd); |
| } else { |
| this->add(oppPtTEnd, oppPtTStart, coinPtTEnd, coinPtTStart); |
| } |
| return; |
| } |
| SkASSERT(Ordered(coinPtTStart, oppPtTStart)); |
| // choose the ptT at the front of the list to track |
| coinPtTStart = coinPtTStart->span()->ptT(); |
| coinPtTEnd = coinPtTEnd->span()->ptT(); |
| oppPtTStart = oppPtTStart->span()->ptT(); |
| oppPtTEnd = oppPtTEnd->span()->ptT(); |
| SkASSERT(coinPtTStart->fT < coinPtTEnd->fT); |
| SkASSERT(oppPtTStart->fT != oppPtTEnd->fT); |
| SkOPASSERT(!coinPtTStart->deleted()); |
| SkOPASSERT(!coinPtTEnd->deleted()); |
| SkOPASSERT(!oppPtTStart->deleted()); |
| SkOPASSERT(!oppPtTEnd->deleted()); |
| DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); |
| DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd); |
| SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate( |
| this->globalState()->allocator()); |
| coinRec->init(SkDEBUGCODE(fGlobalState)); |
| coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd |
| SkDEBUGPARAMS(fGlobalState->nextCoinID())); |
| fHead = coinRec; |
| } |
| |
| // description below |
| bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan) { |
| const SkOpPtT* testPtT = testSpan->ptT(); |
| const SkOpPtT* stopPtT = testPtT; |
| const SkOpSegment* baseSeg = base->segment(); |
| while ((testPtT = testPtT->next()) != stopPtT) { |
| const SkOpSegment* testSeg = testPtT->segment(); |
| if (testPtT->deleted()) { |
| continue; |
| } |
| if (testSeg == baseSeg) { |
| continue; |
| } |
| if (testPtT->span()->ptT() != testPtT) { |
| continue; |
| } |
| if (this->contains(baseSeg, testSeg, testPtT->fT)) { |
| continue; |
| } |
| // intersect perp with base->ptT() with testPtT->segment() |
| SkDVector dxdy = baseSeg->dSlopeAtT(base->t()); |
| const SkPoint& pt = base->pt(); |
| SkDLine ray = {{{pt.fX, pt.fY}, {pt.fX + dxdy.fY, pt.fY - dxdy.fX}}}; |
| SkIntersections i; |
| (*CurveIntersectRay[testSeg->verb()])(testSeg->pts(), testSeg->weight(), ray, &i); |
| for (int index = 0; index < i.used(); ++index) { |
| double t = i[0][index]; |
| if (!between(0, t, 1)) { |
| continue; |
| } |
| SkDPoint oppPt = i.pt(index); |
| if (!oppPt.approximatelyEqual(pt)) { |
| continue; |
| } |
| SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg); |
| SkOpPtT* oppStart = writableSeg->addT(t); |
| SkOpSpan* writableBase = const_cast<SkOpSpan*>(base); |
| oppStart->span()->addOpp(writableBase); |
| if (oppStart->deleted()) { |
| continue; |
| } |
| SkOpSegment* coinSeg = base->segment(); |
| SkOpSegment* oppSeg = oppStart->segment(); |
| double coinTs, coinTe, oppTs, oppTe; |
| if (Ordered(coinSeg, oppSeg)) { |
| coinTs = base->t(); |
| coinTe = testSpan->t(); |
| oppTs = oppStart->fT; |
| oppTe = testPtT->fT; |
| } else { |
| SkTSwap(coinSeg, oppSeg); |
| coinTs = oppStart->fT; |
| coinTe = testPtT->fT; |
| oppTs = base->t(); |
| oppTe = testSpan->t(); |
| } |
| if (coinTs > coinTe) { |
| SkTSwap(coinTs, coinTe); |
| SkTSwap(oppTs, oppTe); |
| } |
| bool added; |
| if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) { |
| return false; |
| } |
| } |
| } |
| return true; |
| } |
| |
| // description below |
| bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) { |
| FAIL_IF(!ptT->span()->upCastable()); |
| const SkOpSpan* base = ptT->span()->upCast(); |
| const SkOpSpan* prev = base->prev(); |
| FAIL_IF(!prev); |
| if (!prev->isCanceled()) { |
| if (!this->addEndMovedSpans(base, base->prev())) { |
| return false; |
| } |
| } |
| if (!base->isCanceled()) { |
| if (!this->addEndMovedSpans(base, base->next())) { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| /* If A is coincident with B and B includes an endpoint, and A's matching point |
| is not the endpoint (i.e., there's an implied line connecting B-end and A) |
| then assume that the same implied line may intersect another curve close to B. |
| Since we only care about coincidence that was undetected, look at the |
| ptT list on B-segment adjacent to the B-end/A ptT loop (not in the loop, but |
| next door) and see if the A matching point is close enough to form another |
| coincident pair. If so, check for a new coincident span between B-end/A ptT loop |
| and the adjacent ptT loop. |
| */ |
| bool SkOpCoincidence::addEndMovedSpans() { |
| SkCoincidentSpans* span = fHead; |
| if (!span) { |
| return true; |
| } |
| fTop = span; |
| fHead = nullptr; |
| do { |
| if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) { |
| FAIL_IF(1 == span->coinPtTStart()->fT); |
| bool onEnd = span->coinPtTStart()->fT == 0; |
| bool oOnEnd = zero_or_one(span->oppPtTStart()->fT); |
| if (onEnd) { |
| if (!oOnEnd) { // if both are on end, any nearby intersect was already found |
| if (!this->addEndMovedSpans(span->oppPtTStart())) { |
| return false; |
| } |
| } |
| } else if (oOnEnd) { |
| if (!this->addEndMovedSpans(span->coinPtTStart())) { |
| return false; |
| } |
| } |
| } |
| if (span->coinPtTEnd()->fPt != span->oppPtTEnd()->fPt) { |
| bool onEnd = span->coinPtTEnd()->fT == 1; |
| bool oOnEnd = zero_or_one(span->oppPtTEnd()->fT); |
| if (onEnd) { |
| if (!oOnEnd) { |
| if (!this->addEndMovedSpans(span->oppPtTEnd())) { |
| return false; |
| } |
| } |
| } else if (oOnEnd) { |
| if (!this->addEndMovedSpans(span->coinPtTEnd())) { |
| return false; |
| } |
| } |
| } |
| } while ((span = span->next())); |
| this->restoreHead(); |
| return true; |
| } |
| |
| /* Please keep this in sync with debugAddExpanded */ |
| // for each coincident pair, match the spans |
| // if the spans don't match, add the missing pt to the segment and loop it in the opposite span |
| bool SkOpCoincidence::addExpanded() { |
| SkCoincidentSpans* coin = this->fHead; |
| if (!coin) { |
| return true; |
| } |
| do { |
| const SkOpPtT* startPtT = coin->coinPtTStart(); |
| const SkOpPtT* oStartPtT = coin->oppPtTStart(); |
| double priorT = startPtT->fT; |
| double oPriorT = oStartPtT->fT; |
| FAIL_IF(!startPtT->contains(oStartPtT)); |
| SkOPASSERT(coin->coinPtTEnd()->contains(coin->oppPtTEnd())); |
| const SkOpSpanBase* start = startPtT->span(); |
| const SkOpSpanBase* oStart = oStartPtT->span(); |
| const SkOpSpanBase* end = coin->coinPtTEnd()->span(); |
| const SkOpSpanBase* oEnd = coin->oppPtTEnd()->span(); |
| FAIL_IF(oEnd->deleted()); |
| FAIL_IF(!start->upCastable()); |
| const SkOpSpanBase* test = start->upCast()->next(); |
| FAIL_IF(!coin->flipped() && !oStart->upCastable()); |
| const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next(); |
| FAIL_IF(!oTest); |
| SkOpSegment* seg = start->segment(); |
| SkOpSegment* oSeg = oStart->segment(); |
| while (test != end || oTest != oEnd) { |
| const SkOpPtT* containedOpp = test->ptT()->contains(oSeg); |
| const SkOpPtT* containedThis = oTest->ptT()->contains(seg); |
| if (!containedOpp || !containedThis) { |
| // choose the ends, or the first common pt-t list shared by both |
| double nextT, oNextT; |
| if (containedOpp) { |
| nextT = test->t(); |
| oNextT = containedOpp->fT; |
| } else if (containedThis) { |
| nextT = containedThis->fT; |
| oNextT = oTest->t(); |
| } else { |
| // iterate through until a pt-t list found that contains the other |
| const SkOpSpanBase* walk = test; |
| const SkOpPtT* walkOpp; |
| do { |
| FAIL_IF(!walk->upCastable()); |
| walk = walk->upCast()->next(); |
| } while (!(walkOpp = walk->ptT()->contains(oSeg)) |
| && walk != coin->coinPtTEnd()->span()); |
| nextT = walk->t(); |
| oNextT = walkOpp->fT; |
| } |
| // use t ranges to guess which one is missing |
| double startRange = nextT - priorT; |
| FAIL_IF(!startRange); |
| double startPart = (test->t() - priorT) / startRange; |
| double oStartRange = oNextT - oPriorT; |
| FAIL_IF(!oStartRange); |
| double oStartPart = (oTest->t() - oPriorT) / oStartRange; |
| FAIL_IF(startPart == oStartPart); |
| bool addToOpp = !containedOpp && !containedThis ? startPart < oStartPart |
| : !!containedThis; |
| bool startOver = false; |
| bool success = addToOpp ? oSeg->addExpanded( |
| oPriorT + oStartRange * startPart, test, &startOver) |
| : seg->addExpanded( |
| priorT + startRange * oStartPart, oTest, &startOver); |
| FAIL_IF(!success); |
| if (startOver) { |
| test = start; |
| oTest = oStart; |
| } |
| end = coin->coinPtTEnd()->span(); |
| oEnd = coin->oppPtTEnd()->span(); |
| } |
| if (test != end) { |
| FAIL_IF(!test->upCastable()); |
| priorT = test->t(); |
| test = test->upCast()->next(); |
| } |
| if (oTest != oEnd) { |
| oPriorT = oTest->t(); |
| oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next(); |
| FAIL_IF(!oTest); |
| } |
| |
| } |
| } while ((coin = coin->next())); |
| return true; |
| } |
| |
| // checks to see if coincidence has already been found |
| bool SkOpCoincidence::alreadyAdded(const SkCoincidentSpans* check, const SkCoincidentSpans* outer, |
| const SkOpPtT* over1s, const SkOpPtT* over1e) const { |
| do { |
| if (check->oppPtTStart() == outer->coinPtTStart() && check->coinPtTStart() == over1s |
| && check->oppPtTEnd() == outer->coinPtTEnd() && check->coinPtTEnd() == over1e) { |
| return true; |
| } |
| if (check->coinPtTStart() == outer->coinPtTStart() && check->oppPtTStart() == over1s |
| && check->coinPtTEnd() == outer->coinPtTEnd() && check->oppPtTEnd() == over1e) { |
| return true; |
| } |
| if (check->startEquals(outer->oppPtTStart()->span(), over1s->span())) { |
| SkDEBUGCODE(check->debugStartCheck(outer->oppPtTEnd()->span(), over1e->span(), |
| fGlobalState)); |
| return true; |
| } |
| if (check->startEquals(over1s->span(), outer->coinPtTStart()->span())) { |
| SkDEBUGCODE(check->debugStartCheck(over1e->span(), outer->oppPtTEnd()->span(), |
| fGlobalState)); |
| return true; |
| } |
| } while ((check = check->next())); |
| return false; |
| } |
| |
| /* Please keep this in sync with debugAddIfMissing() */ |
| bool SkOpCoincidence::addIfMissing(const SkCoincidentSpans* outer, SkOpPtT* over1s, |
| SkOpPtT* over1e) { |
| SkASSERT(fTop); |
| if (this->alreadyAdded(fTop, outer, over1s, over1e)) { |
| return false; |
| } |
| if (fHead && this->alreadyAdded(fHead, outer, over1s, over1e)) { |
| return false; |
| } |
| this->add(outer->coinPtTStart(), outer->coinPtTEnd(), over1s, over1e); |
| this->debugValidate(); |
| return true; |
| } |
| |
| // given a t span, map the same range on the coincident span |
| /* |
| the curves may not scale linearly, so interpolation may only happen within known points |
| remap over1s, over1e, cointPtTStart, coinPtTEnd to smallest range that captures over1s |
| then repeat to capture over1e |
| */ |
| double SkOpCoincidence::TRange(const SkOpPtT* overS, double t, |
| const SkOpSegment* coinSeg SkDEBUGPARAMS(const SkOpPtT* overE)) { |
| const SkOpSpanBase* work = overS->span(); |
| const SkOpPtT* foundStart = nullptr; |
| const SkOpPtT* foundEnd = nullptr; |
| const SkOpPtT* coinStart = nullptr; |
| const SkOpPtT* coinEnd = nullptr; |
| do { |
| const SkOpPtT* contained = work->contains(coinSeg); |
| if (!contained) { |
| if (work->final()) { |
| break; |
| } |
| continue; |
| } |
| if (work->t() <= t) { |
| coinStart = contained; |
| foundStart = work->ptT(); |
| } |
| if (work->t() >= t) { |
| coinEnd = contained; |
| foundEnd = work->ptT(); |
| break; |
| } |
| SkASSERT(work->ptT() != overE); |
| } while ((work = work->upCast()->next())); |
| if (!coinStart || !coinEnd) { |
| return 1; |
| } |
| // while overS->fT <=t and overS contains coinSeg |
| double denom = foundEnd->fT - foundStart->fT; |
| double sRatio = denom ? (t - foundStart->fT) / denom : 1; |
| return coinStart->fT + (coinEnd->fT - coinStart->fT) * sRatio; |
| } |
| |
| // return true if span overlaps existing and needs to adjust the coincident list |
| bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check, |
| const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, |
| double coinTs, double coinTe, double oppTs, double oppTe, |
| SkTDArray<SkCoincidentSpans*>* overlaps) const { |
| if (!Ordered(coinSeg, oppSeg)) { |
| if (oppTs < oppTe) { |
| return this->checkOverlap(check, oppSeg, coinSeg, oppTs, oppTe, coinTs, coinTe, |
| overlaps); |
| } |
| return this->checkOverlap(check, oppSeg, coinSeg, oppTe, oppTs, coinTe, coinTs, overlaps); |
| } |
| bool swapOpp = oppTs > oppTe; |
| if (swapOpp) { |
| SkTSwap(oppTs, oppTe); |
| } |
| do { |
| if (check->coinPtTStart()->segment() != coinSeg) { |
| continue; |
| } |
| if (check->oppPtTStart()->segment() != oppSeg) { |
| continue; |
| } |
| double checkTs = check->coinPtTStart()->fT; |
| double checkTe = check->coinPtTEnd()->fT; |
| bool coinOutside = coinTe < checkTs || coinTs > checkTe; |
| double oCheckTs = check->oppPtTStart()->fT; |
| double oCheckTe = check->oppPtTEnd()->fT; |
| if (swapOpp) { |
| if (oCheckTs <= oCheckTe) { |
| return false; |
| } |
| SkTSwap(oCheckTs, oCheckTe); |
| } |
| bool oppOutside = oppTe < oCheckTs || oppTs > oCheckTe; |
| if (coinOutside && oppOutside) { |
| continue; |
| } |
| bool coinInside = coinTe <= checkTe && coinTs >= checkTs; |
| bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs; |
| if (coinInside && oppInside) { // already included, do nothing |
| return false; |
| } |
| *overlaps->append() = check; // partial overlap, extend existing entry |
| } while ((check = check->next())); |
| return true; |
| } |
| |
| /* Please keep this in sync with debugAddIfMissing() */ |
| // note that over1s, over1e, over2s, over2e are ordered |
| bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s, |
| double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added |
| SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) { |
| SkASSERT(tStart < tEnd); |
| SkASSERT(over1s->fT < over1e->fT); |
| SkASSERT(between(over1s->fT, tStart, over1e->fT)); |
| SkASSERT(between(over1s->fT, tEnd, over1e->fT)); |
| SkASSERT(over2s->fT < over2e->fT); |
| SkASSERT(between(over2s->fT, tStart, over2e->fT)); |
| SkASSERT(between(over2s->fT, tEnd, over2e->fT)); |
| SkASSERT(over1s->segment() == over1e->segment()); |
| SkASSERT(over2s->segment() == over2e->segment()); |
| SkASSERT(over1s->segment() == over2s->segment()); |
| SkASSERT(over1s->segment() != coinSeg); |
| SkASSERT(over1s->segment() != oppSeg); |
| SkASSERT(coinSeg != oppSeg); |
| double coinTs, coinTe, oppTs, oppTe; |
| coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e)); |
| coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e)); |
| if (coinSeg->collapsed(coinTs, coinTe)) { |
| return true; |
| } |
| oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e)); |
| oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e)); |
| if (oppSeg->collapsed(oppTs, oppTe)) { |
| return true; |
| } |
| if (coinTs > coinTe) { |
| SkTSwap(coinTs, coinTe); |
| SkTSwap(oppTs, oppTe); |
| } |
| return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added); |
| } |
| |
| /* Please keep this in sync with debugAddOrOverlap() */ |
| // If this is called by addEndMovedSpans(), a returned false propogates out to an abort. |
| // If this is called by AddIfMissing(), a returned false indicates there was nothing to add |
| bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, |
| double coinTs, double coinTe, double oppTs, double oppTe, bool* added) { |
| SkTDArray<SkCoincidentSpans*> overlaps; |
| FAIL_IF(!fTop); |
| if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { |
| return true; |
| } |
| if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, |
| coinTe, oppTs, oppTe, &overlaps)) { |
| return true; |
| } |
| SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; |
| for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing |
| SkCoincidentSpans* test = overlaps[index]; |
| if (overlap->coinPtTStart()->fT > test->coinPtTStart()->fT) { |
| overlap->setCoinPtTStart(test->coinPtTStart()); |
| } |
| if (overlap->coinPtTEnd()->fT < test->coinPtTEnd()->fT) { |
| overlap->setCoinPtTEnd(test->coinPtTEnd()); |
| } |
| if (overlap->flipped() |
| ? overlap->oppPtTStart()->fT < test->oppPtTStart()->fT |
| : overlap->oppPtTStart()->fT > test->oppPtTStart()->fT) { |
| overlap->setOppPtTStart(test->oppPtTStart()); |
| } |
| if (overlap->flipped() |
| ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT |
| : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) { |
| overlap->setOppPtTEnd(test->oppPtTEnd()); |
| } |
| if (!fHead || !this->release(fHead, test)) { |
| SkAssertResult(this->release(fTop, test)); |
| } |
| } |
| const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg); |
| const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg); |
| if (overlap && cs && ce && overlap->contains(cs, ce)) { |
| return true; |
| } |
| FAIL_IF(cs == ce && cs); |
| const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); |
| const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); |
| if (overlap && os && oe && overlap->contains(os, oe)) { |
| return true; |
| } |
| SkASSERT(!cs || !cs->deleted()); |
| SkASSERT(!os || !os->deleted()); |
| SkASSERT(!ce || !ce->deleted()); |
| SkASSERT(!oe || !oe->deleted()); |
| const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr; |
| const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr; |
| FAIL_IF(csExisting && csExisting == ceExisting); |
| // FAIL_IF(csExisting && (csExisting == ce || |
| // csExisting->contains(ceExisting ? ceExisting : ce))); |
| FAIL_IF(ceExisting && (ceExisting == cs || |
| ceExisting->contains(csExisting ? csExisting : cs))); |
| const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr; |
| const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr; |
| FAIL_IF(osExisting && osExisting == oeExisting); |
| FAIL_IF(osExisting && (osExisting == oe || |
| osExisting->contains(oeExisting ? oeExisting : oe))); |
| FAIL_IF(oeExisting && (oeExisting == os || |
| oeExisting->contains(osExisting ? osExisting : os))); |
| // extra line in debug code |
| this->debugValidate(); |
| if (!cs || !os) { |
| SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs) |
| : coinSeg->addT(coinTs); |
| if (csWritable == ce) { |
| return true; |
| } |
| SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) |
| : oppSeg->addT(oppTs); |
| FAIL_IF(!csWritable || !osWritable); |
| csWritable->span()->addOpp(osWritable->span()); |
| cs = csWritable; |
| os = osWritable->active(); |
| FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted())); |
| } |
| if (!ce || !oe) { |
| SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce) |
| : coinSeg->addT(coinTe); |
| SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe) |
| : oppSeg->addT(oppTe); |
| ceWritable->span()->addOpp(oeWritable->span()); |
| ce = ceWritable; |
| oe = oeWritable; |
| } |
| this->debugValidate(); |
| FAIL_IF(cs->deleted()); |
| FAIL_IF(os->deleted()); |
| FAIL_IF(ce->deleted()); |
| FAIL_IF(oe->deleted()); |
| FAIL_IF(cs->contains(ce) || os->contains(oe)); |
| bool result = true; |
| if (overlap) { |
| if (overlap->coinPtTStart()->segment() == coinSeg) { |
| result = overlap->extend(cs, ce, os, oe); |
| } else { |
| if (os->fT > oe->fT) { |
| SkTSwap(cs, ce); |
| SkTSwap(os, oe); |
| } |
| result = overlap->extend(os, oe, cs, ce); |
| } |
| #if DEBUG_COINCIDENCE_VERBOSE |
| if (result) { |
| overlaps[0]->debugShow(); |
| } |
| #endif |
| } else { |
| this->add(cs, ce, os, oe); |
| #if DEBUG_COINCIDENCE_VERBOSE |
| fHead->debugShow(); |
| #endif |
| } |
| this->debugValidate(); |
| if (result) { |
| *added = true; |
| } |
| return true; |
| } |
| |
| // Please keep this in sync with debugAddMissing() |
| /* detects overlaps of different coincident runs on same segment */ |
| /* does not detect overlaps for pairs without any segments in common */ |
| // returns true if caller should loop again |
| bool SkOpCoincidence::addMissing(bool* added) { |
| SkCoincidentSpans* outer = fHead; |
| *added = false; |
| if (!outer) { |
| return true; |
| } |
| fTop = outer; |
| fHead = nullptr; |
| do { |
| // addifmissing can modify the list that this is walking |
| // save head so that walker can iterate over old data unperturbed |
| // addifmissing adds to head freely then add saved head in the end |
| const SkOpPtT* ocs = outer->coinPtTStart(); |
| SkASSERT(!ocs->deleted()); |
| const SkOpSegment* outerCoin = ocs->segment(); |
| SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list |
| const SkOpPtT* oos = outer->oppPtTStart(); |
| if (oos->deleted()) { |
| return true; |
| } |
| const SkOpSegment* outerOpp = oos->segment(); |
| SkASSERT(!outerOpp->done()); |
| SkOpSegment* outerCoinWritable = const_cast<SkOpSegment*>(outerCoin); |
| SkOpSegment* outerOppWritable = const_cast<SkOpSegment*>(outerOpp); |
| SkCoincidentSpans* inner = outer; |
| while ((inner = inner->next())) { |
| this->debugValidate(); |
| double overS, overE; |
| const SkOpPtT* ics = inner->coinPtTStart(); |
| SkASSERT(!ics->deleted()); |
| const SkOpSegment* innerCoin = ics->segment(); |
| SkASSERT(!innerCoin->done()); |
| const SkOpPtT* ios = inner->oppPtTStart(); |
| SkASSERT(!ios->deleted()); |
| const SkOpSegment* innerOpp = ios->segment(); |
| SkASSERT(!innerOpp->done()); |
| SkOpSegment* innerCoinWritable = const_cast<SkOpSegment*>(innerCoin); |
| SkOpSegment* innerOppWritable = const_cast<SkOpSegment*>(innerOpp); |
| if (outerCoin == innerCoin) { |
| const SkOpPtT* oce = outer->coinPtTEnd(); |
| if (oce->deleted()) { |
| return true; |
| } |
| const SkOpPtT* ice = inner->coinPtTEnd(); |
| SkASSERT(!ice->deleted()); |
| if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) { |
| (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice), |
| overS, overE, outerOppWritable, innerOppWritable, added |
| SkDEBUGPARAMS(ocs->debugEnder(oce)) |
| SkDEBUGPARAMS(ics->debugEnder(ice))); |
| } |
| } else if (outerCoin == innerOpp) { |
| const SkOpPtT* oce = outer->coinPtTEnd(); |
| SkASSERT(!oce->deleted()); |
| const SkOpPtT* ioe = inner->oppPtTEnd(); |
| SkASSERT(!ioe->deleted()); |
| if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) { |
| (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe), |
| overS, overE, outerOppWritable, innerCoinWritable, added |
| SkDEBUGPARAMS(ocs->debugEnder(oce)) |
| SkDEBUGPARAMS(ios->debugEnder(ioe))); |
| } |
| } else if (outerOpp == innerCoin) { |
| const SkOpPtT* ooe = outer->oppPtTEnd(); |
| SkASSERT(!ooe->deleted()); |
| const SkOpPtT* ice = inner->coinPtTEnd(); |
| SkASSERT(!ice->deleted()); |
| SkASSERT(outerCoin != innerOpp); |
| if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) { |
| (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice), |
| overS, overE, outerCoinWritable, innerOppWritable, added |
| SkDEBUGPARAMS(oos->debugEnder(ooe)) |
| SkDEBUGPARAMS(ics->debugEnder(ice))); |
| } |
| } else if (outerOpp == innerOpp) { |
| const SkOpPtT* ooe = outer->oppPtTEnd(); |
| SkASSERT(!ooe->deleted()); |
| const SkOpPtT* ioe = inner->oppPtTEnd(); |
| if (ioe->deleted()) { |
| return true; |
| } |
| SkASSERT(outerCoin != innerCoin); |
| if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) { |
| (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe), |
| overS, overE, outerCoinWritable, innerCoinWritable, added |
| SkDEBUGPARAMS(oos->debugEnder(ooe)) |
| SkDEBUGPARAMS(ios->debugEnder(ioe))); |
| } |
| } |
| this->debugValidate(); |
| } |
| } while ((outer = outer->next())); |
| this->restoreHead(); |
| return true; |
| } |
| |
| bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o, |
| const SkOpSegment* seg2, const SkOpSegment* seg2o, |
| const SkOpPtT* overS, const SkOpPtT* overE) { |
| const SkOpPtT* s1, * e1, * s2, * e2; |
| if (!(s1 = overS->find(seg1))) { |
| return true; |
| } |
| if (!(e1 = overE->find(seg1))) { |
| return true; |
| } |
| if (s1 == e1) { |
| return true; |
| } |
| if (approximately_equal_half(s1->fT, e1->fT)) { |
| return false; |
| } |
| if (!s1->starter(e1)->span()->upCast()->windValue()) { |
| if (!(s1 = overS->find(seg1o))) { |
| return true; |
| } |
| if (!(e1 = overE->find(seg1o))) { |
| return true; |
| } |
| if (s1 == e1) { |
| return true; |
| } |
| if (!s1->starter(e1)->span()->upCast()->windValue()) { |
| return true; |
| } |
| } |
| if (!(s2 = overS->find(seg2))) { |
| return true; |
| } |
| if (!(e2 = overE->find(seg2))) { |
| return true; |
| } |
| if (s2 == e2) { |
| return true; |
| } |
| if (approximately_equal_half(s2->fT, e2->fT)) { |
| return false; |
| } |
| if (!s2->starter(e2)->span()->upCast()->windValue()) { |
| if (!(s2 = overS->find(seg2o))) { |
| return true; |
| } |
| if (!(e2 = overE->find(seg2o))) { |
| return true; |
| } |
| if (s2 == e2) { |
| return true; |
| } |
| if (!s2->starter(e2)->span()->upCast()->windValue()) { |
| return true; |
| } |
| } |
| if (s1->segment() == s2->segment()) { |
| return true; |
| } |
| if (s1->fT > e1->fT) { |
| SkTSwap(s1, e1); |
| SkTSwap(s2, e2); |
| } |
| this->add(s1, e1, s2, e2); |
| return true; |
| } |
| |
| /* look for pairs of coincidence with no common segments |
| if there's no existing coincidence found that matches up the segments, and |
| if the pt-t list for one contains the other, create coincident pairs for what's left */ |
| bool SkOpCoincidence::addUncommon() { |
| SkCoincidentSpans* outer = fHead; |
| if (!outer) { |
| return false; |
| } |
| bool added = false; |
| fTop = outer; |
| fHead = nullptr; |
| do { |
| // addifmissing can modify the list that this is walking |
| // save head so that walker can iterate over old data unperturbed |
| // addifmissing adds to head freely then add saved head in the end |
| const SkOpSegment* outerCoin = outer->coinPtTStart()->segment(); |
| const SkOpSegment* outerOpp = outer->oppPtTStart()->segment(); |
| if (outerCoin->done() || outerOpp->done()) { |
| continue; |
| } |
| SkCoincidentSpans* inner = outer; |
| while ((inner = inner->next())) { |
| this->debugValidate(); |
| const SkOpSegment* innerCoin = inner->coinPtTStart()->segment(); |
| const SkOpSegment* innerOpp = inner->oppPtTStart()->segment(); |
| if (innerCoin->done() || innerOpp->done()) { |
| continue; |
| } |
| // check to see if outer span overlaps the inner span |
| // look for inner segment in pt-t list |
| // if present, and if t values are in coincident range |
| // add two pairs of new coincidence |
| const SkOpPtT* testS = outer->coinPtTStart()->contains(innerCoin); |
| const SkOpPtT* testE = outer->coinPtTEnd()->contains(innerCoin); |
| if (testS && testS->fT >= inner->coinPtTStart()->fT |
| && testE && testE->fT <= inner->coinPtTEnd()->fT |
| && this->testForCoincidence(outer, testS, testE)) { |
| added |= this->addIfMissing(outer, testS, testE); |
| } else { |
| testS = inner->coinPtTStart()->contains(outerCoin); |
| testE = inner->coinPtTEnd()->contains(outerCoin); |
| if (testS && testS->fT >= outer->coinPtTStart()->fT |
| && testE && testE->fT <= outer->coinPtTEnd()->fT |
| && this->testForCoincidence(inner, testS, testE)) { |
| added |= this->addIfMissing(inner, testS, testE); |
| } |
| } |
| } |
| } while ((outer = outer->next())); |
| this->restoreHead(); |
| return added; |
| } |
| |
| bool SkOpCoincidence::contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const { |
| if (this->contains(fHead, seg, opp, oppT)) { |
| return true; |
| } |
| if (this->contains(fTop, seg, opp, oppT)) { |
| return true; |
| } |
| return false; |
| } |
| |
| bool SkOpCoincidence::contains(const SkCoincidentSpans* coin, const SkOpSegment* seg, |
| const SkOpSegment* opp, double oppT) const { |
| if (!coin) { |
| return false; |
| } |
| do { |
| if (coin->coinPtTStart()->segment() == seg && coin->oppPtTStart()->segment() == opp |
| && between(coin->oppPtTStart()->fT, oppT, coin->oppPtTEnd()->fT)) { |
| return true; |
| } |
| if (coin->oppPtTStart()->segment() == seg && coin->coinPtTStart()->segment() == opp |
| && between(coin->coinPtTStart()->fT, oppT, coin->coinPtTEnd()->fT)) { |
| return true; |
| } |
| } while ((coin = coin->next())); |
| return false; |
| } |
| |
| bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, |
| const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const { |
| const SkCoincidentSpans* test = fHead; |
| if (!test) { |
| return false; |
| } |
| const SkOpSegment* coinSeg = coinPtTStart->segment(); |
| const SkOpSegment* oppSeg = oppPtTStart->segment(); |
| if (!Ordered(coinPtTStart, oppPtTStart)) { |
| SkTSwap(coinSeg, oppSeg); |
| SkTSwap(coinPtTStart, oppPtTStart); |
| SkTSwap(coinPtTEnd, oppPtTEnd); |
| if (coinPtTStart->fT > coinPtTEnd->fT) { |
| SkTSwap(coinPtTStart, coinPtTEnd); |
| SkTSwap(oppPtTStart, oppPtTEnd); |
| } |
| } |
| double oppMinT = SkTMin(oppPtTStart->fT, oppPtTEnd->fT); |
| double oppMaxT = SkTMax(oppPtTStart->fT, oppPtTEnd->fT); |
| do { |
| if (coinSeg != test->coinPtTStart()->segment()) { |
| continue; |
| } |
| if (coinPtTStart->fT < test->coinPtTStart()->fT) { |
| continue; |
| } |
| if (coinPtTEnd->fT > test->coinPtTEnd()->fT) { |
| continue; |
| } |
| if (oppSeg != test->oppPtTStart()->segment()) { |
| continue; |
| } |
| if (oppMinT < SkTMin(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { |
| continue; |
| } |
| if (oppMaxT > SkTMax(test->oppPtTStart()->fT, test->oppPtTEnd()->fT)) { |
| continue; |
| } |
| return true; |
| } while ((test = test->next())); |
| return false; |
| } |
| |
| void SkOpCoincidence::correctEnds() { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return; |
| } |
| do { |
| coin->correctEnds(); |
| } while ((coin = coin->next())); |
| } |
| |
| // 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->coinPtTStartWritable()->span()->upCast(); |
| if (start->deleted()) { |
| continue; |
| } |
| const SkOpSpanBase* end = coin->coinPtTEnd()->span(); |
| SkASSERT(start == start->starter(end)); |
| bool flipped = coin->flipped(); |
| SkOpSpan* oStart = (flipped ? coin->oppPtTEndWritable() |
| : coin->oppPtTStartWritable())->span()->upCast(); |
| if (oStart->deleted()) { |
| continue; |
| } |
| const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span(); |
| SkASSERT(oStart == oStart->starter(oEnd)); |
| SkOpSegment* segment = start->segment(); |
| SkOpSegment* oSegment = oStart->segment(); |
| bool operandSwap = segment->operand() != oSegment->operand(); |
| if (flipped) { |
| if (oEnd->deleted()) { |
| continue; |
| } |
| 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; |
| } |
| bool addToStart = windValue && (windValue > windDiff || (windValue == windDiff |
| && oWindValue <= oWindDiff)); |
| if (addToStart ? start->done() : oStart->done()) { |
| addToStart ^= true; |
| } |
| if (addToStart) { |
| 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; |
| } |
| #if DEBUG_COINCIDENCE |
| SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", segment->debugID(), |
| start->debugID(), windValue, oppValue); |
| SkDebugf("seg=%d span=%d windValue=%d oppValue=%d\n", oSegment->debugID(), |
| oStart->debugID(), oWindValue, oOppValue); |
| #endif |
| 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; |
| } |
| if (!next->upCastable()) { |
| return false; |
| } |
| 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->next())); |
| return true; |
| } |
| |
| // Please keep this in sync with debugRelease() |
| bool SkOpCoincidence::release(SkCoincidentSpans* coin, SkCoincidentSpans* remove) { |
| SkCoincidentSpans* head = coin; |
| SkCoincidentSpans* prev = nullptr; |
| SkCoincidentSpans* next; |
| do { |
| next = coin->next(); |
| if (coin == remove) { |
| if (prev) { |
| prev->setNext(next); |
| } else if (head == fHead) { |
| fHead = next; |
| } else { |
| fTop = next; |
| } |
| break; |
| } |
| prev = coin; |
| } while ((coin = next)); |
| return coin != nullptr; |
| } |
| |
| void SkOpCoincidence::releaseDeleted(SkCoincidentSpans* coin) { |
| if (!coin) { |
| return; |
| } |
| SkCoincidentSpans* head = coin; |
| SkCoincidentSpans* prev = nullptr; |
| SkCoincidentSpans* next; |
| do { |
| next = coin->next(); |
| if (coin->coinPtTStart()->deleted()) { |
| SkOPASSERT(coin->flipped() ? coin->oppPtTEnd()->deleted() : |
| coin->oppPtTStart()->deleted()); |
| if (prev) { |
| prev->setNext(next); |
| } else if (head == fHead) { |
| fHead = next; |
| } else { |
| fTop = next; |
| } |
| } else { |
| SkOPASSERT(coin->flipped() ? !coin->oppPtTEnd()->deleted() : |
| !coin->oppPtTStart()->deleted()); |
| prev = coin; |
| } |
| } while ((coin = next)); |
| } |
| |
| void SkOpCoincidence::releaseDeleted() { |
| this->releaseDeleted(fHead); |
| this->releaseDeleted(fTop); |
| } |
| |
| // Please keep this in sync with debugReorder() |
| // iterate through all coincident pairs, looking for ranges greater than 1 |
| // if found, see if the opposite pair can match it -- which may require |
| // reordering the ptT pairs |
| bool SkOpCoincidence::reorder() { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return true; |
| } |
| do { |
| // most commonly, concidence are one span long; check for that first |
| int intervals = coin->spanCount(); |
| if (intervals <= 0) { |
| return false; |
| } |
| if (1 == intervals) { |
| #if DEBUG_COINCIDENCE_VERBOSE |
| SkASSERT(!coin->debugExpand(nullptr, nullptr)); |
| #endif |
| continue; |
| } |
| coin->expand(); // be all that you can be |
| if (coin->spanCount() <= 0) { |
| return false; |
| } |
| // check to see if every span in coin has a mate in opp |
| const SkOpSpan* start = coin->coinPtTStart()->span()->upCast(); |
| bool flipped = coin->flipped(); |
| const SkOpSpanBase* oppStartBase = coin->oppPtTStart()->span(); |
| const SkOpSpan* oppStart = flipped ? oppStartBase->prev() : oppStartBase->upCast(); |
| SkDebugf("", start, oppStart); |
| } while ((coin = coin->next())); |
| return true; |
| } |
| |
| void SkOpCoincidence::restoreHead() { |
| SkCoincidentSpans** headPtr = &fHead; |
| while (*headPtr) { |
| headPtr = (*headPtr)->nextPtr(); |
| } |
| *headPtr = fTop; |
| fTop = nullptr; |
| // segments may have collapsed in the meantime; remove empty referenced segments |
| headPtr = &fHead; |
| while (*headPtr) { |
| SkCoincidentSpans* test = *headPtr; |
| if (test->coinPtTStart()->segment()->done() || test->oppPtTStart()->segment()->done()) { |
| *headPtr = test->next(); |
| continue; |
| } |
| headPtr = (*headPtr)->nextPtr(); |
| } |
| } |
| |
| // Please keep this in sync with debugExpand() |
| // expand the range by checking adjacent spans for coincidence |
| bool SkOpCoincidence::expand() { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return false; |
| } |
| bool expanded = false; |
| do { |
| if (coin->expand()) { |
| // check to see if multiple spans expanded so they are now identical |
| SkCoincidentSpans* test = fHead; |
| do { |
| if (coin == test) { |
| continue; |
| } |
| if (coin->coinPtTStart() == test->coinPtTStart() |
| && coin->oppPtTStart() == test->oppPtTStart()) { |
| this->release(fHead, test); |
| break; |
| } |
| } while ((test = test->next())); |
| expanded = true; |
| } |
| } while ((coin = coin->next())); |
| return expanded; |
| } |
| |
| bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps) const { |
| overlaps->fHead = overlaps->fTop = nullptr; |
| SkCoincidentSpans* outer = fHead; |
| while (outer) { |
| const SkOpSegment* outerCoin = outer->coinPtTStart()->segment(); |
| const SkOpSegment* outerOpp = outer->oppPtTStart()->segment(); |
| SkCoincidentSpans* inner = outer; |
| while ((inner = inner->next())) { |
| const SkOpSegment* innerCoin = inner->coinPtTStart()->segment(); |
| if (outerCoin == innerCoin) { |
| continue; // both winners are the same segment, so there's no additional overlap |
| } |
| const SkOpSegment* innerOpp = inner->oppPtTStart()->segment(); |
| const SkOpPtT* overlapS; |
| const SkOpPtT* overlapE; |
| if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->oppPtTStart(), |
| outer->oppPtTEnd(),inner->coinPtTStart(), inner->coinPtTEnd(), &overlapS, |
| &overlapE)) |
| || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->coinPtTStart(), |
| outer->coinPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), |
| &overlapS, &overlapE)) |
| || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(), |
| outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(), |
| &overlapS, &overlapE))) { |
| if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp, |
| overlapS, overlapE)) { |
| return false; |
| } |
| } |
| } |
| outer = outer->next(); |
| } |
| return true; |
| } |
| |
| // Please keep this in sync with debugRemoveCollapsed() |
| bool SkOpCoincidence::removeCollapsed() { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return true; |
| } |
| SkCoincidentSpans** priorPtr = &fHead; |
| do { |
| if (coin->coinPtTStart() == coin->coinPtTEnd()) { |
| return false; |
| } |
| if (coin->oppPtTStart() == coin->oppPtTEnd()) { |
| return false; |
| } |
| if (coin->coinPtTStart()->collapsed(coin->coinPtTEnd())) { |
| *priorPtr = coin->next(); |
| continue; |
| } |
| if (coin->oppPtTStart()->collapsed(coin->oppPtTEnd())) { |
| *priorPtr = coin->next(); |
| continue; |
| } |
| priorPtr = coin->nextPtr(); |
| } while ((coin = coin->next())); |
| return true; |
| } |
| |
| void SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) { |
| SkOPASSERT(deleted != kept); |
| if (fHead) { |
| this->fixUp(fHead, deleted, kept); |
| } |
| if (fTop) { |
| this->fixUp(fTop, deleted, kept); |
| } |
| } |
| |
| void SkOpCoincidence::fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept) { |
| SkCoincidentSpans* head = coin; |
| do { |
| if (coin->coinPtTStart() == deleted) { |
| if (coin->coinPtTEnd()->span() == kept->span()) { |
| this->release(head, coin); |
| continue; |
| } |
| coin->setCoinPtTStart(kept); |
| } |
| if (coin->coinPtTEnd() == deleted) { |
| if (coin->coinPtTStart()->span() == kept->span()) { |
| this->release(head, coin); |
| continue; |
| } |
| coin->setCoinPtTEnd(kept); |
| } |
| if (coin->oppPtTStart() == deleted) { |
| if (coin->oppPtTEnd()->span() == kept->span()) { |
| this->release(head, coin); |
| continue; |
| } |
| coin->setOppPtTStart(kept); |
| } |
| if (coin->oppPtTEnd() == deleted) { |
| if (coin->oppPtTStart()->span() == kept->span()) { |
| this->release(head, coin); |
| continue; |
| } |
| coin->setOppPtTEnd(kept); |
| } |
| } while ((coin = coin->next())); |
| } |
| |
| // Please keep this in sync with debugMark() |
| /* this sets up the coincidence links in the segments when the coincidence crosses multiple spans */ |
| bool SkOpCoincidence::mark() { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return true; |
| } |
| do { |
| FAIL_IF(!coin->coinPtTStartWritable()->span()->upCastable()); |
| SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast(); |
| SkASSERT(!start->deleted()); |
| SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); |
| SkASSERT(!end->deleted()); |
| SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); |
| FAIL_IF(oStart->deleted()); |
| SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span(); |
| SkASSERT(!oEnd->deleted()); |
| bool flipped = coin->flipped(); |
| if (flipped) { |
| SkTSwap(oStart, oEnd); |
| } |
| /* coin and opp spans may not match up. Mark the ends, and then let the interior |
| get marked as many times as the spans allow */ |
| start->insertCoincidence(oStart->upCast()); |
| end->insertCoinEnd(oEnd); |
| const SkOpSegment* segment = start->segment(); |
| const SkOpSegment* oSegment = oStart->segment(); |
| SkOpSpanBase* next = start; |
| SkOpSpanBase* oNext = oStart; |
| bool ordered = coin->ordered(); |
| while ((next = next->upCast()->next()) != end) { |
| FAIL_IF(!next->upCastable()); |
| if (!next->upCast()->insertCoincidence(oSegment, flipped, ordered)) { |
| return false; |
| } |
| } |
| while ((oNext = oNext->upCast()->next()) != oEnd) { |
| FAIL_IF(!oNext->upCastable()); |
| if (!oNext->upCast()->insertCoincidence(segment, flipped, ordered)) { |
| return false; |
| } |
| } |
| } while ((coin = coin->next())); |
| return true; |
| } |
| |
| // Please keep in sync with debugMarkCollapsed() |
| void SkOpCoincidence::markCollapsed(SkCoincidentSpans* coin, SkOpPtT* test) { |
| SkCoincidentSpans* head = coin; |
| while (coin) { |
| if (coin->collapsed(test)) { |
| if (zero_or_one(coin->coinPtTStart()->fT) && zero_or_one(coin->coinPtTEnd()->fT)) { |
| coin->coinPtTStartWritable()->segment()->markAllDone(); |
| } |
| if (zero_or_one(coin->oppPtTStart()->fT) && zero_or_one(coin->oppPtTEnd()->fT)) { |
| coin->oppPtTStartWritable()->segment()->markAllDone(); |
| } |
| this->release(head, coin); |
| } |
| coin = coin->next(); |
| } |
| } |
| |
| // Please keep in sync with debugMarkCollapsed() |
| void SkOpCoincidence::markCollapsed(SkOpPtT* test) { |
| markCollapsed(fHead, test); |
| markCollapsed(fTop, test); |
| } |
| |
| bool SkOpCoincidence::Ordered(const SkOpSegment* coinSeg, const SkOpSegment* oppSeg) { |
| if (coinSeg->verb() < oppSeg->verb()) { |
| return true; |
| } |
| if (coinSeg->verb() > oppSeg->verb()) { |
| return false; |
| } |
| int count = (SkPathOpsVerbToPoints(coinSeg->verb()) + 1) * 2; |
| const SkScalar* cPt = &coinSeg->pts()[0].fX; |
| const SkScalar* oPt = &oppSeg->pts()[0].fX; |
| for (int index = 0; index < count; ++index) { |
| if (*cPt < *oPt) { |
| return true; |
| } |
| if (*cPt > *oPt) { |
| return false; |
| } |
| ++cPt; |
| ++oPt; |
| } |
| return true; |
| } |
| |
| bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e, |
| const SkOpPtT* coin2s, const SkOpPtT* coin2e, double* overS, double* overE) const { |
| SkASSERT(coin1s->segment() == coin2s->segment()); |
| *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; |
| } |
| |
| // Commented-out lines keep this in sync with debugRelease() |
| void SkOpCoincidence::release(const SkOpSegment* deleted) { |
| SkCoincidentSpans* coin = fHead; |
| if (!coin) { |
| return; |
| } |
| do { |
| if (coin->coinPtTStart()->segment() == deleted |
| || coin->coinPtTEnd()->segment() == deleted |
| || coin->oppPtTStart()->segment() == deleted |
| || coin->oppPtTEnd()->segment() == deleted) { |
| this->release(fHead, coin); |
| } |
| } while ((coin = coin->next())); |
| } |
| |
| bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const SkOpPtT* testS, |
| const SkOpPtT* testE) const { |
| return testS->segment()->testForCoincidence(testS, testE, testS->span(), |
| testE->span(), outer->coinPtTStart()->segment()); |
| } |