| 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 |