diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/pathops/SkOpContour.h | 14 | ||||
-rw-r--r-- | src/pathops/SkOpCubicHull.cpp | 7 | ||||
-rw-r--r-- | src/pathops/SkOpSegment.cpp | 127 | ||||
-rw-r--r-- | src/pathops/SkOpSegment.h | 3 | ||||
-rwxr-xr-x | src/pathops/SkOpSpan.cpp | 2 | ||||
-rw-r--r-- | src/pathops/SkOpSpan.h | 9 | ||||
-rw-r--r-- | src/pathops/SkPathOpsCommon.cpp | 21 | ||||
-rw-r--r-- | src/pathops/SkPathOpsDebug.cpp | 1 |
8 files changed, 157 insertions, 27 deletions
diff --git a/src/pathops/SkOpContour.h b/src/pathops/SkOpContour.h index c86f27b22e..3d26ae84c8 100644 --- a/src/pathops/SkOpContour.h +++ b/src/pathops/SkOpContour.h @@ -211,17 +211,23 @@ public: } while ((segment = segment->next())); } - bool moveNearby() { + bool moveMultiples() { SkASSERT(fCount > 0); SkOpSegment* segment = &fHead; do { - if (!segment->moveNearby()) { - return false; - } + segment->moveMultiples(); } while ((segment = segment->next())); return true; } + void moveNearby() { + SkASSERT(fCount > 0); + SkOpSegment* segment = &fHead; + do { + segment->moveNearby(); + } while ((segment = segment->next())); + } + SkOpContour* next() { return fNext; } diff --git a/src/pathops/SkOpCubicHull.cpp b/src/pathops/SkOpCubicHull.cpp index f3e0a7fc3f..6b17608e84 100644 --- a/src/pathops/SkOpCubicHull.cpp +++ b/src/pathops/SkOpCubicHull.cpp @@ -104,9 +104,10 @@ int SkDCubic::convexHull(char order[4]) const { double dist2_3 = fPts[2].distanceSquared(fPts[3]); double smallest1distSq = SkTMin(dist1_0, dist1_3); double smallest2distSq = SkTMin(dist2_0, dist2_3); - SkASSERT(approximately_zero(SkTMin(smallest1distSq, smallest2distSq))); - order[2] = smallest1distSq < smallest2distSq ? 2 : 1; - return 3; + if (approximately_zero(SkTMin(smallest1distSq, smallest2distSq))) { + order[2] = smallest1distSq < smallest2distSq ? 2 : 1; + return 3; + } } midX = index; } else if (sides == 0) { // '0' means both to one side or the other diff --git a/src/pathops/SkOpSegment.cpp b/src/pathops/SkOpSegment.cpp index b14be78d06..a571609f53 100644 --- a/src/pathops/SkOpSegment.cpp +++ b/src/pathops/SkOpSegment.cpp @@ -365,22 +365,26 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca SkOpSpanBase* span = &fHead; do { SkOpPtT* result = span->ptT(); + SkOpPtT* loop; + bool duplicatePt; if (t == result->fT) { - return result; + goto bumpSpan; } if (this->match(result, this, t, pt)) { // see if any existing alias matches segment, pt, and t - SkOpPtT* loop = result->next(); - bool duplicatePt = false; + loop = result->next(); + duplicatePt = false; while (loop != result) { bool ptMatch = loop->fPt == pt; if (loop->segment() == this && loop->fT == t && ptMatch) { - return result; + goto bumpSpan; } duplicatePt |= ptMatch; loop = loop->next(); } if (kNoAlias == allowAlias) { + bumpSpan: + span->bumpSpanAdds(); return result; } SkOpPtT* alias = SkOpTAllocator<SkOpPtT>::Allocate(allocator); @@ -392,6 +396,7 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca SkDebugf("%s alias t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, alias->segment()->debugID(), alias->span()->debugID()); #endif + span->bumpSpanAdds(); return alias; } if (t < result->fT) { @@ -403,6 +408,7 @@ SkOpPtT* SkOpSegment::addT(double t, AllowAlias allowAlias, SkChunkAlloc* alloca SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, span->segment()->debugID(), span->debugID()); #endif + span->bumpSpanAdds(); return span->ptT(); } SkASSERT(span != &fTail); @@ -725,9 +731,10 @@ SkOpSpan* SkOpSegment::crossedSpanY(const SkPoint& basePt, double mid, bool opp, void SkOpSegment::detach(const SkOpSpan* span) { if (span->done()) { - --this->fDoneCount; + --fDoneCount; } - --this->fCount; + --fCount; + SkASSERT(fCount >= fDoneCount); } double SkOpSegment::distSq(double t, SkOpAngle* oppAngle) { @@ -1423,7 +1430,7 @@ bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, doub if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) { return false; } - return !ptsDisjoint(base->fT, base->fPt, testT, testPt); + return !this->ptsDisjoint(base->fT, base->fPt, testT, testPt); } static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { @@ -1639,8 +1646,107 @@ void SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc clear_visited(&fHead); } +// if a span has more than one intersection, merge the other segments' span as needed +void SkOpSegment::moveMultiples() { + debugValidate(); + SkOpSpanBase* test = &fHead; + do { + int addCount = test->spanAddsCount(); + SkASSERT(addCount >= 1); + if (addCount == 1) { + continue; + } + SkOpPtT* startPtT = test->ptT(); + SkOpPtT* testPtT = startPtT; + do { // iterate through all spans associated with start + SkOpSpanBase* oppSpan = testPtT->span(); + if (oppSpan->spanAddsCount() == addCount) { + continue; + } + if (oppSpan->deleted()) { + continue; + } + SkOpSegment* oppSegment = oppSpan->segment(); + if (oppSegment == this) { + continue; + } + // find range of spans to consider merging + SkOpSpanBase* oppPrev = oppSpan; + SkOpSpanBase* oppFirst = oppSpan; + while ((oppPrev = oppPrev->prev())) { + if (!roughly_equal(oppPrev->t(), oppSpan->t())) { + break; + } + if (oppPrev->spanAddsCount() == addCount) { + continue; + } + if (oppPrev->deleted()) { + continue; + } + oppFirst = oppPrev; + } + SkOpSpanBase* oppNext = oppSpan; + SkOpSpanBase* oppLast = oppSpan; + while ((oppNext = oppNext->final() ? NULL : oppNext->upCast()->next())) { + if (!roughly_equal(oppNext->t(), oppSpan->t())) { + break; + } + if (oppNext->spanAddsCount() == addCount) { + continue; + } + if (oppNext->deleted()) { + continue; + } + oppLast = oppNext; + } + if (oppFirst == oppLast) { + continue; + } + SkOpSpanBase* oppTest = oppFirst; + do { + if (oppTest == oppSpan) { + continue; + } + // check to see if the candidate meets specific criteria: + // it contains spans of segments in test's loop but not including 'this' + SkOpPtT* oppStartPtT = oppTest->ptT(); + SkOpPtT* oppPtT = oppStartPtT; + while ((oppPtT = oppPtT->next()) != oppStartPtT) { + SkOpSegment* oppPtTSegment = oppPtT->segment(); + if (oppPtTSegment == this) { + goto tryNextSpan; + } + SkOpPtT* matchPtT = startPtT; + do { + if (matchPtT->segment() == oppPtTSegment) { + goto foundMatch; + } + } while ((matchPtT = matchPtT->next()) != startPtT); + goto tryNextSpan; + foundMatch: // merge oppTest and oppSpan + oppSegment->debugValidate(); + if (oppTest == &oppSegment->fTail || oppTest == &oppSegment->fHead) { + SkASSERT(oppSpan != &oppSegment->fHead); // don't expect collapse + SkASSERT(oppSpan != &oppSegment->fTail); + oppTest->merge(oppSpan->upCast()); + } else { + oppSpan->merge(oppTest->upCast()); + } + oppSegment->debugValidate(); + goto checkNextSpan; + } + tryNextSpan: + ; + } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); + } while ((testPtT = testPtT->next()) != startPtT); +checkNextSpan: + ; + } while ((test = test->final() ? NULL : test->upCast()->next())); + debugValidate(); +} + // Move nearby t values and pts so they all hang off the same span. Alignment happens later. -bool SkOpSegment::moveNearby() { +void SkOpSegment::moveNearby() { debugValidate(); SkOpSpanBase* spanS = &fHead; do { @@ -1672,11 +1778,11 @@ bool SkOpSegment::moveNearby() { if (test == &this->fTail) { if (spanS == &fHead) { debugValidate(); - return true; // if this span has collapsed, remove it from parent + return; // if this span has collapsed, remove it from parent } this->fTail.merge(spanS->upCast()); debugValidate(); - return true; + return; } spanS->merge(test->upCast()); spanS->upCast()->setNext(next); @@ -1690,7 +1796,6 @@ bool SkOpSegment::moveNearby() { spanS = spanS->upCast()->next(); } while (!spanS->final()); debugValidate(); - return true; } bool SkOpSegment::operand() const { diff --git a/src/pathops/SkOpSegment.h b/src/pathops/SkOpSegment.h index f878f5e64e..1e9e1c44be 100644 --- a/src/pathops/SkOpSegment.h +++ b/src/pathops/SkOpSegment.h @@ -254,7 +254,8 @@ public: bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const; void missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator); bool monotonicInY(const SkOpSpanBase* start, const SkOpSpanBase* end) const; - bool moveNearby(); + void moveMultiples(); + void moveNearby(); SkOpSegment* next() const { return fNext; diff --git a/src/pathops/SkOpSpan.cpp b/src/pathops/SkOpSpan.cpp index 32d2376a0f..b75a692f74 100755 --- a/src/pathops/SkOpSpan.cpp +++ b/src/pathops/SkOpSpan.cpp @@ -275,6 +275,7 @@ void SkOpSpanBase::initBase(SkOpSegment* segment, SkOpSpan* prev, double t, cons fCoinEnd = this; fFromAngle = NULL; fPrev = prev; + fSpanAdds = 0; fAligned = true; fChased = false; SkDEBUGCODE(fCount = 1); @@ -304,6 +305,7 @@ void SkOpSpanBase::merge(SkOpSpan* span) { tryNextRemainder: remainder = next; } + fSpanAdds += span->fSpanAdds; } void SkOpSpan::applyCoincidence(SkOpSpan* opp) { diff --git a/src/pathops/SkOpSpan.h b/src/pathops/SkOpSpan.h index bf03f4d5f6..ee2f332440 100644 --- a/src/pathops/SkOpSpan.h +++ b/src/pathops/SkOpSpan.h @@ -133,6 +133,10 @@ public: void alignEnd(double t, const SkPoint& pt); + void bumpSpanAdds() { + ++fSpanAdds; + } + bool chased() const { return fChased; } @@ -253,6 +257,10 @@ public: return fPtT.next()->next() == &fPtT; } + int spanAddsCount() const { + return fSpanAdds; + } + const SkOpSpan* starter(const SkOpSpanBase* end) const { const SkOpSpanBase* result = t() < end->t() ? this : end; return result->upCast(); @@ -316,6 +324,7 @@ protected: // no direct access to internals to avoid treating a span base as a SkOpSpanBase* fCoinEnd; // linked list of coincident spans that end here (may point to itself) SkOpAngle* fFromAngle; // points to next angle from span start to end SkOpSpan* fPrev; // previous intersection point + int fSpanAdds; // number of times intersections have been added to span bool fAligned; bool fChased; // set after span has been added to chase array SkDEBUGCODE(int fCount); // number of pt/t pairs added diff --git a/src/pathops/SkPathOpsCommon.cpp b/src/pathops/SkPathOpsCommon.cpp index e766f5abe2..3496179e65 100644 --- a/src/pathops/SkPathOpsCommon.cpp +++ b/src/pathops/SkPathOpsCommon.cpp @@ -659,15 +659,20 @@ static void missingCoincidence(SkTDArray<SkOpContour* >* contourList, } } -static bool moveNearby(SkTDArray<SkOpContour* >* contourList) { +static void moveMultiples(SkTDArray<SkOpContour* >* contourList) { int contourCount = (*contourList).count(); for (int cTest = 0; cTest < contourCount; ++cTest) { SkOpContour* contour = (*contourList)[cTest]; - if (!contour->moveNearby()) { - return false; - } + contour->moveMultiples(); + } +} + +static void moveNearby(SkTDArray<SkOpContour* >* contourList) { + int contourCount = (*contourList).count(); + for (int cTest = 0; cTest < contourCount; ++cTest) { + SkOpContour* contour = (*contourList)[cTest]; + contour->moveNearby(); } - return true; } static void sortAngles(SkTDArray<SkOpContour* >* contourList) { @@ -688,10 +693,10 @@ static void sortSegments(SkTDArray<SkOpContour* >* contourList) { bool HandleCoincidence(SkTDArray<SkOpContour* >* contourList, SkOpCoincidence* coincidence, SkChunkAlloc* allocator, SkOpGlobalState* globalState) { + // combine t values when multiple intersections occur on some segments but not others + moveMultiples(contourList); // move t values and points together to eliminate small/tiny gaps - if (!moveNearby(contourList)) { - return false; - } + moveNearby(contourList); align(contourList); // give all span members common values #if DEBUG_VALIDATE globalState->setPhase(SkOpGlobalState::kIntersecting); diff --git a/src/pathops/SkPathOpsDebug.cpp b/src/pathops/SkPathOpsDebug.cpp index 36f459935d..a9f8fe6acc 100644 --- a/src/pathops/SkPathOpsDebug.cpp +++ b/src/pathops/SkPathOpsDebug.cpp @@ -400,6 +400,7 @@ void SkOpSegment::debugValidate() const { } while (!span->final() && (span = span->upCast()->next())); SkASSERT(count == fCount); SkASSERT(done == fDoneCount); + SkASSERT(count >= fDoneCount); SkASSERT(span->final()); span->debugValidate(); #endif |