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 SkOpContour_DEFINED 8 #define SkOpContour_DEFINED 9 10 #include "SkOpSegment.h" 11 #include "SkTDArray.h" 12 #include "SkTSort.h" 13 14 enum class SkOpRayDir; 15 struct SkOpRayHit; 16 class SkPathWriter; 17 18 class SkOpContour { 19 public: SkOpContour()20 SkOpContour() { 21 reset(); 22 } 23 ~SkOpContour()24 ~SkOpContour() { 25 if (fNext) { 26 fNext->~SkOpContour(); 27 } 28 } 29 30 bool operator<(const SkOpContour& rh) const { 31 return fBounds.fTop == rh.fBounds.fTop 32 ? fBounds.fLeft < rh.fBounds.fLeft 33 : fBounds.fTop < rh.fBounds.fTop; 34 } 35 addConic(SkPoint pts[3],SkScalar weight)36 void addConic(SkPoint pts[3], SkScalar weight) { 37 appendSegment().addConic(pts, weight, this); 38 } 39 addCubic(SkPoint pts[4])40 void addCubic(SkPoint pts[4]) { 41 appendSegment().addCubic(pts, this); 42 } 43 44 SkOpSegment* addCurve(SkPath::Verb verb, const SkPoint pts[4], SkScalar weight = 1); 45 addLine(SkPoint pts[2])46 SkOpSegment* addLine(SkPoint pts[2]) { 47 SkASSERT(pts[0] != pts[1]); 48 return appendSegment().addLine(pts, this); 49 } 50 addQuad(SkPoint pts[3])51 void addQuad(SkPoint pts[3]) { 52 appendSegment().addQuad(pts, this); 53 } 54 appendSegment()55 SkOpSegment& appendSegment() { 56 SkOpSegment* result = fCount++ 57 ? SkOpTAllocator<SkOpSegment>::Allocate(this->globalState()->allocator()) : &fHead; 58 result->setPrev(fTail); 59 if (fTail) { 60 fTail->setNext(result); 61 } 62 fTail = result; 63 return *result; 64 } 65 bounds()66 const SkPathOpsBounds& bounds() const { 67 return fBounds; 68 } 69 calcAngles()70 void calcAngles() { 71 SkASSERT(fCount > 0); 72 SkOpSegment* segment = &fHead; 73 do { 74 segment->calcAngles(); 75 } while ((segment = segment->next())); 76 } 77 complete()78 void complete() { 79 setBounds(); 80 } 81 count()82 int count() const { 83 return fCount; 84 } 85 debugID()86 int debugID() const { 87 return SkDEBUGRELEASE(fID, -1); 88 } 89 debugIndent()90 int debugIndent() const { 91 return SkDEBUGRELEASE(fDebugIndent, 0); 92 } 93 94 debugAngle(int id)95 const SkOpAngle* debugAngle(int id) const { 96 return SkDEBUGRELEASE(this->globalState()->debugAngle(id), nullptr); 97 } 98 debugCoincidence()99 const SkOpCoincidence* debugCoincidence() const { 100 return this->globalState()->coincidence(); 101 } 102 103 #if DEBUG_COIN 104 void debugCheckHealth(SkPathOpsDebug::GlitchLog* ) const; 105 #endif 106 debugContour(int id)107 SkOpContour* debugContour(int id) const { 108 return SkDEBUGRELEASE(this->globalState()->debugContour(id), nullptr); 109 } 110 111 #if DEBUG_COIN 112 void debugMissingCoincidence(SkPathOpsDebug::GlitchLog* log) const; 113 void debugMoveMultiples(SkPathOpsDebug::GlitchLog* ) const; 114 void debugMoveNearby(SkPathOpsDebug::GlitchLog* log) const; 115 #endif 116 debugPtT(int id)117 const SkOpPtT* debugPtT(int id) const { 118 return SkDEBUGRELEASE(this->globalState()->debugPtT(id), nullptr); 119 } 120 debugSegment(int id)121 const SkOpSegment* debugSegment(int id) const { 122 return SkDEBUGRELEASE(this->globalState()->debugSegment(id), nullptr); 123 } 124 125 #if DEBUG_ACTIVE_SPANS debugShowActiveSpans()126 void debugShowActiveSpans() { 127 SkOpSegment* segment = &fHead; 128 do { 129 segment->debugShowActiveSpans(); 130 } while ((segment = segment->next())); 131 } 132 #endif 133 debugSpan(int id)134 const SkOpSpanBase* debugSpan(int id) const { 135 return SkDEBUGRELEASE(this->globalState()->debugSpan(id), nullptr); 136 } 137 globalState()138 SkOpGlobalState* globalState() const { 139 return fState; 140 } 141 debugValidate()142 void debugValidate() const { 143 #if DEBUG_VALIDATE 144 const SkOpSegment* segment = &fHead; 145 const SkOpSegment* prior = nullptr; 146 do { 147 segment->debugValidate(); 148 SkASSERT(segment->prev() == prior); 149 prior = segment; 150 } while ((segment = segment->next())); 151 SkASSERT(prior == fTail); 152 #endif 153 } 154 done()155 bool done() const { 156 return fDone; 157 } 158 159 void dump() const; 160 void dumpAll() const; 161 void dumpAngles() const; 162 void dumpContours() const; 163 void dumpContoursAll() const; 164 void dumpContoursAngles() const; 165 void dumpContoursPts() const; 166 void dumpContoursPt(int segmentID) const; 167 void dumpContoursSegment(int segmentID) const; 168 void dumpContoursSpan(int segmentID) const; 169 void dumpContoursSpans() const; 170 void dumpPt(int ) const; 171 void dumpPts(const char* prefix = "seg") const; 172 void dumpPtsX(const char* prefix) const; 173 void dumpSegment(int ) const; 174 void dumpSegments(const char* prefix = "seg", SkPathOp op = (SkPathOp) -1) const; 175 void dumpSpan(int ) const; 176 void dumpSpans() const; 177 end()178 const SkPoint& end() const { 179 return fTail->pts()[SkPathOpsVerbToPoints(fTail->verb())]; 180 } 181 182 SkOpSpan* findSortableTop(SkOpContour* ); 183 first()184 SkOpSegment* first() { 185 SkASSERT(fCount > 0); 186 return &fHead; 187 } 188 first()189 const SkOpSegment* first() const { 190 SkASSERT(fCount > 0); 191 return &fHead; 192 } 193 indentDump()194 void indentDump() const { 195 SkDEBUGCODE(fDebugIndent += 2); 196 } 197 init(SkOpGlobalState * globalState,bool operand,bool isXor)198 void init(SkOpGlobalState* globalState, bool operand, bool isXor) { 199 fState = globalState; 200 fOperand = operand; 201 fXor = isXor; 202 SkDEBUGCODE(fID = globalState->nextContourID()); 203 } 204 isCcw()205 int isCcw() const { 206 return fCcw; 207 } 208 isXor()209 bool isXor() const { 210 return fXor; 211 } 212 joinSegments()213 void joinSegments() { 214 SkOpSegment* segment = &fHead; 215 SkOpSegment* next; 216 do { 217 next = segment->next(); 218 segment->joinEnds(next ? next : &fHead); 219 } while ((segment = next)); 220 } 221 markAllDone()222 void markAllDone() { 223 SkOpSegment* segment = &fHead; 224 do { 225 segment->markAllDone(); 226 } while ((segment = segment->next())); 227 } 228 229 // Please keep this aligned with debugMissingCoincidence() missingCoincidence()230 bool missingCoincidence() { 231 SkASSERT(fCount > 0); 232 SkOpSegment* segment = &fHead; 233 bool result = false; 234 do { 235 if (segment->missingCoincidence()) { 236 result = true; 237 } 238 segment = segment->next(); 239 } while (segment); 240 return result; 241 } 242 moveMultiples()243 bool moveMultiples() { 244 SkASSERT(fCount > 0); 245 SkOpSegment* segment = &fHead; 246 do { 247 if (!segment->moveMultiples()) { 248 return false; 249 } 250 } while ((segment = segment->next())); 251 return true; 252 } 253 moveNearby()254 void moveNearby() { 255 SkASSERT(fCount > 0); 256 SkOpSegment* segment = &fHead; 257 do { 258 segment->moveNearby(); 259 } while ((segment = segment->next())); 260 } 261 next()262 SkOpContour* next() { 263 return fNext; 264 } 265 next()266 const SkOpContour* next() const { 267 return fNext; 268 } 269 operand()270 bool operand() const { 271 return fOperand; 272 } 273 oppXor()274 bool oppXor() const { 275 return fOppXor; 276 } 277 outdentDump()278 void outdentDump() const { 279 SkDEBUGCODE(fDebugIndent -= 2); 280 } 281 282 void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkChunkAlloc* ); 283 reset()284 void reset() { 285 fTail = nullptr; 286 fNext = nullptr; 287 fCount = 0; 288 fDone = false; 289 SkDEBUGCODE(fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMin, SK_ScalarMin)); 290 SkDEBUGCODE(fFirstSorted = -1); 291 SkDEBUGCODE(fDebugIndent = 0); 292 } 293 resetReverse()294 void resetReverse() { 295 SkOpContour* next = this; 296 do { 297 next->fCcw = -1; 298 next->fReverse = false; 299 } while ((next = next->next())); 300 } 301 reversed()302 bool reversed() const { 303 return fReverse; 304 } 305 setBounds()306 void setBounds() { 307 SkASSERT(fCount > 0); 308 const SkOpSegment* segment = &fHead; 309 fBounds = segment->bounds(); 310 while ((segment = segment->next())) { 311 fBounds.add(segment->bounds()); 312 } 313 } 314 setCcw(int ccw)315 void setCcw(int ccw) { 316 fCcw = ccw; 317 } 318 setGlobalState(SkOpGlobalState * state)319 void setGlobalState(SkOpGlobalState* state) { 320 fState = state; 321 } 322 setNext(SkOpContour * contour)323 void setNext(SkOpContour* contour) { 324 // SkASSERT(!fNext == !!contour); 325 fNext = contour; 326 } 327 setOperand(bool isOp)328 void setOperand(bool isOp) { 329 fOperand = isOp; 330 } 331 setOppXor(bool isOppXor)332 void setOppXor(bool isOppXor) { 333 fOppXor = isOppXor; 334 } 335 setReverse()336 void setReverse() { 337 fReverse = true; 338 } 339 setXor(bool isXor)340 void setXor(bool isXor) { 341 fXor = isXor; 342 } 343 sortAngles()344 void sortAngles() { 345 SkASSERT(fCount > 0); 346 SkOpSegment* segment = &fHead; 347 do { 348 segment->sortAngles(); 349 } while ((segment = segment->next())); 350 } 351 start()352 const SkPoint& start() const { 353 return fHead.pts()[0]; 354 } 355 toPartialBackward(SkPathWriter * path)356 void toPartialBackward(SkPathWriter* path) const { 357 const SkOpSegment* segment = fTail; 358 do { 359 SkAssertResult(segment->addCurveTo(segment->tail(), segment->head(), path)); 360 } while ((segment = segment->prev())); 361 } 362 toPartialForward(SkPathWriter * path)363 void toPartialForward(SkPathWriter* path) const { 364 const SkOpSegment* segment = &fHead; 365 do { 366 SkAssertResult(segment->addCurveTo(segment->head(), segment->tail(), path)); 367 } while ((segment = segment->next())); 368 } 369 370 void toReversePath(SkPathWriter* path) const; 371 void toPath(SkPathWriter* path) const; 372 SkOpSegment* undoneSegment(SkOpSpanBase** startPtr, SkOpSpanBase** endPtr); 373 374 private: 375 SkOpGlobalState* fState; 376 SkOpSegment fHead; 377 SkOpSegment* fTail; 378 SkOpContour* fNext; 379 SkPathOpsBounds fBounds; 380 int fCcw; 381 int fCount; 382 int fFirstSorted; 383 bool fDone; // set by find top segment 384 bool fOperand; // true for the second argument to a binary operator 385 bool fReverse; // true if contour should be reverse written to path (used only by fix winding) 386 bool fXor; // set if original path had even-odd fill 387 bool fOppXor; // set if opposite path had even-odd fill 388 SkDEBUGCODE(int fID); 389 SkDEBUGCODE(mutable int fDebugIndent); 390 }; 391 392 class SkOpContourHead : public SkOpContour { 393 public: appendContour()394 SkOpContour* appendContour() { 395 SkOpContour* contour = SkOpTAllocator<SkOpContour>::New(this->globalState()->allocator()); 396 contour->setNext(nullptr); 397 SkOpContour* prev = this; 398 SkOpContour* next; 399 while ((next = prev->next())) { 400 prev = next; 401 } 402 prev->setNext(contour); 403 return contour; 404 } 405 joinAllSegments()406 void joinAllSegments() { 407 SkOpContour* next = this; 408 do { 409 next->joinSegments(); 410 } while ((next = next->next())); 411 } 412 remove(SkOpContour * contour)413 void remove(SkOpContour* contour) { 414 if (contour == this) { 415 SkASSERT(this->count() == 0); 416 return; 417 } 418 SkASSERT(contour->next() == nullptr); 419 SkOpContour* prev = this; 420 SkOpContour* next; 421 while ((next = prev->next()) != contour) { 422 SkASSERT(next); 423 prev = next; 424 } 425 SkASSERT(prev); 426 prev->setNext(nullptr); 427 } 428 429 }; 430 431 #endif 432