Home | History | Annotate | Download | only in pathops 
      1 /*
      2  * Copyright 2012 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 #ifndef SkOpSpan_DEFINED
      8 #define SkOpSpan_DEFINED
      9 
     10 #include "SkPathOpsDebug.h"
     11 #include "SkPoint.h"
     12 
     13 class SkChunkAlloc;
     14 struct SkOpAngle;
     15 class SkOpContour;
     16 class SkOpGlobalState;
     17 class SkOpSegment;
     18 class SkOpSpanBase;
     19 class SkOpSpan;
     20 
     21 // subset of op span used by terminal span (when t is equal to one)
     22 class SkOpPtT {
     23 public:
     24     enum {
     25         kIsAlias = 1,
     26         kIsDuplicate = 1
     27     };
     28 
     29     void addOpp(SkOpPtT* opp) {
     30         // find the fOpp ptr to opp
     31         SkOpPtT* oppPrev = opp->fNext;
     32         if (oppPrev == this) {
     33             return;
     34         }
     35         while (oppPrev->fNext != opp) {
     36             oppPrev = oppPrev->fNext;
     37              if (oppPrev == this) {
     38                  return;
     39              }
     40         }
     41 
     42         SkOpPtT* oldNext = this->fNext;
     43         SkASSERT(this != opp);
     44         this->fNext = opp;
     45         SkASSERT(oppPrev != oldNext);
     46         oppPrev->fNext = oldNext;
     47     }
     48 
     49     bool alias() const;
     50     SkOpContour* contour() const;
     51 
     52     int debugID() const {
     53         return SkDEBUGRELEASE(fID, -1);
     54     }
     55 
     56     const SkOpAngle* debugAngle(int id) const;
     57     SkOpContour* debugContour(int id);
     58     int debugLoopLimit(bool report) const;
     59     bool debugMatchID(int id) const;
     60     const SkOpPtT* debugPtT(int id) const;
     61     const SkOpSegment* debugSegment(int id) const;
     62     const SkOpSpanBase* debugSpan(int id) const;
     63     SkOpGlobalState* globalState() const;
     64     void debugValidate() const;
     65 
     66     bool deleted() const {
     67         return fDeleted;
     68     }
     69 
     70     bool duplicate() const {
     71         return fDuplicatePt;
     72     }
     73 
     74     void dump() const;  // available to testing only
     75     void dumpAll() const;
     76     void dumpBase() const;
     77 
     78     void init(SkOpSpanBase* , double t, const SkPoint& , bool dup);
     79 
     80     void insert(SkOpPtT* span) {
     81         SkASSERT(span != this);
     82         span->fNext = fNext;
     83         fNext = span;
     84     }
     85 
     86     const SkOpPtT* next() const {
     87         return fNext;
     88     }
     89 
     90     SkOpPtT* next() {
     91         return fNext;
     92     }
     93 
     94     bool onEnd() const;
     95     SkOpPtT* prev();
     96     SkOpPtT* remove();
     97     void removeNext(SkOpPtT* kept);
     98 
     99     const SkOpSegment* segment() const;
    100     SkOpSegment* segment();
    101 
    102     void setDeleted() {
    103         SkASSERT(!fDeleted);
    104         fDeleted = true;
    105     }
    106 
    107     const SkOpSpanBase* span() const {
    108         return fSpan;
    109     }
    110 
    111     SkOpSpanBase* span() {
    112         return fSpan;
    113     }
    114 
    115     double fT;
    116     SkPoint fPt;   // cache of point value at this t
    117 protected:
    118     SkOpSpanBase* fSpan;  // contains winding data
    119     SkOpPtT* fNext;  // intersection on opposite curve or alias on this curve
    120     bool fDeleted;  // set if removed from span list
    121     bool fDuplicatePt;  // set if identical pt is somewhere in the next loop
    122     SkDEBUGCODE(int fID);
    123 };
    124 
    125 class SkOpSpanBase {
    126 public:
    127     void align();
    128 
    129     bool aligned() const {
    130         return fAligned;
    131     }
    132 
    133     void alignEnd(double t, const SkPoint& pt);
    134 
    135     void bumpSpanAdds() {
    136         ++fSpanAdds;
    137     }
    138 
    139     bool chased() const {
    140         return fChased;
    141     }
    142 
    143     void clearCoinEnd() {
    144         SkASSERT(fCoinEnd != this);
    145         fCoinEnd = this;
    146     }
    147 
    148     const SkOpSpanBase* coinEnd() const {
    149         return fCoinEnd;
    150     }
    151 
    152     bool contains(const SkOpSpanBase* ) const;
    153     SkOpPtT* contains(const SkOpSegment* );
    154 
    155     bool containsCoinEnd(const SkOpSpanBase* coin) const {
    156         SkASSERT(this != coin);
    157         const SkOpSpanBase* next = this;
    158         while ((next = next->fCoinEnd) != this) {
    159             if (next == coin) {
    160                 return true;
    161             }
    162         }
    163         return false;
    164     }
    165 
    166     bool containsCoinEnd(const SkOpSegment* ) const;
    167     SkOpContour* contour() const;
    168 
    169     int debugBumpCount() {
    170         return SkDEBUGRELEASE(++fCount, -1);
    171     }
    172 
    173     int debugID() const {
    174         return SkDEBUGRELEASE(fID, -1);
    175     }
    176 
    177     const SkOpAngle* debugAngle(int id) const;
    178     bool debugCoinEndLoopCheck() const;
    179     SkOpContour* debugContour(int id);
    180     const SkOpPtT* debugPtT(int id) const;
    181     const SkOpSegment* debugSegment(int id) const;
    182     const SkOpSpanBase* debugSpan(int id) const;
    183     SkOpGlobalState* globalState() const;
    184     void debugValidate() const;
    185 
    186     bool deleted() const {
    187         return fPtT.deleted();
    188     }
    189 
    190     void dump() const;  // available to testing only
    191     void dumpCoin() const;
    192     void dumpAll() const;
    193     void dumpBase() const;
    194 
    195     bool final() const {
    196         return fPtT.fT == 1;
    197     }
    198 
    199     SkOpAngle* fromAngle() const {
    200         return fFromAngle;
    201     }
    202 
    203     void initBase(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
    204 
    205     void insertCoinEnd(SkOpSpanBase* coin) {
    206         if (containsCoinEnd(coin)) {
    207             SkASSERT(coin->containsCoinEnd(this));
    208             return;
    209         }
    210         debugValidate();
    211         SkASSERT(this != coin);
    212         SkOpSpanBase* coinNext = coin->fCoinEnd;
    213         coin->fCoinEnd = this->fCoinEnd;
    214         this->fCoinEnd = coinNext;
    215         debugValidate();
    216     }
    217 
    218     void merge(SkOpSpan* span);
    219 
    220     SkOpSpan* prev() const {
    221         return fPrev;
    222     }
    223 
    224     const SkPoint& pt() const {
    225         return fPtT.fPt;
    226     }
    227 
    228     const SkOpPtT* ptT() const {
    229         return &fPtT;
    230     }
    231 
    232     SkOpPtT* ptT() {
    233         return &fPtT;
    234     }
    235 
    236     SkOpSegment* segment() const {
    237         return fSegment;
    238     }
    239 
    240     void setChased(bool chased) {
    241         fChased = chased;
    242     }
    243 
    244     SkOpPtT* setCoinEnd(SkOpSpanBase* oldCoinEnd, SkOpSegment* oppSegment);
    245 
    246     void setFromAngle(SkOpAngle* angle) {
    247         fFromAngle = angle;
    248     }
    249 
    250     void setPrev(SkOpSpan* prev) {
    251         fPrev = prev;
    252     }
    253 
    254     bool simple() const {
    255         fPtT.debugValidate();
    256         return fPtT.next()->next() == &fPtT;
    257     }
    258 
    259     int spanAddsCount() const {
    260         return fSpanAdds;
    261     }
    262 
    263     const SkOpSpan* starter(const SkOpSpanBase* end) const {
    264         const SkOpSpanBase* result = t() < end->t() ? this : end;
    265         return result->upCast();
    266     }
    267 
    268     SkOpSpan* starter(SkOpSpanBase* end) {
    269         SkASSERT(this->segment() == end->segment());
    270         SkOpSpanBase* result = t() < end->t() ? this : end;
    271         return result->upCast();
    272     }
    273 
    274     SkOpSpan* starter(SkOpSpanBase** endPtr) {
    275         SkOpSpanBase* end = *endPtr;
    276         SkASSERT(this->segment() == end->segment());
    277         SkOpSpanBase* result;
    278         if (t() < end->t()) {
    279             result = this;
    280         } else {
    281             result = end;
    282             *endPtr = this;
    283         }
    284         return result->upCast();
    285     }
    286 
    287     int step(const SkOpSpanBase* end) const {
    288         return t() < end->t() ? 1 : -1;
    289     }
    290 
    291     double t() const {
    292         return fPtT.fT;
    293     }
    294 
    295     void unaligned() {
    296         fAligned = false;
    297     }
    298 
    299     SkOpSpan* upCast() {
    300         SkASSERT(!final());
    301         return (SkOpSpan*) this;
    302     }
    303 
    304     const SkOpSpan* upCast() const {
    305         SkASSERT(!final());
    306         return (const SkOpSpan*) this;
    307     }
    308 
    309     SkOpSpan* upCastable() {
    310         return final() ? NULL : upCast();
    311     }
    312 
    313     const SkOpSpan* upCastable() const {
    314         return final() ? NULL : upCast();
    315     }
    316 
    317 private:
    318     void alignInner();
    319 
    320 protected:  // no direct access to internals to avoid treating a span base as a span
    321     SkOpPtT fPtT;  // list of points and t values associated with the start of this span
    322     SkOpSegment* fSegment;  // segment that contains this span
    323     SkOpSpanBase* fCoinEnd;  // linked list of coincident spans that end here (may point to itself)
    324     SkOpAngle* fFromAngle;  // points to next angle from span start to end
    325     SkOpSpan* fPrev;  // previous intersection point
    326     int fSpanAdds;  // number of times intersections have been added to span
    327     bool fAligned;
    328     bool fChased;  // set after span has been added to chase array
    329     SkDEBUGCODE(int fCount);  // number of pt/t pairs added
    330     SkDEBUGCODE(int fID);
    331 };
    332 
    333 class SkOpSpan : public SkOpSpanBase {
    334 public:
    335     bool clearCoincident() {
    336         SkASSERT(!final());
    337         if (fCoincident == this) {
    338             return false;
    339         }
    340         fCoincident = this;
    341         return true;
    342     }
    343 
    344     int computeWindSum();
    345     bool containsCoincidence(const SkOpSegment* ) const;
    346 
    347     bool containsCoincidence(const SkOpSpan* coin) const {
    348         SkASSERT(this != coin);
    349         const SkOpSpan* next = this;
    350         while ((next = next->fCoincident) != this) {
    351             if (next == coin) {
    352                 return true;
    353             }
    354         }
    355         return false;
    356     }
    357 
    358     bool debugCoinLoopCheck() const;
    359     void detach(SkOpPtT* );
    360 
    361     bool done() const {
    362         SkASSERT(!final());
    363         return fDone;
    364     }
    365 
    366     void dumpCoin() const;
    367     bool dumpSpan() const;
    368     void init(SkOpSegment* parent, SkOpSpan* prev, double t, const SkPoint& pt);
    369 
    370     void insertCoincidence(SkOpSpan* coin) {
    371         if (containsCoincidence(coin)) {
    372             SkASSERT(coin->containsCoincidence(this));
    373             return;
    374         }
    375         debugValidate();
    376         SkASSERT(this != coin);
    377         SkOpSpan* coinNext = coin->fCoincident;
    378         coin->fCoincident = this->fCoincident;
    379         this->fCoincident = coinNext;
    380         debugValidate();
    381     }
    382 
    383     bool isCanceled() const {
    384         SkASSERT(!final());
    385         return fWindValue == 0 && fOppValue == 0;
    386     }
    387 
    388     bool isCoincident() const {
    389         SkASSERT(!final());
    390         return fCoincident != this;
    391     }
    392 
    393     SkOpSpanBase* next() const {
    394         SkASSERT(!final());
    395         return fNext;
    396     }
    397 
    398     int oppSum() const {
    399         SkASSERT(!final());
    400         return fOppSum;
    401     }
    402 
    403     int oppValue() const {
    404         SkASSERT(!final());
    405         return fOppValue;
    406     }
    407 
    408     SkOpPtT* setCoinStart(SkOpSpan* oldCoinStart, SkOpSegment* oppSegment);
    409 
    410     void setDone(bool done) {
    411         SkASSERT(!final());
    412         fDone = done;
    413     }
    414 
    415     void setNext(SkOpSpanBase* nextT) {
    416         SkASSERT(!final());
    417         fNext = nextT;
    418     }
    419 
    420     void setOppSum(int oppSum);
    421 
    422     void setOppValue(int oppValue) {
    423         SkASSERT(!final());
    424         SkASSERT(fOppSum == SK_MinS32);
    425         fOppValue = oppValue;
    426     }
    427 
    428     void setToAngle(SkOpAngle* angle) {
    429         SkASSERT(!final());
    430         fToAngle = angle;
    431     }
    432 
    433     void setWindSum(int windSum);
    434 
    435     void setWindValue(int windValue) {
    436         SkASSERT(!final());
    437         SkASSERT(windValue >= 0);
    438         SkASSERT(fWindSum == SK_MinS32);
    439         fWindValue = windValue;
    440     }
    441 
    442     bool sortableTop(SkOpContour* );
    443 
    444     SkOpAngle* toAngle() const {
    445         SkASSERT(!final());
    446         return fToAngle;
    447     }
    448 
    449     int windSum() const {
    450         SkASSERT(!final());
    451         return fWindSum;
    452     }
    453 
    454     int windValue() const {
    455         SkASSERT(!final());
    456         return fWindValue;
    457     }
    458 
    459 private:  // no direct access to internals to avoid treating a span base as a span
    460     SkOpSpan* fCoincident;  // linked list of spans coincident with this one (may point to itself)
    461     SkOpAngle* fToAngle;  // points to next angle from span start to end
    462     SkOpSpanBase* fNext;  // next intersection point
    463     int fWindSum;  // accumulated from contours surrounding this one.
    464     int fOppSum;  // for binary operators: the opposite winding sum
    465     int fWindValue;  // 0 == canceled; 1 == normal; >1 == coincident
    466     int fOppValue;  // normally 0 -- when binary coincident edges combine, opp value goes here
    467     int fTopTTry; // specifies direction and t value to try next
    468     bool fDone;  // if set, this span to next higher T has been processed
    469 };
    470 
    471 #endif
    472