From 81a478ca6c36aac3e53ce0373a281ac8940f4780 Mon Sep 17 00:00:00 2001 From: caryclark Date: Fri, 9 Sep 2016 09:37:57 -0700 Subject: [PATCH] Skip adding coincident edges found during curve intersection if their ends are nearly the same. Loosen conic/line intersection point check. Detect when coincident points are unordered. This means that points a/b/c on one curve may appear in b/c/a order on the opposite curve. Restructure addMissing to return success and return if a coincidence was added as a parameter. With this, tiger part a works. Tiger part b exposes bugs around tight quads that are nearly coincident with themselves, and are coincident with something else. The greedy coicident matcher may cause the point order to be out of sync. Still working out what to do in this case. TBR=reed@google.com GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2321773002 Review-Url: https://codereview.chromium.org/2321773002 --- src/pathops/SkAddIntersections.cpp | 10 +- src/pathops/SkDConicLineIntersection.cpp | 2 +- src/pathops/SkOpCoincidence.cpp | 151 ++- src/pathops/SkOpCoincidence.h | 28 +- src/pathops/SkOpSpan.cpp | 20 +- src/pathops/SkOpSpan.h | 6 +- src/pathops/SkPathOpsCommon.cpp | 16 +- src/pathops/SkPathOpsDebug.cpp | 29 +- src/pathops/SkPathOpsDebug.h | 2 +- src/pathops/SkPathOpsSimplify.cpp | 5 +- tests/PathOpsSimplifyTest.cpp | 81 +- tools/pathops_sorter.htm | 12 +- tools/pathops_visualizer.htm | 2090 +----------------------------- 13 files changed, 263 insertions(+), 2189 deletions(-) diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index 04f5bc3..2abf67a 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -510,7 +510,7 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coinc SkOpPtT* nextTAt = wn.segment()->addT(ts[!swap][pt]); if (!testTAt->contains(nextTAt)) { SkOpPtT* oppPrev = testTAt->oppPrev(nextTAt); // Returns nullptr if pair - if (oppPrev) { // already shares a pt-t loop. + if (oppPrev) { // already share a pt-t loop. testTAt->span()->mergeMatches(nextTAt->span()); testTAt->addOpp(nextTAt, oppPrev); } @@ -543,6 +543,14 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coinc SkTSwap(testTAt, nextTAt); } SkASSERT(coinPtT[0]->span()->t() < testTAt->span()->t()); + if (coinPtT[0]->span()->deleted()) { + coinIndex = -1; + continue; + } + if (testTAt->span()->deleted()) { + coinIndex = -1; + continue; + } coincidence->add(coinPtT[0], testTAt, coinPtT[1], nextTAt); wt.segment()->debugValidate(); wn.segment()->debugValidate(); diff --git a/src/pathops/SkDConicLineIntersection.cpp b/src/pathops/SkDConicLineIntersection.cpp index b3c120d..3bca611 100644 --- a/src/pathops/SkDConicLineIntersection.cpp +++ b/src/pathops/SkDConicLineIntersection.cpp @@ -109,7 +109,7 @@ public: || !fIntersections->debugGlobalState()->debugSkipAssert()) { SkDEBUGCODE(SkDPoint conicPt = fConic.ptAtT(conicT)); SkDEBUGCODE(SkDPoint linePt = fLine->ptAtT(lineT)); - SkASSERT(conicPt.approximatelyEqual(linePt)); + SkASSERT(conicPt.approximatelyDEqual(linePt)); } #endif SkDPoint pt; diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp index b0cb243..c7a39fc 100755 --- a/src/pathops/SkOpCoincidence.cpp +++ b/src/pathops/SkOpCoincidence.cpp @@ -146,6 +146,37 @@ int SkCoincidentSpans::spanCount() const { return coinIntervals == oppIntervals ? coinIntervals : -1; } +// A coincident span is unordered if the pairs of points in the main and opposite curves' +// t values do not ascend or descend. For instance, if a tightly arced quadratic is +// coincident with another curve, it may intersect it out of order. +bool SkCoincidentSpans::ordered() const { + const SkOpSpanBase* start = this->coinPtTStart()->span(); + const SkOpSpanBase* end = this->coinPtTEnd()->span(); + const SkOpSpanBase* next = start->upCast()->next(); + if (next == end) { + return true; + } + bool flipped = this->flipped(); + const SkOpSegment* oppSeg = this->oppPtTStart()->segment(); + double oppLastT = fOppPtTStart->fT; + do { + const SkOpPtT* opp = next->contains(oppSeg); + if (!opp) { + SkASSERT(0); // may assert if coincident span isn't fully processed + continue; + } + if ((oppLastT > opp->fT) != flipped) { + return false; + } + oppLastT = opp->fT; + if (next == end) { + break; + } + next = next->upCast()->next(); + } while (true); + return true; +} + // returns true if the point is on a coincident edge, and if it is the start of that edge bool SkOpCoincidence::edge(const SkOpPtT* test, bool* start) const { SkCoincidentSpans* coinRec = fHead; @@ -324,8 +355,8 @@ bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* SkTSwap(coinTs, coinTe); SkTSwap(oppTs, oppTe); } - if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe - SkDEBUGPARAMS(true) /* do assert if addOrOverlap fails */ )) { + bool added; + if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &added)) { return false; } } @@ -606,7 +637,7 @@ bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check, double oCheckTe = check->oppPtTEnd()->fT; if (swapOpp) { if (oCheckTs <= oCheckTe) { - return false; + return false; } SkTSwap(oCheckTs, oCheckTe); } @@ -616,8 +647,8 @@ bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check, } bool coinInside = coinTe <= checkTe && coinTs >= checkTs; bool oppInside = oppTe <= oCheckTe && oppTs >= oCheckTs; - if (coinInside && oppInside) { - return false; // complete overlap, already included, do nothing + if (coinInside && oppInside) { // already included, do nothing + return false; } *overlaps->append() = check; // partial overlap, extend existing entry } while ((check = check->next())); @@ -627,7 +658,7 @@ bool SkOpCoincidence::checkOverlap(SkCoincidentSpans* check, /* 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 + double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, bool* added SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)) { SkASSERT(tStart < tEnd); SkASSERT(over1s->fT < over1e->fT); @@ -646,35 +677,33 @@ bool SkOpCoincidence::addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s, coinTs = TRange(over1s, tStart, coinSeg SkDEBUGPARAMS(over1e)); coinTe = TRange(over1s, tEnd, coinSeg SkDEBUGPARAMS(over1e)); if (coinSeg->collapsed(coinTs, coinTe)) { - return false; + return true; } oppTs = TRange(over2s, tStart, oppSeg SkDEBUGPARAMS(over2e)); oppTe = TRange(over2s, tEnd, oppSeg SkDEBUGPARAMS(over2e)); if (oppSeg->collapsed(oppTs, oppTe)) { - return false; + return true; } 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 */ ); + return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added); } /* Please keep this in sync with debugAddOrOverlap() */ // If this is called by addEndMovedSpans(), a returned false propogates out to an abort. // If this is called by AddIfMissing(), a returned false indicates there was nothing to add bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, - double coinTs, double coinTe, double oppTs, double oppTe - SkDEBUGPARAMS(bool callerAborts)) { + double coinTs, double coinTe, double oppTs, double oppTe, bool* added) { SkTDArray overlaps; - RETURN_FALSE_IF(callerAborts, !fTop); + FAIL_IF(!fTop); if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { - return false; + return true; } if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { - return false; + return true; } SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps before continuing @@ -701,28 +730,32 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, } 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); + if (overlap && cs && ce && overlap->contains(cs, ce)) { + return true; + } + FAIL_IF(cs == ce && cs); const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); - RETURN_FALSE_IF(callerAborts, overlap && os && oe && overlap->contains(os, oe)); + if (overlap && os && oe && overlap->contains(os, oe)) { + return true; + } SkASSERT(!cs || !cs->deleted()); SkASSERT(!os || !os->deleted()); SkASSERT(!ce || !ce->deleted()); SkASSERT(!oe || !oe->deleted()); const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullptr; const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullptr; - RETURN_FALSE_IF(callerAborts, csExisting && csExisting == ceExisting); - RETURN_FALSE_IF(callerAborts, csExisting && (csExisting == ce || + FAIL_IF(csExisting && csExisting == ceExisting); + FAIL_IF(csExisting && (csExisting == ce || csExisting->contains(ceExisting ? ceExisting : ce))); - RETURN_FALSE_IF(callerAborts, ceExisting && (ceExisting == cs || + FAIL_IF(ceExisting && (ceExisting == cs || ceExisting->contains(csExisting ? csExisting : cs))); const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr; const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr; - RETURN_FALSE_IF(callerAborts, osExisting && osExisting == oeExisting); - RETURN_FALSE_IF(callerAborts, osExisting && (osExisting == oe || + FAIL_IF(osExisting && osExisting == oeExisting); + FAIL_IF(osExisting && (osExisting == oe || osExisting->contains(oeExisting ? oeExisting : oe))); - RETURN_FALSE_IF(callerAborts, oeExisting && (oeExisting == os || + FAIL_IF(oeExisting && (oeExisting == os || oeExisting->contains(osExisting ? osExisting : os))); // extra line in debug code this->debugValidate(); @@ -731,11 +764,11 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, : coinSeg->addT(coinTs); SkOpPtT* osWritable = os ? const_cast(os) : oppSeg->addT(oppTs); - RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable); + FAIL_IF(!csWritable || !osWritable); csWritable->span()->addOpp(osWritable->span()); cs = csWritable; os = osWritable->active(); - RETURN_FALSE_IF(callerAborts, (ce && ce->deleted()) || (oe && oe->deleted())); + FAIL_IF((ce && ce->deleted()) || (oe && oe->deleted())); } if (!ce || !oe) { SkOpPtT* ceWritable = ce ? const_cast(ce) @@ -747,11 +780,11 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, 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)); + FAIL_IF(cs->deleted()); + FAIL_IF(os->deleted()); + FAIL_IF(ce->deleted()); + FAIL_IF(oe->deleted()); + FAIL_IF(cs->contains(ce) || os->contains(oe)); bool result = true; if (overlap) { if (overlap->coinPtTStart()->segment() == coinSeg) { @@ -775,19 +808,22 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, #endif } this->debugValidate(); - return result; + if (result) { + *added = true; + } + return true; } // Please keep this in sync with debugAddMissing() /* detects overlaps of different coincident runs on same segment */ /* does not detect overlaps for pairs without any segments in common */ // returns true if caller should loop again -bool SkOpCoincidence::addMissing() { +bool SkOpCoincidence::addMissing(bool* added) { SkCoincidentSpans* outer = fHead; + *added = false; if (!outer) { - return false; + return true; } - bool added = false; fTop = outer; fHead = nullptr; do { @@ -800,7 +836,7 @@ bool SkOpCoincidence::addMissing() { SkASSERT(!outerCoin->done()); // if it's done, should have already been removed from list const SkOpPtT* oos = outer->oppPtTStart(); if (oos->deleted()) { - return false; + return true; } const SkOpSegment* outerOpp = oos->segment(); SkASSERT(!outerOpp->done()); @@ -823,13 +859,13 @@ bool SkOpCoincidence::addMissing() { if (outerCoin == innerCoin) { const SkOpPtT* oce = outer->coinPtTEnd(); if (oce->deleted()) { - return false; + return true; } 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 + (void) this->addIfMissing(ocs->starter(oce), ics->starter(ice), + overS, overE, outerOppWritable, innerOppWritable, added SkDEBUGPARAMS(ocs->debugEnder(oce)) SkDEBUGPARAMS(ics->debugEnder(ice))); } @@ -839,8 +875,8 @@ bool SkOpCoincidence::addMissing() { 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 + (void) this->addIfMissing(ocs->starter(oce), ios->starter(ioe), + overS, overE, outerOppWritable, innerCoinWritable, added SkDEBUGPARAMS(ocs->debugEnder(oce)) SkDEBUGPARAMS(ios->debugEnder(ioe))); } @@ -851,8 +887,8 @@ bool SkOpCoincidence::addMissing() { 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 + (void) this->addIfMissing(oos->starter(ooe), ics->starter(ice), + overS, overE, outerCoinWritable, innerOppWritable, added SkDEBUGPARAMS(oos->debugEnder(ooe)) SkDEBUGPARAMS(ics->debugEnder(ice))); } @@ -861,12 +897,12 @@ bool SkOpCoincidence::addMissing() { SkASSERT(!ooe->deleted()); const SkOpPtT* ioe = inner->oppPtTEnd(); if (ioe->deleted()) { - return false; + return true; } 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 + (void) this->addIfMissing(oos->starter(ooe), ios->starter(ioe), + overS, overE, outerCoinWritable, innerCoinWritable, added SkDEBUGPARAMS(oos->debugEnder(ooe)) SkDEBUGPARAMS(ios->debugEnder(ioe))); } @@ -875,7 +911,7 @@ bool SkOpCoincidence::addMissing() { } } while ((outer = outer->next())); this->restoreHead(); - return added; + return true; } bool SkOpCoincidence::addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o, @@ -1455,17 +1491,13 @@ bool SkOpCoincidence::mark() { return true; } do { - if (!coin->coinPtTStartWritable()->span()->upCastable()) { - return false; - } + FAIL_IF(!coin->coinPtTStartWritable()->span()->upCastable()); SkOpSpan* start = coin->coinPtTStartWritable()->span()->upCast(); SkASSERT(!start->deleted()); SkOpSpanBase* end = coin->coinPtTEndWritable()->span(); SkASSERT(!end->deleted()); SkOpSpanBase* oStart = coin->oppPtTStartWritable()->span(); - if (oStart->deleted()) { - return false; - } + FAIL_IF(oStart->deleted()); SkOpSpanBase* oEnd = coin->oppPtTEndWritable()->span(); SkASSERT(!oEnd->deleted()); bool flipped = coin->flipped(); @@ -1480,19 +1512,16 @@ bool SkOpCoincidence::mark() { const SkOpSegment* oSegment = oStart->segment(); SkOpSpanBase* next = start; SkOpSpanBase* oNext = oStart; + bool ordered = coin->ordered(); while ((next = next->upCast()->next()) != end) { - if (!next->upCastable()) { - return false; - } - if (!next->upCast()->insertCoincidence(oSegment, flipped)) { + FAIL_IF(!next->upCastable()); + if (!next->upCast()->insertCoincidence(oSegment, flipped, ordered)) { return false; } } while ((oNext = oNext->upCast()->next()) != oEnd) { - if (!oNext->upCastable()) { - return false; - } - if (!oNext->upCast()->insertCoincidence(segment, flipped)) { + FAIL_IF(!oNext->upCastable()); + if (!oNext->upCast()->insertCoincidence(segment, flipped, ordered)) { return false; } } diff --git a/src/pathops/SkOpCoincidence.h b/src/pathops/SkOpCoincidence.h index e399ee2..fbd6686 100644 --- a/src/pathops/SkOpCoincidence.h +++ b/src/pathops/SkOpCoincidence.h @@ -56,15 +56,16 @@ public: SkDEBUGCODE(fGlobalState = globalState); } + SkCoincidentSpans* next() { return fNext; } + const SkCoincidentSpans* next() const { return fNext; } + SkCoincidentSpans** nextPtr() { return &fNext; } const SkOpPtT* oppPtTStart() const { return fOppPtTStart; } const SkOpPtT* oppPtTEnd() const { return fOppPtTEnd; } // These return non-const pointers so that, as copies, they can be added // to a new span pair SkOpPtT* oppPtTStartWritable() const { return const_cast(fOppPtTStart); } SkOpPtT* oppPtTEndWritable() const { return const_cast(fOppPtTEnd); } - SkCoincidentSpans* next() { return fNext; } - const SkCoincidentSpans* next() const { return fNext; } - SkCoincidentSpans** nextPtr() { return &fNext; } + bool ordered() const; int spanCount() const; void set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, @@ -118,6 +119,7 @@ public: bool startEquals(const SkOpSpanBase* outer, const SkOpSpanBase* over) const { return fCoinPtTStart->span() == over && fOppPtTStart->span() == outer; } + private: SkCoincidentSpans* fNext; const SkOpPtT* fCoinPtTStart; @@ -146,7 +148,7 @@ public: SkOpPtT* oppPtTEnd); bool addEndMovedSpans(); bool addExpanded(); - bool addMissing(); + bool addMissing(bool* added); bool addUncommon(); bool apply(); bool contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, @@ -155,10 +157,11 @@ public: #if DEBUG_COINCIDENCE_VERBOSE void debugAddExpanded(const char* id, SkPathOpsDebug::GlitchLog* ) const; - void debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* ) const; + void debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* , bool* added) const; void debugAddOrOverlap(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, - double coinTs, double coinTe, double oppTs, double oppTe) const; + double coinTs, double coinTe, double oppTs, double oppTe, + bool* added) const; #endif const SkOpAngle* debugAngle(int id) const { @@ -166,7 +169,6 @@ public: } #if DEBUG_COINCIDENCE_VERBOSE - void debugCheckOverlap(const char* id, SkPathOpsDebug::GlitchLog* log) const; void debugCheckValid(const char* id, SkPathOpsDebug::GlitchLog* log) const; #endif @@ -216,6 +218,10 @@ public: return fGlobalState; } + const SkOpGlobalState* globalState() const { + return fGlobalState; + } + bool isEmpty() const { return !fHead && !fTop; } @@ -251,11 +257,11 @@ private: } bool addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s, - double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg + double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg, + bool* added SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e)); bool addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, - double coinTs, double coinTe, double oppTs, double oppTe - SkDEBUGPARAMS(bool callerAborts)); + double coinTs, double coinTe, double oppTs, double oppTe, bool* added); bool addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o, const SkOpSegment* seg2, const SkOpSegment* seg2o, const SkOpPtT* overS, const SkOpPtT* overE); @@ -275,7 +281,7 @@ private: void debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* , const SkOpPtT* over1s, const SkOpPtT* over2s, double tStart, double tEnd, - const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, + const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, bool* added, const SkOpPtT* over1e, const SkOpPtT* over2e) const; #endif void fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept); diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp index 70b47b6..26c6f25 100755 --- a/src/pathops/SkOpSpan.cpp +++ b/src/pathops/SkOpSpan.cpp @@ -459,7 +459,7 @@ void SkOpSpan::init(SkOpSegment* segment, SkOpSpan* prev, double t, const SkPoin } // Please keep this in sync with debugInsertCoincidence() -bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped) { +bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped, bool ordered) { if (this->containsCoincidence(segment)) { return true; } @@ -467,16 +467,16 @@ bool SkOpSpan::insertCoincidence(const SkOpSegment* segment, bool flipped) { while ((next = next->next()) != &fPtT) { if (next->segment() == segment) { SkOpSpan* span; - if (flipped) { - span = next->span()->prev(); - if (!span) { - return false; - } + SkOpSpanBase* base = next->span(); + if (!ordered) { + const SkOpSpanBase* spanEnd = fNext->contains(segment)->span(); + const SkOpPtT* start = base->ptT()->starter(spanEnd->ptT()); + span = const_cast(start->span()->upCast()); + } else if (flipped) { + span = base->prev(); + FAIL_IF(!span); } else { - SkOpSpanBase* base = next->span(); - if (!base->upCastable()) { - return false; - } + FAIL_IF(!base->upCastable()); span = base->upCast(); } this->insertCoincidence(span); diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h index 14bb712..4ba452b 100644 --- a/src/pathops/SkOpSpan.h +++ b/src/pathops/SkOpSpan.h @@ -426,6 +426,10 @@ public: return false; } + bool checkAlreadyAdded() const { + return fAlreadyAdded; + } + bool clearCoincident() { SkASSERT(!final()); if (fCoincident == this) { @@ -464,7 +468,7 @@ public: } void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt); - bool insertCoincidence(const SkOpSegment* , bool flipped); + bool insertCoincidence(const SkOpSegment* , bool flipped, bool ordered); // Please keep this in sync with debugInsertCoincidence() void insertCoincidence(SkOpSpan* coin) { diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index c8ee84c..34895db 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -483,7 +483,14 @@ bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidenc const int SAFETY_COUNT = 100; // FIXME: tune int safetyHatch = SAFETY_COUNT; // look for coincidence present in A-B and A-C but missing in B-C - while (coincidence->addMissing()) { + do { + bool added; + if (!coincidence->addMissing(&added)) { + return false; + } + if (!added) { + break; + } if (!--safetyHatch) { SkASSERT(globalState->debugSkipAssert()); return false; @@ -491,7 +498,7 @@ bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidenc DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing"); moveNearby(contourList); DEBUG_COINCIDENCE_HEALTH(contourList, "moveNearby"); - } + } while (true); DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2"); // FIXME: only call this if addMissing modified something when returning false moveNearby(contourList); @@ -499,7 +506,10 @@ bool HandleCoincidence(SkOpContourHead* contourList, SkOpCoincidence* coincidenc // check to see if, loosely, coincident ranges may be expanded if (coincidence->expand()) { DEBUG_COINCIDENCE_HEALTH(contourList, "expand1"); - coincidence->addMissing(); + bool added; + if (!coincidence->addMissing(&added)) { + return false; + } DEBUG_COINCIDENCE_HEALTH(contourList, "addMissing2"); if (!coincidence->addExpanded()) { return false; diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index b5b42c4..22ea12e 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -269,7 +269,8 @@ void SkPathOpsDebug::CheckHealth(SkOpContourHead* contourList, const char* id) { contour->debugMissingCoincidence(id, &glitches); } while ((contour = contour->next())); coincidence->debugRemoveCollapsed(id, &glitches); - coincidence->debugAddMissing(id, &glitches); + bool added; + coincidence->debugAddMissing(id, &glitches, &added); coincidence->debugExpand(id, &glitches); coincidence->debugAddExpanded(id, &glitches); coincidence->debugMark(id, &glitches); @@ -1393,7 +1394,7 @@ void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLo /* Commented-out lines keep this in sync addIfMissing() */ // note that over1s, over1e, over2s, over2e are ordered void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpPtT* over1s, const SkOpPtT* over2s, - double tStart, double tEnd, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, + double tStart, double tEnd, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, bool* added, const SkOpPtT* over1e, const SkOpPtT* over2e) const { SkASSERT(tStart < tEnd); SkASSERT(over1s->fT < over1e->fT); @@ -1423,7 +1424,7 @@ void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLo SkTSwap(coinTs, coinTe); SkTSwap(oppTs, oppTe); } - return this->debugAddOrOverlap(id, log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe + return this->debugAddOrOverlap(id, log, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, added ); } @@ -1432,10 +1433,11 @@ void SkOpCoincidence::debugAddIfMissing(const char* id, SkPathOpsDebug::GlitchLo // If this is called by AddIfMissing(), a returned false indicates there was nothing to add void SkOpCoincidence::debugAddOrOverlap(const char* id, SkPathOpsDebug::GlitchLog* log, const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, - double coinTs, double coinTe, double oppTs, double oppTe) const { + double coinTs, double coinTe, double oppTs, double oppTe, bool* added) const { SkTDArray overlaps; SkASSERT(!fTop); // this is (correctly) reversed in addifMissing() - if (fTop && !this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, &overlaps)) { + if (fTop && !this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe, + &overlaps)) { return; } if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, @@ -1548,7 +1550,7 @@ void SkOpCoincidence::debugAddOrOverlap(const char* id, SkPathOpsDebug::GlitchLo /* 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 -void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log) const { +void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* log, bool* added) const { const SkCoincidentSpans* outer = fHead; if (!outer) { return; @@ -1591,7 +1593,7 @@ void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* SkASSERT(!ice->deleted()); if (outerOpp != innerOpp && this->overlap(ocs, oce, ics, ice, &overS, &overE)) { this->debugAddIfMissing(id, log, ocs->starter(oce), ics->starter(ice), - overS, overE, outerOpp, innerOpp, + overS, overE, outerOpp, innerOpp, added, ocs->debugEnder(oce), ics->debugEnder(ice)); } @@ -1602,7 +1604,7 @@ void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* SkASSERT(!ioe->deleted()); if (outerOpp != innerCoin && this->overlap(ocs, oce, ios, ioe, &overS, &overE)) { this->debugAddIfMissing(id, log, ocs->starter(oce), ios->starter(ioe), - overS, overE, outerOpp, innerCoin, + overS, overE, outerOpp, innerCoin, added, ocs->debugEnder(oce), ios->debugEnder(ioe)); } @@ -1614,7 +1616,7 @@ void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* SkASSERT(outerCoin != innerOpp); if (this->overlap(oos, ooe, ics, ice, &overS, &overE)) { this->debugAddIfMissing(id, log, oos->starter(ooe), ics->starter(ice), - overS, overE, outerCoin, innerOpp, + overS, overE, outerCoin, innerOpp, added, oos->debugEnder(ooe), ics->debugEnder(ice)); } @@ -1626,7 +1628,7 @@ void SkOpCoincidence::debugAddMissing(const char* id, SkPathOpsDebug::GlitchLog* SkASSERT(outerCoin != innerCoin); if (this->overlap(oos, ooe, ios, ioe, &overS, &overE)) { this->debugAddIfMissing(id, log, oos->starter(ooe), ios->starter(ioe), - overS, overE, outerCoin, innerCoin, + overS, overE, outerCoin, innerCoin, added, oos->debugEnder(ooe), ios->debugEnder(ioe)); } @@ -1973,13 +1975,6 @@ static void DebugCheckOverlapTop(const SkCoincidentSpans* head, const SkCoincide } } -#if DEBUG_COINCIDENCE_VERBOSE -void SkOpCoincidence::debugCheckOverlap(const char* id, SkPathOpsDebug::GlitchLog* log) const { - DebugCheckOverlapTop(fHead, fTop, id, log); - DebugCheckOverlapTop(fTop, nullptr, id, log); -} -#endif - static void DebugValidate(const SkCoincidentSpans* head, const SkCoincidentSpans* opt, const char* id, SkPathOpsDebug::GlitchLog* log) { // look for pts inside coincident spans that are not inside the opposite spans diff --git a/src/pathops/SkPathOpsDebug.h b/src/pathops/SkPathOpsDebug.h index bdfd3a4..ecf2eef 100644 --- a/src/pathops/SkPathOpsDebug.h +++ b/src/pathops/SkPathOpsDebug.h @@ -78,7 +78,7 @@ #define DEBUG_ANGLE 1 #define DEBUG_ASSEMBLE 1 #define DEBUG_COINCIDENCE 01 -#define DEBUG_COINCIDENCE_ORDER 01 +#define DEBUG_COINCIDENCE_ORDER 0 // tight arc quads may generate out-of-order coincdence spans #define DEBUG_COINCIDENCE_VERBOSE 01 #define DEBUG_CUBIC_BINARY_SEARCH 0 #define DEBUG_CUBIC_SPLIT 1 diff --git a/src/pathops/SkPathOpsSimplify.cpp b/src/pathops/SkPathOpsSimplify.cpp index dcd75f1..2376e1d 100644 --- a/src/pathops/SkPathOpsSimplify.cpp +++ b/src/pathops/SkPathOpsSimplify.cpp @@ -36,7 +36,10 @@ static bool bridgeWinding(SkOpContourHead* contourList, SkPathWriter* simple, bo if (!unsortable && simple->hasMove() && current->verb() != SkPath::kLine_Verb && !simple->isClosed()) { - if (!current->addCurveTo(start, end, simple)) { + // FIXME: put in the next two lines to avoid handling already added + if (start->starter(end)->checkAlreadyAdded()) { + simple->close(); + } else if (!current->addCurveTo(start, end, simple)) { return false; } if (!simple->isClosed()) { diff --git a/tests/PathOpsSimplifyTest.cpp b/tests/PathOpsSimplifyTest.cpp index e5751aa..d91cc98 100644 --- a/tests/PathOpsSimplifyTest.cpp +++ b/tests/PathOpsSimplifyTest.cpp @@ -5256,10 +5256,85 @@ static void tiger8a_h_1(skiatest::Reporter* reporter, const char* filename) { #if DEBUG_UNDER_DEVELOPMENT // tiger return; #endif - uint64_t testlines = 0x0000001d14c14bb1; // best so far: 0x0000001d14c14bb1; + uint64_t testlines = 0x0000000a01900c00; // best so far: 0x0000001d14c14bb1; tiger8a_x(reporter, filename, testlines); } +static void tiger8b_x(skiatest::Reporter* reporter, const char* filename, uint64_t testlines) { +#if DEBUG_UNDER_DEVELOPMENT // tiger + return; +#endif + SkPath path; +uint64_t i = 0; +if (testlines & (1LL << i++)) path.moveTo(SkBits2Float(0x43f72ca1), SkBits2Float(0x43609572)); // 494.349f, 224.584f +if (testlines & (1LL << i++)) path.conicTo(SkBits2Float(0x43f72ebd), SkBits2Float(0x4360a219), SkBits2Float(0x43f7302e), SkBits2Float(0x4360af1f), SkBits2Float(0x3f7fa741)); // 494.365f, 224.633f, 494.376f, 224.684f, 0.998646f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f63333), SkBits2Float(0x4360e667)); // 492.4f, 224.9f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f63333), SkBits2Float(0x4360ca4b), SkBits2Float(0x43f6363f), SkBits2Float(0x4360aede)); // 492.4f, 224.79f, 492.424f, 224.683f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f64377), SkBits2Float(0x436037ee), SkBits2Float(0x43f679f5), SkBits2Float(0x4360016e)); // 492.527f, 224.218f, 492.953f, 224.006f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f6df06), SkBits2Float(0x435f9c5c), SkBits2Float(0x43f71db4), SkBits2Float(0x43605866)); // 493.742f, 223.611f, 494.232f, 224.345f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f722f8), SkBits2Float(0x43606830), SkBits2Float(0x43f72704), SkBits2Float(0x43607966)); // 494.273f, 224.407f, 494.305f, 224.474f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f72ae0), SkBits2Float(0x436089cd), SkBits2Float(0x43f72d8a), SkBits2Float(0x43609b1e)); // 494.335f, 224.538f, 494.356f, 224.606f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f72e8e), SkBits2Float(0x4360a1b8), SkBits2Float(0x43f72f61), SkBits2Float(0x4360a850)); // 494.364f, 224.632f, 494.37f, 224.657f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f72f68), SkBits2Float(0x4360a88a), SkBits2Float(0x43f72f83), SkBits2Float(0x4360a964)); // 494.37f, 224.658f, 494.371f, 224.662f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f72fbb), SkBits2Float(0x4360ab2a), SkBits2Float(0x43f72ff4), SkBits2Float(0x4360ad1d)); // 494.373f, 224.669f, 494.375f, 224.676f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f73000), SkBits2Float(0x4360ad83), SkBits2Float(0x43f73009), SkBits2Float(0x4360add5)); // 494.375f, 224.678f, 494.375f, 224.679f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f7300b), SkBits2Float(0x4360ade9), SkBits2Float(0x43f73022), SkBits2Float(0x4360aeb5)); // 494.375f, 224.679f, 494.376f, 224.682f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f7301f), SkBits2Float(0x4360ae97)); // 494.376f, 224.682f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f73027), SkBits2Float(0x4360aee3)); // 494.376f, 224.683f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f73028), SkBits2Float(0x4360aeeb)); // 494.376f, 224.683f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f73027), SkBits2Float(0x4360aedf)); // 494.376f, 224.683f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f73021), SkBits2Float(0x4360aeaa)); // 494.376f, 224.682f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f73016), SkBits2Float(0x4360ae50)); // 494.376f, 224.681f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f73007), SkBits2Float(0x4360adc1)); // 494.375f, 224.679f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f72ff9), SkBits2Float(0x4360ad4d)); // 494.375f, 224.677f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f7300d), SkBits2Float(0x4360adf7), SkBits2Float(0x43f73031), SkBits2Float(0x4360af12)); // 494.375f, 224.68f, 494.376f, 224.684f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f730f0), SkBits2Float(0x4360b4f1), SkBits2Float(0x43f7320a), SkBits2Float(0x4360bc94)); // 494.382f, 224.707f, 494.391f, 224.737f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f73625), SkBits2Float(0x4360d8fe), SkBits2Float(0x43f73c59), SkBits2Float(0x4360fa4a)); // 494.423f, 224.848f, 494.471f, 224.978f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f75132), SkBits2Float(0x43616a36), SkBits2Float(0x43f772ac), SkBits2Float(0x4361d738)); // 494.634f, 225.415f, 494.896f, 225.841f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f7de60), SkBits2Float(0x436335ea), SkBits2Float(0x43f89f25), SkBits2Float(0x4363e779)); // 495.737f, 227.211f, 497.243f, 227.904f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43fb3d30), SkBits2Float(0x436650a0), SkBits2Float(0x44005a14), SkBits2Float(0x43602133)); // 502.478f, 230.315f, 513.407f, 224.13f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x4400799a), SkBits2Float(0x4360ffff)); // 513.9f, 225 +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x44003ca2), SkBits2Float(0x43614dd5)); // 512.947f, 225.304f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43ff92b8), SkBits2Float(0x435ba8f8), SkBits2Float(0x43fee825), SkBits2Float(0x4353aa15)); // 511.146f, 219.66f, 509.814f, 211.664f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43ff6667), SkBits2Float(0x43537fff)); // 510.8f, 211.5f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43ffcaf2), SkBits2Float(0x43541e6d)); // 511.586f, 212.119f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43fd4888), SkBits2Float(0x435a7d38), SkBits2Float(0x43f8d864), SkBits2Float(0x435b4bbf)); // 506.567f, 218.489f, 497.691f, 219.296f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f8cccd), SkBits2Float(0x435a4ccc)); // 497.6f, 218.3f +if (testlines & (1LL << i++)) path.lineTo(SkBits2Float(0x43f8e5e7), SkBits2Float(0x435b47d3)); // 497.796f, 219.281f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f84300), SkBits2Float(0x435b88fd), SkBits2Float(0x43f7b75b), SkBits2Float(0x435c5e8e)); // 496.523f, 219.535f, 495.432f, 220.369f +if (testlines & (1LL << i++)) path.quadTo(SkBits2Float(0x43f6b984), SkBits2Float(0x435de2c4), SkBits2Float(0x43f72ca1), SkBits2Float(0x43609572)); // 493.449f, 221.886f, 494.349f, 224.584f +if (testlines & (1LL << i++)) path.close(); +testSimplify(reporter, path, filename); +} + +static void tiger8b_h(skiatest::Reporter* reporter, const char* filename) { +#if DEBUG_UNDER_DEVELOPMENT // tiger + return; +#endif + SkRandom r; + for (int samples = 2; samples < 37; ++samples) { + for (int tests = 0; tests < 10000; ++tests) { + uint64_t testlines = 0; + for (int i = 0; i < samples; ++i) { + int bit; + do { + bit = r.nextRangeU(0, 38); + } while (testlines & (1LL << bit)); + testlines |= 1LL << bit; + } + tiger8b_x(reporter, filename, testlines); + } + } +} + +static void tiger8b_h_1(skiatest::Reporter* reporter, const char* filename) { +#if DEBUG_UNDER_DEVELOPMENT // tiger + return; +#endif + uint64_t testlines = 0x0000000001000893; // best so far: 0x0000000001000893 + tiger8b_x(reporter, filename, testlines); +} + // tries to add same edge twice static void tiger8b(skiatest::Reporter* reporter, const char* filename) { #if DEBUG_UNDER_DEVELOPMENT // tiger @@ -5785,13 +5860,15 @@ static void testQuads72(skiatest::Reporter* reporter, const char* filename) { } static void (*skipTest)(skiatest::Reporter* , const char* filename) = 0; -static void (*firstTest)(skiatest::Reporter* , const char* filename) = 0; +static void (*firstTest)(skiatest::Reporter* , const char* filename) = tiger8b_h_1; static void (*stopTest)(skiatest::Reporter* , const char* filename) = 0; static TestDesc tests[] = { TEST(tiger8a_h_1), TEST(tiger8a_h), TEST(tiger8a), + TEST(tiger8b_h_1), + TEST(tiger8b_h), TEST(tiger8b), TEST(tiger8), TEST(testQuads72), diff --git a/tools/pathops_sorter.htm b/tools/pathops_sorter.htm index 58af3da..053cc10 100644 --- a/tools/pathops_sorter.htm +++ b/tools/pathops_sorter.htm @@ -6,18 +6,18 @@
-
-{{{492.424042f, 225.118027f}, {492.427094f, 225.131409f}, {492.428802f, 225.138336f}}} id=3 -{{{492.428802f, 225.138336f}, {492.423584f, 225.115952f}}} id=4 -{{{492.451324f, 225.216217f}, {492.426239f, 225.127716f}, {492.425629f, 225.125076f}}} id=1 -
+
+ {{{494.348663f, 224.583771f}, {494.37619f, 224.68309f}}} id=1 +{{{494.375671f, 224.680908f}, {494.375397f, 224.67955f}, {494.376495f, 224.683868f}}} id=3 + {{fX=494.37557983398438 fY=224.68092346191406 }, {fX=494.47489929199219 fY=224.65339660644531 }} +