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