SkOpCoincidence.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303
  1. /*
  2. * Copyright 2013 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #ifndef SkOpCoincidence_DEFINED
  8. #define SkOpCoincidence_DEFINED
  9. #include "include/private/SkTDArray.h"
  10. #include "src/core/SkArenaAlloc.h"
  11. #include "src/pathops/SkOpSpan.h"
  12. #include "src/pathops/SkPathOpsTypes.h"
  13. class SkOpPtT;
  14. class SkOpSpanBase;
  15. class SkCoincidentSpans {
  16. public:
  17. const SkOpPtT* coinPtTEnd() const;
  18. const SkOpPtT* coinPtTStart() const;
  19. // These return non-const pointers so that, as copies, they can be added
  20. // to a new span pair
  21. SkOpPtT* coinPtTEndWritable() const { return const_cast<SkOpPtT*>(fCoinPtTEnd); }
  22. SkOpPtT* coinPtTStartWritable() const { return const_cast<SkOpPtT*>(fCoinPtTStart); }
  23. bool collapsed(const SkOpPtT* ) const;
  24. bool contains(const SkOpPtT* s, const SkOpPtT* e) const;
  25. void correctEnds();
  26. void correctOneEnd(const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
  27. void (SkCoincidentSpans::* setEnd)(const SkOpPtT* ptT) );
  28. #if DEBUG_COIN
  29. void debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const;
  30. void debugCorrectOneEnd(SkPathOpsDebug::GlitchLog* log,
  31. const SkOpPtT* (SkCoincidentSpans::* getEnd)() const,
  32. void (SkCoincidentSpans::* setEnd)(const SkOpPtT* ptT) const) const;
  33. bool debugExpand(SkPathOpsDebug::GlitchLog* log) const;
  34. #endif
  35. const char* debugID() const {
  36. #if DEBUG_COIN
  37. return fGlobalState->debugCoinDictEntry().fFunctionName;
  38. #else
  39. return nullptr;
  40. #endif
  41. }
  42. void debugShow() const;
  43. #ifdef SK_DEBUG
  44. void debugStartCheck(const SkOpSpanBase* outer, const SkOpSpanBase* over,
  45. const SkOpGlobalState* debugState) const;
  46. #endif
  47. void dump() const;
  48. bool expand();
  49. bool extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
  50. const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd);
  51. bool flipped() const { return fOppPtTStart->fT > fOppPtTEnd->fT; }
  52. SkDEBUGCODE(SkOpGlobalState* globalState() { return fGlobalState; })
  53. void init(SkDEBUGCODE(SkOpGlobalState* globalState)) {
  54. sk_bzero(this, sizeof(*this));
  55. SkDEBUGCODE(fGlobalState = globalState);
  56. }
  57. SkCoincidentSpans* next() { return fNext; }
  58. const SkCoincidentSpans* next() const { return fNext; }
  59. SkCoincidentSpans** nextPtr() { return &fNext; }
  60. const SkOpPtT* oppPtTStart() const;
  61. const SkOpPtT* oppPtTEnd() const;
  62. // These return non-const pointers so that, as copies, they can be added
  63. // to a new span pair
  64. SkOpPtT* oppPtTStartWritable() const { return const_cast<SkOpPtT*>(fOppPtTStart); }
  65. SkOpPtT* oppPtTEndWritable() const { return const_cast<SkOpPtT*>(fOppPtTEnd); }
  66. bool ordered(bool* result) const;
  67. void set(SkCoincidentSpans* next, const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
  68. const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd);
  69. void setCoinPtTEnd(const SkOpPtT* ptT) {
  70. SkOPASSERT(ptT == ptT->span()->ptT());
  71. SkOPASSERT(!fCoinPtTStart || ptT->fT != fCoinPtTStart->fT);
  72. SkASSERT(!fCoinPtTStart || fCoinPtTStart->segment() == ptT->segment());
  73. fCoinPtTEnd = ptT;
  74. ptT->setCoincident();
  75. }
  76. void setCoinPtTStart(const SkOpPtT* ptT) {
  77. SkOPASSERT(ptT == ptT->span()->ptT());
  78. SkOPASSERT(!fCoinPtTEnd || ptT->fT != fCoinPtTEnd->fT);
  79. SkASSERT(!fCoinPtTEnd || fCoinPtTEnd->segment() == ptT->segment());
  80. fCoinPtTStart = ptT;
  81. ptT->setCoincident();
  82. }
  83. void setEnds(const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTEnd) {
  84. this->setCoinPtTEnd(coinPtTEnd);
  85. this->setOppPtTEnd(oppPtTEnd);
  86. }
  87. void setOppPtTEnd(const SkOpPtT* ptT) {
  88. SkOPASSERT(ptT == ptT->span()->ptT());
  89. SkOPASSERT(!fOppPtTStart || ptT->fT != fOppPtTStart->fT);
  90. SkASSERT(!fOppPtTStart || fOppPtTStart->segment() == ptT->segment());
  91. fOppPtTEnd = ptT;
  92. ptT->setCoincident();
  93. }
  94. void setOppPtTStart(const SkOpPtT* ptT) {
  95. SkOPASSERT(ptT == ptT->span()->ptT());
  96. SkOPASSERT(!fOppPtTEnd || ptT->fT != fOppPtTEnd->fT);
  97. SkASSERT(!fOppPtTEnd || fOppPtTEnd->segment() == ptT->segment());
  98. fOppPtTStart = ptT;
  99. ptT->setCoincident();
  100. }
  101. void setStarts(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) {
  102. this->setCoinPtTStart(coinPtTStart);
  103. this->setOppPtTStart(oppPtTStart);
  104. }
  105. void setNext(SkCoincidentSpans* next) { fNext = next; }
  106. private:
  107. SkCoincidentSpans* fNext;
  108. const SkOpPtT* fCoinPtTStart;
  109. const SkOpPtT* fCoinPtTEnd;
  110. const SkOpPtT* fOppPtTStart;
  111. const SkOpPtT* fOppPtTEnd;
  112. SkDEBUGCODE(SkOpGlobalState* fGlobalState);
  113. };
  114. class SkOpCoincidence {
  115. public:
  116. SkOpCoincidence(SkOpGlobalState* globalState)
  117. : fHead(nullptr)
  118. , fTop(nullptr)
  119. , fGlobalState(globalState)
  120. , fContinue(false)
  121. , fSpanDeleted(false)
  122. , fPtAllocated(false)
  123. , fCoinExtended(false)
  124. , fSpanMerged(false) {
  125. globalState->setCoincidence(this);
  126. }
  127. void add(SkOpPtT* coinPtTStart, SkOpPtT* coinPtTEnd, SkOpPtT* oppPtTStart,
  128. SkOpPtT* oppPtTEnd);
  129. bool addEndMovedSpans(DEBUG_COIN_DECLARE_ONLY_PARAMS());
  130. bool addExpanded(DEBUG_COIN_DECLARE_ONLY_PARAMS());
  131. bool addMissing(bool* added DEBUG_COIN_DECLARE_PARAMS());
  132. bool apply(DEBUG_COIN_DECLARE_ONLY_PARAMS());
  133. bool contains(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd,
  134. const SkOpPtT* oppPtTStart, const SkOpPtT* oppPtTEnd) const;
  135. void correctEnds(DEBUG_COIN_DECLARE_ONLY_PARAMS());
  136. #if DEBUG_COIN
  137. void debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* log) const;
  138. void debugAddExpanded(SkPathOpsDebug::GlitchLog* ) const;
  139. void debugAddMissing(SkPathOpsDebug::GlitchLog* , bool* added) const;
  140. void debugAddOrOverlap(SkPathOpsDebug::GlitchLog* log,
  141. const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
  142. double coinTs, double coinTe, double oppTs, double oppTe,
  143. bool* added) const;
  144. #endif
  145. const SkOpAngle* debugAngle(int id) const {
  146. return SkDEBUGRELEASE(fGlobalState->debugAngle(id), nullptr);
  147. }
  148. void debugCheckBetween() const;
  149. #if DEBUG_COIN
  150. void debugCheckValid(SkPathOpsDebug::GlitchLog* log) const;
  151. #endif
  152. SkOpContour* debugContour(int id) const {
  153. return SkDEBUGRELEASE(fGlobalState->debugContour(id), nullptr);
  154. }
  155. #if DEBUG_COIN
  156. void debugCorrectEnds(SkPathOpsDebug::GlitchLog* log) const;
  157. bool debugExpand(SkPathOpsDebug::GlitchLog* ) const;
  158. void debugMark(SkPathOpsDebug::GlitchLog* ) const;
  159. void debugMarkCollapsed(SkPathOpsDebug::GlitchLog* ,
  160. const SkCoincidentSpans* coin, const SkOpPtT* test) const;
  161. void debugMarkCollapsed(SkPathOpsDebug::GlitchLog* , const SkOpPtT* test) const;
  162. #endif
  163. const SkOpPtT* debugPtT(int id) const {
  164. return SkDEBUGRELEASE(fGlobalState->debugPtT(id), nullptr);
  165. }
  166. const SkOpSegment* debugSegment(int id) const {
  167. return SkDEBUGRELEASE(fGlobalState->debugSegment(id), nullptr);
  168. }
  169. #if DEBUG_COIN
  170. void debugRelease(SkPathOpsDebug::GlitchLog* , const SkCoincidentSpans* ,
  171. const SkCoincidentSpans* ) const;
  172. void debugRelease(SkPathOpsDebug::GlitchLog* , const SkOpSegment* ) const;
  173. #endif
  174. void debugShowCoincidence() const;
  175. const SkOpSpanBase* debugSpan(int id) const {
  176. return SkDEBUGRELEASE(fGlobalState->debugSpan(id), nullptr);
  177. }
  178. void debugValidate() const;
  179. void dump() const;
  180. bool expand(DEBUG_COIN_DECLARE_ONLY_PARAMS());
  181. bool extend(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart,
  182. const SkOpPtT* oppPtTEnd);
  183. bool findOverlaps(SkOpCoincidence* DEBUG_COIN_DECLARE_PARAMS()) const;
  184. void fixUp(SkOpPtT* deleted, const SkOpPtT* kept);
  185. SkOpGlobalState* globalState() {
  186. return fGlobalState;
  187. }
  188. const SkOpGlobalState* globalState() const {
  189. return fGlobalState;
  190. }
  191. bool isEmpty() const {
  192. return !fHead && !fTop;
  193. }
  194. bool mark(DEBUG_COIN_DECLARE_ONLY_PARAMS());
  195. void markCollapsed(SkOpPtT* );
  196. static bool Ordered(const SkOpPtT* coinPtTStart, const SkOpPtT* oppPtTStart) {
  197. return Ordered(coinPtTStart->segment(), oppPtTStart->segment());
  198. }
  199. static bool Ordered(const SkOpSegment* coin, const SkOpSegment* opp);
  200. void release(const SkOpSegment* );
  201. void releaseDeleted();
  202. private:
  203. void add(const SkOpPtT* coinPtTStart, const SkOpPtT* coinPtTEnd, const SkOpPtT* oppPtTStart,
  204. const SkOpPtT* oppPtTEnd) {
  205. this->add(const_cast<SkOpPtT*>(coinPtTStart), const_cast<SkOpPtT*>(coinPtTEnd),
  206. const_cast<SkOpPtT*>(oppPtTStart), const_cast<SkOpPtT*>(oppPtTEnd));
  207. }
  208. bool addEndMovedSpans(const SkOpSpan* base, const SkOpSpanBase* testSpan);
  209. bool addEndMovedSpans(const SkOpPtT* ptT);
  210. bool addIfMissing(const SkOpPtT* over1s, const SkOpPtT* over2s,
  211. double tStart, double tEnd, SkOpSegment* coinSeg, SkOpSegment* oppSeg,
  212. bool* added
  213. SkDEBUGPARAMS(const SkOpPtT* over1e) SkDEBUGPARAMS(const SkOpPtT* over2e));
  214. bool addOrOverlap(SkOpSegment* coinSeg, SkOpSegment* oppSeg,
  215. double coinTs, double coinTe, double oppTs, double oppTe, bool* added);
  216. bool addOverlap(const SkOpSegment* seg1, const SkOpSegment* seg1o,
  217. const SkOpSegment* seg2, const SkOpSegment* seg2o,
  218. const SkOpPtT* overS, const SkOpPtT* overE);
  219. bool checkOverlap(SkCoincidentSpans* check,
  220. const SkOpSegment* coinSeg, const SkOpSegment* oppSeg,
  221. double coinTs, double coinTe, double oppTs, double oppTe,
  222. SkTDArray<SkCoincidentSpans*>* overlaps) const;
  223. bool contains(const SkOpSegment* seg, const SkOpSegment* opp, double oppT) const;
  224. bool contains(const SkCoincidentSpans* coin, const SkOpSegment* seg,
  225. const SkOpSegment* opp, double oppT) const;
  226. #if DEBUG_COIN
  227. void debugAddIfMissing(SkPathOpsDebug::GlitchLog* ,
  228. const SkCoincidentSpans* outer, const SkOpPtT* over1s,
  229. const SkOpPtT* over1e) const;
  230. void debugAddIfMissing(SkPathOpsDebug::GlitchLog* ,
  231. const SkOpPtT* over1s, const SkOpPtT* over2s,
  232. double tStart, double tEnd,
  233. const SkOpSegment* coinSeg, const SkOpSegment* oppSeg, bool* added,
  234. const SkOpPtT* over1e, const SkOpPtT* over2e) const;
  235. void debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* ,
  236. const SkOpSpan* base, const SkOpSpanBase* testSpan) const;
  237. void debugAddEndMovedSpans(SkPathOpsDebug::GlitchLog* ,
  238. const SkOpPtT* ptT) const;
  239. #endif
  240. void fixUp(SkCoincidentSpans* coin, SkOpPtT* deleted, const SkOpPtT* kept);
  241. void markCollapsed(SkCoincidentSpans* head, SkOpPtT* test);
  242. bool overlap(const SkOpPtT* coinStart1, const SkOpPtT* coinEnd1,
  243. const SkOpPtT* coinStart2, const SkOpPtT* coinEnd2,
  244. double* overS, double* overE) const;
  245. bool release(SkCoincidentSpans* coin, SkCoincidentSpans* );
  246. void releaseDeleted(SkCoincidentSpans* );
  247. void restoreHead();
  248. // return coinPtT->segment()->t mapped from overS->fT <= t <= overE->fT
  249. static double TRange(const SkOpPtT* overS, double t, const SkOpSegment* coinPtT
  250. SkDEBUGPARAMS(const SkOpPtT* overE));
  251. SkCoincidentSpans* fHead;
  252. SkCoincidentSpans* fTop;
  253. SkOpGlobalState* fGlobalState;
  254. bool fContinue;
  255. bool fSpanDeleted;
  256. bool fPtAllocated;
  257. bool fCoinExtended;
  258. bool fSpanMerged;
  259. };
  260. #endif