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 "SkPathOpsBounds.h" 13 #include "SkPathOpsCurve.h" 14 #include "SkTArray.h" 15 #include "SkTDArray.h" 16 17 class SkPathWriter; 18 19 class SkOpSegment { 20 public: 21 SkOpSegment() { 22 #if DEBUG_DUMP 23 fID = ++gSegmentID; 24 #endif 25 } 26 27 bool operator<(const SkOpSegment& rh) const { 28 return fBounds.fTop < rh.fBounds.fTop; 29 } 30 31 const SkPathOpsBounds& bounds() const { 32 return fBounds; 33 } 34 35 // OPTIMIZE 36 // when the edges are initially walked, they don't automatically get the prior and next 37 // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check, 38 // and would additionally remove the need for similar checks in condition edges. It would 39 // also allow intersection code to assume end of segment intersections (maybe?) 40 bool complete() const { 41 int count = fTs.count(); 42 return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1; 43 } 44 45 int count() const { 46 return fTs.count(); 47 } 48 49 bool done() const { 50 SkASSERT(fDoneSpans <= fTs.count()); 51 return fDoneSpans == fTs.count(); 52 } 53 54 bool done(int min) const { 55 return fTs[min].fDone; 56 } 57 58 bool done(const SkOpAngle* angle) const { 59 return done(SkMin32(angle->start(), angle->end())); 60 } 61 62 SkVector dxdy(int index) const { 63 return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT); 64 } 65 66 SkScalar dy(int index) const { 67 return dxdy(index).fY; 68 } 69 70 bool intersected() const { 71 return fTs.count() > 0; 72 } 73 74 bool isCanceled(int tIndex) const { 75 return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0; 76 } 77 78 bool isConnected(int startIndex, int endIndex) const { 79 return fTs[startIndex].fWindSum != SK_MinS32 || fTs[endIndex].fWindSum != SK_MinS32; 80 } 81 82 bool isHorizontal() const { 83 return fBounds.fTop == fBounds.fBottom; 84 } 85 86 bool isVertical() const { 87 return fBounds.fLeft == fBounds.fRight; 88 } 89 90 bool isVertical(int start, int end) const { 91 return (*CurveIsVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, start, end); 92 } 93 94 bool operand() const { 95 return fOperand; 96 } 97 98 int oppSign(const SkOpAngle* angle) const { 99 SkASSERT(angle->segment() == this); 100 return oppSign(angle->start(), angle->end()); 101 } 102 103 int oppSign(int startIndex, int endIndex) const { 104 int result = startIndex < endIndex ? -fTs[startIndex].fOppValue : fTs[endIndex].fOppValue; 105 #if DEBUG_WIND_BUMP 106 SkDebugf("%s oppSign=%d\n", __FUNCTION__, result); 107 #endif 108 return result; 109 } 110 111 int oppSum(int tIndex) const { 112 return fTs[tIndex].fOppSum; 113 } 114 115 int oppSum(const SkOpAngle* angle) const { 116 int lesser = SkMin32(angle->start(), angle->end()); 117 return fTs[lesser].fOppSum; 118 } 119 120 int oppValue(int tIndex) const { 121 return fTs[tIndex].fOppValue; 122 } 123 124 int oppValue(const SkOpAngle* angle) const { 125 int lesser = SkMin32(angle->start(), angle->end()); 126 return fTs[lesser].fOppValue; 127 } 128 129 const SkOpSegment* other(int index) const { 130 return fTs[index].fOther; 131 } 132 133 // was used only by right angle winding finding 134 SkPoint ptAtT(double mid) const { 135 return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); 136 } 137 138 const SkPoint* pts() const { 139 return fPts; 140 } 141 142 void reset() { 143 init(NULL, (SkPath::Verb) -1, false, false); 144 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 145 fTs.reset(); 146 } 147 148 void setOppXor(bool isOppXor) { 149 fOppXor = isOppXor; 150 } 151 152 void setUpWinding(int index, int endIndex, int* maxWinding, int* sumWinding) { 153 int deltaSum = spanSign(index, endIndex); 154 *maxWinding = *sumWinding; 155 *sumWinding -= deltaSum; 156 } 157 158 // OPTIMIZATION: mark as debugging only if used solely by tests 159 const SkOpSpan& span(int tIndex) const { 160 return fTs[tIndex]; 161 } 162 163 // OPTIMIZATION: mark as debugging only if used solely by tests 164 const SkTDArray<SkOpSpan>& spans() const { 165 return fTs; 166 } 167 168 int spanSign(const SkOpAngle* angle) const { 169 SkASSERT(angle->segment() == this); 170 return spanSign(angle->start(), angle->end()); 171 } 172 173 int spanSign(int startIndex, int endIndex) const { 174 int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : fTs[endIndex].fWindValue; 175 #if DEBUG_WIND_BUMP 176 SkDebugf("%s spanSign=%d\n", __FUNCTION__, result); 177 #endif 178 return result; 179 } 180 181 // OPTIMIZATION: mark as debugging only if used solely by tests 182 double t(int tIndex) const { 183 return fTs[tIndex].fT; 184 } 185 186 double tAtMid(int start, int end, double mid) const { 187 return fTs[start].fT * (1 - mid) + fTs[end].fT * mid; 188 } 189 190 bool unsortable(int index) const { 191 return fTs[index].fUnsortableStart || fTs[index].fUnsortableEnd; 192 } 193 194 void updatePts(const SkPoint pts[]) { 195 fPts = pts; 196 } 197 198 SkPath::Verb verb() const { 199 return fVerb; 200 } 201 202 int windSum(int tIndex) const { 203 return fTs[tIndex].fWindSum; 204 } 205 206 int windValue(int tIndex) const { 207 return fTs[tIndex].fWindValue; 208 } 209 210 SkScalar xAtT(int index) const { 211 return xAtT(&fTs[index]); 212 } 213 214 SkScalar xAtT(const SkOpSpan* span) const { 215 return xyAtT(span).fX; 216 } 217 218 const SkPoint& xyAtT(const SkOpSpan* span) const { 219 return span->fPt; 220 } 221 222 const SkPoint& xyAtT(int index) const { 223 return xyAtT(&fTs[index]); 224 } 225 226 SkScalar yAtT(int index) const { 227 return yAtT(&fTs[index]); 228 } 229 230 SkScalar yAtT(const SkOpSpan* span) const { 231 return xyAtT(span).fY; 232 } 233 234 bool activeAngle(int index, int* done, SkTArray<SkOpAngle, true>* angles); 235 SkPoint activeLeftTop(bool onlySortable, int* firstT) const; 236 bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op); 237 bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op, 238 int* sumMiWinding, int* sumSuWinding, int* maxWinding, int* sumWinding, 239 int* oppMaxWinding, int* oppSumWinding); 240 bool activeWinding(int index, int endIndex); 241 bool activeWinding(int index, int endIndex, int* maxWinding, int* sumWinding); 242 void addCubic(const SkPoint pts[4], bool operand, bool evenOdd); 243 void addCurveTo(int start, int end, SkPathWriter* path, bool active) const; 244 void addLine(const SkPoint pts[2], bool operand, bool evenOdd); 245 void addOtherT(int index, double otherT, int otherIndex); 246 void addQuad(const SkPoint pts[3], bool operand, bool evenOdd); 247 int addSelfT(SkOpSegment* other, const SkPoint& pt, double newT); 248 int addT(SkOpSegment* other, const SkPoint& pt, double newT); 249 void addTCancel(double startT, double endT, SkOpSegment* other, double oStartT, double oEndT); 250 void addTCoincident(double startT, double endT, SkOpSegment* other, double oStartT, 251 double oEndT); 252 void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt); 253 void addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, const SkPoint& pt, 254 const SkPoint& oPt); 255 int addUnsortableT(SkOpSegment* other, bool start, const SkPoint& pt, double newT); 256 bool betweenTs(int lesser, double testT, int greater) const; 257 void checkEnds(); 258 int computeSum(int startIndex, int endIndex, bool binary); 259 int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, 260 double mid, bool opp, bool current) const; 261 SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, 262 bool* unsortable, SkPathOp op, const int xorMiMask, 263 const int xorSuMask); 264 SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, 265 bool* unsortable); 266 SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable); 267 void findTooCloseToCall(); 268 SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool onlySortable); 269 void fixOtherTIndex(); 270 void initWinding(int start, int end); 271 void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind, 272 SkScalar hitOppDx); 273 bool isLinear(int start, int end) const; 274 bool isMissing(double startT) const; 275 bool isSimple(int end) const; 276 bool isTiny(const SkOpAngle* angle) const; 277 bool isTiny(int index) const; 278 SkOpSpan* markAndChaseDoneBinary(int index, int endIndex); 279 SkOpSpan* markAndChaseDoneUnary(int index, int endIndex); 280 SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding); 281 SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding, 282 bool activeAngle, const SkOpAngle* angle); 283 void markDone(int index, int winding); 284 void markDoneBinary(int index); 285 void markDoneUnary(int index); 286 SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding); 287 SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding); 288 void markWinding(int index, int winding); 289 void markWinding(int index, int winding, int oppWinding); 290 bool nextCandidate(int* start, int* end) const; 291 int nextExactSpan(int from, int step) const; 292 int nextSpan(int from, int step) const; 293 void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding, 294 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding); 295 enum SortAngleKind { 296 kMustBeOrdered_SortAngleKind, // required for winding calc 297 kMayBeUnordered_SortAngleKind // ok for find top 298 }; 299 static bool SortAngles(const SkTArray<SkOpAngle, true>& angles, 300 SkTArray<SkOpAngle*, true>* angleList, 301 SortAngleKind ); 302 bool subDivide(int start, int end, SkPoint edge[4]) const; 303 bool subDivide(int start, int end, SkDCubic* result) const; 304 void undoneSpan(int* start, int* end); 305 int updateOppWindingReverse(const SkOpAngle* angle) const; 306 int updateWindingReverse(const SkOpAngle* angle) const; 307 static bool UseInnerWinding(int outerWinding, int innerWinding); 308 int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const; 309 int windSum(const SkOpAngle* angle) const; 310 int windValue(const SkOpAngle* angle) const; 311 312 #if DEBUG_DUMP 313 int debugID() const { 314 return fID; 315 } 316 #endif 317 #if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY 318 void debugShowActiveSpans() const; 319 #endif 320 #if DEBUG_SORT || DEBUG_SWAP_TOP 321 void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first, 322 const int contourWinding, const int oppContourWinding, bool sortable) const; 323 void debugShowSort(const char* fun, const SkTArray<SkOpAngle*, true>& angles, int first, 324 bool sortable); 325 #endif 326 #if DEBUG_CONCIDENT 327 void debugShowTs() const; 328 #endif 329 #if DEBUG_SHOW_WINDING 330 int debugShowWindingValues(int slotCount, int ofInterest) const; 331 #endif 332 333 private: 334 bool activeAngleOther(int index, int* done, SkTArray<SkOpAngle, true>* angles); 335 bool activeAngleInner(int index, int* done, SkTArray<SkOpAngle, true>* angles); 336 void addAngle(SkTArray<SkOpAngle, true>* angles, int start, int end) const; 337 void addCancelOutsides(double tStart, double oStart, SkOpSegment* other, double oEnd); 338 void addCoinOutsides(const SkTArray<double, true>& outsideTs, SkOpSegment* other, double oEnd); 339 void addTwoAngles(int start, int end, SkTArray<SkOpAngle, true>* angles) const; 340 int advanceCoincidentOther(const SkOpSpan* test, double oEndT, int oIndex); 341 int advanceCoincidentThis(const SkOpSpan* oTest, bool opp, int index); 342 void buildAngles(int index, SkTArray<SkOpAngle, true>* angles, bool includeOpp) const; 343 void buildAnglesInner(int index, SkTArray<SkOpAngle, true>* angles) const; 344 int bumpCoincidentThis(const SkOpSpan& oTest, bool opp, int index, 345 SkTArray<double, true>* outsideTs); 346 int bumpCoincidentOther(const SkOpSpan& test, double oEndT, int& oIndex, 347 SkTArray<double, true>* oOutsideTs); 348 bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta); 349 bool clockwise(int tStart, int tEnd) const; 350 void decrementSpan(SkOpSpan* span); 351 bool equalPoints(int greaterTIndex, int lesserTIndex); 352 int findStartingEdge(const SkTArray<SkOpAngle*, true>& sorted, int start, int end); 353 void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd); 354 void matchWindingValue(int tIndex, double t, bool borrowWind); 355 SkOpSpan* markAndChaseDone(int index, int endIndex, int winding); 356 SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding); 357 SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, const int winding); 358 SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding); 359 SkOpSpan* markAngle(int maxWinding, int sumWinding, bool activeAngle, const SkOpAngle* angle); 360 void markDoneBinary(int index, int winding, int oppWinding); 361 SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding); 362 void markOneDone(const char* funName, int tIndex, int winding); 363 void markOneDoneBinary(const char* funName, int tIndex); 364 void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding); 365 void markOneDoneUnary(const char* funName, int tIndex); 366 void markUnsortable(int start, int end); 367 bool monotonicInY(int tStart, int tEnd) const; 368 bool multipleSpans(int end) const; 369 SkOpSegment* nextChase(int* index, const int step, int* min, SkOpSpan** last); 370 bool serpentine(int tStart, int tEnd) const; 371 void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const; 372 static void TrackOutside(SkTArray<double, true>* outsideTs, double end, double start); 373 int updateOppWinding(int index, int endIndex) const; 374 int updateOppWinding(const SkOpAngle* angle) const; 375 int updateWinding(int index, int endIndex) const; 376 int updateWinding(const SkOpAngle* angle) const; 377 SkOpSpan* verifyOneWinding(const char* funName, int tIndex); 378 SkOpSpan* verifyOneWindingU(const char* funName, int tIndex); 379 int windValueAt(double t) const; 380 void zeroSpan(SkOpSpan* span); 381 382 #if DEBUG_SWAP_TOP 383 bool controlsContainedByEnds(int tStart, int tEnd) const; 384 #endif 385 #if DEBUG_CONCIDENT 386 void debugAddTPair(double t, const SkOpSegment& other, double otherT) const; 387 #endif 388 #if DEBUG_MARK_DONE || DEBUG_UNSORTABLE 389 void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding); 390 void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding); 391 #endif 392 #if DEBUG_WINDING 393 static char as_digit(int value) { 394 return value < 0 ? '?' : value <= 9 ? '0' + value : '+'; 395 } 396 #endif 397 void debugValidate() const; 398 399 const SkPoint* fPts; 400 SkPathOpsBounds fBounds; 401 // FIXME: can't convert to SkTArray because it uses insert 402 SkTDArray<SkOpSpan> fTs; // two or more (always includes t=0 t=1) 403 // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value 404 int fDoneSpans; // quick check that segment is finished 405 // OPTIMIZATION: force the following to be byte-sized 406 SkPath::Verb fVerb; 407 bool fOperand; 408 bool fXor; // set if original contour had even-odd fill 409 bool fOppXor; // set if opposite operand had even-odd fill 410 #if DEBUG_DUMP 411 int fID; 412 #endif 413 }; 414 415 #endif 416
