SkGeometry.h 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455
  1. /*
  2. * Copyright 2006 The Android Open Source Project
  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 SkGeometry_DEFINED
  8. #define SkGeometry_DEFINED
  9. #include "include/core/SkMatrix.h"
  10. #include "include/private/SkNx.h"
  11. static inline Sk2s from_point(const SkPoint& point) {
  12. return Sk2s::Load(&point);
  13. }
  14. static inline SkPoint to_point(const Sk2s& x) {
  15. SkPoint point;
  16. x.store(&point);
  17. return point;
  18. }
  19. static Sk2s times_2(const Sk2s& value) {
  20. return value + value;
  21. }
  22. /** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the
  23. equation.
  24. */
  25. int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]);
  26. ///////////////////////////////////////////////////////////////////////////////
  27. SkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t);
  28. SkPoint SkEvalQuadTangentAt(const SkPoint src[3], SkScalar t);
  29. /** Set pt to the point on the src quadratic specified by t. t must be
  30. 0 <= t <= 1.0
  31. */
  32. void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent = nullptr);
  33. /** Given a src quadratic bezier, chop it at the specified t value,
  34. where 0 < t < 1, and return the two new quadratics in dst:
  35. dst[0..2] and dst[2..4]
  36. */
  37. void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t);
  38. /** Given a src quadratic bezier, chop it at the specified t == 1/2,
  39. The new quads are returned in dst[0..2] and dst[2..4]
  40. */
  41. void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]);
  42. /** Given the 3 coefficients for a quadratic bezier (either X or Y values), look
  43. for extrema, and return the number of t-values that are found that represent
  44. these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the
  45. function returns 0.
  46. Returned count tValues[]
  47. 0 ignored
  48. 1 0 < tValues[0] < 1
  49. */
  50. int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]);
  51. /** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that
  52. the resulting beziers are monotonic in Y. This is called by the scan converter.
  53. Depending on what is returned, dst[] is treated as follows
  54. 0 dst[0..2] is the original quad
  55. 1 dst[0..2] and dst[2..4] are the two new quads
  56. */
  57. int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]);
  58. int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]);
  59. /** Given 3 points on a quadratic bezier, if the point of maximum
  60. curvature exists on the segment, returns the t value for this
  61. point along the curve. Otherwise it will return a value of 0.
  62. */
  63. SkScalar SkFindQuadMaxCurvature(const SkPoint src[3]);
  64. /** Given 3 points on a quadratic bezier, divide it into 2 quadratics
  65. if the point of maximum curvature exists on the quad segment.
  66. Depending on what is returned, dst[] is treated as follows
  67. 1 dst[0..2] is the original quad
  68. 2 dst[0..2] and dst[2..4] are the two new quads
  69. If dst == null, it is ignored and only the count is returned.
  70. */
  71. int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]);
  72. /** Given 3 points on a quadratic bezier, use degree elevation to
  73. convert it into the cubic fitting the same curve. The new cubic
  74. curve is returned in dst[0..3].
  75. */
  76. SK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]);
  77. ///////////////////////////////////////////////////////////////////////////////
  78. /** Set pt to the point on the src cubic specified by t. t must be
  79. 0 <= t <= 1.0
  80. */
  81. void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull,
  82. SkVector* tangentOrNull, SkVector* curvatureOrNull);
  83. /** Given a src cubic bezier, chop it at the specified t value,
  84. where 0 < t < 1, and return the two new cubics in dst:
  85. dst[0..3] and dst[3..6]
  86. */
  87. void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t);
  88. /** Given a src cubic bezier, chop it at the specified t values,
  89. where 0 < t < 1, and return the new cubics in dst:
  90. dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)]
  91. */
  92. void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[],
  93. int t_count);
  94. /** Given a src cubic bezier, chop it at the specified t == 1/2,
  95. The new cubics are returned in dst[0..3] and dst[3..6]
  96. */
  97. void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]);
  98. /** Given the 4 coefficients for a cubic bezier (either X or Y values), look
  99. for extrema, and return the number of t-values that are found that represent
  100. these extrema. If the cubic has no extrema betwee (0..1) exclusive, the
  101. function returns 0.
  102. Returned count tValues[]
  103. 0 ignored
  104. 1 0 < tValues[0] < 1
  105. 2 0 < tValues[0] < tValues[1] < 1
  106. */
  107. int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d,
  108. SkScalar tValues[2]);
  109. /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that
  110. the resulting beziers are monotonic in Y. This is called by the scan converter.
  111. Depending on what is returned, dst[] is treated as follows
  112. 0 dst[0..3] is the original cubic
  113. 1 dst[0..3] and dst[3..6] are the two new cubics
  114. 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics
  115. If dst == null, it is ignored and only the count is returned.
  116. */
  117. int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]);
  118. int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]);
  119. /** Given a cubic bezier, return 0, 1, or 2 t-values that represent the
  120. inflection points.
  121. */
  122. int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]);
  123. /** Return 1 for no chop, 2 for having chopped the cubic at a single
  124. inflection point, 3 for having chopped at 2 inflection points.
  125. dst will hold the resulting 1, 2, or 3 cubics.
  126. */
  127. int SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]);
  128. int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]);
  129. int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13],
  130. SkScalar tValues[3] = nullptr);
  131. /** Returns t value of cusp if cubic has one; returns -1 otherwise.
  132. */
  133. SkScalar SkFindCubicCusp(const SkPoint src[4]);
  134. bool SkChopMonoCubicAtX(SkPoint src[4], SkScalar y, SkPoint dst[7]);
  135. bool SkChopMonoCubicAtY(SkPoint src[4], SkScalar x, SkPoint dst[7]);
  136. enum class SkCubicType {
  137. kSerpentine,
  138. kLoop,
  139. kLocalCusp, // Cusp at a non-infinite parameter value with an inflection at t=infinity.
  140. kCuspAtInfinity, // Cusp with a cusp at t=infinity and a local inflection.
  141. kQuadratic,
  142. kLineOrPoint
  143. };
  144. static inline bool SkCubicIsDegenerate(SkCubicType type) {
  145. switch (type) {
  146. case SkCubicType::kSerpentine:
  147. case SkCubicType::kLoop:
  148. case SkCubicType::kLocalCusp:
  149. case SkCubicType::kCuspAtInfinity:
  150. return false;
  151. case SkCubicType::kQuadratic:
  152. case SkCubicType::kLineOrPoint:
  153. return true;
  154. }
  155. SK_ABORT("Invalid SkCubicType");
  156. return true;
  157. }
  158. static inline const char* SkCubicTypeName(SkCubicType type) {
  159. switch (type) {
  160. case SkCubicType::kSerpentine: return "kSerpentine";
  161. case SkCubicType::kLoop: return "kLoop";
  162. case SkCubicType::kLocalCusp: return "kLocalCusp";
  163. case SkCubicType::kCuspAtInfinity: return "kCuspAtInfinity";
  164. case SkCubicType::kQuadratic: return "kQuadratic";
  165. case SkCubicType::kLineOrPoint: return "kLineOrPoint";
  166. }
  167. SK_ABORT("Invalid SkCubicType");
  168. return "";
  169. }
  170. /** Returns the cubic classification.
  171. t[],s[] are set to the two homogeneous parameter values at which points the lines L & M
  172. intersect with K, sorted from smallest to largest and oriented so positive values of the
  173. implicit are on the "left" side. For a serpentine curve they are the inflection points. For a
  174. loop they are the double point. For a local cusp, they are both equal and denote the cusp point.
  175. For a cusp at an infinite parameter value, one will be the local inflection point and the other
  176. +inf (t,s = 1,0). If the curve is degenerate (i.e. quadratic or linear) they are both set to a
  177. parameter value of +inf (t,s = 1,0).
  178. d[] is filled with the cubic inflection function coefficients. See "Resolution Independent
  179. Curve Rendering using Programmable Graphics Hardware", 4.2 Curve Categorization:
  180. If the input points contain infinities or NaN, the return values are undefined.
  181. https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
  182. */
  183. SkCubicType SkClassifyCubic(const SkPoint p[4], double t[2] = nullptr, double s[2] = nullptr,
  184. double d[4] = nullptr);
  185. ///////////////////////////////////////////////////////////////////////////////
  186. enum SkRotationDirection {
  187. kCW_SkRotationDirection,
  188. kCCW_SkRotationDirection
  189. };
  190. struct SkConic {
  191. SkConic() {}
  192. SkConic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
  193. fPts[0] = p0;
  194. fPts[1] = p1;
  195. fPts[2] = p2;
  196. fW = w;
  197. }
  198. SkConic(const SkPoint pts[3], SkScalar w) {
  199. memcpy(fPts, pts, sizeof(fPts));
  200. fW = w;
  201. }
  202. SkPoint fPts[3];
  203. SkScalar fW;
  204. void set(const SkPoint pts[3], SkScalar w) {
  205. memcpy(fPts, pts, 3 * sizeof(SkPoint));
  206. fW = w;
  207. }
  208. void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
  209. fPts[0] = p0;
  210. fPts[1] = p1;
  211. fPts[2] = p2;
  212. fW = w;
  213. }
  214. /**
  215. * Given a t-value [0...1] return its position and/or tangent.
  216. * If pos is not null, return its position at the t-value.
  217. * If tangent is not null, return its tangent at the t-value. NOTE the
  218. * tangent value's length is arbitrary, and only its direction should
  219. * be used.
  220. */
  221. void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = nullptr) const;
  222. bool SK_WARN_UNUSED_RESULT chopAt(SkScalar t, SkConic dst[2]) const;
  223. void chopAt(SkScalar t1, SkScalar t2, SkConic* dst) const;
  224. void chop(SkConic dst[2]) const;
  225. SkPoint evalAt(SkScalar t) const;
  226. SkVector evalTangentAt(SkScalar t) const;
  227. void computeAsQuadError(SkVector* err) const;
  228. bool asQuadTol(SkScalar tol) const;
  229. /**
  230. * return the power-of-2 number of quads needed to approximate this conic
  231. * with a sequence of quads. Will be >= 0.
  232. */
  233. int SK_API computeQuadPOW2(SkScalar tol) const;
  234. /**
  235. * Chop this conic into N quads, stored continguously in pts[], where
  236. * N = 1 << pow2. The amount of storage needed is (1 + 2 * N)
  237. */
  238. int SK_API SK_WARN_UNUSED_RESULT chopIntoQuadsPOW2(SkPoint pts[], int pow2) const;
  239. bool findXExtrema(SkScalar* t) const;
  240. bool findYExtrema(SkScalar* t) const;
  241. bool chopAtXExtrema(SkConic dst[2]) const;
  242. bool chopAtYExtrema(SkConic dst[2]) const;
  243. void computeTightBounds(SkRect* bounds) const;
  244. void computeFastBounds(SkRect* bounds) const;
  245. /** Find the parameter value where the conic takes on its maximum curvature.
  246. *
  247. * @param t output scalar for max curvature. Will be unchanged if
  248. * max curvature outside 0..1 range.
  249. *
  250. * @return true if max curvature found inside 0..1 range, false otherwise
  251. */
  252. // bool findMaxCurvature(SkScalar* t) const; // unimplemented
  253. static SkScalar TransformW(const SkPoint[3], SkScalar w, const SkMatrix&);
  254. enum {
  255. kMaxConicsForArc = 5
  256. };
  257. static int BuildUnitArc(const SkVector& start, const SkVector& stop, SkRotationDirection,
  258. const SkMatrix*, SkConic conics[kMaxConicsForArc]);
  259. };
  260. // inline helpers are contained in a namespace to avoid external leakage to fragile SkNx members
  261. namespace { // NOLINT(google-build-namespaces)
  262. /**
  263. * use for : eval(t) == A * t^2 + B * t + C
  264. */
  265. struct SkQuadCoeff {
  266. SkQuadCoeff() {}
  267. SkQuadCoeff(const Sk2s& A, const Sk2s& B, const Sk2s& C)
  268. : fA(A)
  269. , fB(B)
  270. , fC(C)
  271. {
  272. }
  273. SkQuadCoeff(const SkPoint src[3]) {
  274. fC = from_point(src[0]);
  275. Sk2s P1 = from_point(src[1]);
  276. Sk2s P2 = from_point(src[2]);
  277. fB = times_2(P1 - fC);
  278. fA = P2 - times_2(P1) + fC;
  279. }
  280. Sk2s eval(SkScalar t) {
  281. Sk2s tt(t);
  282. return eval(tt);
  283. }
  284. Sk2s eval(const Sk2s& tt) {
  285. return (fA * tt + fB) * tt + fC;
  286. }
  287. Sk2s fA;
  288. Sk2s fB;
  289. Sk2s fC;
  290. };
  291. struct SkConicCoeff {
  292. SkConicCoeff(const SkConic& conic) {
  293. Sk2s p0 = from_point(conic.fPts[0]);
  294. Sk2s p1 = from_point(conic.fPts[1]);
  295. Sk2s p2 = from_point(conic.fPts[2]);
  296. Sk2s ww(conic.fW);
  297. Sk2s p1w = p1 * ww;
  298. fNumer.fC = p0;
  299. fNumer.fA = p2 - times_2(p1w) + p0;
  300. fNumer.fB = times_2(p1w - p0);
  301. fDenom.fC = Sk2s(1);
  302. fDenom.fB = times_2(ww - fDenom.fC);
  303. fDenom.fA = Sk2s(0) - fDenom.fB;
  304. }
  305. Sk2s eval(SkScalar t) {
  306. Sk2s tt(t);
  307. Sk2s numer = fNumer.eval(tt);
  308. Sk2s denom = fDenom.eval(tt);
  309. return numer / denom;
  310. }
  311. SkQuadCoeff fNumer;
  312. SkQuadCoeff fDenom;
  313. };
  314. struct SkCubicCoeff {
  315. SkCubicCoeff(const SkPoint src[4]) {
  316. Sk2s P0 = from_point(src[0]);
  317. Sk2s P1 = from_point(src[1]);
  318. Sk2s P2 = from_point(src[2]);
  319. Sk2s P3 = from_point(src[3]);
  320. Sk2s three(3);
  321. fA = P3 + three * (P1 - P2) - P0;
  322. fB = three * (P2 - times_2(P1) + P0);
  323. fC = three * (P1 - P0);
  324. fD = P0;
  325. }
  326. Sk2s eval(SkScalar t) {
  327. Sk2s tt(t);
  328. return eval(tt);
  329. }
  330. Sk2s eval(const Sk2s& t) {
  331. return ((fA * t + fB) * t + fC) * t + fD;
  332. }
  333. Sk2s fA;
  334. Sk2s fB;
  335. Sk2s fC;
  336. Sk2s fD;
  337. };
  338. }
  339. #include "include/private/SkTemplates.h"
  340. /**
  341. * Help class to allocate storage for approximating a conic with N quads.
  342. */
  343. class SkAutoConicToQuads {
  344. public:
  345. SkAutoConicToQuads() : fQuadCount(0) {}
  346. /**
  347. * Given a conic and a tolerance, return the array of points for the
  348. * approximating quad(s). Call countQuads() to know the number of quads
  349. * represented in these points.
  350. *
  351. * The quads are allocated to share end-points. e.g. if there are 4 quads,
  352. * there will be 9 points allocated as follows
  353. * quad[0] == pts[0..2]
  354. * quad[1] == pts[2..4]
  355. * quad[2] == pts[4..6]
  356. * quad[3] == pts[6..8]
  357. */
  358. const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) {
  359. int pow2 = conic.computeQuadPOW2(tol);
  360. fQuadCount = 1 << pow2;
  361. SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount);
  362. fQuadCount = conic.chopIntoQuadsPOW2(pts, pow2);
  363. return pts;
  364. }
  365. const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight,
  366. SkScalar tol) {
  367. SkConic conic;
  368. conic.set(pts, weight);
  369. return computeQuads(conic, tol);
  370. }
  371. int countQuads() const { return fQuadCount; }
  372. private:
  373. enum {
  374. kQuadCount = 8, // should handle most conics
  375. kPointCount = 1 + 2 * kQuadCount,
  376. };
  377. SkAutoSTMalloc<kPointCount, SkPoint> fStorage;
  378. int fQuadCount; // #quads for current usage
  379. };
  380. #endif