Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1253)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/pathops/SkOpCoincidence.cpp

Issue 2128633003: pathops coincidence and security rewrite (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: require resulting t to be between 0 and 1 Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« src/pathops/SkDQuadLineIntersection.cpp ('K') | « src/pathops/SkOpCoincidence.h ('k') | src/pathops/SkOpContour.h » ('j') | src/pathops/SkPathOpsCurve.h » ('J')
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/pathops/SkOpCoincidence.cpp
diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp
index 4b46e685ee838bdf50edc0e5f0b01ed03c4a8040..0c868c40dd86fb6e00b315d490e75d34378a26a9 100755
--- a/src/pathops/SkOpCoincidence.cpp
+++ b/src/pathops/SkOpCoincidence.cpp
@@ -8,237 +8,723 @@
#include "SkOpSegment.h"
#include "SkPathOpsTSect.h"
-bool SkOpCoincidence::extend(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
- SkOpPtT* oppPtTEnd) {
- // if there is an existing pair that overlaps the addition, extend it
+#if DEBUG_COINCIDENCE
+#define FAIL_IF(cond) SkASSERT(!(cond))
+#else
+#define FAIL_IF(cond) do { if (cond) return false; } while (false)
+#endif
+
+// 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) ) {
herb_g 2016/07/18 15:13:39 Do you need method pointers? Can this just use pla
caryclark 2016/07/18 15:55:49 It could be rewritten. I'm curious how that rewrit
+ 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);
+ }
+}
+
+// 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();
+ 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) {
- do {
- if (coinRec->fCoinPtTStart->segment() != coinPtTStart->segment()) {
- continue;
- }
- if (coinRec->fOppPtTStart->segment() != oppPtTStart->segment()) {
+ 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) {
+ // FIXME: caller should have already sorted
herb_g 2016/07/18 15:13:39 Does this need an assert to check for sortedness?
caryclark 2016/07/18 15:55:49 If it is already sorted, the Ordered() function wi
+ 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);
+ SkASSERT(!coinPtTStart->deleted());
+ SkASSERT(!coinPtTEnd->deleted());
+ SkASSERT(!oppPtTStart->deleted());
+ SkASSERT(!oppPtTEnd->deleted());
+ DebugCheckAdd(fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
+ DebugCheckAdd(fTop, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd);
+ SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(
+ this->globalState()->allocator());
+ coinRec->init();
+ coinRec->set(this->fHead, coinPtTStart, coinPtTEnd, oppPtTStart, oppPtTEnd
+ SkDEBUGPARAMS(fGlobalState->nextCoinID()));
+ fHead = coinRec;
+}
+
+// description below
+void 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 (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;
}
- if (coinRec->fCoinPtTStart->fT > coinPtTEnd->fT) {
+ SkDPoint oppPt = i.pt(index);
+ if (!oppPt.approximatelyEqual(pt)) {
continue;
}
- if (coinRec->fCoinPtTEnd->fT < coinPtTStart->fT) {
+ SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg);
+ SkOpPtT* oppStart = writableSeg->addT(t, SkOpSegment::kAllowAliasMatch, nullptr);
+ SkOpSpan* writableBase = const_cast<SkOpSpan*>(base);
+ oppStart->span()->addOppAndMerge(writableBase);
+ if (oppStart->deleted()) {
continue;
}
- if (coinRec->fCoinPtTStart->fT > coinPtTStart->fT) {
- coinRec->fCoinPtTStart = coinPtTStart;
- coinRec->fOppPtTStart = oppPtTStart;
+ SkOpSegment* coinSeg = base->segment();
+ SkOpSegment* oppSeg = oppStart->segment();
+ double coinTs, coinTe, oppTs, oppTe;
+ if (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 (coinRec->fCoinPtTEnd->fT < coinPtTEnd->fT) {
- coinRec->fCoinPtTEnd = coinPtTEnd;
- coinRec->fOppPtTEnd = oppPtTEnd;
+ if (coinTs > coinTe) {
+ SkTSwap(coinTs, coinTe);
+ SkTSwap(oppTs, oppTe);
}
- return true;
- } while ((coinRec = coinRec->fNext));
+ (void) this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe);
+ }
}
- return false;
}
-void SkOpCoincidence::add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
- SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
- SkASSERT(coinPtTStart->fT < coinPtTEnd->fT);
- bool flipped = oppPtTStart->fT > oppPtTEnd->fT;
- SkCoincidentSpans* coinRec = SkOpTAllocator<SkCoincidentSpans>::Allocate(allocator);
- coinRec->fNext = this->fHead;
- coinRec->fCoinPtTStart = coinPtTStart;
- coinRec->fCoinPtTEnd = coinPtTEnd;
- coinRec->fOppPtTStart = oppPtTStart;
- coinRec->fOppPtTEnd = oppPtTEnd;
- coinRec->fFlipped = flipped;
- SkDEBUGCODE(coinRec->fID = fDebugState->nextCoinID());
-
- this->fHead = coinRec;
+// description below
+bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) {
+ const SkOpSpan* base = ptT->span()->upCast();
+ const SkOpSpan* prev = base->prev();
+ if (!prev) {
+ return false;
+ }
+ if (!prev->isCanceled()) {
+ this->addEndMovedSpans(base, base->prev());
+ }
+ if (!base->isCanceled()) {
+ this->addEndMovedSpans(base, base->next());
+ }
+ return true;
}
-static void t_range(const SkOpPtT* overS, const SkOpPtT* overE, double tStart, double tEnd,
- const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs, double* coinTe) {
- double denom = overE->fT - overS->fT;
- double start = 0 < denom ? tStart : tEnd;
- double end = 0 < denom ? tEnd : tStart;
- double sRatio = (start - overS->fT) / denom;
- double eRatio = (end - overS->fT) / denom;
- *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio;
- *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio;
+/* 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) {
+ if (1 == span->coinPtTStart()->fT) {
+ return false;
+ }
+ 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;
}
-bool SkOpCoincidence::addExpanded(SkChunkAlloc* allocator
- PATH_OPS_DEBUG_VALIDATE_PARAMS(SkOpGlobalState* globalState)) {
-#if DEBUG_VALIDATE
- globalState->setPhase(SkOpGlobalState::kIntersecting);
-#endif
- // for each coincident pair, match the spans
- // if the spans don't match, add the mssing pt to the segment and loop it in the opposite span
+/* 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;
- SkASSERT(coin);
+ if (!coin) {
+ return true;
+ }
do {
- SkOpPtT* startPtT = coin->fCoinPtTStart;
- SkOpPtT* oStartPtT = coin->fOppPtTStart;
+ const SkOpPtT* startPtT = coin->coinPtTStart();
+ const SkOpPtT* oStartPtT = coin->oppPtTStart();
SkASSERT(startPtT->contains(oStartPtT));
- SkASSERT(coin->fCoinPtTEnd->contains(coin->fOppPtTEnd));
- SkOpSpanBase* start = startPtT->span();
- SkOpSpanBase* oStart = oStartPtT->span();
- const SkOpSpanBase* end = coin->fCoinPtTEnd->span();
- const SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
- if (oEnd->deleted()) {
- return false;
- }
- SkOpSpanBase* test = start->upCast()->next();
- SkOpSpanBase* oTest = coin->fFlipped ? oStart->prev() : oStart->upCast()->next();
+ SkASSERT(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());
+ const SkOpSpanBase* test = start->upCast()->next();
+ const SkOpSpanBase* oTest = coin->flipped() ? oStart->prev() : oStart->upCast()->next();
if (!oTest) {
return false;
}
while (test != end || oTest != oEnd) {
- if (!test->ptT()->contains(oTest->ptT())) {
+ if (!test->ptT()->contains(oStart->segment())
+ || !oTest->ptT()->contains(start->segment())) {
// use t ranges to guess which one is missing
- double startRange = coin->fCoinPtTEnd->fT - startPtT->fT;
- if (!startRange) {
- return false;
- }
+ double startRange = coin->coinPtTEnd()->fT - startPtT->fT;
+ FAIL_IF(!startRange);
double startPart = (test->t() - startPtT->fT) / startRange;
- double oStartRange = coin->fOppPtTEnd->fT - oStartPtT->fT;
- if (!oStartRange) {
- return false;
- }
+ double oStartRange = coin->oppPtTEnd()->fT - oStartPtT->fT;
+ FAIL_IF(!oStartRange);
double oStartPart = (oTest->t() - oStartPtT->fT) / oStartRange;
- if (startPart == oStartPart) {
+ FAIL_IF(startPart == oStartPart);
+ bool startOver = false;
+ bool success = startPart < oStartPart
+ ? oStart->segment()->addExpanded(
+ oStartPtT->fT + oStartRange * startPart, test, &startOver)
+ : start->segment()->addExpanded(
+ startPtT->fT + startRange * oStartPart, oTest, &startOver);
+ if (!success) {
+ SkASSERT(0);
return false;
}
- SkOpPtT* newPt;
- if (startPart < oStartPart) {
- double newT = oStartPtT->fT + oStartRange * startPart;
- newPt = oStart->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator);
- if (!newPt) {
- return false;
- }
- newPt->fPt = test->pt();
- test->ptT()->addOpp(newPt);
- } else {
- double newT = startPtT->fT + startRange * oStartPart;
- newPt = start->segment()->addT(newT, SkOpSegment::kAllowAlias, allocator);
- if (!newPt) {
- return false;
- }
- newPt->fPt = oTest->pt();
- oTest->ptT()->addOpp(newPt);
+ if (startOver) {
+ test = start;
+ oTest = oStart;
}
- // start over
- test = start;
- oTest = oStart;
}
if (test != end) {
test = test->upCast()->next();
}
if (oTest != oEnd) {
- oTest = coin->fFlipped ? oTest->prev() : oTest->upCast()->next();
+ oTest = coin->flipped() ? oTest->prev() : oTest->upCast()->next();
if (!oTest) {
return false;
}
}
}
- } while ((coin = coin->fNext));
-#if DEBUG_VALIDATE
- globalState->setPhase(SkOpGlobalState::kWalking);
-#endif
+ } 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, SkChunkAlloc* allocator) {
- SkCoincidentSpans* check = this->fTop;
+ 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
+void SkOpCoincidence::TRange(const SkOpPtT* overS, const SkOpPtT* overE, double tStart,
+ double tEnd, const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, double* coinTs,
+ double* coinTe) {
+ double denom = overE->fT - overS->fT;
+ double start = 0 < denom ? tStart : tEnd;
+ double end = 0 < denom ? tEnd : tStart;
+ double sRatio = (start - overS->fT) / denom;
+ double eRatio = (end - overS->fT) / denom;
+ *coinTs = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * sRatio;
+ *coinTe = coinPtTStart->fT + (coinPtTEnd->fT - coinPtTStart->fT) * eRatio;
+}
+
+// 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->fCoinPtTStart->span() == over1s->span()
- && check->fOppPtTStart->span() == outer->fOppPtTStart->span()) {
- SkASSERT(check->fCoinPtTEnd->span() == over1e->span()
- || !fDebugState->debugRunFail());
- SkASSERT(check->fOppPtTEnd->span() == outer->fOppPtTEnd->span()
- || !fDebugState->debugRunFail());
- return false;
+ if (check->coinPtTStart()->segment() != coinSeg) {
+ continue;
}
- if (check->fCoinPtTStart->span() == outer->fCoinPtTStart->span()
- && check->fOppPtTStart->span() == over1s->span()) {
- SkASSERT(check->fCoinPtTEnd->span() == outer->fCoinPtTEnd->span()
- || !fDebugState->debugRunFail());
- SkASSERT(check->fOppPtTEnd->span() == over1e->span()
- || !fDebugState->debugRunFail());
- return false;
+ if (check->oppPtTStart()->segment() != oppSeg) {
+ continue;
}
- } while ((check = check->fNext));
- this->add(outer->fCoinPtTStart, outer->fCoinPtTEnd, over1s, over1e, allocator);
-#if 0
- // FIXME: up to four flavors could be added -- do we need only one?
-#endif
+ 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() */
bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over1e,
- const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
+ const SkOpPtT* over2s, const SkOpPtT* over2e, double tStart, double tEnd,
SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
- SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, SkChunkAlloc* allocator) {
+ SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) {
double coinTs, coinTe, oppTs, oppTe;
- t_range(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
- t_range(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
+ TRange(over1s, over1e, tStart, tEnd, coinPtTStart, coinPtTEnd, &coinTs, &coinTe);
+ TRange(over2s, over2e, tStart, tEnd, oppPtTStart, oppPtTEnd, &oppTs, &oppTe);
+ bool swap = coinTs > coinTe;
+ if (swap) {
+ SkTSwap(coinTs, coinTe);
+ }
+ if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
+ SkTSwap(oppTs, oppTe);
+ }
+ if (swap) {
+ SkTSwap(oppTs, oppTe);
+ }
SkOpSegment* coinSeg = coinPtTStart->segment();
SkOpSegment* oppSeg = oppPtTStart->segment();
- SkASSERT(coinSeg != oppSeg);
- SkCoincidentSpans* check = this->fTop;
- do {
- const SkOpSegment* checkCoinSeg = check->fCoinPtTStart->segment();
- if (checkCoinSeg != coinSeg && checkCoinSeg != oppSeg) {
- continue;
+ if (coinSeg == oppSeg) {
+ return false;
+ }
+ return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe);
+}
+
+/* Please keep this in sync with debugAddOrOverlap() */
+bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
+ double coinTs, double coinTe, double oppTs, double oppTe) {
+ SkTDArray<SkCoincidentSpans*> overlaps;
+ SkASSERT(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());
}
- const SkOpSegment* checkOppSeg = check->fOppPtTStart->segment();
- if (checkOppSeg != coinSeg && checkOppSeg != oppSeg) {
- continue;
+ 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());
}
- int cTs = coinTs;
- int cTe = coinTe;
- int oTs = oppTs;
- int oTe = oppTe;
- if (checkCoinSeg != coinSeg) {
- SkASSERT(checkOppSeg != oppSeg);
- SkTSwap(cTs, oTs);
- SkTSwap(cTe, oTe);
- }
- int tweenCount = (int) between(check->fCoinPtTStart->fT, cTs, check->fCoinPtTEnd->fT)
- + (int) between(check->fCoinPtTStart->fT, cTe, check->fCoinPtTEnd->fT)
- + (int) between(check->fOppPtTStart->fT, oTs, check->fOppPtTEnd->fT)
- + (int) between(check->fOppPtTStart->fT, oTe, check->fOppPtTEnd->fT);
-// SkASSERT(tweenCount == 0 || tweenCount == 4);
- if (tweenCount) {
+ 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 false;
+ }
+ SkASSERT(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 false;
+ }
+ 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;
+ if (csExisting && csExisting == ceExisting) {
+ return false;
+ }
+ if (csExisting && (csExisting == ce || csExisting->contains(ceExisting ? ceExisting : ce))) {
+ return false;
+ }
+ if (ceExisting && (ceExisting == cs || ceExisting->contains(csExisting ? csExisting : cs))) {
+ return false;
+ }
+ const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr;
+ const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr;
+ if (osExisting && osExisting == oeExisting) {
+ return false;
+ }
+ if (osExisting && (osExisting == oe || osExisting->contains(oeExisting ? oeExisting : oe))) {
+ return false;
+ }
+ if (oeExisting && (oeExisting == os || oeExisting->contains(osExisting ? osExisting : os))) {
+ return false;
+ }
+ // extra line in debug code
+ this->debugValidate();
+ if (!cs || !os) {
+ SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs)
+ : coinSeg->addT(coinTs, SkOpSegment::kNoAliasMatch, nullptr);
+ SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os)
+ : oppSeg->addT(oppTs, SkOpSegment::kNoAliasMatch, nullptr);
+ csWritable->span()->addOppAndMerge(osWritable->span());
+ cs = csWritable;
+ os = osWritable;
+ if ((ce && ce->deleted()) || (oe && oe->deleted())) {
return false;
}
- } while ((check = check->fNext));
- if ((over1s->fT < over1e->fT) != (over2s->fT < over2e->fT)) {
- SkTSwap(oppTs, oppTe);
}
- if (coinTs > coinTe) {
- SkTSwap(coinTs, coinTe);
- SkTSwap(oppTs, oppTe);
+ if (!ce || !oe) {
+ SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce)
+ : coinSeg->addT(coinTe, SkOpSegment::kNoAliasMatch, nullptr);
+ SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe)
+ : oppSeg->addT(oppTe, SkOpSegment::kNoAliasMatch, nullptr);
+ ceWritable->span()->addOppAndMerge(oeWritable->span());
+ ce = ceWritable;
+ oe = oeWritable;
}
- SkOpPtT* cs = coinSeg->addMissing(coinTs, oppSeg, allocator);
- SkOpPtT* ce = coinSeg->addMissing(coinTe, oppSeg, allocator);
- SkASSERT(cs != ce);
- SkOpPtT* os = oppSeg->addMissing(oppTs, coinSeg, allocator);
- SkOpPtT* oe = oppSeg->addMissing(oppTe, coinSeg, allocator);
-// SkASSERT(os != oe);
- cs->addOpp(os);
- ce->addOpp(oe);
- this->add(cs, ce, os, oe, allocator);
- return true;
+ this->debugValidate();
+ if (cs->deleted() || os->deleted() || ce->deleted() || oe->deleted()) {
+ return false;
+ }
+ if (cs->contains(ce) || os->contains(oe)) {
+ return false;
+ }
+ 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 */
-bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) {
+// returns true if caller should loop again
+bool SkOpCoincidence::addMissing() {
SkCoincidentSpans* outer = fHead;
if (!outer) {
- return true;
+ return false;
}
bool added = false;
fTop = outer;
@@ -247,107 +733,116 @@ bool SkOpCoincidence::addMissing(SkChunkAlloc* allocator) {
// 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->fCoinPtTStart->segment();
- SkASSERT(outerCoin == outer->fCoinPtTEnd->segment());
- const SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
- SkASSERT(outerOpp == outer->fOppPtTEnd->segment());
+ const SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
+ const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
+ if (outerCoin->done() || outerOpp->done()) {
+ continue;
+ }
SkCoincidentSpans* inner = outer;
- while ((inner = inner->fNext)) {
+ while ((inner = inner->next())) {
+ this->debugValidate();
double overS, overE;
- const SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
- SkASSERT(innerCoin == inner->fCoinPtTEnd->segment());
- const SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
- SkASSERT(innerOpp == inner->fOppPtTEnd->segment());
- if (outerCoin == innerCoin
- && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
- inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
- added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
- inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
- outer->fOppPtTStart, outer->fOppPtTEnd,
- inner->fOppPtTStart, inner->fOppPtTEnd, allocator);
- } else if (outerCoin == innerOpp
- && this->overlap(outer->fCoinPtTStart, outer->fCoinPtTEnd,
- inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
- added |= this->addIfMissing(outer->fCoinPtTStart, outer->fCoinPtTEnd,
- inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
- outer->fOppPtTStart, outer->fOppPtTEnd,
- inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator);
- } else if (outerOpp == innerCoin
- && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
- inner->fCoinPtTStart, inner->fCoinPtTEnd, &overS, &overE)) {
- added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
- inner->fCoinPtTStart, inner->fCoinPtTEnd, overS, overE,
- outer->fCoinPtTStart, outer->fCoinPtTEnd,
- inner->fOppPtTStart, inner->fOppPtTEnd, allocator);
- } else if (outerOpp == innerOpp
- && this->overlap(outer->fOppPtTStart, outer->fOppPtTEnd,
- inner->fOppPtTStart, inner->fOppPtTEnd, &overS, &overE)) {
- added |= this->addIfMissing(outer->fOppPtTStart, outer->fOppPtTEnd,
- inner->fOppPtTStart, inner->fOppPtTEnd, overS, overE,
- outer->fCoinPtTStart, outer->fCoinPtTEnd,
- inner->fCoinPtTStart, inner->fCoinPtTEnd, allocator);
- } else if (outerCoin != innerCoin) {
- // 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
- SkOpPtT* testS = outer->fCoinPtTStart->contains(innerCoin);
- SkOpPtT* testE = outer->fCoinPtTEnd->contains(innerCoin);
- if (testS && testS->fT >= inner->fCoinPtTStart->fT
- && testE && testE->fT <= inner->fCoinPtTEnd->fT
- && this->testForCoincidence(outer, testS, testE)) {
- added |= this->addIfMissing(outer, testS, testE, allocator);
- } else {
- testS = inner->fCoinPtTStart->contains(outerCoin);
- testE = inner->fCoinPtTEnd->contains(outerCoin);
- if (testS && testS->fT >= outer->fCoinPtTStart->fT
- && testE && testE->fT <= outer->fCoinPtTEnd->fT
- && this->testForCoincidence(inner, testS, testE)) {
- added |= this->addIfMissing(inner, testS, testE, allocator);
- }
+ const SkOpSegment* innerCoin = inner->coinPtTStart()->segment();
+ const SkOpSegment* innerOpp = inner->oppPtTStart()->segment();
+ if (innerCoin->done() || innerOpp->done()) {
+ continue;
+ }
+ if (outerCoin == innerCoin) {
+ if (outerOpp != innerOpp
+ && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
+ added |= this->addIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
+ outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd());
+ }
+ } else if (outerCoin == innerOpp) {
+ if (outerOpp != innerCoin
+ && this->overlap(outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
+ added |= this->addIfMissing(outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
+ outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd());
+ }
+ } else if (outerOpp == innerCoin) {
+ SkASSERT(outerCoin != innerOpp);
+ if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), &overS, &overE)) {
+ added |= this->addIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd(), overS, overE,
+ outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd());
+ }
+ } else if (outerOpp == innerOpp) {
+ SkASSERT(outerCoin != innerCoin);
+ if (this->overlap(outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), &overS, &overE)) {
+ added |= this->addIfMissing(outer->oppPtTStart(), outer->oppPtTEnd(),
+ inner->oppPtTStart(), inner->oppPtTEnd(), overS, overE,
+ outer->coinPtTStart(), outer->coinPtTEnd(),
+ inner->coinPtTStart(), inner->coinPtTEnd());
}
}
-#if 0 && DEBUG_COINCIDENCE
- SkString miss;
- miss.printf("addMissing inner=%d outer=%d", inner->debugID(), outer->debugID());
- DEBUG_COINCIDENCE_HEALTH(fDebugState->contourHead(), miss.c_str());
-#endif
+ this->debugValidate();
}
- } while ((outer = outer->fNext));
- SkCoincidentSpans** headPtr = &fHead;
- while (*headPtr) {
- SkCoincidentSpans** headNext = &(*headPtr)->fNext;
- if (*headNext) {
- break;
- }
- headPtr = headNext;
- }
- *headPtr = fTop;
+ } while ((outer = outer->next()));
+ this->restoreHead();
return added;
}
-bool SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegment* seg2,
- SkOpSegment* seg2o, SkOpPtT* overS, SkOpPtT* overE, SkChunkAlloc* allocator) {
- SkOpPtT* s1 = overS->find(seg1);
- SkOpPtT* e1 = overE->find(seg1);
+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()) {
- s1 = overS->find(seg1o);
- e1 = overE->find(seg1o);
+ 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;
}
}
- SkOpPtT* s2 = overS->find(seg2);
- SkOpPtT* e2 = overE->find(seg2);
+ 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()) {
- s2 = overS->find(seg2o);
- e2 = overE->find(seg2o);
+ 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;
}
@@ -359,26 +854,144 @@ bool SkOpCoincidence::addOverlap(SkOpSegment* seg1, SkOpSegment* seg1o, SkOpSegm
SkTSwap(s1, e1);
SkTSwap(s2, e2);
}
- this->add(s1, e1, s2, e2, allocator);
+ this->add(s1, e1, s2, e2);
return true;
}
-bool SkOpCoincidence::contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
- const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd, bool flipped) const {
- const SkCoincidentSpans* coin = fHead;
- if (!coin) {
+/* 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 {
- if (coin->fCoinPtTStart == coinPtTStart && coin->fCoinPtTEnd == coinPtTEnd
- && coin->fOppPtTStart == oppPtTStart && coin->fOppPtTEnd == oppPtTEnd
- && coin->fFlipped == flipped) {
+ // 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;
}
- } while ((coin = coin->fNext));
+ 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;
@@ -386,18 +999,19 @@ bool SkOpCoincidence::apply() {
return true;
}
do {
- SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
+ SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
if (start->deleted()) {
continue;
}
- SkOpSpanBase* end = coin->fCoinPtTEnd->span();
+ const SkOpSpanBase* end = coin->coinPtTEnd()->span();
SkASSERT(start == start->starter(end));
- bool flipped = coin->fFlipped;
- SkOpSpan* oStart = (flipped ? coin->fOppPtTEnd : coin->fOppPtTStart)->span()->upCast();
+ bool flipped = coin->flipped();
+ SkOpSpan* oStart = (flipped ? coin->oppPtTEndWritable()
+ : coin->oppPtTStartWritable())->span()->upCast();
if (oStart->deleted()) {
continue;
}
- SkOpSpanBase* oEnd = (flipped ? coin->fOppPtTStart : coin->fOppPtTEnd)->span();
+ const SkOpSpanBase* oEnd = (flipped ? coin->oppPtTStart() : coin->oppPtTEnd())->span();
SkASSERT(oStart == oStart->starter(oEnd));
SkOpSegment* segment = start->segment();
SkOpSegment* oSegment = oStart->segment();
@@ -427,8 +1041,12 @@ bool SkOpCoincidence::apply() {
windDiff = -windDiff;
oWindDiff = -oWindDiff;
}
- if (windValue && (windValue > windDiff || (windValue == windDiff
- && oWindValue <= 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);
}
@@ -465,6 +1083,12 @@ bool SkOpCoincidence::apply() {
}
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);
@@ -490,29 +1114,87 @@ bool SkOpCoincidence::apply() {
}
oStart = oNext->upCast();
} while (true);
- } while ((coin = coin->fNext));
+ } while ((coin = coin->next()));
return true;
}
-void SkOpCoincidence::release(SkCoincidentSpans* remove) {
- SkCoincidentSpans* coin = fHead;
+// 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->fNext;
+ next = coin->next();
if (coin == remove) {
if (prev) {
- prev->fNext = next;
- } else {
+ prev->setNext(next);
+ } else if (head == fHead) {
fHead = next;
+ } else {
+ fTop = next;
}
break;
}
prev = coin;
} while ((coin = next));
- SkASSERT(coin);
+ return coin != nullptr;
+}
+
+// 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()
bool SkOpCoincidence::expand() {
SkCoincidentSpans* coin = fHead;
if (!coin) {
@@ -520,142 +1202,132 @@ bool SkOpCoincidence::expand() {
}
bool expanded = false;
do {
- SkOpSpan* start = coin->fCoinPtTStart->span()->upCast();
- SkOpSpanBase* end = coin->fCoinPtTEnd->span();
- SkOpSegment* segment = coin->fCoinPtTStart->segment();
- SkOpSegment* oppSegment = coin->fOppPtTStart->segment();
- SkOpSpan* prev = start->prev();
- SkOpPtT* oppPtT;
- if (prev && (oppPtT = prev->contains(oppSegment))) {
- double midT = (prev->t() + start->t()) / 2;
- if (segment->isClose(midT, oppSegment)) {
- coin->fCoinPtTStart = prev->ptT();
- coin->fOppPtTStart = oppPtT;
- expanded = true;
- }
- }
- SkOpSpanBase* next = end->final() ? nullptr : end->upCast()->next();
- if (next && (oppPtT = next->contains(oppSegment))) {
- double midT = (end->t() + next->t()) / 2;
- if (segment->isClose(midT, oppSegment)) {
- coin->fCoinPtTEnd = next->ptT();
- coin->fOppPtTEnd = oppPtT;
- expanded = true;
- }
+ 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->fNext));
+ } while ((coin = coin->next()));
return expanded;
}
-bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps, SkChunkAlloc* allocator) const {
+bool SkOpCoincidence::findOverlaps(SkOpCoincidence* overlaps) const {
overlaps->fHead = overlaps->fTop = nullptr;
- SkDEBUGCODE_(overlaps->debugSetGlobalState(fDebugState));
SkCoincidentSpans* outer = fHead;
while (outer) {
- SkOpSegment* outerCoin = outer->fCoinPtTStart->segment();
- SkOpSegment* outerOpp = outer->fOppPtTStart->segment();
+ const SkOpSegment* outerCoin = outer->coinPtTStart()->segment();
+ const SkOpSegment* outerOpp = outer->oppPtTStart()->segment();
SkCoincidentSpans* inner = outer;
- while ((inner = inner->fNext)) {
- SkOpSegment* innerCoin = inner->fCoinPtTStart->segment();
+ 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
}
- SkOpSegment* innerOpp = inner->fOppPtTStart->segment();
- SkOpPtT* overlapS, * overlapE;
- if ((outerOpp == innerCoin && SkOpPtT::Overlaps(outer->fOppPtTStart, outer->fOppPtTEnd,
- inner->fCoinPtTStart, inner->fCoinPtTEnd, &overlapS, &overlapE))
- || (outerCoin == innerOpp && SkOpPtT::Overlaps(outer->fCoinPtTStart,
- outer->fCoinPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd,
+ 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->fOppPtTStart,
- outer->fOppPtTEnd, inner->fOppPtTStart, inner->fOppPtTEnd,
+ || (outerOpp == innerOpp && SkOpPtT::Overlaps(outer->oppPtTStart(),
+ outer->oppPtTEnd(), inner->oppPtTStart(), inner->oppPtTEnd(),
&overlapS, &overlapE))) {
if (!overlaps->addOverlap(outerCoin, outerOpp, innerCoin, innerOpp,
- overlapS, overlapE, allocator)) {
+ overlapS, overlapE)) {
return false;
}
}
}
- outer = outer->fNext;
+ outer = outer->next();
}
return true;
}
-bool SkOpCoincidence::fixAligned() {
+// Please keep this in sync with debugRemoveCollapsed()
+bool SkOpCoincidence::removeCollapsed() {
SkCoincidentSpans* coin = fHead;
if (!coin) {
return true;
}
- do {
- if (coin->fCoinPtTStart->deleted()) {
- coin->fCoinPtTStart = coin->fCoinPtTStart->doppelganger();
- }
- if (coin->fCoinPtTEnd->deleted()) {
- coin->fCoinPtTEnd = coin->fCoinPtTEnd->doppelganger();
- }
- if (coin->fOppPtTStart->deleted()) {
- coin->fOppPtTStart = coin->fOppPtTStart->doppelganger();
- }
- if (coin->fOppPtTEnd->deleted()) {
- coin->fOppPtTEnd = coin->fOppPtTEnd->doppelganger();
- }
- } while ((coin = coin->fNext));
- coin = fHead;
SkCoincidentSpans** priorPtr = &fHead;
do {
- if (coin->fCoinPtTStart == coin->fCoinPtTEnd) {
+ if (coin->coinPtTStart() == coin->coinPtTEnd()) {
return false;
}
- if (coin->fOppPtTStart == coin->fOppPtTEnd) {
+ if (coin->oppPtTStart() == coin->oppPtTEnd()) {
return false;
}
- if (coin->fCoinPtTStart->collapsed(coin->fCoinPtTEnd)
- || coin->fOppPtTStart->collapsed(coin->fOppPtTEnd)) {
- *priorPtr = coin->fNext;
+ if (coin->coinPtTStart()->collapsed(coin->coinPtTEnd())) {
+ *priorPtr = coin->next();
continue;
}
- priorPtr = &coin->fNext;
- } while ((coin = coin->fNext));
+ if (coin->oppPtTStart()->collapsed(coin->oppPtTEnd())) {
+ *priorPtr = coin->next();
+ continue;
+ }
+ priorPtr = coin->nextPtr();
+ } while ((coin = coin->next()));
return true;
}
-void SkOpCoincidence::fixUp(SkOpPtT* deleted, SkOpPtT* kept) {
- SkCoincidentSpans* coin = fHead;
- if (!coin) {
- return;
+void SkOpCoincidence::fixUp(SkOpPtT* deleted, const SkOpPtT* kept) {
+ SkASSERT(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->fCoinPtTStart == deleted) {
- if (coin->fCoinPtTEnd->span() == kept->span()) {
- this->release(coin);
+ if (coin->coinPtTStart() == deleted) {
+ if (coin->coinPtTEnd()->span() == kept->span()) {
+ this->release(head, coin);
continue;
}
- coin->fCoinPtTStart = kept;
+ coin->setCoinPtTStart(kept);
}
- if (coin->fCoinPtTEnd == deleted) {
- if (coin->fCoinPtTStart->span() == kept->span()) {
- this->release(coin);
+ if (coin->coinPtTEnd() == deleted) {
+ if (coin->coinPtTStart()->span() == kept->span()) {
+ this->release(head, coin);
continue;
}
- coin->fCoinPtTEnd = kept;
- }
- if (coin->fOppPtTStart == deleted) {
- if (coin->fOppPtTEnd->span() == kept->span()) {
- this->release(coin);
+ coin->setCoinPtTEnd(kept);
+ }
+ if (coin->oppPtTStart() == deleted) {
+ if (coin->oppPtTEnd()->span() == kept->span()) {
+ this->release(head, coin);
continue;
}
- coin->fOppPtTStart = kept;
+ coin->setOppPtTStart(kept);
}
- if (coin->fOppPtTEnd == deleted) {
- if (coin->fOppPtTStart->span() == kept->span()) {
- this->release(coin);
+ if (coin->oppPtTEnd() == deleted) {
+ if (coin->oppPtTStart()->span() == kept->span()) {
+ this->release(head, coin);
continue;
}
- coin->fOppPtTEnd = kept;
+ coin->setOppPtTEnd(kept);
}
- } while ((coin = coin->fNext));
+ } 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;
@@ -663,44 +1335,87 @@ bool SkOpCoincidence::mark() {
return true;
}
do {
- SkOpSpanBase* end = coin->fCoinPtTEnd->span();
- if (end->deleted()) {
- return false;
- }
- SkOpSpanBase* oldEnd = end;
- SkOpSpan* start = coin->fCoinPtTStart->span()->starter(&end);
- SkOpSpanBase* oEnd = coin->fOppPtTEnd->span();
- if (oEnd->deleted()) {
- return false;
- }
- SkOpSpanBase* oOldEnd = oEnd;
- SkOpSpanBase* oStart = coin->fOppPtTStart->span()->starter(&oEnd);
- bool flipped = (end == oldEnd) != (oEnd == oOldEnd);
+ SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast();
+ SkASSERT(!start->deleted());
+ SkOpSpanBase* end = coin->coinPtTEndWritable()->span();
+ SkASSERT(!end->deleted());
+ SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span();
+ SkASSERT(!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;
- do {
- next = next->upCast()->next();
- oNext = flipped ? oNext->prev() : oNext->upCast()->next();
- if (next == end || oNext == oEnd) {
- break;
+ while ((next = next->upCast()->next()) != end) {
+ if (!next->upCast()->insertCoincidence(oSegment, flipped)) {
+ return false;
}
- if (!next->containsCoinEnd(oNext)) {
- next->insertCoinEnd(oNext);
+ }
+ while ((oNext = oNext->upCast()->next()) != oEnd) {
+ if (!oNext->upCast()->insertCoincidence(segment, flipped)) {
+ return false;
}
- SkOpSpan* nextSpan = next->upCast();
- SkOpSpan* oNextSpan = oNext->upCast();
- if (!nextSpan->containsCoincidence(oNextSpan)) {
- nextSpan->insertCoincidence(oNextSpan);
+ }
+ } 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();
}
- } while (true);
- } while ((coin = coin->fNext));
+ 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,
+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));
@@ -708,8 +1423,24 @@ bool SkOpCoincidence::overlap(const SkOpPtT* coin1s, const SkOpPtT* coin1e,
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->fCoinPtTStart->segment(), 120000); // FIXME: replace with tuned
+ testE->span(), outer->coinPtTStart()->segment());
}
« src/pathops/SkDQuadLineIntersection.cpp ('K') | « src/pathops/SkOpCoincidence.h ('k') | src/pathops/SkOpContour.h » ('j') | src/pathops/SkPathOpsCurve.h » ('J')

Powered by Google App Engine
This is Rietveld 408576698