OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2014 Google Inc. | 2 * Copyright 2014 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 | 7 |
8 #include "SkChunkAlloc.h" | 8 #include "SkChunkAlloc.h" |
9 #include "SkPathOpsBounds.h" | 9 #include "SkPathOpsBounds.h" |
10 #include "SkPathOpsRect.h" | 10 #include "SkPathOpsRect.h" |
11 #include "SkIntersections.h" | 11 #include "SkIntersections.h" |
12 #include "SkTSort.h" | 12 #include "SkTSort.h" |
13 | 13 |
14 #ifdef SK_DEBUG | |
15 typedef uint8_t SkOpDebugBool; | |
16 #else | |
17 typedef bool SkOpDebugBool; | |
18 #endif | |
19 | |
20 /* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */ | 14 /* TCurve and OppCurve are one of { SkDQuadratic, SkDConic, SkDCubic } */ |
21 template<typename TCurve, typename OppCurve> | 15 template<typename TCurve, typename OppCurve> |
22 class SkTCoincident { | 16 class SkTCoincident { |
23 public: | 17 public: |
24 SkTCoincident() { | 18 SkTCoincident() { |
25 this->init(); | 19 this->init(); |
26 } | 20 } |
27 | 21 |
28 void debugInit() { | |
29 #ifdef SK_DEBUG | |
30 this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN; | |
31 this->fPerpT = SK_ScalarNaN; | |
32 this->fCoincident = 0xFF; | |
33 #endif | |
34 } | |
35 | |
36 char dumpIsCoincidentStr() const; | |
37 void dump() const; | 22 void dump() const; |
38 | 23 |
39 bool isCoincident() const { | 24 bool isCoincident() const { |
40 SkASSERT(!!fCoincident == fCoincident); | 25 return fCoincident; |
41 return SkToBool(fCoincident); | |
42 } | 26 } |
43 | 27 |
44 void init() { | 28 void init() { |
45 fPerpT = -1; | 29 fPerpT = -1; |
46 fCoincident = false; | 30 fCoincident = false; |
47 fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN; | 31 fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN; |
48 } | 32 } |
49 | 33 |
50 void markCoincident() { | 34 void markCoincident() { |
51 if (!fCoincident) { | 35 if (!fCoincident) { |
52 fPerpT = -1; | 36 fPerpT = -1; |
53 } | 37 } |
54 fCoincident = true; | 38 fCoincident = true; |
55 } | 39 } |
56 | 40 |
57 const SkDPoint& perpPt() const { | 41 const SkDPoint& perpPt() const { |
58 return fPerpPt; | 42 return fPerpPt; |
59 } | 43 } |
60 | 44 |
61 double perpT() const { | 45 double perpT() const { |
62 return fPerpT; | 46 return fPerpT; |
63 } | 47 } |
64 | 48 |
65 void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve
& ); | 49 void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const OppCurve
& ); |
66 | 50 |
67 private: | 51 private: |
68 SkDPoint fPerpPt; | 52 SkDPoint fPerpPt; |
69 double fPerpT; // perpendicular intersection on opposite curve | 53 double fPerpT; // perpendicular intersection on opposite curve |
70 SkOpDebugBool fCoincident; | 54 bool fCoincident; |
71 }; | 55 }; |
72 | 56 |
73 template<typename TCurve, typename OppCurve> class SkTSect; | 57 template<typename TCurve, typename OppCurve> class SkTSect; |
74 template<typename TCurve, typename OppCurve> class SkTSpan; | 58 template<typename TCurve, typename OppCurve> class SkTSpan; |
75 | 59 |
76 template<typename TCurve, typename OppCurve> | 60 template<typename TCurve, typename OppCurve> |
77 struct SkTSpanBounded { | 61 struct SkTSpanBounded { |
78 SkTSpan<TCurve, OppCurve>* fBounded; | 62 SkTSpan<TCurve, OppCurve>* fBounded; |
79 SkTSpanBounded* fNext; | 63 SkTSpanBounded* fNext; |
80 }; | 64 }; |
(...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
194 TCurve fPart; | 178 TCurve fPart; |
195 SkTCoincident<TCurve, OppCurve> fCoinStart; | 179 SkTCoincident<TCurve, OppCurve> fCoinStart; |
196 SkTCoincident<TCurve, OppCurve> fCoinEnd; | 180 SkTCoincident<TCurve, OppCurve> fCoinEnd; |
197 SkTSpanBounded<OppCurve, TCurve>* fBounded; | 181 SkTSpanBounded<OppCurve, TCurve>* fBounded; |
198 SkTSpan* fPrev; | 182 SkTSpan* fPrev; |
199 SkTSpan* fNext; | 183 SkTSpan* fNext; |
200 SkDRect fBounds; | 184 SkDRect fBounds; |
201 double fStartT; | 185 double fStartT; |
202 double fEndT; | 186 double fEndT; |
203 double fBoundsMax; | 187 double fBoundsMax; |
204 SkOpDebugBool fCollapsed; | 188 bool fCollapsed; |
205 SkOpDebugBool fHasPerp; | 189 bool fHasPerp; |
206 SkOpDebugBool fIsLinear; | 190 bool fIsLinear; |
207 SkOpDebugBool fIsLine; | 191 bool fIsLine; |
208 SkOpDebugBool fDeleted; | 192 bool fDeleted; |
209 SkDEBUGCODE_(SkTSect<TCurve, OppCurve>* fDebugSect); | 193 SkDEBUGCODE_(SkTSect<TCurve, OppCurve>* fDebugSect); |
210 PATH_OPS_DEBUG_T_SECT_CODE(int fID); | 194 PATH_OPS_DEBUG_T_SECT_CODE(int fID); |
211 friend class SkTSect<TCurve, OppCurve>; | 195 friend class SkTSect<TCurve, OppCurve>; |
212 friend class SkTSect<OppCurve, TCurve>; | 196 friend class SkTSect<OppCurve, TCurve>; |
213 friend class SkTSpan<OppCurve, TCurve>; | 197 friend class SkTSpan<OppCurve, TCurve>; |
214 }; | 198 }; |
215 | 199 |
216 template<typename TCurve, typename OppCurve> | 200 template<typename TCurve, typename OppCurve> |
217 class SkTSect { | 201 class SkTSect { |
218 public: | 202 public: |
(...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
278 void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const; | 262 void dumpCommonCurves(const SkTSpan<TCurve, OppCurve>* ) const; |
279 static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>*
sect2, | 263 static int EndsEqual(const SkTSect* sect1, const SkTSect<OppCurve, TCurve>*
sect2, |
280 SkIntersections* ); | 264 SkIntersections* ); |
281 SkTSpan<TCurve, OppCurve>* extractCoincident(SkTSect<OppCurve, TCurve>* sect
2, | 265 SkTSpan<TCurve, OppCurve>* extractCoincident(SkTSect<OppCurve, TCurve>* sect
2, |
282 SkTSpan<TCurve, OppCurve>* fir
st, | 266 SkTSpan<TCurve, OppCurve>* fir
st, |
283 SkTSpan<TCurve, OppCurve>* las
t); | 267 SkTSpan<TCurve, OppCurve>* las
t); |
284 SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* firs
t, | 268 SkTSpan<TCurve, OppCurve>* findCoincidentRun(SkTSpan<TCurve, OppCurve>* firs
t, |
285 SkTSpan<TCurve, OppCurve>** la
stPtr); | 269 SkTSpan<TCurve, OppCurve>** la
stPtr); |
286 int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* o
pp, | 270 int intersects(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve>* o
pp, |
287 SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult); | 271 SkTSpan<OppCurve, TCurve>* oppSpan, int* oppResult); |
288 bool isParallel(const SkDLine& thisLine, const SkTSect<OppCurve, TCurve>* op
p) const; | |
289 int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve
>* opp, | 272 int linesIntersect(SkTSpan<TCurve, OppCurve>* span, SkTSect<OppCurve, TCurve
>* opp, |
290 SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* ); | 273 SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* ); |
291 void markSpanGone(SkTSpan<TCurve, OppCurve>* span); | 274 void markSpanGone(SkTSpan<TCurve, OppCurve>* span); |
292 bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, doub
le t2) const; | 275 bool matchedDirection(double t, const SkTSect<OppCurve, TCurve>* sect2, doub
le t2) const; |
293 void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, doubl
e t2, | 276 void matchedDirCheck(double t, const SkTSect<OppCurve, TCurve>* sect2, doubl
e t2, |
294 bool* calcMatched, bool* oppMatched) const; | 277 bool* calcMatched, bool* oppMatched) const; |
295 void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2); | 278 void mergeCoincidence(SkTSect<OppCurve, TCurve>* sect2); |
296 SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const; | 279 SkTSpan<TCurve, OppCurve>* prev(SkTSpan<TCurve, OppCurve>* ) const; |
297 void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp); | 280 void removeByPerpendicular(SkTSect<OppCurve, TCurve>* opp); |
298 void recoverCollapsed(); | 281 void recoverCollapsed(); |
(...skipping 539 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
838 { | 821 { |
839 fHead = addOne(); | 822 fHead = addOne(); |
840 fHead->init(c); | 823 fHead->init(c); |
841 } | 824 } |
842 | 825 |
843 template<typename TCurve, typename OppCurve> | 826 template<typename TCurve, typename OppCurve> |
844 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() { | 827 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() { |
845 SkTSpan<TCurve, OppCurve>* result; | 828 SkTSpan<TCurve, OppCurve>* result; |
846 if (fDeleted) { | 829 if (fDeleted) { |
847 result = fDeleted; | 830 result = fDeleted; |
| 831 result->reset(); |
848 fDeleted = result->fNext; | 832 fDeleted = result->fNext; |
849 } else { | 833 } else { |
850 result = new (fHeap.allocThrow(sizeof(SkTSpan<TCurve, OppCurve>)))( | 834 result = new (fHeap.allocThrow(sizeof(SkTSpan<TCurve, OppCurve>)))( |
851 SkTSpan<TCurve, OppCurve>); | 835 SkTSpan<TCurve, OppCurve>); |
| 836 result->fBounded = nullptr; |
852 #if DEBUG_T_SECT | 837 #if DEBUG_T_SECT |
853 ++fDebugAllocatedCount; | 838 ++fDebugAllocatedCount; |
854 #endif | 839 #endif |
855 } | 840 } |
856 result->reset(); | |
857 result->fHasPerp = false; | 841 result->fHasPerp = false; |
858 result->fDeleted = false; | 842 result->fDeleted = false; |
859 ++fActiveCount; | 843 ++fActiveCount; |
860 PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID); | 844 PATH_OPS_DEBUG_T_SECT_CODE(result->fID = fDebugCount++ * 2 + fID); |
861 SkDEBUGCODE(result->fDebugSect = this); | 845 SkDEBUGCODE(result->fDebugSect = this); |
862 #ifdef SK_DEBUG | |
863 result->fPart.debugInit(); | |
864 result->fCoinStart.debugInit(); | |
865 result->fCoinEnd.debugInit(); | |
866 result->fPrev = result->fNext = nullptr; | |
867 result->fBounds.debugInit(); | |
868 result->fStartT = result->fEndT = result->fBoundsMax = SK_ScalarNaN; | |
869 result->fCollapsed = result->fIsLinear = result->fIsLine = 0xFF; | |
870 #endif | |
871 return result; | 846 return result; |
872 } | 847 } |
873 | 848 |
874 template<typename TCurve, typename OppCurve> | 849 template<typename TCurve, typename OppCurve> |
875 bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect
2, double tStart, | 850 bool SkTSect<TCurve, OppCurve>::binarySearchCoin(SkTSect<OppCurve, TCurve>* sect
2, double tStart, |
876 double tStep, double* resultT, double* oppT) { | 851 double tStep, double* resultT, double* oppT) { |
877 SkTSpan<TCurve, OppCurve> work; | 852 SkTSpan<TCurve, OppCurve> work; |
878 double result = work.fStartT = work.fEndT = tStart; | 853 double result = work.fStartT = work.fEndT = tStart; |
879 SkDEBUGCODE(work.fDebugSect = this); | 854 SkDEBUGCODE(work.fDebugSect = this); |
880 SkDPoint last = fCurve.ptAtT(tStart); | 855 SkDPoint last = fCurve.ptAtT(tStart); |
(...skipping 414 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1295 span->fStartT = span->fEndT = i[0][0]; | 1270 span->fStartT = span->fEndT = i[0][0]; |
1296 oppSpan->fStartT = oppSpan->fEndT = i[1][0]; | 1271 oppSpan->fStartT = oppSpan->fEndT = i[1][0]; |
1297 return *oppResult = 2; | 1272 return *oppResult = 2; |
1298 } | 1273 } |
1299 if (span->fIsLinear || oppSpan->fIsLinear) { | 1274 if (span->fIsLinear || oppSpan->fIsLinear) { |
1300 return *oppResult = (int) span->linearsIntersect(oppSpan); | 1275 return *oppResult = (int) span->linearsIntersect(oppSpan); |
1301 } | 1276 } |
1302 return *oppResult = 1; | 1277 return *oppResult = 1; |
1303 } | 1278 } |
1304 | 1279 |
1305 template<typename TCurve> | |
1306 static bool is_parallel(const SkDLine& thisLine, const TCurve& opp) { | |
1307 if (!opp.IsConic()) { | |
1308 return false; // FIXME : breaks a lot of stuff now | |
1309 } | |
1310 int finds = 0; | |
1311 SkDLine thisPerp; | |
1312 thisPerp.fPts[0].fX = thisLine.fPts[1].fX + (thisLine.fPts[1].fY - thisLine.
fPts[0].fY); | |
1313 thisPerp.fPts[0].fY = thisLine.fPts[1].fY + (thisLine.fPts[0].fX - thisLine.
fPts[1].fX); | |
1314 thisPerp.fPts[1] = thisLine.fPts[1]; | |
1315 SkIntersections perpRayI; | |
1316 perpRayI.intersectRay(opp, thisPerp); | |
1317 for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) { | |
1318 finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[1]); | |
1319 } | |
1320 thisPerp.fPts[1].fX = thisLine.fPts[0].fX + (thisLine.fPts[1].fY - thisLine.
fPts[0].fY); | |
1321 thisPerp.fPts[1].fY = thisLine.fPts[0].fY + (thisLine.fPts[0].fX - thisLine.
fPts[1].fX); | |
1322 thisPerp.fPts[0] = thisLine.fPts[0]; | |
1323 perpRayI.intersectRay(opp, thisPerp); | |
1324 for (int pIndex = 0; pIndex < perpRayI.used(); ++pIndex) { | |
1325 finds += perpRayI.pt(pIndex).approximatelyEqual(thisPerp.fPts[0]); | |
1326 } | |
1327 return finds >= 2; | |
1328 } | |
1329 | |
1330 // while the intersection points are sufficiently far apart: | 1280 // while the intersection points are sufficiently far apart: |
1331 // construct the tangent lines from the intersections | 1281 // construct the tangent lines from the intersections |
1332 // find the point where the tangent line intersects the opposite curve | 1282 // find the point where the tangent line intersects the opposite curve |
1333 template<typename TCurve, typename OppCurve> | 1283 template<typename TCurve, typename OppCurve> |
1334 int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span, | 1284 int SkTSect<TCurve, OppCurve>::linesIntersect(SkTSpan<TCurve, OppCurve>* span, |
1335 SkTSect<OppCurve, TCurve>* opp, | 1285 SkTSect<OppCurve, TCurve>* opp, |
1336 SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) { | 1286 SkTSpan<OppCurve, TCurve>* oppSpan, SkIntersections* i) { |
1337 SkIntersections thisRayI, oppRayI; | 1287 SkIntersections thisRayI, oppRayI; |
1338 SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }}; | 1288 SkDLine thisLine = {{ span->fPart[0], span->fPart[TCurve::kPointLast] }}; |
1339 SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast]
}}; | 1289 SkDLine oppLine = {{ oppSpan->fPart[0], oppSpan->fPart[OppCurve::kPointLast]
}}; |
1340 int loopCount = 0; | 1290 int loopCount = 0; |
1341 double bestDistSq = DBL_MAX; | 1291 double bestDistSq = DBL_MAX; |
1342 if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { | 1292 if (!thisRayI.intersectRay(opp->fCurve, thisLine)) { |
1343 return 0; | 1293 return 0; |
1344 } | 1294 } |
1345 if (!oppRayI.intersectRay(this->fCurve, oppLine)) { | 1295 if (!oppRayI.intersectRay(this->fCurve, oppLine)) { |
1346 return 0; | 1296 return 0; |
1347 } | 1297 } |
1348 // if the ends of each line intersect the opposite curve, the lines are coin
cident | 1298 // if the ends of each line intersect the opposite curve, the lines are coin
cident |
1349 if (thisRayI.used() > 1) { | 1299 if (thisRayI.used() > 1) { |
1350 int ptMatches = 0; | 1300 int ptMatches = 0; |
1351 for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) { | 1301 for (int tIndex = 0; tIndex < thisRayI.used(); ++tIndex) { |
1352 for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); +
+lIndex) { | 1302 for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); +
+lIndex) { |
1353 ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPt
s[lIndex]); | 1303 ptMatches += thisRayI.pt(tIndex).approximatelyEqual(thisLine.fPt
s[lIndex]); |
1354 } | 1304 } |
1355 } | 1305 } |
1356 if (ptMatches == 2 || is_parallel(thisLine, opp->fCurve)) { | 1306 if (ptMatches == 2) { |
1357 return 2; | 1307 return 2; |
1358 } | 1308 } |
1359 } | 1309 } |
1360 if (oppRayI.used() > 1) { | 1310 if (oppRayI.used() > 1) { |
1361 int ptMatches = 0; | 1311 int ptMatches = 0; |
1362 for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) { | 1312 for (int oIndex = 0; oIndex < oppRayI.used(); ++oIndex) { |
1363 for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); +
+lIndex) { | 1313 for (int lIndex = 0; lIndex < (int) SK_ARRAY_COUNT(thisLine.fPts); +
+lIndex) { |
1364 ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[
lIndex]); | 1314 ptMatches += oppRayI.pt(oIndex).approximatelyEqual(oppLine.fPts[
lIndex]); |
1365 } | 1315 } |
1366 } | 1316 } |
1367 if (ptMatches == 2|| is_parallel(oppLine, this->fCurve)) { | 1317 if (ptMatches == 2) { |
1368 return 2; | 1318 return 2; |
1369 } | 1319 } |
1370 } | 1320 } |
1371 do { | 1321 do { |
1372 // pick the closest pair of points | 1322 // pick the closest pair of points |
1373 double closest = DBL_MAX; | 1323 double closest = DBL_MAX; |
1374 int closeIndex SK_INIT_TO_AVOID_WARNING; | 1324 int closeIndex SK_INIT_TO_AVOID_WARNING; |
1375 int oppCloseIndex SK_INIT_TO_AVOID_WARNING; | 1325 int oppCloseIndex SK_INIT_TO_AVOID_WARNING; |
1376 for (int index = 0; index < oppRayI.used(); ++index) { | 1326 for (int index = 0; index < oppRayI.used(); ++index) { |
1377 if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT))
{ | 1327 if (!roughly_between(span->fStartT, oppRayI[0][index], span->fEndT))
{ |
(...skipping 846 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2224 } else if (intersections->isCoincident(index + 1)) { | 2174 } else if (intersections->isCoincident(index + 1)) { |
2225 intersections->removeOne(index + 1); | 2175 intersections->removeOne(index + 1); |
2226 --last; | 2176 --last; |
2227 } else { | 2177 } else { |
2228 intersections->setCoincident(index++); | 2178 intersections->setCoincident(index++); |
2229 } | 2179 } |
2230 intersections->setCoincident(index); | 2180 intersections->setCoincident(index); |
2231 } | 2181 } |
2232 SkASSERT(intersections->used() <= TCurve::kMaxIntersections); | 2182 SkASSERT(intersections->used() <= TCurve::kMaxIntersections); |
2233 } | 2183 } |
OLD | NEW |