Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(3)

Side by Side Diff: src/pathops/SkOpSegment.cpp

Issue 686843002: Revert of harden pathops for pathological test (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 6 years, 1 month ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « src/pathops/SkOpSegment.h ('k') | src/pathops/SkPathOpsCommon.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 /* 1 /*
2 * Copyright 2012 Google Inc. 2 * Copyright 2012 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 "SkIntersections.h" 7 #include "SkIntersections.h"
8 #include "SkOpContour.h" 8 #include "SkOpContour.h"
9 #include "SkOpSegment.h" 9 #include "SkOpSegment.h"
10 #include "SkPathWriter.h" 10 #include "SkPathWriter.h"
(...skipping 142 matching lines...) Expand 10 before | Expand all | Expand 10 after
153 } 153 }
154 next: 154 next:
155 lastDone = span.fDone; 155 lastDone = span.fDone;
156 } 156 }
157 return topPt; 157 return topPt;
158 } 158 }
159 159
160 bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask , SkPathOp op) { 160 bool SkOpSegment::activeOp(int index, int endIndex, int xorMiMask, int xorSuMask , SkPathOp op) {
161 int sumMiWinding = updateWinding(endIndex, index); 161 int sumMiWinding = updateWinding(endIndex, index);
162 int sumSuWinding = updateOppWinding(endIndex, index); 162 int sumSuWinding = updateOppWinding(endIndex, index);
163 #if DEBUG_LIMIT_WIND_SUM
164 SkASSERT(abs(sumMiWinding) <= DEBUG_LIMIT_WIND_SUM);
165 SkASSERT(abs(sumSuWinding) <= DEBUG_LIMIT_WIND_SUM);
166 #endif
167 if (fOperand) { 163 if (fOperand) {
168 SkTSwap<int>(sumMiWinding, sumSuWinding); 164 SkTSwap<int>(sumMiWinding, sumSuWinding);
169 } 165 }
170 return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &s umSuWinding); 166 return activeOp(xorMiMask, xorSuMask, index, endIndex, op, &sumMiWinding, &s umSuWinding);
171 } 167 }
172 168
173 bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex , SkPathOp op, 169 bool SkOpSegment::activeOp(int xorMiMask, int xorSuMask, int index, int endIndex , SkPathOp op,
174 int* sumMiWinding, int* sumSuWinding) { 170 int* sumMiWinding, int* sumSuWinding) {
175 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding; 171 int maxWinding, sumWinding, oppMaxWinding, oppSumWinding;
176 setUpWindings(index, endIndex, sumMiWinding, sumSuWinding, 172 setUpWindings(index, endIndex, sumMiWinding, sumSuWinding,
(...skipping 437 matching lines...) Expand 10 before | Expand all | Expand 10 after
614 span->fChased = false; 610 span->fChased = false;
615 span->fCoincident = false; 611 span->fCoincident = false;
616 span->fLoop = false; 612 span->fLoop = false;
617 span->fNear = false; 613 span->fNear = false;
618 span->fMultiple = false; 614 span->fMultiple = false;
619 span->fSmall = false; 615 span->fSmall = false;
620 span->fTiny = false; 616 span->fTiny = false;
621 if ((span->fDone = newT == 1)) { 617 if ((span->fDone = newT == 1)) {
622 ++fDoneSpans; 618 ++fDoneSpans;
623 } 619 }
624 setSpanFlags(pt, newT, span);
625 return insertedAt;
626 }
627
628 void SkOpSegment::setSpanFlags(const SkPoint& pt, double newT, SkOpSpan* span) {
629 int less = -1; 620 int less = -1;
630 // FIXME: note that this relies on spans being a continguous array 621 // FIXME: note that this relies on spans being a continguous array
631 // find range of spans with nearly the same point as this one 622 // find range of spans with nearly the same point as this one
632 // FIXME: SkDPoint::ApproximatelyEqual is better but breaks tests at the mom ent 623 // FIXME: SkDPoint::ApproximatelyEqual is better but breaks tests at the mom ent
633 while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) { 624 while (&span[less + 1] - fTs.begin() > 0 && AlmostEqualUlps(span[less].fPt, pt)) {
634 if (fVerb == SkPath::kCubic_Verb) { 625 if (fVerb == SkPath::kCubic_Verb) {
635 double tInterval = newT - span[less].fT; 626 double tInterval = newT - span[less].fT;
636 double tMid = newT - tInterval / 2; 627 double tMid = newT - tInterval / 2;
637 SkDPoint midPt = dcubic_xy_at_t(fPts, tMid); 628 SkDPoint midPt = dcubic_xy_at_t(fPts, tMid);
638 if (!midPt.approximatelyEqual(xyAtT(span))) { 629 if (!midPt.approximatelyEqual(xyAtT(span))) {
(...skipping 15 matching lines...) Expand all
654 } 645 }
655 ++more; 646 ++more;
656 } 647 }
657 ++less; 648 ++less;
658 --more; 649 --more;
659 while (more - 1 > less && span[more].fPt == span[more - 1].fPt 650 while (more - 1 > less && span[more].fPt == span[more - 1].fPt
660 && span[more].fT == span[more - 1].fT) { 651 && span[more].fT == span[more - 1].fT) {
661 --more; 652 --more;
662 } 653 }
663 if (less == more) { 654 if (less == more) {
664 return; 655 return insertedAt;
665 } 656 }
666 if (precisely_negative(span[more].fT - span[less].fT)) { 657 if (precisely_negative(span[more].fT - span[less].fT)) {
667 return; 658 return insertedAt;
668 } 659 }
669 // if the total range of t values is big enough, mark all tiny 660 // if the total range of t values is big enough, mark all tiny
670 bool tiny = span[less].fPt == span[more].fPt; 661 bool tiny = span[less].fPt == span[more].fPt;
671 int index = less; 662 int index = less;
672 do { 663 do {
673 fSmall = span[index].fSmall = true; 664 fSmall = span[index].fSmall = true;
674 fTiny |= span[index].fTiny = tiny; 665 fTiny |= span[index].fTiny = tiny;
675 if (!span[index].fDone) { 666 if (!span[index].fDone) {
676 span[index].fDone = true; 667 span[index].fDone = true;
677 ++fDoneSpans; 668 ++fDoneSpans;
678 } 669 }
679 } while (++index < more); 670 } while (++index < more);
680 return; 671 return insertedAt;
681 }
682
683 void SkOpSegment::resetSpanFlags() {
684 fSmall = fTiny = false;
685 fDoneSpans = 0;
686 int start = 0;
687 int last = this->count() - 1;
688 do {
689 SkOpSpan* startSpan = &this->fTs[start];
690 double startT = startSpan->fT;
691 startSpan->fSmall = startSpan->fTiny = false; // sets range initial
692 bool terminus = startT == 1;
693 if ((startSpan->fDone = !startSpan->fWindValue | terminus)) {
694 ++fDoneSpans;
695 }
696 ++start; // range initial + 1
697 if (terminus) {
698 continue;
699 }
700 const SkPoint& pt = startSpan->fPt;
701 int end = start; // range initial + 1
702 while (end <= last) {
703 const SkOpSpan& endSpan = this->span(end);
704 if (!AlmostEqualUlps(endSpan.fPt, pt)) {
705 break;
706 }
707 if (fVerb == SkPath::kCubic_Verb) {
708 double tMid = (startSpan->fT + endSpan.fT) / 2;
709 SkDPoint midEndPt = dcubic_xy_at_t(fPts, tMid);
710 if (!midEndPt.approximatelyEqual(xyAtT(startSpan))) {
711 break;
712 }
713 }
714 ++end;
715 }
716 if (start == end) { // end == range final + 1
717 continue;
718 }
719 while (--end >= start) { // end == range final
720 const SkOpSpan& endSpan = this->span(end);
721 const SkOpSpan& priorSpan = this->span(end - 1);
722 if (endSpan.fPt != priorSpan.fPt || endSpan.fT != priorSpan.fT) {
723 break; // end == range final + 1
724 }
725 }
726 if (end < start) { // end == range final + 1
727 continue;
728 }
729 int index = start - 1; // index == range initial
730 start = end; // start = range final + 1
731 const SkOpSpan& nextSpan = this->span(end);
732 if (precisely_negative(nextSpan.fT - startSpan->fT)) {
733 while (++index < end) {
734 startSpan = &this->fTs[index];
735 startSpan->fSmall = startSpan->fTiny = false; // sets range ini tial + 1
736 if ((startSpan->fDone = !startSpan->fWindValue)) {
737 ++fDoneSpans;
738 }
739 }
740 continue;
741 }
742 if (!startSpan->fWindValue) {
743 --fDoneSpans; // added back below
744 }
745 bool tiny = nextSpan.fPt == startSpan->fPt;
746 do {
747 fSmall = startSpan->fSmall = true; // sets range initial
748 fTiny |= startSpan->fTiny = tiny;
749 startSpan->fDone = true;
750 ++fDoneSpans;
751 startSpan = &this->fTs[++index];
752 } while (index < end); // loop through tiny small range end (last)
753 } while (start <= last);
754 } 672 }
755 673
756 // set spans from start to end to decrement by one 674 // set spans from start to end to decrement by one
757 // note this walks other backwards 675 // note this walks other backwards
758 // FIXME: there's probably an edge case that can be constructed where 676 // FIXME: there's probably an edge case that can be constructed where
759 // two span in one segment are separated by float epsilon on one span but 677 // two span in one segment are separated by float epsilon on one span but
760 // not the other, if one segment is very small. For this 678 // not the other, if one segment is very small. For this
761 // case the counts asserted below may or may not be enough to separate the 679 // case the counts asserted below may or may not be enough to separate the
762 // spans. Even if the counts work out, what if the spans aren't correctly 680 // spans. Even if the counts work out, what if the spans aren't correctly
763 // sorted? It feels better in such a case to match the span's other span 681 // sorted? It feels better in such a case to match the span's other span
(...skipping 281 matching lines...) Expand 10 before | Expand all | Expand 10 after
1045 } 963 }
1046 skipExactMatches: 964 skipExactMatches:
1047 ; 965 ;
1048 } 966 }
1049 ++index; 967 ++index;
1050 } 968 }
1051 } 969 }
1052 debugValidate(); 970 debugValidate();
1053 } 971 }
1054 972
1055 void SkOpSegment::alignRange(int lower, int upper,
1056 const SkOpSegment* other, int oLower, int oUpper) {
1057 for (int oIndex = oLower; oIndex <= oUpper; ++oIndex) {
1058 const SkOpSpan& oSpan = other->span(oIndex);
1059 const SkOpSegment* oOther = oSpan.fOther;
1060 if (oOther == this) {
1061 continue;
1062 }
1063 SkOpSpan* matchSpan;
1064 int matchIndex;
1065 const SkOpSpan* refSpan;
1066 for (int iIndex = lower; iIndex <= upper; ++iIndex) {
1067 const SkOpSpan& iSpan = this->span(iIndex);
1068 const SkOpSegment* iOther = iSpan.fOther;
1069 if (iOther == other) {
1070 continue;
1071 }
1072 if (iOther == oOther) {
1073 goto nextI;
1074 }
1075 }
1076 {
1077 // oSpan does not have a match in this
1078 int iCount = this->count();
1079 const SkOpSpan* iMatch = NULL;
1080 double iMatchTDiff;
1081 matchIndex = -1;
1082 for (int iIndex = 0; iIndex < iCount; ++iIndex) {
1083 const SkOpSpan& iSpan = this->span(iIndex);
1084 const SkOpSegment* iOther = iSpan.fOther;
1085 if (iOther != oOther) {
1086 continue;
1087 }
1088 double testTDiff = fabs(iSpan.fOtherT - oSpan.fOtherT);
1089 if (!iMatch || testTDiff < iMatchTDiff) {
1090 matchIndex = iIndex;
1091 iMatch = &iSpan;
1092 iMatchTDiff = testTDiff;
1093 }
1094 }
1095 if (matchIndex < 0) {
1096 continue; // the entry is missing, & will be picked up later (F IXME: fix it here?)
1097 }
1098 matchSpan = &this->fTs[matchIndex];
1099 refSpan = &this->span(lower);
1100 if (!SkDPoint::ApproximatelyEqual(matchSpan->fPt, refSpan->fPt)) {
1101 goto nextI;
1102 }
1103 if (matchIndex != lower - 1 && matchIndex != upper + 1) {
1104 // the consecutive spans need to be rearranged to get the missin g one close
1105 continue; // FIXME: more work to do
1106 }
1107 }
1108 {
1109 this->fixOtherTIndex();
1110 SkScalar newT;
1111 if (matchSpan->fT != 0 && matchSpan->fT != 1) {
1112 newT = matchSpan->fT = refSpan->fT;
1113 matchSpan->fOther->fTs[matchSpan->fOtherIndex].fOtherT = refSpan ->fT;
1114 } else { // leave span at the start or end there and adjust the nei ghbors
1115 newT = matchSpan->fT;
1116 for (int iIndex = lower; iIndex <= upper; ++iIndex) {
1117 matchSpan = &this->fTs[iIndex];
1118 matchSpan->fT = newT;
1119 matchSpan->fOther->fTs[matchSpan->fOtherIndex].fOtherT = new T;
1120 }
1121 }
1122 this->resetSpanFlags(); // fix up small / tiny / done
1123 // align ts of other ranges with adjacent spans that match the align ed points
1124 lower = SkTMin(lower, matchIndex);
1125 while (lower > 0) {
1126 const SkOpSpan& span = this->span(lower - 1);
1127 if (span.fT != newT) {
1128 break;
1129 }
1130 --lower;
1131 }
1132 upper = SkTMax(upper, matchIndex);
1133 int last = this->count() - 1;
1134 while (upper < last) {
1135 const SkOpSpan& span = this->span(upper + 1);
1136 if (span.fT != newT) {
1137 break;
1138 }
1139 ++upper;
1140 }
1141 for (int iIndex = lower; iIndex <= upper; ++iIndex) {
1142 const SkOpSpan& span = this->span(iIndex);
1143 SkOpSegment* aOther = span.fOther;
1144 int aLower = span.fOtherIndex;
1145 SkScalar aT = span.fOtherT;
1146 bool aResetFlags = false;
1147 while (aLower > 0) {
1148 SkOpSpan* aSpan = &aOther->fTs[aLower - 1];
1149 for (int iIndex = lower; iIndex <= upper; ++iIndex) {
1150 if (aSpan->fPt == this->fTs[iIndex].fPt) {
1151 goto matchFound;
1152 }
1153 }
1154 break;
1155 matchFound:
1156 --aLower;
1157 }
1158 int aUpper = span.fOtherIndex;
1159 int aLast = aOther->count() - 1;
1160 while (aUpper < aLast) {
1161 SkOpSpan* aSpan = &aOther->fTs[aUpper + 1];
1162 for (int iIndex = lower; iIndex <= upper; ++iIndex) {
1163 if (aSpan->fPt == this->fTs[iIndex].fPt) {
1164 goto matchFound2;
1165 }
1166 }
1167 break;
1168 matchFound2:
1169 ++aUpper;
1170 }
1171 if (aOther->fTs[aLower].fT == 0) {
1172 aT = 0;
1173 } else if (aOther->fTs[aUpper].fT == 1) {
1174 aT = 1;
1175 }
1176 bool aFixed = false;
1177 for (int aIndex = aLower; aIndex <= aUpper; ++aIndex) {
1178 SkOpSpan* aSpan = &aOther->fTs[aIndex];
1179 if (aSpan->fT == aT) {
1180 continue;
1181 }
1182 SkASSERT(way_roughly_equal(aSpan->fT, aT));
1183 if (!aFixed) {
1184 aOther->fixOtherTIndex();
1185 aFixed = true;
1186 }
1187 aSpan->fT = aT;
1188 aSpan->fOther->fTs[aSpan->fOtherIndex].fOtherT = aT;
1189 aResetFlags = true;
1190 }
1191 if (aResetFlags) {
1192 aOther->resetSpanFlags();
1193 }
1194 }
1195 }
1196 nextI: ;
1197 }
1198 }
1199
1200 void SkOpSegment::alignSpan(const SkPoint& newPt, double newT, const SkOpSegment * other, 973 void SkOpSegment::alignSpan(const SkPoint& newPt, double newT, const SkOpSegment * other,
1201 double otherT, const SkOpSegment* other2, SkOpSpan* oSpan, 974 double otherT, const SkOpSegment* other2, SkOpSpan* oSpan,
1202 SkTDArray<AlignedSpan>* alignedArray) { 975 SkTDArray<AlignedSpan>* alignedArray) {
1203 AlignedSpan* aligned = alignedArray->append(); 976 AlignedSpan* aligned = alignedArray->append();
1204 aligned->fOldPt = oSpan->fPt; 977 aligned->fOldPt = oSpan->fPt;
1205 aligned->fPt = newPt; 978 aligned->fPt = newPt;
1206 aligned->fOldT = oSpan->fT; 979 aligned->fOldT = oSpan->fT;
1207 aligned->fT = newT; 980 aligned->fT = newT;
1208 aligned->fSegment = this; // OPTIMIZE: may be unused, can remove 981 aligned->fSegment = this; // OPTIMIZE: may be unused, can remove
1209 aligned->fOther1 = other; 982 aligned->fOther1 = other;
(...skipping 255 matching lines...) Expand 10 before | Expand all | Expand 10 after
1465 void SkOpSegment::bumpCoincidentOBlind(int index, int endIndex) { 1238 void SkOpSegment::bumpCoincidentOBlind(int index, int endIndex) {
1466 do { 1239 do {
1467 zeroSpan(&fTs[index]); 1240 zeroSpan(&fTs[index]);
1468 } while (++index < endIndex); 1241 } while (++index < endIndex);
1469 } 1242 }
1470 1243
1471 // because of the order in which coincidences are resolved, this and other 1244 // because of the order in which coincidences are resolved, this and other
1472 // may not have the same intermediate points. Compute the corresponding 1245 // may not have the same intermediate points. Compute the corresponding
1473 // intermediate T values (using this as the master, other as the follower) 1246 // intermediate T values (using this as the master, other as the follower)
1474 // and walk other conditionally -- hoping that it catches up in the end 1247 // and walk other conditionally -- hoping that it catches up in the end
1475 bool SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr, 1248 void SkOpSegment::bumpCoincidentOther(const SkOpSpan& test, int* oIndexPtr,
1476 SkTArray<SkPoint, true>* oOutsidePts, const SkPoint& oEndPt) { 1249 SkTArray<SkPoint, true>* oOutsidePts) {
1477 int oIndex = *oIndexPtr; 1250 int oIndex = *oIndexPtr;
1478 SkOpSpan* const oTest = &fTs[oIndex]; 1251 SkOpSpan* const oTest = &fTs[oIndex];
1479 SkOpSpan* oEnd = oTest; 1252 SkOpSpan* oEnd = oTest;
1480 const SkPoint& oStartPt = oTest->fPt; 1253 const SkPoint& oStartPt = oTest->fPt;
1481 double oStartT = oTest->fT; 1254 double oStartT = oTest->fT;
1482 #if 0 // FIXME : figure out what disabling this breaks 1255 #if 0 // FIXME : figure out what disabling this breaks
1483 const SkPoint& startPt = test.fPt; 1256 const SkPoint& startPt = test.fPt;
1484 // this is always true since oEnd == oTest && oStartPt == oTest->fPt -- find proper condition 1257 // this is always true since oEnd == oTest && oStartPt == oTest->fPt -- find proper condition
1485 if (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) { 1258 if (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
1486 TrackOutside(oOutsidePts, startPt); 1259 TrackOutside(oOutsidePts, startPt);
1487 } 1260 }
1488 #endif 1261 #endif
1489 bool foundEnd = false;
1490 while (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) { 1262 while (oStartPt == oEnd->fPt || precisely_equal(oStartT, oEnd->fT)) {
1491 foundEnd |= oEndPt == oEnd->fPt;
1492 zeroSpan(oEnd); 1263 zeroSpan(oEnd);
1493 oEnd = &fTs[++oIndex]; 1264 oEnd = &fTs[++oIndex];
1494 } 1265 }
1495 *oIndexPtr = oIndex; 1266 *oIndexPtr = oIndex;
1496 return foundEnd;
1497 } 1267 }
1498 1268
1499 // FIXME: need to test this case: 1269 // FIXME: need to test this case:
1500 // contourA has two segments that are coincident 1270 // contourA has two segments that are coincident
1501 // contourB has two segments that are coincident in the same place 1271 // contourB has two segments that are coincident in the same place
1502 // each ends up with +2/0 pairs for winding count 1272 // each ends up with +2/0 pairs for winding count
1503 // since logic below doesn't transfer count (only increments/decrements) can thi s be 1273 // since logic below doesn't transfer count (only increments/decrements) can thi s be
1504 // resolved to +4/0 ? 1274 // resolved to +4/0 ?
1505 1275
1506 // set spans from start to end to increment the greater by one and decrement 1276 // set spans from start to end to increment the greater by one and decrement
(...skipping 29 matching lines...) Expand all
1536 // paths with extreme data will fail this test and eject out of pathops alto gether later on 1306 // paths with extreme data will fail this test and eject out of pathops alto gether later on
1537 // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); 1307 // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1538 do { 1308 do {
1539 SkASSERT(test->fT < 1); 1309 SkASSERT(test->fT < 1);
1540 if (oTest->fT == 1) { 1310 if (oTest->fT == 1) {
1541 // paths with extreme data may be so mismatched that we fail here 1311 // paths with extreme data may be so mismatched that we fail here
1542 return false; 1312 return false;
1543 } 1313 }
1544 1314
1545 // consolidate the winding count even if done 1315 // consolidate the winding count even if done
1546 bool foundEnd = false;
1547 if ((test->fWindValue == 0 && test->fOppValue == 0) 1316 if ((test->fWindValue == 0 && test->fOppValue == 0)
1548 || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) { 1317 || (oTest->fWindValue == 0 && oTest->fOppValue == 0)) {
1549 SkDEBUGCODE(int firstWind = test->fWindValue); 1318 SkDEBUGCODE(int firstWind = test->fWindValue);
1550 SkDEBUGCODE(int firstOpp = test->fOppValue); 1319 SkDEBUGCODE(int firstOpp = test->fOppValue);
1551 do { 1320 do {
1552 SkASSERT(firstWind == fTs[index].fWindValue); 1321 SkASSERT(firstWind == fTs[index].fWindValue);
1553 SkASSERT(firstOpp == fTs[index].fOppValue); 1322 SkASSERT(firstOpp == fTs[index].fOppValue);
1554 ++index; 1323 ++index;
1555 SkASSERT(index < fTs.count()); 1324 SkASSERT(index < fTs.count());
1556 } while (*testPt == fTs[index].fPt); 1325 } while (*testPt == fTs[index].fPt);
1557 SkDEBUGCODE(firstWind = oTest->fWindValue); 1326 SkDEBUGCODE(firstWind = oTest->fWindValue);
1558 SkDEBUGCODE(firstOpp = oTest->fOppValue); 1327 SkDEBUGCODE(firstOpp = oTest->fOppValue);
1559 do { 1328 do {
1560 SkASSERT(firstWind == other->fTs[oIndex].fWindValue); 1329 SkASSERT(firstWind == other->fTs[oIndex].fWindValue);
1561 SkASSERT(firstOpp == other->fTs[oIndex].fOppValue); 1330 SkASSERT(firstOpp == other->fTs[oIndex].fOppValue);
1562 ++oIndex; 1331 ++oIndex;
1563 SkASSERT(oIndex < other->fTs.count()); 1332 SkASSERT(oIndex < other->fTs.count());
1564 } while (*oTestPt == other->fTs[oIndex].fPt); 1333 } while (*oTestPt == other->fTs[oIndex].fPt);
1565 } else { 1334 } else {
1566 if (!binary || test->fWindValue + oTest->fOppValue >= 0) { 1335 if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1567 if (!bumpCoincidentThis(*oTest, binary, &index, &outsidePts)) { 1336 if (!bumpCoincidentThis(*oTest, binary, &index, &outsidePts)) {
1568 return false; 1337 return false;
1569 } 1338 }
1570 foundEnd = other->bumpCoincidentOther(*test, &oIndex, &oOutsideP ts, endPt); 1339 other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
1571 } else { 1340 } else {
1572 if (!other->bumpCoincidentThis(*test, binary, &oIndex, &oOutside Pts)) { 1341 if (!other->bumpCoincidentThis(*test, binary, &oIndex, &oOutside Pts)) {
1573 return false; 1342 return false;
1574 } 1343 }
1575 foundEnd = bumpCoincidentOther(*oTest, &index, &outsidePts, endP t); 1344 bumpCoincidentOther(*oTest, &index, &outsidePts);
1576 } 1345 }
1577 } 1346 }
1578 test = &fTs[index]; 1347 test = &fTs[index];
1579 testPt = &test->fPt; 1348 testPt = &test->fPt;
1580 testT = test->fT; 1349 testT = test->fT;
1581 oTest = &other->fTs[oIndex]; 1350 oTest = &other->fTs[oIndex];
1582 oTestPt = &oTest->fPt; 1351 oTestPt = &oTest->fPt;
1583 if (endPt == *testPt || precisely_equal(endT, testT)) { 1352 if (endPt == *testPt || precisely_equal(endT, testT)) {
1584 break; 1353 break;
1585 } 1354 }
1586 if (0 && foundEnd) { // FIXME: this is likely needed but wait until a t est case triggers it
1587 break;
1588 }
1589 // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt)); 1355 // SkASSERT(AlmostEqualUlps(*testPt, *oTestPt));
1590 } while (endPt != *oTestPt); 1356 } while (endPt != *oTestPt);
1591 // in rare cases, one may have ended before the other 1357 // in rare cases, one may have ended before the other
1592 if (endPt != *testPt && !precisely_equal(endT, testT)) { 1358 if (endPt != *testPt && !precisely_equal(endT, testT)) {
1593 int lastWind = test[-1].fWindValue; 1359 int lastWind = test[-1].fWindValue;
1594 int lastOpp = test[-1].fOppValue; 1360 int lastOpp = test[-1].fOppValue;
1595 bool zero = lastWind == 0 && lastOpp == 0; 1361 bool zero = lastWind == 0 && lastOpp == 0;
1596 do { 1362 do {
1597 if (test->fWindValue || test->fOppValue) { 1363 if (test->fWindValue || test->fOppValue) {
1598 test->fWindValue = lastWind; 1364 test->fWindValue = lastWind;
1599 test->fOppValue = lastOpp; 1365 test->fOppValue = lastOpp;
1600 if (zero) { 1366 if (zero) {
1601 SkASSERT(!test->fDone);
1602 test->fDone = true; 1367 test->fDone = true;
1603 ++fDoneSpans; 1368 ++fDoneSpans;
1604 } 1369 }
1605 } 1370 }
1606 test = &fTs[++index]; 1371 test = &fTs[++index];
1607 testPt = &test->fPt; 1372 testPt = &test->fPt;
1608 } while (endPt != *testPt); 1373 } while (endPt != *testPt);
1609 } 1374 }
1610 if (endPt != *oTestPt) { 1375 if (endPt != *oTestPt) {
1611 // look ahead to see if zeroing more spans will allows us to catch up 1376 // look ahead to see if zeroing more spans will allows us to catch up
(...skipping 18 matching lines...) Expand all
1630 } 1395 }
1631 if (++oPeekIndex == oCount) { 1396 if (++oPeekIndex == oCount) {
1632 break; 1397 break;
1633 } 1398 }
1634 oPeek = &other->fTs[oPeekIndex]; 1399 oPeek = &other->fTs[oPeekIndex];
1635 } while (endPt == oPeek->fPt); 1400 } while (endPt == oPeek->fPt);
1636 } 1401 }
1637 if (success) { 1402 if (success) {
1638 do { 1403 do {
1639 if (!binary || test->fWindValue + oTest->fOppValue >= 0) { 1404 if (!binary || test->fWindValue + oTest->fOppValue >= 0) {
1640 if (other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts, endPt)) { 1405 other->bumpCoincidentOther(*test, &oIndex, &oOutsidePts);
1641 break;
1642 }
1643 } else { 1406 } else {
1644 if (!other->bumpCoincidentThis(*test, binary, &oIndex, &oOut sidePts)) { 1407 if (!other->bumpCoincidentThis(*test, binary, &oIndex, &oOut sidePts)) {
1645 return false; 1408 return false;
1646 } 1409 }
1647 } 1410 }
1648 oTest = &other->fTs[oIndex]; 1411 oTest = &other->fTs[oIndex];
1649 oTestPt = &oTest->fPt; 1412 oTestPt = &oTest->fPt;
1650 } while (endPt != *oTestPt); 1413 } while (endPt != *oTestPt);
1651 } 1414 }
1652 } 1415 }
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after
1706 } 1469 }
1707 } 1470 }
1708 } 1471 }
1709 #if DEBUG_ADD_T_PAIR 1472 #if DEBUG_ADD_T_PAIR
1710 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n", 1473 SkDebugf("%s addTPair this=%d %1.9g other=%d %1.9g\n",
1711 __FUNCTION__, fID, t, other->fID, otherT); 1474 __FUNCTION__, fID, t, other->fID, otherT);
1712 #endif 1475 #endif
1713 SkASSERT(other != this); 1476 SkASSERT(other != this);
1714 int insertedAt = addT(other, pt, t); 1477 int insertedAt = addT(other, pt, t);
1715 int otherInsertedAt = other->addT(this, pt2, otherT); 1478 int otherInsertedAt = other->addT(this, pt2, otherT);
1716 this->addOtherT(insertedAt, otherT, otherInsertedAt); 1479 addOtherT(insertedAt, otherT, otherInsertedAt);
1717 other->addOtherT(otherInsertedAt, t, insertedAt); 1480 other->addOtherT(otherInsertedAt, t, insertedAt);
1718 this->matchWindingValue(insertedAt, t, borrowWind); 1481 matchWindingValue(insertedAt, t, borrowWind);
1719 other->matchWindingValue(otherInsertedAt, otherT, borrowWind); 1482 other->matchWindingValue(otherInsertedAt, otherT, borrowWind);
1720 SkOpSpan& span = this->fTs[insertedAt]; 1483 SkOpSpan& span = this->fTs[insertedAt];
1721 if (pt != pt2) { 1484 if (pt != pt2) {
1722 span.fNear = true; 1485 span.fNear = true;
1723 SkOpSpan& oSpan = other->fTs[otherInsertedAt]; 1486 SkOpSpan& oSpan = other->fTs[otherInsertedAt];
1724 oSpan.fNear = true; 1487 oSpan.fNear = true;
1725 } 1488 }
1726 // if the newly inserted spans match a neighbor on one but not the other, ma ke them agree
1727 int lower = this->nextExactSpan(insertedAt, -1) + 1;
1728 int upper = this->nextExactSpan(insertedAt, 1) - 1;
1729 if (upper < 0) {
1730 upper = this->count() - 1;
1731 }
1732 int oLower = other->nextExactSpan(otherInsertedAt, -1) + 1;
1733 int oUpper = other->nextExactSpan(otherInsertedAt, 1) - 1;
1734 if (oUpper < 0) {
1735 oUpper = other->count() - 1;
1736 }
1737 if (lower == upper && oLower == oUpper) {
1738 return &span;
1739 }
1740 #if DEBUG_CONCIDENT
1741 SkDebugf("%s id=%d lower=%d upper=%d other=%d oLower=%d oUpper=%d\n", __FUNC TION__,
1742 debugID(), lower, upper, other->debugID(), oLower, oUpper);
1743 #endif
1744 // find the nearby spans in one range missing in the other
1745 this->alignRange(lower, upper, other, oLower, oUpper);
1746 other->alignRange(oLower, oUpper, this, lower, upper);
1747 return &span; 1489 return &span;
1748 } 1490 }
1749 1491
1750 const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double other T, bool borrowWind, 1492 const SkOpSpan* SkOpSegment::addTPair(double t, SkOpSegment* other, double other T, bool borrowWind,
1751 const SkPoint& pt) { 1493 const SkPoint& pt) {
1752 return addTPair(t, other, otherT, borrowWind, pt, pt); 1494 return addTPair(t, other, otherT, borrowWind, pt, pt);
1753 } 1495 }
1754 1496
1755 bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const { 1497 bool SkOpSegment::betweenPoints(double midT, const SkPoint& pt1, const SkPoint& pt2) const {
1756 const SkPoint midPt = ptAtT(midT); 1498 const SkPoint midPt = ptAtT(midT);
(...skipping 387 matching lines...) Expand 10 before | Expand all | Expand 10 after
2144 SkASSERT(span->fWindValue >= 0); 1886 SkASSERT(span->fWindValue >= 0);
2145 span->fOppValue += oppDelta; 1887 span->fOppValue += oppDelta;
2146 SkASSERT(span->fOppValue >= 0); 1888 SkASSERT(span->fOppValue >= 0);
2147 if (fXor) { 1889 if (fXor) {
2148 span->fWindValue &= 1; 1890 span->fWindValue &= 1;
2149 } 1891 }
2150 if (fOppXor) { 1892 if (fOppXor) {
2151 span->fOppValue &= 1; 1893 span->fOppValue &= 1;
2152 } 1894 }
2153 if (!span->fWindValue && !span->fOppValue) { 1895 if (!span->fWindValue && !span->fOppValue) {
2154 if (!span->fDone) { 1896 span->fDone = true;
2155 span->fDone = true; 1897 ++fDoneSpans;
2156 ++fDoneSpans;
2157 }
2158 return true; 1898 return true;
2159 } 1899 }
2160 return false; 1900 return false;
2161 } 1901 }
2162 1902
2163 const SkOpSpan& SkOpSegment::firstSpan(const SkOpSpan& thisSpan) const { 1903 const SkOpSpan& SkOpSegment::firstSpan(const SkOpSpan& thisSpan) const {
2164 const SkOpSpan* firstSpan = &thisSpan; // rewind to the start 1904 const SkOpSpan* firstSpan = &thisSpan; // rewind to the start
2165 const SkOpSpan* beginSpan = fTs.begin(); 1905 const SkOpSpan* beginSpan = fTs.begin();
2166 const SkPoint& testPt = thisSpan.fPt; 1906 const SkPoint& testPt = thisSpan.fPt;
2167 while (firstSpan > beginSpan && firstSpan[-1].fPt == testPt) { 1907 while (firstSpan > beginSpan && firstSpan[-1].fPt == testPt) {
(...skipping 203 matching lines...) Expand 10 before | Expand all | Expand 10 after
2371 missing.fOther->fixOtherTIndex(); 2111 missing.fOther->fixOtherTIndex();
2372 } 2112 }
2373 for (index = 0; index < missingCoincidence.count(); ++index) { 2113 for (index = 0; index < missingCoincidence.count(); ++index) {
2374 MissingSpan& missing = missingCoincidence[index]; 2114 MissingSpan& missing = missingCoincidence[index];
2375 missing.fSegment->fixOtherTIndex(); 2115 missing.fSegment->fixOtherTIndex();
2376 } 2116 }
2377 debugValidate(); 2117 debugValidate();
2378 } 2118 }
2379 2119
2380 // look to see if the curve end intersects an intermediary that intersects the o ther 2120 // look to see if the curve end intersects an intermediary that intersects the o ther
2381 bool SkOpSegment::checkEnds() { 2121 void SkOpSegment::checkEnds() {
2382 debugValidate(); 2122 debugValidate();
2383 SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans; 2123 SkSTArray<kMissingSpanCount, MissingSpan, true> missingSpans;
2384 int count = fTs.count(); 2124 int count = fTs.count();
2385 for (int index = 0; index < count; ++index) { 2125 for (int index = 0; index < count; ++index) {
2386 const SkOpSpan& span = fTs[index]; 2126 const SkOpSpan& span = fTs[index];
2387 double otherT = span.fOtherT; 2127 double otherT = span.fOtherT;
2388 if (otherT != 0 && otherT != 1) { // only check ends 2128 if (otherT != 0 && otherT != 1) { // only check ends
2389 continue; 2129 continue;
2390 } 2130 }
2391 const SkOpSegment* other = span.fOther; 2131 const SkOpSegment* other = span.fOther;
(...skipping 54 matching lines...) Expand 10 before | Expand all | Expand 10 after
2446 if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) { 2186 if (match->betweenPoints(midT, tSpan.fPt, peekSpan.fPt)) {
2447 goto nextPeekIndex; 2187 goto nextPeekIndex;
2448 } 2188 }
2449 } 2189 }
2450 } 2190 }
2451 if (missingSpans.count() > 0) { 2191 if (missingSpans.count() > 0) {
2452 const MissingSpan& lastMissing = missingSpans.back(); 2192 const MissingSpan& lastMissing = missingSpans.back();
2453 if (lastMissing.fT == t 2193 if (lastMissing.fT == t
2454 && lastMissing.fOther == match 2194 && lastMissing.fOther == match
2455 && lastMissing.fOtherT == matchT) { 2195 && lastMissing.fOtherT == matchT) {
2456 SkASSERT(SkDPoint::ApproximatelyEqual(lastMissing.fPt, peekS pan.fPt)); 2196 SkASSERT(lastMissing.fPt == peekSpan.fPt);
2457 continue; 2197 continue;
2458 } 2198 }
2459 } 2199 }
2460 if (this == match) { 2200 #if DEBUG_CHECK_ENDS
2461 return false; // extremely large paths can trigger this
2462 }
2463 #if DEBUG_CHECK_ALIGN
2464 SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,% 1.9g)\n", 2201 SkDebugf("%s id=%d missing t=%1.9g other=%d otherT=%1.9g pt=(%1.9g,% 1.9g)\n",
2465 __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, p eekSpan.fPt.fY); 2202 __FUNCTION__, fID, t, match->fID, matchT, peekSpan.fPt.fX, p eekSpan.fPt.fY);
2466 #endif 2203 #endif
2467 // this segment is missing a entry that the other contains 2204 // this segment is missing a entry that the other contains
2468 // remember so we can add the missing one and recompute the indices 2205 // remember so we can add the missing one and recompute the indices
2469 { 2206 {
2470 MissingSpan& missing = missingSpans.push_back(); 2207 MissingSpan& missing = missingSpans.push_back();
2471 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing))); 2208 SkDEBUGCODE(sk_bzero(&missing, sizeof(missing)));
2472 missing.fT = t; 2209 missing.fT = t;
2473 SkASSERT(this != match); 2210 SkASSERT(this != match);
2474 missing.fOther = match; 2211 missing.fOther = match;
2475 missing.fOtherT = matchT; 2212 missing.fOtherT = matchT;
2476 missing.fPt = peekSpan.fPt; 2213 missing.fPt = peekSpan.fPt;
2477 } 2214 }
2478 break; 2215 break;
2479 nextPeekIndex: 2216 nextPeekIndex:
2480 ; 2217 ;
2481 } 2218 }
2482 } 2219 }
2483 if (missingSpans.count() == 0) { 2220 if (missingSpans.count() == 0) {
2484 debugValidate(); 2221 debugValidate();
2485 return true; 2222 return;
2486 } 2223 }
2487 debugValidate(); 2224 debugValidate();
2488 int missingCount = missingSpans.count(); 2225 int missingCount = missingSpans.count();
2489 for (int index = 0; index < missingCount; ++index) { 2226 for (int index = 0; index < missingCount; ++index) {
2490 MissingSpan& missing = missingSpans[index]; 2227 MissingSpan& missing = missingSpans[index];
2491 if (this != missing.fOther) { 2228 if (this != missing.fOther) {
2492 addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing .fPt); 2229 addTPair(missing.fT, missing.fOther, missing.fOtherT, false, missing .fPt);
2493 } 2230 }
2494 } 2231 }
2495 fixOtherTIndex(); 2232 fixOtherTIndex();
2496 // OPTIMIZATION: this may fix indices more than once. Build an array of uniq ue segments to 2233 // OPTIMIZATION: this may fix indices more than once. Build an array of uniq ue segments to
2497 // avoid this 2234 // avoid this
2498 for (int index = 0; index < missingCount; ++index) { 2235 for (int index = 0; index < missingCount; ++index) {
2499 missingSpans[index].fOther->fixOtherTIndex(); 2236 missingSpans[index].fOther->fixOtherTIndex();
2500 } 2237 }
2501 debugValidate(); 2238 debugValidate();
2502 return true;
2503 } 2239 }
2504 2240
2505 void SkOpSegment::checkLinks(const SkOpSpan* base, 2241 void SkOpSegment::checkLinks(const SkOpSpan* base,
2506 SkTArray<MissingSpan, true>* missingSpans) const { 2242 SkTArray<MissingSpan, true>* missingSpans) const {
2507 const SkOpSpan* first = fTs.begin(); 2243 const SkOpSpan* first = fTs.begin();
2508 const SkOpSpan* last = fTs.end() - 1; 2244 const SkOpSpan* last = fTs.end() - 1;
2509 SkASSERT(base >= first && last >= base); 2245 SkASSERT(base >= first && last >= base);
2510 const SkOpSegment* other = base->fOther; 2246 const SkOpSegment* other = base->fOther;
2511 const SkOpSpan* oFirst = other->fTs.begin(); 2247 const SkOpSpan* oFirst = other->fTs.begin();
2512 const SkOpSpan* oLast = other->fTs.end() - 1; 2248 const SkOpSpan* oLast = other->fTs.end() - 1;
2513 const SkOpSpan* oSpan = &other->fTs[base->fOtherIndex]; 2249 const SkOpSpan* oSpan = &other->fTs[base->fOtherIndex];
2514 const SkOpSpan* test = base; 2250 const SkOpSpan* test = base;
2515 const SkOpSpan* missing = NULL; 2251 const SkOpSpan* missing = NULL;
2516 while (test > first && (--test)->fPt == base->fPt) { 2252 while (test > first && (--test)->fPt == base->fPt) {
2517 if (this == test->fOther) { 2253 if (this == test->fOther) {
2518 continue; 2254 continue;
2519 } 2255 }
2520 CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans); 2256 CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
2521 } 2257 }
2522 test = base; 2258 test = base;
2523 while (test < last && (++test)->fPt == base->fPt) { 2259 while (test < last && (++test)->fPt == base->fPt) {
2524 SkASSERT(this != test->fOther || test->fLoop); 2260 SkASSERT(this != test->fOther);
2525 CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans); 2261 CheckOneLink(test, oSpan, oFirst, oLast, &missing, missingSpans);
2526 } 2262 }
2527 } 2263 }
2528 2264
2529 // see if spans with two or more intersections all agree on common t and point v alues 2265 // see if spans with two or more intersections all agree on common t and point v alues
2530 void SkOpSegment::checkMultiples() { 2266 void SkOpSegment::checkMultiples() {
2531 debugValidate(); 2267 debugValidate();
2532 int index; 2268 int index;
2533 int end = 0; 2269 int end = 0;
2534 while (fTs[++end].fT == 0) 2270 while (fTs[++end].fT == 0)
(...skipping 833 matching lines...) Expand 10 before | Expand all | Expand 10 after
3368 for (int index = 0; index < count; ++index) { 3104 for (int index = 0; index < count; ++index) {
3369 const SkOpSpan& span = fTs[index]; 3105 const SkOpSpan& span = fTs[index];
3370 if (span.fT == t && span.fOther == match) { 3106 if (span.fT == t && span.fOther == match) {
3371 return index; 3107 return index;
3372 } 3108 }
3373 } 3109 }
3374 SkASSERT(0); 3110 SkASSERT(0);
3375 return -1; 3111 return -1;
3376 } 3112 }
3377 3113
3378
3379
3380 int SkOpSegment::findOtherT(double t, const SkOpSegment* match) const { 3114 int SkOpSegment::findOtherT(double t, const SkOpSegment* match) const {
3381 int count = this->count(); 3115 int count = this->count();
3382 for (int index = 0; index < count; ++index) { 3116 for (int index = 0; index < count; ++index) {
3383 const SkOpSpan& span = fTs[index]; 3117 const SkOpSpan& span = fTs[index];
3384 if (span.fOtherT == t && span.fOther == match) { 3118 if (span.fOtherT == t && span.fOther == match) {
3385 return index; 3119 return index;
3386 } 3120 }
3387 } 3121 }
3388 return -1; 3122 return -1;
3389 } 3123 }
(...skipping 66 matching lines...) Expand 10 before | Expand all | Expand 10 after
3456 return NULL; // nothing to do 3190 return NULL; // nothing to do
3457 } 3191 }
3458 SkScalar top = SK_ScalarMax; 3192 SkScalar top = SK_ScalarMax;
3459 const SkOpAngle* firstAngle = NULL; 3193 const SkOpAngle* firstAngle = NULL;
3460 const SkOpAngle* angle = baseAngle; 3194 const SkOpAngle* angle = baseAngle;
3461 do { 3195 do {
3462 if (!angle->unorderable()) { 3196 if (!angle->unorderable()) {
3463 SkOpSegment* next = angle->segment(); 3197 SkOpSegment* next = angle->segment();
3464 SkPathOpsBounds bounds; 3198 SkPathOpsBounds bounds;
3465 next->subDivideBounds(angle->end(), angle->start(), &bounds); 3199 next->subDivideBounds(angle->end(), angle->start(), &bounds);
3466 bool nearSame = AlmostEqualUlps(top, bounds.top()); 3200 if (approximately_greater(top, bounds.fTop)) {
3467 bool lowerSector = !firstAngle || angle->sectorEnd() < firstAngle->s ectorStart();
3468 bool lesserSector = top > bounds.fTop;
3469 if (lesserSector && (!nearSame || lowerSector)) {
3470 top = bounds.fTop; 3201 top = bounds.fTop;
3471 firstAngle = angle; 3202 firstAngle = angle;
3472 } 3203 }
3473 } 3204 }
3474 angle = angle->next(); 3205 angle = angle->next();
3475 } while (angle != baseAngle); 3206 } while (angle != baseAngle);
3476 if (!firstAngle) { 3207 SkASSERT(firstAngle);
3477 return NULL; // if all are unorderable, give up
3478 }
3479 #if DEBUG_SORT 3208 #if DEBUG_SORT
3480 SkDebugf("%s\n", __FUNCTION__); 3209 SkDebugf("%s\n", __FUNCTION__);
3481 firstAngle->debugLoop(); 3210 firstAngle->debugLoop();
3482 #endif 3211 #endif
3483 // skip edges that have already been processed 3212 // skip edges that have already been processed
3484 angle = firstAngle; 3213 angle = firstAngle;
3485 SkOpSegment* leftSegment = NULL; 3214 SkOpSegment* leftSegment = NULL;
3486 bool looped = false; 3215 bool looped = false;
3487 do { 3216 do {
3488 *unsortable = angle->unorderable(); 3217 *unsortable = angle->unorderable();
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after
3565 for (int index = 0; index < count; ++index) { 3294 for (int index = 0; index < count; ++index) {
3566 const SkOpSpan& span = this->span(index); 3295 const SkOpSpan& span = this->span(index);
3567 if (span.fCoincident) { 3296 if (span.fCoincident) {
3568 foundEnds |= (span.fOther == other) << ((t > span.fT) + (t >= span.f T)); 3297 foundEnds |= (span.fOther == other) << ((t > span.fT) + (t >= span.f T));
3569 } 3298 }
3570 } 3299 }
3571 SkASSERT(foundEnds != 7); 3300 SkASSERT(foundEnds != 7);
3572 return foundEnds == 0x3 || foundEnds == 0x5 || foundEnds == 0x6; // two bit s set 3301 return foundEnds == 0x3 || foundEnds == 0x5 || foundEnds == 0x6; // two bit s set
3573 } 3302 }
3574 3303
3575 bool SkOpSegment::inconsistentAngle(int maxWinding, int sumWinding, int oppMaxWi nding,
3576 int oppSumWinding, const SkOpAngle* angle) const {
3577 SkASSERT(angle->segment() == this);
3578 if (UseInnerWinding(maxWinding, sumWinding)) {
3579 maxWinding = sumWinding;
3580 }
3581 if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumW inding)) {
3582 oppMaxWinding = oppSumWinding;
3583 }
3584 return inconsistentWinding(angle, maxWinding, oppMaxWinding);
3585 }
3586
3587 bool SkOpSegment::inconsistentWinding(const SkOpAngle* angle, int winding,
3588 int oppWinding) const {
3589 int index = angle->start();
3590 int endIndex = angle->end();
3591 int min = SkMin32(index, endIndex);
3592 int step = SkSign32(endIndex - index);
3593 if (inconsistentWinding(min, winding, oppWinding)) {
3594 return true;
3595 }
3596 const SkOpSegment* other = this;
3597 while ((other = other->nextChase(&index, &step, &min, NULL))) {
3598 if (other->fTs[min].fWindSum != SK_MinS32) {
3599 break;
3600 }
3601 if (fOperand == other->fOperand) {
3602 if (other->inconsistentWinding(min, winding, oppWinding)) {
3603 return true;
3604 }
3605 } else {
3606 if (other->inconsistentWinding(min, oppWinding, winding)) {
3607 return true;
3608 }
3609 }
3610 }
3611 return false;
3612 }
3613
3614 bool SkOpSegment::inconsistentWinding(int index, int winding, int oppWinding) co nst {
3615 SkASSERT(winding || oppWinding);
3616 double referenceT = this->span(index).fT;
3617 int lesser = index;
3618 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3619 if (inconsistentWinding(__FUNCTION__, lesser, winding, oppWinding)) {
3620 return true;
3621 }
3622 }
3623 do {
3624 if (inconsistentWinding(__FUNCTION__, index, winding, oppWinding)) {
3625 return true;
3626 }
3627 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenc eT));
3628 return false;
3629 }
3630
3631 bool SkOpSegment::inconsistentWinding(const char* funName, int tIndex, int windi ng,
3632 int oppWinding) const {
3633 const SkOpSpan& span = this->span(tIndex);
3634 if (span.fDone && !span.fSmall) {
3635 return false;
3636 }
3637 return (span.fWindSum != SK_MinS32 && span.fWindSum != winding)
3638 || (span.fOppSum != SK_MinS32 && span.fOppSum != oppWinding);
3639 }
3640
3641 void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, boo l evenOdd) { 3304 void SkOpSegment::init(const SkPoint pts[], SkPath::Verb verb, bool operand, boo l evenOdd) {
3642 fDoneSpans = 0; 3305 fDoneSpans = 0;
3643 fOperand = operand; 3306 fOperand = operand;
3644 fXor = evenOdd; 3307 fXor = evenOdd;
3645 fPts = pts; 3308 fPts = pts;
3646 fVerb = verb; 3309 fVerb = verb;
3647 fLoop = fMultiples = fSmall = fTiny = false; 3310 fLoop = fMultiples = fSmall = fTiny = false;
3648 } 3311 }
3649 3312
3650 void SkOpSegment::initWinding(int start, int end, SkOpAngle::IncludeType angleIn cludeType) { 3313 void SkOpSegment::initWinding(int start, int end, SkOpAngle::IncludeType angleIn cludeType) {
3651 int local = spanSign(start, end); 3314 int local = spanSign(start, end);
3652 SkDEBUGCODE(bool success);
3653 if (angleIncludeType == SkOpAngle::kBinarySingle) { 3315 if (angleIncludeType == SkOpAngle::kBinarySingle) {
3654 int oppLocal = oppSign(start, end); 3316 int oppLocal = oppSign(start, end);
3655 SkDEBUGCODE(success =) markAndChaseWinding(start, end, local, oppLocal, NULL); 3317 (void) markAndChaseWinding(start, end, local, oppLocal);
3656 // OPTIMIZATION: the reverse mark and chase could skip the first marking 3318 // OPTIMIZATION: the reverse mark and chase could skip the first marking
3657 SkDEBUGCODE(success |=) markAndChaseWinding(end, start, local, oppLocal, NULL); 3319 (void) markAndChaseWinding(end, start, local, oppLocal);
3658 } else { 3320 } else {
3659 SkDEBUGCODE(success =) markAndChaseWinding(start, end, local, NULL); 3321 (void) markAndChaseWinding(start, end, local);
3660 // OPTIMIZATION: the reverse mark and chase could skip the first marking 3322 // OPTIMIZATION: the reverse mark and chase could skip the first marking
3661 SkDEBUGCODE(success |=) markAndChaseWinding(end, start, local, NULL); 3323 (void) markAndChaseWinding(end, start, local);
3662 } 3324 }
3663 SkASSERT(success);
3664 } 3325 }
3665 3326
3666 /* 3327 /*
3667 when we start with a vertical intersect, we try to use the dx to determine if th e edge is to 3328 when we start with a vertical intersect, we try to use the dx to determine if th e edge is to
3668 the left or the right of vertical. This determines if we need to add the span's 3329 the left or the right of vertical. This determines if we need to add the span's
3669 sign or not. However, this isn't enough. 3330 sign or not. However, this isn't enough.
3670 If the supplied sign (winding) is zero, then we didn't hit another vertical span , so dx is needed. 3331 If the supplied sign (winding) is zero, then we didn't hit another vertical span , so dx is needed.
3671 If there was a winding, then it may or may not need adjusting. If the span the w inding was borrowed 3332 If there was a winding, then it may or may not need adjusting. If the span the w inding was borrowed
3672 from has the same x direction as this span, the winding should change. If the dx is opposite, then 3333 from has the same x direction as this span, the winding should change. If the dx is opposite, then
3673 the same winding is shared by both. 3334 the same winding is shared by both.
3674 */ 3335 */
3675 bool SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkSc alar hitDx, 3336 void SkOpSegment::initWinding(int start, int end, double tHit, int winding, SkSc alar hitDx,
3676 int oppWind, SkScalar hitOppDx) { 3337 int oppWind, SkScalar hitOppDx) {
3677 SkASSERT(hitDx || !winding); 3338 SkASSERT(hitDx || !winding);
3678 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX; 3339 SkScalar dx = (*CurveSlopeAtT[SkPathOpsVerbToPoints(fVerb)])(fPts, tHit).fX;
3679 SkASSERT(dx); 3340 SkASSERT(dx);
3680 int windVal = windValue(SkMin32(start, end)); 3341 int windVal = windValue(SkMin32(start, end));
3681 #if DEBUG_WINDING_AT_T 3342 #if DEBUG_WINDING_AT_T
3682 SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, d ebugID(), winding, 3343 SkDebugf("%s id=%d oldWinding=%d hitDx=%c dx=%c windVal=%d", __FUNCTION__, d ebugID(), winding,
3683 hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal); 3344 hitDx ? hitDx > 0 ? '+' : '-' : '0', dx > 0 ? '+' : '-', windVal);
3684 #endif 3345 #endif
3685 int sideWind = winding + (dx < 0 ? windVal : -windVal); 3346 int sideWind = winding + (dx < 0 ? windVal : -windVal);
3686 if (abs(winding) < abs(sideWind)) { 3347 if (abs(winding) < abs(sideWind)) {
3687 winding = sideWind; 3348 winding = sideWind;
3688 } 3349 }
3689 SkDEBUGCODE(int oppLocal = oppSign(start, end)); 3350 SkDEBUGCODE(int oppLocal = oppSign(start, end));
3690 SkASSERT(hitOppDx || !oppWind || !oppLocal); 3351 SkASSERT(hitOppDx || !oppWind || !oppLocal);
3691 int oppWindVal = oppValue(SkMin32(start, end)); 3352 int oppWindVal = oppValue(SkMin32(start, end));
3692 if (!oppWind) { 3353 if (!oppWind) {
3693 oppWind = dx < 0 ? oppWindVal : -oppWindVal; 3354 oppWind = dx < 0 ? oppWindVal : -oppWindVal;
3694 } else if (hitOppDx * dx >= 0) { 3355 } else if (hitOppDx * dx >= 0) {
3695 int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal); 3356 int oppSideWind = oppWind + (dx < 0 ? oppWindVal : -oppWindVal);
3696 if (abs(oppWind) < abs(oppSideWind)) { 3357 if (abs(oppWind) < abs(oppSideWind)) {
3697 oppWind = oppSideWind; 3358 oppWind = oppSideWind;
3698 } 3359 }
3699 } 3360 }
3700 #if DEBUG_WINDING_AT_T 3361 #if DEBUG_WINDING_AT_T
3701 SkDebugf(" winding=%d oppWind=%d\n", winding, oppWind); 3362 SkDebugf(" winding=%d oppWind=%d\n", winding, oppWind);
3702 #endif 3363 #endif
3703 // if this fails to mark (because the edges are too small) inform caller to try again 3364 (void) markAndChaseWinding(start, end, winding, oppWind);
3704 bool success = markAndChaseWinding(start, end, winding, oppWind, NULL);
3705 // OPTIMIZATION: the reverse mark and chase could skip the first marking 3365 // OPTIMIZATION: the reverse mark and chase could skip the first marking
3706 success |= markAndChaseWinding(end, start, winding, oppWind, NULL); 3366 (void) markAndChaseWinding(end, start, winding, oppWind);
3707 return success;
3708 } 3367 }
3709 3368
3710 bool SkOpSegment::inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPt r) const { 3369 bool SkOpSegment::inLoop(const SkOpAngle* baseAngle, int spanCount, int* indexPt r) const {
3711 if (!baseAngle->inLoop()) { 3370 if (!baseAngle->inLoop()) {
3712 return false; 3371 return false;
3713 } 3372 }
3714 int index = *indexPtr; 3373 int index = *indexPtr;
3715 SkOpAngle* from = fTs[index].fFromAngle; 3374 SkOpAngle* from = fTs[index].fFromAngle;
3716 SkOpAngle* to = fTs[index].fToAngle; 3375 SkOpAngle* to = fTs[index].fToAngle;
3717 while (++index < spanCount) { 3376 while (++index < spanCount) {
(...skipping 43 matching lines...) Expand 10 before | Expand all | Expand 10 after
3761 // if neither is a line, test for coincidence 3420 // if neither is a line, test for coincidence
3762 bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, const SkPoi nt& otherPt, 3421 bool SkOpSegment::joinCoincidence(SkOpSegment* other, double otherT, const SkPoi nt& otherPt,
3763 int step, bool cancel) { 3422 int step, bool cancel) {
3764 int otherTIndex = other->findT(otherT, otherPt, this); 3423 int otherTIndex = other->findT(otherT, otherPt, this);
3765 int next = other->nextExactSpan(otherTIndex, step); 3424 int next = other->nextExactSpan(otherTIndex, step);
3766 int otherMin = SkMin32(otherTIndex, next); 3425 int otherMin = SkMin32(otherTIndex, next);
3767 int otherWind = other->span(otherMin).fWindValue; 3426 int otherWind = other->span(otherMin).fWindValue;
3768 if (otherWind == 0) { 3427 if (otherWind == 0) {
3769 return false; 3428 return false;
3770 } 3429 }
3771 if (next < 0) { 3430 SkASSERT(next >= 0);
3772 return false; // can happen if t values were adjusted but coincident ts were not
3773 }
3774 int tIndex = 0; 3431 int tIndex = 0;
3775 do { 3432 do {
3776 SkOpSpan* test = &fTs[tIndex]; 3433 SkOpSpan* test = &fTs[tIndex];
3777 SkASSERT(test->fT == 0); 3434 SkASSERT(test->fT == 0);
3778 if (test->fOther == other || test->fOtherT != 1) { 3435 if (test->fOther == other || test->fOtherT != 1) {
3779 continue; 3436 continue;
3780 } 3437 }
3781 SkPoint startPt, endPt; 3438 SkPoint startPt, endPt;
3782 double endT; 3439 double endT;
3783 if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) { 3440 if (findCoincidentMatch(test, other, otherTIndex, next, step, &startPt, &endPt, &endT)) {
3784 SkOpSegment* match = test->fOther; 3441 SkOpSegment* match = test->fOther;
3785 if (cancel) { 3442 if (cancel) {
3786 match->addTCancel(startPt, endPt, other); 3443 match->addTCancel(startPt, endPt, other);
3787 } else { 3444 } else {
3788 if (!match->addTCoincident(startPt, endPt, endT, other)) { 3445 SkAssertResult(match->addTCoincident(startPt, endPt, endT, other ));
3789 return false;
3790 }
3791 } 3446 }
3792 return true; 3447 return true;
3793 } 3448 }
3794 } while (fTs[++tIndex].fT == 0); 3449 } while (fTs[++tIndex].fT == 0);
3795 return false; 3450 return false;
3796 } 3451 }
3797 3452
3798 // this span is excluded by the winding rule -- chase the ends 3453 // this span is excluded by the winding rule -- chase the ends
3799 // as long as they are unambiguous to mark connections as done 3454 // as long as they are unambiguous to mark connections as done
3800 // and give them the same winding value 3455 // and give them the same winding value
(...skipping 23 matching lines...) Expand all
3824 while ((other = other->nextChase(&index, &step, &min, &last))) { 3479 while ((other = other->nextChase(&index, &step, &min, &last))) {
3825 if (other->done()) { 3480 if (other->done()) {
3826 SkASSERT(!last); 3481 SkASSERT(!last);
3827 break; 3482 break;
3828 } 3483 }
3829 other->markDoneUnary(min); 3484 other->markDoneUnary(min);
3830 } 3485 }
3831 return last; 3486 return last;
3832 } 3487 }
3833 3488
3834 bool SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, SkOpS pan** lastPtr) { 3489 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding) {
3835 int index = angle->start(); 3490 int index = angle->start();
3836 int endIndex = angle->end(); 3491 int endIndex = angle->end();
3837 return markAndChaseWinding(index, endIndex, winding, lastPtr); 3492 int step = SkSign32(endIndex - index);
3838 }
3839
3840 bool SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, SkOp Span** lastPtr) {
3841 int min = SkMin32(index, endIndex); 3493 int min = SkMin32(index, endIndex);
3842 int step = SkSign32(endIndex - index); 3494 markWinding(min, winding);
3843 bool success = markWinding(min, winding);
3844 SkOpSpan* last = NULL; 3495 SkOpSpan* last = NULL;
3845 SkOpSegment* other = this; 3496 SkOpSegment* other = this;
3846 while ((other = other->nextChase(&index, &step, &min, &last))) { 3497 while ((other = other->nextChase(&index, &step, &min, &last))) {
3498 if (other->fTs[min].fWindSum != SK_MinS32) {
3499 // SkASSERT(other->fTs[min].fWindSum == winding);
3500 SkASSERT(!last);
3501 break;
3502 }
3503 other->markWinding(min, winding);
3504 }
3505 return last;
3506 }
3507
3508 SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding) {
3509 int min = SkMin32(index, endIndex);
3510 int step = SkSign32(endIndex - index);
3511 markWinding(min, winding);
3512 SkOpSpan* last = NULL;
3513 SkOpSegment* other = this;
3514 while ((other = other->nextChase(&index, &step, &min, &last))) {
3847 if (other->fTs[min].fWindSum != SK_MinS32) { 3515 if (other->fTs[min].fWindSum != SK_MinS32) {
3848 SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoo p); 3516 SkASSERT(other->fTs[min].fWindSum == winding || other->fTs[min].fLoo p);
3849 SkASSERT(!last); 3517 SkASSERT(!last);
3850 break; 3518 break;
3851 } 3519 }
3852 (void) other->markWinding(min, winding); 3520 other->markWinding(min, winding);
3853 } 3521 }
3854 if (lastPtr) { 3522 return last;
3855 *lastPtr = last;
3856 }
3857 return success;
3858 } 3523 }
3859 3524
3860 bool SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding, 3525 SkOpSpan* SkOpSegment::markAndChaseWinding(int index, int endIndex, int winding, int oppWinding) {
3861 SkOpSpan** lastPtr) {
3862 int min = SkMin32(index, endIndex); 3526 int min = SkMin32(index, endIndex);
3863 int step = SkSign32(endIndex - index); 3527 int step = SkSign32(endIndex - index);
3864 bool success = markWinding(min, winding, oppWinding); 3528 markWinding(min, winding, oppWinding);
3865 SkOpSpan* last = NULL; 3529 SkOpSpan* last = NULL;
3866 SkOpSegment* other = this; 3530 SkOpSegment* other = this;
3867 while ((other = other->nextChase(&index, &step, &min, &last))) { 3531 while ((other = other->nextChase(&index, &step, &min, &last))) {
3868 if (other->fTs[min].fWindSum != SK_MinS32) { 3532 if (other->fTs[min].fWindSum != SK_MinS32) {
3869 #ifdef SK_DEBUG 3533 #ifdef SK_DEBUG
3870 if (!other->fTs[min].fLoop) { 3534 if (!other->fTs[min].fLoop) {
3871 if (fOperand == other->fOperand) { 3535 if (fOperand == other->fOperand) {
3872 // FIXME: this is probably a bug -- rects4 asserts here 3536 // FIXME: this is probably a bug -- rects4 asserts here
3873 // SkASSERT(other->fTs[min].fWindSum == winding); 3537 // SkASSERT(other->fTs[min].fWindSum == winding);
3874 // FIXME: this is probably a bug -- rects3 asserts here 3538 // FIXME: this is probably a bug -- rects3 asserts here
3875 // SkASSERT(other->fTs[min].fOppSum == oppWinding); 3539 // SkASSERT(other->fTs[min].fOppSum == oppWinding);
3876 } else { 3540 } else {
3877 // FIXME: this is probably a bug -- issue414409b asserts here 3541 // FIXME: this is probably a bug -- issue414409b asserts here
3878 // SkASSERT(other->fTs[min].fWindSum == oppWinding); 3542 // SkASSERT(other->fTs[min].fWindSum == oppWinding);
3879 // FIXME: this is probably a bug -- skpwww_joomla_org_23 asserts here 3543 // FIXME: this is probably a bug -- skpwww_joomla_org_23 asserts here
3880 // SkASSERT(other->fTs[min].fOppSum == winding); 3544 // SkASSERT(other->fTs[min].fOppSum == winding);
3881 } 3545 }
3882 } 3546 }
3883 SkASSERT(!last); 3547 SkASSERT(!last);
3884 #endif 3548 #endif
3885 break; 3549 break;
3886 } 3550 }
3887 if (fOperand == other->fOperand) { 3551 if (fOperand == other->fOperand) {
3888 (void) other->markWinding(min, winding, oppWinding); 3552 other->markWinding(min, winding, oppWinding);
3889 } else { 3553 } else {
3890 (void) other->markWinding(min, oppWinding, winding); 3554 other->markWinding(min, oppWinding, winding);
3891 } 3555 }
3892 } 3556 }
3893 if (lastPtr) { 3557 return last;
3894 *lastPtr = last;
3895 }
3896 return success;
3897 } 3558 }
3898 3559
3899 bool SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int o ppWinding, 3560 SkOpSpan* SkOpSegment::markAndChaseWinding(const SkOpAngle* angle, int winding, int oppWinding) {
3900 SkOpSpan** lastPtr) {
3901 int start = angle->start(); 3561 int start = angle->start();
3902 int end = angle->end(); 3562 int end = angle->end();
3903 return markAndChaseWinding(start, end, winding, oppWinding, lastPtr); 3563 return markAndChaseWinding(start, end, winding, oppWinding);
3904 } 3564 }
3905 3565
3906 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle * angle) { 3566 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, const SkOpAngle * angle) {
3907 SkASSERT(angle->segment() == this); 3567 SkASSERT(angle->segment() == this);
3908 if (UseInnerWinding(maxWinding, sumWinding)) { 3568 if (UseInnerWinding(maxWinding, sumWinding)) {
3909 maxWinding = sumWinding; 3569 maxWinding = sumWinding;
3910 } 3570 }
3911 SkOpSpan* last; 3571 SkOpSpan* last = markAndChaseWinding(angle, maxWinding);
3912 SkAssertResult(markAndChaseWinding(angle, maxWinding, &last));
3913 #if DEBUG_WINDING 3572 #if DEBUG_WINDING
3914 if (last) { 3573 if (last) {
3915 SkDebugf("%s last id=%d windSum=", __FUNCTION__, 3574 SkDebugf("%s last id=%d windSum=", __FUNCTION__,
3916 last->fOther->fTs[last->fOtherIndex].fOther->debugID()); 3575 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
3917 SkPathOpsDebug::WindingPrintf(last->fWindSum); 3576 SkPathOpsDebug::WindingPrintf(last->fWindSum);
3918 SkDebugf(" small=%d\n", last->fSmall); 3577 SkDebugf(" small=%d\n", last->fSmall);
3919 } 3578 }
3920 #endif 3579 #endif
3921 return last; 3580 return last;
3922 } 3581 }
3923 3582
3924 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWindi ng, 3583 SkOpSpan* SkOpSegment::markAngle(int maxWinding, int sumWinding, int oppMaxWindi ng,
3925 int oppSumWinding, const SkOpAngle* angle) { 3584 int oppSumWinding, const SkOpAngle* angle) {
3926 SkASSERT(angle->segment() == this); 3585 SkASSERT(angle->segment() == this);
3927 if (UseInnerWinding(maxWinding, sumWinding)) { 3586 if (UseInnerWinding(maxWinding, sumWinding)) {
3928 maxWinding = sumWinding; 3587 maxWinding = sumWinding;
3929 } 3588 }
3930 if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumW inding)) { 3589 if (oppMaxWinding != oppSumWinding && UseInnerWinding(oppMaxWinding, oppSumW inding)) {
3931 oppMaxWinding = oppSumWinding; 3590 oppMaxWinding = oppSumWinding;
3932 } 3591 }
3933 SkOpSpan* last; 3592 SkOpSpan* last = markAndChaseWinding(angle, maxWinding, oppMaxWinding);
3934 // caller doesn't require that this marks anything
3935 (void) markAndChaseWinding(angle, maxWinding, oppMaxWinding, &last);
3936 #if DEBUG_WINDING 3593 #if DEBUG_WINDING
3937 if (last) { 3594 if (last) {
3938 SkDebugf("%s last id=%d windSum=", __FUNCTION__, 3595 SkDebugf("%s last id=%d windSum=", __FUNCTION__,
3939 last->fOther->fTs[last->fOtherIndex].fOther->debugID()); 3596 last->fOther->fTs[last->fOtherIndex].fOther->debugID());
3940 SkPathOpsDebug::WindingPrintf(last->fWindSum); 3597 SkPathOpsDebug::WindingPrintf(last->fWindSum);
3941 SkDebugf(" small=%d\n", last->fSmall); 3598 SkDebugf(" small=%d\n", last->fSmall);
3942 } 3599 }
3943 #endif 3600 #endif
3944 return last; 3601 return last;
3945 } 3602 }
(...skipping 22 matching lines...) Expand all
3968 int lesser = index; 3625 int lesser = index;
3969 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3626 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3970 markOneDoneBinary(__FUNCTION__, lesser); 3627 markOneDoneBinary(__FUNCTION__, lesser);
3971 } 3628 }
3972 do { 3629 do {
3973 markOneDoneBinary(__FUNCTION__, index); 3630 markOneDoneBinary(__FUNCTION__, index);
3974 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referen ceT)); 3631 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referen ceT));
3975 debugValidate(); 3632 debugValidate();
3976 } 3633 }
3977 3634
3978 void SkOpSegment::markDoneFinal(int index) {
3979 double referenceT = fTs[index].fT;
3980 int lesser = index;
3981 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3982 markOneDoneFinal(__FUNCTION__, lesser);
3983 }
3984 do {
3985 markOneDoneFinal(__FUNCTION__, index);
3986 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referen ceT));
3987 debugValidate();
3988 }
3989
3990 void SkOpSegment::markDoneUnary(int index) { 3635 void SkOpSegment::markDoneUnary(int index) {
3991 double referenceT = fTs[index].fT; 3636 double referenceT = fTs[index].fT;
3992 int lesser = index; 3637 int lesser = index;
3993 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3638 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
3994 markOneDoneUnary(__FUNCTION__, lesser); 3639 markOneDoneUnary(__FUNCTION__, lesser);
3995 } 3640 }
3996 do { 3641 do {
3997 markOneDoneUnary(__FUNCTION__, index); 3642 markOneDoneUnary(__FUNCTION__, index);
3998 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referen ceT)); 3643 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referen ceT));
3999 debugValidate(); 3644 debugValidate();
4000 } 3645 }
4001 3646
4002 void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) { 3647 void SkOpSegment::markOneDone(const char* funName, int tIndex, int winding) {
4003 SkOpSpan* span; 3648 SkOpSpan* span = markOneWinding(funName, tIndex, winding);
4004 (void) markOneWinding(funName, tIndex, winding, &span); // allowed to do no thing 3649 if (!span || span->fDone) {
4005 if (span->fDone) {
4006 return; 3650 return;
4007 } 3651 }
4008 span->fDone = true; 3652 span->fDone = true;
4009 ++fDoneSpans; 3653 fDoneSpans++;
4010 }
4011
4012 void SkOpSegment::markOneDoneFinal(const char* funName, int tIndex) {
4013 SkOpSpan* span = &fTs[tIndex];
4014 if (span->fDone) {
4015 return;
4016 }
4017 span->fDone = true;
4018 ++fDoneSpans;
4019 } 3654 }
4020 3655
4021 void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) { 3656 void SkOpSegment::markOneDoneBinary(const char* funName, int tIndex) {
4022 SkOpSpan* span = verifyOneWinding(funName, tIndex); 3657 SkOpSpan* span = verifyOneWinding(funName, tIndex);
4023 if (!span) { 3658 if (!span) {
4024 return; 3659 return;
4025 } 3660 }
4026 SkASSERT(!span->fDone); 3661 SkASSERT(!span->fDone);
4027 span->fDone = true; 3662 span->fDone = true;
4028 ++fDoneSpans; 3663 fDoneSpans++;
4029 } 3664 }
4030 3665
4031 void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) { 3666 void SkOpSegment::markOneDoneUnary(const char* funName, int tIndex) {
4032 SkOpSpan* span = verifyOneWindingU(funName, tIndex); 3667 SkOpSpan* span = verifyOneWindingU(funName, tIndex);
4033 if (!span) { 3668 if (!span) {
4034 return; 3669 return;
4035 } 3670 }
4036 if (span->fWindSum == SK_MinS32) { 3671 if (span->fWindSum == SK_MinS32) {
4037 SkDebugf("%s uncomputed\n", __FUNCTION__); 3672 SkDebugf("%s uncomputed\n", __FUNCTION__);
4038 } 3673 }
4039 SkASSERT(!span->fDone); 3674 SkASSERT(!span->fDone);
4040 span->fDone = true; 3675 span->fDone = true;
4041 ++fDoneSpans; 3676 fDoneSpans++;
4042 } 3677 }
4043 3678
4044 bool SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding, S kOpSpan** lastPtr) { 3679 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int windi ng) {
4045 SkOpSpan* span = &fTs[tIndex]; 3680 SkOpSpan& span = fTs[tIndex];
4046 if (lastPtr) { 3681 if (span.fDone && !span.fSmall) {
4047 *lastPtr = span; 3682 return NULL;
4048 }
4049 if (span->fDone && !span->fSmall) {
4050 return false;
4051 } 3683 }
4052 #if DEBUG_MARK_DONE 3684 #if DEBUG_MARK_DONE
4053 debugShowNewWinding(funName, *span, winding); 3685 debugShowNewWinding(funName, span, winding);
4054 #endif 3686 #endif
4055 SkASSERT(span->fWindSum == SK_MinS32 || span->fWindSum == winding); 3687 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
4056 #if DEBUG_LIMIT_WIND_SUM 3688 #if DEBUG_LIMIT_WIND_SUM
4057 SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM); 3689 SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
4058 #endif 3690 #endif
4059 span->fWindSum = winding; 3691 span.fWindSum = winding;
4060 return true; 3692 return &span;
4061 } 3693 }
4062 3694
4063 bool SkOpSegment::markOneWinding(const char* funName, int tIndex, int winding, 3695 SkOpSpan* SkOpSegment::markOneWinding(const char* funName, int tIndex, int windi ng,
4064 int oppWinding, SkOpSpan** lastPtr) { 3696 int oppWinding) {
4065 SkOpSpan* span = &fTs[tIndex]; 3697 SkOpSpan& span = fTs[tIndex];
4066 if (span->fDone && !span->fSmall) { 3698 if (span.fDone && !span.fSmall) {
4067 return false; 3699 return NULL;
4068 } 3700 }
4069 #if DEBUG_MARK_DONE 3701 #if DEBUG_MARK_DONE
4070 debugShowNewWinding(funName, *span, winding, oppWinding); 3702 debugShowNewWinding(funName, span, winding, oppWinding);
4071 #endif 3703 #endif
4072 SkASSERT(span->fWindSum == SK_MinS32 || span->fWindSum == winding); 3704 SkASSERT(span.fWindSum == SK_MinS32 || span.fWindSum == winding);
4073 #if DEBUG_LIMIT_WIND_SUM 3705 #if DEBUG_LIMIT_WIND_SUM
4074 SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM); 3706 SkASSERT(abs(winding) <= DEBUG_LIMIT_WIND_SUM);
4075 #endif 3707 #endif
4076 span->fWindSum = winding; 3708 span.fWindSum = winding;
4077 SkASSERT(span->fOppSum == SK_MinS32 || span->fOppSum == oppWinding); 3709 SkASSERT(span.fOppSum == SK_MinS32 || span.fOppSum == oppWinding);
4078 #if DEBUG_LIMIT_WIND_SUM 3710 #if DEBUG_LIMIT_WIND_SUM
4079 SkASSERT(abs(oppWinding) <= DEBUG_LIMIT_WIND_SUM); 3711 SkASSERT(abs(oppWinding) <= DEBUG_LIMIT_WIND_SUM);
4080 #endif 3712 #endif
4081 span->fOppSum = oppWinding; 3713 span.fOppSum = oppWinding;
4082 debugValidate(); 3714 debugValidate();
4083 if (lastPtr) { 3715 return &span;
4084 *lastPtr = span;
4085 }
4086 return true;
4087 } 3716 }
4088 3717
4089 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of -polygon-points-are-in-clockwise-order 3718 // from http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of -polygon-points-are-in-clockwise-order
4090 bool SkOpSegment::clockwise(int tStart, int tEnd, bool* swap) const { 3719 bool SkOpSegment::clockwise(int tStart, int tEnd, bool* swap) const {
4091 SkASSERT(fVerb != SkPath::kLine_Verb); 3720 SkASSERT(fVerb != SkPath::kLine_Verb);
4092 SkPoint edge[4]; 3721 SkPoint edge[4];
4093 subDivide(tStart, tEnd, edge); 3722 subDivide(tStart, tEnd, edge);
4094 int points = SkPathOpsVerbToPoints(fVerb); 3723 int points = SkPathOpsVerbToPoints(fVerb);
4095 double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY) ; 3724 double sum = (edge[0].fX - edge[points].fX) * (edge[0].fY + edge[points].fY) ;
4096 bool sumSet = false; 3725 bool sumSet = false;
(...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after
4200 debugShowNewWinding(funName, span, span.fWindSum); 3829 debugShowNewWinding(funName, span, span.fWindSum);
4201 #endif 3830 #endif
4202 // If the prior angle in the sort is unorderable, the winding sum may not be com putable. 3831 // If the prior angle in the sort is unorderable, the winding sum may not be com putable.
4203 // To enable the assert, the 'prior is unorderable' state could be 3832 // To enable the assert, the 'prior is unorderable' state could be
4204 // piped down to this test, but not sure it's worth it. 3833 // piped down to this test, but not sure it's worth it.
4205 // (Once the sort order is stored in the span, this test may be feasible.) 3834 // (Once the sort order is stored in the span, this test may be feasible.)
4206 // SkASSERT(span.fWindSum != SK_MinS32); 3835 // SkASSERT(span.fWindSum != SK_MinS32);
4207 return &span; 3836 return &span;
4208 } 3837 }
4209 3838
4210 bool SkOpSegment::markWinding(int index, int winding) { 3839 void SkOpSegment::markWinding(int index, int winding) {
4211 // SkASSERT(!done()); 3840 // SkASSERT(!done());
4212 SkASSERT(winding); 3841 SkASSERT(winding);
4213 double referenceT = fTs[index].fT; 3842 double referenceT = fTs[index].fT;
4214 int lesser = index; 3843 int lesser = index;
4215 bool success = false;
4216 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3844 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
4217 success |= markOneWinding(__FUNCTION__, lesser, winding, NULL); 3845 markOneWinding(__FUNCTION__, lesser, winding);
4218 } 3846 }
4219 do { 3847 do {
4220 success |= markOneWinding(__FUNCTION__, index, winding, NULL); 3848 markOneWinding(__FUNCTION__, index, winding);
4221 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenc eT)); 3849 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenc eT));
4222 debugValidate(); 3850 debugValidate();
4223 return success;
4224 } 3851 }
4225 3852
4226 bool SkOpSegment::markWinding(int index, int winding, int oppWinding) { 3853 void SkOpSegment::markWinding(int index, int winding, int oppWinding) {
4227 // SkASSERT(!done()); 3854 // SkASSERT(!done());
4228 SkASSERT(winding || oppWinding); 3855 SkASSERT(winding || oppWinding);
4229 double referenceT = fTs[index].fT; 3856 double referenceT = fTs[index].fT;
4230 int lesser = index; 3857 int lesser = index;
4231 bool success = false;
4232 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) { 3858 while (--lesser >= 0 && precisely_negative(referenceT - fTs[lesser].fT)) {
4233 success |= markOneWinding(__FUNCTION__, lesser, winding, oppWinding, NUL L); 3859 markOneWinding(__FUNCTION__, lesser, winding, oppWinding);
4234 } 3860 }
4235 do { 3861 do {
4236 success |= markOneWinding(__FUNCTION__, index, winding, oppWinding, NULL ); 3862 markOneWinding(__FUNCTION__, index, winding, oppWinding);
4237 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenc eT)); 3863 } while (++index < fTs.count() && precisely_negative(fTs[index].fT - referenc eT));
4238 debugValidate(); 3864 debugValidate();
4239 return success;
4240 } 3865 }
4241 3866
4242 void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) { 3867 void SkOpSegment::matchWindingValue(int tIndex, double t, bool borrowWind) {
4243 int nextDoorWind = SK_MaxS32; 3868 int nextDoorWind = SK_MaxS32;
4244 int nextOppWind = SK_MaxS32; 3869 int nextOppWind = SK_MaxS32;
4245 // prefer exact matches 3870 // prefer exact matches
4246 if (tIndex > 0) { 3871 if (tIndex > 0) {
4247 const SkOpSpan& below = fTs[tIndex - 1]; 3872 const SkOpSpan& below = fTs[tIndex - 1];
4248 if (below.fT == t) { 3873 if (below.fT == t) {
4249 nextDoorWind = below.fWindValue; 3874 nextDoorWind = below.fWindValue;
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after
4292 if (fTs[*end].fT == 1) { 3917 if (fTs[*end].fT == 1) {
4293 return false; 3918 return false;
4294 } 3919 }
4295 ++(*end); 3920 ++(*end);
4296 } 3921 }
4297 *start = *end; 3922 *start = *end;
4298 *end = nextExactSpan(*start, 1); 3923 *end = nextExactSpan(*start, 1);
4299 return true; 3924 return true;
4300 } 3925 }
4301 3926
4302 static SkOpSegment* set_last(SkOpSpan** last, const SkOpSpan* endSpan) { 3927 static SkOpSegment* set_last(SkOpSpan** last, SkOpSpan* endSpan) {
4303 if (last && !endSpan->fSmall) { 3928 if (last && !endSpan->fSmall) {
4304 *last = const_cast<SkOpSpan*>(endSpan); // FIXME: get rid of cast 3929 *last = endSpan;
4305 } 3930 }
4306 return NULL; 3931 return NULL;
4307 } 3932 }
4308 3933
4309 SkOpSegment* SkOpSegment::nextChase(int* indexPtr, int* stepPtr, int* minPtr, 3934 SkOpSegment* SkOpSegment::nextChase(int* indexPtr, int* stepPtr, int* minPtr, Sk OpSpan** last) {
4310 SkOpSpan** last) const {
4311 int origIndex = *indexPtr; 3935 int origIndex = *indexPtr;
4312 int step = *stepPtr; 3936 int step = *stepPtr;
4313 int end = nextExactSpan(origIndex, step); 3937 int end = nextExactSpan(origIndex, step);
4314 SkASSERT(end >= 0); 3938 SkASSERT(end >= 0);
4315 const SkOpSpan& endSpan = this->span(end); 3939 SkOpSpan& endSpan = fTs[end];
4316 SkOpAngle* angle = step > 0 ? endSpan.fFromAngle : endSpan.fToAngle; 3940 SkOpAngle* angle = step > 0 ? endSpan.fFromAngle : endSpan.fToAngle;
4317 int foundIndex; 3941 int foundIndex;
4318 int otherEnd; 3942 int otherEnd;
4319 SkOpSegment* other; 3943 SkOpSegment* other;
4320 if (angle == NULL) { 3944 if (angle == NULL) {
4321 if (endSpan.fT != 0 && endSpan.fT != 1) { 3945 if (endSpan.fT != 0 && endSpan.fT != 1) {
4322 return NULL; 3946 return NULL;
4323 } 3947 }
4324 other = endSpan.fOther; 3948 other = endSpan.fOther;
4325 foundIndex = endSpan.fOtherIndex; 3949 foundIndex = endSpan.fOtherIndex;
(...skipping 505 matching lines...) Expand 10 before | Expand all | Expand 10 after
4831 SkASSERT(span->fWindValue > 0 || span->fOppValue != 0); 4455 SkASSERT(span->fWindValue > 0 || span->fOppValue != 0);
4832 span->fWindValue = 0; 4456 span->fWindValue = 0;
4833 span->fOppValue = 0; 4457 span->fOppValue = 0;
4834 if (span->fTiny || span->fSmall) { 4458 if (span->fTiny || span->fSmall) {
4835 return; 4459 return;
4836 } 4460 }
4837 SkASSERT(!span->fDone); 4461 SkASSERT(!span->fDone);
4838 span->fDone = true; 4462 span->fDone = true;
4839 ++fDoneSpans; 4463 ++fDoneSpans;
4840 } 4464 }
OLDNEW
« no previous file with comments | « src/pathops/SkOpSegment.h ('k') | src/pathops/SkPathOpsCommon.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698