| /* | |
| * 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; | |
| } | |
| // 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); | |
| } | |
| if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe | |
| SkDEBUGPARAMS(true) /* do assert if addOrOverlap fails */ )) { | |
| 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; | |
| SkASSERT(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(); | |
| 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->t() >= t) { | |
| return 1; | |
| } | |
| 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())); | |
| SkASSERT(coinStart); | |
| SkASSERT(coinEnd); | |
| // 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) { | |
| return false; // complete overlap, already included, do nothing | |
| } | |
| *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 | |
| 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 false; | |
| } | |
| oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e)); | |
| oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e)); | |
| if (oppSeg->collapsed(oppTs, oppTe)) { | |
| return false; | |
| } | |
| if (coinTs > coinTe) { | |
| SkTSwap(coinTs, coinTe); | |
| SkTSwap(oppTs, oppTe); | |
| } | |
| return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe | |
| SkDEBUGPARAMS(false) /* don't assert if addOrOverlap fails */ ); | |
| } | |
| /* 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 | |
| SkDEBUGPARAMS(bool callerAborts)) { | |
| SkTDArray<SkCoincidentSpans*> overlaps; | |
| RETURN_FALSE_IF(callerAborts, !fTop); | |
| if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { | |
| return false; | |
| } | |
| if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, | |
| coinTe, oppTs, oppTe, &overlaps)) { | |
| return false; | |
| } | |
| 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); | |
| RETURN_FALSE_IF(callerAborts, overlap && cs && ce && overlap->contains(cs, ce)); | |
| RETURN_FALSE_IF(callerAborts, cs == ce && cs); | |
| const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); | |
| const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); | |
| RETURN_FALSE_IF(callerAborts, overlap && os && oe && overlap->contains(os, oe)); | |
| 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; | |
| RETURN_FALSE_IF(callerAborts, csExisting && csExisting == ceExisting); | |
| RETURN_FALSE_IF(callerAborts, csExisting && (csExisting == ce || | |
| csExisting->contains(ceExisting ? ceExisting : ce))); | |
| RETURN_FALSE_IF(callerAborts, 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; | |
| RETURN_FALSE_IF(callerAborts, osExisting && osExisting == oeExisting); | |
| RETURN_FALSE_IF(callerAborts, osExisting && (osExisting == oe || | |
| osExisting->contains(oeExisting ? oeExisting : oe))); | |
| RETURN_FALSE_IF(callerAborts, 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); | |
| SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) | |
| : oppSeg->addT(oppTs); | |
| RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable); | |
| csWritable->span()->addOpp(osWritable->span()); | |
| cs = csWritable; | |
| os = osWritable->active(); | |
| RETURN_FALSE_IF(callerAborts, (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(); | |
| RETURN_FALSE_IF(callerAborts, cs->deleted()); | |
| RETURN_FALSE_IF(callerAborts, os->deleted()); | |
| RETURN_FALSE_IF(callerAborts, ce->deleted()); | |
| RETURN_FALSE_IF(callerAborts, oe->deleted()); | |
| RETURN_FALSE_IF(callerAborts, 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(); | |
| return result; | |
| } | |
| // 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() { | |
| 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 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 false; | |
| } | |
| 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 false; | |
| } | |
| const SkOpPtT* ice = inner->coinPtTEnd(); | |
| SkASSERT(!ice->deleted()); | |
| if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) { | |
| added |= this->addIfMissing(ocs->starter(oce), ics->starter(ice), | |
| overS, overE, outerOppWritable, innerOppWritable | |
| 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)) { | |
| added |= this->addIfMissing(ocs->starter(oce), ios->starter(ioe), | |
| overS, overE, outerOppWritable, innerCoinWritable | |
| 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)) { | |
| added |= this->addIfMissing(oos->starter(ooe), ics->starter(ice), | |
| overS, overE, outerCoinWritable, innerOppWritable | |
| 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 false; | |
| } | |
| SkASSERT(outerCoin != innerCoin); | |
| if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) { | |
| added |= this->addIfMissing(oos->starter(ooe), ios->starter(ioe), | |
| overS, overE, outerCoinWritable, innerCoinWritable | |
| SkDEBUGPARAMS(oos->debugEnder(ooe)) | |
| SkDEBUGPARAMS(ios->debugEnder(ioe))); | |
| } | |
| } | |
| this->debugValidate(); | |
| } | |
| } while ((outer = outer->next())); | |
| this->restoreHead(); | |
| return added; | |
| } | |
| 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 { | |
| if (!coin->coinPtTStartWritable()->span()->upCastable()) { | |
| return false; | |
| } | |
| SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast(); | |
| SkASSERT(!start->deleted()); | |
| SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); | |
| SkASSERT(!end->deleted()); | |
| SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); | |
| if (oStart->deleted()) { | |
| return false; | |
| } | |
| 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; | |
| while ((next = next->upCast()->next()) != end) { | |
| if (!next->upCastable()) { | |
| return false; | |
| } | |
| if (!next->upCast()->insertCoincidence(oSegment, flipped)) { | |
| return false; | |
| } | |
| } | |
| while ((oNext = oNext->upCast()->next()) != oEnd) { | |
| if (!oNext->upCastable()) { | |
| return false; | |
| } | |
| if (!oNext->upCast()->insertCoincidence(segment, flipped)) { | |
| 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()); | |
| } |