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