SkPathOpsTSect.h 9.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374
  1. /*
  2. * Copyright 2014 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 SkPathOpsTSect_DEFINED
  8. #define SkPathOpsTSect_DEFINED
  9. #include "include/private/SkMacros.h"
  10. #include "src/core/SkArenaAlloc.h"
  11. #include "src/core/SkTSort.h"
  12. #include "src/pathops/SkIntersections.h"
  13. #include "src/pathops/SkPathOpsBounds.h"
  14. #include "src/pathops/SkPathOpsRect.h"
  15. #include "src/pathops/SkPathOpsTCurve.h"
  16. #include <utility>
  17. #ifdef SK_DEBUG
  18. typedef uint8_t SkOpDebugBool;
  19. #else
  20. typedef bool SkOpDebugBool;
  21. #endif
  22. static inline bool SkDoubleIsNaN(double x) {
  23. return x != x;
  24. }
  25. class SkTCoincident {
  26. public:
  27. SkTCoincident() {
  28. this->init();
  29. }
  30. void debugInit() {
  31. #ifdef SK_DEBUG
  32. this->fPerpPt.fX = this->fPerpPt.fY = SK_ScalarNaN;
  33. this->fPerpT = SK_ScalarNaN;
  34. this->fMatch = 0xFF;
  35. #endif
  36. }
  37. char dumpIsCoincidentStr() const;
  38. void dump() const;
  39. bool isMatch() const {
  40. SkASSERT(!!fMatch == fMatch);
  41. return SkToBool(fMatch);
  42. }
  43. void init() {
  44. fPerpT = -1;
  45. fMatch = false;
  46. fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN;
  47. }
  48. void markCoincident() {
  49. if (!fMatch) {
  50. fPerpT = -1;
  51. }
  52. fMatch = true;
  53. }
  54. const SkDPoint& perpPt() const {
  55. return fPerpPt;
  56. }
  57. double perpT() const {
  58. return fPerpT;
  59. }
  60. void setPerp(const SkTCurve& c1, double t, const SkDPoint& cPt, const SkTCurve& );
  61. private:
  62. SkDPoint fPerpPt;
  63. double fPerpT; // perpendicular intersection on opposite curve
  64. SkOpDebugBool fMatch;
  65. };
  66. class SkTSect;
  67. class SkTSpan;
  68. struct SkTSpanBounded {
  69. SkTSpan* fBounded;
  70. SkTSpanBounded* fNext;
  71. };
  72. class SkTSpan {
  73. public:
  74. SkTSpan(const SkTCurve& curve, SkArenaAlloc& heap) {
  75. fPart = curve.make(heap);
  76. }
  77. void addBounded(SkTSpan* , SkArenaAlloc* );
  78. double closestBoundedT(const SkDPoint& pt) const;
  79. bool contains(double t) const;
  80. void debugInit(const SkTCurve& curve, SkArenaAlloc& heap) {
  81. #ifdef SK_DEBUG
  82. SkTCurve* dummy = curve.make(heap);
  83. dummy->debugInit();
  84. init(*dummy);
  85. initBounds(*dummy);
  86. fCoinStart.init();
  87. fCoinEnd.init();
  88. #endif
  89. }
  90. const SkTSect* debugOpp() const;
  91. #ifdef SK_DEBUG
  92. void debugSetGlobalState(SkOpGlobalState* state) {
  93. fDebugGlobalState = state;
  94. }
  95. const SkTSpan* debugSpan(int ) const;
  96. const SkTSpan* debugT(double t) const;
  97. bool debugIsBefore(const SkTSpan* span) const;
  98. #endif
  99. void dump() const;
  100. void dumpAll() const;
  101. void dumpBounded(int id) const;
  102. void dumpBounds() const;
  103. void dumpCoin() const;
  104. double endT() const {
  105. return fEndT;
  106. }
  107. SkTSpan* findOppSpan(const SkTSpan* opp) const;
  108. SkTSpan* findOppT(double t) const {
  109. SkTSpan* result = oppT(t);
  110. SkOPASSERT(result);
  111. return result;
  112. }
  113. SkDEBUGCODE(SkOpGlobalState* globalState() const { return fDebugGlobalState; })
  114. bool hasOppT(double t) const {
  115. return SkToBool(oppT(t));
  116. }
  117. int hullsIntersect(SkTSpan* span, bool* start, bool* oppStart);
  118. void init(const SkTCurve& );
  119. bool initBounds(const SkTCurve& );
  120. bool isBounded() const {
  121. return fBounded != nullptr;
  122. }
  123. bool linearsIntersect(SkTSpan* span);
  124. double linearT(const SkDPoint& ) const;
  125. void markCoincident() {
  126. fCoinStart.markCoincident();
  127. fCoinEnd.markCoincident();
  128. }
  129. const SkTSpan* next() const {
  130. return fNext;
  131. }
  132. bool onlyEndPointsInCommon(const SkTSpan* opp, bool* start,
  133. bool* oppStart, bool* ptsInCommon);
  134. const SkTCurve& part() const {
  135. return *fPart;
  136. }
  137. int pointCount() const {
  138. return fPart->pointCount();
  139. }
  140. const SkDPoint& pointFirst() const {
  141. return (*fPart)[0];
  142. }
  143. const SkDPoint& pointLast() const {
  144. return (*fPart)[fPart->pointLast()];
  145. }
  146. bool removeAllBounded();
  147. bool removeBounded(const SkTSpan* opp);
  148. void reset() {
  149. fBounded = nullptr;
  150. }
  151. void resetBounds(const SkTCurve& curve) {
  152. fIsLinear = fIsLine = false;
  153. initBounds(curve);
  154. }
  155. bool split(SkTSpan* work, SkArenaAlloc* heap) {
  156. return splitAt(work, (work->fStartT + work->fEndT) * 0.5, heap);
  157. }
  158. bool splitAt(SkTSpan* work, double t, SkArenaAlloc* heap);
  159. double startT() const {
  160. return fStartT;
  161. }
  162. private:
  163. // implementation is for testing only
  164. int debugID() const {
  165. return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
  166. }
  167. void dumpID() const;
  168. int hullCheck(const SkTSpan* opp, bool* start, bool* oppStart);
  169. int linearIntersects(const SkTCurve& ) const;
  170. SkTSpan* oppT(double t) const;
  171. void validate() const;
  172. void validateBounded() const;
  173. void validatePerpT(double oppT) const;
  174. void validatePerpPt(double t, const SkDPoint& ) const;
  175. SkTCurve* fPart;
  176. SkTCoincident fCoinStart;
  177. SkTCoincident fCoinEnd;
  178. SkTSpanBounded* fBounded;
  179. SkTSpan* fPrev;
  180. SkTSpan* fNext;
  181. SkDRect fBounds;
  182. double fStartT;
  183. double fEndT;
  184. double fBoundsMax;
  185. SkOpDebugBool fCollapsed;
  186. SkOpDebugBool fHasPerp;
  187. SkOpDebugBool fIsLinear;
  188. SkOpDebugBool fIsLine;
  189. SkOpDebugBool fDeleted;
  190. SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
  191. SkDEBUGCODE(SkTSect* fDebugSect);
  192. PATH_OPS_DEBUG_T_SECT_CODE(int fID);
  193. friend class SkTSect;
  194. };
  195. class SkTSect {
  196. public:
  197. SkTSect(const SkTCurve& c
  198. SkDEBUGPARAMS(SkOpGlobalState* ) PATH_OPS_DEBUG_T_SECT_PARAMS(int id));
  199. static void BinarySearch(SkTSect* sect1, SkTSect* sect2,
  200. SkIntersections* intersections);
  201. SkDEBUGCODE(SkOpGlobalState* globalState() { return fDebugGlobalState; })
  202. bool hasBounded(const SkTSpan* ) const;
  203. const SkTSect* debugOpp() const {
  204. return SkDEBUGRELEASE(fOppSect, nullptr);
  205. }
  206. #ifdef SK_DEBUG
  207. const SkTSpan* debugSpan(int id) const;
  208. const SkTSpan* debugT(double t) const;
  209. #endif
  210. void dump() const;
  211. void dumpBoth(SkTSect* ) const;
  212. void dumpBounded(int id) const;
  213. void dumpBounds() const;
  214. void dumpCoin() const;
  215. void dumpCoinCurves() const;
  216. void dumpCurves() const;
  217. private:
  218. enum {
  219. kZeroS1Set = 1,
  220. kOneS1Set = 2,
  221. kZeroS2Set = 4,
  222. kOneS2Set = 8
  223. };
  224. SkTSpan* addFollowing(SkTSpan* prior);
  225. void addForPerp(SkTSpan* span, double t);
  226. SkTSpan* addOne();
  227. SkTSpan* addSplitAt(SkTSpan* span, double t) {
  228. SkTSpan* result = this->addOne();
  229. SkDEBUGCODE(result->debugSetGlobalState(this->globalState()));
  230. result->splitAt(span, t, &fHeap);
  231. result->initBounds(fCurve);
  232. span->initBounds(fCurve);
  233. return result;
  234. }
  235. bool binarySearchCoin(SkTSect* , double tStart, double tStep, double* t,
  236. double* oppT, SkTSpan** oppFirst);
  237. SkTSpan* boundsMax();
  238. bool coincidentCheck(SkTSect* sect2);
  239. void coincidentForce(SkTSect* sect2, double start1s, double start1e);
  240. bool coincidentHasT(double t);
  241. int collapsed() const;
  242. void computePerpendiculars(SkTSect* sect2, SkTSpan* first,
  243. SkTSpan* last);
  244. int countConsecutiveSpans(SkTSpan* first,
  245. SkTSpan** last) const;
  246. int debugID() const {
  247. return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1);
  248. }
  249. bool deleteEmptySpans();
  250. void dumpCommon(const SkTSpan* ) const;
  251. void dumpCommonCurves(const SkTSpan* ) const;
  252. static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2,
  253. SkIntersections* );
  254. bool extractCoincident(SkTSect* sect2, SkTSpan* first,
  255. SkTSpan* last, SkTSpan** result);
  256. SkTSpan* findCoincidentRun(SkTSpan* first, SkTSpan** lastPtr);
  257. int intersects(SkTSpan* span, SkTSect* opp,
  258. SkTSpan* oppSpan, int* oppResult);
  259. bool isParallel(const SkDLine& thisLine, const SkTSect* opp) const;
  260. int linesIntersect(SkTSpan* span, SkTSect* opp,
  261. SkTSpan* oppSpan, SkIntersections* );
  262. bool markSpanGone(SkTSpan* span);
  263. bool matchedDirection(double t, const SkTSect* sect2, double t2) const;
  264. void matchedDirCheck(double t, const SkTSect* sect2, double t2,
  265. bool* calcMatched, bool* oppMatched) const;
  266. void mergeCoincidence(SkTSect* sect2);
  267. const SkDPoint& pointLast() const {
  268. return fCurve[fCurve.pointLast()];
  269. }
  270. SkTSpan* prev(SkTSpan* ) const;
  271. bool removeByPerpendicular(SkTSect* opp);
  272. void recoverCollapsed();
  273. bool removeCoincident(SkTSpan* span, bool isBetween);
  274. void removeAllBut(const SkTSpan* keep, SkTSpan* span,
  275. SkTSect* opp);
  276. bool removeSpan(SkTSpan* span);
  277. void removeSpanRange(SkTSpan* first, SkTSpan* last);
  278. bool removeSpans(SkTSpan* span, SkTSect* opp);
  279. void removedEndCheck(SkTSpan* span);
  280. void resetRemovedEnds() {
  281. fRemovedStartT = fRemovedEndT = false;
  282. }
  283. SkTSpan* spanAtT(double t, SkTSpan** priorSpan);
  284. SkTSpan* tail();
  285. bool trim(SkTSpan* span, SkTSect* opp);
  286. bool unlinkSpan(SkTSpan* span);
  287. bool updateBounded(SkTSpan* first, SkTSpan* last,
  288. SkTSpan* oppFirst);
  289. void validate() const;
  290. void validateBounded() const;
  291. const SkTCurve& fCurve;
  292. SkSTArenaAlloc<1024> fHeap;
  293. SkTSpan* fHead;
  294. SkTSpan* fCoincident;
  295. SkTSpan* fDeleted;
  296. int fActiveCount;
  297. bool fRemovedStartT;
  298. bool fRemovedEndT;
  299. bool fHung;
  300. SkDEBUGCODE(SkOpGlobalState* fDebugGlobalState);
  301. SkDEBUGCODE(SkTSect* fOppSect);
  302. PATH_OPS_DEBUG_T_SECT_CODE(int fID);
  303. PATH_OPS_DEBUG_T_SECT_CODE(int fDebugCount);
  304. #if DEBUG_T_SECT
  305. int fDebugAllocatedCount;
  306. #endif
  307. friend class SkTSpan;
  308. };
  309. #endif