| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2015 Google Inc. | 2 * Copyright 2015 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 #include "SkOpCoincidence.h" | 7 #include "SkOpCoincidence.h" |
| 8 #include "SkOpSegment.h" | 8 #include "SkOpSegment.h" |
| 9 #include "SkPathOpsTSect.h" | 9 #include "SkPathOpsTSect.h" |
| 10 | 10 |
| 11 #if DEBUG_COINCIDENCE | |
| 12 #define FAIL_IF(cond) SkASSERT(!(cond)) | |
| 13 #else | |
| 14 #define FAIL_IF(cond) do { if (cond) return false; } while (false) | |
| 15 #endif | |
| 16 | |
| 17 // returns true if coincident span's start and end are the same | 11 // returns true if coincident span's start and end are the same |
| 18 bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const { | 12 bool SkCoincidentSpans::collapsed(const SkOpPtT* test) const { |
| 19 return (fCoinPtTStart == test && fCoinPtTEnd->contains(test)) | 13 return (fCoinPtTStart == test && fCoinPtTEnd->contains(test)) |
| 20 || (fCoinPtTEnd == test && fCoinPtTStart->contains(test)) | 14 || (fCoinPtTEnd == test && fCoinPtTStart->contains(test)) |
| 21 || (fOppPtTStart == test && fOppPtTEnd->contains(test)) | 15 || (fOppPtTStart == test && fOppPtTEnd->contains(test)) |
| 22 || (fOppPtTEnd == test && fOppPtTStart->contains(test)); | 16 || (fOppPtTEnd == test && fOppPtTStart->contains(test)); |
| 23 } | 17 } |
| 24 | 18 |
| 25 // sets the span's end to the ptT referenced by the previous-next | 19 // sets the span's end to the ptT referenced by the previous-next |
| 26 void SkCoincidentSpans::correctOneEnd( | 20 void SkCoincidentSpans::correctOneEnd( |
| (...skipping 296 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 323 SkTSwap(coinSeg, oppSeg); | 317 SkTSwap(coinSeg, oppSeg); |
| 324 coinTs = oppStart->fT; | 318 coinTs = oppStart->fT; |
| 325 coinTe = testPtT->fT; | 319 coinTe = testPtT->fT; |
| 326 oppTs = base->t(); | 320 oppTs = base->t(); |
| 327 oppTe = testSpan->t(); | 321 oppTe = testSpan->t(); |
| 328 } | 322 } |
| 329 if (coinTs > coinTe) { | 323 if (coinTs > coinTe) { |
| 330 SkTSwap(coinTs, coinTe); | 324 SkTSwap(coinTs, coinTe); |
| 331 SkTSwap(oppTs, oppTe); | 325 SkTSwap(oppTs, oppTe); |
| 332 } | 326 } |
| 333 if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppT
e)) { | 327 if (!this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppT
e |
| 328 SkDEBUGPARAMS(true) /* do assert if addOrOverlap fails */ ))
{ |
| 334 return false; | 329 return false; |
| 335 } | 330 } |
| 336 } | 331 } |
| 337 } | 332 } |
| 338 return true; | 333 return true; |
| 339 } | 334 } |
| 340 | 335 |
| 341 // description below | 336 // description below |
| 342 bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) { | 337 bool SkOpCoincidence::addEndMovedSpans(const SkOpPtT* ptT) { |
| 343 if (!ptT->span()->upCastable()) { | 338 FAIL_IF(!ptT->span()->upCastable()); |
| 344 return false; | |
| 345 } | |
| 346 const SkOpSpan* base = ptT->span()->upCast(); | 339 const SkOpSpan* base = ptT->span()->upCast(); |
| 347 const SkOpSpan* prev = base->prev(); | 340 const SkOpSpan* prev = base->prev(); |
| 348 if (!prev) { | 341 FAIL_IF(!prev); |
| 349 return false; | |
| 350 } | |
| 351 if (!prev->isCanceled()) { | 342 if (!prev->isCanceled()) { |
| 352 if (!this->addEndMovedSpans(base, base->prev())) { | 343 if (!this->addEndMovedSpans(base, base->prev())) { |
| 353 return false; | 344 return false; |
| 354 } | 345 } |
| 355 } | 346 } |
| 356 if (!base->isCanceled()) { | 347 if (!base->isCanceled()) { |
| 357 if (!this->addEndMovedSpans(base, base->next())) { | 348 if (!this->addEndMovedSpans(base, base->next())) { |
| 358 return false; | 349 return false; |
| 359 } | 350 } |
| 360 } | 351 } |
| (...skipping 11 matching lines...) Expand all Loading... |
| 372 */ | 363 */ |
| 373 bool SkOpCoincidence::addEndMovedSpans() { | 364 bool SkOpCoincidence::addEndMovedSpans() { |
| 374 SkCoincidentSpans* span = fHead; | 365 SkCoincidentSpans* span = fHead; |
| 375 if (!span) { | 366 if (!span) { |
| 376 return true; | 367 return true; |
| 377 } | 368 } |
| 378 fTop = span; | 369 fTop = span; |
| 379 fHead = nullptr; | 370 fHead = nullptr; |
| 380 do { | 371 do { |
| 381 if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) { | 372 if (span->coinPtTStart()->fPt != span->oppPtTStart()->fPt) { |
| 382 if (1 == span->coinPtTStart()->fT) { | 373 FAIL_IF(1 == span->coinPtTStart()->fT); |
| 383 return false; | |
| 384 } | |
| 385 bool onEnd = span->coinPtTStart()->fT == 0; | 374 bool onEnd = span->coinPtTStart()->fT == 0; |
| 386 bool oOnEnd = zero_or_one(span->oppPtTStart()->fT); | 375 bool oOnEnd = zero_or_one(span->oppPtTStart()->fT); |
| 387 if (onEnd) { | 376 if (onEnd) { |
| 388 if (!oOnEnd) { // if both are on end, any nearby intersect was
already found | 377 if (!oOnEnd) { // if both are on end, any nearby intersect was
already found |
| 389 if (!this->addEndMovedSpans(span->oppPtTStart())) { | 378 if (!this->addEndMovedSpans(span->oppPtTStart())) { |
| 390 return false; | 379 return false; |
| 391 } | 380 } |
| 392 } | 381 } |
| 393 } else if (oOnEnd) { | 382 } else if (oOnEnd) { |
| 394 if (!this->addEndMovedSpans(span->coinPtTStart())) { | 383 if (!this->addEndMovedSpans(span->coinPtTStart())) { |
| (...skipping 206 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 601 SkTSwap(oppTs, oppTe); | 590 SkTSwap(oppTs, oppTe); |
| 602 } | 591 } |
| 603 if (swap) { | 592 if (swap) { |
| 604 SkTSwap(oppTs, oppTe); | 593 SkTSwap(oppTs, oppTe); |
| 605 } | 594 } |
| 606 SkOpSegment* coinSeg = coinPtTStart->segment(); | 595 SkOpSegment* coinSeg = coinPtTStart->segment(); |
| 607 SkOpSegment* oppSeg = oppPtTStart->segment(); | 596 SkOpSegment* oppSeg = oppPtTStart->segment(); |
| 608 if (coinSeg == oppSeg) { | 597 if (coinSeg == oppSeg) { |
| 609 return false; | 598 return false; |
| 610 } | 599 } |
| 611 return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe); | 600 return this->addOrOverlap(coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe |
| 601 SkDEBUGPARAMS(false) /* don't assert if addOrOverlap fails */ ); |
| 612 } | 602 } |
| 613 | 603 |
| 614 /* Please keep this in sync with debugAddOrOverlap() */ | 604 /* Please keep this in sync with debugAddOrOverlap() */ |
| 605 // If this is called by addEndMovedSpans(), a returned false propogates out to a
n abort. |
| 606 // If this is called by AddIfMissing(), a returned false indicates there was not
hing to add |
| 615 bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, | 607 bool SkOpCoincidence::addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg, |
| 616 double coinTs, double coinTe, double oppTs, double oppTe) { | 608 double coinTs, double coinTe, double oppTs, double oppTe |
| 609 SkDEBUGPARAMS(bool callerAborts)) { |
| 617 SkTDArray<SkCoincidentSpans*> overlaps; | 610 SkTDArray<SkCoincidentSpans*> overlaps; |
| 618 if (!fTop) { | 611 RETURN_FALSE_IF(callerAborts, !fTop); |
| 619 return false; | |
| 620 } | |
| 621 if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe,
&overlaps)) { | 612 if (!this->checkOverlap(fTop, coinSeg, oppSeg, coinTs, coinTe, oppTs, oppTe,
&overlaps)) { |
| 622 return false; | 613 return false; |
| 623 } | 614 } |
| 624 if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, | 615 if (fHead && !this->checkOverlap(fHead, coinSeg, oppSeg, coinTs, |
| 625 coinTe, oppTs, oppTe, &overlaps)) { | 616 coinTe, oppTs, oppTe, &overlaps)) { |
| 626 return false; | 617 return false; |
| 627 } | 618 } |
| 628 SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; | 619 SkCoincidentSpans* overlap = overlaps.count() ? overlaps[0] : nullptr; |
| 629 for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps
before continuing | 620 for (int index = 1; index < overlaps.count(); ++index) { // combine overlaps
before continuing |
| 630 SkCoincidentSpans* test = overlaps[index]; | 621 SkCoincidentSpans* test = overlaps[index]; |
| (...skipping 12 matching lines...) Expand all Loading... |
| 643 ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT | 634 ? overlap->oppPtTEnd()->fT > test->oppPtTEnd()->fT |
| 644 : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) { | 635 : overlap->oppPtTEnd()->fT < test->oppPtTEnd()->fT) { |
| 645 overlap->setOppPtTEnd(test->oppPtTEnd()); | 636 overlap->setOppPtTEnd(test->oppPtTEnd()); |
| 646 } | 637 } |
| 647 if (!fHead || !this->release(fHead, test)) { | 638 if (!fHead || !this->release(fHead, test)) { |
| 648 SkAssertResult(this->release(fTop, test)); | 639 SkAssertResult(this->release(fTop, test)); |
| 649 } | 640 } |
| 650 } | 641 } |
| 651 const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg); | 642 const SkOpPtT* cs = coinSeg->existing(coinTs, oppSeg); |
| 652 const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg); | 643 const SkOpPtT* ce = coinSeg->existing(coinTe, oppSeg); |
| 653 if (overlap && cs && ce && overlap->contains(cs, ce)) { | 644 RETURN_FALSE_IF(callerAborts, overlap && cs && ce && overlap->contains(cs, c
e)); |
| 654 return false; | 645 RETURN_FALSE_IF(callerAborts, cs == ce && cs); |
| 655 } | |
| 656 if (cs == ce && cs) { | |
| 657 return false; | |
| 658 } | |
| 659 const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); | 646 const SkOpPtT* os = oppSeg->existing(oppTs, coinSeg); |
| 660 const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); | 647 const SkOpPtT* oe = oppSeg->existing(oppTe, coinSeg); |
| 661 if (overlap && os && oe && overlap->contains(os, oe)) { | 648 RETURN_FALSE_IF(callerAborts, overlap && os && oe && overlap->contains(os, o
e)); |
| 662 return false; | |
| 663 } | |
| 664 SkASSERT(!cs || !cs->deleted()); | 649 SkASSERT(!cs || !cs->deleted()); |
| 665 SkASSERT(!os || !os->deleted()); | 650 SkASSERT(!os || !os->deleted()); |
| 666 SkASSERT(!ce || !ce->deleted()); | 651 SkASSERT(!ce || !ce->deleted()); |
| 667 SkASSERT(!oe || !oe->deleted()); | 652 SkASSERT(!oe || !oe->deleted()); |
| 668 const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullp
tr; | 653 const SkOpPtT* csExisting = !cs ? coinSeg->existing(coinTs, nullptr) : nullp
tr; |
| 669 const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullp
tr; | 654 const SkOpPtT* ceExisting = !ce ? coinSeg->existing(coinTe, nullptr) : nullp
tr; |
| 670 if (csExisting && csExisting == ceExisting) { | 655 RETURN_FALSE_IF(callerAborts, csExisting && csExisting == ceExisting); |
| 671 return false; | 656 RETURN_FALSE_IF(callerAborts, csExisting && (csExisting == ce || |
| 672 } | 657 csExisting->contains(ceExisting ? ceExisting : ce))); |
| 673 if (csExisting && (csExisting == ce || csExisting->contains(ceExisting ? ceE
xisting : ce))) { | 658 RETURN_FALSE_IF(callerAborts, ceExisting && (ceExisting == cs || |
| 674 return false; | 659 ceExisting->contains(csExisting ? csExisting : cs))); |
| 675 } | |
| 676 if (ceExisting && (ceExisting == cs || ceExisting->contains(csExisting ? csE
xisting : cs))) { | |
| 677 return false; | |
| 678 } | |
| 679 const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr
; | 660 const SkOpPtT* osExisting = !os ? oppSeg->existing(oppTs, nullptr) : nullptr
; |
| 680 const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr
; | 661 const SkOpPtT* oeExisting = !oe ? oppSeg->existing(oppTe, nullptr) : nullptr
; |
| 681 if (osExisting && osExisting == oeExisting) { | 662 RETURN_FALSE_IF(callerAborts, osExisting && osExisting == oeExisting); |
| 682 return false; | 663 RETURN_FALSE_IF(callerAborts, osExisting && (osExisting == oe || |
| 683 } | 664 osExisting->contains(oeExisting ? oeExisting : oe))); |
| 684 if (osExisting && (osExisting == oe || osExisting->contains(oeExisting ? oeE
xisting : oe))) { | 665 RETURN_FALSE_IF(callerAborts, oeExisting && (oeExisting == os || |
| 685 return false; | 666 oeExisting->contains(osExisting ? osExisting : os))); |
| 686 } | |
| 687 if (oeExisting && (oeExisting == os || oeExisting->contains(osExisting ? osE
xisting : os))) { | |
| 688 return false; | |
| 689 } | |
| 690 // extra line in debug code | 667 // extra line in debug code |
| 691 this->debugValidate(); | 668 this->debugValidate(); |
| 692 if (!cs || !os) { | 669 if (!cs || !os) { |
| 693 SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs) | 670 SkOpPtT* csWritable = cs ? const_cast<SkOpPtT*>(cs) |
| 694 : coinSeg->addT(coinTs, nullptr); | 671 : coinSeg->addT(coinTs, nullptr); |
| 695 SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) | 672 SkOpPtT* osWritable = os ? const_cast<SkOpPtT*>(os) |
| 696 : oppSeg->addT(oppTs, nullptr); | 673 : oppSeg->addT(oppTs, nullptr); |
| 697 if (!csWritable || !osWritable) { | 674 RETURN_FALSE_IF(callerAborts, !csWritable || !osWritable); |
| 698 return false; | |
| 699 } | |
| 700 csWritable->span()->addOppAndMerge(osWritable->span()); | 675 csWritable->span()->addOppAndMerge(osWritable->span()); |
| 701 cs = csWritable; | 676 cs = csWritable; |
| 702 os = osWritable; | 677 os = osWritable; |
| 703 if ((ce && ce->deleted()) || (oe && oe->deleted())) { | 678 RETURN_FALSE_IF(callerAborts, (ce && ce->deleted()) || (oe && oe->delete
d())); |
| 704 return false; | |
| 705 } | |
| 706 } | 679 } |
| 707 if (!ce || !oe) { | 680 if (!ce || !oe) { |
| 708 SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce) | 681 SkOpPtT* ceWritable = ce ? const_cast<SkOpPtT*>(ce) |
| 709 : coinSeg->addT(coinTe, nullptr); | 682 : coinSeg->addT(coinTe, nullptr); |
| 710 SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe) | 683 SkOpPtT* oeWritable = oe ? const_cast<SkOpPtT*>(oe) |
| 711 : oppSeg->addT(oppTe, nullptr); | 684 : oppSeg->addT(oppTe, nullptr); |
| 712 ceWritable->span()->addOppAndMerge(oeWritable->span()); | 685 ceWritable->span()->addOppAndMerge(oeWritable->span()); |
| 713 ce = ceWritable; | 686 ce = ceWritable; |
| 714 oe = oeWritable; | 687 oe = oeWritable; |
| 715 } | 688 } |
| 716 this->debugValidate(); | 689 this->debugValidate(); |
| 717 if (cs->deleted() || os->deleted() || ce->deleted() || oe->deleted()) { | 690 RETURN_FALSE_IF(callerAborts, cs->deleted()); |
| 718 return false; | 691 RETURN_FALSE_IF(callerAborts, os->deleted()); |
| 719 } | 692 RETURN_FALSE_IF(callerAborts, ce->deleted()); |
| 720 if (cs->contains(ce) || os->contains(oe)) { | 693 RETURN_FALSE_IF(callerAborts, oe->deleted()); |
| 721 return false; | 694 RETURN_FALSE_IF(callerAborts, cs->contains(ce) || os->contains(oe)); |
| 722 } | |
| 723 bool result = true; | 695 bool result = true; |
| 724 if (overlap) { | 696 if (overlap) { |
| 725 if (overlap->coinPtTStart()->segment() == coinSeg) { | 697 if (overlap->coinPtTStart()->segment() == coinSeg) { |
| 726 result = overlap->extend(cs, ce, os, oe); | 698 result = overlap->extend(cs, ce, os, oe); |
| 727 } else { | 699 } else { |
| 728 if (os->fT > oe->fT) { | 700 if (os->fT > oe->fT) { |
| 729 SkTSwap(cs, ce); | 701 SkTSwap(cs, ce); |
| 730 SkTSwap(os, oe); | 702 SkTSwap(os, oe); |
| 731 } | 703 } |
| 732 result = overlap->extend(os, oe, cs, ce); | 704 result = overlap->extend(os, oe, cs, ce); |
| (...skipping 742 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1475 this->release(fHead, coin); | 1447 this->release(fHead, coin); |
| 1476 } | 1448 } |
| 1477 } while ((coin = coin->next())); | 1449 } while ((coin = coin->next())); |
| 1478 } | 1450 } |
| 1479 | 1451 |
| 1480 bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const S
kOpPtT* testS, | 1452 bool SkOpCoincidence::testForCoincidence(const SkCoincidentSpans* outer, const S
kOpPtT* testS, |
| 1481 const SkOpPtT* testE) const { | 1453 const SkOpPtT* testE) const { |
| 1482 return testS->segment()->testForCoincidence(testS, testE, testS->span(), | 1454 return testS->segment()->testForCoincidence(testS, testE, testS->span(), |
| 1483 testE->span(), outer->coinPtTStart()->segment()); | 1455 testE->span(), outer->coinPtTStart()->segment()); |
| 1484 } | 1456 } |
| OLD | NEW |