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#if defined(SK_DEBUG) || !FORCE_RELEASE 18#include "SkThread.h" 19#endif 20 21struct SkCoincidence; 22class SkPathWriter; 23 24class SkOpSegment { 25public: 26 SkOpSegment() { 27#if defined(SK_DEBUG) || !FORCE_RELEASE 28 fID = sk_atomic_inc(&SkPathOpsDebug::gSegmentID); 29#endif 30 } 31 32 bool operator<(const SkOpSegment& rh) const { 33 return fBounds.fTop < rh.fBounds.fTop; 34 } 35 36 struct AlignedSpan { 37 double fOldT; 38 double fT; 39 SkPoint fOldPt; 40 SkPoint fPt; 41 const SkOpSegment* fSegment; 42 const SkOpSegment* fOther1; 43 const SkOpSegment* fOther2; 44 }; 45 46 const SkPathOpsBounds& bounds() const { 47 return fBounds; 48 } 49 50 // OPTIMIZE 51 // when the edges are initially walked, they don't automatically get the prior and next 52 // edges assigned to positions t=0 and t=1. Doing that would remove the need for this check, 53 // and would additionally remove the need for similar checks in condition edges. It would 54 // also allow intersection code to assume end of segment intersections (maybe?) 55 bool complete() const { 56 int count = fTs.count(); 57 return count > 1 && fTs[0].fT == 0 && fTs[--count].fT == 1; 58 } 59 60 int count() const { 61 return fTs.count(); 62 } 63 64 bool done() const { 65 SkASSERT(fDoneSpans <= fTs.count()); 66 return fDoneSpans == fTs.count(); 67 } 68 69 bool done(int min) const { 70 return fTs[min].fDone; 71 } 72 73 bool done(const SkOpAngle* angle) const { 74 return done(SkMin32(angle->start(), angle->end())); 75 } 76 77 SkDPoint dPtAtT(double mid) const { 78 return (*CurveDPointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); 79 } 80 81 SkVector dxdy(int index) const { 82 return (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, fTs[index].fT); 83 } 84 85 SkScalar dy(int index) const { 86 return dxdy(index).fY; 87 } 88 89 bool hasMultiples() const { 90 return fMultiples; 91 } 92 93 bool hasSmall() const { 94 return fSmall; 95 } 96 97 bool hasTiny() const { 98 return fTiny; 99 } 100 101 bool intersected() const { 102 return fTs.count() > 0; 103 } 104 105 bool isCanceled(int tIndex) const { 106 return fTs[tIndex].fWindValue == 0 && fTs[tIndex].fOppValue == 0; 107 } 108 109 bool isConnected(int startIndex, int endIndex) const { 110 return fTs[startIndex].fWindSum != SK_MinS32 || fTs[endIndex].fWindSum != SK_MinS32; 111 } 112 113 bool isHorizontal() const { 114 return fBounds.fTop == fBounds.fBottom; 115 } 116 117 bool isVertical() const { 118 return fBounds.fLeft == fBounds.fRight; 119 } 120 121 bool isVertical(int start, int end) const { 122 return (*CurveIsVertical[SkPathOpsVerbToPoints(fVerb)])(fPts, start, end); 123 } 124 125 bool operand() const { 126 return fOperand; 127 } 128 129 int oppSign(const SkOpAngle* angle) const { 130 SkASSERT(angle->segment() == this); 131 return oppSign(angle->start(), angle->end()); 132 } 133 134 int oppSign(int startIndex, int endIndex) const { 135 int result = startIndex < endIndex ? -fTs[startIndex].fOppValue : fTs[endIndex].fOppValue; 136#if DEBUG_WIND_BUMP 137 SkDebugf("%s oppSign=%d\n", __FUNCTION__, result); 138#endif 139 return result; 140 } 141 142 int oppSum(int tIndex) const { 143 return fTs[tIndex].fOppSum; 144 } 145 146 int oppSum(const SkOpAngle* angle) const { 147 int lesser = SkMin32(angle->start(), angle->end()); 148 return fTs[lesser].fOppSum; 149 } 150 151 int oppValue(int tIndex) const { 152 return fTs[tIndex].fOppValue; 153 } 154 155 int oppValue(const SkOpAngle* angle) const { 156 int lesser = SkMin32(angle->start(), angle->end()); 157 return fTs[lesser].fOppValue; 158 } 159 160#if DEBUG_VALIDATE 161 bool oppXor() const { 162 return fOppXor; 163 } 164#endif 165 166 SkPoint ptAtT(double mid) const { 167 return (*CurvePointAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, mid); 168 } 169 170 const SkPoint* pts() const { 171 return fPts; 172 } 173 174 void reset() { 175 init(NULL, (SkPath::Verb) -1, false, false); 176 fBounds.set(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 177 fTs.reset(); 178 } 179 180 void setOppXor(bool isOppXor) { 181 fOppXor = isOppXor; 182 } 183 184 void setUpWinding(int index, int endIndex, int* maxWinding, int* sumWinding) { 185 int deltaSum = spanSign(index, endIndex); 186 *maxWinding = *sumWinding; 187 *sumWinding -= deltaSum; 188 } 189 190 const SkOpSpan& span(int tIndex) const { 191 return fTs[tIndex]; 192 } 193 194 const SkOpAngle* spanToAngle(int tStart, int tEnd) const { 195 SkASSERT(tStart != tEnd); 196 const SkOpSpan& span = fTs[tStart]; 197 return tStart < tEnd ? span.fToAngle : span.fFromAngle; 198 } 199 200 // FIXME: create some sort of macro or template that avoids casting 201 SkOpAngle* spanToAngle(int tStart, int tEnd) { 202 const SkOpAngle* cAngle = (const_cast<const SkOpSegment*>(this))->spanToAngle(tStart, tEnd); 203 return const_cast<SkOpAngle*>(cAngle); 204 } 205 206 int spanSign(const SkOpAngle* angle) const { 207 SkASSERT(angle->segment() == this); 208 return spanSign(angle->start(), angle->end()); 209 } 210 211 int spanSign(int startIndex, int endIndex) const { 212 int result = startIndex < endIndex ? -fTs[startIndex].fWindValue : fTs[endIndex].fWindValue; 213#if DEBUG_WIND_BUMP 214 SkDebugf("%s spanSign=%d\n", __FUNCTION__, result); 215#endif 216 return result; 217 } 218 219 double t(int tIndex) const { 220 return fTs[tIndex].fT; 221 } 222 223 double tAtMid(int start, int end, double mid) const { 224 return fTs[start].fT * (1 - mid) + fTs[end].fT * mid; 225 } 226 227 void updatePts(const SkPoint pts[]) { 228 fPts = pts; 229 } 230 231 SkPath::Verb verb() const { 232 return fVerb; 233 } 234 235 int windSum(int tIndex) const { 236 return fTs[tIndex].fWindSum; 237 } 238 239 int windValue(int tIndex) const { 240 return fTs[tIndex].fWindValue; 241 } 242 243#if defined(SK_DEBUG) || DEBUG_WINDING 244 SkScalar xAtT(int index) const { 245 return xAtT(&fTs[index]); 246 } 247#endif 248 249#if DEBUG_VALIDATE 250 bool _xor() const { // FIXME: used only by SkOpAngle::debugValidateLoop() 251 return fXor; 252 } 253#endif 254 255 const SkPoint& xyAtT(const SkOpSpan* span) const { 256 return span->fPt; 257 } 258 259 const SkPoint& xyAtT(int index) const { 260 return xyAtT(&fTs[index]); 261 } 262 263#if defined(SK_DEBUG) || DEBUG_WINDING 264 SkScalar yAtT(int index) const { 265 return yAtT(&fTs[index]); 266 } 267#endif 268 269 const SkOpAngle* activeAngle(int index, int* start, int* end, bool* done, 270 bool* sortable) const; 271 SkPoint activeLeftTop(int* firstT) const; 272 bool activeOp(int index, int endIndex, int xorMiMask, int xorSuMask, SkPathOp op); 273 bool activeWinding(int index, int endIndex); 274 void addCubic(const SkPoint pts[4], bool operand, bool evenOdd); 275 void addCurveTo(int start, int end, SkPathWriter* path, bool active) const; 276 void addEndSpan(int endIndex); 277 void addLine(const SkPoint pts[2], bool operand, bool evenOdd); 278 void addOtherT(int index, double otherT, int otherIndex); 279 void addQuad(const SkPoint pts[3], bool operand, bool evenOdd); 280 void addSimpleAngle(int endIndex); 281 int addSelfT(const SkPoint& pt, double newT); 282 void addStartSpan(int endIndex); 283 int addT(SkOpSegment* other, const SkPoint& pt, double newT); 284 void addTCancel(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); 285 void addTCoincident(const SkPoint& startPt, const SkPoint& endPt, double endT, 286 SkOpSegment* other); 287 const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, 288 const SkPoint& pt); 289 const SkOpSpan* addTPair(double t, SkOpSegment* other, double otherT, bool borrowWind, 290 const SkPoint& pt, const SkPoint& oPt); 291 void alignMultiples(SkTDArray<AlignedSpan>* aligned); 292 bool alignSpan(int index, double thisT, const SkPoint& thisPt); 293 void alignSpanState(int start, int end); 294 bool betweenTs(int lesser, double testT, int greater) const; 295 void blindCancel(const SkCoincidence& coincidence, SkOpSegment* other); 296 void blindCoincident(const SkCoincidence& coincidence, SkOpSegment* other); 297 bool calcAngles(); 298 double calcMissingTEnd(const SkOpSegment* ref, double loEnd, double min, double max, 299 double hiEnd, const SkOpSegment* other, int thisEnd); 300 double calcMissingTStart(const SkOpSegment* ref, double loEnd, double min, double max, 301 double hiEnd, const SkOpSegment* other, int thisEnd); 302 void checkDuplicates(); 303 void checkEnds(); 304 void checkMultiples(); 305 void checkSmall(); 306 bool checkSmall(int index) const; 307 void checkTiny(); 308 int computeSum(int startIndex, int endIndex, SkOpAngle::IncludeType includeType); 309 bool containsPt(const SkPoint& , int index, int endIndex) const; 310 int crossedSpanY(const SkPoint& basePt, SkScalar* bestY, double* hitT, bool* hitSomething, 311 double mid, bool opp, bool current) const; 312 bool findCoincidentMatch(const SkOpSpan* span, const SkOpSegment* other, int oStart, int oEnd, 313 int step, SkPoint* startPt, SkPoint* endPt, double* endT) const; 314 SkOpSegment* findNextOp(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, 315 bool* unsortable, SkPathOp op, int xorMiMask, int xorSuMask); 316 SkOpSegment* findNextWinding(SkTDArray<SkOpSpan*>* chase, int* nextStart, int* nextEnd, 317 bool* unsortable); 318 SkOpSegment* findNextXor(int* nextStart, int* nextEnd, bool* unsortable); 319 int findExactT(double t, const SkOpSegment* ) const; 320 int findOtherT(double t, const SkOpSegment* ) const; 321 int findT(double t, const SkPoint& , const SkOpSegment* ) const; 322 SkOpSegment* findTop(int* tIndex, int* endIndex, bool* unsortable, bool firstPass); 323 void fixOtherTIndex(); 324 void initWinding(int start, int end, SkOpAngle::IncludeType angleIncludeType); 325 void initWinding(int start, int end, double tHit, int winding, SkScalar hitDx, int oppWind, 326 SkScalar hitOppDx); 327 bool isMissing(double startT, const SkPoint& pt) const; 328 bool isTiny(const SkOpAngle* angle) const; 329 bool joinCoincidence(SkOpSegment* other, double otherT, const SkPoint& otherPt, int step, 330 bool cancel); 331 SkOpSpan* markAndChaseDoneBinary(int index, int endIndex); 332 SkOpSpan* markAndChaseDoneUnary(int index, int endIndex); 333 SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding); 334 SkOpSpan* markAngle(int maxWinding, int sumWinding, int oppMaxWinding, int oppSumWinding, 335 const SkOpAngle* angle); 336 void markDone(int index, int winding); 337 void markDoneBinary(int index); 338 void markDoneUnary(int index); 339 bool nextCandidate(int* start, int* end) const; 340 int nextSpan(int from, int step) const; 341 void pinT(const SkPoint& pt, double* t); 342 void setUpWindings(int index, int endIndex, int* sumMiWinding, int* sumSuWinding, 343 int* maxWinding, int* sumWinding, int* oppMaxWinding, int* oppSumWinding); 344 void sortAngles(); 345 bool subDivide(int start, int end, SkPoint edge[4]) const; 346 bool subDivide(int start, int end, SkDCubic* result) const; 347 void undoneSpan(int* start, int* end); 348 int updateOppWindingReverse(const SkOpAngle* angle) const; 349 int updateWindingReverse(const SkOpAngle* angle) const; 350 static bool UseInnerWinding(int outerWinding, int innerWinding); 351 static bool UseInnerWindingReverse(int outerWinding, int innerWinding); 352 int windingAtT(double tHit, int tIndex, bool crossOpp, SkScalar* dx) const; 353 int windSum(const SkOpAngle* angle) const; 354// available for testing only 355#if defined(SK_DEBUG) || !FORCE_RELEASE 356 int debugID() const { 357 return fID; 358 } 359#else 360 int debugID() const { 361 return -1; 362 } 363#endif 364#if DEBUG_ACTIVE_SPANS || DEBUG_ACTIVE_SPANS_FIRST_ONLY 365 void debugShowActiveSpans() const; 366#endif 367#if DEBUG_CONCIDENT 368 void debugShowTs(const char* prefix) const; 369#endif 370#if DEBUG_SHOW_WINDING 371 int debugShowWindingValues(int slotCount, int ofInterest) const; 372#endif 373 const SkTDArray<SkOpSpan>& debugSpans() const; 374 void debugValidate() const; 375 // available to testing only 376 const SkOpAngle* debugLastAngle() const; 377 void dumpAngles() const; 378 void dumpContour(int firstID, int lastID) const; 379 void dumpPts() const; 380 void dumpSpans() const; 381 382private: 383 struct MissingSpan { 384 double fT; 385 double fEndT; 386 SkOpSegment* fSegment; 387 SkOpSegment* fOther; 388 double fOtherT; 389 SkPoint fPt; 390 }; 391 392 const SkOpAngle* activeAngleInner(int index, int* start, int* end, bool* done, 393 bool* sortable) const; 394 const SkOpAngle* activeAngleOther(int index, int* start, int* end, bool* done, 395 bool* sortable) const; 396 bool activeOp(int xorMiMask, int xorSuMask, int index, int endIndex, SkPathOp op, 397 int* sumMiWinding, int* sumSuWinding); 398 bool activeWinding(int index, int endIndex, int* sumWinding); 399 void addCancelOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); 400 void addCoinOutsides(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); 401 SkOpAngle* addSingletonAngleDown(SkOpSegment** otherPtr, SkOpAngle** ); 402 SkOpAngle* addSingletonAngleUp(SkOpSegment** otherPtr, SkOpAngle** ); 403 SkOpAngle* addSingletonAngles(int step); 404 void alignSpan(const SkPoint& newPt, double newT, const SkOpSegment* other, double otherT, 405 const SkOpSegment* other2, SkOpSpan* oSpan, SkTDArray<AlignedSpan>* ); 406 bool betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const; 407 void bumpCoincidentBlind(bool binary, int index, int last); 408 void bumpCoincidentThis(const SkOpSpan& oTest, bool binary, int* index, 409 SkTArray<SkPoint, true>* outsideTs); 410 void bumpCoincidentOBlind(int index, int last); 411 void bumpCoincidentOther(const SkOpSpan& oTest, int* index, 412 SkTArray<SkPoint, true>* outsideTs); 413 bool bumpSpan(SkOpSpan* span, int windDelta, int oppDelta); 414 bool calcLoopSpanCount(const SkOpSpan& thisSpan, int* smallCounts); 415 bool checkForSmall(const SkOpSpan* span, const SkPoint& pt, double newT, 416 int* less, int* more) const; 417 void checkLinks(const SkOpSpan* , 418 SkTArray<MissingSpan, true>* missingSpans) const; 419 static void CheckOneLink(const SkOpSpan* test, const SkOpSpan* oSpan, 420 const SkOpSpan* oFirst, const SkOpSpan* oLast, 421 const SkOpSpan** missingPtr, 422 SkTArray<MissingSpan, true>* missingSpans); 423 int checkSetAngle(int tIndex) const; 424 void checkSmallCoincidence(const SkOpSpan& span, SkTArray<MissingSpan, true>* ); 425 bool coincidentSmall(const SkPoint& pt, double t, const SkOpSegment* other) const; 426 bool clockwise(int tStart, int tEnd, bool* swap) const; 427 static void ComputeOneSum(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 428 SkOpAngle::IncludeType ); 429 static void ComputeOneSumReverse(const SkOpAngle* baseAngle, SkOpAngle* nextAngle, 430 SkOpAngle::IncludeType ); 431 bool containsT(double t, const SkOpSegment* other, double otherT) const; 432 bool decrementSpan(SkOpSpan* span); 433 int findEndSpan(int endIndex) const; 434 int findStartSpan(int startIndex) const; 435 int firstActive(int tIndex) const; 436 const SkOpSpan& firstSpan(const SkOpSpan& thisSpan) const; 437 void init(const SkPoint pts[], SkPath::Verb verb, bool operand, bool evenOdd); 438 bool inCoincidentSpan(double t, const SkOpSegment* other) const; 439 bool inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPtr) const; 440#if OLD_CHASE 441 bool isSimple(int end) const; 442#else 443 SkOpSegment* isSimple(int* end, int* step); 444#endif 445 bool isTiny(int index) const; 446 const SkOpSpan& lastSpan(const SkOpSpan& thisSpan) const; 447 void matchWindingValue(int tIndex, double t, bool borrowWind); 448 SkOpSpan* markAndChaseDone(int index, int endIndex, int winding); 449 SkOpSpan* markAndChaseDoneBinary(const SkOpAngle* angle, int winding, int oppWinding); 450 SkOpSpan* markAndChaseWinding(const SkOpAngle* angle, int winding); 451 SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding); 452 SkOpSpan* markAndChaseWinding(int index, int endIndex, int winding, int oppWinding); 453 SkOpSpan* markAngle(int maxWinding, int sumWinding, const SkOpAngle* angle); 454 void markDoneBinary(int index, int winding, int oppWinding); 455 SkOpSpan* markAndChaseDoneUnary(const SkOpAngle* angle, int winding); 456 void markOneDone(const char* funName, int tIndex, int winding); 457 void markOneDoneBinary(const char* funName, int tIndex); 458 void markOneDoneBinary(const char* funName, int tIndex, int winding, int oppWinding); 459 void markOneDoneUnary(const char* funName, int tIndex); 460 SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding); 461 SkOpSpan* markOneWinding(const char* funName, int tIndex, int winding, int oppWinding); 462 void markWinding(int index, int winding); 463 void markWinding(int index, int winding, int oppWinding); 464 bool monotonicInY(int tStart, int tEnd) const; 465 466 bool multipleEnds() const { return fTs[count() - 2].fT == 1; } 467 bool multipleStarts() const { return fTs[1].fT == 0; } 468 469 SkOpSegment* nextChase(int* index, int* step, int* min, SkOpSpan** last); 470 int nextExactSpan(int from, int step) const; 471 bool serpentine(int tStart, int tEnd) const; 472 void setCoincidentRange(const SkPoint& startPt, const SkPoint& endPt, SkOpSegment* other); 473 void setFromAngle(int endIndex, SkOpAngle* ); 474 void setToAngle(int endIndex, SkOpAngle* ); 475 void setUpWindings(int index, int endIndex, int* sumMiWinding, 476 int* maxWinding, int* sumWinding); 477 void subDivideBounds(int start, int end, SkPathOpsBounds* bounds) const; 478 static void TrackOutsidePair(SkTArray<SkPoint, true>* outsideTs, const SkPoint& endPt, 479 const SkPoint& startPt); 480 static void TrackOutside(SkTArray<SkPoint, true>* outsideTs, const SkPoint& startPt); 481 int updateOppWinding(int index, int endIndex) const; 482 int updateOppWinding(const SkOpAngle* angle) const; 483 int updateWinding(int index, int endIndex) const; 484 int updateWinding(const SkOpAngle* angle) const; 485 int updateWindingReverse(int index, int endIndex) const; 486 SkOpSpan* verifyOneWinding(const char* funName, int tIndex); 487 SkOpSpan* verifyOneWindingU(const char* funName, int tIndex); 488 489 SkScalar xAtT(const SkOpSpan* span) const { 490 return xyAtT(span).fX; 491 } 492 493 SkScalar yAtT(const SkOpSpan* span) const { 494 return xyAtT(span).fY; 495 } 496 497 void zeroSpan(SkOpSpan* span); 498 499#if DEBUG_SWAP_TOP 500 bool controlsContainedByEnds(int tStart, int tEnd) const; 501#endif 502 void debugAddAngle(int start, int end); 503#if DEBUG_CONCIDENT 504 void debugAddTPair(double t, const SkOpSegment& other, double otherT) const; 505#endif 506#if DEBUG_ANGLE 507 void debugCheckPointsEqualish(int tStart, int tEnd) const; 508#endif 509#if DEBUG_SWAP_TOP 510 int debugInflections(int index, int endIndex) const; 511#endif 512#if DEBUG_MARK_DONE || DEBUG_UNSORTABLE 513 void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding); 514 void debugShowNewWinding(const char* fun, const SkOpSpan& span, int winding, int oppWinding); 515#endif 516#if DEBUG_WINDING 517 static char as_digit(int value) { 518 return value < 0 ? '?' : value <= 9 ? '0' + value : '+'; 519 } 520#endif 521 // available to testing only 522 void debugConstruct(); 523 void debugConstructCubic(SkPoint shortQuad[4]); 524 void debugConstructLine(SkPoint shortQuad[2]); 525 void debugConstructQuad(SkPoint shortQuad[3]); 526 void debugReset(); 527 void dumpDPts() const; 528 void dumpSpan(int index) const; 529 530 const SkPoint* fPts; 531 SkPathOpsBounds fBounds; 532 // FIXME: can't convert to SkTArray because it uses insert 533 SkTDArray<SkOpSpan> fTs; // 2+ (always includes t=0 t=1) -- at least (number of spans) + 1 534 SkOpAngleSet fAngles; // empty or 2+ -- (number of non-zero spans) * 2 535 // OPTIMIZATION: could pack donespans, verb, operand, xor into 1 int-sized value 536 int fDoneSpans; // quick check that segment is finished 537 // OPTIMIZATION: force the following to be byte-sized 538 SkPath::Verb fVerb; 539 bool fLoop; // set if cubic intersects itself 540 bool fMultiples; // set if curve intersects multiple other curves at one interior point 541 bool fOperand; 542 bool fXor; // set if original contour had even-odd fill 543 bool fOppXor; // set if opposite operand had even-odd fill 544 bool fSmall; // set if some span is small 545 bool fTiny; // set if some span is tiny 546#if defined(SK_DEBUG) || !FORCE_RELEASE 547 int fID; 548#endif 549 550 friend class PathOpsSegmentTester; 551}; 552 553#endif 554