1 /* 2 * Copyright 2014 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 SkPathOpsTSect_DEFINED 8 #define SkPathOpsTSect_DEFINED 9 10 #include "include/core/SkScalar.h" 11 #include "include/core/SkTypes.h" 12 #include "include/private/base/SkDebug.h" 13 #include "include/private/base/SkTo.h" 14 #include "src/base/SkArenaAlloc.h" 15 #include "src/pathops/SkPathOpsPoint.h" 16 #include "src/pathops/SkPathOpsRect.h" 17 #include "src/pathops/SkPathOpsTCurve.h" 18 #include "src/pathops/SkPathOpsTypes.h" 19 20 #include <cstdint> 21 22 class SkIntersections; 23 class SkTSect; 24 class SkTSpan; 25 struct SkDLine; 26 27 #ifdef SK_DEBUG 28 typedef uint8_t SkOpDebugBool; 29 #else 30 typedef bool SkOpDebugBool; 31 #endif 32 33 class SkTCoincident { 34 public: SkTCoincident()35 SkTCoincident() { 36 this->init(); 37 } 38 debugInit()39 void debugInit() { 40 #ifdef SK_DEBUG 41 this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN; 42 this->fPerpT = SK_ScalarNaN; 43 this->fMatch = 0xFF; 44 #endif 45 } 46 47 char dumpIsCoincidentStr() const; 48 void dump() const; 49 isMatch()50 bool isMatch() const { 51 SkASSERT(!!fMatch == fMatch); 52 return SkToBool(fMatch); 53 } 54 init()55 void init() { 56 fPerpT = -1; 57 fMatch = false; 58 fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN; 59 } 60 markCoincident()61 void markCoincident() { 62 if (!fMatch) { 63 fPerpT = -1; 64 } 65 fMatch = true; 66 } 67 perpPt()68 const SkDPoint& perpPt() const { 69 return fPerpPt; 70 } 71 perpT()72 double perpT() const { 73 return fPerpT; 74 } 75 76 void setPerp(const SkTCurve& c1, double t, const SkDPoint& cPt, const SkTCurve& ); 77 78 private: 79 SkDPoint fPerpPt; 80 double fPerpT; // perpendicular intersection on opposite curve 81 SkOpDebugBool fMatch; 82 }; 83 84 struct SkTSpanBounded { 85 SkTSpan* fBounded; 86 SkTSpanBounded* fNext; 87 }; 88 89 class SkTSpan { 90 public: SkTSpan(const SkTCurve & curve,SkArenaAlloc & heap)91 SkTSpan(const SkTCurve& curve, SkArenaAlloc& heap) { 92 fPart = curve.make(heap); 93 } 94 95 void addBounded(SkTSpan* , SkArenaAlloc* ); 96 double closestBoundedT(const SkDPoint& pt) const; 97 bool contains(double t) const; 98 debugInit(const SkTCurve & curve,SkArenaAlloc & heap)99 void debugInit(const SkTCurve& curve, SkArenaAlloc& heap) { 100 #ifdef SK_DEBUG 101 SkTCurve* fake = curve.make(heap); 102 fake->debugInit(); 103 init(*fake); 104 initBounds(*fake); 105 fCoinStart.init(); 106 fCoinEnd.init(); 107 #endif 108 } 109 110 const SkTSect* debugOpp() const; 111 112 #ifdef SK_DEBUG debugSetGlobalState(SkOpGlobalState * state)113 void debugSetGlobalState(SkOpGlobalState* state) { 114 fDebugGlobalState = state; 115 } 116 117 const SkTSpan* debugSpan(int ) const; 118 const SkTSpan* debugT(double t) const; 119 bool debugIsBefore(const SkTSpan* span) const; 120 #endif 121 void dump() const; 122 void dumpAll() const; 123 void dumpBounded(int id) const; 124 void dumpBounds() const; 125 void dumpCoin() const; 126 endT()127 double endT() const { 128 return fEndT; 129 } 130 131 SkTSpan* findOppSpan(const SkTSpan* opp) const; 132 findOppT(double t)133 SkTSpan* findOppT(double t) const { 134 SkTSpan* result = oppT(t); 135 SkOPASSERT(result); 136 return result; 137 } 138 SkDEBUGCODE(SkOpGlobalState * globalState ()const{ return fDebugGlobalState; })139 SkDEBUGCODE(SkOpGlobalState* globalState() const { return fDebugGlobalState; }) 140 141 bool hasOppT(double t) const { 142 return SkToBool(oppT(t)); 143 } 144 145 int hullsIntersect(SkTSpan* span, bool* start, bool* oppStart); 146 void init(const SkTCurve& ); 147 bool initBounds(const SkTCurve& ); 148 isBounded()149 bool isBounded() const { 150 return fBounded != nullptr; 151 } 152 153 bool linearsIntersect(SkTSpan* span); 154 double linearT(const SkDPoint& ) const; 155 markCoincident()156 void markCoincident() { 157 fCoinStart.markCoincident(); 158 fCoinEnd.markCoincident(); 159 } 160 next()161 const SkTSpan* next() const { 162 return fNext; 163 } 164 165 bool onlyEndPointsInCommon(const SkTSpan* opp, bool* start, 166 bool* oppStart, bool* ptsInCommon); 167 part()168 const SkTCurve& part() const { 169 return *fPart; 170 } 171 pointCount()172 int pointCount() const { 173 return fPart->pointCount(); 174 } 175 pointFirst()176 const SkDPoint& pointFirst() const { 177 return (*fPart)[0]; 178 } 179 pointLast()180 const SkDPoint& pointLast() const { 181 return (*fPart)[fPart->pointLast()]; 182 } 183 184 bool removeAllBounded(); 185 bool removeBounded(const SkTSpan* opp); 186 reset()187 void reset() { 188 fBounded = nullptr; 189 } 190 resetBounds(const SkTCurve & curve)191 void resetBounds(const SkTCurve& curve) { 192 fIsLinear = fIsLine = false; 193 initBounds(curve); 194 } 195 split(SkTSpan * work,SkArenaAlloc * heap)196 bool split(SkTSpan* work, SkArenaAlloc* heap) { 197 return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap); 198 } 199 200 bool splitAt(SkTSpan* work, double t, SkArenaAlloc* heap); 201 startT()202 double startT() const { 203 return fStartT; 204 } 205 206 private: 207 208 // implementation is for testing only debugID()209 int debugID() const { 210 return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); 211 } 212 213 void dumpID() const; 214 215 int hullCheck(const SkTSpan* opp, bool* start, bool* oppStart); 216 int linearIntersects(const SkTCurve& ) const; 217 SkTSpan* oppT(double t) const; 218 219 void validate() const; 220 void validateBounded() const; 221 void validatePerpT(double oppT) const; 222 void validatePerpPt(double t, const SkDPoint& ) const; 223 224 SkTCurve* fPart; 225 SkTCoincident fCoinStart; 226 SkTCoincident fCoinEnd; 227 SkTSpanBounded* fBounded; 228 SkTSpan* fPrev; 229 SkTSpan* fNext; 230 SkDRect fBounds; 231 double fStartT; 232 double fEndT; 233 double fBoundsMax; 234 SkOpDebugBool fCollapsed; 235 SkOpDebugBool fHasPerp; 236 SkOpDebugBool fIsLinear; 237 SkOpDebugBool fIsLine; 238 SkOpDebugBool fDeleted; 239 SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState;) 240 SkDEBUGCODE(SkTSect* fDebugSect;) 241 PATH_OPS_DEBUG_T_SECT_CODE(int fID;) 242 friend class SkTSect; 243 }; 244 245 class SkTSect { 246 public: 247 SkTSect(const SkTCurve& c 248 SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id)); 249 static void BinarySearch(SkTSect* sect1, SkTSect* sect2, 250 SkIntersections* intersections); 251 252 SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; }) 253 bool hasBounded(const SkTSpan* ) const; 254 debugOpp()255 const SkTSect* debugOpp() const { 256 return SkDEBUGRELEASE(fOppSect, nullptr); 257 } 258 259 #ifdef SK_DEBUG 260 const SkTSpan* debugSpan(int id) const; 261 const SkTSpan* debugT(double t) const; 262 #endif 263 void dump() const; 264 void dumpBoth(SkTSect* ) const; 265 void dumpBounded(int id) const; 266 void dumpBounds() const; 267 void dumpCoin() const; 268 void dumpCoinCurves() const; 269 void dumpCurves() const; 270 271 private: 272 enum { 273 kZeroS1Set = 1, 274 kOneS1Set = 2, 275 kZeroS2Set = 4, 276 kOneS2Set = 8 277 }; 278 279 SkTSpan* addFollowing(SkTSpan* prior); 280 void addForPerp(SkTSpan* span, double t); 281 SkTSpan* addOne(); 282 addSplitAt(SkTSpan * span,double t)283 SkTSpan* addSplitAt(SkTSpan* span, double t) { 284 SkTSpan* result = this->addOne(); 285 SkDEBUGCODE(result->debugSetGlobalState(this->globalState())); 286 result->splitAt(span, t, &fHeap); 287 result->initBounds(fCurve); 288 span->initBounds(fCurve); 289 return result; 290 } 291 292 bool binarySearchCoin(SkTSect* , double tStart, double tStep, double* t, 293 double* oppT, SkTSpan** oppFirst); 294 SkTSpan* boundsMax(); 295 bool coincidentCheck(SkTSect* sect2); 296 void coincidentForce(SkTSect* sect2, double start1s, double start1e); 297 bool coincidentHasT(double t); 298 int collapsed() const; 299 void computePerpendiculars(SkTSect* sect2, SkTSpan* first, 300 SkTSpan* last); 301 int countConsecutiveSpans(SkTSpan* first, 302 SkTSpan** last) const; 303 debugID()304 int debugID() const { 305 return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); 306 } 307 308 bool deleteEmptySpans(); 309 void dumpCommon(const SkTSpan* ) const; 310 void dumpCommonCurves(const SkTSpan* ) const; 311 static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2, 312 SkIntersections* ); 313 bool extractCoincident(SkTSect* sect2, SkTSpan* first, 314 SkTSpan* last, SkTSpan** result); 315 SkTSpan* findCoincidentRun(SkTSpan* first, SkTSpan** lastPtr); 316 int intersects(SkTSpan* span, SkTSect* opp, 317 SkTSpan* oppSpan, int* oppResult); 318 bool isParallel(const SkDLine& thisLine, const SkTSect* opp) const; 319 int linesIntersect(SkTSpan* span, SkTSect* opp, 320 SkTSpan* oppSpan, SkIntersections* ); 321 bool markSpanGone(SkTSpan* span); 322 bool matchedDirection(double t, const SkTSect* sect2, double t2) const; 323 void matchedDirCheck(double t, const SkTSect* sect2, double t2, 324 bool* calcMatched, bool* oppMatched) const; 325 void mergeCoincidence(SkTSect* sect2); 326 pointLast()327 const SkDPoint& pointLast() const { 328 return fCurve[fCurve.pointLast()]; 329 } 330 331 SkTSpan* prev(SkTSpan* ) const; 332 bool removeByPerpendicular(SkTSect* opp); 333 void recoverCollapsed(); 334 bool removeCoincident(SkTSpan* span, bool isBetween); 335 void removeAllBut(const SkTSpan* keep, SkTSpan* span, 336 SkTSect* opp); 337 bool removeSpan(SkTSpan* span); 338 void removeSpanRange(SkTSpan* first, SkTSpan* last); 339 bool removeSpans(SkTSpan* span, SkTSect* opp); 340 void removedEndCheck(SkTSpan* span); 341 resetRemovedEnds()342 void resetRemovedEnds() { 343 fRemovedStartT = fRemovedEndT = false; 344 } 345 346 SkTSpan* spanAtT(double t, SkTSpan** priorSpan); 347 SkTSpan* tail(); 348 bool trim(SkTSpan* span, SkTSect* opp); 349 bool unlinkSpan(SkTSpan* span); 350 bool updateBounded(SkTSpan* first, SkTSpan* last, 351 SkTSpan* oppFirst); 352 void validate() const; 353 void validateBounded() const; 354 355 const SkTCurve& fCurve; 356 SkSTArenaAlloc<1024> fHeap; 357 SkTSpan* fHead; 358 SkTSpan* fCoincident; 359 SkTSpan* fDeleted; 360 int fActiveCount; 361 bool fRemovedStartT; 362 bool fRemovedEndT; 363 bool fHung; 364 SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState;) 365 SkDEBUGCODE(SkTSect* fOppSect;) 366 PATH_OPS_DEBUG_T_SECT_CODE(int fID;) 367 PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount;) 368 #if DEBUG_T_SECT 369 int fDebugAllocatedCount; 370 #endif 371 friend class SkTSpan; 372 }; 373 374 #endif 375