| /* |
| * Copyright 2012 Google Inc. |
| * |
| * Use of this source code is governed by a BSD-style license that can be |
| * found in the LICENSE file. |
| */ |
| #ifndef SkOpSpan_DEFINED |
| #define SkOpSpan_DEFINED |
| |
| #include "include/core/SkPoint.h" |
| #include "src/pathops/SkPathOpsDebug.h" |
| #include "src/pathops/SkPathOpsTypes.h" |
| |
| class SkArenaAlloc; |
| class SkOpAngle; |
| class SkOpContour; |
| class SkOpGlobalState; |
| class SkOpSegment; |
| class SkOpSpanBase; |
| class SkOpSpan; |
| struct SkPathOpsBounds; |
| |
| // subset of op span used by terminal span (when t is equal to one) |
| class SkOpPtT { |
| public: |
| enum { |
| kIsAlias = 1, |
| kIsDuplicate = 1 |
| }; |
| |
| const SkOpPtT* active() const; |
| |
| // please keep in sync with debugAddOpp() |
| void addOpp(SkOpPtT* opp, SkOpPtT* oppPrev) { |
| SkOpPtT* oldNext = this->fNext; |
| SkASSERT(this != opp); |
| this->fNext = opp; |
| SkASSERT(oppPrev != oldNext); |
| oppPrev->fNext = oldNext; |
| } |
| |
| bool alias() const; |
| bool coincident() const { return fCoincident; } |
| bool contains(const SkOpPtT* ) const; |
| bool contains(const SkOpSegment*, const SkPoint& ) const; |
| bool contains(const SkOpSegment*, double t) const; |
| const SkOpPtT* contains(const SkOpSegment* ) const; |
| SkOpContour* contour() const; |
| |
| int debugID() const { |
| return SkDEBUGRELEASE(fID, -1); |
| } |
| |
| void debugAddOpp(const SkOpPtT* opp, const SkOpPtT* oppPrev) const; |
| const SkOpAngle* debugAngle(int id) const; |
| const SkOpCoincidence* debugCoincidence() const; |
| bool debugContains(const SkOpPtT* ) const; |
| const SkOpPtT* debugContains(const SkOpSegment* check) const; |
| SkOpContour* debugContour(int id) const; |
| const SkOpPtT* debugEnder(const SkOpPtT* end) const; |
| int debugLoopLimit(bool report) const; |
| bool debugMatchID(int id) const; |
| const SkOpPtT* debugOppPrev(const SkOpPtT* opp) const; |
| const SkOpPtT* debugPtT(int id) const; |
| void debugResetCoinT() const; |
| const SkOpSegment* debugSegment(int id) const; |
| void debugSetCoinT(int ) const; |
| const SkOpSpanBase* debugSpan(int id) const; |
| void debugValidate() const; |
| |
| bool deleted() const { |
| return fDeleted; |
| } |
| |
| bool duplicate() const { |
| return fDuplicatePt; |
| } |
| |
| void dump() const; // available to testing only |
| void dumpAll() const; |
| void dumpBase() const; |
| |
| const SkOpPtT* find(const SkOpSegment* ) const; |
| SkOpGlobalState* globalState() const; |
| void init(SkOpSpanBase* , double t, const SkPoint& , bool dup); |
| |
| void insert(SkOpPtT* span) { |
| SkASSERT(span != this); |
| span->fNext = fNext; |
| fNext = span; |
| } |
| |
| const SkOpPtT* next() const { |
| return fNext; |
| } |
| |
| SkOpPtT* next() { |
| return fNext; |
| } |
| |
| bool onEnd() const; |
| |
| // returns nullptr if this is already in the opp ptT loop |
| SkOpPtT* oppPrev(const SkOpPtT* opp) const { |
| // find the fOpp ptr to opp |
| SkOpPtT* oppPrev = opp->fNext; |
| if (oppPrev == this) { |
| return nullptr; |
| } |
| while (oppPrev->fNext != opp) { |
| oppPrev = oppPrev->fNext; |
| if (oppPrev == this) { |
| return nullptr; |
| } |
| } |
| return oppPrev; |
| } |
| |
| static bool Overlaps(const SkOpPtT* s1, const SkOpPtT* e1, const SkOpPtT* s2, |
| const SkOpPtT* e2, const SkOpPtT** sOut, const SkOpPtT** eOut) { |
| const SkOpPtT* start1 = s1->fT < e1->fT ? s1 : e1; |
| const SkOpPtT* start2 = s2->fT < e2->fT ? s2 : e2; |
| *sOut = between(s1->fT, start2->fT, e1->fT) ? start2 |
| : between(s2->fT, start1->fT, e2->fT) ? start1 : nullptr; |
| const SkOpPtT* end1 = s1->fT < e1->fT ? e1 : s1; |
| const SkOpPtT* end2 = s2->fT < e2->fT ? e2 : s2; |
| *eOut = between(s1->fT, end2->fT, e1->fT) ? end2 |
| : between(s2->fT, end1->fT, e2->fT) ? end1 : nullptr; |
| if (*sOut == *eOut) { |
| SkOPOBJASSERT(s1, start1->fT >= end2->fT || start2->fT >= end1->fT); |
| return false; |
| } |
| SkASSERT(!*sOut || *sOut != *eOut); |
| return *sOut && *eOut; |
| } |
| |
| bool ptAlreadySeen(const SkOpPtT* head) const; |
| SkOpPtT* prev(); |
| |
| const SkOpSegment* segment() const; |
| SkOpSegment* segment(); |
| |
| void setCoincident() const { |
| SkOPASSERT(!fDeleted); |
| fCoincident = true; |
| } |
| |
| void setDeleted(); |
| |
| void setSpan(const SkOpSpanBase* span) { |
| fSpan = const_cast<SkOpSpanBase*>(span); |
| } |
| |
| const SkOpSpanBase* span() const { |
| return fSpan; |
| } |
| |
| SkOpSpanBase* span() { |
| return fSpan; |
| } |
| |
| const SkOpPtT* starter(const SkOpPtT* end) const { |
| return fT < end->fT ? this : end; |
| } |
| |
| double fT; |
| SkPoint fPt; // cache of point value at this t |
| protected: |
| SkOpSpanBase* fSpan; // contains winding data |
| SkOpPtT* fNext; // intersection on opposite curve or alias on this curve |
| bool fDeleted; // set if removed from span list |
| bool fDuplicatePt; // set if identical pt is somewhere in the next loop |
| // below mutable since referrer is otherwise always const |
| mutable bool fCoincident; // set if at some point a coincident span pointed here |
| SkDEBUGCODE(int fID); |
| }; |
| |
| class SkOpSpanBase { |
| public: |
| enum class Collapsed { |
| kNo, |
| kYes, |
| kError, |
| }; |
| |
| bool addOpp(SkOpSpanBase* opp); |
| |
| void bumpSpanAdds() { |
| ++fSpanAdds; |
| } |
| |
| bool chased() const { |
| return fChased; |
| } |
| |
| void checkForCollapsedCoincidence(); |
| |
| const SkOpSpanBase* coinEnd() const { |
| return fCoinEnd; |
| } |
| |
| Collapsed collapsed(double s, double e) const; |
| bool contains(const SkOpSpanBase* ) const; |
| const SkOpPtT* contains(const SkOpSegment* ) const; |
| |
| bool containsCoinEnd(const SkOpSpanBase* coin) const { |
| SkASSERT(this != coin); |
| const SkOpSpanBase* next = this; |
| while ((next = next->fCoinEnd) != this) { |
| if (next == coin) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| bool containsCoinEnd(const SkOpSegment* ) const; |
| SkOpContour* contour() const; |
| |
| int debugBumpCount() { |
| return SkDEBUGRELEASE(++fCount, -1); |
| } |
| |
| int debugID() const { |
| return SkDEBUGRELEASE(fID, -1); |
| } |
| |
| #if DEBUG_COIN |
| void debugAddOpp(SkPathOpsDebug::GlitchLog* , const SkOpSpanBase* opp) const; |
| #endif |
| bool debugAlignedEnd(double t, const SkPoint& pt) const; |
| bool debugAlignedInner() const; |
| const SkOpAngle* debugAngle(int id) const; |
| #if DEBUG_COIN |
| void debugCheckForCollapsedCoincidence(SkPathOpsDebug::GlitchLog* ) const; |
| #endif |
| const SkOpCoincidence* debugCoincidence() const; |
| bool debugCoinEndLoopCheck() const; |
| SkOpContour* debugContour(int id) const; |
| #ifdef SK_DEBUG |
| bool debugDeleted() const { return fDebugDeleted; } |
| #endif |
| #if DEBUG_COIN |
| void debugInsertCoinEnd(SkPathOpsDebug::GlitchLog* , |
| const SkOpSpanBase* ) const; |
| void debugMergeMatches(SkPathOpsDebug::GlitchLog* log, |
| const SkOpSpanBase* opp) const; |
| #endif |
| const SkOpPtT* debugPtT(int id) const; |
| void debugResetCoinT() const; |
| const SkOpSegment* debugSegment(int id) const; |
| void debugSetCoinT(int ) const; |
| #ifdef SK_DEBUG |
| void debugSetDeleted() { fDebugDeleted = true; } |
| #endif |
| const SkOpSpanBase* debugSpan(int id) const; |
| const SkOpSpan* debugStarter(SkOpSpanBase const** endPtr) const; |
| SkOpGlobalState* globalState() const; |
| void debugValidate() const; |
| |
| bool deleted() const { |
| return fPtT.deleted(); |
| } |
| |
| void dump() const; // available to testing only |
| void dumpCoin() const; |
| void dumpAll() const; |
| void dumpBase() const; |
| void dumpHead() const; |
| |
| bool final() const { |
| return fPtT.fT == 1; |
| } |
| |
| SkOpAngle* fromAngle() const { |
| return fFromAngle; |
| } |
| |
| void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt); |
| |
| // Please keep this in sync with debugInsertCoinEnd() |
| void insertCoinEnd(SkOpSpanBase* coin) { |
| if (containsCoinEnd(coin)) { |
| SkASSERT(coin->containsCoinEnd(this)); |
| return; |
| } |
| debugValidate(); |
| SkASSERT(this != coin); |
| SkOpSpanBase* coinNext = coin->fCoinEnd; |
| coin->fCoinEnd = this->fCoinEnd; |
| this->fCoinEnd = coinNext; |
| debugValidate(); |
| } |
| |
| void merge(SkOpSpan* span); |
| bool mergeMatches(SkOpSpanBase* opp); |
| |
| const SkOpSpan* prev() const { |
| return fPrev; |
| } |
| |
| SkOpSpan* prev() { |
| return fPrev; |
| } |
| |
| const SkPoint& pt() const { |
| return fPtT.fPt; |
| } |
| |
| const SkOpPtT* ptT() const { |
| return &fPtT; |
| } |
| |
| SkOpPtT* ptT() { |
| return &fPtT; |
| } |
| |
| SkOpSegment* segment() const { |
| return fSegment; |
| } |
| |
| void setAligned() { |
| fAligned = true; |
| } |
| |
| void setChased(bool chased) { |
| fChased = chased; |
| } |
| |
| void setFromAngle(SkOpAngle* angle) { |
| fFromAngle = angle; |
| } |
| |
| void setPrev(SkOpSpan* prev) { |
| fPrev = prev; |
| } |
| |
| bool simple() const { |
| fPtT.debugValidate(); |
| 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(); |
| } |
| |
| SkOpSpan* starter(SkOpSpanBase* end) { |
| SkASSERT(this->segment() == end->segment()); |
| SkOpSpanBase* result = t() < end->t() ? this : end; |
| return result->upCast(); |
| } |
| |
| SkOpSpan* starter(SkOpSpanBase** endPtr) { |
| SkOpSpanBase* end = *endPtr; |
| SkASSERT(this->segment() == end->segment()); |
| SkOpSpanBase* result; |
| if (t() < end->t()) { |
| result = this; |
| } else { |
| result = end; |
| *endPtr = this; |
| } |
| return result->upCast(); |
| } |
| |
| int step(const SkOpSpanBase* end) const { |
| return t() < end->t() ? 1 : -1; |
| } |
| |
| double t() const { |
| return fPtT.fT; |
| } |
| |
| void unaligned() { |
| fAligned = false; |
| } |
| |
| SkOpSpan* upCast() { |
| SkASSERT(!final()); |
| return (SkOpSpan*) this; |
| } |
| |
| const SkOpSpan* upCast() const { |
| SkOPASSERT(!final()); |
| return (const SkOpSpan*) this; |
| } |
| |
| SkOpSpan* upCastable() { |
| return final() ? nullptr : upCast(); |
| } |
| |
| const SkOpSpan* upCastable() const { |
| return final() ? nullptr : upCast(); |
| } |
| |
| private: |
| void alignInner(); |
| |
| protected: // no direct access to internals to avoid treating a span base as a span |
| SkOpPtT fPtT; // list of points and t values associated with the start of this span |
| SkOpSegment* fSegment; // segment that contains this span |
| 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 |
| SkDEBUGCODE(int fID); |
| SkDEBUGCODE(bool fDebugDeleted); // set when span was merged with another span |
| }; |
| |
| class SkOpSpan : public SkOpSpanBase { |
| public: |
| bool alreadyAdded() const { |
| if (fAlreadyAdded) { |
| return true; |
| } |
| return false; |
| } |
| |
| bool clearCoincident() { |
| SkASSERT(!final()); |
| if (fCoincident == this) { |
| return false; |
| } |
| fCoincident = this; |
| return true; |
| } |
| |
| int computeWindSum(); |
| bool containsCoincidence(const SkOpSegment* ) const; |
| |
| bool containsCoincidence(const SkOpSpan* coin) const { |
| SkASSERT(this != coin); |
| const SkOpSpan* next = this; |
| while ((next = next->fCoincident) != this) { |
| if (next == coin) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| bool debugCoinLoopCheck() const; |
| #if DEBUG_COIN |
| void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* , const SkOpSpan* ) const; |
| void debugInsertCoincidence(SkPathOpsDebug::GlitchLog* , |
| const SkOpSegment* , bool flipped, bool ordered) const; |
| #endif |
| void dumpCoin() const; |
| bool dumpSpan() const; |
| |
| bool done() const { |
| SkASSERT(!final()); |
| return fDone; |
| } |
| |
| void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt); |
| bool insertCoincidence(const SkOpSegment* , bool flipped, bool ordered); |
| |
| // Please keep this in sync with debugInsertCoincidence() |
| void insertCoincidence(SkOpSpan* coin) { |
| if (containsCoincidence(coin)) { |
| SkASSERT(coin->containsCoincidence(this)); |
| return; |
| } |
| debugValidate(); |
| SkASSERT(this != coin); |
| SkOpSpan* coinNext = coin->fCoincident; |
| coin->fCoincident = this->fCoincident; |
| this->fCoincident = coinNext; |
| debugValidate(); |
| } |
| |
| bool isCanceled() const { |
| SkASSERT(!final()); |
| return fWindValue == 0 && fOppValue == 0; |
| } |
| |
| bool isCoincident() const { |
| SkASSERT(!final()); |
| return fCoincident != this; |
| } |
| |
| void markAdded() { |
| fAlreadyAdded = true; |
| } |
| |
| SkOpSpanBase* next() const { |
| SkASSERT(!final()); |
| return fNext; |
| } |
| |
| int oppSum() const { |
| SkASSERT(!final()); |
| return fOppSum; |
| } |
| |
| int oppValue() const { |
| SkASSERT(!final()); |
| return fOppValue; |
| } |
| |
| void release(const SkOpPtT* ); |
| |
| SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment); |
| |
| void setDone(bool done) { |
| SkASSERT(!final()); |
| fDone = done; |
| } |
| |
| void setNext(SkOpSpanBase* nextT) { |
| SkASSERT(!final()); |
| fNext = nextT; |
| } |
| |
| void setOppSum(int oppSum); |
| |
| void setOppValue(int oppValue) { |
| SkASSERT(!final()); |
| SkASSERT(fOppSum == SK_MinS32); |
| SkOPASSERT(!oppValue || !fDone); |
| fOppValue = oppValue; |
| } |
| |
| void setToAngle(SkOpAngle* angle) { |
| SkASSERT(!final()); |
| fToAngle = angle; |
| } |
| |
| void setWindSum(int windSum); |
| |
| void setWindValue(int windValue) { |
| SkASSERT(!final()); |
| SkASSERT(windValue >= 0); |
| SkASSERT(fWindSum == SK_MinS32); |
| SkOPASSERT(!windValue || !fDone); |
| fWindValue = windValue; |
| } |
| |
| bool sortableTop(SkOpContour* ); |
| |
| SkOpAngle* toAngle() const { |
| SkASSERT(!final()); |
| return fToAngle; |
| } |
| |
| int windSum() const { |
| SkASSERT(!final()); |
| return fWindSum; |
| } |
| |
| int windValue() const { |
| SkOPASSERT(!final()); |
| return fWindValue; |
| } |
| |
| private: // no direct access to internals to avoid treating a span base as a span |
| SkOpSpan* fCoincident; // linked list of spans coincident with this one (may point to itself) |
| SkOpAngle* fToAngle; // points to next angle from span start to end |
| SkOpSpanBase* fNext; // next intersection point |
| int fWindSum; // accumulated from contours surrounding this one. |
| int fOppSum; // for binary operators: the opposite winding sum |
| int fWindValue; // 0 == canceled; 1 == normal; >1 == coincident |
| int fOppValue; // normally 0 -- when binary coincident edges combine, opp value goes here |
| int fTopTTry; // specifies direction and t value to try next |
| bool fDone; // if set, this span to next higher T has been processed |
| bool fAlreadyAdded; |
| }; |
| |
| #endif |