OLD | NEW |
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 "SkOpCoincidence.h" | 7 #include "SkOpCoincidence.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 141 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
152 | 152 |
153 bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sum
Winding) { | 153 bool SkOpSegment::activeWinding(SkOpSpanBase* start, SkOpSpanBase* end, int* sum
Winding) { |
154 int maxWinding; | 154 int maxWinding; |
155 setUpWinding(start, end, &maxWinding, sumWinding); | 155 setUpWinding(start, end, &maxWinding, sumWinding); |
156 bool from = maxWinding != 0; | 156 bool from = maxWinding != 0; |
157 bool to = *sumWinding != 0; | 157 bool to = *sumWinding != 0; |
158 bool result = gUnaryActiveEdge[from][to]; | 158 bool result = gUnaryActiveEdge[from][to]; |
159 return result; | 159 return result; |
160 } | 160 } |
161 | 161 |
| 162 void SkOpSegment::addAlignIntersection(SkOpPtT& endPtT, SkPoint& oldPt, |
| 163 SkOpContourHead* contourList, SkChunkAlloc* allocator) { |
| 164 const SkPoint& newPt = endPtT.fPt; |
| 165 if (newPt == oldPt) { |
| 166 return; |
| 167 } |
| 168 SkPoint line[2] = { newPt, oldPt }; |
| 169 SkPathOpsBounds lineBounds; |
| 170 lineBounds.setBounds(line, 2); |
| 171 SkDLine aLine; |
| 172 aLine.set(line); |
| 173 SkOpContour* current = contourList; |
| 174 do { |
| 175 if (!SkPathOpsBounds::Intersects(current->bounds(), lineBounds)) { |
| 176 continue; |
| 177 } |
| 178 SkOpSegment* segment = current->first(); |
| 179 do { |
| 180 if (!SkPathOpsBounds::Intersects(segment->bounds(), lineBounds)) { |
| 181 continue; |
| 182 } |
| 183 if (newPt == segment->fPts[0]) { |
| 184 continue; |
| 185 } |
| 186 if (newPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { |
| 187 continue; |
| 188 } |
| 189 if (oldPt == segment->fPts[0]) { |
| 190 continue; |
| 191 } |
| 192 if (oldPt == segment->fPts[SkPathOpsVerbToPoints(segment->fVerb)]) { |
| 193 continue; |
| 194 } |
| 195 if (endPtT.contains(segment)) { |
| 196 continue; |
| 197 } |
| 198 SkIntersections i; |
| 199 switch (segment->fVerb) { |
| 200 case SkPath::kLine_Verb: { |
| 201 SkDLine bLine; |
| 202 bLine.set(segment->fPts); |
| 203 i.intersect(bLine, aLine); |
| 204 } break; |
| 205 case SkPath::kQuad_Verb: { |
| 206 SkDQuad bQuad; |
| 207 bQuad.set(segment->fPts); |
| 208 i.intersect(bQuad, aLine); |
| 209 } break; |
| 210 case SkPath::kConic_Verb: { |
| 211 SkDConic bConic; |
| 212 bConic.set(segment->fPts, segment->fWeight); |
| 213 i.intersect(bConic, aLine); |
| 214 } break; |
| 215 case SkPath::kCubic_Verb: { |
| 216 SkDCubic bCubic; |
| 217 bCubic.set(segment->fPts); |
| 218 i.intersect(bCubic, aLine); |
| 219 } break; |
| 220 default: |
| 221 SkASSERT(0); |
| 222 } |
| 223 if (i.used()) { |
| 224 SkASSERT(i.used() == 1); |
| 225 SkASSERT(!zero_or_one(i[0][0])); |
| 226 SkOpSpanBase* checkSpan = fHead.next(); |
| 227 while (!checkSpan->final()) { |
| 228 if (checkSpan->contains(segment)) { |
| 229 goto nextSegment; |
| 230 } |
| 231 checkSpan = checkSpan->upCast()->next(); |
| 232 } |
| 233 SkOpPtT* ptT = segment->addT(i[0][0], SkOpSegment::kAllowAlias,
allocator); |
| 234 ptT->fPt = newPt; |
| 235 endPtT.addOpp(ptT); |
| 236 } |
| 237 nextSegment: |
| 238 ; |
| 239 } while ((segment = segment->next())); |
| 240 } while ((current = current->next())); |
| 241 } |
| 242 |
162 void SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, | 243 void SkOpSegment::addCurveTo(const SkOpSpanBase* start, const SkOpSpanBase* end, |
163 SkPathWriter* path, bool active) const { | 244 SkPathWriter* path, bool active) const { |
164 SkOpCurve edge; | 245 SkOpCurve edge; |
165 const SkPoint* ePtr; | 246 const SkPoint* ePtr; |
166 SkScalar eWeight; | 247 SkScalar eWeight; |
167 if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead)
) { | 248 if ((start == &fHead && end == &fTail) || (start == &fTail && end == &fHead)
) { |
168 ePtr = fPts; | 249 ePtr = fPts; |
169 eWeight = fWeight; | 250 eWeight = fWeight; |
170 } else { | 251 } else { |
171 // OPTIMIZE? if not active, skip remainder and return xyAtT(end) | 252 // OPTIMIZE? if not active, skip remainder and return xyAtT(end) |
(...skipping 591 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
763 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->pre
v(); | 844 *nextEnd = step > 0 ? (*nextStart)->upCast()->next() : (*nextStart)->pre
v(); |
764 return other; | 845 return other; |
765 } | 846 } |
766 SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next(
) \ | 847 SkDEBUGCODE(SkOpSpanBase* endNear = step > 0 ? (*nextStart)->upCast()->next(
) \ |
767 : (*nextStart)->prev()); | 848 : (*nextStart)->prev()); |
768 SkASSERT(endNear == end); // is this ever not end? | 849 SkASSERT(endNear == end); // is this ever not end? |
769 SkASSERT(endNear); | 850 SkASSERT(endNear); |
770 SkASSERT(start != endNear); | 851 SkASSERT(start != endNear); |
771 SkASSERT((start->t() < endNear->t()) ^ (step < 0)); | 852 SkASSERT((start->t() < endNear->t()) ^ (step < 0)); |
772 SkOpAngle* angle = this->spanToAngle(end, start); | 853 SkOpAngle* angle = this->spanToAngle(end, start); |
773 if (angle->unorderable()) { | 854 if (!angle || angle->unorderable()) { |
774 *unsortable = true; | 855 *unsortable = true; |
775 markDone(start->starter(end)); | 856 markDone(start->starter(end)); |
776 return NULL; | 857 return NULL; |
777 } | 858 } |
778 #if DEBUG_SORT | 859 #if DEBUG_SORT |
779 SkDebugf("%s\n", __FUNCTION__); | 860 SkDebugf("%s\n", __FUNCTION__); |
780 angle->debugLoop(); | 861 angle->debugLoop(); |
781 #endif | 862 #endif |
782 SkOpAngle* nextAngle = angle->next(); | 863 SkOpAngle* nextAngle = angle->next(); |
783 const SkOpAngle* foundAngle = NULL; | 864 const SkOpAngle* foundAngle = NULL; |
(...skipping 26 matching lines...) Expand all Loading... |
810 return nextSegment; | 891 return nextSegment; |
811 } | 892 } |
812 | 893 |
813 SkOpGlobalState* SkOpSegment::globalState() const { | 894 SkOpGlobalState* SkOpSegment::globalState() const { |
814 return contour()->globalState(); | 895 return contour()->globalState(); |
815 } | 896 } |
816 | 897 |
817 void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkP
ath::Verb verb) { | 898 void SkOpSegment::init(SkPoint pts[], SkScalar weight, SkOpContour* contour, SkP
ath::Verb verb) { |
818 fContour = contour; | 899 fContour = contour; |
819 fNext = NULL; | 900 fNext = NULL; |
| 901 fOriginal[0] = pts[0]; |
| 902 fOriginal[1] = pts[SkPathOpsVerbToPoints(verb)]; |
820 fPts = pts; | 903 fPts = pts; |
821 fWeight = weight; | 904 fWeight = weight; |
822 fVerb = verb; | 905 fVerb = verb; |
823 fCubicType = SkDCubic::kUnsplit_SkDCubicType; | 906 fCubicType = SkDCubic::kUnsplit_SkDCubicType; |
824 fCount = 0; | 907 fCount = 0; |
825 fDoneCount = 0; | 908 fDoneCount = 0; |
826 fTopsFound = false; | 909 fTopsFound = false; |
827 fVisited = false; | 910 fVisited = false; |
828 SkOpSpan* zeroSpan = &fHead; | 911 SkOpSpan* zeroSpan = &fHead; |
829 zeroSpan->init(this, NULL, 0, fPts[0]); | 912 zeroSpan->init(this, NULL, 0, fPts[0]); |
(...skipping 276 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1106 opp->resetVisited(); | 1189 opp->resetVisited(); |
1107 } | 1190 } |
1108 } while (!span->final() && (span = span->upCast()->next())); | 1191 } while (!span->final() && (span = span->upCast()->next())); |
1109 } | 1192 } |
1110 | 1193 |
1111 // look for pairs of undetected coincident curves | 1194 // look for pairs of undetected coincident curves |
1112 // assumes that segments going in have visited flag clear | 1195 // assumes that segments going in have visited flag clear |
1113 // curve/curve intersection should now do a pretty good job of finding coinciden
t runs so | 1196 // curve/curve intersection should now do a pretty good job of finding coinciden
t runs so |
1114 // this may be only be necessary for line/curve pairs -- so skip unless this is
a line and the | 1197 // this may be only be necessary for line/curve pairs -- so skip unless this is
a line and the |
1115 // the opp is not a line | 1198 // the opp is not a line |
1116 void SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
* allocator) { | 1199 bool SkOpSegment::missingCoincidence(SkOpCoincidence* coincidences, SkChunkAlloc
* allocator) { |
1117 if (this->verb() != SkPath::kLine_Verb) { | 1200 if (this->verb() != SkPath::kLine_Verb) { |
1118 return; | 1201 return false; |
1119 } | 1202 } |
1120 if (this->done()) { | 1203 if (this->done()) { |
1121 return; | 1204 return false; |
1122 } | 1205 } |
1123 SkOpSpan* prior = NULL; | 1206 SkOpSpan* prior = NULL; |
1124 SkOpSpanBase* spanBase = &fHead; | 1207 SkOpSpanBase* spanBase = &fHead; |
1125 do { | 1208 do { |
1126 SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; | 1209 SkOpPtT* ptT = spanBase->ptT(), * spanStopPtT = ptT; |
1127 SkASSERT(ptT->span() == spanBase); | 1210 SkASSERT(ptT->span() == spanBase); |
1128 while ((ptT = ptT->next()) != spanStopPtT) { | 1211 while ((ptT = ptT->next()) != spanStopPtT) { |
1129 if (ptT->deleted()) { | 1212 if (ptT->deleted()) { |
1130 continue; | 1213 continue; |
1131 } | 1214 } |
(...skipping 47 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1179 bool swapped = priorPtT->fT > ptT->fT; | 1262 bool swapped = priorPtT->fT > ptT->fT; |
1180 if (swapped) { | 1263 if (swapped) { |
1181 SkTSwap(priorPtT, ptT); | 1264 SkTSwap(priorPtT, ptT); |
1182 SkTSwap(oppStart, oppEnd); | 1265 SkTSwap(oppStart, oppEnd); |
1183 } | 1266 } |
1184 bool flipped = oppStart->fT > oppEnd->fT; | 1267 bool flipped = oppStart->fT > oppEnd->fT; |
1185 bool coincident; | 1268 bool coincident; |
1186 if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)
) { | 1269 if (coincidences->contains(priorPtT, ptT, oppStart, oppEnd, flipped)
) { |
1187 goto swapBack; | 1270 goto swapBack; |
1188 } | 1271 } |
1189 { | 1272 coincident = testForCoincidence(priorPtT, ptT, prior, spanBase, opp,
5000); |
1190 // average t, find mid pt | |
1191 double midT = (prior->t() + spanBase->t()) / 2; | |
1192 SkPoint midPt = this->ptAtT(midT); | |
1193 coincident = true; | |
1194 // if the mid pt is not near either end pt, project perpendicula
r through opp seg | |
1195 if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) | |
1196 && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { | |
1197 coincident = false; | |
1198 SkIntersections i; | |
1199 SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->w
eight(), midT); | |
1200 SkDLine ray = {{{midPt.fX, midPt.fY}, | |
1201 {midPt.fX + dxdy.fY, midPt.fY - dxdy.fX}}}; | |
1202 (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(),
ray, &i); | |
1203 // measure distance and see if it's small enough to denote c
oincidence | |
1204 for (int index = 0; index < i.used(); ++index) { | |
1205 SkDPoint oppPt = i.pt(index); | |
1206 if (oppPt.approximatelyEqual(midPt)) { | |
1207 SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp
->pts(), | |
1208 opp->weight(), i[index][0]); | |
1209 oppDxdy.normalize(); | |
1210 dxdy.normalize(); | |
1211 SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy)
/ FLT_EPSILON); | |
1212 coincident |= flatness < 5000; // FIXME: replace wi
th tuned value | |
1213 } | |
1214 } | |
1215 } | |
1216 } | |
1217 if (coincident) { | 1273 if (coincident) { |
1218 // mark coincidence | 1274 // mark coincidence |
1219 if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd) | 1275 if (!coincidences->extend(priorPtT, ptT, oppStart, oppEnd) |
1220 && !coincidences->extend(oppStart, oppEnd, priorPtT, ptT
)) { | 1276 && !coincidences->extend(oppStart, oppEnd, priorPtT, ptT
)) { |
1221 coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator
); | 1277 coincidences->add(priorPtT, ptT, oppStart, oppEnd, allocator
); |
1222 } | 1278 } |
1223 clear_visited(&fHead); | 1279 clear_visited(&fHead); |
1224 return; | 1280 return true; |
1225 } | 1281 } |
1226 swapBack: | 1282 swapBack: |
1227 if (swapped) { | 1283 if (swapped) { |
1228 SkTSwap(priorPtT, ptT); | 1284 SkTSwap(priorPtT, ptT); |
1229 } | 1285 } |
1230 } | 1286 } |
1231 } while ((spanBase = spanBase->final() ? NULL : spanBase->upCast()->next()))
; | 1287 } while ((spanBase = spanBase->final() ? NULL : spanBase->upCast()->next()))
; |
1232 clear_visited(&fHead); | 1288 clear_visited(&fHead); |
| 1289 return false; |
1233 } | 1290 } |
1234 | 1291 |
1235 // if a span has more than one intersection, merge the other segments' span as n
eeded | 1292 // if a span has more than one intersection, merge the other segments' span as n
eeded |
1236 void SkOpSegment::moveMultiples() { | 1293 void SkOpSegment::moveMultiples() { |
1237 debugValidate(); | 1294 debugValidate(); |
1238 SkOpSpanBase* test = &fHead; | 1295 SkOpSpanBase* test = &fHead; |
1239 do { | 1296 do { |
1240 int addCount = test->spanAddsCount(); | 1297 int addCount = test->spanAddsCount(); |
1241 SkASSERT(addCount >= 1); | 1298 SkASSERT(addCount >= 1); |
1242 if (addCount == 1) { | 1299 if (addCount == 1) { |
(...skipping 357 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1600 } else if (fVerb == SkPath::kConic_Verb) { | 1657 } else if (fVerb == SkPath::kConic_Verb) { |
1601 edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edg
e->fQuad[2], | 1658 edge->fConic[1] = SkDConic::SubDivide(fPts, fWeight, edge->fQuad[0], edg
e->fQuad[2], |
1602 startT, endT, &edge->fConic.fWeight); | 1659 startT, endT, &edge->fConic.fWeight); |
1603 } else { | 1660 } else { |
1604 SkASSERT(fVerb == SkPath::kCubic_Verb); | 1661 SkASSERT(fVerb == SkPath::kCubic_Verb); |
1605 SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT
, &edge->fCubic[1]); | 1662 SkDCubic::SubDivide(fPts, edge->fCubic[0], edge->fCubic[3], startT, endT
, &edge->fCubic[1]); |
1606 } | 1663 } |
1607 return true; | 1664 return true; |
1608 } | 1665 } |
1609 | 1666 |
| 1667 bool SkOpSegment::testForCoincidence(const SkOpPtT* priorPtT, const SkOpPtT* ptT
, |
| 1668 const SkOpSpanBase* prior, const SkOpSpanBase* spanBase, const SkOpSegme
nt* opp, |
| 1669 SkScalar flatnessLimit) const { |
| 1670 // average t, find mid pt |
| 1671 double midT = (prior->t() + spanBase->t()) / 2; |
| 1672 SkPoint midPt = this->ptAtT(midT); |
| 1673 bool coincident = true; |
| 1674 // if the mid pt is not near either end pt, project perpendicular through op
p seg |
| 1675 if (!SkDPoint::ApproximatelyEqual(priorPtT->fPt, midPt) |
| 1676 && !SkDPoint::ApproximatelyEqual(ptT->fPt, midPt)) { |
| 1677 coincident = false; |
| 1678 SkIntersections i; |
| 1679 SkVector dxdy = (*CurveSlopeAtT[fVerb])(this->pts(), this->weight(), mid
T); |
| 1680 SkDLine ray = {{{midPt.fX, midPt.fY}, {midPt.fX + dxdy.fY, midPt.fY - dx
dy.fX}}}; |
| 1681 (*CurveIntersectRay[opp->verb()])(opp->pts(), opp->weight(), ray, &i); |
| 1682 // measure distance and see if it's small enough to denote coincidence |
| 1683 for (int index = 0; index < i.used(); ++index) { |
| 1684 SkDPoint oppPt = i.pt(index); |
| 1685 if (oppPt.approximatelyEqual(midPt)) { |
| 1686 SkVector oppDxdy = (*CurveSlopeAtT[opp->verb()])(opp->pts(), |
| 1687 opp->weight(), i[index][0]); |
| 1688 oppDxdy.normalize(); |
| 1689 dxdy.normalize(); |
| 1690 SkScalar flatness = SkScalarAbs(dxdy.cross(oppDxdy) / FLT_EPSILO
N); |
| 1691 coincident |= flatness < flatnessLimit; |
| 1692 } |
| 1693 } |
| 1694 } |
| 1695 return coincident; |
| 1696 } |
| 1697 |
1610 void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) { | 1698 void SkOpSegment::undoneSpan(SkOpSpanBase** start, SkOpSpanBase** end) { |
1611 SkOpSpan* span = this->head(); | 1699 SkOpSpan* span = this->head(); |
1612 do { | 1700 do { |
1613 if (!span->done()) { | 1701 if (!span->done()) { |
1614 break; | 1702 break; |
1615 } | 1703 } |
1616 } while ((span = span->next()->upCastable())); | 1704 } while ((span = span->next()->upCastable())); |
1617 SkASSERT(span); | 1705 SkASSERT(span); |
1618 *start = span; | 1706 *start = span; |
1619 *end = span->next(); | 1707 *end = span->next(); |
(...skipping 60 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1680 int absOut = abs(outerWinding); | 1768 int absOut = abs(outerWinding); |
1681 int absIn = abs(innerWinding); | 1769 int absIn = abs(innerWinding); |
1682 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; | 1770 bool result = absOut == absIn ? outerWinding < 0 : absOut < absIn; |
1683 return result; | 1771 return result; |
1684 } | 1772 } |
1685 | 1773 |
1686 int SkOpSegment::windSum(const SkOpAngle* angle) const { | 1774 int SkOpSegment::windSum(const SkOpAngle* angle) const { |
1687 const SkOpSpan* minSpan = angle->start()->starter(angle->end()); | 1775 const SkOpSpan* minSpan = angle->start()->starter(angle->end()); |
1688 return minSpan->windSum(); | 1776 return minSpan->windSum(); |
1689 } | 1777 } |
OLD | NEW |