123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578 |
- /*
- * 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
|