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 15class SkOpPtT; 16class SkOpSpanBase; 17 18class SkCoincidentSpans { 19public: 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 125private: 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 134class SkOpCoincidence { 135public: 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 241private: 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