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 #ifndef SkPathOpsTSect_DEFINED | 7 #ifndef SkPathOpsTSect_DEFINED |
8 #define SkPathOpsTSect_DEFINED | 8 #define SkPathOpsTSect_DEFINED |
9 | 9 |
10 #include "SkChunkAlloc.h" | 10 #include "SkChunkAlloc.h" |
(...skipping 200 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
211 SkDEBUGCODE_(SkTSect<TCurve, OppCurve>* fDebugSect); | 211 SkDEBUGCODE_(SkTSect<TCurve, OppCurve>* fDebugSect); |
212 PATH_OPS_DEBUG_T_SECT_CODE(int fID); | 212 PATH_OPS_DEBUG_T_SECT_CODE(int fID); |
213 friend class SkTSect<TCurve, OppCurve>; | 213 friend class SkTSect<TCurve, OppCurve>; |
214 friend class SkTSect<OppCurve, TCurve>; | 214 friend class SkTSect<OppCurve, TCurve>; |
215 friend class SkTSpan<OppCurve, TCurve>; | 215 friend class SkTSpan<OppCurve, TCurve>; |
216 }; | 216 }; |
217 | 217 |
218 template<typename TCurve, typename OppCurve> | 218 template<typename TCurve, typename OppCurve> |
219 class SkTSect { | 219 class SkTSect { |
220 public: | 220 public: |
221 SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(int id)); | 221 SkTSect(const TCurve& c SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_S
ECT_PARAMS(int id)); |
222 static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2, | 222 static void BinarySearch(SkTSect* sect1, SkTSect<OppCurve, TCurve>* sect2, |
223 SkIntersections* intersections); | 223 SkIntersections* intersections); |
224 | 224 |
| 225 SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; }) |
225 // for testing only | 226 // for testing only |
226 bool debugHasBounded(const SkTSpan<OppCurve, TCurve>* ) const; | 227 bool debugHasBounded(const SkTSpan<OppCurve, TCurve>* ) const; |
227 | 228 |
228 const SkTSect<OppCurve, TCurve>* debugOpp() const { | 229 const SkTSect<OppCurve, TCurve>* debugOpp() const { |
229 return SkDEBUGRELEASE(fOppSect, nullptr); | 230 return SkDEBUGRELEASE(fOppSect, nullptr); |
230 } | 231 } |
231 | 232 |
232 const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const; | 233 const SkTSpan<TCurve, OppCurve>* debugSpan(int id) const; |
233 const SkTSpan<TCurve, OppCurve>* debugT(double t) const; | 234 const SkTSpan<TCurve, OppCurve>* debugT(double t) const; |
234 void dump() const; | 235 void dump() const; |
(...skipping 77 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
312 SkTSpan<OppCurve, TCurve>* oppFirst); | 313 SkTSpan<OppCurve, TCurve>* oppFirst); |
313 void validate() const; | 314 void validate() const; |
314 void validateBounded() const; | 315 void validateBounded() const; |
315 | 316 |
316 const TCurve& fCurve; | 317 const TCurve& fCurve; |
317 SkChunkAlloc fHeap; | 318 SkChunkAlloc fHeap; |
318 SkTSpan<TCurve, OppCurve>* fHead; | 319 SkTSpan<TCurve, OppCurve>* fHead; |
319 SkTSpan<TCurve, OppCurve>* fCoincident; | 320 SkTSpan<TCurve, OppCurve>* fCoincident; |
320 SkTSpan<TCurve, OppCurve>* fDeleted; | 321 SkTSpan<TCurve, OppCurve>* fDeleted; |
321 int fActiveCount; | 322 int fActiveCount; |
| 323 SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState); |
322 SkDEBUGCODE_(SkTSect<OppCurve, TCurve>* fOppSect); | 324 SkDEBUGCODE_(SkTSect<OppCurve, TCurve>* fOppSect); |
323 PATH_OPS_DEBUG_T_SECT_CODE(int fID); | 325 PATH_OPS_DEBUG_T_SECT_CODE(int fID); |
324 PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount); | 326 PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount); |
325 #if DEBUG_T_SECT | 327 #if DEBUG_T_SECT |
326 int fDebugAllocatedCount; | 328 int fDebugAllocatedCount; |
327 #endif | 329 #endif |
328 friend class SkTSpan<TCurve, OppCurve>; | 330 friend class SkTSpan<TCurve, OppCurve>; |
329 friend class SkTSpan<OppCurve, TCurve>; | 331 friend class SkTSpan<OppCurve, TCurve>; |
330 friend class SkTSect<OppCurve, TCurve>; | 332 friend class SkTSect<OppCurve, TCurve>; |
331 }; | 333 }; |
(...skipping 489 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
821 SkASSERT(0); | 823 SkASSERT(0); |
822 } | 824 } |
823 | 825 |
824 template<typename TCurve, typename OppCurve> | 826 template<typename TCurve, typename OppCurve> |
825 void SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) con
st { | 827 void SkTSpan<TCurve, OppCurve>::validatePerpPt(double t, const SkDPoint& pt) con
st { |
826 SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt); | 828 SkASSERT(fDebugSect->fOppSect->fCurve.ptAtT(t) == pt); |
827 } | 829 } |
828 | 830 |
829 | 831 |
830 template<typename TCurve, typename OppCurve> | 832 template<typename TCurve, typename OppCurve> |
831 SkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_T_SECT_PARAMS(
int id)) | 833 SkTSect<TCurve, OppCurve>::SkTSect(const TCurve& c |
| 834 SkDEBUGPARAMS(SkOpGlobalState* debugGlobalState) |
| 835 PATH_OPS_DEBUG_T_SECT_PARAMS(int id)) |
832 : fCurve(c) | 836 : fCurve(c) |
833 , fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4) | 837 , fHeap(sizeof(SkTSpan<TCurve, OppCurve>) * 4) |
834 , fCoincident(nullptr) | 838 , fCoincident(nullptr) |
835 , fDeleted(nullptr) | 839 , fDeleted(nullptr) |
836 , fActiveCount(0) | 840 , fActiveCount(0) |
| 841 SkDEBUGPARAMS(fDebugGlobalState(debugGlobalState)) |
837 PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id)) | 842 PATH_OPS_DEBUG_T_SECT_PARAMS(fID(id)) |
838 PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0)) | 843 PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugCount(0)) |
839 PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0)) | 844 PATH_OPS_DEBUG_T_SECT_PARAMS(fDebugAllocatedCount(0)) |
840 { | 845 { |
841 fHead = addOne(); | 846 fHead = addOne(); |
842 fHead->init(c); | 847 fHead->init(c); |
843 } | 848 } |
844 | 849 |
845 template<typename TCurve, typename OppCurve> | 850 template<typename TCurve, typename OppCurve> |
846 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() { | 851 SkTSpan<TCurve, OppCurve>* SkTSect<TCurve, OppCurve>::addOne() { |
(...skipping 325 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1172 // FIXME: incomplete : if we're not at the end, find end of coin | 1177 // FIXME: incomplete : if we're not at the end, find end of coin |
1173 SkTSpan<OppCurve, TCurve>* oppLast; | 1178 SkTSpan<OppCurve, TCurve>* oppLast; |
1174 SkASSERT(last->fCoinEnd.isCoincident()); | 1179 SkASSERT(last->fCoinEnd.isCoincident()); |
1175 oppLast = last->findOppT(last->fCoinEnd.perpT()); | 1180 oppLast = last->findOppT(last->fCoinEnd.perpT()); |
1176 SkDEBUGCODE(coinEnd = last->fEndT); | 1181 SkDEBUGCODE(coinEnd = last->fEndT); |
1177 SkDEBUGCODE(oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT); | 1182 SkDEBUGCODE(oppEndT = oppMatched ? oppLast->fEndT : oppLast->fStartT); |
1178 if (!oppMatched) { | 1183 if (!oppMatched) { |
1179 SkTSwap(oppFirst, oppLast); | 1184 SkTSwap(oppFirst, oppLast); |
1180 SkTSwap(oppStartT, oppEndT); | 1185 SkTSwap(oppStartT, oppEndT); |
1181 } | 1186 } |
1182 SkASSERT(oppStartT < oppEndT); | 1187 SkOPASSERT(oppStartT < oppEndT); |
1183 SkASSERT(coinStart == first->fStartT); | 1188 SkASSERT(coinStart == first->fStartT); |
1184 SkASSERT(coinEnd == last->fEndT); | 1189 SkASSERT(coinEnd == last->fEndT); |
1185 SkASSERT(oppStartT == oppFirst->fStartT); | 1190 SkASSERT(oppStartT == oppFirst->fStartT); |
1186 SkASSERT(oppEndT == oppLast->fEndT); | 1191 SkASSERT(oppEndT == oppLast->fEndT); |
1187 // reduce coincident runs to single entries | 1192 // reduce coincident runs to single entries |
1188 this->validate(); | 1193 this->validate(); |
1189 sect2->validate(); | 1194 sect2->validate(); |
1190 bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); | 1195 bool deleteEmptySpans = this->updateBounded(first, last, oppFirst); |
1191 deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); | 1196 deleteEmptySpans |= sect2->updateBounded(oppFirst, oppLast, first); |
1192 this->removeSpanRange(first, last); | 1197 this->removeSpanRange(first, last); |
(...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1244 *lastPtr = lastCandidate; | 1249 *lastPtr = lastCandidate; |
1245 return first; | 1250 return first; |
1246 } else { | 1251 } else { |
1247 lastCandidate = nullptr; | 1252 lastCandidate = nullptr; |
1248 SkASSERT(!first); | 1253 SkASSERT(!first); |
1249 } | 1254 } |
1250 if (work == *lastPtr) { | 1255 if (work == *lastPtr) { |
1251 return first; | 1256 return first; |
1252 } | 1257 } |
1253 work = work->fNext; | 1258 work = work->fNext; |
1254 SkASSERT(work); | 1259 if (!work) { |
| 1260 return nullptr; |
| 1261 } |
1255 } while (true); | 1262 } while (true); |
1256 if (lastCandidate) { | 1263 if (lastCandidate) { |
1257 *lastPtr = lastCandidate; | 1264 *lastPtr = lastCandidate; |
1258 } | 1265 } |
1259 return first; | 1266 return first; |
1260 } | 1267 } |
1261 | 1268 |
1262 template<typename TCurve, typename OppCurve> | 1269 template<typename TCurve, typename OppCurve> |
1263 int SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span, | 1270 int SkTSect<TCurve, OppCurve>::intersects(SkTSpan<TCurve, OppCurve>* span, |
1264 SkTSect<OppCurve, TCurve>* opp, | 1271 SkTSect<OppCurve, TCurve>* opp, |
(...skipping 231 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1496 i->insert(workT, oppTTest, workPt); | 1503 i->insert(workT, oppTTest, workPt); |
1497 return 1; | 1504 return 1; |
1498 } | 1505 } |
1499 | 1506 |
1500 | 1507 |
1501 template<typename TCurve, typename OppCurve> | 1508 template<typename TCurve, typename OppCurve> |
1502 void SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) { | 1509 void SkTSect<TCurve, OppCurve>::markSpanGone(SkTSpan<TCurve, OppCurve>* span) { |
1503 --fActiveCount; | 1510 --fActiveCount; |
1504 span->fNext = fDeleted; | 1511 span->fNext = fDeleted; |
1505 fDeleted = span; | 1512 fDeleted = span; |
1506 SkASSERT(!span->fDeleted); | 1513 SkOPASSERT(!span->fDeleted); |
1507 span->fDeleted = true; | 1514 span->fDeleted = true; |
1508 } | 1515 } |
1509 | 1516 |
1510 template<typename TCurve, typename OppCurve> | 1517 template<typename TCurve, typename OppCurve> |
1511 bool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurv
e, TCurve>* sect2, | 1518 bool SkTSect<TCurve, OppCurve>::matchedDirection(double t, const SkTSect<OppCurv
e, TCurve>* sect2, |
1512 double t2) const { | 1519 double t2) const { |
1513 SkDVector dxdy = this->fCurve.dxdyAtT(t); | 1520 SkDVector dxdy = this->fCurve.dxdyAtT(t); |
1514 SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2); | 1521 SkDVector dxdy2 = sect2->fCurve.dxdyAtT(t2); |
1515 return dxdy.dot(dxdy2) >= 0; | 1522 return dxdy.dot(dxdy2) >= 0; |
1516 } | 1523 } |
(...skipping 270 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1787 } | 1794 } |
1788 | 1795 |
1789 template<typename TCurve, typename OppCurve> | 1796 template<typename TCurve, typename OppCurve> |
1790 bool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first, | 1797 bool SkTSect<TCurve, OppCurve>::updateBounded(SkTSpan<TCurve, OppCurve>* first, |
1791 SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) { | 1798 SkTSpan<TCurve, OppCurve>* last, SkTSpan<OppCurve, TCurve>* oppFirst) { |
1792 SkTSpan<TCurve, OppCurve>* test = first; | 1799 SkTSpan<TCurve, OppCurve>* test = first; |
1793 const SkTSpan<TCurve, OppCurve>* final = last->next(); | 1800 const SkTSpan<TCurve, OppCurve>* final = last->next(); |
1794 bool deleteSpan = false; | 1801 bool deleteSpan = false; |
1795 do { | 1802 do { |
1796 deleteSpan |= test->removeAllBounded(); | 1803 deleteSpan |= test->removeAllBounded(); |
1797 } while ((test = test->fNext) != final); | 1804 } while ((test = test->fNext) != final && test); |
1798 first->fBounded = nullptr; | 1805 first->fBounded = nullptr; |
1799 first->addBounded(oppFirst, &fHeap); | 1806 first->addBounded(oppFirst, &fHeap); |
1800 // cannot call validate until remove span range is called | 1807 // cannot call validate until remove span range is called |
1801 return deleteSpan; | 1808 return deleteSpan; |
1802 } | 1809 } |
1803 | 1810 |
1804 | 1811 |
1805 template<typename TCurve, typename OppCurve> | 1812 template<typename TCurve, typename OppCurve> |
1806 void SkTSect<TCurve, OppCurve>::validate() const { | 1813 void SkTSect<TCurve, OppCurve>::validate() const { |
1807 #if DEBUG_T_SECT | 1814 #if DEBUG_T_SECT |
(...skipping 439 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2247 --last; | 2254 --last; |
2248 } else { | 2255 } else { |
2249 intersections->setCoincident(index++); | 2256 intersections->setCoincident(index++); |
2250 } | 2257 } |
2251 intersections->setCoincident(index); | 2258 intersections->setCoincident(index); |
2252 } | 2259 } |
2253 SkASSERT(intersections->used() <= TCurve::kMaxIntersections); | 2260 SkASSERT(intersections->used() <= TCurve::kMaxIntersections); |
2254 } | 2261 } |
2255 | 2262 |
2256 #endif | 2263 #endif |
OLD | NEW |