1 /* 2 * Copyright 2012 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 SkOpSegment_DEFINE 8 #define SkOpSegment_DEFINE 9 10 #include "SkOpAngle.h" 11 #include "SkOpSpan.h" 12 #include "SkOpTAllocator.h" 13 #include "SkPathOpsBounds.h" 14 #include "SkPathOpsCubic.h" 15 #include "SkPathOpsCurve.h" 16 17 struct SkDCurve; 18 class SkOpCoincidence; 19 class SkOpContour; 20 enum class SkOpRayDir; 21 struct SkOpRayHit; 22 class SkPathWriter; 23 24 class SkOpSegment { 25 public: 26 bool operator<(const SkOpSegment& rh) const { 27 return fBounds.fTop < rh.fBounds.fTop; 28 } 29 30 SkOpAngle* activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr, 31 bool* done); 32 SkOpAngle* activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr, 33 SkOpSpanBase** endPtr, bool* done); 34 SkOpAngle* activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr, 35 SkOpSpanBase** endPtr, bool* done); 36 bool activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask, 37 SkPathOp op); 38 bool activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, SkPathOp op, 39 int* sumMiWinding, int* sumSuWinding); 40 41 bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end); 42 bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding); 43 44 SkOpSegment* addConic(SkPoint pts[3], SkScalar weight, SkOpContour* parent) { 45 init(pts, weight, parent, SkPath::kConic_Verb); 46 SkDCurve curve; 47 curve.fConic.set(pts, weight); 48 curve.setConicBounds(pts, weight, 0, 1, &fBounds); 49 return this; 50 } 51 52 SkOpSegment* addCubic(SkPoint pts[4], SkOpContour* parent) { 53 init(pts, 1, parent, SkPath::kCubic_Verb); 54 SkDCurve curve; 55 curve.fCubic.set(pts); 56 curve.setCubicBounds(pts, 1, 0, 1, &fBounds); 57 return this; 58 } 59 60 bool addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path) const; 61 62 SkOpAngle* addEndSpan() { 63 SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(this->globalState()->allocator()); 64 angle->set(&fTail, fTail.prev()); 65 fTail.setFromAngle(angle); 66 return angle; 67 } 68 69 bool addExpanded(double newT, const SkOpSpanBase* test, bool* startOver); 70 71 SkOpSegment* addLine(SkPoint pts[2], SkOpContour* parent) { 72 SkASSERT(pts[0] != pts[1]); 73 init(pts, 1, parent, SkPath::kLine_Verb); 74 fBounds.set(pts, 2); 75 return this; 76 } 77 78 SkOpPtT* addMissing(double t, SkOpSegment* opp, bool* allExist); 79 80 SkOpAngle* addStartSpan() { 81 SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(this->globalState()->allocator()); 82 angle->set(&fHead, fHead.next()); 83 fHead.setToAngle(angle); 84 return angle; 85 } 86 87 SkOpSegment* addQuad(SkPoint pts[3], SkOpContour* parent) { 88 init(pts, 1, parent, SkPath::kQuad_Verb); 89 SkDCurve curve; 90 curve.fQuad.set(pts); 91 curve.setQuadBounds(pts, 1, 0, 1, &fBounds); 92 return this; 93 } 94 95 SkOpPtT* addT(double t); 96 SkOpPtT* addT(double t, const SkPoint& pt); 97 98 template<typename T> T* allocateArray(int count) { 99 return SkOpTAllocator<T>::AllocateArray(this->globalState()->allocator(), count); 100 } 101 102 const SkPathOpsBounds& bounds() const { 103 return fBounds; 104 } 105 106 void bumpCount() { 107 ++fCount; 108 } 109 110 void calcAngles(); 111 bool collapsed(double startT, double endT) const; 112 static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 113 SkOpAngle::IncludeType ); 114 static void ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, 115 SkOpAngle::IncludeType ); 116 int computeSum(SkOpSpanBase* start, SkOpSpanBase* end, SkOpAngle::IncludeType includeType); 117 118 void clearAll(); 119 void clearOne(SkOpSpan* span); 120 static void ClearVisited(SkOpSpanBase* span); 121 bool contains(double t) const; 122 123 SkOpContour* contour() const { 124 return fContour; 125 } 126 127 int count() const { 128 return fCount; 129 } 130 131 void debugAddAngle(double startT, double endT); 132 #if DEBUG_COIN 133 const SkOpPtT* debugAddT(double t, SkPathOpsDebug::GlitchLog* ) const; 134 #endif 135 const SkOpAngle* debugAngle(int id) const; 136 #if DEBUG_ANGLE 137 void debugCheckAngleCoin() const; 138 #endif 139 #if DEBUG_COIN 140 void debugCheckHealth(SkPathOpsDebug::GlitchLog* ) const; 141 void debugClearAll(SkPathOpsDebug::GlitchLog* glitches) const; 142 void debugClearOne(const SkOpSpan* span, SkPathOpsDebug::GlitchLog* glitches) const; 143 #endif 144 const SkOpCoincidence* debugCoincidence() const; 145 SkOpContour* debugContour(int id) const; 146 147 int debugID() const { 148 return SkDEBUGRELEASE(fID, -1); 149 } 150 151 SkOpAngle* debugLastAngle(); 152 #if DEBUG_COIN 153 void debugMissingCoincidence(SkPathOpsDebug::GlitchLog* glitches) const; 154 void debugMoveMultiples(SkPathOpsDebug::GlitchLog* glitches) const; 155 void debugMoveNearby(SkPathOpsDebug::GlitchLog* glitches) const; 156 #endif 157 const SkOpPtT* debugPtT(int id) const; 158 void debugReset(); 159 const SkOpSegment* debugSegment(int id) const; 160 161 #if DEBUG_ACTIVE_SPANS 162 void debugShowActiveSpans(SkString* str) const; 163 #endif 164 #if DEBUG_MARK_DONE 165 void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding); 166 void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, int oppWinding); 167 #endif 168 169 const SkOpSpanBase* debugSpan(int id) const; 170 void debugValidate() const; 171 172 #if DEBUG_COINCIDENCE_ORDER 173 void debugResetCoinT() const; 174 void debugSetCoinT(int, SkScalar ) const; 175 #endif 176 177 #if DEBUG_COIN 178 static void DebugClearVisited(const SkOpSpanBase* span); 179 180 bool debugVisited() const { 181 if (!fDebugVisited) { 182 fDebugVisited = true; 183 return false; 184 } 185 return true; 186 } 187 #endif 188 189 #if DEBUG_ANGLE 190 double distSq(double t, const SkOpAngle* opp) const; 191 #endif 192 193 bool done() const { 194 SkOPASSERT(fDoneCount <= fCount); 195 return fDoneCount == fCount; 196 } 197 198 bool done(const SkOpAngle* angle) const { 199 return angle->start()->starter(angle->end())->done(); 200 } 201 202 SkDPoint dPtAtT(double mid) const { 203 return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid); 204 } 205 206 SkDVector dSlopeAtT(double mid) const { 207 return (*CurveDSlopeAtT[fVerb])(fPts, fWeight, mid); 208 } 209 210 void dump() const; 211 void dumpAll() const; 212 void dumpAngles() const; 213 void dumpCoin() const; 214 void dumpPts(const char* prefix = "seg") const; 215 void dumpPtsInner(const char* prefix = "seg") const; 216 217 const SkOpPtT* existing(double t, const SkOpSegment* opp) const; 218 SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 219 SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, 220 int xorMiMask, int xorSuMask); 221 SkOpSegment* findNextWinding(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 222 SkOpSpanBase** nextEnd, bool* unsortable); 223 SkOpSegment* findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable); 224 SkOpSpan* findSortableTop(SkOpContour* ); 225 SkOpGlobalState* globalState() const; 226 227 const SkOpSpan* head() const { 228 return &fHead; 229 } 230 231 SkOpSpan* head() { 232 return &fHead; 233 } 234 235 void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb); 236 237 SkOpSpan* insert(SkOpSpan* prev) { 238 SkOpGlobalState* globalState = this->globalState(); 239 globalState->setAllocatedOpSpan(); 240 SkOpSpan* result = SkOpTAllocator<SkOpSpan>::Allocate(globalState->allocator()); 241 SkOpSpanBase* next = prev->next(); 242 result->setPrev(prev); 243 prev->setNext(result); 244 SkDEBUGCODE(result->ptT()->fT = 0); 245 result->setNext(next); 246 if (next) { 247 next->setPrev(result); 248 } 249 return result; 250 } 251 252 bool isClose(double t, const SkOpSegment* opp) const; 253 254 bool isHorizontal() const { 255 return fBounds.fTop == fBounds.fBottom; 256 } 257 258 SkOpSegment* isSimple(SkOpSpanBase** end, int* step) { 259 return nextChase(end, step, nullptr, nullptr); 260 } 261 262 bool isVertical() const { 263 return fBounds.fLeft == fBounds.fRight; 264 } 265 266 bool isVertical(SkOpSpanBase* start, SkOpSpanBase* end) const { 267 return (*CurveIsVertical[fVerb])(fPts, fWeight, start->t(), end->t()); 268 } 269 270 bool isXor() const; 271 272 void joinEnds(SkOpSegment* start) { 273 fTail.ptT()->addOpp(start->fHead.ptT(), start->fHead.ptT()); 274 } 275 276 const SkPoint& lastPt() const { 277 return fPts[SkPathOpsVerbToPoints(fVerb)]; 278 } 279 280 void markAllDone(); 281 SkOpSpanBase* markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end); 282 bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 283 SkOpSpanBase** lastPtr); 284 bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 285 int oppWinding, SkOpSpanBase** lastPtr); 286 SkOpSpanBase* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle); 287 SkOpSpanBase* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding, 288 const SkOpAngle* angle); 289 void markDone(SkOpSpan* ); 290 bool markWinding(SkOpSpan* , int winding); 291 bool markWinding(SkOpSpan* , int winding, int oppWinding); 292 bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const; 293 bool missingCoincidence(); 294 bool moveMultiples(); 295 bool moveNearby(); 296 297 SkOpSegment* next() const { 298 return fNext; 299 } 300 301 SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const; 302 bool operand() const; 303 304 static int OppSign(const SkOpSpanBase* start, const SkOpSpanBase* end) { 305 int result = start->t() < end->t() ? -start->upCast()->oppValue() 306 : end->upCast()->oppValue(); 307 return result; 308 } 309 310 bool oppXor() const; 311 312 const SkOpSegment* prev() const { 313 return fPrev; 314 } 315 316 SkPoint ptAtT(double mid) const { 317 return (*CurvePointAtT[fVerb])(fPts, fWeight, mid); 318 } 319 320 const SkPoint* pts() const { 321 return fPts; 322 } 323 324 bool ptsDisjoint(const SkOpPtT& span, const SkOpPtT& test) const { 325 SkASSERT(this == span.segment()); 326 SkASSERT(this == test.segment()); 327 return ptsDisjoint(span.fT, span.fPt, test.fT, test.fPt); 328 } 329 330 bool ptsDisjoint(const SkOpPtT& span, double t, const SkPoint& pt) const { 331 SkASSERT(this == span.segment()); 332 return ptsDisjoint(span.fT, span.fPt, t, pt); 333 } 334 335 bool ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const; 336 337 void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, SkArenaAlloc*); 338 void release(const SkOpSpan* ); 339 340 #if DEBUG_COIN 341 void resetDebugVisited() const { 342 fDebugVisited = false; 343 } 344 #endif 345 346 void resetVisited() { 347 fVisited = false; 348 } 349 350 void setContour(SkOpContour* contour) { 351 fContour = contour; 352 } 353 354 void setNext(SkOpSegment* next) { 355 fNext = next; 356 } 357 358 void setPrev(SkOpSegment* prev) { 359 fPrev = prev; 360 } 361 362 void setUpWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* maxWinding, int* sumWinding) { 363 int deltaSum = SpanSign(start, end); 364 *maxWinding = *sumWinding; 365 if (*sumWinding == SK_MinS32) { 366 return; 367 } 368 *sumWinding -= deltaSum; 369 } 370 371 void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 372 int* maxWinding, int* sumWinding); 373 void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, int* sumSuWinding, 374 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding); 375 bool sortAngles(); 376 bool spansNearby(const SkOpSpanBase* ref, const SkOpSpanBase* check, bool* found) const; 377 378 static int SpanSign(const SkOpSpanBase* start, const SkOpSpanBase* end) { 379 int result = start->t() < end->t() ? -start->upCast()->windValue() 380 : end->upCast()->windValue(); 381 return result; 382 } 383 384 SkOpAngle* spanToAngle(SkOpSpanBase* start, SkOpSpanBase* end) { 385 SkASSERT(start != end); 386 return start->t() < end->t() ? start->upCast()->toAngle() : start->fromAngle(); 387 } 388 389 bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCurve* result) const; 390 391 const SkOpSpanBase* tail() const { 392 return &fTail; 393 } 394 395 SkOpSpanBase* tail() { 396 return &fTail; 397 } 398 399 bool testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT, const SkOpSpanBase* prior, 400 const SkOpSpanBase* spanBase, const SkOpSegment* opp) const; 401 402 SkOpSpan* undoneSpan(); 403 int updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const; 404 int updateOppWinding(const SkOpAngle* angle) const; 405 int updateOppWindingReverse(const SkOpAngle* angle) const; 406 int updateWinding(SkOpSpanBase* start, SkOpSpanBase* end); 407 int updateWinding(SkOpAngle* angle); 408 int updateWindingReverse(const SkOpAngle* angle); 409 410 static bool UseInnerWinding(int outerWinding, int innerWinding); 411 412 SkPath::Verb verb() const { 413 return fVerb; 414 } 415 416 // look for two different spans that point to the same opposite segment 417 bool visited() { 418 if (!fVisited) { 419 fVisited = true; 420 return false; 421 } 422 return true; 423 } 424 425 SkScalar weight() const { 426 return fWeight; 427 } 428 429 SkOpSpan* windingSpanAtT(double tHit); 430 int windSum(const SkOpAngle* angle) const; 431 432 private: 433 SkOpSpan fHead; // the head span always has its t set to zero 434 SkOpSpanBase fTail; // the tail span always has its t set to one 435 SkOpContour* fContour; 436 SkOpSegment* fNext; // forward-only linked list used by contour to walk the segments 437 const SkOpSegment* fPrev; 438 SkPoint* fPts; // pointer into array of points owned by edge builder that may be tweaked 439 SkPathOpsBounds fBounds; // tight bounds 440 SkScalar fWeight; 441 int fCount; // number of spans (one for a non-intersecting segment) 442 int fDoneCount; // number of processed spans (zero initially) 443 SkPath::Verb fVerb; 444 bool fVisited; // used by missing coincidence check 445 #if DEBUG_COIN 446 mutable bool fDebugVisited; // used by debug missing coincidence check 447 #endif 448 #if DEBUG_COINCIDENCE_ORDER 449 mutable int fDebugBaseIndex; 450 mutable SkScalar fDebugBaseMin; // if > 0, the 1st t value in this seg vis-a-vis the ref seg 451 mutable SkScalar fDebugBaseMax; 452 mutable int fDebugLastIndex; 453 mutable SkScalar fDebugLastMin; // if > 0, the last t -- next t val - base has same sign 454 mutable SkScalar fDebugLastMax; 455 #endif 456 SkDEBUGCODE(int fID); 457 }; 458 459 #endif 460
