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