SkIntersections.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333
  1. /*
  2. * Copyright 2012 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 SkIntersections_DEFINE
  8. #define SkIntersections_DEFINE
  9. #include "src/pathops/SkPathOpsConic.h"
  10. #include "src/pathops/SkPathOpsCubic.h"
  11. #include "src/pathops/SkPathOpsLine.h"
  12. #include "src/pathops/SkPathOpsPoint.h"
  13. #include "src/pathops/SkPathOpsQuad.h"
  14. class SkIntersections {
  15. public:
  16. SkIntersections(SkDEBUGCODE(SkOpGlobalState* globalState = nullptr))
  17. : fSwap(0)
  18. #ifdef SK_DEBUG
  19. SkDEBUGPARAMS(fDebugGlobalState(globalState))
  20. , fDepth(0)
  21. #endif
  22. {
  23. sk_bzero(fPt, sizeof(fPt));
  24. sk_bzero(fPt2, sizeof(fPt2));
  25. sk_bzero(fT, sizeof(fT));
  26. sk_bzero(fNearlySame, sizeof(fNearlySame));
  27. #if DEBUG_T_SECT_LOOP_COUNT
  28. sk_bzero(fDebugLoopCount, sizeof(fDebugLoopCount));
  29. #endif
  30. reset();
  31. fMax = 0; // require that the caller set the max
  32. }
  33. class TArray {
  34. public:
  35. explicit TArray(const double ts[10]) : fTArray(ts) {}
  36. double operator[](int n) const {
  37. return fTArray[n];
  38. }
  39. const double* fTArray;
  40. };
  41. TArray operator[](int n) const { return TArray(fT[n]); }
  42. void allowNear(bool nearAllowed) {
  43. fAllowNear = nearAllowed;
  44. }
  45. void clearCoincidence(int index) {
  46. SkASSERT(index >= 0);
  47. int bit = 1 << index;
  48. fIsCoincident[0] &= ~bit;
  49. fIsCoincident[1] &= ~bit;
  50. }
  51. int conicHorizontal(const SkPoint a[3], SkScalar weight, SkScalar left, SkScalar right,
  52. SkScalar y, bool flipped) {
  53. SkDConic conic;
  54. conic.set(a, weight);
  55. fMax = 2;
  56. return horizontal(conic, left, right, y, flipped);
  57. }
  58. int conicVertical(const SkPoint a[3], SkScalar weight, SkScalar top, SkScalar bottom,
  59. SkScalar x, bool flipped) {
  60. SkDConic conic;
  61. conic.set(a, weight);
  62. fMax = 2;
  63. return vertical(conic, top, bottom, x, flipped);
  64. }
  65. int conicLine(const SkPoint a[3], SkScalar weight, const SkPoint b[2]) {
  66. SkDConic conic;
  67. conic.set(a, weight);
  68. SkDLine line;
  69. line.set(b);
  70. fMax = 3; // 2; permit small coincident segment + non-coincident intersection
  71. return intersect(conic, line);
  72. }
  73. int cubicHorizontal(const SkPoint a[4], SkScalar left, SkScalar right, SkScalar y,
  74. bool flipped) {
  75. SkDCubic cubic;
  76. cubic.set(a);
  77. fMax = 3;
  78. return horizontal(cubic, left, right, y, flipped);
  79. }
  80. int cubicVertical(const SkPoint a[4], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
  81. SkDCubic cubic;
  82. cubic.set(a);
  83. fMax = 3;
  84. return vertical(cubic, top, bottom, x, flipped);
  85. }
  86. int cubicLine(const SkPoint a[4], const SkPoint b[2]) {
  87. SkDCubic cubic;
  88. cubic.set(a);
  89. SkDLine line;
  90. line.set(b);
  91. fMax = 3;
  92. return intersect(cubic, line);
  93. }
  94. #ifdef SK_DEBUG
  95. SkOpGlobalState* globalState() const { return fDebugGlobalState; }
  96. #endif
  97. bool hasT(double t) const {
  98. SkASSERT(t == 0 || t == 1);
  99. return fUsed > 0 && (t == 0 ? fT[0][0] == 0 : fT[0][fUsed - 1] == 1);
  100. }
  101. bool hasOppT(double t) const {
  102. SkASSERT(t == 0 || t == 1);
  103. return fUsed > 0 && (fT[1][0] == t || fT[1][fUsed - 1] == t);
  104. }
  105. int insertSwap(double one, double two, const SkDPoint& pt) {
  106. if (fSwap) {
  107. return insert(two, one, pt);
  108. } else {
  109. return insert(one, two, pt);
  110. }
  111. }
  112. bool isCoincident(int index) {
  113. return (fIsCoincident[0] & 1 << index) != 0;
  114. }
  115. int lineHorizontal(const SkPoint a[2], SkScalar left, SkScalar right, SkScalar y,
  116. bool flipped) {
  117. SkDLine line;
  118. line.set(a);
  119. fMax = 2;
  120. return horizontal(line, left, right, y, flipped);
  121. }
  122. int lineVertical(const SkPoint a[2], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
  123. SkDLine line;
  124. line.set(a);
  125. fMax = 2;
  126. return vertical(line, top, bottom, x, flipped);
  127. }
  128. int lineLine(const SkPoint a[2], const SkPoint b[2]) {
  129. SkDLine aLine, bLine;
  130. aLine.set(a);
  131. bLine.set(b);
  132. fMax = 2;
  133. return intersect(aLine, bLine);
  134. }
  135. bool nearlySame(int index) const {
  136. SkASSERT(index == 0 || index == 1);
  137. return fNearlySame[index];
  138. }
  139. const SkDPoint& pt(int index) const {
  140. return fPt[index];
  141. }
  142. const SkDPoint& pt2(int index) const {
  143. return fPt2[index];
  144. }
  145. int quadHorizontal(const SkPoint a[3], SkScalar left, SkScalar right, SkScalar y,
  146. bool flipped) {
  147. SkDQuad quad;
  148. quad.set(a);
  149. fMax = 2;
  150. return horizontal(quad, left, right, y, flipped);
  151. }
  152. int quadVertical(const SkPoint a[3], SkScalar top, SkScalar bottom, SkScalar x, bool flipped) {
  153. SkDQuad quad;
  154. quad.set(a);
  155. fMax = 2;
  156. return vertical(quad, top, bottom, x, flipped);
  157. }
  158. int quadLine(const SkPoint a[3], const SkPoint b[2]) {
  159. SkDQuad quad;
  160. quad.set(a);
  161. SkDLine line;
  162. line.set(b);
  163. return intersect(quad, line);
  164. }
  165. // leaves swap, max alone
  166. void reset() {
  167. fAllowNear = true;
  168. fUsed = 0;
  169. sk_bzero(fIsCoincident, sizeof(fIsCoincident));
  170. }
  171. void set(bool swap, int tIndex, double t) {
  172. fT[(int) swap][tIndex] = t;
  173. }
  174. void setMax(int max) {
  175. SkASSERT(max <= (int) SK_ARRAY_COUNT(fPt));
  176. fMax = max;
  177. }
  178. void swap() {
  179. fSwap ^= true;
  180. }
  181. bool swapped() const {
  182. return fSwap;
  183. }
  184. int used() const {
  185. return fUsed;
  186. }
  187. void downDepth() {
  188. SkASSERT(--fDepth >= 0);
  189. }
  190. bool unBumpT(int index) {
  191. SkASSERT(fUsed == 1);
  192. fT[0][index] = fT[0][index] * (1 + BUMP_EPSILON * 2) - BUMP_EPSILON;
  193. if (!between(0, fT[0][index], 1)) {
  194. fUsed = 0;
  195. return false;
  196. }
  197. return true;
  198. }
  199. void upDepth() {
  200. SkASSERT(++fDepth < 16);
  201. }
  202. void alignQuadPts(const SkPoint a[3], const SkPoint b[3]);
  203. int cleanUpCoincidence();
  204. int closestTo(double rangeStart, double rangeEnd, const SkDPoint& testPt, double* dist) const;
  205. void cubicInsert(double one, double two, const SkDPoint& pt, const SkDCubic& c1,
  206. const SkDCubic& c2);
  207. void flip();
  208. int horizontal(const SkDLine&, double left, double right, double y, bool flipped);
  209. int horizontal(const SkDQuad&, double left, double right, double y, bool flipped);
  210. int horizontal(const SkDQuad&, double left, double right, double y, double tRange[2]);
  211. int horizontal(const SkDCubic&, double y, double tRange[3]);
  212. int horizontal(const SkDConic&, double left, double right, double y, bool flipped);
  213. int horizontal(const SkDCubic&, double left, double right, double y, bool flipped);
  214. int horizontal(const SkDCubic&, double left, double right, double y, double tRange[3]);
  215. static double HorizontalIntercept(const SkDLine& line, double y);
  216. static int HorizontalIntercept(const SkDQuad& quad, SkScalar y, double* roots);
  217. static int HorizontalIntercept(const SkDConic& conic, SkScalar y, double* roots);
  218. // FIXME : does not respect swap
  219. int insert(double one, double two, const SkDPoint& pt);
  220. void insertNear(double one, double two, const SkDPoint& pt1, const SkDPoint& pt2);
  221. // start if index == 0 : end if index == 1
  222. int insertCoincident(double one, double two, const SkDPoint& pt);
  223. int intersect(const SkDLine&, const SkDLine&);
  224. int intersect(const SkDQuad&, const SkDLine&);
  225. int intersect(const SkDQuad&, const SkDQuad&);
  226. int intersect(const SkDConic&, const SkDLine&);
  227. int intersect(const SkDConic&, const SkDQuad&);
  228. int intersect(const SkDConic&, const SkDConic&);
  229. int intersect(const SkDCubic&, const SkDLine&);
  230. int intersect(const SkDCubic&, const SkDQuad&);
  231. int intersect(const SkDCubic&, const SkDConic&);
  232. int intersect(const SkDCubic&, const SkDCubic&);
  233. int intersectRay(const SkDLine&, const SkDLine&);
  234. int intersectRay(const SkDQuad&, const SkDLine&);
  235. int intersectRay(const SkDConic&, const SkDLine&);
  236. int intersectRay(const SkDCubic&, const SkDLine&);
  237. int intersectRay(const SkTCurve& tCurve, const SkDLine& line) {
  238. return tCurve.intersectRay(this, line);
  239. }
  240. void merge(const SkIntersections& , int , const SkIntersections& , int );
  241. int mostOutside(double rangeStart, double rangeEnd, const SkDPoint& origin) const;
  242. void removeOne(int index);
  243. void setCoincident(int index);
  244. int vertical(const SkDLine&, double top, double bottom, double x, bool flipped);
  245. int vertical(const SkDQuad&, double top, double bottom, double x, bool flipped);
  246. int vertical(const SkDConic&, double top, double bottom, double x, bool flipped);
  247. int vertical(const SkDCubic&, double top, double bottom, double x, bool flipped);
  248. static double VerticalIntercept(const SkDLine& line, double x);
  249. static int VerticalIntercept(const SkDQuad& quad, SkScalar x, double* roots);
  250. static int VerticalIntercept(const SkDConic& conic, SkScalar x, double* roots);
  251. int depth() const {
  252. #ifdef SK_DEBUG
  253. return fDepth;
  254. #else
  255. return 0;
  256. #endif
  257. }
  258. enum DebugLoop {
  259. kIterations_DebugLoop,
  260. kCoinCheck_DebugLoop,
  261. kComputePerp_DebugLoop,
  262. };
  263. void debugBumpLoopCount(DebugLoop );
  264. int debugCoincidentUsed() const;
  265. int debugLoopCount(DebugLoop ) const;
  266. void debugResetLoopCount();
  267. void dump() const; // implemented for testing only
  268. private:
  269. bool cubicCheckCoincidence(const SkDCubic& c1, const SkDCubic& c2);
  270. bool cubicExactEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2);
  271. void cubicNearEnd(const SkDCubic& cubic1, bool start, const SkDCubic& cubic2, const SkDRect& );
  272. void cleanUpParallelLines(bool parallel);
  273. void computePoints(const SkDLine& line, int used);
  274. SkDPoint fPt[13]; // FIXME: since scans store points as SkPoint, this should also
  275. SkDPoint fPt2[2]; // used by nearly same to store alternate intersection point
  276. double fT[2][13];
  277. uint16_t fIsCoincident[2]; // bit set for each curve's coincident T
  278. bool fNearlySame[2]; // true if end points nearly match
  279. unsigned char fUsed;
  280. unsigned char fMax;
  281. bool fAllowNear;
  282. bool fSwap;
  283. #ifdef SK_DEBUG
  284. SkOpGlobalState* fDebugGlobalState;
  285. int fDepth;
  286. #endif
  287. #if DEBUG_T_SECT_LOOP_COUNT
  288. int fDebugLoopCount[3];
  289. #endif
  290. };
  291. #endif