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