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