1 /* 2 * Copyright 2014 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 SkPathOpsTSect_DEFINED 8 #define SkPathOpsTSect_DEFINED 9 10 #include "SkArenaAlloc.h" 11 #include "SkPathOpsBounds.h" 12 #include "SkPathOpsRect.h" 13 #include "SkIntersections.h" 14 #include "SkTSort.h" 15 16 #ifdef SK_DEBUG 17 typedef uint8_t SkOpDebugBool; 18 #else 19 typedef bool SkOpDebugBool; 20 #endif 21 22 /* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */ 23 template<typename TCurve, typename OppCurve> 24 class SkTCoincident { 25 public: 26 SkTCoincident() { 27 this->init(); 28 } 29 30 void debugInit() { 31 #ifdef SK_DEBUG 32 this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN; 33 this->fPerpT = SK_ScalarNaN; 34 this->fMatch = 0xFF; 35 #endif 36 } 37 38 char dumpIsCoincidentStr() const; 39 void dump() const; 40 41 bool isMatch() const { 42 SkASSERT(!!fMatch == fMatch); 43 return SkToBool(fMatch); 44 } 45 46 void init() { 47 fPerpT = -1; 48 fMatch = false; 49 fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN; 50 } 51 52 void markCoincident() { 53 if (!fMatch) { 54 fPerpT = -1; 55 } 56 fMatch = true; 57 } 58 59 const SkDPoint& perpPt() const { 60 return fPerpPt; 61 } 62 63 double perpT() const { 64 return fPerpT; 65 } 66 67 void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve& ); 68 69 private: 70 SkDPoint fPerpPt; 71 double fPerpT; // perpendicular intersection on opposite curve 72 SkOpDebugBool fMatch; 73 }; 74 75 template<typename TCurve, typename OppCurve> class SkTSect; 76 template<typename TCurve, typename OppCurve> class SkTSpan; 77 78 template<typename TCurve, typename OppCurve> 79 struct SkTSpanBounded { 80 SkTSpan<TCurve, OppCurve>* fBounded; 81 SkTSpanBounded* fNext; 82 }; 83 84 /* Curve is either TCurve or SkDCubic */ 85 template<typename TCurve, typename OppCurve> 86 class SkTSpan { 87 public: 88 void addBounded(SkTSpan<OppCurve, TCurve>* , SkArenaAlloc* ); 89 double closestBoundedT(const SkDPoint& pt) const; 90 bool contains(double t) const; 91 92 void debugInit() { 93 TCurve dummy; 94 dummy.debugInit(); 95 init(dummy); 96 initBounds(dummy); 97 fCoinStart.init(); 98 fCoinEnd.init(); 99 } 100 101 const SkTSect<OppCurve, TCurve>* debugOpp() const; 102 103 #ifdef SK_DEBUG 104 void debugSetGlobalState(SkOpGlobalState* state) { 105 fDebugGlobalState = state; 106 } 107 #endif 108 109 const SkTSpan* debugSpan(int ) const; 110 const SkTSpan* debugT(double t) const; 111 #ifdef SK_DEBUG 112 bool debugIsBefore(const SkTSpan* span) const; 113 #endif 114 void dump() const; 115 void dumpAll() const; 116 void dumpBounded(int id) const; 117 void dumpBounds() const; 118 void dumpCoin() const; 119 120 double endT() const { 121 return fEndT; 122 } 123 124 SkTSpan<OppCurve, TCurve>* findOppSpan(const SkTSpan<OppCurve, TCurve>* opp) const; 125 126 SkTSpan<OppCurve, TCurve>* findOppT(double t) const { 127 SkTSpan<OppCurve, TCurve>* result = oppT(t); 128 SkOPASSERT(result); 129 return result; 130 } 131 132 SkDEBUGCODE(SkOpGlobalState* globalState() const { return fDebugGlobalState; }) 133 134 bool hasOppT(double t) const { 135 return SkToBool(oppT(t)); 136 } 137 138 int hullsIntersect(SkTSpan<OppCurve, TCurve>* span, bool* start, bool* oppStart); 139 void init(const TCurve& ); 140 bool initBounds(const TCurve& ); 141 142 bool isBounded() const { 143 return fBounded != nullptr; 144 } 145 146 bool linearsIntersect(SkTSpan<OppCurve, TCurve>* span); 147 double linearT(const SkDPoint& ) const; 148 149 void markCoincident() { 150 fCoinStart.markCoincident(); 151 fCoinEnd.markCoincident(); 152 } 153 154 const SkTSpan* next() const { 155 return fNext; 156 } 157 158 bool onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, bool* start, 159 bool* oppStart, bool* ptsInCommon); 160 161 const TCurve& part() const { 162 return fPart; 163 } 164 165 bool removeAllBounded(); 166 bool removeBounded(const SkTSpan<OppCurve, TCurve>* opp); 167 168 void reset() { 169 fBounded = nullptr; 170 } 171 172 void resetBounds(const TCurve& curve) { 173 fIsLinear = fIsLine = false; 174 initBounds(curve); 175 } 176 177 bool split(SkTSpan* work, SkArenaAlloc* heap) { 178 return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap); 179 } 180 181 bool splitAt(SkTSpan* work, double t, SkArenaAlloc* heap); 182 183 double startT() const { 184 return fStartT; 185 } 186 187 private: 188 189 // implementation is for testing only 190 int debugID() const { 191 return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); 192 } 193 194 void dumpID() const; 195 196 int hullCheck(const SkTSpan<OppCurve, TCurve>* opp, bool* start, bool* oppStart); 197 int linearIntersects(const OppCurve& ) const; 198 SkTSpan<OppCurve, TCurve>* oppT(double t) const; 199 200 void validate() const; 201 void validateBounded() const; 202 void validatePerpT(double oppT) const; 203 void validatePerpPt(double t, const SkDPoint& ) const; 204 205 TCurve fPart; 206 SkTCoincident<TCurve, OppCurve> fCoinStart; 207 SkTCoincident<TCurve, OppCurve> fCoinEnd; 208 SkTSpanBounded<OppCurve, TCurve>* fBounded; 209 SkTSpan* fPrev; 210 SkTSpan* fNext; 211 SkDRect fBounds; 212 double fStartT; 213 double fEndT; 214 double fBoundsMax; 215 SkOpDebugBool fCollapsed; 216 SkOpDebugBool fHasPerp; 217 SkOpDebugBool fIsLinear; 218 SkOpDebugBool fIsLine; 219 SkOpDebugBool fDeleted; 220 SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); 221 SkDEBUGCODE(SkTSect<TCurve, OppCurve>* fDebugSect); 222 PATH_OPS_DEBUG_T_SECT_CODE(int fID); 223 friend class SkTSect<TCurve, OppCurve>; 224 friend class SkTSect<OppCurve, TCurve>; 225 friend class SkTSpan<OppCurve, TCurve>; 226 }; 227 228 template<typename TCurve, typename OppCurve> 229 class SkTSect { 230 public: 231 SkTSect(const TCurve& c SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id)); 232 static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2, 233 SkIntersections* intersections); 234 235 SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; }) 236 // for testing only 237 bool debugHasBounded(const SkTSpan<OppCurve, TCurve>* ) const; 238 239 const SkTSect<OppCurve, TCurve>* debugOpp() const { 240 return SkDEBUGRELEASE(fOppSect, nullptr); 241 } 242 243 const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const; 244 const SkTSpan<TCurve, OppCurve>* debugT(double t) const; 245 void dump() const; 246 void dumpBoth(SkTSect<OppCurve, TCurve>* ) const; 247 void dumpBounded(int id) const; 248 void dumpBounds() const; 249 void dumpCoin() const; 250 void dumpCoinCurves() const; 251 void dumpCurves() const; 252 253 private: 254 enum { 255 kZeroS1Set = 1, 256 kOneS1Set = 2, 257 kZeroS2Set = 4, 258 kOneS2Set = 8 259 }; 260 261 SkTSpan<TCurve, OppCurve>* addFollowing(SkTSpan<TCurve, OppCurve>* prior); 262 void addForPerp(SkTSpan<OppCurve, TCurve>* span, double t); 263 SkTSpan<TCurve, OppCurve>* addOne(); 264 265 SkTSpan<TCurve, OppCurve>* addSplitAt(SkTSpan<TCurve, OppCurve>* span, double t) { 266 SkTSpan<TCurve, OppCurve>* result = this->addOne(); 267 SkDEBUGCODE(result->debugSetGlobalState(this->globalState())); 268 result->splitAt(span, t, &fHeap); 269 result->initBounds(fCurve); 270 span->initBounds(fCurve); 271 return result; 272 } 273 274 bool binarySearchCoin(SkTSect<OppCurve, TCurve>* , double tStart, double tStep, double* t, 275 double* oppT); 276 SkTSpan<TCurve, OppCurve>* boundsMax() const; 277 bool coincidentCheck(SkTSect<OppCurve, TCurve>* sect2); 278 void coincidentForce(SkTSect<OppCurve, TCurve>* sect2, double start1s, double start1e); 279 bool coincidentHasT(double t); 280 int collapsed() const; 281 void computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first, 282 SkTSpan<TCurve, OppCurve>* last); 283 int countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first, 284 SkTSpan<TCurve, OppCurve>** last) const; 285 286 int debugID() const { 287 return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); 288 } 289 290 bool deleteEmptySpans(); 291 void dumpCommon(const SkTSpan<TCurve, OppCurve>* ) const; 292 void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const; 293 static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>* sect2, 294 SkIntersections* ); 295 bool extractCoincident(SkTSect<OppCurve, TCurve>* sect2, SkTSpan<TCurve, OppCurve>* first, 296 SkTSpan<TCurve, OppCurve>* last, SkTSpan<TCurve, OppCurve>** result); 297 SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* first, 298 SkTSpan<TCurve, OppCurve>** lastPtr); 299 int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp, 300 SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult); 301 bool isParallel(const SkDLine& thisLine, const SkTSect<OppCurve, TCurve>* opp) const; 302 int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp, 303 SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* ); 304 bool markSpanGone(SkTSpan<TCurve, OppCurve>* span); 305 bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2) const; 306 void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, double t2, 307 bool* calcMatched, bool* oppMatched) const; 308 void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2); 309 SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const; 310 void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp); 311 void recoverCollapsed(); 312 void removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween); 313 void removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, SkTSpan<TCurve, OppCurve>* span, 314 SkTSect<OppCurve, TCurve>* opp); 315 bool removeSpan(SkTSpan<TCurve, OppCurve>* span); 316 void removeSpanRange(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last); 317 void removeSpans(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp); 318 void removedEndCheck(SkTSpan<TCurve, OppCurve>* span); 319 320 void resetRemovedEnds() { 321 fRemovedStartT = fRemovedEndT = false; 322 } 323 324 SkTSpan<TCurve, OppCurve>* spanAtT(double t, SkTSpan<TCurve, OppCurve>** priorSpan); 325 SkTSpan<TCurve, OppCurve>* tail(); 326 bool trim(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp); 327 void unlinkSpan(SkTSpan<TCurve, OppCurve>* span); 328 bool updateBounded(SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last, 329 SkTSpan<OppCurve, TCurve>* oppFirst); 330 void validate() const; 331 void validateBounded() const; 332 333 const TCurve& fCurve; 334 SkArenaAlloc fHeap; 335 SkTSpan<TCurve, OppCurve>* fHead; 336 SkTSpan<TCurve, OppCurve>* fCoincident; 337 SkTSpan<TCurve, OppCurve>* fDeleted; 338 int fActiveCount; 339 bool fRemovedStartT; 340 bool fRemovedEndT; 341 SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); 342 SkDEBUGCODE(SkTSect<OppCurve, TCurve>* fOppSect); 343 PATH_OPS_DEBUG_T_SECT_CODE(int fID); 344 PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount); 345 #if DEBUG_T_SECT 346 int fDebugAllocatedCount; 347 #endif 348 friend class SkTSpan<TCurve, OppCurve>; 349 friend class SkTSpan<OppCurve, TCurve>; 350 friend class SkTSect<OppCurve, TCurve>; 351 }; 352 353 #define COINCIDENT_SPAN_COUNT 9 354 355 template<typename TCurve, typename OppCurve> 356 void SkTCoincident<TCurve, OppCurve>::setPerp(const TCurve& c1, double t, 357 const SkDPoint& cPt, const OppCurve& c2) { 358 SkDVector dxdy = c1.dxdyAtT(t); 359 SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }}; 360 SkIntersections i SkDEBUGCODE((c1.globalState())); 361 int used = i.intersectRay(c2, perp); 362 // only keep closest 363 if (used == 0 || used == 3) { 364 this->init(); 365 return; 366 } 367 fPerpT = i[0][0]; 368 fPerpPt = i.pt(0); 369 SkASSERT(used <= 2); 370 if (used == 2) { 371 double distSq = (fPerpPt - cPt).lengthSquared(); 372 double dist2Sq = (i.pt(1) - cPt).lengthSquared(); 373 if (dist2Sq < distSq) { 374 fPerpT = i[0][1]; 375 fPerpPt = i.pt(1); 376 } 377 } 378 #if DEBUG_T_SECT 379 SkDebugf("setPerp t=%1.9g cPt=(%1.9g,%1.9g) %s oppT=%1.9g fPerpPt=(%1.9g,%1.9g)\n", 380 t, cPt.fX, cPt.fY, 381 cPt.approximatelyEqual(fPerpPt) ? "==" : "!=", fPerpT, fPerpPt.fX, fPerpPt.fY); 382 #endif 383 fMatch = cPt.approximatelyEqual(fPerpPt); 384 #if DEBUG_T_SECT 385 if (fMatch) { 386 SkDebugf(""); // allow setting breakpoint 387 } 388 #endif 389 } 390 391 template<typename TCurve, typename OppCurve> 392 void SkTSpan<TCurve, OppCurve>::addBounded(SkTSpan<OppCurve, TCurve>* span, SkArenaAlloc* heap) { 393 SkTSpanBounded<OppCurve, TCurve>* bounded = heap->make<SkTSpanBounded<OppCurve, TCurve>>(); 394 bounded->fBounded = span; 395 bounded->fNext = fBounded; 396 fBounded = bounded; 397 } 398 399 template<typename TCurve, typename OppCurve> 400 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addFollowing( 401 SkTSpan<TCurve, OppCurve>* prior) { 402 SkTSpan<TCurve, OppCurve>* result = this->addOne(); 403 SkDEBUGCODE(result->debugSetGlobalState(this->globalState())); 404 result->fStartT = prior ? prior->fEndT : 0; 405 SkTSpan<TCurve, OppCurve>* next = prior ? prior->fNext : fHead; 406 result->fEndT = next ? next->fStartT : 1; 407 result->fPrev = prior; 408 result->fNext = next; 409 if (prior) { 410 prior->fNext = result; 411 } else { 412 fHead = result; 413 } 414 if (next) { 415 next->fPrev = result; 416 } 417 result->resetBounds(fCurve); 418 result->validate(); 419 return result; 420 } 421 422 template<typename TCurve, typename OppCurve> 423 void SkTSect<TCurve, OppCurve>::addForPerp(SkTSpan<OppCurve, TCurve>* span, double t) { 424 if (!span->hasOppT(t)) { 425 SkTSpan<TCurve, OppCurve>* priorSpan; 426 SkTSpan<TCurve, OppCurve>* opp = this->spanAtT(t, &priorSpan); 427 if (!opp) { 428 opp = this->addFollowing(priorSpan); 429 #if DEBUG_PERP 430 SkDebugf("%s priorSpan=%d t=%1.9g opp=%d\n", __FUNCTION__, priorSpan ? 431 priorSpan->debugID() : -1, t, opp->debugID()); 432 #endif 433 } 434 #if DEBUG_PERP 435 opp->dump(); SkDebugf("\n"); 436 SkDebugf("%s addBounded span=%d opp=%d\n", __FUNCTION__, priorSpan ? 437 priorSpan->debugID() : -1, opp->debugID()); 438 #endif 439 opp->addBounded(span, &fHeap); 440 span->addBounded(opp, &fHeap); 441 } 442 this->validate(); 443 #if DEBUG_T_SECT 444 span->validatePerpT(t); 445 #endif 446 } 447 448 template<typename TCurve, typename OppCurve> 449 double SkTSpan<TCurve, OppCurve>::closestBoundedT(const SkDPoint& pt) const { 450 double result = -1; 451 double closest = DBL_MAX; 452 const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; 453 while (testBounded) { 454 const SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded; 455 double startDist = test->fPart[0].distanceSquared(pt); 456 if (closest > startDist) { 457 closest = startDist; 458 result = test->fStartT; 459 } 460 double endDist = test->fPart[OppCurve::kPointLast].distanceSquared(pt); 461 if (closest > endDist) { 462 closest = endDist; 463 result = test->fEndT; 464 } 465 testBounded = testBounded->fNext; 466 } 467 SkASSERT(between(0, result, 1)); 468 return result; 469 } 470 471 #ifdef SK_DEBUG 472 template<typename TCurve, typename OppCurve> 473 bool SkTSpan<TCurve, OppCurve>::debugIsBefore(const SkTSpan* span) const { 474 const SkTSpan* work = this; 475 do { 476 if (span == work) { 477 return true; 478 } 479 } while ((work = work->fNext)); 480 return false; 481 } 482 #endif 483 484 template<typename TCurve, typename OppCurve> 485 bool SkTSpan<TCurve, OppCurve>::contains(double t) const { 486 const SkTSpan* work = this; 487 do { 488 if (between(work->fStartT, t, work->fEndT)) { 489 return true; 490 } 491 } while ((work = work->fNext)); 492 return false; 493 } 494 495 template<typename TCurve, typename OppCurve> 496 const SkTSect<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::debugOpp() const { 497 return SkDEBUGRELEASE(fDebugSect->debugOpp(), nullptr); 498 } 499 500 template<typename TCurve, typename OppCurve> 501 SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::findOppSpan( 502 const SkTSpan<OppCurve, TCurve>* opp) const { 503 SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 504 while (bounded) { 505 SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; 506 if (opp == test) { 507 return test; 508 } 509 bounded = bounded->fNext; 510 } 511 return nullptr; 512 } 513 514 // returns 0 if no hull intersection 515 // 1 if hulls intersect 516 // 2 if hulls only share a common endpoint 517 // -1 if linear and further checking is required 518 template<typename TCurve, typename OppCurve> 519 int SkTSpan<TCurve, OppCurve>::hullCheck(const SkTSpan<OppCurve, TCurve>* opp, 520 bool* start, bool* oppStart) { 521 if (fIsLinear) { 522 return -1; 523 } 524 bool ptsInCommon; 525 if (onlyEndPointsInCommon(opp, start, oppStart, &ptsInCommon)) { 526 SkASSERT(ptsInCommon); 527 return 2; 528 } 529 bool linear; 530 if (fPart.hullIntersects(opp->fPart, &linear)) { 531 if (!linear) { // check set true if linear 532 return 1; 533 } 534 fIsLinear = true; 535 fIsLine = fPart.controlsInside(); 536 return ptsInCommon ? 1 : -1; 537 } else { // hull is not linear; check set true if intersected at the end points 538 return ((int) ptsInCommon) << 1; // 0 or 2 539 } 540 return 0; 541 } 542 543 // OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear, 544 // use line intersection to guess a better split than 0.5 545 // OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear 546 template<typename TCurve, typename OppCurve> 547 int SkTSpan<TCurve, OppCurve>::hullsIntersect(SkTSpan<OppCurve, TCurve>* opp, 548 bool* start, bool* oppStart) { 549 if (!fBounds.intersects(opp->fBounds)) { 550 return 0; 551 } 552 int hullSect = this->hullCheck(opp, start, oppStart); 553 if (hullSect >= 0) { 554 return hullSect; 555 } 556 hullSect = opp->hullCheck(this, oppStart, start); 557 if (hullSect >= 0) { 558 return hullSect; 559 } 560 return -1; 561 } 562 563 template<typename TCurve, typename OppCurve> 564 void SkTSpan<TCurve, OppCurve>::init(const TCurve& c) { 565 fPrev = fNext = nullptr; 566 fStartT = 0; 567 fEndT = 1; 568 fBounded = nullptr; 569 resetBounds(c); 570 } 571 572 template<typename TCurve, typename OppCurve> 573 bool SkTSpan<TCurve, OppCurve>::initBounds(const TCurve& c) { 574 fPart = c.subDivide(fStartT, fEndT); 575 fBounds.setBounds(fPart); 576 fCoinStart.init(); 577 fCoinEnd.init(); 578 fBoundsMax = SkTMax(fBounds.width(), fBounds.height()); 579 fCollapsed = fPart.collapsed(); 580 fHasPerp = false; 581 fDeleted = false; 582 #if DEBUG_T_SECT 583 if (fCollapsed) { 584 SkDebugf(""); // for convenient breakpoints 585 } 586 #endif 587 return fBounds.valid(); 588 } 589 590 template<typename TCurve, typename OppCurve> 591 bool SkTSpan<TCurve, OppCurve>::linearsIntersect(SkTSpan<OppCurve, TCurve>* span) { 592 int result = this->linearIntersects(span->fPart); 593 if (result <= 1) { 594 return SkToBool(result); 595 } 596 SkASSERT(span->fIsLinear); 597 result = span->linearIntersects(this->fPart); 598 // SkASSERT(result <= 1); 599 return SkToBool(result); 600 } 601 602 template<typename TCurve, typename OppCurve> 603 double SkTSpan<TCurve, OppCurve>::linearT(const SkDPoint& pt) const { 604 SkDVector len = fPart[TCurve::kPointLast] - fPart[0]; 605 return fabs(len.fX) > fabs(len.fY) 606 ? (pt.fX - fPart[0].fX) / len.fX 607 : (pt.fY - fPart[0].fY) / len.fY; 608 } 609 610 template<typename TCurve, typename OppCurve> 611 int SkTSpan<TCurve, OppCurve>::linearIntersects(const OppCurve& q2) const { 612 // looks like q1 is near-linear 613 int start = 0, end = TCurve::kPointLast; // the outside points are usually the extremes 614 if (!fPart.controlsInside()) { 615 double dist = 0; // if there's any question, compute distance to find best outsiders 616 for (int outer = 0; outer < TCurve::kPointCount - 1; ++outer) { 617 for (int inner = outer + 1; inner < TCurve::kPointCount; ++inner) { 618 double test = (fPart[outer] - fPart[inner]).lengthSquared(); 619 if (dist > test) { 620 continue; 621 } 622 dist = test; 623 start = outer; 624 end = inner; 625 } 626 } 627 } 628 // see if q2 is on one side of the line formed by the extreme points 629 double origX = fPart[start].fX; 630 double origY = fPart[start].fY; 631 double adj = fPart[end].fX - origX; 632 double opp = fPart[end].fY - origY; 633 double maxPart = SkTMax(fabs(adj), fabs(opp)); 634 double sign = 0; // initialization to shut up warning in release build 635 for (int n = 0; n < OppCurve::kPointCount; ++n) { 636 double dx = q2[n].fY - origY; 637 double dy = q2[n].fX - origX; 638 double maxVal = SkTMax(maxPart, SkTMax(fabs(dx), fabs(dy))); 639 double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp; 640 if (precisely_zero_when_compared_to(test, maxVal)) { 641 return 1; 642 } 643 if (approximately_zero_when_compared_to(test, maxVal)) { 644 return 3; 645 } 646 if (n == 0) { 647 sign = test; 648 continue; 649 } 650 if (test * sign < 0) { 651 return 1; 652 } 653 } 654 return 0; 655 } 656 657 template<typename TCurve, typename OppCurve> 658 bool SkTSpan<TCurve, OppCurve>::onlyEndPointsInCommon(const SkTSpan<OppCurve, TCurve>* opp, 659 bool* start, bool* oppStart, bool* ptsInCommon) { 660 if (opp->fPart[0] == fPart[0]) { 661 *start = *oppStart = true; 662 } else if (opp->fPart[0] == fPart[TCurve::kPointLast]) { 663 *start = false; 664 *oppStart = true; 665 } else if (opp->fPart[OppCurve::kPointLast] == fPart[0]) { 666 *start = true; 667 *oppStart = false; 668 } else if (opp->fPart[OppCurve::kPointLast] == fPart[TCurve::kPointLast]) { 669 *start = *oppStart = false; 670 } else { 671 *ptsInCommon = false; 672 return false; 673 } 674 *ptsInCommon = true; 675 const SkDPoint* otherPts[TCurve::kPointCount - 1], * oppOtherPts[OppCurve::kPointCount - 1]; 676 int baseIndex = *start ? 0 : TCurve::kPointLast; 677 fPart.otherPts(baseIndex, otherPts); 678 opp->fPart.otherPts(*oppStart ? 0 : OppCurve::kPointLast, oppOtherPts); 679 const SkDPoint& base = fPart[baseIndex]; 680 for (int o1 = 0; o1 < (int) SK_ARRAY_COUNT(otherPts); ++o1) { 681 SkDVector v1 = *otherPts[o1] - base; 682 for (int o2 = 0; o2 < (int) SK_ARRAY_COUNT(oppOtherPts); ++o2) { 683 SkDVector v2 = *oppOtherPts[o2] - base; 684 if (v2.dot(v1) >= 0) { 685 return false; 686 } 687 } 688 } 689 return true; 690 } 691 692 template<typename TCurve, typename OppCurve> 693 SkTSpan<OppCurve, TCurve>* SkTSpan<TCurve, OppCurve>::oppT(double t) const { 694 SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 695 while (bounded) { 696 SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; 697 if (between(test->fStartT, t, test->fEndT)) { 698 return test; 699 } 700 bounded = bounded->fNext; 701 } 702 return nullptr; 703 } 704 705 template<typename TCurve, typename OppCurve> 706 bool SkTSpan<TCurve, OppCurve>::removeAllBounded() { 707 bool deleteSpan = false; 708 SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 709 while (bounded) { 710 SkTSpan<OppCurve, TCurve>* opp = bounded->fBounded; 711 deleteSpan |= opp->removeBounded(this); 712 bounded = bounded->fNext; 713 } 714 return deleteSpan; 715 } 716 717 template<typename TCurve, typename OppCurve> 718 bool SkTSpan<TCurve, OppCurve>::removeBounded(const SkTSpan<OppCurve, TCurve>* opp) { 719 if (fHasPerp) { 720 bool foundStart = false; 721 bool foundEnd = false; 722 SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 723 while (bounded) { 724 SkTSpan<OppCurve, TCurve>* test = bounded->fBounded; 725 if (opp != test) { 726 foundStart |= between(test->fStartT, fCoinStart.perpT(), test->fEndT); 727 foundEnd |= between(test->fStartT, fCoinEnd.perpT(), test->fEndT); 728 } 729 bounded = bounded->fNext; 730 } 731 if (!foundStart || !foundEnd) { 732 fHasPerp = false; 733 fCoinStart.init(); 734 fCoinEnd.init(); 735 } 736 } 737 SkTSpanBounded<OppCurve, TCurve>* bounded = fBounded; 738 SkTSpanBounded<OppCurve, TCurve>* prev = nullptr; 739 while (bounded) { 740 SkTSpanBounded<OppCurve, TCurve>* boundedNext = bounded->fNext; 741 if (opp == bounded->fBounded) { 742 if (prev) { 743 prev->fNext = boundedNext; 744 return false; 745 } else { 746 fBounded = boundedNext; 747 return fBounded == nullptr; 748 } 749 } 750 prev = bounded; 751 bounded = boundedNext; 752 } 753 SkOPASSERT(0); 754 return false; 755 } 756 757 template<typename TCurve, typename OppCurve> 758 bool SkTSpan<TCurve, OppCurve>::splitAt(SkTSpan* work, double t, SkArenaAlloc* heap) { 759 fStartT = t; 760 fEndT = work->fEndT; 761 if (fStartT == fEndT) { 762 fCollapsed = true; 763 return false; 764 } 765 work->fEndT = t; 766 if (work->fStartT == work->fEndT) { 767 work->fCollapsed = true; 768 return false; 769 } 770 fPrev = work; 771 fNext = work->fNext; 772 fIsLinear = work->fIsLinear; 773 fIsLine = work->fIsLine; 774 775 work->fNext = this; 776 if (fNext) { 777 fNext->fPrev = this; 778 } 779 this->validate(); 780 SkTSpanBounded<OppCurve, TCurve>* bounded = work->fBounded; 781 fBounded = nullptr; 782 while (bounded) { 783 this->addBounded(bounded->fBounded, heap); 784 bounded = bounded->fNext; 785 } 786 bounded = fBounded; 787 while (bounded) { 788 bounded->fBounded->addBounded(this, heap); 789 bounded = bounded->fNext; 790 } 791 return true; 792 } 793 794 template<typename TCurve, typename OppCurve> 795 void SkTSpan<TCurve, OppCurve>::validate() const { 796 #if DEBUG_VALIDATE 797 SkASSERT(this != fPrev); 798 SkASSERT(this != fNext); 799 SkASSERT(fNext == nullptr || fNext != fPrev); 800 SkASSERT(fNext == nullptr || this == fNext->fPrev); 801 SkASSERT(fPrev == nullptr || this == fPrev->fNext); 802 this->validateBounded(); 803 #endif 804 #if DEBUG_T_SECT 805 SkASSERT(fBounds.width() || fBounds.height() || fCollapsed); 806 SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()) || fCollapsed == 0xFF); 807 SkASSERT(0 <= fStartT); 808 SkASSERT(fEndT <= 1); 809 SkASSERT(fStartT <= fEndT); 810 SkASSERT(fBounded || fCollapsed == 0xFF); 811 if (fHasPerp) { 812 if (fCoinStart.isMatch()) { 813 validatePerpT(fCoinStart.perpT()); 814 validatePerpPt(fCoinStart.perpT(), fCoinStart.perpPt()); 815 } 816 if (fCoinEnd.isMatch()) { 817 validatePerpT(fCoinEnd.perpT()); 818 validatePerpPt(fCoinEnd.perpT(), fCoinEnd.perpPt()); 819 } 820 } 821 #endif 822 } 823 824 template<typename TCurve, typename OppCurve> 825 void SkTSpan<TCurve, OppCurve>::validateBounded() const { 826 #if DEBUG_VALIDATE 827 const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; 828 while (testBounded) { 829 SkDEBUGCODE(const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded); 830 SkASSERT(!overlap->fDeleted); 831 #if DEBUG_T_SECT 832 SkASSERT(((this->debugID() ^ overlap->debugID()) & 1) == 1); 833 SkASSERT(overlap->findOppSpan(this)); 834 #endif 835 testBounded = testBounded->fNext; 836 } 837 #endif 838 } 839 840 template<typename TCurve, typename OppCurve> 841 void SkTSpan<TCurve, OppCurve>::validatePerpT(double oppT) const { 842 const SkTSpanBounded<OppCurve, TCurve>* testBounded = fBounded; 843 while (testBounded) { 844 const SkTSpan<OppCurve, TCurve>* overlap = testBounded->fBounded; 845 if (precisely_between(overlap->fStartT, oppT, overlap->fEndT)) { 846 return; 847 } 848 testBounded = testBounded->fNext; 849 } 850 SkASSERT(0); 851 } 852 853 template<typename TCurve, typename OppCurve> 854 void SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) const { 855 SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt); 856 } 857 858 859 template<typename TCurve, typename OppCurve> 860 SkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c 861 SkDEBUGPARAMS(SkOpGlobalState* debugGlobalState) 862 PATH_OPS_DEBUG_T_SECT_PARAMS(int id)) 863 : fCurve(c) 864 , fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4) 865 , fCoincident(nullptr) 866 , fDeleted(nullptr) 867 , fActiveCount(0) 868 SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState)) 869 PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id)) 870 PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0)) 871 PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0)) 872 { 873 this->resetRemovedEnds(); 874 fHead = this->addOne(); 875 SkDEBUGCODE(fHead->debugSetGlobalState(debugGlobalState)); 876 fHead->init(c); 877 } 878 879 template<typename TCurve, typename OppCurve> 880 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() { 881 SkTSpan<TCurve, OppCurve>* result; 882 if (fDeleted) { 883 result = fDeleted; 884 fDeleted = result->fNext; 885 } else { 886 result = fHeap.make<SkTSpan<TCurve, OppCurve>>(); 887 #if DEBUG_T_SECT 888 ++fDebugAllocatedCount; 889 #endif 890 } 891 result->reset(); 892 result->fHasPerp = false; 893 result->fDeleted = false; 894 ++fActiveCount; 895 PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID); 896 SkDEBUGCODE(result->fDebugSect = this); 897 #ifdef SK_DEBUG 898 result->fPart.debugInit(); 899 result->fCoinStart.debugInit(); 900 result->fCoinEnd.debugInit(); 901 result->fPrev = result->fNext = nullptr; 902 result->fBounds.debugInit(); 903 result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN; 904 result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF; 905 #endif 906 return result; 907 } 908 909 template<typename TCurve, typename OppCurve> 910 bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect2, double tStart, 911 double tStep, double* resultT, double* oppT) { 912 SkTSpan<TCurve, OppCurve> work; 913 double result = work.fStartT = work.fEndT = tStart; 914 SkDEBUGCODE(work.fDebugSect = this); 915 SkDPoint last = fCurve.ptAtT(tStart); 916 SkDPoint oppPt; 917 bool flip = false; 918 bool contained = false; 919 SkDEBUGCODE(bool down = tStep < 0); 920 const OppCurve& opp = sect2->fCurve; 921 do { 922 tStep *= 0.5; 923 work.fStartT += tStep; 924 if (flip) { 925 tStep = -tStep; 926 flip = false; 927 } 928 work.initBounds(fCurve); 929 if (work.fCollapsed) { 930 return false; 931 } 932 if (last.approximatelyEqual(work.fPart[0])) { 933 break; 934 } 935 last = work.fPart[0]; 936 work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp); 937 if (work.fCoinStart.isMatch()) { 938 #if DEBUG_T_SECT 939 work.validatePerpPt(work.fCoinStart.perpT(), work.fCoinStart.perpPt()); 940 #endif 941 double oppTTest = work.fCoinStart.perpT(); 942 if (sect2->fHead->contains(oppTTest)) { 943 *oppT = oppTTest; 944 oppPt = work.fCoinStart.perpPt(); 945 contained = true; 946 SkASSERT(down ? result > work.fStartT : result < work.fStartT); 947 result = work.fStartT; 948 continue; 949 } 950 } 951 tStep = -tStep; 952 flip = true; 953 } while (true); 954 if (!contained) { 955 return false; 956 } 957 if (last.approximatelyEqual(fCurve[0])) { 958 result = 0; 959 } else if (last.approximatelyEqual(fCurve[TCurve::kPointLast])) { 960 result = 1; 961 } 962 if (oppPt.approximatelyEqual(opp[0])) { 963 *oppT = 0; 964 } else if (oppPt.approximatelyEqual(opp[OppCurve::kPointLast])) { 965 *oppT = 1; 966 } 967 *resultT = result; 968 return true; 969 } 970 971 // OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span 972 // so that each quad sect has a pointer to the largest, and can update it as spans 973 // are split 974 template<typename TCurve, typename OppCurve> 975 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::boundsMax() const { 976 SkTSpan<TCurve, OppCurve>* test = fHead; 977 SkTSpan<TCurve, OppCurve>* largest = fHead; 978 bool lCollapsed = largest->fCollapsed; 979 while ((test = test->fNext)) { 980 bool tCollapsed = test->fCollapsed; 981 if ((lCollapsed && !tCollapsed) || (lCollapsed == tCollapsed && 982 largest->fBoundsMax < test->fBoundsMax)) { 983 largest = test; 984 lCollapsed = test->fCollapsed; 985 } 986 } 987 return largest; 988 } 989 990 template<typename TCurve, typename OppCurve> 991 bool SkTSect<TCurve, OppCurve>::coincidentCheck(SkTSect<OppCurve, TCurve>* sect2) { 992 SkTSpan<TCurve, OppCurve>* first = fHead; 993 if (!first) { 994 return false; 995 } 996 SkTSpan<TCurve, OppCurve>* last, * next; 997 do { 998 int consecutive = this->countConsecutiveSpans(first, &last); 999 next = last->fNext; 1000 if (consecutive < COINCIDENT_SPAN_COUNT) { 1001 continue; 1002 } 1003 this->validate(); 1004 sect2->validate(); 1005 this->computePerpendiculars(sect2, first, last); 1006 this->validate(); 1007 sect2->validate(); 1008 // check to see if a range of points are on the curve 1009 SkTSpan<TCurve, OppCurve>* coinStart = first; 1010 do { 1011 bool success = this->extractCoincident(sect2, coinStart, last, &coinStart); 1012 if (!success) { 1013 return false; 1014 } 1015 } while (coinStart && !last->fDeleted); 1016 if (!fHead || !sect2->fHead) { 1017 break; 1018 } 1019 if (!next || next->fDeleted) { 1020 break; 1021 } 1022 } while ((first = next)); 1023 return true; 1024 } 1025 1026 template<typename TCurve, typename OppCurve> 1027 void SkTSect<TCurve, OppCurve>::coincidentForce(SkTSect<OppCurve, TCurve>* sect2, 1028 double start1s, double start1e) { 1029 SkTSpan<TCurve, OppCurve>* first = fHead; 1030 SkTSpan<TCurve, OppCurve>* last = this->tail(); 1031 SkTSpan<OppCurve, TCurve>* oppFirst = sect2->fHead; 1032 SkTSpan<OppCurve, TCurve>* oppLast = sect2->tail(); 1033 bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); 1034 deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); 1035 this->removeSpanRange(first, last); 1036 sect2->removeSpanRange(oppFirst, oppLast); 1037 first->fStartT = start1s; 1038 first->fEndT = start1e; 1039 first->resetBounds(fCurve); 1040 first->fCoinStart.setPerp(fCurve, start1s, fCurve[0], sect2->fCurve); 1041 first->fCoinEnd.setPerp(fCurve, start1e, fCurve[TCurve::kPointLast], sect2->fCurve); 1042 bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT(); 1043 double oppStartT = first->fCoinStart.perpT() == -1 ? 0 : SkTMax(0., first->fCoinStart.perpT()); 1044 double oppEndT = first->fCoinEnd.perpT() == -1 ? 1 : SkTMin(1., first->fCoinEnd.perpT()); 1045 if (!oppMatched) { 1046 SkTSwap(oppStartT, oppEndT); 1047 } 1048 oppFirst->fStartT = oppStartT; 1049 oppFirst->fEndT = oppEndT; 1050 oppFirst->resetBounds(sect2->fCurve); 1051 this->removeCoincident(first, false); 1052 sect2->removeCoincident(oppFirst, true); 1053 if (deleteEmptySpans) { 1054 this->deleteEmptySpans(); 1055 sect2->deleteEmptySpans(); 1056 } 1057 } 1058 1059 template<typename TCurve, typename OppCurve> 1060 bool SkTSect<TCurve, OppCurve>::coincidentHasT(double t) { 1061 SkTSpan<TCurve, OppCurve>* test = fCoincident; 1062 while (test) { 1063 if (between(test->fStartT, t, test->fEndT)) { 1064 return true; 1065 } 1066 test = test->fNext; 1067 } 1068 return false; 1069 } 1070 1071 template<typename TCurve, typename OppCurve> 1072 int SkTSect<TCurve, OppCurve>::collapsed() const { 1073 int result = 0; 1074 const SkTSpan<TCurve, OppCurve>* test = fHead; 1075 while (test) { 1076 if (test->fCollapsed) { 1077 ++result; 1078 } 1079 test = test->next(); 1080 } 1081 return result; 1082 } 1083 1084 template<typename TCurve, typename OppCurve> 1085 void SkTSect<TCurve, OppCurve>::computePerpendiculars(SkTSect<OppCurve, TCurve>* sect2, 1086 SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last) { 1087 const OppCurve& opp = sect2->fCurve; 1088 SkTSpan<TCurve, OppCurve>* work = first; 1089 SkTSpan<TCurve, OppCurve>* prior = nullptr; 1090 do { 1091 if (!work->fHasPerp && !work->fCollapsed) { 1092 if (prior) { 1093 work->fCoinStart = prior->fCoinEnd; 1094 } else { 1095 work->fCoinStart.setPerp(fCurve, work->fStartT, work->fPart[0], opp); 1096 } 1097 if (work->fCoinStart.isMatch()) { 1098 double perpT = work->fCoinStart.perpT(); 1099 if (sect2->coincidentHasT(perpT)) { 1100 work->fCoinStart.init(); 1101 } else { 1102 sect2->addForPerp(work, perpT); 1103 } 1104 } 1105 work->fCoinEnd.setPerp(fCurve, work->fEndT, work->fPart[TCurve::kPointLast], opp); 1106 if (work->fCoinEnd.isMatch()) { 1107 double perpT = work->fCoinEnd.perpT(); 1108 if (sect2->coincidentHasT(perpT)) { 1109 work->fCoinEnd.init(); 1110 } else { 1111 sect2->addForPerp(work, perpT); 1112 } 1113 } 1114 work->fHasPerp = true; 1115 } 1116 if (work == last) { 1117 break; 1118 } 1119 prior = work; 1120 work = work->fNext; 1121 SkASSERT(work); 1122 } while (true); 1123 } 1124 1125 template<typename TCurve, typename OppCurve> 1126 int SkTSect<TCurve, OppCurve>::countConsecutiveSpans(SkTSpan<TCurve, OppCurve>* first, 1127 SkTSpan<TCurve, OppCurve>** lastPtr) const { 1128 int consecutive = 1; 1129 SkTSpan<TCurve, OppCurve>* last = first; 1130 do { 1131 SkTSpan<TCurve, OppCurve>* next = last->fNext; 1132 if (!next) { 1133 break; 1134 } 1135 if (next->fStartT > last->fEndT) { 1136 break; 1137 } 1138 ++consecutive; 1139 last = next; 1140 } while (true); 1141 *lastPtr = last; 1142 return consecutive; 1143 } 1144 1145 template<typename TCurve, typename OppCurve> 1146 bool SkTSect<TCurve, OppCurve>::debugHasBounded(const SkTSpan<OppCurve, TCurve>* span) const { 1147 const SkTSpan<TCurve, OppCurve>* test = fHead; 1148 if (!test) { 1149 return false; 1150 } 1151 do { 1152 if (test->findOppSpan(span)) { 1153 return true; 1154 } 1155 } while ((test = test->next())); 1156 return false; 1157 } 1158 1159 template<typename TCurve, typename OppCurve> 1160 bool SkTSect<TCurve, OppCurve>::deleteEmptySpans() { 1161 SkTSpan<TCurve, OppCurve>* test; 1162 SkTSpan<TCurve, OppCurve>* next = fHead; 1163 int safetyHatch = 1000; 1164 while ((test = next)) { 1165 next = test->fNext; 1166 if (!test->fBounded) { 1167 if (!this->removeSpan(test)) { 1168 return false; 1169 } 1170 } 1171 if (--safetyHatch < 0) { 1172 return false; 1173 } 1174 } 1175 return true; 1176 } 1177 1178 template<typename TCurve, typename OppCurve> 1179 bool SkTSect<TCurve, OppCurve>::extractCoincident( 1180 SkTSect<OppCurve, TCurve>* sect2, 1181 SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>* last, 1182 SkTSpan<TCurve, OppCurve>** result) { 1183 first = findCoincidentRun(first, &last); 1184 if (!first || !last) { 1185 *result = nullptr; 1186 return true; 1187 } 1188 // march outwards to find limit of coincidence from here to previous and next spans 1189 double startT = first->fStartT; 1190 double oppStartT SK_INIT_TO_AVOID_WARNING; 1191 double oppEndT SK_INIT_TO_AVOID_WARNING; 1192 SkTSpan<TCurve, OppCurve>* prev = first->fPrev; 1193 SkASSERT(first->fCoinStart.isMatch()); 1194 SkTSpan<OppCurve, TCurve>* oppFirst = first->findOppT(first->fCoinStart.perpT()); 1195 SkOPASSERT(last->fCoinEnd.isMatch()); 1196 bool oppMatched = first->fCoinStart.perpT() < first->fCoinEnd.perpT(); 1197 double coinStart; 1198 SkDEBUGCODE(double coinEnd); 1199 SkTSpan<OppCurve, TCurve>* cutFirst; 1200 if (prev && prev->fEndT == startT 1201 && this->binarySearchCoin(sect2, startT, prev->fStartT - startT, &coinStart, 1202 &oppStartT) 1203 && prev->fStartT < coinStart && coinStart < startT 1204 && (cutFirst = prev->oppT(oppStartT))) { 1205 oppFirst = cutFirst; 1206 first = this->addSplitAt(prev, coinStart); 1207 first->markCoincident(); 1208 prev->fCoinEnd.markCoincident(); 1209 if (oppFirst->fStartT < oppStartT && oppStartT < oppFirst->fEndT) { 1210 SkTSpan<OppCurve, TCurve>* oppHalf = sect2->addSplitAt(oppFirst, oppStartT); 1211 if (oppMatched) { 1212 oppFirst->fCoinEnd.markCoincident(); 1213 oppHalf->markCoincident(); 1214 oppFirst = oppHalf; 1215 } else { 1216 oppFirst->markCoincident(); 1217 oppHalf->fCoinStart.markCoincident(); 1218 } 1219 } 1220 } else { 1221 SkDEBUGCODE(coinStart = first->fStartT); 1222 FAIL_IF(!oppFirst); 1223 SkDEBUGCODE(oppStartT = oppMatched ? oppFirst->fStartT : oppFirst->fEndT); 1224 } 1225 // FIXME: incomplete : if we're not at the end, find end of coin 1226 SkTSpan<OppCurve, TCurve>* oppLast; 1227 SkOPASSERT(last->fCoinEnd.isMatch()); 1228 oppLast = last->findOppT(last->fCoinEnd.perpT()); 1229 SkDEBUGCODE(coinEnd = last->fEndT); 1230 #ifdef SK_DEBUG 1231 if (!this->globalState() || !this->globalState()->debugSkipAssert()) { 1232 oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT; 1233 } 1234 #endif 1235 if (!oppMatched) { 1236 SkTSwap(oppFirst, oppLast); 1237 SkTSwap(oppStartT, oppEndT); 1238 } 1239 SkOPASSERT(oppStartT < oppEndT); 1240 SkASSERT(coinStart == first->fStartT); 1241 SkASSERT(coinEnd == last->fEndT); 1242 SkOPASSERT(oppStartT == oppFirst->fStartT); 1243 SkOPASSERT(oppEndT == oppLast->fEndT); 1244 if (!oppFirst) { 1245 *result = nullptr; 1246 return true; 1247 } 1248 if (!oppLast) { 1249 *result = nullptr; 1250 return true; 1251 } 1252 // reduce coincident runs to single entries 1253 this->validate(); 1254 sect2->validate(); 1255 bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); 1256 deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); 1257 this->removeSpanRange(first, last); 1258 sect2->removeSpanRange(oppFirst, oppLast); 1259 first->fEndT = last->fEndT; 1260 first->resetBounds(this->fCurve); 1261 first->fCoinStart.setPerp(fCurve, first->fStartT, first->fPart[0], sect2->fCurve); 1262 first->fCoinEnd.setPerp(fCurve, first->fEndT, first->fPart[TCurve::kPointLast], sect2->fCurve); 1263 oppStartT = first->fCoinStart.perpT(); 1264 oppEndT = first->fCoinEnd.perpT(); 1265 if (between(0, oppStartT, 1) && between(0, oppEndT, 1)) { 1266 if (!oppMatched) { 1267 SkTSwap(oppStartT, oppEndT); 1268 } 1269 oppFirst->fStartT = oppStartT; 1270 oppFirst->fEndT = oppEndT; 1271 oppFirst->resetBounds(sect2->fCurve); 1272 } 1273 this->validateBounded(); 1274 sect2->validateBounded(); 1275 last = first->fNext; 1276 this->removeCoincident(first, false); 1277 sect2->removeCoincident(oppFirst, true); 1278 if (deleteEmptySpans) { 1279 if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) { 1280 *result = nullptr; 1281 return false; 1282 } 1283 } 1284 this->validate(); 1285 sect2->validate(); 1286 *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr; 1287 return true; 1288 } 1289 1290 template<typename TCurve, typename OppCurve> 1291 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::findCoincidentRun( 1292 SkTSpan<TCurve, OppCurve>* first, SkTSpan<TCurve, OppCurve>** lastPtr) { 1293 SkTSpan<TCurve, OppCurve>* work = first; 1294 SkTSpan<TCurve, OppCurve>* lastCandidate = nullptr; 1295 first = nullptr; 1296 // find the first fully coincident span 1297 do { 1298 if (work->fCoinStart.isMatch()) { 1299 #if DEBUG_T_SECT 1300 work->validatePerpT(work->fCoinStart.perpT()); 1301 work->validatePerpPt(work->fCoinStart.perpT(), work->fCoinStart.perpPt()); 1302 #endif 1303 SkOPASSERT(work->hasOppT(work->fCoinStart.perpT())); 1304 if (!work->fCoinEnd.isMatch()) { 1305 break; 1306 } 1307 lastCandidate = work; 1308 if (!first) { 1309 first = work; 1310 } 1311 } else if (first && work->fCollapsed) { 1312 *lastPtr = lastCandidate; 1313 return first; 1314 } else { 1315 lastCandidate = nullptr; 1316 SkOPASSERT(!first); 1317 } 1318 if (work == *lastPtr) { 1319 return first; 1320 } 1321 work = work->fNext; 1322 if (!work) { 1323 return nullptr; 1324 } 1325 } while (true); 1326 if (lastCandidate) { 1327 *lastPtr = lastCandidate; 1328 } 1329 return first; 1330 } 1331 1332 template<typename TCurve, typename OppCurve> 1333 int SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span, 1334 SkTSect<OppCurve, TCurve>* opp, 1335 SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult) { 1336 bool spanStart, oppStart; 1337 int hullResult = span->hullsIntersect(oppSpan, &spanStart, &oppStart); 1338 if (hullResult >= 0) { 1339 if (hullResult == 2) { // hulls have one point in common 1340 if (!span->fBounded || !span->fBounded->fNext) { 1341 SkASSERT(!span->fBounded || span->fBounded->fBounded == oppSpan); 1342 if (spanStart) { 1343 span->fEndT = span->fStartT; 1344 } else { 1345 span->fStartT = span->fEndT; 1346 } 1347 } else { 1348 hullResult = 1; 1349 } 1350 if (!oppSpan->fBounded || !oppSpan->fBounded->fNext) { 1351 SkASSERT(!oppSpan->fBounded || oppSpan->fBounded->fBounded == span); 1352 if (oppStart) { 1353 oppSpan->fEndT = oppSpan->fStartT; 1354 } else { 1355 oppSpan->fStartT = oppSpan->fEndT; 1356 } 1357 *oppResult = 2; 1358 } else { 1359 *oppResult = 1; 1360 } 1361 } else { 1362 *oppResult = 1; 1363 } 1364 return hullResult; 1365 } 1366 if (span->fIsLine && oppSpan->fIsLine) { 1367 SkIntersections i; 1368 int sects = this->linesIntersect(span, opp, oppSpan, &i); 1369 if (sects == 2) { 1370 return *oppResult = 1; 1371 } 1372 if (!sects) { 1373 return -1; 1374 } 1375 this->removedEndCheck(span); 1376 span->fStartT = span->fEndT = i[0][0]; 1377 opp->removedEndCheck(oppSpan); 1378 oppSpan->fStartT = oppSpan->fEndT = i[1][0]; 1379 return *oppResult = 2; 1380 } 1381 if (span->fIsLinear || oppSpan->fIsLinear) { 1382 return *oppResult = (int) span->linearsIntersect(oppSpan); 1383 } 1384 return *oppResult = 1; 1385 } 1386 1387 template<typename TCurve> 1388 static bool is_parallel(const SkDLine& thisLine, const TCurve& opp) { 1389 if (!opp.IsConic()) { 1390 return false; // FIXME : breaks a lot of stuff now 1391 } 1392 int finds = 0; 1393 SkDLine thisPerp; 1394 thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY); 1395 thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX); 1396 thisPerp.fPts[1] = thisLine.fPts[1]; 1397 SkIntersections perpRayI; 1398 perpRayI.intersectRay(opp, thisPerp); 1399 for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) { 1400 finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]); 1401 } 1402 thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.fPts[0].fY); 1403 thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.fPts[1].fX); 1404 thisPerp.fPts[0] = thisLine.fPts[0]; 1405 perpRayI.intersectRay(opp, thisPerp); 1406 for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) { 1407 finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]); 1408 } 1409 return finds >= 2; 1410 } 1411 1412 // while the intersection points are sufficiently far apart: 1413 // construct the tangent lines from the intersections 1414 // find the point where the tangent line intersects the opposite curve 1415 template<typename TCurve, typename OppCurve> 1416 int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span, 1417 SkTSect<OppCurve, TCurve>* opp, 1418 SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) { 1419 SkIntersections thisRayI SkDEBUGCODE((span->fDebugGlobalState)); 1420 SkIntersections oppRayI SkDEBUGCODE((span->fDebugGlobalState)); 1421 SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }}; 1422 SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast] }}; 1423 int loopCount = 0; 1424 double bestDistSq = DBL_MAX; 1425 if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { 1426 return 0; 1427 } 1428 if (!oppRayI.intersectRay(this->fCurve, oppLine)) { 1429 return 0; 1430 } 1431 // if the ends of each line intersect the opposite curve, the lines are coincident 1432 if (thisRayI.used() > 1) { 1433 int ptMatches = 0; 1434 for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) { 1435 for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) { 1436 ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPts[lIndex]); 1437 } 1438 } 1439 if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) { 1440 return 2; 1441 } 1442 } 1443 if (oppRayI.used() > 1) { 1444 int ptMatches = 0; 1445 for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) { 1446 for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); ++lIndex) { 1447 ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[lIndex]); 1448 } 1449 } 1450 if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) { 1451 return 2; 1452 } 1453 } 1454 do { 1455 // pick the closest pair of points 1456 double closest = DBL_MAX; 1457 int closeIndex SK_INIT_TO_AVOID_WARNING; 1458 int oppCloseIndex SK_INIT_TO_AVOID_WARNING; 1459 for (int index = 0; index < oppRayI.used(); ++index) { 1460 if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT)) { 1461 continue; 1462 } 1463 for (int oIndex = 0; oIndex < thisRayI.used(); ++oIndex) { 1464 if (!roughly_between(oppSpan->fStartT, thisRayI[0][oIndex], oppSpan->fEndT)) { 1465 continue; 1466 } 1467 double distSq = thisRayI.pt(index).distanceSquared(oppRayI.pt(oIndex)); 1468 if (closest > distSq) { 1469 closest = distSq; 1470 closeIndex = index; 1471 oppCloseIndex = oIndex; 1472 } 1473 } 1474 } 1475 if (closest == DBL_MAX) { 1476 break; 1477 } 1478 const SkDPoint& oppIPt = thisRayI.pt(oppCloseIndex); 1479 const SkDPoint& iPt = oppRayI.pt(closeIndex); 1480 if (between(span->fStartT, oppRayI[0][closeIndex], span->fEndT) 1481 && between(oppSpan->fStartT, thisRayI[0][oppCloseIndex], oppSpan->fEndT) 1482 && oppIPt.approximatelyEqual(iPt)) { 1483 i->merge(oppRayI, closeIndex, thisRayI, oppCloseIndex); 1484 return i->used(); 1485 } 1486 double distSq = oppIPt.distanceSquared(iPt); 1487 if (bestDistSq < distSq || ++loopCount > 5) { 1488 return 0; 1489 } 1490 bestDistSq = distSq; 1491 double oppStart = oppRayI[0][closeIndex]; 1492 thisLine[0] = fCurve.ptAtT(oppStart); 1493 thisLine[1] = thisLine[0] + fCurve.dxdyAtT(oppStart); 1494 if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { 1495 break; 1496 } 1497 double start = thisRayI[0][oppCloseIndex]; 1498 oppLine[0] = opp->fCurve.ptAtT(start); 1499 oppLine[1] = oppLine[0] + opp->fCurve.dxdyAtT(start); 1500 if (!oppRayI.intersectRay(this->fCurve, oppLine)) { 1501 break; 1502 } 1503 } while (true); 1504 // convergence may fail if the curves are nearly coincident 1505 SkTCoincident<OppCurve, TCurve> oCoinS, oCoinE; 1506 oCoinS.setPerp(opp->fCurve, oppSpan->fStartT, oppSpan->fPart[0], fCurve); 1507 oCoinE.setPerp(opp->fCurve, oppSpan->fEndT, oppSpan->fPart[OppCurve::kPointLast], fCurve); 1508 double tStart = oCoinS.perpT(); 1509 double tEnd = oCoinE.perpT(); 1510 bool swap = tStart > tEnd; 1511 if (swap) { 1512 SkTSwap(tStart, tEnd); 1513 } 1514 tStart = SkTMax(tStart, span->fStartT); 1515 tEnd = SkTMin(tEnd, span->fEndT); 1516 if (tStart > tEnd) { 1517 return 0; 1518 } 1519 SkDVector perpS, perpE; 1520 if (tStart == span->fStartT) { 1521 SkTCoincident<TCurve, OppCurve> coinS; 1522 coinS.setPerp(fCurve, span->fStartT, span->fPart[0], opp->fCurve); 1523 perpS = span->fPart[0] - coinS.perpPt(); 1524 } else if (swap) { 1525 perpS = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast]; 1526 } else { 1527 perpS = oCoinS.perpPt() - oppSpan->fPart[0]; 1528 } 1529 if (tEnd == span->fEndT) { 1530 SkTCoincident<TCurve, OppCurve> coinE; 1531 coinE.setPerp(fCurve, span->fEndT, span->fPart[TCurve::kPointLast], opp->fCurve); 1532 perpE = span->fPart[TCurve::kPointLast] - coinE.perpPt(); 1533 } else if (swap) { 1534 perpE = oCoinS.perpPt() - oppSpan->fPart[0]; 1535 } else { 1536 perpE = oCoinE.perpPt() - oppSpan->fPart[OppCurve::kPointLast]; 1537 } 1538 if (perpS.dot(perpE) >= 0) { 1539 return 0; 1540 } 1541 SkTCoincident<TCurve, OppCurve> coinW; 1542 double workT = tStart; 1543 double tStep = tEnd - tStart; 1544 SkDPoint workPt; 1545 do { 1546 tStep *= 0.5; 1547 if (precisely_zero(tStep)) { 1548 return 0; 1549 } 1550 workT += tStep; 1551 workPt = fCurve.ptAtT(workT); 1552 coinW.setPerp(fCurve, workT, workPt, opp->fCurve); 1553 double perpT = coinW.perpT(); 1554 if (coinW.isMatch() ? !between(oppSpan->fStartT, perpT, oppSpan->fEndT) : perpT < 0) { 1555 continue; 1556 } 1557 SkDVector perpW = workPt - coinW.perpPt(); 1558 if ((perpS.dot(perpW) >= 0) == (tStep < 0)) { 1559 tStep = -tStep; 1560 } 1561 if (workPt.approximatelyEqual(coinW.perpPt())) { 1562 break; 1563 } 1564 } while (true); 1565 double oppTTest = coinW.perpT(); 1566 if (!opp->fHead->contains(oppTTest)) { 1567 return 0; 1568 } 1569 i->setMax(1); 1570 i->insert(workT, oppTTest, workPt); 1571 return 1; 1572 } 1573 1574 1575 template<typename TCurve, typename OppCurve> 1576 bool SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) { 1577 if (--fActiveCount < 0) { 1578 return false; 1579 } 1580 span->fNext = fDeleted; 1581 fDeleted = span; 1582 SkOPASSERT(!span->fDeleted); 1583 span->fDeleted = true; 1584 return true; 1585 } 1586 1587 template<typename TCurve, typename OppCurve> 1588 bool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, 1589 double t2) const { 1590 SkDVector dxdy = this->fCurve.dxdyAtT(t); 1591 SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2); 1592 return dxdy.dot(dxdy2) >= 0; 1593 } 1594 1595 template<typename TCurve, typename OppCurve> 1596 void SkTSect<TCurve, OppCurve>::matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, 1597 double t2, bool* calcMatched, bool* oppMatched) const { 1598 if (*calcMatched) { 1599 SkASSERT(*oppMatched == this->matchedDirection(t, sect2, t2)); 1600 } else { 1601 *oppMatched = this->matchedDirection(t, sect2, t2); 1602 *calcMatched = true; 1603 } 1604 } 1605 1606 template<typename TCurve, typename OppCurve> 1607 void SkTSect<TCurve, OppCurve>::mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2) { 1608 double smallLimit = 0; 1609 do { 1610 // find the smallest unprocessed span 1611 SkTSpan<TCurve, OppCurve>* smaller = nullptr; 1612 SkTSpan<TCurve, OppCurve>* test = fCoincident; 1613 do { 1614 if (!test) { 1615 return; 1616 } 1617 if (test->fStartT < smallLimit) { 1618 continue; 1619 } 1620 if (smaller && smaller->fEndT < test->fStartT) { 1621 continue; 1622 } 1623 smaller = test; 1624 } while ((test = test->fNext)); 1625 if (!smaller) { 1626 return; 1627 } 1628 smallLimit = smaller->fEndT; 1629 // find next larger span 1630 SkTSpan<TCurve, OppCurve>* prior = nullptr; 1631 SkTSpan<TCurve, OppCurve>* larger = nullptr; 1632 SkTSpan<TCurve, OppCurve>* largerPrior = nullptr; 1633 test = fCoincident; 1634 do { 1635 if (test->fStartT < smaller->fEndT) { 1636 continue; 1637 } 1638 SkOPASSERT(test->fStartT != smaller->fEndT); 1639 if (larger && larger->fStartT < test->fStartT) { 1640 continue; 1641 } 1642 largerPrior = prior; 1643 larger = test; 1644 } while ((prior = test), (test = test->fNext)); 1645 if (!larger) { 1646 continue; 1647 } 1648 // check middle t value to see if it is coincident as well 1649 double midT = (smaller->fEndT + larger->fStartT) / 2; 1650 SkDPoint midPt = fCurve.ptAtT(midT); 1651 SkTCoincident<TCurve, OppCurve> coin; 1652 coin.setPerp(fCurve, midT, midPt, sect2->fCurve); 1653 if (coin.isMatch()) { 1654 smaller->fEndT = larger->fEndT; 1655 smaller->fCoinEnd = larger->fCoinEnd; 1656 if (largerPrior) { 1657 largerPrior->fNext = larger->fNext; 1658 largerPrior->validate(); 1659 } else { 1660 fCoincident = larger->fNext; 1661 } 1662 } 1663 } while (true); 1664 } 1665 1666 template<typename TCurve, typename OppCurve> 1667 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::prev( 1668 SkTSpan<TCurve, OppCurve>* span) const { 1669 SkTSpan<TCurve, OppCurve>* result = nullptr; 1670 SkTSpan<TCurve, OppCurve>* test = fHead; 1671 while (span != test) { 1672 result = test; 1673 test = test->fNext; 1674 SkASSERT(test); 1675 } 1676 return result; 1677 } 1678 1679 template<typename TCurve, typename OppCurve> 1680 void SkTSect<TCurve, OppCurve>::recoverCollapsed() { 1681 SkTSpan<TCurve, OppCurve>* deleted = fDeleted; 1682 while (deleted) { 1683 SkTSpan<TCurve, OppCurve>* delNext = deleted->fNext; 1684 if (deleted->fCollapsed) { 1685 SkTSpan<TCurve, OppCurve>** spanPtr = &fHead; 1686 while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) { 1687 spanPtr = &(*spanPtr)->fNext; 1688 } 1689 deleted->fNext = *spanPtr; 1690 *spanPtr = deleted; 1691 } 1692 deleted = delNext; 1693 } 1694 } 1695 1696 template<typename TCurve, typename OppCurve> 1697 void SkTSect<TCurve, OppCurve>::removeAllBut(const SkTSpan<OppCurve, TCurve>* keep, 1698 SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* opp) { 1699 const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded; 1700 while (testBounded) { 1701 SkTSpan<OppCurve, TCurve>* bounded = testBounded->fBounded; 1702 const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext; 1703 // may have been deleted when opp did 'remove all but' 1704 if (bounded != keep && !bounded->fDeleted) { 1705 SkAssertResult(SkDEBUGCODE(!) span->removeBounded(bounded)); 1706 if (bounded->removeBounded(span)) { 1707 opp->removeSpan(bounded); 1708 } 1709 } 1710 testBounded = next; 1711 } 1712 SkASSERT(!span->fDeleted); 1713 SkASSERT(span->findOppSpan(keep)); 1714 SkASSERT(keep->findOppSpan(span)); 1715 } 1716 1717 template<typename TCurve, typename OppCurve> 1718 void SkTSect<TCurve, OppCurve>::removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp) { 1719 SkTSpan<TCurve, OppCurve>* test = fHead; 1720 SkTSpan<TCurve, OppCurve>* next; 1721 do { 1722 next = test->fNext; 1723 if (test->fCoinStart.perpT() < 0 || test->fCoinEnd.perpT() < 0) { 1724 continue; 1725 } 1726 SkDVector startV = test->fCoinStart.perpPt() - test->fPart[0]; 1727 SkDVector endV = test->fCoinEnd.perpPt() - test->fPart[TCurve::kPointLast]; 1728 #if DEBUG_T_SECT 1729 SkDebugf("%s startV=(%1.9g,%1.9g) endV=(%1.9g,%1.9g) dot=%1.9g\n", __FUNCTION__, 1730 startV.fX, startV.fY, endV.fX, endV.fY, startV.dot(endV)); 1731 #endif 1732 if (startV.dot(endV) <= 0) { 1733 continue; 1734 } 1735 this->removeSpans(test, opp); 1736 } while ((test = next)); 1737 } 1738 1739 template<typename TCurve, typename OppCurve> 1740 void SkTSect<TCurve, OppCurve>::removeCoincident(SkTSpan<TCurve, OppCurve>* span, bool isBetween) { 1741 this->unlinkSpan(span); 1742 if (isBetween || between(0, span->fCoinStart.perpT(), 1)) { 1743 --fActiveCount; 1744 span->fNext = fCoincident; 1745 fCoincident = span; 1746 } else { 1747 this->markSpanGone(span); 1748 } 1749 } 1750 1751 template<typename TCurve, typename OppCurve> 1752 void SkTSect<TCurve, OppCurve>::removedEndCheck(SkTSpan<TCurve, OppCurve>* span) { 1753 if (!span->fStartT) { 1754 fRemovedStartT = true; 1755 } 1756 if (1 == span->fEndT) { 1757 fRemovedEndT = true; 1758 } 1759 } 1760 1761 template<typename TCurve, typename OppCurve> 1762 bool SkTSect<TCurve, OppCurve>::removeSpan(SkTSpan<TCurve, OppCurve>* span) {\ 1763 this->removedEndCheck(span); 1764 this->unlinkSpan(span); 1765 return this->markSpanGone(span); 1766 } 1767 1768 template<typename TCurve, typename OppCurve> 1769 void SkTSect<TCurve, OppCurve>::removeSpanRange(SkTSpan<TCurve, OppCurve>* first, 1770 SkTSpan<TCurve, OppCurve>* last) { 1771 if (first == last) { 1772 return; 1773 } 1774 SkTSpan<TCurve, OppCurve>* span = first; 1775 SkASSERT(span); 1776 SkTSpan<TCurve, OppCurve>* final = last->fNext; 1777 SkTSpan<TCurve, OppCurve>* next = span->fNext; 1778 while ((span = next) && span != final) { 1779 next = span->fNext; 1780 this->markSpanGone(span); 1781 } 1782 if (final) { 1783 final->fPrev = first; 1784 } 1785 first->fNext = final; 1786 first->validate(); 1787 } 1788 1789 template<typename TCurve, typename OppCurve> 1790 void SkTSect<TCurve, OppCurve>::removeSpans(SkTSpan<TCurve, OppCurve>* span, 1791 SkTSect<OppCurve, TCurve>* opp) { 1792 SkTSpanBounded<OppCurve, TCurve>* bounded = span->fBounded; 1793 while (bounded) { 1794 SkTSpan<OppCurve, TCurve>* spanBounded = bounded->fBounded; 1795 SkTSpanBounded<OppCurve, TCurve>* next = bounded->fNext; 1796 if (span->removeBounded(spanBounded)) { // shuffles last into position 0 1797 this->removeSpan(span); 1798 } 1799 if (spanBounded->removeBounded(span)) { 1800 opp->removeSpan(spanBounded); 1801 } 1802 SkASSERT(!span->fDeleted || !opp->debugHasBounded(span)); 1803 bounded = next; 1804 } 1805 } 1806 1807 template<typename TCurve, typename OppCurve> 1808 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::spanAtT(double t, 1809 SkTSpan<TCurve, OppCurve>** priorSpan) { 1810 SkTSpan<TCurve, OppCurve>* test = fHead; 1811 SkTSpan<TCurve, OppCurve>* prev = nullptr; 1812 while (test && test->fEndT < t) { 1813 prev = test; 1814 test = test->fNext; 1815 } 1816 *priorSpan = prev; 1817 return test && test->fStartT <= t ? test : nullptr; 1818 } 1819 1820 template<typename TCurve, typename OppCurve> 1821 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::tail() { 1822 SkTSpan<TCurve, OppCurve>* result = fHead; 1823 SkTSpan<TCurve, OppCurve>* next = fHead; 1824 while ((next = next->fNext)) { 1825 if (next->fEndT > result->fEndT) { 1826 result = next; 1827 } 1828 } 1829 return result; 1830 } 1831 1832 /* Each span has a range of opposite spans it intersects. After the span is split in two, 1833 adjust the range to its new size */ 1834 template<typename TCurve, typename OppCurve> 1835 bool SkTSect<TCurve, OppCurve>::trim(SkTSpan<TCurve, OppCurve>* span, 1836 SkTSect<OppCurve, TCurve>* opp) { 1837 FAIL_IF(!span->initBounds(fCurve)); 1838 const SkTSpanBounded<OppCurve, TCurve>* testBounded = span->fBounded; 1839 while (testBounded) { 1840 SkTSpan<OppCurve, TCurve>* test = testBounded->fBounded; 1841 const SkTSpanBounded<OppCurve, TCurve>* next = testBounded->fNext; 1842 int oppSects, sects = this->intersects(span, opp, test, &oppSects); 1843 if (sects >= 1) { 1844 if (oppSects == 2) { 1845 test->initBounds(opp->fCurve); 1846 opp->removeAllBut(span, test, this); 1847 } 1848 if (sects == 2) { 1849 span->initBounds(fCurve); 1850 this->removeAllBut(test, span, opp); 1851 return true; 1852 } 1853 } else { 1854 if (span->removeBounded(test)) { 1855 this->removeSpan(span); 1856 } 1857 if (test->removeBounded(span)) { 1858 opp->removeSpan(test); 1859 } 1860 } 1861 testBounded = next; 1862 } 1863 return true; 1864 } 1865 1866 template<typename TCurve, typename OppCurve> 1867 void SkTSect<TCurve, OppCurve>::unlinkSpan(SkTSpan<TCurve, OppCurve>* span) { 1868 SkTSpan<TCurve, OppCurve>* prev = span->fPrev; 1869 SkTSpan<TCurve, OppCurve>* next = span->fNext; 1870 if (prev) { 1871 prev->fNext = next; 1872 if (next) { 1873 next->fPrev = prev; 1874 next->validate(); 1875 } 1876 } else { 1877 fHead = next; 1878 if (next) { 1879 next->fPrev = nullptr; 1880 } 1881 } 1882 } 1883 1884 template<typename TCurve, typename OppCurve> 1885 bool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first, 1886 SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) { 1887 SkTSpan<TCurve, OppCurve>* test = first; 1888 const SkTSpan<TCurve, OppCurve>* final = last->next(); 1889 bool deleteSpan = false; 1890 do { 1891 deleteSpan |= test->removeAllBounded(); 1892 } while ((test = test->fNext) != final && test); 1893 first->fBounded = nullptr; 1894 first->addBounded(oppFirst, &fHeap); 1895 // cannot call validate until remove span range is called 1896 return deleteSpan; 1897 } 1898 1899 1900 template<typename TCurve, typename OppCurve> 1901 void SkTSect<TCurve, OppCurve>::validate() const { 1902 #if DEBUG_VALIDATE 1903 int count = 0; 1904 double last = 0; 1905 if (fHead) { 1906 const SkTSpan<TCurve, OppCurve>* span = fHead; 1907 SkASSERT(!span->fPrev); 1908 const SkTSpan<TCurve, OppCurve>* next; 1909 do { 1910 span->validate(); 1911 SkASSERT(span->fStartT >= last); 1912 last = span->fEndT; 1913 ++count; 1914 next = span->fNext; 1915 SkASSERT(next != span); 1916 } while ((span = next) != nullptr); 1917 } 1918 SkASSERT(count == fActiveCount); 1919 #endif 1920 #if DEBUG_T_SECT 1921 SkASSERT(fActiveCount <= fDebugAllocatedCount); 1922 int deletedCount = 0; 1923 const SkTSpan<TCurve, OppCurve>* deleted = fDeleted; 1924 while (deleted) { 1925 ++deletedCount; 1926 deleted = deleted->fNext; 1927 } 1928 const SkTSpan<TCurve, OppCurve>* coincident = fCoincident; 1929 while (coincident) { 1930 ++deletedCount; 1931 coincident = coincident->fNext; 1932 } 1933 SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount); 1934 #endif 1935 } 1936 1937 template<typename TCurve, typename OppCurve> 1938 void SkTSect<TCurve, OppCurve>::validateBounded() const { 1939 #if DEBUG_VALIDATE 1940 if (!fHead) { 1941 return; 1942 } 1943 const SkTSpan<TCurve, OppCurve>* span = fHead; 1944 do { 1945 span->validateBounded(); 1946 } while ((span = span->fNext) != nullptr); 1947 #endif 1948 } 1949 1950 template<typename TCurve, typename OppCurve> 1951 int SkTSect<TCurve, OppCurve>::EndsEqual(const SkTSect<TCurve, OppCurve>* sect1, 1952 const SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) { 1953 int zeroOneSet = 0; 1954 if (sect1->fCurve[0] == sect2->fCurve[0]) { 1955 zeroOneSet |= kZeroS1Set | kZeroS2Set; 1956 intersections->insert(0, 0, sect1->fCurve[0]); 1957 } 1958 if (sect1->fCurve[0] == sect2->fCurve[OppCurve::kPointLast]) { 1959 zeroOneSet |= kZeroS1Set | kOneS2Set; 1960 intersections->insert(0, 1, sect1->fCurve[0]); 1961 } 1962 if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[0]) { 1963 zeroOneSet |= kOneS1Set | kZeroS2Set; 1964 intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]); 1965 } 1966 if (sect1->fCurve[TCurve::kPointLast] == sect2->fCurve[OppCurve::kPointLast]) { 1967 zeroOneSet |= kOneS1Set | kOneS2Set; 1968 intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]); 1969 } 1970 // check for zero 1971 if (!(zeroOneSet & (kZeroS1Set | kZeroS2Set)) 1972 && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) { 1973 zeroOneSet |= kZeroS1Set | kZeroS2Set; 1974 intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]); 1975 } 1976 if (!(zeroOneSet & (kZeroS1Set | kOneS2Set)) 1977 && sect1->fCurve[0].approximatelyEqual(sect2->fCurve[OppCurve::kPointLast])) { 1978 zeroOneSet |= kZeroS1Set | kOneS2Set; 1979 intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[OppCurve::kPointLast]); 1980 } 1981 // check for one 1982 if (!(zeroOneSet & (kOneS1Set | kZeroS2Set)) 1983 && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[0])) { 1984 zeroOneSet |= kOneS1Set | kZeroS2Set; 1985 intersections->insertNear(1, 0, sect1->fCurve[TCurve::kPointLast], sect2->fCurve[0]); 1986 } 1987 if (!(zeroOneSet & (kOneS1Set | kOneS2Set)) 1988 && sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[ 1989 OppCurve::kPointLast])) { 1990 zeroOneSet |= kOneS1Set | kOneS2Set; 1991 intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast], 1992 sect2->fCurve[OppCurve::kPointLast]); 1993 } 1994 return zeroOneSet; 1995 } 1996 1997 template<typename TCurve, typename OppCurve> 1998 struct SkClosestRecord { 1999 bool operator<(const SkClosestRecord& rh) const { 2000 return fClosest < rh.fClosest; 2001 } 2002 2003 void addIntersection(SkIntersections* intersections) const { 2004 double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT(); 2005 double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT(); 2006 intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]); 2007 } 2008 2009 void findEnd(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2, 2010 int c1Index, int c2Index) { 2011 const TCurve& c1 = span1->part(); 2012 const OppCurve& c2 = span2->part(); 2013 if (!c1[c1Index].approximatelyEqual(c2[c2Index])) { 2014 return; 2015 } 2016 double dist = c1[c1Index].distanceSquared(c2[c2Index]); 2017 if (fClosest < dist) { 2018 return; 2019 } 2020 fC1Span = span1; 2021 fC2Span = span2; 2022 fC1StartT = span1->startT(); 2023 fC1EndT = span1->endT(); 2024 fC2StartT = span2->startT(); 2025 fC2EndT = span2->endT(); 2026 fC1Index = c1Index; 2027 fC2Index = c2Index; 2028 fClosest = dist; 2029 } 2030 2031 bool matesWith(const SkClosestRecord& mate SkDEBUGPARAMS(SkIntersections* i)) const { 2032 SkOPOBJASSERT(i, fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT() 2033 || mate.fC1Span->endT() <= fC1Span->startT()); 2034 SkOPOBJASSERT(i, fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT() 2035 || mate.fC2Span->endT() <= fC2Span->startT()); 2036 return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT() 2037 || fC1Span->startT() == mate.fC1Span->endT() 2038 || fC2Span == mate.fC2Span 2039 || fC2Span->endT() == mate.fC2Span->startT() 2040 || fC2Span->startT() == mate.fC2Span->endT(); 2041 } 2042 2043 void merge(const SkClosestRecord& mate) { 2044 fC1Span = mate.fC1Span; 2045 fC2Span = mate.fC2Span; 2046 fClosest = mate.fClosest; 2047 fC1Index = mate.fC1Index; 2048 fC2Index = mate.fC2Index; 2049 } 2050 2051 void reset() { 2052 fClosest = FLT_MAX; 2053 SkDEBUGCODE(fC1Span = nullptr); 2054 SkDEBUGCODE(fC2Span = nullptr); 2055 SkDEBUGCODE(fC1Index = fC2Index = -1); 2056 } 2057 2058 void update(const SkClosestRecord& mate) { 2059 fC1StartT = SkTMin(fC1StartT, mate.fC1StartT); 2060 fC1EndT = SkTMax(fC1EndT, mate.fC1EndT); 2061 fC2StartT = SkTMin(fC2StartT, mate.fC2StartT); 2062 fC2EndT = SkTMax(fC2EndT, mate.fC2EndT); 2063 } 2064 2065 const SkTSpan<TCurve, OppCurve>* fC1Span; 2066 const SkTSpan<OppCurve, TCurve>* fC2Span; 2067 double fC1StartT; 2068 double fC1EndT; 2069 double fC2StartT; 2070 double fC2EndT; 2071 double fClosest; 2072 int fC1Index; 2073 int fC2Index; 2074 }; 2075 2076 template<typename TCurve, typename OppCurve> 2077 struct SkClosestSect { 2078 SkClosestSect() 2079 : fUsed(0) { 2080 fClosest.push_back().reset(); 2081 } 2082 2083 bool find(const SkTSpan<TCurve, OppCurve>* span1, const SkTSpan<OppCurve, TCurve>* span2 2084 SkDEBUGPARAMS(SkIntersections* i)) { 2085 SkClosestRecord<TCurve, OppCurve>* record = &fClosest[fUsed]; 2086 record->findEnd(span1, span2, 0, 0); 2087 record->findEnd(span1, span2, 0, OppCurve::kPointLast); 2088 record->findEnd(span1, span2, TCurve::kPointLast, 0); 2089 record->findEnd(span1, span2, TCurve::kPointLast, OppCurve::kPointLast); 2090 if (record->fClosest == FLT_MAX) { 2091 return false; 2092 } 2093 for (int index = 0; index < fUsed; ++index) { 2094 SkClosestRecord<TCurve, OppCurve>* test = &fClosest[index]; 2095 if (test->matesWith(*record SkDEBUGPARAMS(i))) { 2096 if (test->fClosest > record->fClosest) { 2097 test->merge(*record); 2098 } 2099 test->update(*record); 2100 record->reset(); 2101 return false; 2102 } 2103 } 2104 ++fUsed; 2105 fClosest.push_back().reset(); 2106 return true; 2107 } 2108 2109 void finish(SkIntersections* intersections) const { 2110 SkSTArray<TCurve::kMaxIntersections * 3, 2111 const SkClosestRecord<TCurve, OppCurve>*, true> closestPtrs; 2112 for (int index = 0; index < fUsed; ++index) { 2113 closestPtrs.push_back(&fClosest[index]); 2114 } 2115 SkTQSort<const SkClosestRecord<TCurve, OppCurve> >(closestPtrs.begin(), closestPtrs.end() 2116 - 1); 2117 for (int index = 0; index < fUsed; ++index) { 2118 const SkClosestRecord<TCurve, OppCurve>* test = closestPtrs[index]; 2119 test->addIntersection(intersections); 2120 } 2121 } 2122 2123 // this is oversized so that an extra records can merge into final one 2124 SkSTArray<TCurve::kMaxIntersections * 2, SkClosestRecord<TCurve, OppCurve>, true> fClosest; 2125 int fUsed; 2126 }; 2127 2128 // returns true if the rect is too small to consider 2129 template<typename TCurve, typename OppCurve> 2130 void SkTSect<TCurve, OppCurve>::BinarySearch(SkTSect<TCurve, OppCurve>* sect1, 2131 SkTSect<OppCurve, TCurve>* sect2, SkIntersections* intersections) { 2132 #if DEBUG_T_SECT_DUMP > 1 2133 gDumpTSectNum = 0; 2134 #endif 2135 SkDEBUGCODE(sect1->fOppSect = sect2); 2136 SkDEBUGCODE(sect2->fOppSect = sect1); 2137 intersections->reset(); 2138 intersections->setMax(TCurve::kMaxIntersections + 4); // give extra for slop 2139 SkTSpan<TCurve, OppCurve>* span1 = sect1->fHead; 2140 SkTSpan<OppCurve, TCurve>* span2 = sect2->fHead; 2141 int oppSect, sect = sect1->intersects(span1, sect2, span2, &oppSect); 2142 // SkASSERT(between(0, sect, 2)); 2143 if (!sect) { 2144 return; 2145 } 2146 if (sect == 2 && oppSect == 2) { 2147 (void) EndsEqual(sect1, sect2, intersections); 2148 return; 2149 } 2150 span1->addBounded(span2, §1->fHeap); 2151 span2->addBounded(span1, §2->fHeap); 2152 const int kMaxCoinLoopCount = 8; 2153 int coinLoopCount = kMaxCoinLoopCount; 2154 double start1s SK_INIT_TO_AVOID_WARNING; 2155 double start1e SK_INIT_TO_AVOID_WARNING; 2156 do { 2157 // find the largest bounds 2158 SkTSpan<TCurve, OppCurve>* largest1 = sect1->boundsMax(); 2159 if (!largest1) { 2160 break; 2161 } 2162 SkTSpan<OppCurve, TCurve>* largest2 = sect2->boundsMax(); 2163 // split it 2164 if (!largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax 2165 || (!largest1->fCollapsed && largest2->fCollapsed)))) { 2166 if (largest1->fCollapsed) { 2167 break; 2168 } 2169 sect1->resetRemovedEnds(); 2170 sect2->resetRemovedEnds(); 2171 // trim parts that don't intersect the opposite 2172 SkTSpan<TCurve, OppCurve>* half1 = sect1->addOne(); 2173 SkDEBUGCODE(half1->debugSetGlobalState(sect1->globalState())); 2174 if (!half1->split(largest1, §1->fHeap)) { 2175 break; 2176 } 2177 if (!sect1->trim(largest1, sect2)) { 2178 SkOPOBJASSERT(intersections, 0); 2179 return; 2180 } 2181 if (!sect1->trim(half1, sect2)) { 2182 SkOPOBJASSERT(intersections, 0); 2183 return; 2184 } 2185 } else { 2186 if (largest2->fCollapsed) { 2187 break; 2188 } 2189 sect1->resetRemovedEnds(); 2190 sect2->resetRemovedEnds(); 2191 // trim parts that don't intersect the opposite 2192 SkTSpan<OppCurve, TCurve>* half2 = sect2->addOne(); 2193 SkDEBUGCODE(half2->debugSetGlobalState(sect2->globalState())); 2194 if (!half2->split(largest2, §2->fHeap)) { 2195 break; 2196 } 2197 if (!sect2->trim(largest2, sect1)) { 2198 SkOPOBJASSERT(intersections, 0); 2199 return; 2200 } 2201 if (!sect2->trim(half2, sect1)) { 2202 SkOPOBJASSERT(intersections, 0); 2203 return; 2204 } 2205 } 2206 sect1->validate(); 2207 sect2->validate(); 2208 #if DEBUG_T_SECT_LOOP_COUNT 2209 intersections->debugBumpLoopCount(SkIntersections::kIterations_DebugLoop); 2210 #endif 2211 // if there are 9 or more continuous spans on both sects, suspect coincidence 2212 if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT 2213 && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) { 2214 if (coinLoopCount == kMaxCoinLoopCount) { 2215 start1s = sect1->fHead->fStartT; 2216 start1e = sect1->tail()->fEndT; 2217 } 2218 if (!sect1->coincidentCheck(sect2)) { 2219 return; 2220 } 2221 sect1->validate(); 2222 sect2->validate(); 2223 #if DEBUG_T_SECT_LOOP_COUNT 2224 intersections->debugBumpLoopCount(SkIntersections::kCoinCheck_DebugLoop); 2225 #endif 2226 if (!--coinLoopCount && sect1->fHead && sect2->fHead) { 2227 /* All known working cases resolve in two tries. Sadly, cubicConicTests[0] 2228 gets stuck in a loop. It adds an extension to allow a coincident end 2229 perpendicular to track its intersection in the opposite curve. However, 2230 the bounding box of the extension does not intersect the original curve, 2231 so the extension is discarded, only to be added again the next time around. */ 2232 sect1->coincidentForce(sect2, start1s, start1e); 2233 sect1->validate(); 2234 sect2->validate(); 2235 } 2236 } 2237 if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT 2238 && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) { 2239 if (!sect1->fHead) { 2240 return; 2241 } 2242 sect1->computePerpendiculars(sect2, sect1->fHead, sect1->tail()); 2243 if (!sect2->fHead) { 2244 return; 2245 } 2246 sect2->computePerpendiculars(sect1, sect2->fHead, sect2->tail()); 2247 sect1->removeByPerpendicular(sect2); 2248 sect1->validate(); 2249 sect2->validate(); 2250 #if DEBUG_T_SECT_LOOP_COUNT 2251 intersections->debugBumpLoopCount(SkIntersections::kComputePerp_DebugLoop); 2252 #endif 2253 if (sect1->collapsed() > TCurve::kMaxIntersections) { 2254 break; 2255 } 2256 } 2257 #if DEBUG_T_SECT_DUMP 2258 sect1->dumpBoth(sect2); 2259 #endif 2260 if (!sect1->fHead || !sect2->fHead) { 2261 break; 2262 } 2263 } while (true); 2264 SkTSpan<TCurve, OppCurve>* coincident = sect1->fCoincident; 2265 if (coincident) { 2266 // if there is more than one coincident span, check loosely to see if they should be joined 2267 if (coincident->fNext) { 2268 sect1->mergeCoincidence(sect2); 2269 coincident = sect1->fCoincident; 2270 } 2271 SkASSERT(sect2->fCoincident); // courtesy check : coincidence only looks at sect 1 2272 do { 2273 if (!coincident) { 2274 return; 2275 } 2276 if (!coincident->fCoinStart.isMatch()) { 2277 continue; 2278 } 2279 if (!coincident->fCoinEnd.isMatch()) { 2280 continue; 2281 } 2282 double perpT = coincident->fCoinStart.perpT(); 2283 if (perpT < 0) { 2284 return; 2285 } 2286 int index = intersections->insertCoincident(coincident->fStartT, 2287 perpT, coincident->fPart[0]); 2288 if ((intersections->insertCoincident(coincident->fEndT, 2289 coincident->fCoinEnd.perpT(), 2290 coincident->fPart[TCurve::kPointLast]) < 0) && index >= 0) { 2291 intersections->clearCoincidence(index); 2292 } 2293 } while ((coincident = coincident->fNext)); 2294 } 2295 int zeroOneSet = EndsEqual(sect1, sect2, intersections); 2296 // if (!sect1->fHead || !sect2->fHead) { 2297 // if the final iteration contains an end (0 or 1), 2298 if (sect1->fRemovedStartT && !(zeroOneSet & kZeroS1Set)) { 2299 SkTCoincident<TCurve, OppCurve> perp; // intersect perpendicular with opposite curve 2300 perp.setPerp(sect1->fCurve, 0, sect1->fCurve[0], sect2->fCurve); 2301 if (perp.isMatch()) { 2302 intersections->insert(0, perp.perpT(), perp.perpPt()); 2303 } 2304 } 2305 if (sect1->fRemovedEndT && !(zeroOneSet & kOneS1Set)) { 2306 SkTCoincident<TCurve, OppCurve> perp; 2307 perp.setPerp(sect1->fCurve, 1, sect1->fCurve[TCurve::kPointLast], sect2->fCurve); 2308 if (perp.isMatch()) { 2309 intersections->insert(1, perp.perpT(), perp.perpPt()); 2310 } 2311 } 2312 if (sect2->fRemovedStartT && !(zeroOneSet & kZeroS2Set)) { 2313 SkTCoincident<OppCurve, TCurve> perp; 2314 perp.setPerp(sect2->fCurve, 0, sect2->fCurve[0], sect1->fCurve); 2315 if (perp.isMatch()) { 2316 intersections->insert(perp.perpT(), 0, perp.perpPt()); 2317 } 2318 } 2319 if (sect2->fRemovedEndT && !(zeroOneSet & kOneS2Set)) { 2320 SkTCoincident<OppCurve, TCurve> perp; 2321 perp.setPerp(sect2->fCurve, 1, sect2->fCurve[OppCurve::kPointLast], sect1->fCurve); 2322 if (perp.isMatch()) { 2323 intersections->insert(perp.perpT(), 1, perp.perpPt()); 2324 } 2325 } 2326 // } 2327 if (!sect1->fHead || !sect2->fHead) { 2328 return; 2329 } 2330 sect1->recoverCollapsed(); 2331 sect2->recoverCollapsed(); 2332 SkTSpan<TCurve, OppCurve>* result1 = sect1->fHead; 2333 // check heads and tails for zero and ones and insert them if we haven't already done so 2334 const SkTSpan<TCurve, OppCurve>* head1 = result1; 2335 if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) { 2336 const SkDPoint& start1 = sect1->fCurve[0]; 2337 if (head1->isBounded()) { 2338 double t = head1->closestBoundedT(start1); 2339 if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) { 2340 intersections->insert(0, t, start1); 2341 } 2342 } 2343 } 2344 const SkTSpan<OppCurve, TCurve>* head2 = sect2->fHead; 2345 if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) { 2346 const SkDPoint& start2 = sect2->fCurve[0]; 2347 if (head2->isBounded()) { 2348 double t = head2->closestBoundedT(start2); 2349 if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) { 2350 intersections->insert(t, 0, start2); 2351 } 2352 } 2353 } 2354 const SkTSpan<TCurve, OppCurve>* tail1 = sect1->tail(); 2355 if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) { 2356 const SkDPoint& end1 = sect1->fCurve[TCurve::kPointLast]; 2357 if (tail1->isBounded()) { 2358 double t = tail1->closestBoundedT(end1); 2359 if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) { 2360 intersections->insert(1, t, end1); 2361 } 2362 } 2363 } 2364 const SkTSpan<OppCurve, TCurve>* tail2 = sect2->tail(); 2365 if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) { 2366 const SkDPoint& end2 = sect2->fCurve[OppCurve::kPointLast]; 2367 if (tail2->isBounded()) { 2368 double t = tail2->closestBoundedT(end2); 2369 if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) { 2370 intersections->insert(t, 1, end2); 2371 } 2372 } 2373 } 2374 SkClosestSect<TCurve, OppCurve> closest; 2375 do { 2376 while (result1 && result1->fCoinStart.isMatch() && result1->fCoinEnd.isMatch()) { 2377 result1 = result1->fNext; 2378 } 2379 if (!result1) { 2380 break; 2381 } 2382 SkTSpan<OppCurve, TCurve>* result2 = sect2->fHead; 2383 bool found = false; 2384 while (result2) { 2385 found |= closest.find(result1, result2 SkDEBUGPARAMS(intersections)); 2386 result2 = result2->fNext; 2387 } 2388 } while ((result1 = result1->fNext)); 2389 closest.finish(intersections); 2390 // if there is more than one intersection and it isn't already coincident, check 2391 int last = intersections->used() - 1; 2392 for (int index = 0; index < last; ) { 2393 if (intersections->isCoincident(index) && intersections->isCoincident(index + 1)) { 2394 ++index; 2395 continue; 2396 } 2397 double midT = ((*intersections)[0][index] + (*intersections)[0][index + 1]) / 2; 2398 SkDPoint midPt = sect1->fCurve.ptAtT(midT); 2399 // intersect perpendicular with opposite curve 2400 SkTCoincident<TCurve, OppCurve> perp; 2401 perp.setPerp(sect1->fCurve, midT, midPt, sect2->fCurve); 2402 if (!perp.isMatch()) { 2403 ++index; 2404 continue; 2405 } 2406 if (intersections->isCoincident(index)) { 2407 intersections->removeOne(index); 2408 --last; 2409 } else if (intersections->isCoincident(index + 1)) { 2410 intersections->removeOne(index + 1); 2411 --last; 2412 } else { 2413 intersections->setCoincident(index++); 2414 } 2415 intersections->setCoincident(index); 2416 } 2417 SkOPOBJASSERT(intersections, intersections->used() <= TCurve::kMaxIntersections); 2418 } 2419 2420 #endif 2421
