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 "SkArenaAlloc.h" 11 #include "SkTDArray.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 coinPtTEndWritable()25 SkOpPtT* coinPtTEndWritable() const { return const_cast<SkOpPtT*>(fCoinPtTEnd); } coinPtTStartWritable()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 debugID()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); flipped()59 bool flipped() const { return fOppPtTStart->fT > fOppPtTEnd->fT; } SkDEBUGCODE(SkOpGlobalState * globalState (){ return fGlobalState; })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 next()67 SkCoincidentSpans* next() { return fNext; } next()68 const SkCoincidentSpans* next() const { return fNext; } nextPtr()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 oppPtTStartWritable()74 SkOpPtT* oppPtTStartWritable() const { return const_cast<SkOpPtT*>(fOppPtTStart); } oppPtTEndWritable()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 setCoinPtTEnd(const SkOpPtT * ptT)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 setCoinPtTStart(const SkOpPtT * ptT)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 setEnds(const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTEnd)97 void setEnds(const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTEnd) { 98 this->setCoinPtTEnd(coinPtTEnd); 99 this->setOppPtTEnd(oppPtTEnd); 100 } 101 setOppPtTEnd(const SkOpPtT * ptT)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 setOppPtTStart(const SkOpPtT * ptT)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 setStarts(const SkOpPtT * coinPtTStart,const SkOpPtT * oppPtTStart)118 void setStarts(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) { 119 this->setCoinPtTStart(coinPtTStart); 120 this->setOppPtTStart(oppPtTStart); 121 } 122 setNext(SkCoincidentSpans * next)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: SkOpCoincidence(SkOpGlobalState * globalState)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 debugAngle(int id)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 debugContour(int id)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 debugPtT(int id)191 const SkOpPtT* debugPtT(int id) const { 192 return SkDEBUGRELEASE(fGlobalState->debugPtT(id), nullptr); 193 } 194 debugSegment(int id)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 debugSpan(int id)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 globalState()218 SkOpGlobalState* globalState() { 219 return fGlobalState; 220 } 221 globalState()222 const SkOpGlobalState* globalState() const { 223 return fGlobalState; 224 } 225 isEmpty()226 bool isEmpty() const { 227 return !fHead && !fTop; 228 } 229 230 bool mark(DEBUG_COIN_DECLARE_ONLY_PARAMS()); 231 void markCollapsed(SkOpPtT* ); 232 Ordered(const SkOpPtT * coinPtTStart,const SkOpPtT * oppPtTStart)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: add(const SkOpPtT * coinPtTStart,const SkOpPtT * coinPtTEnd,const SkOpPtT * oppPtTStart,const SkOpPtT * oppPtTEnd)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