SkPathOpsCurve.h 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421
  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 SkPathOpsCurve_DEFINE
  8. #define SkPathOpsCurve_DEFINE
  9. #include "src/pathops/SkIntersections.h"
  10. #ifndef SK_RELEASE
  11. #include "include/core/SkPath.h"
  12. #endif
  13. struct SkPathOpsBounds;
  14. struct SkOpCurve {
  15. SkPoint fPts[4];
  16. SkScalar fWeight;
  17. SkDEBUGCODE(SkPath::Verb fVerb);
  18. const SkPoint& operator[](int n) const {
  19. SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
  20. return fPts[n];
  21. }
  22. void dump() const;
  23. void set(const SkDQuad& quad) {
  24. for (int index = 0; index < SkDQuad::kPointCount; ++index) {
  25. fPts[index] = quad[index].asSkPoint();
  26. }
  27. SkDEBUGCODE(fWeight = 1);
  28. SkDEBUGCODE(fVerb = SkPath::kQuad_Verb);
  29. }
  30. void set(const SkDCubic& cubic) {
  31. for (int index = 0; index < SkDCubic::kPointCount; ++index) {
  32. fPts[index] = cubic[index].asSkPoint();
  33. }
  34. SkDEBUGCODE(fWeight = 1);
  35. SkDEBUGCODE(fVerb = SkPath::kCubic_Verb);
  36. }
  37. };
  38. struct SkDCurve {
  39. union {
  40. SkDLine fLine;
  41. SkDQuad fQuad;
  42. SkDConic fConic;
  43. SkDCubic fCubic;
  44. };
  45. SkDEBUGCODE(SkPath::Verb fVerb);
  46. const SkDPoint& operator[](int n) const {
  47. SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
  48. return fCubic[n];
  49. }
  50. SkDPoint& operator[](int n) {
  51. SkASSERT(n >= 0 && n <= SkPathOpsVerbToPoints(fVerb));
  52. return fCubic[n];
  53. }
  54. SkDPoint conicTop(const SkPoint curve[3], SkScalar curveWeight,
  55. double s, double e, double* topT);
  56. SkDPoint cubicTop(const SkPoint curve[4], SkScalar , double s, double e, double* topT);
  57. void dump() const;
  58. void dumpID(int ) const;
  59. SkDPoint lineTop(const SkPoint[2], SkScalar , double , double , double* topT);
  60. double nearPoint(SkPath::Verb verb, const SkDPoint& xy, const SkDPoint& opp) const;
  61. void offset(SkPath::Verb verb, const SkDVector& );
  62. SkDPoint quadTop(const SkPoint curve[3], SkScalar , double s, double e, double* topT);
  63. void setConicBounds(const SkPoint curve[3], SkScalar curveWeight,
  64. double s, double e, SkPathOpsBounds* );
  65. void setCubicBounds(const SkPoint curve[4], SkScalar ,
  66. double s, double e, SkPathOpsBounds* );
  67. void setQuadBounds(const SkPoint curve[3], SkScalar ,
  68. double s, double e, SkPathOpsBounds*);
  69. };
  70. class SkDCurveSweep {
  71. public:
  72. bool isCurve() const { return fIsCurve; }
  73. bool isOrdered() const { return fOrdered; }
  74. void setCurveHullSweep(SkPath::Verb verb);
  75. SkDCurve fCurve;
  76. SkDVector fSweep[2];
  77. private:
  78. bool fIsCurve;
  79. bool fOrdered; // cleared when a cubic's control point isn't between the sweep vectors
  80. };
  81. extern SkDPoint (SkDCurve::* const Top[])(const SkPoint curve[], SkScalar cWeight,
  82. double tStart, double tEnd, double* topT);
  83. static SkDPoint dline_xy_at_t(const SkPoint a[2], SkScalar , double t) {
  84. SkDLine line;
  85. line.set(a);
  86. return line.ptAtT(t);
  87. }
  88. static SkDPoint dquad_xy_at_t(const SkPoint a[3], SkScalar , double t) {
  89. SkDQuad quad;
  90. quad.set(a);
  91. return quad.ptAtT(t);
  92. }
  93. static SkDPoint dconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
  94. SkDConic conic;
  95. conic.set(a, weight);
  96. return conic.ptAtT(t);
  97. }
  98. static SkDPoint dcubic_xy_at_t(const SkPoint a[4], SkScalar , double t) {
  99. SkDCubic cubic;
  100. cubic.set(a);
  101. return cubic.ptAtT(t);
  102. }
  103. static SkDPoint (* const CurveDPointAtT[])(const SkPoint[], SkScalar , double ) = {
  104. nullptr,
  105. dline_xy_at_t,
  106. dquad_xy_at_t,
  107. dconic_xy_at_t,
  108. dcubic_xy_at_t
  109. };
  110. static SkDPoint ddline_xy_at_t(const SkDCurve& c, double t) {
  111. return c.fLine.ptAtT(t);
  112. }
  113. static SkDPoint ddquad_xy_at_t(const SkDCurve& c, double t) {
  114. return c.fQuad.ptAtT(t);
  115. }
  116. static SkDPoint ddconic_xy_at_t(const SkDCurve& c, double t) {
  117. return c.fConic.ptAtT(t);
  118. }
  119. static SkDPoint ddcubic_xy_at_t(const SkDCurve& c, double t) {
  120. return c.fCubic.ptAtT(t);
  121. }
  122. static SkDPoint (* const CurveDDPointAtT[])(const SkDCurve& , double ) = {
  123. nullptr,
  124. ddline_xy_at_t,
  125. ddquad_xy_at_t,
  126. ddconic_xy_at_t,
  127. ddcubic_xy_at_t
  128. };
  129. static SkPoint fline_xy_at_t(const SkPoint a[2], SkScalar weight, double t) {
  130. return dline_xy_at_t(a, weight, t).asSkPoint();
  131. }
  132. static SkPoint fquad_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
  133. return dquad_xy_at_t(a, weight, t).asSkPoint();
  134. }
  135. static SkPoint fconic_xy_at_t(const SkPoint a[3], SkScalar weight, double t) {
  136. return dconic_xy_at_t(a, weight, t).asSkPoint();
  137. }
  138. static SkPoint fcubic_xy_at_t(const SkPoint a[4], SkScalar weight, double t) {
  139. return dcubic_xy_at_t(a, weight, t).asSkPoint();
  140. }
  141. static SkPoint (* const CurvePointAtT[])(const SkPoint[], SkScalar , double ) = {
  142. nullptr,
  143. fline_xy_at_t,
  144. fquad_xy_at_t,
  145. fconic_xy_at_t,
  146. fcubic_xy_at_t
  147. };
  148. static SkDVector dline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) {
  149. SkDLine line;
  150. line.set(a);
  151. return line[1] - line[0];
  152. }
  153. static SkDVector dquad_dxdy_at_t(const SkPoint a[3], SkScalar , double t) {
  154. SkDQuad quad;
  155. quad.set(a);
  156. return quad.dxdyAtT(t);
  157. }
  158. static SkDVector dconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
  159. SkDConic conic;
  160. conic.set(a, weight);
  161. return conic.dxdyAtT(t);
  162. }
  163. static SkDVector dcubic_dxdy_at_t(const SkPoint a[4], SkScalar , double t) {
  164. SkDCubic cubic;
  165. cubic.set(a);
  166. return cubic.dxdyAtT(t);
  167. }
  168. static SkDVector (* const CurveDSlopeAtT[])(const SkPoint[], SkScalar , double ) = {
  169. nullptr,
  170. dline_dxdy_at_t,
  171. dquad_dxdy_at_t,
  172. dconic_dxdy_at_t,
  173. dcubic_dxdy_at_t
  174. };
  175. static SkDVector ddline_dxdy_at_t(const SkDCurve& c, double ) {
  176. return c.fLine.fPts[1] - c.fLine.fPts[0];
  177. }
  178. static SkDVector ddquad_dxdy_at_t(const SkDCurve& c, double t) {
  179. return c.fQuad.dxdyAtT(t);
  180. }
  181. static SkDVector ddconic_dxdy_at_t(const SkDCurve& c, double t) {
  182. return c.fConic.dxdyAtT(t);
  183. }
  184. static SkDVector ddcubic_dxdy_at_t(const SkDCurve& c, double t) {
  185. return c.fCubic.dxdyAtT(t);
  186. }
  187. static SkDVector (* const CurveDDSlopeAtT[])(const SkDCurve& , double ) = {
  188. nullptr,
  189. ddline_dxdy_at_t,
  190. ddquad_dxdy_at_t,
  191. ddconic_dxdy_at_t,
  192. ddcubic_dxdy_at_t
  193. };
  194. static SkVector fline_dxdy_at_t(const SkPoint a[2], SkScalar , double ) {
  195. return a[1] - a[0];
  196. }
  197. static SkVector fquad_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
  198. return dquad_dxdy_at_t(a, weight, t).asSkVector();
  199. }
  200. static SkVector fconic_dxdy_at_t(const SkPoint a[3], SkScalar weight, double t) {
  201. return dconic_dxdy_at_t(a, weight, t).asSkVector();
  202. }
  203. static SkVector fcubic_dxdy_at_t(const SkPoint a[4], SkScalar weight, double t) {
  204. return dcubic_dxdy_at_t(a, weight, t).asSkVector();
  205. }
  206. static SkVector (* const CurveSlopeAtT[])(const SkPoint[], SkScalar , double ) = {
  207. nullptr,
  208. fline_dxdy_at_t,
  209. fquad_dxdy_at_t,
  210. fconic_dxdy_at_t,
  211. fcubic_dxdy_at_t
  212. };
  213. static bool line_is_vertical(const SkPoint a[2], SkScalar , double startT, double endT) {
  214. SkDLine line;
  215. line.set(a);
  216. SkDPoint dst[2] = { line.ptAtT(startT), line.ptAtT(endT) };
  217. return AlmostEqualUlps(dst[0].fX, dst[1].fX);
  218. }
  219. static bool quad_is_vertical(const SkPoint a[3], SkScalar , double startT, double endT) {
  220. SkDQuad quad;
  221. quad.set(a);
  222. SkDQuad dst = quad.subDivide(startT, endT);
  223. return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
  224. }
  225. static bool conic_is_vertical(const SkPoint a[3], SkScalar weight, double startT, double endT) {
  226. SkDConic conic;
  227. conic.set(a, weight);
  228. SkDConic dst = conic.subDivide(startT, endT);
  229. return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX);
  230. }
  231. static bool cubic_is_vertical(const SkPoint a[4], SkScalar , double startT, double endT) {
  232. SkDCubic cubic;
  233. cubic.set(a);
  234. SkDCubic dst = cubic.subDivide(startT, endT);
  235. return AlmostEqualUlps(dst[0].fX, dst[1].fX) && AlmostEqualUlps(dst[1].fX, dst[2].fX)
  236. && AlmostEqualUlps(dst[2].fX, dst[3].fX);
  237. }
  238. static bool (* const CurveIsVertical[])(const SkPoint[], SkScalar , double , double) = {
  239. nullptr,
  240. line_is_vertical,
  241. quad_is_vertical,
  242. conic_is_vertical,
  243. cubic_is_vertical
  244. };
  245. static void line_intersect_ray(const SkPoint a[2], SkScalar , const SkDLine& ray,
  246. SkIntersections* i) {
  247. SkDLine line;
  248. line.set(a);
  249. i->intersectRay(line, ray);
  250. }
  251. static void quad_intersect_ray(const SkPoint a[3], SkScalar , const SkDLine& ray,
  252. SkIntersections* i) {
  253. SkDQuad quad;
  254. quad.set(a);
  255. i->intersectRay(quad, ray);
  256. }
  257. static void conic_intersect_ray(const SkPoint a[3], SkScalar weight, const SkDLine& ray,
  258. SkIntersections* i) {
  259. SkDConic conic;
  260. conic.set(a, weight);
  261. i->intersectRay(conic, ray);
  262. }
  263. static void cubic_intersect_ray(const SkPoint a[4], SkScalar , const SkDLine& ray,
  264. SkIntersections* i) {
  265. SkDCubic cubic;
  266. cubic.set(a);
  267. i->intersectRay(cubic, ray);
  268. }
  269. static void (* const CurveIntersectRay[])(const SkPoint[] , SkScalar , const SkDLine& ,
  270. SkIntersections* ) = {
  271. nullptr,
  272. line_intersect_ray,
  273. quad_intersect_ray,
  274. conic_intersect_ray,
  275. cubic_intersect_ray
  276. };
  277. static void dline_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
  278. i->intersectRay(c.fLine, ray);
  279. }
  280. static void dquad_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
  281. i->intersectRay(c.fQuad, ray);
  282. }
  283. static void dconic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
  284. i->intersectRay(c.fConic, ray);
  285. }
  286. static void dcubic_intersect_ray(const SkDCurve& c, const SkDLine& ray, SkIntersections* i) {
  287. i->intersectRay(c.fCubic, ray);
  288. }
  289. static void (* const CurveDIntersectRay[])(const SkDCurve& , const SkDLine& , SkIntersections* ) = {
  290. nullptr,
  291. dline_intersect_ray,
  292. dquad_intersect_ray,
  293. dconic_intersect_ray,
  294. dcubic_intersect_ray
  295. };
  296. static int line_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) {
  297. if (a[0].fY == a[1].fY) {
  298. return false;
  299. }
  300. SkDLine line;
  301. roots[0] = SkIntersections::HorizontalIntercept(line.set(a), y);
  302. return between(0, roots[0], 1);
  303. }
  304. static int line_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) {
  305. if (a[0].fX == a[1].fX) {
  306. return false;
  307. }
  308. SkDLine line;
  309. roots[0] = SkIntersections::VerticalIntercept(line.set(a), x);
  310. return between(0, roots[0], 1);
  311. }
  312. static int quad_intercept_h(const SkPoint a[2], SkScalar , SkScalar y, double* roots) {
  313. SkDQuad quad;
  314. return SkIntersections::HorizontalIntercept(quad.set(a), y, roots);
  315. }
  316. static int quad_intercept_v(const SkPoint a[2], SkScalar , SkScalar x, double* roots) {
  317. SkDQuad quad;
  318. return SkIntersections::VerticalIntercept(quad.set(a), x, roots);
  319. }
  320. static int conic_intercept_h(const SkPoint a[2], SkScalar w, SkScalar y, double* roots) {
  321. SkDConic conic;
  322. return SkIntersections::HorizontalIntercept(conic.set(a, w), y, roots);
  323. }
  324. static int conic_intercept_v(const SkPoint a[2], SkScalar w, SkScalar x, double* roots) {
  325. SkDConic conic;
  326. return SkIntersections::VerticalIntercept(conic.set(a, w), x, roots);
  327. }
  328. static int cubic_intercept_h(const SkPoint a[3], SkScalar , SkScalar y, double* roots) {
  329. SkDCubic cubic;
  330. return cubic.set(a).horizontalIntersect(y, roots);
  331. }
  332. static int cubic_intercept_v(const SkPoint a[3], SkScalar , SkScalar x, double* roots) {
  333. SkDCubic cubic;
  334. return cubic.set(a).verticalIntersect(x, roots);
  335. }
  336. static int (* const CurveIntercept[])(const SkPoint[] , SkScalar , SkScalar , double* ) = {
  337. nullptr,
  338. nullptr,
  339. line_intercept_h,
  340. line_intercept_v,
  341. quad_intercept_h,
  342. quad_intercept_v,
  343. conic_intercept_h,
  344. conic_intercept_v,
  345. cubic_intercept_h,
  346. cubic_intercept_v,
  347. };
  348. #endif