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