Home | History | Annotate | Download | only in pathops 
      1 /*
      2  * Copyright 2013 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 SkOpCoincidence_DEFINED
      8 #define SkOpCoincidence_DEFINED
      9 
     10 #include "SkTDArray.h"
     11 #include "SkOpTAllocator.h"
     12 #include "SkOpSpan.h"
     13 #include "SkPathOpsTypes.h"
     14 
     15 class SkOpPtT;
     16 class SkOpSpanBase;
     17 
     18 class SkCoincidentSpans {
     19 public:
     20     const SkOpPtT* coinPtTEnd() const;
     21     const SkOpPtT* coinPtTStart() const;
     22 
     23     // These return non-const pointers so that, as copies, they can be added
     24     // to a new span pair
     25     SkOpPtT* coinPtTEndWritable() const { return const_cast<SkOpPtT*>(fCoinPtTEnd); }
     26     SkOpPtT* coinPtTStartWritable() const { return const_cast<SkOpPtT*>(fCoinPtTStart); }
     27 
     28     bool collapsed(const SkOpPtT* ) const;
     29     bool contains(const SkOpPtT* s, const SkOpPtT* e) const;
     30     void correctEnds();
     31     void correctOneEnd(const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
     32                        void (SkCoincidentSpans::* setEnd)(const SkOpPtT* ptT) );
     33 
     34 #if DEBUG_COIN
     35     void debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const;
     36     void debugCorrectOneEnd(SkPathOpsDebug::GlitchLog* log,
     37                             const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
     38                             void (SkCoincidentSpans::* setEnd)(const SkOpPtT* ptT) const) const;
     39     bool debugExpand(SkPathOpsDebug::GlitchLog* log) const;
     40 #endif
     41 
     42     const char* debugID() const {
     43 #if DEBUG_COIN
     44         return fGlobalState->debugCoinDictEntry().fFunctionName;
     45 #else
     46         return nullptr;
     47 #endif
     48     }
     49 
     50     void debugShow() const;
     51 #ifdef SK_DEBUG
     52     void debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
     53             const SkOpGlobalState* debugState) const;
     54 #endif
     55     void dump() const;
     56     bool expand();
     57     bool extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
     58                 const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd);
     59     bool flipped() const { return fOppPtTStart->fT > fOppPtTEnd->fT; }
     60     SkDEBUGCODE(SkOpGlobalState* globalState() { return fGlobalState; })
     61 
     62     void init(SkDEBUGCODE(SkOpGlobalState* globalState)) {
     63         sk_bzero(this, sizeof(*this));
     64         SkDEBUGCODE(fGlobalState = globalState);
     65     }
     66 
     67     SkCoincidentSpans* next() { return fNext; }
     68     const SkCoincidentSpans* next() const { return fNext; }
     69     SkCoincidentSpans** nextPtr() { return &fNext; }
     70     const SkOpPtT* oppPtTStart() const;
     71     const SkOpPtT* oppPtTEnd() const;
     72     // These return non-const pointers so that, as copies, they can be added
     73     // to a new span pair
     74     SkOpPtT* oppPtTStartWritable() const { return const_cast<SkOpPtT*>(fOppPtTStart); }
     75     SkOpPtT* oppPtTEndWritable() const { return const_cast<SkOpPtT*>(fOppPtTEnd); }
     76     bool ordered(bool* result) const;
     77 
     78     void set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
     79             const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd);
     80 
     81     void setCoinPtTEnd(const SkOpPtT* ptT) {
     82         SkOPASSERT(ptT == ptT->span()->ptT());
     83         SkOPASSERT(!fCoinPtTStart || ptT->fT != fCoinPtTStart->fT);
     84         SkASSERT(!fCoinPtTStart || fCoinPtTStart->segment() == ptT->segment());
     85         fCoinPtTEnd = ptT;
     86         ptT->setCoincident();
     87     }
     88 
     89     void setCoinPtTStart(const SkOpPtT* ptT) {
     90         SkOPASSERT(ptT == ptT->span()->ptT());
     91         SkOPASSERT(!fCoinPtTEnd || ptT->fT != fCoinPtTEnd->fT);
     92         SkASSERT(!fCoinPtTEnd || fCoinPtTEnd->segment() == ptT->segment());
     93         fCoinPtTStart = ptT;
     94         ptT->setCoincident();
     95     }
     96 
     97     void setEnds(const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTEnd) {
     98         this->setCoinPtTEnd(coinPtTEnd);
     99         this->setOppPtTEnd(oppPtTEnd);
    100     }
    101 
    102     void setOppPtTEnd(const SkOpPtT* ptT) {
    103         SkOPASSERT(ptT == ptT->span()->ptT());
    104         SkOPASSERT(!fOppPtTStart || ptT->fT != fOppPtTStart->fT);
    105         SkASSERT(!fOppPtTStart || fOppPtTStart->segment() == ptT->segment());
    106         fOppPtTEnd = ptT;
    107         ptT->setCoincident();
    108     }
    109 
    110     void setOppPtTStart(const SkOpPtT* ptT) {
    111         SkOPASSERT(ptT == ptT->span()->ptT());
    112         SkOPASSERT(!fOppPtTEnd || ptT->fT != fOppPtTEnd->fT);
    113         SkASSERT(!fOppPtTEnd || fOppPtTEnd->segment() == ptT->segment());
    114         fOppPtTStart = ptT;
    115         ptT->setCoincident();
    116     }
    117 
    118     void setStarts(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) {
    119         this->setCoinPtTStart(coinPtTStart);
    120         this->setOppPtTStart(oppPtTStart);
    121     }
    122 
    123     void setNext(SkCoincidentSpans* next) { fNext = next; }
    124 
    125 private:
    126     SkCoincidentSpans* fNext;
    127     const SkOpPtT* fCoinPtTStart;
    128     const SkOpPtT* fCoinPtTEnd;
    129     const SkOpPtT* fOppPtTStart;
    130     const SkOpPtT* fOppPtTEnd;
    131     SkDEBUGCODE(SkOpGlobalState* fGlobalState);
    132 };
    133 
    134 class SkOpCoincidence {
    135 public:
    136     SkOpCoincidence(SkOpGlobalState* globalState)
    137         : fHead(nullptr)
    138         , fTop(nullptr)
    139         , fGlobalState(globalState)
    140         , fContinue(false)
    141         , fSpanDeleted(false)
    142         , fPtAllocated(false)
    143         , fCoinExtended(false)
    144         , fSpanMerged(false) {
    145         globalState->setCoincidence(this);
    146     }
    147 
    148     void add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
    149              SkOpPtT* oppPtTEnd);
    150     bool addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS());
    151     bool addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS());
    152     bool addMissing(bool* added  DEBUG_COIN_DECLARE_PARAMS());
    153     bool apply(DEBUG_COIN_DECLARE_ONLY_PARAMS());
    154     bool contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
    155                   const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const;
    156     void correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS());
    157 
    158 #if DEBUG_COIN
    159     void debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log) const;
    160     void debugAddExpanded(SkPathOpsDebug::GlitchLog* ) const;
    161     void debugAddMissing(SkPathOpsDebug::GlitchLog* , bool* added) const;
    162     void debugAddOrOverlap(SkPathOpsDebug::GlitchLog* log,
    163                            const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
    164                            double coinTs, double coinTe, double oppTs, double oppTe,
    165                            bool* added) const;
    166 #endif
    167 
    168     const SkOpAngle* debugAngle(int id) const {
    169         return SkDEBUGRELEASE(fGlobalState->debugAngle(id), nullptr);
    170     }
    171 
    172     void debugCheckBetween() const;
    173 
    174 #if DEBUG_COIN
    175     void debugCheckValid(SkPathOpsDebug::GlitchLog* log) const;
    176 #endif
    177 
    178     SkOpContour* debugContour(int id) const {
    179         return SkDEBUGRELEASE(fGlobalState->debugContour(id), nullptr);
    180     }
    181 
    182 #if DEBUG_COIN
    183     void debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const;
    184     bool debugExpand(SkPathOpsDebug::GlitchLog* ) const;
    185     void debugMark(SkPathOpsDebug::GlitchLog* ) const;
    186     void debugMarkCollapsed(SkPathOpsDebug::GlitchLog* ,
    187                             const SkCoincidentSpans* coin, const SkOpPtT* test) const;
    188     void debugMarkCollapsed(SkPathOpsDebug::GlitchLog* , const SkOpPtT* test) const;
    189 #endif
    190 
    191     const SkOpPtT* debugPtT(int id) const {
    192         return SkDEBUGRELEASE(fGlobalState->debugPtT(id), nullptr);
    193     }
    194 
    195     const SkOpSegment* debugSegment(int id) const {
    196         return SkDEBUGRELEASE(fGlobalState->debugSegment(id), nullptr);
    197     }
    198 
    199 #if DEBUG_COIN
    200     void debugRelease(SkPathOpsDebug::GlitchLog* , const SkCoincidentSpans* ,
    201                       const SkCoincidentSpans* ) const;
    202     void debugRelease(SkPathOpsDebug::GlitchLog* , const SkOpSegment* ) const;
    203 #endif
    204     void debugShowCoincidence() const;
    205 
    206     const SkOpSpanBase* debugSpan(int id) const {
    207         return SkDEBUGRELEASE(fGlobalState->debugSpan(id), nullptr);
    208     }
    209 
    210     void debugValidate() const;
    211     void dump() const;
    212     bool expand(DEBUG_COIN_DECLARE_ONLY_PARAMS());
    213     bool extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart,
    214                 const SkOpPtT* oppPtTEnd);
    215     bool findOverlaps(SkOpCoincidence*  DEBUG_COIN_DECLARE_PARAMS()) const;
    216     void fixUp(SkOpPtT* deleted, const SkOpPtT* kept);
    217 
    218     SkOpGlobalState* globalState() {
    219         return fGlobalState;
    220     }
    221 
    222     const SkOpGlobalState* globalState() const {
    223         return fGlobalState;
    224     }
    225 
    226     bool isEmpty() const {
    227         return !fHead && !fTop;
    228     }
    229 
    230     bool mark(DEBUG_COIN_DECLARE_ONLY_PARAMS());
    231     void markCollapsed(SkOpPtT* );
    232 
    233     static bool Ordered(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) {
    234       return Ordered(coinPtTStart->segment(), oppPtTStart->segment());
    235     }
    236 
    237     static bool Ordered(const SkOpSegment* coin, const SkOpSegment* opp);
    238     void release(const SkOpSegment* );
    239     void releaseDeleted();
    240 
    241 private:
    242     void add(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart,
    243              const SkOpPtT* oppPtTEnd) {
    244         this->add(const_cast<SkOpPtT*>(coinPtTStart), const_cast<SkOpPtT*>(coinPtTEnd),
    245             const_cast<SkOpPtT*>(oppPtTStart), const_cast<SkOpPtT*>(oppPtTEnd));
    246     }
    247 
    248     bool addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan);
    249     bool addEndMovedSpans(const SkOpPtT* ptT);
    250 
    251     bool addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
    252                       double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg,
    253                       bool* added
    254                       SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e));
    255     bool addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
    256                       double coinTs, double coinTe, double oppTs, double oppTe, bool* added);
    257     bool addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
    258                     const SkOpSegment* seg2, const SkOpSegment* seg2o,
    259                     const SkOpPtT* overS, const SkOpPtT* overE);
    260     bool checkOverlap(SkCoincidentSpans* check,
    261                       const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
    262                       double coinTs, double coinTe, double oppTs, double oppTe,
    263                       SkTDArray<SkCoincidentSpans*>* overlaps) const;
    264     bool contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const;
    265     bool contains(const SkCoincidentSpans* coin, const SkOpSegment* seg,
    266                   const SkOpSegment* opp, double oppT) const;
    267 #if DEBUG_COIN
    268     void debugAddIfMissing(SkPathOpsDebug::GlitchLog* ,
    269                            const SkCoincidentSpans* outer, const SkOpPtT* over1s,
    270                            const SkOpPtT* over1e) const;
    271     void debugAddIfMissing(SkPathOpsDebug::GlitchLog* ,
    272                            const SkOpPtT* over1s, const SkOpPtT* over2s,
    273                            double tStart, double tEnd,
    274                            const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, bool* added,
    275                            const SkOpPtT* over1e, const SkOpPtT* over2e) const;
    276     void debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* ,
    277                                const SkOpSpan* base, const SkOpSpanBase* testSpan) const;
    278     void debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* ,
    279                                const SkOpPtT* ptT) const;
    280 #endif
    281     void fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept);
    282     void markCollapsed(SkCoincidentSpans* head, SkOpPtT* test);
    283     bool overlap(const SkOpPtT* coinStart1, const SkOpPtT* coinEnd1,
    284                  const SkOpPtT* coinStart2, const SkOpPtT* coinEnd2,
    285                  double* overS, double* overE) const;
    286     bool release(SkCoincidentSpans* coin, SkCoincidentSpans* );
    287     void releaseDeleted(SkCoincidentSpans* );
    288     void restoreHead();
    289     // return coinPtT->segment()->t mapped from overS->fT <= t <= overE->fT
    290     static double TRange(const SkOpPtT* overS, double t, const SkOpSegment* coinPtT
    291                          SkDEBUGPARAMS(const SkOpPtT* overE));
    292 
    293     SkCoincidentSpans* fHead;
    294     SkCoincidentSpans* fTop;
    295     SkOpGlobalState* fGlobalState;
    296     bool fContinue;
    297     bool fSpanDeleted;
    298     bool fPtAllocated;
    299     bool fCoinExtended;
    300     bool fSpanMerged;
    301 };
    302 
    303 #endif
    304