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 |