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