diff options
author | caryclark <caryclark@google.com> | 2016-08-24 09:24:18 -0700 |
---|---|---|
committer | Commit bot <commit-bot@chromium.org> | 2016-08-24 09:24:18 -0700 |
commit | ef4f32ac858825dc443cfe4739ea878fb0bf550f (patch) | |
tree | 357340c761e3e2c0d82bc53489f0ea7b10511b95 | |
parent | ea17dfe40b04fa476008af67984b7a41dc5243f7 (diff) |
remove point aliases
This removes the notion of keeping track of every different t value
that resolves to the same or a similar point. Other fixes make
this concept unnecessary, and removing it simplifies the code.
This removes an allocation, and speeds up paths with many
overlapping curves.
As a bonus, four fuzzer tests that failed before now succeed.
TBR=reed@google.com
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2275703003
Review-Url: https://codereview.chromium.org/2275703003
-rw-r--r-- | src/pathops/SkAddIntersections.cpp | 6 | ||||
-rwxr-xr-x | src/pathops/SkOpCoincidence.cpp | 10 | ||||
-rw-r--r-- | src/pathops/SkOpSegment.cpp | 30 | ||||
-rw-r--r-- | src/pathops/SkOpSegment.h | 13 | ||||
-rwxr-xr-x | src/pathops/SkOpSpan.cpp | 2 | ||||
-rw-r--r-- | src/pathops/SkOpSpan.h | 6 | ||||
-rw-r--r-- | src/pathops/SkPathOpsDebug.cpp | 30 | ||||
-rw-r--r-- | tests/PathOpsAngleTest.cpp | 4 | ||||
-rw-r--r-- | tests/PathOpsOpTest.cpp | 8 |
9 files changed, 34 insertions, 75 deletions
diff --git a/src/pathops/SkAddIntersections.cpp b/src/pathops/SkAddIntersections.cpp index 1ca56b8f23..a6cebca4b8 100644 --- a/src/pathops/SkAddIntersections.cpp +++ b/src/pathops/SkAddIntersections.cpp @@ -505,11 +505,9 @@ bool AddIntersectTs(SkOpContour* test, SkOpContour* next, SkOpCoincidence* coinc SkASSERT(ts[0][pt] >= 0 && ts[0][pt] <= 1); SkASSERT(ts[1][pt] >= 0 && ts[1][pt] <= 1); wt.segment()->debugValidate(); - SkOpPtT* testTAt = wt.segment()->addT(ts[swap][pt], SkOpSegment::kAllowAliasMatch, - nullptr); + SkOpPtT* testTAt = wt.segment()->addT(ts[swap][pt], nullptr); wn.segment()->debugValidate(); - SkOpPtT* nextTAt = wn.segment()->addT(ts[!swap][pt], SkOpSegment::kAllowAliasMatch, - nullptr); + SkOpPtT* nextTAt = wn.segment()->addT(ts[!swap][pt], nullptr); if (testTAt->addOpp(nextTAt)) { testTAt->span()->checkForCollapsedCoincidence(); } diff --git a/src/pathops/SkOpCoincidence.cpp b/src/pathops/SkOpCoincidence.cpp index ea84e04e01..84c4003968 100755 --- a/src/pathops/SkOpCoincidence.cpp +++ b/src/pathops/SkOpCoincidence.cpp @@ -305,7 +305,7 @@ bool SkOpCoincidence::addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* continue; } SkOpSegment* writableSeg = const_cast<SkOpSegment*>(testSeg); - SkOpPtT* oppStart = writableSeg->addT(t, SkOpSegment::kAllowAliasMatch, nullptr); + SkOpPtT* oppStart = writableSeg->addT(t, nullptr); SkOpSpan* writableBase = const_cast<SkOpSpan*>(base); oppStart->span()->addOppAndMerge(writableBase); if (oppStart->deleted()) { @@ -691,9 +691,9 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, this->debugValidate(); if (!cs || !os) { SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs) - : coinSeg->addT(coinTs, SkOpSegment::kNoAliasMatch, nullptr); + : coinSeg->addT(coinTs, nullptr); SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) - : oppSeg->addT(oppTs, SkOpSegment::kNoAliasMatch, nullptr); + : oppSeg->addT(oppTs, nullptr); if (!csWritable || !osWritable) { return false; } @@ -706,9 +706,9 @@ bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, } if (!ce || !oe) { SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce) - : coinSeg->addT(coinTe, SkOpSegment::kNoAliasMatch, nullptr); + : coinSeg->addT(coinTe, nullptr); SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe) - : oppSeg->addT(oppTe, SkOpSegment::kNoAliasMatch, nullptr); + : oppSeg->addT(oppTe, nullptr); ceWritable->span()->addOppAndMerge(oeWritable->span()); ce = ceWritable; oe = oeWritable; diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index de74f7d557..20f0013230 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -229,7 +229,7 @@ const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const { if (testPtT->fT == t) { break; } - if (!this->match(testPtT, this, t, pt, opp ? kAllowAliasMatch : kNoAliasMatch)) { + if (!this->match(testPtT, this, t, pt)) { if (t < testPtT->fT) { return nullptr; } @@ -256,7 +256,7 @@ bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* start if (this->contains(newT)) { return true; } - SkOpPtT* newPtT = this->addT(newT, kAllowAliasMatch, startOver); + SkOpPtT* newPtT = this->addT(newT, startOver); if (!newPtT) { return false; } @@ -270,7 +270,7 @@ bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* start } // Please keep this in sync with debugAddT() -SkOpPtT* SkOpSegment::addT(double t, AliasMatch allowAlias, bool* allocated) { +SkOpPtT* SkOpSegment::addT(double t, bool* allocated) { debugValidate(); SkPoint pt = this->ptAtT(t); SkOpSpanBase* span = &fHead; @@ -281,7 +281,7 @@ SkOpPtT* SkOpSegment::addT(double t, AliasMatch allowAlias, bool* allocated) { if (t == result->fT) { goto bumpSpan; } - if (this->match(result, this, t, pt, allowAlias)) { + if (this->match(result, this, t, pt)) { // see if any existing alias matches segment, pt, and t loop = result->next(); duplicatePt = false; @@ -293,25 +293,9 @@ SkOpPtT* SkOpSegment::addT(double t, AliasMatch allowAlias, bool* allocated) { duplicatePt |= ptMatch; loop = loop->next(); } - if (kNoAliasMatch == allowAlias) { bumpSpan: - span->bumpSpanAdds(); - return result; - } - SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(this->globalState()->allocator()); - alias->init(result->span(), t, pt, duplicatePt); - result->insert(alias); - result->span()->unaligned(); - this->debugValidate(); -#if DEBUG_ADD_T - SkDebugf("%s alias t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, - alias->segment()->debugID(), alias->span()->debugID()); -#endif span->bumpSpanAdds(); - if (allocated) { - *allocated = true; - } - return alias; + return result; } if (t < result->fT) { SkOpSpan* prev = result->span()->prev(); @@ -1051,7 +1035,7 @@ bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { } bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT, - const SkPoint& testPt, AliasMatch aliasMatch) const { + const SkPoint& testPt) const { SkASSERT(this == base->segment()); if (this == testParent) { if (precisely_equal(base->fT, testT)) { @@ -1421,7 +1405,7 @@ nextRef: } while ((ref = ref->next()) != refHead); doneCheckingDistance: return checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT, - checkBest->fPt, kAllowAliasMatch); + checkBest->fPt); } // Please keep this function in sync with debugMoveNearby() diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index 89af5a10fc..61a9e45ac8 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -23,11 +23,6 @@ class SkPathWriter; class SkOpSegment { public: - enum AliasMatch { - kNoAliasMatch, - kAllowAliasMatch, - }; - bool operator<(const SkOpSegment& rh) const { return fBounds.fTop < rh.fBounds.fTop; } @@ -97,7 +92,7 @@ public: return this; } - SkOpPtT* addT(double t, AliasMatch, bool* allocated); + SkOpPtT* addT(double t, bool* allocated); template<typename T> T* allocateArray(int count) { return SkOpTAllocator<T>::AllocateArray(this->globalState()->allocator(), count); @@ -133,7 +128,7 @@ public: } void debugAddAngle(double startT, double endT); - const SkOpPtT* debugAddT(double t, AliasMatch , bool* allocated) const; + const SkOpPtT* debugAddT(double t, bool* allocated) const; const SkOpAngle* debugAngle(int id) const; #if DEBUG_ANGLE void debugCheckAngleCoin() const; @@ -279,8 +274,7 @@ public: void markDone(SkOpSpan* ); bool markWinding(SkOpSpan* , int winding); bool markWinding(SkOpSpan* , int winding, int oppWinding); - bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt, - AliasMatch ) const; + bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const; bool missingCoincidence(); bool moveMultiples(); void moveNearby(); @@ -397,7 +391,6 @@ public: const SkOpSpanBase* spanBase, const SkOpSegment* opp) const; void undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end); - bool uniqueT(double t, AliasMatch allowAlias) const; int updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const; int updateOppWinding(const SkOpAngle* angle) const; int updateOppWindingReverse(const SkOpAngle* angle) const; diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp index 8937bdd5bb..640ba8feb7 100755 --- a/src/pathops/SkOpSpan.cpp +++ b/src/pathops/SkOpSpan.cpp @@ -238,7 +238,7 @@ void SkOpSpanBase::mergeContained(const SkPathOpsBounds& bounds) { bool SkOpSpanBase::contains(const SkOpSpanBase* span) const { const SkOpPtT* start = &fPtT; const SkOpPtT* check = &span->fPtT; - SkASSERT(start != check); + SkOPASSERT(start != check); const SkOpPtT* walk = start; while ((walk = walk->next()) != start) { if (walk == check) { diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h index 9e91f154ae..aff3646190 100644 --- a/src/pathops/SkOpSpan.h +++ b/src/pathops/SkOpSpan.h @@ -369,7 +369,7 @@ public: } const SkOpSpan* upCast() const { - SkASSERT(!final()); + SkOPASSERT(!final()); return (const SkOpSpan*) this; } @@ -520,7 +520,7 @@ public: SkASSERT(!final()); SkASSERT(windValue >= 0); SkASSERT(fWindSum == SK_MinS32); - SkASSERT(!windValue || !fDone); + SkOPASSERT(!windValue || !fDone); fWindValue = windValue; } @@ -537,7 +537,7 @@ public: } int windValue() const { - SkASSERT(!final()); + SkOPASSERT(!final()); return fWindValue; } diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index b839feeadb..4d833a0b84 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -582,7 +582,7 @@ void SkDRect::debugInit() { #if DEBUG_COINCIDENCE // commented-out lines keep this in sync with addT() - const SkOpPtT* SkOpSegment::debugAddT(double t, AliasMatch allowAlias, bool* allocated) const { + const SkOpPtT* SkOpSegment::debugAddT(double t, bool* allocated) const { debugValidate(); SkPoint pt = this->ptAtT(t); const SkOpSpanBase* span = &fHead; @@ -593,7 +593,7 @@ void SkDRect::debugInit() { if (t == result->fT) { goto bumpSpan; } - if (this->match(result, this, t, pt, allowAlias)) { + if (this->match(result, this, t, pt)) { // see if any existing alias matches segment, pt, and t loop = result->next(); duplicatePt = false; @@ -605,25 +605,9 @@ void SkDRect::debugInit() { duplicatePt |= ptMatch; loop = loop->next(); } - if (kNoAliasMatch == allowAlias) { bumpSpan: -// span->bumpSpanAdds(); - return result; - } -// SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator); -// alias->init(result->span(), t, pt, duplicatePt); -// result->insert(alias); -// result->span()->unaligned(); - this->debugValidate(); -// #if DEBUG_ADD_T -// SkDebugf("%s alias t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, -// alias->segment()->debugID(), alias->span()->debugID()); -// #endif // span->bumpSpanAdds(); - if (allocated) { - *allocated = true; - } - return nullptr; + return result; } if (t < result->fT) { const SkOpSpan* prev = result->span()->prev(); @@ -1488,9 +1472,9 @@ void SkOpCoincidence::debugAddOrOverlap(const SkOpSegment* coinSeg, const SkOpSe this->debugValidate(); if (!cs || !os) { if (!cs) - cs = coinSeg->debugAddT(coinTs, SkOpSegment::kNoAliasMatch, nullptr); + cs = coinSeg->debugAddT(coinTs, nullptr); if (!os) - os = oppSeg->debugAddT(oppTs, SkOpSegment::kNoAliasMatch, nullptr); + os = oppSeg->debugAddT(oppTs, nullptr); if (cs && os) cs->span()->debugAddOppAndMerge(id, log, os->span(), &csDeleted, &osDeleted); // cs = csWritable; // os = osWritable; @@ -1500,9 +1484,9 @@ void SkOpCoincidence::debugAddOrOverlap(const SkOpSegment* coinSeg, const SkOpSe } if (!ce || !oe) { if (!ce) - ce = coinSeg->debugAddT(coinTe, SkOpSegment::kNoAliasMatch, nullptr); + ce = coinSeg->debugAddT(coinTe, nullptr); if (!oe) - oe = oppSeg->debugAddT(oppTe, SkOpSegment::kNoAliasMatch, nullptr); + oe = oppSeg->debugAddT(oppTe, nullptr); if (ce && oe) ce->span()->debugAddOppAndMerge(id, log, oe->span(), &ceDeleted, &oeDeleted); // ce = ceWritable; // oe = oeWritable; diff --git a/tests/PathOpsAngleTest.cpp b/tests/PathOpsAngleTest.cpp index fa8d31469b..12d1d5579a 100644 --- a/tests/PathOpsAngleTest.cpp +++ b/tests/PathOpsAngleTest.cpp @@ -478,9 +478,9 @@ DEF_TEST(PathOpsAngleAfter, reporter) { void SkOpSegment::debugAddAngle(double startT, double endT) { SkOpPtT* startPtT = startT == 0 ? fHead.ptT() : startT == 1 ? fTail.ptT() - : this->addT(startT, kNoAliasMatch, nullptr); + : this->addT(startT, nullptr); SkOpPtT* endPtT = endT == 0 ? fHead.ptT() : endT == 1 ? fTail.ptT() - : this->addT(endT, kNoAliasMatch, nullptr); + : this->addT(endT, nullptr); SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(this->globalState()->allocator()); SkOpSpanBase* startSpan = &fHead; while (startSpan->ptT() != startPtT) { diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index 759b3bcae3..d659e8863e 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -6822,7 +6822,7 @@ path.conicTo(SkBits2Float(0x084b0321), SkBits2Float(0x6ac07b2a), SkBits2Float(0x path.lineTo(SkBits2Float(0x8c558c55), SkBits2Float(0x212a1f2a)); // -1.64512e-31f, 5.76395e-19f SkPath path2(path); - testPathOpFailSkipAssert(reporter, path1, path2, (SkPathOp) 0, filename); + testPathOpSkipAssert(reporter, path1, path2, (SkPathOp) 0, filename); } static void fuzz763_17(skiatest::Reporter* reporter, const char* filename) { @@ -6976,7 +6976,7 @@ path.lineTo(SkBits2Float(0x68395b2d), SkBits2Float(0xf0682955)); // 3.50128e+24 path.close(); SkPath path2(path); - testPathOpFailSkipAssert(reporter, path1, path2, (SkPathOp) 0, filename); + testPathOpSkipAssert(reporter, path1, path2, (SkPathOp) 0, filename); } static void fuzz763_20(skiatest::Reporter* reporter, const char* filename) { @@ -7276,7 +7276,7 @@ path.lineTo(SkBits2Float(0x68385b2d), SkBits2Float(0xf0682955)); // 3.48239e+24 path.close(); SkPath path2(path); - testPathOpFailSkipAssert(reporter, path1, path2, (SkPathOp) 0, filename); + testPathOpSkipAssert(reporter, path1, path2, (SkPathOp) 0, filename); } static void fuzz763_28(skiatest::Reporter* reporter, const char* filename) { @@ -7314,7 +7314,7 @@ path.moveTo(SkBits2Float(0x0321081f), SkBits2Float(0x6a4b7bc0)); // 4.7323e-37f path.conicTo(SkBits2Float(0x212a8ced), SkBits2Float(0x0321081f), SkBits2Float(0x6a3a7bc0), SkBits2Float(0x2147ed7a), SkBits2Float(0x28282a3a)); // 5.77848e-19f, 4.7323e-37f, 5.63611e+25f, 6.77381e-19f, 9.33503e-15f SkPath path2(path); - testPathOpFailSkipAssert(reporter, path1, path2, (SkPathOp) 0, filename); + testPathOpSkipAssert(reporter, path1, path2, (SkPathOp) 0, filename); } static void fuzz763_27(skiatest::Reporter* reporter, const char* filename) { |