| /* | |
| * Copyright 2012 Google Inc. | |
| * | |
| * Use of this source code is governed by a BSD-style license that can be | |
| * found in the LICENSE file. | |
| */ | |
| #include "src/pathops/SkOpSegment.h" | |
| #include "include/private/SkTDArray.h" | |
| #include "include/private/SkTemplates.h" | |
| #include "src/core/SkPointPriv.h" | |
| #include "src/pathops/SkIntersections.h" | |
| #include "src/pathops/SkOpCoincidence.h" | |
| #include "src/pathops/SkOpContour.h" | |
| #include "src/pathops/SkPathOpsLine.h" | |
| #include "src/pathops/SkPathWriter.h" | |
| #include <algorithm> | |
| #include <cfloat> | |
| /* | |
| After computing raw intersections, post process all segments to: | |
| - find small collections of points that can be collapsed to a single point | |
| - find missing intersections to resolve differences caused by different algorithms | |
| Consider segments containing tiny or small intervals. Consider coincident segments | |
| because coincidence finds intersections through distance measurement that non-coincident | |
| intersection tests cannot. | |
| */ | |
| #define F (false) // discard the edge | |
| #define T (true) // keep the edge | |
| static constexpr bool kUnaryActiveEdge[2][2] = { | |
| // from=0 from=1 | |
| // to=0,1 to=0,1 | |
| {F, T}, {T, F}, | |
| }; | |
| static constexpr bool kActiveEdge[kXOR_SkPathOp + 1][2][2][2][2] = { | |
| // miFrom=0 miFrom=1 | |
| // miTo=0 miTo=1 miTo=0 miTo=1 | |
| // suFrom=0 1 suFrom=0 1 suFrom=0 1 suFrom=0 1 | |
| // suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 suTo=0,1 | |
| {{{{F, F}, {F, F}}, {{T, F}, {T, F}}}, {{{T, T}, {F, F}}, {{F, T}, {T, F}}}}, // mi - su | |
| {{{{F, F}, {F, F}}, {{F, T}, {F, T}}}, {{{F, F}, {T, T}}, {{F, T}, {T, F}}}}, // mi & su | |
| {{{{F, T}, {T, F}}, {{T, T}, {F, F}}}, {{{T, F}, {T, F}}, {{F, F}, {F, F}}}}, // mi | su | |
| {{{{F, T}, {T, F}}, {{T, F}, {F, T}}}, {{{T, F}, {F, T}}, {{F, T}, {T, F}}}}, // mi ^ su | |
| }; | |
| #undef F | |
| #undef T | |
| SkOpAngle* SkOpSegment::activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, | |
| SkOpSpanBase** endPtr, bool* done) { | |
| if (SkOpAngle* result = activeAngleInner(start, startPtr, endPtr, done)) { | |
| return result; | |
| } | |
| if (SkOpAngle* result = activeAngleOther(start, startPtr, endPtr, done)) { | |
| return result; | |
| } | |
| return nullptr; | |
| } | |
| SkOpAngle* SkOpSegment::activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr, | |
| SkOpSpanBase** endPtr, bool* done) { | |
| SkOpSpan* upSpan = start->upCastable(); | |
| if (upSpan) { | |
| if (upSpan->windValue() || upSpan->oppValue()) { | |
| SkOpSpanBase* next = upSpan->next(); | |
| if (!*endPtr) { | |
| *startPtr = start; | |
| *endPtr = next; | |
| } | |
| if (!upSpan->done()) { | |
| if (upSpan->windSum() != SK_MinS32) { | |
| return spanToAngle(start, next); | |
| } | |
| *done = false; | |
| } | |
| } else { | |
| SkASSERT(upSpan->done()); | |
| } | |
| } | |
| SkOpSpan* downSpan = start->prev(); | |
| // edge leading into junction | |
| if (downSpan) { | |
| if (downSpan->windValue() || downSpan->oppValue()) { | |
| if (!*endPtr) { | |
| *startPtr = start; | |
| *endPtr = downSpan; | |
| } | |
| if (!downSpan->done()) { | |
| if (downSpan->windSum() != SK_MinS32) { | |
| return spanToAngle(start, downSpan); | |
| } | |
| *done = false; | |
| } | |
| } else { | |
| SkASSERT(downSpan->done()); | |
| } | |
| } | |
| return nullptr; | |
| } | |
| SkOpAngle* SkOpSegment::activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr, | |
| SkOpSpanBase** endPtr, bool* done) { | |
| SkOpPtT* oPtT = start->ptT()->next(); | |
| SkOpSegment* other = oPtT->segment(); | |
| SkOpSpanBase* oSpan = oPtT->span(); | |
| return other->activeAngleInner(oSpan, startPtr, endPtr, done); | |
| } | |
| bool SkOpSegment::activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask, | |
| SkPathOp op) { | |
| int sumMiWinding = this->updateWinding(end, start); | |
| int sumSuWinding = this->updateOppWinding(end, start); | |
| #if DEBUG_LIMIT_WIND_SUM | |
| SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM); | |
| SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM); | |
| #endif | |
| if (this->operand()) { | |
| using std::swap; | |
| swap(sumMiWinding, sumSuWinding); | |
| } | |
| return this->activeOp(xorMiMask, xorSuMask, start, end, op, &sumMiWinding, &sumSuWinding); | |
| } | |
| bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, | |
| SkPathOp op, int* sumMiWinding, int* sumSuWinding) { | |
| int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; | |
| this->setUpWindings(start, end, sumMiWinding, sumSuWinding, | |
| &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); | |
| bool miFrom; | |
| bool miTo; | |
| bool suFrom; | |
| bool suTo; | |
| if (operand()) { | |
| miFrom = (oppMaxWinding & xorMiMask) != 0; | |
| miTo = (oppSumWinding & xorMiMask) != 0; | |
| suFrom = (maxWinding & xorSuMask) != 0; | |
| suTo = (sumWinding & xorSuMask) != 0; | |
| } else { | |
| miFrom = (maxWinding & xorMiMask) != 0; | |
| miTo = (sumWinding & xorMiMask) != 0; | |
| suFrom = (oppMaxWinding & xorSuMask) != 0; | |
| suTo = (oppSumWinding & xorSuMask) != 0; | |
| } | |
| bool result = kActiveEdge[op][miFrom][miTo][suFrom][suTo]; | |
| #if DEBUG_ACTIVE_OP | |
| SkDebugf("%s id=%d t=%1.9g tEnd=%1.9g op=%s miFrom=%d miTo=%d suFrom=%d suTo=%d result=%d\n", | |
| __FUNCTION__, debugID(), start->t(), end->t(), | |
| SkPathOpsDebug::kPathOpStr[op], miFrom, miTo, suFrom, suTo, result); | |
| #endif | |
| return result; | |
| } | |
| bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end) { | |
| int sumWinding = updateWinding(end, start); | |
| return activeWinding(start, end, &sumWinding); | |
| } | |
| bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding) { | |
| int maxWinding; | |
| setUpWinding(start, end, &maxWinding, sumWinding); | |
| bool from = maxWinding != 0; | |
| bool to = *sumWinding != 0; | |
| bool result = kUnaryActiveEdge[from][to]; | |
| return result; | |
| } | |
| bool SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, | |
| SkPathWriter* path) const { | |
| const SkOpSpan* spanStart = start->starter(end); | |
| FAIL_IF(spanStart->alreadyAdded()); | |
| const_cast<SkOpSpan*>(spanStart)->markAdded(); | |
| SkDCurveSweep curvePart; | |
| start->segment()->subDivide(start, end, &curvePart.fCurve); | |
| curvePart.setCurveHullSweep(fVerb); | |
| SkPath::Verb verb = curvePart.isCurve() ? fVerb : SkPath::kLine_Verb; | |
| path->deferredMove(start->ptT()); | |
| switch (verb) { | |
| case SkPath::kLine_Verb: | |
| FAIL_IF(!path->deferredLine(end->ptT())); | |
| break; | |
| case SkPath::kQuad_Verb: | |
| path->quadTo(curvePart.fCurve.fQuad[1].asSkPoint(), end->ptT()); | |
| break; | |
| case SkPath::kConic_Verb: | |
| path->conicTo(curvePart.fCurve.fConic[1].asSkPoint(), end->ptT(), | |
| curvePart.fCurve.fConic.fWeight); | |
| break; | |
| case SkPath::kCubic_Verb: | |
| path->cubicTo(curvePart.fCurve.fCubic[1].asSkPoint(), | |
| curvePart.fCurve.fCubic[2].asSkPoint(), end->ptT()); | |
| break; | |
| default: | |
| SkASSERT(0); | |
| } | |
| return true; | |
| } | |
| const SkOpPtT* SkOpSegment::existing(double t, const SkOpSegment* opp) const { | |
| const SkOpSpanBase* test = &fHead; | |
| const SkOpPtT* testPtT; | |
| SkPoint pt = this->ptAtT(t); | |
| do { | |
| testPtT = test->ptT(); | |
| if (testPtT->fT == t) { | |
| break; | |
| } | |
| if (!this->match(testPtT, this, t, pt)) { | |
| if (t < testPtT->fT) { | |
| return nullptr; | |
| } | |
| continue; | |
| } | |
| if (!opp) { | |
| return testPtT; | |
| } | |
| const SkOpPtT* loop = testPtT->next(); | |
| while (loop != testPtT) { | |
| if (loop->segment() == this && loop->fT == t && loop->fPt == pt) { | |
| goto foundMatch; | |
| } | |
| loop = loop->next(); | |
| } | |
| return nullptr; | |
| } while ((test = test->upCast()->next())); | |
| foundMatch: | |
| return opp && !test->contains(opp) ? nullptr : testPtT; | |
| } | |
| // break the span so that the coincident part does not change the angle of the remainder | |
| bool SkOpSegment::addExpanded(double newT, const SkOpSpanBase* test, bool* startOver) { | |
| if (this->contains(newT)) { | |
| return true; | |
| } | |
| this->globalState()->resetAllocatedOpSpan(); | |
| FAIL_IF(!between(0, newT, 1)); | |
| SkOpPtT* newPtT = this->addT(newT); | |
| *startOver |= this->globalState()->allocatedOpSpan(); | |
| if (!newPtT) { | |
| return false; | |
| } | |
| newPtT->fPt = this->ptAtT(newT); | |
| SkOpPtT* oppPrev = test->ptT()->oppPrev(newPtT); | |
| if (oppPrev) { | |
| // const cast away to change linked list; pt/t values stays unchanged | |
| SkOpSpanBase* writableTest = const_cast<SkOpSpanBase*>(test); | |
| writableTest->mergeMatches(newPtT->span()); | |
| writableTest->ptT()->addOpp(newPtT, oppPrev); | |
| writableTest->checkForCollapsedCoincidence(); | |
| } | |
| return true; | |
| } | |
| // Please keep this in sync with debugAddT() | |
| SkOpPtT* SkOpSegment::addT(double t, const SkPoint& pt) { | |
| debugValidate(); | |
| SkOpSpanBase* spanBase = &fHead; | |
| do { | |
| SkOpPtT* result = spanBase->ptT(); | |
| if (t == result->fT || (!zero_or_one(t) && this->match(result, this, t, pt))) { | |
| spanBase->bumpSpanAdds(); | |
| return result; | |
| } | |
| if (t < result->fT) { | |
| SkOpSpan* prev = result->span()->prev(); | |
| FAIL_WITH_NULL_IF(!prev); | |
| // marks in global state that new op span has been allocated | |
| SkOpSpan* span = this->insert(prev); | |
| span->init(this, prev, t, pt); | |
| this->debugValidate(); | |
| #if DEBUG_ADD_T | |
| SkDebugf("%s insert t=%1.9g segID=%d spanID=%d\n", __FUNCTION__, t, | |
| span->segment()->debugID(), span->debugID()); | |
| #endif | |
| span->bumpSpanAdds(); | |
| return span->ptT(); | |
| } | |
| FAIL_WITH_NULL_IF(spanBase == &fTail); | |
| } while ((spanBase = spanBase->upCast()->next())); | |
| SkASSERT(0); | |
| return nullptr; // we never get here, but need this to satisfy compiler | |
| } | |
| SkOpPtT* SkOpSegment::addT(double t) { | |
| return addT(t, this->ptAtT(t)); | |
| } | |
| void SkOpSegment::calcAngles() { | |
| bool activePrior = !fHead.isCanceled(); | |
| if (activePrior && !fHead.simple()) { | |
| addStartSpan(); | |
| } | |
| SkOpSpan* prior = &fHead; | |
| SkOpSpanBase* spanBase = fHead.next(); | |
| while (spanBase != &fTail) { | |
| if (activePrior) { | |
| SkOpAngle* priorAngle = this->globalState()->allocator()->make<SkOpAngle>(); | |
| priorAngle->set(spanBase, prior); | |
| spanBase->setFromAngle(priorAngle); | |
| } | |
| SkOpSpan* span = spanBase->upCast(); | |
| bool active = !span->isCanceled(); | |
| SkOpSpanBase* next = span->next(); | |
| if (active) { | |
| SkOpAngle* angle = this->globalState()->allocator()->make<SkOpAngle>(); | |
| angle->set(span, next); | |
| span->setToAngle(angle); | |
| } | |
| activePrior = active; | |
| prior = span; | |
| spanBase = next; | |
| } | |
| if (activePrior && !fTail.simple()) { | |
| addEndSpan(); | |
| } | |
| } | |
| // Please keep this in sync with debugClearAll() | |
| void SkOpSegment::clearAll() { | |
| SkOpSpan* span = &fHead; | |
| do { | |
| this->clearOne(span); | |
| } while ((span = span->next()->upCastable())); | |
| this->globalState()->coincidence()->release(this); | |
| } | |
| // Please keep this in sync with debugClearOne() | |
| void SkOpSegment::clearOne(SkOpSpan* span) { | |
| span->setWindValue(0); | |
| span->setOppValue(0); | |
| this->markDone(span); | |
| } | |
| SkOpSpanBase::Collapsed SkOpSegment::collapsed(double s, double e) const { | |
| const SkOpSpanBase* span = &fHead; | |
| do { | |
| SkOpSpanBase::Collapsed result = span->collapsed(s, e); | |
| if (SkOpSpanBase::Collapsed::kNo != result) { | |
| return result; | |
| } | |
| } while (span->upCastable() && (span = span->upCast()->next())); | |
| return SkOpSpanBase::Collapsed::kNo; | |
| } | |
| bool SkOpSegment::ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, | |
| SkOpAngle::IncludeType includeType) { | |
| SkOpSegment* baseSegment = baseAngle->segment(); | |
| int sumMiWinding = baseSegment->updateWindingReverse(baseAngle); | |
| int sumSuWinding; | |
| bool binary = includeType >= SkOpAngle::kBinarySingle; | |
| if (binary) { | |
| sumSuWinding = baseSegment->updateOppWindingReverse(baseAngle); | |
| if (baseSegment->operand()) { | |
| using std::swap; | |
| swap(sumMiWinding, sumSuWinding); | |
| } | |
| } | |
| SkOpSegment* nextSegment = nextAngle->segment(); | |
| int maxWinding, sumWinding; | |
| SkOpSpanBase* last = nullptr; | |
| if (binary) { | |
| int oppMaxWinding, oppSumWinding; | |
| nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, | |
| &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); | |
| if (!nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, | |
| nextAngle, &last)) { | |
| return false; | |
| } | |
| } else { | |
| nextSegment->setUpWindings(nextAngle->start(), nextAngle->end(), &sumMiWinding, | |
| &maxWinding, &sumWinding); | |
| if (!nextSegment->markAngle(maxWinding, sumWinding, nextAngle, &last)) { | |
| return false; | |
| } | |
| } | |
| nextAngle->setLastMarked(last); | |
| return true; | |
| } | |
| bool SkOpSegment::ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, | |
| SkOpAngle::IncludeType includeType) { | |
| SkOpSegment* baseSegment = baseAngle->segment(); | |
| int sumMiWinding = baseSegment->updateWinding(baseAngle); | |
| int sumSuWinding; | |
| bool binary = includeType >= SkOpAngle::kBinarySingle; | |
| if (binary) { | |
| sumSuWinding = baseSegment->updateOppWinding(baseAngle); | |
| if (baseSegment->operand()) { | |
| using std::swap; | |
| swap(sumMiWinding, sumSuWinding); | |
| } | |
| } | |
| SkOpSegment* nextSegment = nextAngle->segment(); | |
| int maxWinding, sumWinding; | |
| SkOpSpanBase* last = nullptr; | |
| if (binary) { | |
| int oppMaxWinding, oppSumWinding; | |
| nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, | |
| &sumSuWinding, &maxWinding, &sumWinding, &oppMaxWinding, &oppSumWinding); | |
| if (!nextSegment->markAngle(maxWinding, sumWinding, oppMaxWinding, oppSumWinding, | |
| nextAngle, &last)) { | |
| return false; | |
| } | |
| } else { | |
| nextSegment->setUpWindings(nextAngle->end(), nextAngle->start(), &sumMiWinding, | |
| &maxWinding, &sumWinding); | |
| if (!nextSegment->markAngle(maxWinding, sumWinding, nextAngle, &last)) { | |
| return false; | |
| } | |
| } | |
| nextAngle->setLastMarked(last); | |
| return true; | |
| } | |
| // at this point, the span is already ordered, or unorderable | |
| int SkOpSegment::computeSum(SkOpSpanBase* start, SkOpSpanBase* end, | |
| SkOpAngle::IncludeType includeType) { | |
| SkASSERT(includeType != SkOpAngle::kUnaryXor); | |
| SkOpAngle* firstAngle = this->spanToAngle(end, start); | |
| if (nullptr == firstAngle || nullptr == firstAngle->next()) { | |
| return SK_NaN32; | |
| } | |
| // if all angles have a computed winding, | |
| // or if no adjacent angles are orderable, | |
| // or if adjacent orderable angles have no computed winding, | |
| // there's nothing to do | |
| // if two orderable angles are adjacent, and both are next to orderable angles, | |
| // and one has winding computed, transfer to the other | |
| SkOpAngle* baseAngle = nullptr; | |
| bool tryReverse = false; | |
| // look for counterclockwise transfers | |
| SkOpAngle* angle = firstAngle->previous(); | |
| SkOpAngle* next = angle->next(); | |
| firstAngle = next; | |
| do { | |
| SkOpAngle* prior = angle; | |
| angle = next; | |
| next = angle->next(); | |
| SkASSERT(prior->next() == angle); | |
| SkASSERT(angle->next() == next); | |
| if (prior->unorderable() || angle->unorderable() || next->unorderable()) { | |
| baseAngle = nullptr; | |
| continue; | |
| } | |
| int testWinding = angle->starter()->windSum(); | |
| if (SK_MinS32 != testWinding) { | |
| baseAngle = angle; | |
| tryReverse = true; | |
| continue; | |
| } | |
| if (baseAngle) { | |
| ComputeOneSum(baseAngle, angle, includeType); | |
| baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; | |
| } | |
| } while (next != firstAngle); | |
| if (baseAngle && SK_MinS32 == firstAngle->starter()->windSum()) { | |
| firstAngle = baseAngle; | |
| tryReverse = true; | |
| } | |
| if (tryReverse) { | |
| baseAngle = nullptr; | |
| SkOpAngle* prior = firstAngle; | |
| do { | |
| angle = prior; | |
| prior = angle->previous(); | |
| SkASSERT(prior->next() == angle); | |
| next = angle->next(); | |
| if (prior->unorderable() || angle->unorderable() || next->unorderable()) { | |
| baseAngle = nullptr; | |
| continue; | |
| } | |
| int testWinding = angle->starter()->windSum(); | |
| if (SK_MinS32 != testWinding) { | |
| baseAngle = angle; | |
| continue; | |
| } | |
| if (baseAngle) { | |
| ComputeOneSumReverse(baseAngle, angle, includeType); | |
| baseAngle = SK_MinS32 != angle->starter()->windSum() ? angle : nullptr; | |
| } | |
| } while (prior != firstAngle); | |
| } | |
| return start->starter(end)->windSum(); | |
| } | |
| bool SkOpSegment::contains(double newT) const { | |
| const SkOpSpanBase* spanBase = &fHead; | |
| do { | |
| if (spanBase->ptT()->contains(this, newT)) { | |
| return true; | |
| } | |
| if (spanBase == &fTail) { | |
| break; | |
| } | |
| spanBase = spanBase->upCast()->next(); | |
| } while (true); | |
| return false; | |
| } | |
| void SkOpSegment::release(const SkOpSpan* span) { | |
| if (span->done()) { | |
| --fDoneCount; | |
| } | |
| --fCount; | |
| SkOPASSERT(fCount >= fDoneCount); | |
| } | |
| #if DEBUG_ANGLE | |
| // called only by debugCheckNearCoincidence | |
| double SkOpSegment::distSq(double t, const SkOpAngle* oppAngle) const { | |
| SkDPoint testPt = this->dPtAtT(t); | |
| SkDLine testPerp = {{ testPt, testPt }}; | |
| SkDVector slope = this->dSlopeAtT(t); | |
| testPerp[1].fX += slope.fY; | |
| testPerp[1].fY -= slope.fX; | |
| SkIntersections i; | |
| const SkOpSegment* oppSegment = oppAngle->segment(); | |
| (*CurveIntersectRay[oppSegment->verb()])(oppSegment->pts(), oppSegment->weight(), testPerp, &i); | |
| double closestDistSq = SK_ScalarInfinity; | |
| for (int index = 0; index < i.used(); ++index) { | |
| if (!between(oppAngle->start()->t(), i[0][index], oppAngle->end()->t())) { | |
| continue; | |
| } | |
| double testDistSq = testPt.distanceSquared(i.pt(index)); | |
| if (closestDistSq > testDistSq) { | |
| closestDistSq = testDistSq; | |
| } | |
| } | |
| return closestDistSq; | |
| } | |
| #endif | |
| /* | |
| The M and S variable name parts stand for the operators. | |
| Mi stands for Minuend (see wiki subtraction, analogous to difference) | |
| Su stands for Subtrahend | |
| The Opp variable name part designates that the value is for the Opposite operator. | |
| Opposite values result from combining coincident spans. | |
| */ | |
| SkOpSegment* SkOpSegment::findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, | |
| SkOpSpanBase** nextEnd, bool* unsortable, bool* simple, | |
| SkPathOp op, int xorMiMask, int xorSuMask) { | |
| SkOpSpanBase* start = *nextStart; | |
| SkOpSpanBase* end = *nextEnd; | |
| SkASSERT(start != end); | |
| int step = start->step(end); | |
| SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart | |
| if ((*simple = other)) { | |
| // mark the smaller of startIndex, endIndex done, and all adjacent | |
| // spans with the same T value (but not 'other' spans) | |
| #if DEBUG_WINDING | |
| SkDebugf("%s simple\n", __FUNCTION__); | |
| #endif | |
| SkOpSpan* startSpan = start->starter(end); | |
| if (startSpan->done()) { | |
| return nullptr; | |
| } | |
| markDone(startSpan); | |
| *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); | |
| return other; | |
| } | |
| SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); | |
| SkASSERT(endNear == end); // is this ever not end? | |
| SkASSERT(endNear); | |
| SkASSERT(start != endNear); | |
| SkASSERT((start->t() < endNear->t()) ^ (step < 0)); | |
| // more than one viable candidate -- measure angles to find best | |
| int calcWinding = computeSum(start, endNear, SkOpAngle::kBinaryOpp); | |
| bool sortable = calcWinding != SK_NaN32; | |
| if (!sortable) { | |
| *unsortable = true; | |
| markDone(start->starter(end)); | |
| return nullptr; | |
| } | |
| SkOpAngle* angle = this->spanToAngle(end, start); | |
| if (angle->unorderable()) { | |
| *unsortable = true; | |
| markDone(start->starter(end)); | |
| return nullptr; | |
| } | |
| #if DEBUG_SORT | |
| SkDebugf("%s\n", __FUNCTION__); | |
| angle->debugLoop(); | |
| #endif | |
| int sumMiWinding = updateWinding(end, start); | |
| if (sumMiWinding == SK_MinS32) { | |
| *unsortable = true; | |
| markDone(start->starter(end)); | |
| return nullptr; | |
| } | |
| int sumSuWinding = updateOppWinding(end, start); | |
| if (operand()) { | |
| using std::swap; | |
| swap(sumMiWinding, sumSuWinding); | |
| } | |
| SkOpAngle* nextAngle = angle->next(); | |
| const SkOpAngle* foundAngle = nullptr; | |
| bool foundDone = false; | |
| // iterate through the angle, and compute everyone's winding | |
| SkOpSegment* nextSegment; | |
| int activeCount = 0; | |
| do { | |
| nextSegment = nextAngle->segment(); | |
| bool activeAngle = nextSegment->activeOp(xorMiMask, xorSuMask, nextAngle->start(), | |
| nextAngle->end(), op, &sumMiWinding, &sumSuWinding); | |
| if (activeAngle) { | |
| ++activeCount; | |
| if (!foundAngle || (foundDone && activeCount & 1)) { | |
| foundAngle = nextAngle; | |
| foundDone = nextSegment->done(nextAngle); | |
| } | |
| } | |
| if (nextSegment->done()) { | |
| continue; | |
| } | |
| if (!activeAngle) { | |
| (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end(), nullptr); | |
| } | |
| SkOpSpanBase* last = nextAngle->lastMarked(); | |
| if (last) { | |
| SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); | |
| *chase->append() = last; | |
| #if DEBUG_WINDING | |
| SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, | |
| last->segment()->debugID(), last->debugID()); | |
| if (!last->final()) { | |
| SkDebugf(" windSum=%d", last->upCast()->windSum()); | |
| } | |
| SkDebugf("\n"); | |
| #endif | |
| } | |
| } while ((nextAngle = nextAngle->next()) != angle); | |
| start->segment()->markDone(start->starter(end)); | |
| if (!foundAngle) { | |
| return nullptr; | |
| } | |
| *nextStart = foundAngle->start(); | |
| *nextEnd = foundAngle->end(); | |
| nextSegment = foundAngle->segment(); | |
| #if DEBUG_WINDING | |
| SkDebugf("%s from:[%d] to:[%d] start=%p end=%p\n", | |
| __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); | |
| #endif | |
| return nextSegment; | |
| } | |
| SkOpSegment* SkOpSegment::findNextWinding(SkTDArray<SkOpSpanBase*>* chase, | |
| SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable) { | |
| SkOpSpanBase* start = *nextStart; | |
| SkOpSpanBase* end = *nextEnd; | |
| SkASSERT(start != end); | |
| int step = start->step(end); | |
| SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart | |
| if (other) { | |
| // mark the smaller of startIndex, endIndex done, and all adjacent | |
| // spans with the same T value (but not 'other' spans) | |
| #if DEBUG_WINDING | |
| SkDebugf("%s simple\n", __FUNCTION__); | |
| #endif | |
| SkOpSpan* startSpan = start->starter(end); | |
| if (startSpan->done()) { | |
| return nullptr; | |
| } | |
| markDone(startSpan); | |
| *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); | |
| return other; | |
| } | |
| SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); | |
| SkASSERT(endNear == end); // is this ever not end? | |
| SkASSERT(endNear); | |
| SkASSERT(start != endNear); | |
| SkASSERT((start->t() < endNear->t()) ^ (step < 0)); | |
| // more than one viable candidate -- measure angles to find best | |
| int calcWinding = computeSum(start, endNear, SkOpAngle::kUnaryWinding); | |
| bool sortable = calcWinding != SK_NaN32; | |
| if (!sortable) { | |
| *unsortable = true; | |
| markDone(start->starter(end)); | |
| return nullptr; | |
| } | |
| SkOpAngle* angle = this->spanToAngle(end, start); | |
| if (angle->unorderable()) { | |
| *unsortable = true; | |
| markDone(start->starter(end)); | |
| return nullptr; | |
| } | |
| #if DEBUG_SORT | |
| SkDebugf("%s\n", __FUNCTION__); | |
| angle->debugLoop(); | |
| #endif | |
| int sumWinding = updateWinding(end, start); | |
| SkOpAngle* nextAngle = angle->next(); | |
| const SkOpAngle* foundAngle = nullptr; | |
| bool foundDone = false; | |
| // iterate through the angle, and compute everyone's winding | |
| SkOpSegment* nextSegment; | |
| int activeCount = 0; | |
| do { | |
| nextSegment = nextAngle->segment(); | |
| bool activeAngle = nextSegment->activeWinding(nextAngle->start(), nextAngle->end(), | |
| &sumWinding); | |
| if (activeAngle) { | |
| ++activeCount; | |
| if (!foundAngle || (foundDone && activeCount & 1)) { | |
| foundAngle = nextAngle; | |
| foundDone = nextSegment->done(nextAngle); | |
| } | |
| } | |
| if (nextSegment->done()) { | |
| continue; | |
| } | |
| if (!activeAngle) { | |
| (void) nextSegment->markAndChaseDone(nextAngle->start(), nextAngle->end(), nullptr); | |
| } | |
| SkOpSpanBase* last = nextAngle->lastMarked(); | |
| if (last) { | |
| SkASSERT(!SkPathOpsDebug::ChaseContains(*chase, last)); | |
| *chase->append() = last; | |
| #if DEBUG_WINDING | |
| SkDebugf("%s chase.append segment=%d span=%d", __FUNCTION__, | |
| last->segment()->debugID(), last->debugID()); | |
| if (!last->final()) { | |
| SkDebugf(" windSum=%d", last->upCast()->windSum()); | |
| } | |
| SkDebugf("\n"); | |
| #endif | |
| } | |
| } while ((nextAngle = nextAngle->next()) != angle); | |
| start->segment()->markDone(start->starter(end)); | |
| if (!foundAngle) { | |
| return nullptr; | |
| } | |
| *nextStart = foundAngle->start(); | |
| *nextEnd = foundAngle->end(); | |
| nextSegment = foundAngle->segment(); | |
| #if DEBUG_WINDING | |
| SkDebugf("%s from:[%d] to:[%d] start=%p end=%p\n", | |
| __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); | |
| #endif | |
| return nextSegment; | |
| } | |
| SkOpSegment* SkOpSegment::findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, | |
| bool* unsortable) { | |
| SkOpSpanBase* start = *nextStart; | |
| SkOpSpanBase* end = *nextEnd; | |
| SkASSERT(start != end); | |
| int step = start->step(end); | |
| SkOpSegment* other = this->isSimple(nextStart, &step); // advances nextStart | |
| if (other) { | |
| // mark the smaller of startIndex, endIndex done, and all adjacent | |
| // spans with the same T value (but not 'other' spans) | |
| #if DEBUG_WINDING | |
| SkDebugf("%s simple\n", __FUNCTION__); | |
| #endif | |
| SkOpSpan* startSpan = start->starter(end); | |
| if (startSpan->done()) { | |
| return nullptr; | |
| } | |
| markDone(startSpan); | |
| *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->prev(); | |
| return other; | |
| } | |
| SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next() \ | |
| : (*nextStart)->prev()); | |
| SkASSERT(endNear == end); // is this ever not end? | |
| SkASSERT(endNear); | |
| SkASSERT(start != endNear); | |
| SkASSERT((start->t() < endNear->t()) ^ (step < 0)); | |
| SkOpAngle* angle = this->spanToAngle(end, start); | |
| if (!angle || angle->unorderable()) { | |
| *unsortable = true; | |
| markDone(start->starter(end)); | |
| return nullptr; | |
| } | |
| #if DEBUG_SORT | |
| SkDebugf("%s\n", __FUNCTION__); | |
| angle->debugLoop(); | |
| #endif | |
| SkOpAngle* nextAngle = angle->next(); | |
| const SkOpAngle* foundAngle = nullptr; | |
| bool foundDone = false; | |
| // iterate through the angle, and compute everyone's winding | |
| SkOpSegment* nextSegment; | |
| int activeCount = 0; | |
| do { | |
| if (!nextAngle) { | |
| return nullptr; | |
| } | |
| nextSegment = nextAngle->segment(); | |
| ++activeCount; | |
| if (!foundAngle || (foundDone && activeCount & 1)) { | |
| foundAngle = nextAngle; | |
| if (!(foundDone = nextSegment->done(nextAngle))) { | |
| break; | |
| } | |
| } | |
| nextAngle = nextAngle->next(); | |
| } while (nextAngle != angle); | |
| start->segment()->markDone(start->starter(end)); | |
| if (!foundAngle) { | |
| return nullptr; | |
| } | |
| *nextStart = foundAngle->start(); | |
| *nextEnd = foundAngle->end(); | |
| nextSegment = foundAngle->segment(); | |
| #if DEBUG_WINDING | |
| SkDebugf("%s from:[%d] to:[%d] start=%p end=%p\n", | |
| __FUNCTION__, debugID(), nextSegment->debugID(), *nextStart, *nextEnd); | |
| #endif | |
| return nextSegment; | |
| } | |
| SkOpGlobalState* SkOpSegment::globalState() const { | |
| return contour()->globalState(); | |
| } | |
| void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkPath::Verb verb) { | |
| fContour = contour; | |
| fNext = nullptr; | |
| fPts = pts; | |
| fWeight = weight; | |
| fVerb = verb; | |
| fCount = 0; | |
| fDoneCount = 0; | |
| fVisited = false; | |
| SkOpSpan* zeroSpan = &fHead; | |
| zeroSpan->init(this, nullptr, 0, fPts[0]); | |
| SkOpSpanBase* oneSpan = &fTail; | |
| zeroSpan->setNext(oneSpan); | |
| oneSpan->initBase(this, zeroSpan, 1, fPts[SkPathOpsVerbToPoints(fVerb)]); | |
| SkDEBUGCODE(fID = globalState()->nextSegmentID()); | |
| } | |
| bool SkOpSegment::isClose(double t, const SkOpSegment* opp) const { | |
| SkDPoint cPt = this->dPtAtT(t); | |
| SkDVector dxdy = (*CurveDSlopeAtT[this->verb()])(this->pts(), this->weight(), t); | |
| SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; | |
| SkIntersections i; | |
| (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), perp, &i); | |
| int used = i.used(); | |
| for (int index = 0; index < used; ++index) { | |
| if (cPt.roughlyEqual(i.pt(index))) { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| bool SkOpSegment::isXor() const { | |
| return fContour->isXor(); | |
| } | |
| void SkOpSegment::markAllDone() { | |
| SkOpSpan* span = this->head(); | |
| do { | |
| this->markDone(span); | |
| } while ((span = span->next()->upCastable())); | |
| } | |
| bool SkOpSegment::markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end, SkOpSpanBase** found) { | |
| int step = start->step(end); | |
| SkOpSpan* minSpan = start->starter(end); | |
| markDone(minSpan); | |
| SkOpSpanBase* last = nullptr; | |
| SkOpSegment* other = this; | |
| SkOpSpan* priorDone = nullptr; | |
| SkOpSpan* lastDone = nullptr; | |
| int safetyNet = 1000; | |
| while ((other = other->nextChase(&start, &step, &minSpan, &last))) { | |
| if (!--safetyNet) { | |
| return false; | |
| } | |
| if (other->done()) { | |
| SkASSERT(!last); | |
| break; | |
| } | |
| if (lastDone == minSpan || priorDone == minSpan) { | |
| if (found) { | |
| *found = nullptr; | |
| } | |
| return true; | |
| } | |
| other->markDone(minSpan); | |
| priorDone = lastDone; | |
| lastDone = minSpan; | |
| } | |
| if (found) { | |
| *found = last; | |
| } | |
| return true; | |
| } | |
| bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, | |
| SkOpSpanBase** lastPtr) { | |
| SkOpSpan* spanStart = start->starter(end); | |
| int step = start->step(end); | |
| bool success = markWinding(spanStart, winding); | |
| SkOpSpanBase* last = nullptr; | |
| SkOpSegment* other = this; | |
| int safetyNet = 1000; | |
| while ((other = other->nextChase(&start, &step, &spanStart, &last))) { | |
| if (!--safetyNet) { | |
| return false; | |
| } | |
| if (spanStart->windSum() != SK_MinS32) { | |
| // SkASSERT(spanStart->windSum() == winding); // FIXME: is this assert too aggressive? | |
| SkASSERT(!last); | |
| break; | |
| } | |
| (void) other->markWinding(spanStart, winding); | |
| } | |
| if (lastPtr) { | |
| *lastPtr = last; | |
| } | |
| return success; | |
| } | |
| bool SkOpSegment::markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, | |
| int winding, int oppWinding, SkOpSpanBase** lastPtr) { | |
| SkOpSpan* spanStart = start->starter(end); | |
| int step = start->step(end); | |
| bool success = markWinding(spanStart, winding, oppWinding); | |
| SkOpSpanBase* last = nullptr; | |
| SkOpSegment* other = this; | |
| int safetyNet = 1000; | |
| while ((other = other->nextChase(&start, &step, &spanStart, &last))) { | |
| if (!--safetyNet) { | |
| return false; | |
| } | |
| if (spanStart->windSum() != SK_MinS32) { | |
| if (this->operand() == other->operand()) { | |
| if (spanStart->windSum() != winding || spanStart->oppSum() != oppWinding) { | |
| this->globalState()->setWindingFailed(); | |
| return true; // ... but let it succeed anyway | |
| } | |
| } else { | |
| FAIL_IF(spanStart->windSum() != oppWinding); | |
| FAIL_IF(spanStart->oppSum() != winding); | |
| } | |
| SkASSERT(!last); | |
| break; | |
| } | |
| if (this->operand() == other->operand()) { | |
| (void) other->markWinding(spanStart, winding, oppWinding); | |
| } else { | |
| (void) other->markWinding(spanStart, oppWinding, winding); | |
| } | |
| } | |
| if (lastPtr) { | |
| *lastPtr = last; | |
| } | |
| return success; | |
| } | |
| bool SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle, | |
| SkOpSpanBase** result) { | |
| SkASSERT(angle->segment() == this); | |
| if (UseInnerWinding(maxWinding, sumWinding)) { | |
| maxWinding = sumWinding; | |
| } | |
| if (!markAndChaseWinding(angle->start(), angle->end(), maxWinding, result)) { | |
| return false; | |
| } | |
| #if DEBUG_WINDING | |
| SkOpSpanBase* last = *result; | |
| if (last) { | |
| SkDebugf("%s last seg=%d span=%d", __FUNCTION__, | |
| last->segment()->debugID(), last->debugID()); | |
| if (!last->final()) { | |
| SkDebugf(" windSum="); | |
| SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); | |
| } | |
| SkDebugf("\n"); | |
| } | |
| #endif | |
| return true; | |
| } | |
| bool SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWinding, | |
| int oppSumWinding, const SkOpAngle* angle, SkOpSpanBase** result) { | |
| SkASSERT(angle->segment() == this); | |
| if (UseInnerWinding(maxWinding, sumWinding)) { | |
| maxWinding = sumWinding; | |
| } | |
| if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumWinding)) { | |
| oppMaxWinding = oppSumWinding; | |
| } | |
| // caller doesn't require that this marks anything | |
| if (!markAndChaseWinding(angle->start(), angle->end(), maxWinding, oppMaxWinding, result)) { | |
| return false; | |
| } | |
| #if DEBUG_WINDING | |
| if (result) { | |
| SkOpSpanBase* last = *result; | |
| if (last) { | |
| SkDebugf("%s last segment=%d span=%d", __FUNCTION__, | |
| last->segment()->debugID(), last->debugID()); | |
| if (!last->final()) { | |
| SkDebugf(" windSum="); | |
| SkPathOpsDebug::WindingPrintf(last->upCast()->windSum()); | |
| } | |
| SkDebugf(" \n"); | |
| } | |
| } | |
| #endif | |
| return true; | |
| } | |
| void SkOpSegment::markDone(SkOpSpan* span) { | |
| SkASSERT(this == span->segment()); | |
| if (span->done()) { | |
| return; | |
| } | |
| #if DEBUG_MARK_DONE | |
| debugShowNewWinding(__FUNCTION__, span, span->windSum(), span->oppSum()); | |
| #endif | |
| span->setDone(true); | |
| ++fDoneCount; | |
| debugValidate(); | |
| } | |
| bool SkOpSegment::markWinding(SkOpSpan* span, int winding) { | |
| SkASSERT(this == span->segment()); | |
| SkASSERT(winding); | |
| if (span->done()) { | |
| return false; | |
| } | |
| #if DEBUG_MARK_DONE | |
| debugShowNewWinding(__FUNCTION__, span, winding); | |
| #endif | |
| span->setWindSum(winding); | |
| debugValidate(); | |
| return true; | |
| } | |
| bool SkOpSegment::markWinding(SkOpSpan* span, int winding, int oppWinding) { | |
| SkASSERT(this == span->segment()); | |
| SkASSERT(winding || oppWinding); | |
| if (span->done()) { | |
| return false; | |
| } | |
| #if DEBUG_MARK_DONE | |
| debugShowNewWinding(__FUNCTION__, span, winding, oppWinding); | |
| #endif | |
| span->setWindSum(winding); | |
| span->setOppSum(oppWinding); | |
| debugValidate(); | |
| return true; | |
| } | |
| bool SkOpSegment::match(const SkOpPtT* base, const SkOpSegment* testParent, double testT, | |
| const SkPoint& testPt) const { | |
| SkASSERT(this == base->segment()); | |
| if (this == testParent) { | |
| if (precisely_equal(base->fT, testT)) { | |
| return true; | |
| } | |
| } | |
| if (!SkDPoint::ApproximatelyEqual(testPt, base->fPt)) { | |
| return false; | |
| } | |
| return this != testParent || !this->ptsDisjoint(base->fT, base->fPt, testT, testPt); | |
| } | |
| static SkOpSegment* set_last(SkOpSpanBase** last, SkOpSpanBase* endSpan) { | |
| if (last) { | |
| *last = endSpan; | |
| } | |
| return nullptr; | |
| } | |
| SkOpSegment* SkOpSegment::nextChase(SkOpSpanBase** startPtr, int* stepPtr, SkOpSpan** minPtr, | |
| SkOpSpanBase** last) const { | |
| SkOpSpanBase* origStart = *startPtr; | |
| int step = *stepPtr; | |
| SkOpSpanBase* endSpan = step > 0 ? origStart->upCast()->next() : origStart->prev(); | |
| SkASSERT(endSpan); | |
| SkOpAngle* angle = step > 0 ? endSpan->fromAngle() : endSpan->upCast()->toAngle(); | |
| SkOpSpanBase* foundSpan; | |
| SkOpSpanBase* otherEnd; | |
| SkOpSegment* other; | |
| if (angle == nullptr) { | |
| if (endSpan->t() != 0 && endSpan->t() != 1) { | |
| return nullptr; | |
| } | |
| SkOpPtT* otherPtT = endSpan->ptT()->next(); | |
| other = otherPtT->segment(); | |
| foundSpan = otherPtT->span(); | |
| otherEnd = step > 0 | |
| ? foundSpan->upCastable() ? foundSpan->upCast()->next() : nullptr | |
| : foundSpan->prev(); | |
| } else { | |
| int loopCount = angle->loopCount(); | |
| if (loopCount > 2) { | |
| return set_last(last, endSpan); | |
| } | |
| const SkOpAngle* next = angle->next(); | |
| if (nullptr == next) { | |
| return nullptr; | |
| } | |
| #if DEBUG_WINDING | |
| if (angle->debugSign() != next->debugSign() && !angle->segment()->contour()->isXor() | |
| && !next->segment()->contour()->isXor()) { | |
| SkDebugf("%s mismatched signs\n", __FUNCTION__); | |
| } | |
| #endif | |
| other = next->segment(); | |
| foundSpan = endSpan = next->start(); | |
| otherEnd = next->end(); | |
| } | |
| if (!otherEnd) { | |
| return nullptr; | |
| } | |
| int foundStep = foundSpan->step(otherEnd); | |
| if (*stepPtr != foundStep) { | |
| return set_last(last, endSpan); | |
| } | |
| SkASSERT(*startPtr); | |
| // SkASSERT(otherEnd >= 0); | |
| SkOpSpan* origMin = step < 0 ? origStart->prev() : origStart->upCast(); | |
| SkOpSpan* foundMin = foundSpan->starter(otherEnd); | |
| if (foundMin->windValue() != origMin->windValue() | |
| || foundMin->oppValue() != origMin->oppValue()) { | |
| return set_last(last, endSpan); | |
| } | |
| *startPtr = foundSpan; | |
| *stepPtr = foundStep; | |
| if (minPtr) { | |
| *minPtr = foundMin; | |
| } | |
| return other; | |
| } | |
| // Please keep this in sync with DebugClearVisited() | |
| void SkOpSegment::ClearVisited(SkOpSpanBase* span) { | |
| // reset visited flag back to false | |
| do { | |
| SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; | |
| while ((ptT = ptT->next()) != stopPtT) { | |
| SkOpSegment* opp = ptT->segment(); | |
| opp->resetVisited(); | |
| } | |
| } while (!span->final() && (span = span->upCast()->next())); | |
| } | |
| // Please keep this in sync with debugMissingCoincidence() | |
| // look for pairs of undetected coincident curves | |
| // assumes that segments going in have visited flag clear | |
| // Even though pairs of curves correct detect coincident runs, a run may be missed | |
| // if the coincidence is a product of multiple intersections. For instance, given | |
| // curves A, B, and C: | |
| // A-B intersect at a point 1; A-C and B-C intersect at point 2, so near | |
| // the end of C that the intersection is replaced with the end of C. | |
| // Even though A-B correctly do not detect an intersection at point 2, | |
| // the resulting run from point 1 to point 2 is coincident on A and B. | |
| bool SkOpSegment::missingCoincidence() { | |
| if (this->done()) { | |
| return false; | |
| } | |
| SkOpSpan* prior = nullptr; | |
| SkOpSpanBase* spanBase = &fHead; | |
| bool result = false; | |
| int safetyNet = 1000; | |
| do { | |
| SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; | |
| SkOPASSERT(ptT->span() == spanBase); | |
| while ((ptT = ptT->next()) != spanStopPtT) { | |
| if (!--safetyNet) { | |
| return false; | |
| } | |
| if (ptT->deleted()) { | |
| continue; | |
| } | |
| SkOpSegment* opp = ptT->span()->segment(); | |
| if (opp->done()) { | |
| continue; | |
| } | |
| // when opp is encounted the 1st time, continue; on 2nd encounter, look for coincidence | |
| if (!opp->visited()) { | |
| continue; | |
| } | |
| if (spanBase == &fHead) { | |
| continue; | |
| } | |
| if (ptT->segment() == this) { | |
| continue; | |
| } | |
| SkOpSpan* span = spanBase->upCastable(); | |
| // FIXME?: this assumes that if the opposite segment is coincident then no more | |
| // coincidence needs to be detected. This may not be true. | |
| if (span && span->containsCoincidence(opp)) { | |
| continue; | |
| } | |
| if (spanBase->containsCoinEnd(opp)) { | |
| continue; | |
| } | |
| SkOpPtT* priorPtT = nullptr, * priorStopPtT; | |
| // find prior span containing opp segment | |
| SkOpSegment* priorOpp = nullptr; | |
| SkOpSpan* priorTest = spanBase->prev(); | |
| while (!priorOpp && priorTest) { | |
| priorStopPtT = priorPtT = priorTest->ptT(); | |
| while ((priorPtT = priorPtT->next()) != priorStopPtT) { | |
| if (priorPtT->deleted()) { | |
| continue; | |
| } | |
| SkOpSegment* segment = priorPtT->span()->segment(); | |
| if (segment == opp) { | |
| prior = priorTest; | |
| priorOpp = opp; | |
| break; | |
| } | |
| } | |
| priorTest = priorTest->prev(); | |
| } | |
| if (!priorOpp) { | |
| continue; | |
| } | |
| if (priorPtT == ptT) { | |
| continue; | |
| } | |
| SkOpPtT* oppStart = prior->ptT(); | |
| SkOpPtT* oppEnd = spanBase->ptT(); | |
| bool swapped = priorPtT->fT > ptT->fT; | |
| if (swapped) { | |
| using std::swap; | |
| swap(priorPtT, ptT); | |
| swap(oppStart, oppEnd); | |
| } | |
| SkOpCoincidence* coincidences = this->globalState()->coincidence(); | |
| SkOpPtT* rootPriorPtT = priorPtT->span()->ptT(); | |
| SkOpPtT* rootPtT = ptT->span()->ptT(); | |
| SkOpPtT* rootOppStart = oppStart->span()->ptT(); | |
| SkOpPtT* rootOppEnd = oppEnd->span()->ptT(); | |
| if (coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { | |
| goto swapBack; | |
| } | |
| if (this->testForCoincidence(rootPriorPtT, rootPtT, prior, spanBase, opp)) { | |
| // mark coincidence | |
| #if DEBUG_COINCIDENCE_VERBOSE | |
| SkDebugf("%s coinSpan=%d endSpan=%d oppSpan=%d oppEndSpan=%d\n", __FUNCTION__, | |
| rootPriorPtT->debugID(), rootPtT->debugID(), rootOppStart->debugID(), | |
| rootOppEnd->debugID()); | |
| #endif | |
| if (!coincidences->extend(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)) { | |
| coincidences->add(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd); | |
| } | |
| #if DEBUG_COINCIDENCE | |
| SkASSERT(coincidences->contains(rootPriorPtT, rootPtT, rootOppStart, rootOppEnd)); | |
| #endif | |
| result = true; | |
| } | |
| swapBack: | |
| if (swapped) { | |
| using std::swap; | |
| swap(priorPtT, ptT); | |
| } | |
| } | |
| } while ((spanBase = spanBase->final() ? nullptr : spanBase->upCast()->next())); | |
| ClearVisited(&fHead); | |
| return result; | |
| } | |
| // please keep this in sync with debugMoveMultiples() | |
| // if a span has more than one intersection, merge the other segments' span as needed | |
| bool SkOpSegment::moveMultiples() { | |
| debugValidate(); | |
| SkOpSpanBase* test = &fHead; | |
| do { | |
| int addCount = test->spanAddsCount(); | |
| // FAIL_IF(addCount < 1); | |
| if (addCount <= 1) { | |
| continue; | |
| } | |
| SkOpPtT* startPtT = test->ptT(); | |
| SkOpPtT* testPtT = startPtT; | |
| int safetyHatch = 1000; | |
| do { // iterate through all spans associated with start | |
| if (!--safetyHatch) { | |
| return false; | |
| } | |
| 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() ? nullptr : 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(); | |
| oppTest->mergeMatches(oppSpan); | |
| oppTest->addOpp(oppSpan); | |
| oppSegment->debugValidate(); | |
| goto checkNextSpan; | |
| } | |
| tryNextSpan: | |
| ; | |
| } while (oppTest != oppLast && (oppTest = oppTest->upCast()->next())); | |
| } while ((testPtT = testPtT->next()) != startPtT); | |
| checkNextSpan: | |
| ; | |
| } while ((test = test->final() ? nullptr : test->upCast()->next())); | |
| debugValidate(); | |
| return true; | |
| } | |
| // adjacent spans may have points close by | |
| bool SkOpSegment::spansNearby(const SkOpSpanBase* refSpan, const SkOpSpanBase* checkSpan, | |
| bool* found) const { | |
| const SkOpPtT* refHead = refSpan->ptT(); | |
| const SkOpPtT* checkHead = checkSpan->ptT(); | |
| // if the first pt pair from adjacent spans are far apart, assume that all are far enough apart | |
| if (!SkDPoint::WayRoughlyEqual(refHead->fPt, checkHead->fPt)) { | |
| #if DEBUG_COINCIDENCE | |
| // verify that no combination of points are close | |
| const SkOpPtT* dBugRef = refHead; | |
| do { | |
| const SkOpPtT* dBugCheck = checkHead; | |
| do { | |
| SkOPASSERT(!SkDPoint::ApproximatelyEqual(dBugRef->fPt, dBugCheck->fPt)); | |
| dBugCheck = dBugCheck->next(); | |
| } while (dBugCheck != checkHead); | |
| dBugRef = dBugRef->next(); | |
| } while (dBugRef != refHead); | |
| #endif | |
| *found = false; | |
| return true; | |
| } | |
| // check only unique points | |
| SkScalar distSqBest = SK_ScalarMax; | |
| const SkOpPtT* refBest = nullptr; | |
| const SkOpPtT* checkBest = nullptr; | |
| const SkOpPtT* ref = refHead; | |
| do { | |
| if (ref->deleted()) { | |
| continue; | |
| } | |
| while (ref->ptAlreadySeen(refHead)) { | |
| ref = ref->next(); | |
| if (ref == refHead) { | |
| goto doneCheckingDistance; | |
| } | |
| } | |
| const SkOpPtT* check = checkHead; | |
| const SkOpSegment* refSeg = ref->segment(); | |
| int escapeHatch = 100; // defend against infinite loops | |
| do { | |
| if (check->deleted()) { | |
| continue; | |
| } | |
| while (check->ptAlreadySeen(checkHead)) { | |
| check = check->next(); | |
| if (check == checkHead) { | |
| goto nextRef; | |
| } | |
| } | |
| SkScalar distSq = SkPointPriv::DistanceToSqd(ref->fPt, check->fPt); | |
| if (distSqBest > distSq && (refSeg != check->segment() | |
| || !refSeg->ptsDisjoint(*ref, *check))) { | |
| distSqBest = distSq; | |
| refBest = ref; | |
| checkBest = check; | |
| } | |
| if (--escapeHatch <= 0) { | |
| return false; | |
| } | |
| } while ((check = check->next()) != checkHead); | |
| nextRef: | |
| ; | |
| } while ((ref = ref->next()) != refHead); | |
| doneCheckingDistance: | |
| *found = checkBest && refBest->segment()->match(refBest, checkBest->segment(), checkBest->fT, | |
| checkBest->fPt); | |
| return true; | |
| } | |
| // Please keep this function in sync with debugMoveNearby() | |
| // Move nearby t values and pts so they all hang off the same span. Alignment happens later. | |
| bool SkOpSegment::moveNearby() { | |
| debugValidate(); | |
| // release undeleted spans pointing to this seg that are linked to the primary span | |
| SkOpSpanBase* spanBase = &fHead; | |
| int escapeHatch = 9999; // the largest count for a regular test is 50; for a fuzzer, 500 | |
| do { | |
| SkOpPtT* ptT = spanBase->ptT(); | |
| const SkOpPtT* headPtT = ptT; | |
| while ((ptT = ptT->next()) != headPtT) { | |
| if (!--escapeHatch) { | |
| return false; | |
| } | |
| SkOpSpanBase* test = ptT->span(); | |
| if (ptT->segment() == this && !ptT->deleted() && test != spanBase | |
| && test->ptT() == ptT) { | |
| if (test->final()) { | |
| if (spanBase == &fHead) { | |
| this->clearAll(); | |
| return true; | |
| } | |
| spanBase->upCast()->release(ptT); | |
| } else if (test->prev()) { | |
| test->upCast()->release(headPtT); | |
| } | |
| break; | |
| } | |
| } | |
| spanBase = spanBase->upCast()->next(); | |
| } while (!spanBase->final()); | |
| // This loop looks for adjacent spans which are near by | |
| spanBase = &fHead; | |
| do { // iterate through all spans associated with start | |
| SkOpSpanBase* test = spanBase->upCast()->next(); | |
| bool found; | |
| if (!this->spansNearby(spanBase, test, &found)) { | |
| return false; | |
| } | |
| if (found) { | |
| if (test->final()) { | |
| if (spanBase->prev()) { | |
| test->merge(spanBase->upCast()); | |
| } else { | |
| this->clearAll(); | |
| return true; | |
| } | |
| } else { | |
| spanBase->merge(test->upCast()); | |
| } | |
| } | |
| spanBase = test; | |
| } while (!spanBase->final()); | |
| debugValidate(); | |
| return true; | |
| } | |
| bool SkOpSegment::operand() const { | |
| return fContour->operand(); | |
| } | |
| bool SkOpSegment::oppXor() const { | |
| return fContour->oppXor(); | |
| } | |
| bool SkOpSegment::ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const { | |
| if (fVerb == SkPath::kLine_Verb) { | |
| return false; | |
| } | |
| // quads (and cubics) can loop back to nearly a line so that an opposite curve | |
| // hits in two places with very different t values. | |
| // OPTIMIZATION: curves could be preflighted so that, for example, something like | |
| // 'controls contained by ends' could avoid this check for common curves | |
| // 'ends are extremes in x or y' is cheaper to compute and real-world common | |
| // on the other hand, the below check is relatively inexpensive | |
| double midT = (t1 + t2) / 2; | |
| SkPoint midPt = this->ptAtT(midT); | |
| double seDistSq = std::max(SkPointPriv::DistanceToSqd(pt1, pt2) * 2, FLT_EPSILON * 2); | |
| return SkPointPriv::DistanceToSqd(midPt, pt1) > seDistSq || | |
| SkPointPriv::DistanceToSqd(midPt, pt2) > seDistSq; | |
| } | |
| void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, | |
| int* maxWinding, int* sumWinding) { | |
| int deltaSum = SpanSign(start, end); | |
| *maxWinding = *sumMiWinding; | |
| *sumWinding = *sumMiWinding -= deltaSum; | |
| SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); | |
| } | |
| void SkOpSegment::setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, | |
| int* sumSuWinding, int* maxWinding, int* sumWinding, int* oppMaxWinding, | |
| int* oppSumWinding) { | |
| int deltaSum = SpanSign(start, end); | |
| int oppDeltaSum = OppSign(start, end); | |
| if (operand()) { | |
| *maxWinding = *sumSuWinding; | |
| *sumWinding = *sumSuWinding -= deltaSum; | |
| *oppMaxWinding = *sumMiWinding; | |
| *oppSumWinding = *sumMiWinding -= oppDeltaSum; | |
| } else { | |
| *maxWinding = *sumMiWinding; | |
| *sumWinding = *sumMiWinding -= deltaSum; | |
| *oppMaxWinding = *sumSuWinding; | |
| *oppSumWinding = *sumSuWinding -= oppDeltaSum; | |
| } | |
| SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*sumWinding) <= DEBUG_LIMIT_WIND_SUM); | |
| SkASSERT(!DEBUG_LIMIT_WIND_SUM || SkTAbs(*oppSumWinding) <= DEBUG_LIMIT_WIND_SUM); | |
| } | |
| bool SkOpSegment::sortAngles() { | |
| SkOpSpanBase* span = &this->fHead; | |
| do { | |
| SkOpAngle* fromAngle = span->fromAngle(); | |
| SkOpAngle* toAngle = span->final() ? nullptr : span->upCast()->toAngle(); | |
| if (!fromAngle && !toAngle) { | |
| continue; | |
| } | |
| #if DEBUG_ANGLE | |
| bool wroteAfterHeader = false; | |
| #endif | |
| SkOpAngle* baseAngle = fromAngle; | |
| if (fromAngle && toAngle) { | |
| #if DEBUG_ANGLE | |
| SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), span->t(), | |
| span->debugID()); | |
| wroteAfterHeader = true; | |
| #endif | |
| FAIL_IF(!fromAngle->insert(toAngle)); | |
| } else if (!fromAngle) { | |
| baseAngle = toAngle; | |
| } | |
| SkOpPtT* ptT = span->ptT(), * stopPtT = ptT; | |
| int safetyNet = 1000; | |
| do { | |
| if (!--safetyNet) { | |
| return false; | |
| } | |
| SkOpSpanBase* oSpan = ptT->span(); | |
| if (oSpan == span) { | |
| continue; | |
| } | |
| SkOpAngle* oAngle = oSpan->fromAngle(); | |
| if (oAngle) { | |
| #if DEBUG_ANGLE | |
| if (!wroteAfterHeader) { | |
| SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), | |
| span->t(), span->debugID()); | |
| wroteAfterHeader = true; | |
| } | |
| #endif | |
| if (!oAngle->loopContains(baseAngle)) { | |
| baseAngle->insert(oAngle); | |
| } | |
| } | |
| if (!oSpan->final()) { | |
| oAngle = oSpan->upCast()->toAngle(); | |
| if (oAngle) { | |
| #if DEBUG_ANGLE | |
| if (!wroteAfterHeader) { | |
| SkDebugf("%s [%d] tStart=%1.9g [%d]\n", __FUNCTION__, debugID(), | |
| span->t(), span->debugID()); | |
| wroteAfterHeader = true; | |
| } | |
| #endif | |
| if (!oAngle->loopContains(baseAngle)) { | |
| baseAngle->insert(oAngle); | |
| } | |
| } | |
| } | |
| } while ((ptT = ptT->next()) != stopPtT); | |
| if (baseAngle->loopCount() == 1) { | |
| span->setFromAngle(nullptr); | |
| if (toAngle) { | |
| span->upCast()->setToAngle(nullptr); | |
| } | |
| baseAngle = nullptr; | |
| } | |
| #if DEBUG_SORT | |
| SkASSERT(!baseAngle || baseAngle->loopCount() > 1); | |
| #endif | |
| } while (!span->final() && (span = span->upCast()->next())); | |
| return true; | |
| } | |
| bool SkOpSegment::subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, | |
| SkDCurve* edge) const { | |
| SkASSERT(start != end); | |
| const SkOpPtT& startPtT = *start->ptT(); | |
| const SkOpPtT& endPtT = *end->ptT(); | |
| SkDEBUGCODE(edge->fVerb = fVerb); | |
| edge->fCubic[0].set(startPtT.fPt); | |
| int points = SkPathOpsVerbToPoints(fVerb); | |
| edge->fCubic[points].set(endPtT.fPt); | |
| if (fVerb == SkPath::kLine_Verb) { | |
| return false; | |
| } | |
| double startT = startPtT.fT; | |
| double endT = endPtT.fT; | |
| if ((startT == 0 || endT == 0) && (startT == 1 || endT == 1)) { | |
| // don't compute midpoints if we already have them | |
| if (fVerb == SkPath::kQuad_Verb) { | |
| edge->fLine[1].set(fPts[1]); | |
| return false; | |
| } | |
| if (fVerb == SkPath::kConic_Verb) { | |
| edge->fConic[1].set(fPts[1]); | |
| edge->fConic.fWeight = fWeight; | |
| return false; | |
| } | |
| SkASSERT(fVerb == SkPath::kCubic_Verb); | |
| if (startT == 0) { | |
| edge->fCubic[1].set(fPts[1]); | |
| edge->fCubic[2].set(fPts[2]); | |
| return false; | |
| } | |
| edge->fCubic[1].set(fPts[2]); | |
| edge->fCubic[2].set(fPts[1]); | |
| return false; | |
| } | |
| if (fVerb == SkPath::kQuad_Verb) { | |
| edge->fQuad[1] = SkDQuad::SubDivide(fPts, edge->fQuad[0], edge->fQuad[2], startT, endT); | |
| } else if (fVerb == SkPath::kConic_Verb) { | |
| edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edge->fQuad[2], | |
| startT, endT, &edge->fConic.fWeight); | |
| } else { | |
| SkASSERT(fVerb == SkPath::kCubic_Verb); | |
| SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT, &edge->fCubic[1]); | |
| } | |
| return true; | |
| } | |
| bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, | |
| const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegment* opp) const { | |
| // average t, find mid pt | |
| double midT = (prior->t() + spanBase->t()) / 2; | |
| SkPoint midPt = this->ptAtT(midT); | |
| bool coincident = true; | |
| // if the mid pt is not near either end pt, project perpendicular through opp seg | |
| if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) | |
| && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { | |
| if (priorPtT->span() == ptT->span()) { | |
| return false; | |
| } | |
| coincident = false; | |
| SkIntersections i; | |
| SkDCurve curvePart; | |
| this->subDivide(prior, spanBase, &curvePart); | |
| SkDVector dxdy = (*CurveDDSlopeAtT[fVerb])(curvePart, 0.5f); | |
| SkDPoint partMidPt = (*CurveDDPointAtT[fVerb])(curvePart, 0.5f); | |
| SkDLine ray = {{{midPt.fX, midPt.fY}, {partMidPt.fX + dxdy.fY, partMidPt.fY - dxdy.fX}}}; | |
| SkDCurve oppPart; | |
| opp->subDivide(priorPtT->span(), ptT->span(), &oppPart); | |
| (*CurveDIntersectRay[opp->verb()])(oppPart, ray, &i); | |
| // measure distance and see if it's small enough to denote coincidence | |
| for (int index = 0; index < i.used(); ++index) { | |
| if (!between(0, i[0][index], 1)) { | |
| continue; | |
| } | |
| SkDPoint oppPt = i.pt(index); | |
| if (oppPt.approximatelyDEqual(midPt)) { | |
| // the coincidence can occur at almost any angle | |
| coincident = true; | |
| } | |
| } | |
| } | |
| return coincident; | |
| } | |
| SkOpSpan* SkOpSegment::undoneSpan() { | |
| SkOpSpan* span = &fHead; | |
| SkOpSpanBase* next; | |
| do { | |
| next = span->next(); | |
| if (!span->done()) { | |
| return span; | |
| } | |
| } while (!next->final() && (span = next->upCast())); | |
| return nullptr; | |
| } | |
| int SkOpSegment::updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const { | |
| const SkOpSpan* lesser = start->starter(end); | |
| int oppWinding = lesser->oppSum(); | |
| int oppSpanWinding = SkOpSegment::OppSign(start, end); | |
| if (oppSpanWinding && UseInnerWinding(oppWinding - oppSpanWinding, oppWinding) | |
| && oppWinding != SK_MaxS32) { | |
| oppWinding -= oppSpanWinding; | |
| } | |
| return oppWinding; | |
| } | |
| int SkOpSegment::updateOppWinding(const SkOpAngle* angle) const { | |
| const SkOpSpanBase* startSpan = angle->start(); | |
| const SkOpSpanBase* endSpan = angle->end(); | |
| return updateOppWinding(endSpan, startSpan); | |
| } | |
| int SkOpSegment::updateOppWindingReverse(const SkOpAngle* angle) const { | |
| const SkOpSpanBase* startSpan = angle->start(); | |
| const SkOpSpanBase* endSpan = angle->end(); | |
| return updateOppWinding(startSpan, endSpan); | |
| } | |
| int SkOpSegment::updateWinding(SkOpSpanBase* start, SkOpSpanBase* end) { | |
| SkOpSpan* lesser = start->starter(end); | |
| int winding = lesser->windSum(); | |
| if (winding == SK_MinS32) { | |
| winding = lesser->computeWindSum(); | |
| } | |
| if (winding == SK_MinS32) { | |
| return winding; | |
| } | |
| int spanWinding = SkOpSegment::SpanSign(start, end); | |
| if (winding && UseInnerWinding(winding - spanWinding, winding) | |
| && winding != SK_MaxS32) { | |
| winding -= spanWinding; | |
| } | |
| return winding; | |
| } | |
| int SkOpSegment::updateWinding(SkOpAngle* angle) { | |
| SkOpSpanBase* startSpan = angle->start(); | |
| SkOpSpanBase* endSpan = angle->end(); | |
| return updateWinding(endSpan, startSpan); | |
| } | |
| int SkOpSegment::updateWindingReverse(const SkOpAngle* angle) { | |
| SkOpSpanBase* startSpan = angle->start(); | |
| SkOpSpanBase* endSpan = angle->end(); | |
| return updateWinding(startSpan, endSpan); | |
| } | |
| // OPTIMIZATION: does the following also work, and is it any faster? | |
| // return outerWinding * innerWinding > 0 | |
| // || ((outerWinding + innerWinding < 0) ^ ((outerWinding - innerWinding) < 0))) | |
| bool SkOpSegment::UseInnerWinding(int outerWinding, int innerWinding) { | |
| SkASSERT(outerWinding != SK_MaxS32); | |
| SkASSERT(innerWinding != SK_MaxS32); | |
| int absOut = SkTAbs(outerWinding); | |
| int absIn = SkTAbs(innerWinding); | |
| bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; | |
| return result; | |
| } | |
| int SkOpSegment::windSum(const SkOpAngle* angle) const { | |
| const SkOpSpan* minSpan = angle->start()->starter(angle->end()); | |
| return minSpan->windSum(); | |
| } |