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