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 enum AllowAlias { 27 kAllowAlias, 28 kNoAlias 29 }; 30 31 bool operator<(const SkOpSegment& rh) const { 32 return fBounds.fTop < rh.fBounds.fTop; 33 } 34 35 SkOpAngle* activeAngle(SkOpSpanBase* start, SkOpSpanBase** startPtr, SkOpSpanBase** endPtr, 36 bool* done); 37 SkOpAngle* activeAngleInner(SkOpSpanBase* start, SkOpSpanBase** startPtr, 38 SkOpSpanBase** endPtr, bool* done); 39 SkOpAngle* activeAngleOther(SkOpSpanBase* start, SkOpSpanBase** startPtr, 40 SkOpSpanBase** endPtr, bool* done); 41 bool activeOp(SkOpSpanBase* start, SkOpSpanBase* end, int xorMiMask, int xorSuMask, 42 SkPathOp op); 43 bool activeOp(int xorMiMask, int xorSuMask, SkOpSpanBase* start, SkOpSpanBase* end, SkPathOp op, 44 int* sumMiWinding, int* sumSuWinding); 45 46 bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end); 47 bool activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sumWinding); 48 49 SkOpSegment* addConic(SkPoint pts[3], SkScalar weight, SkOpContour* parent) { 50 init(pts, weight, parent, SkPath::kConic_Verb); 51 SkDCurve curve; 52 curve.fConic.set(pts, weight); 53 curve.setConicBounds(pts, weight, 0, 1, &fBounds); 54 return this; 55 } 56 57 SkOpSegment* addCubic(SkPoint pts[4], SkOpContour* parent) { 58 init(pts, 1, parent, SkPath::kCubic_Verb); 59 SkDCurve curve; 60 curve.fCubic.set(pts); 61 curve.setCubicBounds(pts, 1, 0, 1, &fBounds); 62 return this; 63 } 64 65 void addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, SkPathWriter* path, 66 bool active) const; 67 68 SkOpAngle* addEndSpan(SkChunkAlloc* allocator) { 69 SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); 70 angle->set(&fTail, fTail.prev()); 71 fTail.setFromAngle(angle); 72 return angle; 73 } 74 75 SkOpSegment* addLine(SkPoint pts[2], SkOpContour* parent) { 76 init(pts, 1, parent, SkPath::kLine_Verb); 77 fBounds.set(pts, 2); 78 return this; 79 } 80 81 SkOpPtT* addMissing(double t, SkOpSegment* opp, SkChunkAlloc* ); 82 83 SkOpAngle* addStartSpan(SkChunkAlloc* allocator) { 84 SkOpAngle* angle = SkOpTAllocator<SkOpAngle>::Allocate(allocator); 85 angle->set(&fHead, fHead.next()); 86 fHead.setToAngle(angle); 87 return angle; 88 } 89 90 SkOpSegment* addQuad(SkPoint pts[3], SkOpContour* parent) { 91 init(pts, 1, parent, SkPath::kQuad_Verb); 92 SkDCurve curve; 93 curve.fQuad.set(pts); 94 curve.setQuadBounds(pts, 1, 0, 1, &fBounds); 95 return this; 96 } 97 98 SkOpPtT* addT(double t, AllowAlias , SkChunkAlloc* ); 99 100 void align(); 101 102 const SkPathOpsBounds& bounds() const { 103 return fBounds; 104 } 105 106 void bumpCount() { 107 ++fCount; 108 } 109 110 void calcAngles(SkChunkAlloc*); 111 void checkAngleCoin(SkOpCoincidence* coincidences, SkChunkAlloc* allocator); 112 void checkNearCoincidence(SkOpAngle* ); 113 bool collapsed() const; 114 static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 115 SkOpAngle::IncludeType ); 116 static void ComputeOneSumReverse(SkOpAngle* baseAngle, SkOpAngle* nextAngle, 117 SkOpAngle::IncludeType ); 118 int computeSum(SkOpSpanBase* start, SkOpSpanBase* end, SkOpAngle::IncludeType includeType); 119 120 SkOpContour* contour() const { 121 return fContour; 122 } 123 124 int count() const { 125 return fCount; 126 } 127 128 void debugAddAngle(double startT, double endT, SkChunkAlloc*); 129 const SkOpAngle* debugAngle(int id) const; 130 SkOpContour* debugContour(int id); 131 132 int debugID() const { 133 return SkDEBUGRELEASE(fID, -1); 134 } 135 136 SkOpAngle* debugLastAngle(); 137 const SkOpPtT* debugPtT(int id) const; 138 void debugReset(); 139 const SkOpSegment* debugSegment(int id) const; 140 141 #if DEBUG_ACTIVE_SPANS 142 void debugShowActiveSpans() const; 143 #endif 144 #if DEBUG_MARK_DONE 145 void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding); 146 void debugShowNewWinding(const char* fun, const SkOpSpan* span, int winding, int oppWinding); 147 #endif 148 149 const SkOpSpanBase* debugSpan(int id) const; 150 void debugValidate() const; 151 void detach(const SkOpSpan* ); 152 double distSq(double t, SkOpAngle* opp); 153 154 bool done() const { 155 SkASSERT(fDoneCount <= fCount); 156 return fDoneCount == fCount; 157 } 158 159 bool done(const SkOpAngle* angle) const { 160 return angle->start()->starter(angle->end())->done(); 161 } 162 163 SkDPoint dPtAtT(double mid) const { 164 return (*CurveDPointAtT[fVerb])(fPts, fWeight, mid); 165 } 166 167 SkDVector dSlopeAtT(double mid) const { 168 return (*CurveDSlopeAtT[fVerb])(fPts, fWeight, mid); 169 } 170 171 void dump() const; 172 void dumpAll() const; 173 void dumpAngles() const; 174 void dumpCoin() const; 175 void dumpPts() const; 176 void dumpPtsInner() const; 177 178 SkOpSegment* findNextOp(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 179 SkOpSpanBase** nextEnd, bool* unsortable, SkPathOp op, 180 int xorMiMask, int xorSuMask); 181 SkOpSegment* findNextWinding(SkTDArray<SkOpSpanBase*>* chase, SkOpSpanBase** nextStart, 182 SkOpSpanBase** nextEnd, bool* unsortable); 183 SkOpSegment* findNextXor(SkOpSpanBase** nextStart, SkOpSpanBase** nextEnd, bool* unsortable); 184 SkOpSpan* findSortableTop(SkOpContour* ); 185 SkOpGlobalState* globalState() const; 186 187 const SkOpSpan* head() const { 188 return &fHead; 189 } 190 191 SkOpSpan* head() { 192 return &fHead; 193 } 194 195 void init(SkPoint pts[], SkScalar weight, SkOpContour* parent, SkPath::Verb verb); 196 197 SkOpSpan* insert(SkOpSpan* prev, SkChunkAlloc* allocator) { 198 SkOpSpan* result = SkOpTAllocator<SkOpSpan>::Allocate(allocator); 199 SkOpSpanBase* next = prev->next(); 200 result->setPrev(prev); 201 prev->setNext(result); 202 SkDEBUGCODE(result->ptT()->fT = 0); 203 result->setNext(next); 204 if (next) { 205 next->setPrev(result); 206 } 207 return result; 208 } 209 210 bool isClose(double t, const SkOpSegment* opp) const; 211 212 bool isHorizontal() const { 213 return fBounds.fTop == fBounds.fBottom; 214 } 215 216 SkOpSegment* isSimple(SkOpSpanBase** end, int* step) { 217 return nextChase(end, step, NULL, NULL); 218 } 219 220 bool isVertical() const { 221 return fBounds.fLeft == fBounds.fRight; 222 } 223 224 bool isVertical(SkOpSpanBase* start, SkOpSpanBase* end) const { 225 return (*CurveIsVertical[fVerb])(fPts, fWeight, start->t(), end->t()); 226 } 227 228 bool isXor() const; 229 230 const SkPoint& lastPt() const { 231 return fPts[SkPathOpsVerbToPoints(fVerb)]; 232 } 233 234 SkOpSpanBase* markAndChaseDone(SkOpSpanBase* start, SkOpSpanBase* end); 235 bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 236 SkOpSpanBase** lastPtr); 237 bool markAndChaseWinding(SkOpSpanBase* start, SkOpSpanBase* end, int winding, 238 int oppWinding, SkOpSpanBase** lastPtr); 239 SkOpSpanBase* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle); 240 SkOpSpanBase* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding, 241 const SkOpAngle* angle); 242 void markDone(SkOpSpan* ); 243 bool markWinding(SkOpSpan* , int winding); 244 bool markWinding(SkOpSpan* , int winding, int oppWinding); 245 bool match(const SkOpPtT* span, const SkOpSegment* parent, double t, const SkPoint& pt) const; 246 void missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc* allocator); 247 void moveMultiples(); 248 void moveNearby(); 249 250 SkOpSegment* next() const { 251 return fNext; 252 } 253 254 SkOpSegment* nextChase(SkOpSpanBase** , int* step, SkOpSpan** , SkOpSpanBase** last) const; 255 bool operand() const; 256 257 static int OppSign(const SkOpSpanBase* start, const SkOpSpanBase* end) { 258 int result = start->t() < end->t() ? -start->upCast()->oppValue() 259 : end->upCast()->oppValue(); 260 return result; 261 } 262 263 bool oppXor() const; 264 265 const SkOpSegment* prev() const { 266 return fPrev; 267 } 268 269 SkPoint ptAtT(double mid) const { 270 return (*CurvePointAtT[fVerb])(fPts, fWeight, mid); 271 } 272 273 const SkPoint* pts() const { 274 return fPts; 275 } 276 277 bool ptsDisjoint(const SkOpPtT& span, const SkOpPtT& test) const { 278 return ptsDisjoint(span.fT, span.fPt, test.fT, test.fPt); 279 } 280 281 bool ptsDisjoint(const SkOpPtT& span, double t, const SkPoint& pt) const { 282 return ptsDisjoint(span.fT, span.fPt, t, pt); 283 } 284 285 bool ptsDisjoint(double t1, const SkPoint& pt1, double t2, const SkPoint& pt2) const; 286 287 void rayCheck(const SkOpRayHit& base, SkOpRayDir dir, SkOpRayHit** hits, 288 SkChunkAlloc* allocator); 289 290 void resetVisited() { 291 fVisited = false; 292 } 293 294 void setContour(SkOpContour* contour) { 295 fContour = contour; 296 } 297 298 void setCubicType(SkDCubic::CubicType cubicType) { 299 fCubicType = cubicType; 300 } 301 302 void setNext(SkOpSegment* next) { 303 fNext = next; 304 } 305 306 void setPrev(SkOpSegment* prev) { 307 fPrev = prev; 308 } 309 310 void setVisited() { 311 fVisited = true; 312 } 313 314 void setUpWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* maxWinding, int* sumWinding) { 315 int deltaSum = SpanSign(start, end); 316 *maxWinding = *sumWinding; 317 *sumWinding -= deltaSum; 318 } 319 320 void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, 321 int* maxWinding, int* sumWinding); 322 void setUpWindings(SkOpSpanBase* start, SkOpSpanBase* end, int* sumMiWinding, int* sumSuWinding, 323 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding); 324 void sortAngles(); 325 326 static int SpanSign(const SkOpSpanBase* start, const SkOpSpanBase* end) { 327 int result = start->t() < end->t() ? -start->upCast()->windValue() 328 : end->upCast()->windValue(); 329 return result; 330 } 331 332 SkOpAngle* spanToAngle(SkOpSpanBase* start, SkOpSpanBase* end) { 333 SkASSERT(start != end); 334 return start->t() < end->t() ? start->upCast()->toAngle() : start->fromAngle(); 335 } 336 337 bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkDCurve* result) const; 338 bool subDivide(const SkOpSpanBase* start, const SkOpSpanBase* end, SkOpCurve* result) const; 339 340 const SkOpSpanBase* tail() const { 341 return &fTail; 342 } 343 344 SkOpSpanBase* tail() { 345 return &fTail; 346 } 347 348 void undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end); 349 int updateOppWinding(const SkOpSpanBase* start, const SkOpSpanBase* end) const; 350 int updateOppWinding(const SkOpAngle* angle) const; 351 int updateOppWindingReverse(const SkOpAngle* angle) const; 352 int updateWinding(SkOpSpanBase* start, SkOpSpanBase* end); 353 int updateWinding(SkOpAngle* angle); 354 int updateWindingReverse(const SkOpAngle* angle); 355 356 static bool UseInnerWinding(int outerWinding, int innerWinding); 357 358 SkPath::Verb verb() const { 359 return fVerb; 360 } 361 362 // look for two different spans that point to the same opposite segment 363 bool visited() { 364 if (!fVisited) { 365 fVisited = true; 366 return false; 367 } 368 return true; 369 } 370 371 SkScalar weight() const { 372 return fWeight; 373 } 374 375 SkOpSpan* windingSpanAtT(double tHit); 376 int windSum(const SkOpAngle* angle) const; 377 378 SkPoint* writablePt(bool end) { 379 return &fPts[end ? SkPathOpsVerbToPoints(fVerb) : 0]; 380 } 381 382 private: 383 SkOpSpan fHead; // the head span always has its t set to zero 384 SkOpSpanBase fTail; // the tail span always has its t set to one 385 SkOpContour* fContour; 386 SkOpSegment* fNext; // forward-only linked list used by contour to walk the segments 387 const SkOpSegment* fPrev; 388 SkPoint* fPts; // pointer into array of points owned by edge builder that may be tweaked 389 SkPathOpsBounds fBounds; // tight bounds 390 SkScalar fWeight; 391 int fCount; // number of spans (one for a non-intersecting segment) 392 int fDoneCount; // number of processed spans (zero initially) 393 SkPath::Verb fVerb; 394 SkDCubic::CubicType fCubicType; 395 bool fTopsFound; 396 bool fVisited; // used by missing coincidence check 397 SkDEBUGCODE(int fID); 398 }; 399 400 #endif 401
