GrCCFillGeometry.cpp 31 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802
  1. /*
  2. * Copyright 2017 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. #include "src/gpu/ccpr/GrCCFillGeometry.h"
  8. #include "include/gpu/GrTypes.h"
  9. #include "src/core/SkGeometry.h"
  10. #include <algorithm>
  11. #include <cmath>
  12. #include <cstdlib>
  13. static constexpr float kFlatnessThreshold = 1/16.f; // 1/16 of a pixel.
  14. void GrCCFillGeometry::beginPath() {
  15. SkASSERT(!fBuildingContour);
  16. fVerbs.push_back(Verb::kBeginPath);
  17. }
  18. void GrCCFillGeometry::beginContour(const SkPoint& pt) {
  19. SkASSERT(!fBuildingContour);
  20. // Store the current verb count in the fTriangles field for now. When we close the contour we
  21. // will use this value to calculate the actual number of triangles in its fan.
  22. fCurrContourTallies = {fVerbs.count(), 0, 0, 0, 0};
  23. fPoints.push_back(pt);
  24. fVerbs.push_back(Verb::kBeginContour);
  25. fCurrAnchorPoint = pt;
  26. SkDEBUGCODE(fBuildingContour = true);
  27. }
  28. void GrCCFillGeometry::lineTo(const SkPoint P[2]) {
  29. SkASSERT(fBuildingContour);
  30. SkASSERT(P[0] == fPoints.back());
  31. Sk2f p0 = Sk2f::Load(P);
  32. Sk2f p1 = Sk2f::Load(P+1);
  33. this->appendLine(p0, p1);
  34. }
  35. inline void GrCCFillGeometry::appendLine(const Sk2f& p0, const Sk2f& p1) {
  36. SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1]));
  37. if ((p0 == p1).allTrue()) {
  38. return;
  39. }
  40. p1.store(&fPoints.push_back());
  41. fVerbs.push_back(Verb::kLineTo);
  42. }
  43. static inline Sk2f normalize(const Sk2f& n) {
  44. Sk2f nn = n*n;
  45. return n * (nn + SkNx_shuffle<1,0>(nn)).rsqrt();
  46. }
  47. static inline float dot(const Sk2f& a, const Sk2f& b) {
  48. float product[2];
  49. (a * b).store(product);
  50. return product[0] + product[1];
  51. }
  52. static inline bool are_collinear(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
  53. float tolerance = kFlatnessThreshold) {
  54. Sk2f l = p2 - p0; // Line from p0 -> p2.
  55. // lwidth = Manhattan width of l.
  56. Sk2f labs = l.abs();
  57. float lwidth = labs[0] + labs[1];
  58. // d = |p1 - p0| dot | l.y|
  59. // |-l.x| = distance from p1 to l.
  60. Sk2f dd = (p1 - p0) * SkNx_shuffle<1,0>(l);
  61. float d = dd[0] - dd[1];
  62. // We are collinear if a box with radius "tolerance", centered on p1, touches the line l.
  63. // To decide this, we check if the distance from p1 to the line is less than the distance from
  64. // p1 to the far corner of this imaginary box, along that same normal vector.
  65. // The far corner of the box can be found at "p1 + sign(n) * tolerance", where n is normal to l:
  66. //
  67. // abs(dot(p1 - p0, n)) <= dot(sign(n) * tolerance, n)
  68. //
  69. // Which reduces to:
  70. //
  71. // abs(d) <= (n.x * sign(n.x) + n.y * sign(n.y)) * tolerance
  72. // abs(d) <= (abs(n.x) + abs(n.y)) * tolerance
  73. //
  74. // Use "<=" in case l == 0.
  75. return std::abs(d) <= lwidth * tolerance;
  76. }
  77. static inline bool are_collinear(const SkPoint P[4], float tolerance = kFlatnessThreshold) {
  78. Sk4f Px, Py; // |Px Py| |p0 - p3|
  79. Sk4f::Load2(P, &Px, &Py); // |. . | = |p1 - p3|
  80. Px -= Px[3]; // |. . | |p2 - p3|
  81. Py -= Py[3]; // |. . | | 0 |
  82. // Find [lx, ly] = the line from p3 to the furthest-away point from p3.
  83. Sk4f Pwidth = Px.abs() + Py.abs(); // Pwidth = Manhattan width of each point.
  84. int lidx = Pwidth[0] > Pwidth[1] ? 0 : 1;
  85. lidx = Pwidth[lidx] > Pwidth[2] ? lidx : 2;
  86. float lx = Px[lidx], ly = Py[lidx];
  87. float lwidth = Pwidth[lidx]; // lwidth = Manhattan width of [lx, ly].
  88. // |Px Py|
  89. // d = |. . | * | ly| = distances from each point to l (two of the distances will be zero).
  90. // |. . | |-lx|
  91. // |. . |
  92. Sk4f d = Px*ly - Py*lx;
  93. // We are collinear if boxes with radius "tolerance", centered on all 4 points all touch line l.
  94. // (See the rationale for this formula in the above, 3-point version of this function.)
  95. // Use "<=" in case l == 0.
  96. return (d.abs() <= lwidth * tolerance).allTrue();
  97. }
  98. // Returns whether the (convex) curve segment is monotonic with respect to [endPt - startPt].
  99. static inline bool is_convex_curve_monotonic(const Sk2f& startPt, const Sk2f& tan0,
  100. const Sk2f& endPt, const Sk2f& tan1) {
  101. Sk2f v = endPt - startPt;
  102. float dot0 = dot(tan0, v);
  103. float dot1 = dot(tan1, v);
  104. // A small, negative tolerance handles floating-point error in the case when one tangent
  105. // approaches 0 length, meaning the (convex) curve segment is effectively a flat line.
  106. float tolerance = -std::max(std::abs(dot0), std::abs(dot1)) * SK_ScalarNearlyZero;
  107. return dot0 >= tolerance && dot1 >= tolerance;
  108. }
  109. template<int N> static inline SkNx<N,float> lerp(const SkNx<N,float>& a, const SkNx<N,float>& b,
  110. const SkNx<N,float>& t) {
  111. return SkNx_fma(t, b - a, a);
  112. }
  113. void GrCCFillGeometry::quadraticTo(const SkPoint P[3]) {
  114. SkASSERT(fBuildingContour);
  115. SkASSERT(P[0] == fPoints.back());
  116. Sk2f p0 = Sk2f::Load(P);
  117. Sk2f p1 = Sk2f::Load(P+1);
  118. Sk2f p2 = Sk2f::Load(P+2);
  119. // Don't crunch on the curve if it is nearly flat (or just very small). Flat curves can break
  120. // The monotonic chopping math.
  121. if (are_collinear(p0, p1, p2)) {
  122. this->appendLine(p0, p2);
  123. return;
  124. }
  125. this->appendQuadratics(p0, p1, p2);
  126. }
  127. inline void GrCCFillGeometry::appendQuadratics(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2) {
  128. Sk2f tan0 = p1 - p0;
  129. Sk2f tan1 = p2 - p1;
  130. // This should almost always be this case for well-behaved curves in the real world.
  131. if (is_convex_curve_monotonic(p0, tan0, p2, tan1)) {
  132. this->appendMonotonicQuadratic(p0, p1, p2);
  133. return;
  134. }
  135. // Chop the curve into two segments with equal curvature. To do this we find the T value whose
  136. // tangent angle is halfway between tan0 and tan1.
  137. Sk2f n = normalize(tan0) - normalize(tan1);
  138. // The midtangent can be found where (dQ(t) dot n) = 0:
  139. //
  140. // 0 = (dQ(t) dot n) = | 2*t 1 | * | p0 - 2*p1 + p2 | * | n |
  141. // | -2*p0 + 2*p1 | | . |
  142. //
  143. // = | 2*t 1 | * | tan1 - tan0 | * | n |
  144. // | 2*tan0 | | . |
  145. //
  146. // = 2*t * ((tan1 - tan0) dot n) + (2*tan0 dot n)
  147. //
  148. // t = (tan0 dot n) / ((tan0 - tan1) dot n)
  149. Sk2f dQ1n = (tan0 - tan1) * n;
  150. Sk2f dQ0n = tan0 * n;
  151. Sk2f t = (dQ0n + SkNx_shuffle<1,0>(dQ0n)) / (dQ1n + SkNx_shuffle<1,0>(dQ1n));
  152. t = Sk2f::Min(Sk2f::Max(t, 0), 1); // Clamp for FP error.
  153. Sk2f p01 = SkNx_fma(t, tan0, p0);
  154. Sk2f p12 = SkNx_fma(t, tan1, p1);
  155. Sk2f p012 = lerp(p01, p12, t);
  156. this->appendMonotonicQuadratic(p0, p01, p012);
  157. this->appendMonotonicQuadratic(p012, p12, p2);
  158. }
  159. inline void GrCCFillGeometry::appendMonotonicQuadratic(const Sk2f& p0, const Sk2f& p1,
  160. const Sk2f& p2) {
  161. // Don't send curves to the GPU if we know they are nearly flat (or just very small).
  162. if (are_collinear(p0, p1, p2)) {
  163. this->appendLine(p0, p2);
  164. return;
  165. }
  166. SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1]));
  167. SkASSERT((p0 != p2).anyTrue());
  168. p1.store(&fPoints.push_back());
  169. p2.store(&fPoints.push_back());
  170. fVerbs.push_back(Verb::kMonotonicQuadraticTo);
  171. ++fCurrContourTallies.fQuadratics;
  172. }
  173. static inline Sk2f first_unless_nearly_zero(const Sk2f& a, const Sk2f& b) {
  174. Sk2f aa = a*a;
  175. aa += SkNx_shuffle<1,0>(aa);
  176. SkASSERT(aa[0] == aa[1]);
  177. Sk2f bb = b*b;
  178. bb += SkNx_shuffle<1,0>(bb);
  179. SkASSERT(bb[0] == bb[1]);
  180. return (aa > bb * SK_ScalarNearlyZero).thenElse(a, b);
  181. }
  182. static inline void get_cubic_tangents(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
  183. const Sk2f& p3, Sk2f* tan0, Sk2f* tan1) {
  184. *tan0 = first_unless_nearly_zero(p1 - p0, p2 - p0);
  185. *tan1 = first_unless_nearly_zero(p3 - p2, p3 - p1);
  186. }
  187. static inline bool is_cubic_nearly_quadratic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
  188. const Sk2f& p3, const Sk2f& tan0, const Sk2f& tan1,
  189. Sk2f* c) {
  190. Sk2f c1 = SkNx_fma(Sk2f(1.5f), tan0, p0);
  191. Sk2f c2 = SkNx_fma(Sk2f(-1.5f), tan1, p3);
  192. *c = (c1 + c2) * .5f; // Hopefully optimized out if not used?
  193. return ((c1 - c2).abs() <= 1).allTrue();
  194. }
  195. enum class ExcludedTerm : bool {
  196. kQuadraticTerm,
  197. kLinearTerm
  198. };
  199. // Finds where to chop a non-loop around its inflection points. The resulting cubic segments will be
  200. // chopped such that a box of radius 'padRadius', centered at any point along the curve segment, is
  201. // guaranteed to not cross the tangent lines at the inflection points (a.k.a lines L & M).
  202. //
  203. // 'chops' will be filled with 0, 2, or 4 T values. The segments between T0..T1 and T2..T3 must be
  204. // drawn with flat lines instead of cubics.
  205. //
  206. // A serpentine cubic has two inflection points, so this method takes Sk2f and computes the padding
  207. // for both in SIMD.
  208. static inline void find_chops_around_inflection_points(float padRadius, Sk2f tl, Sk2f sl,
  209. const Sk2f& C0, const Sk2f& C1,
  210. ExcludedTerm skipTerm, float Cdet,
  211. SkSTArray<4, float>* chops) {
  212. SkASSERT(chops->empty());
  213. SkASSERT(padRadius >= 0);
  214. padRadius /= std::abs(Cdet); // Scale this single value rather than all of C^-1 later on.
  215. // The homogeneous parametric functions for distance from lines L & M are:
  216. //
  217. // l(t,s) = (t*sl - s*tl)^3
  218. // m(t,s) = (t*sm - s*tm)^3
  219. //
  220. // See "Resolution Independent Curve Rendering using Programmable Graphics Hardware",
  221. // 4.3 Finding klmn:
  222. //
  223. // https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
  224. //
  225. // From here on we use Sk2f with "L" names, but the second lane will be for line M.
  226. tl = (sl > 0).thenElse(tl, -tl); // Tl=tl/sl is the triple root of l(t,s). Normalize so s >= 0.
  227. sl = sl.abs();
  228. // Convert l(t,s), m(t,s) to power-basis form:
  229. //
  230. // | l3 m3 |
  231. // |l(t,s) m(t,s)| = |t^3 t^2*s t*s^2 s^3| * | l2 m2 |
  232. // | l1 m1 |
  233. // | l0 m0 |
  234. //
  235. Sk2f l3 = sl*sl*sl;
  236. Sk2f l2or1 = (ExcludedTerm::kLinearTerm == skipTerm) ? sl*sl*tl*-3 : sl*tl*tl*3;
  237. // The equation for line L can be found as follows:
  238. //
  239. // L = C^-1 * (l excluding skipTerm)
  240. //
  241. // (See comments for GrPathUtils::calcCubicInverseTransposePowerBasisMatrix.)
  242. // We are only interested in the normal to L, so only need the upper 2x2 of C^-1. And rather
  243. // than divide by determinant(C) here, we have already performed this divide on padRadius.
  244. Sk2f Lx = C1[1]*l3 - C0[1]*l2or1;
  245. Sk2f Ly = -C1[0]*l3 + C0[0]*l2or1;
  246. // A box of radius "padRadius" is touching line L if "center dot L" is less than the Manhattan
  247. // with of L. (See rationale in are_collinear.)
  248. Sk2f Lwidth = Lx.abs() + Ly.abs();
  249. Sk2f pad = Lwidth * padRadius;
  250. // Will T=(t + cbrt(pad))/s be greater than 0? No need to solve roots outside T=0..1.
  251. Sk2f insideLeftPad = pad + tl*tl*tl;
  252. // Will T=(t - cbrt(pad))/s be less than 1? No need to solve roots outside T=0..1.
  253. Sk2f tms = tl - sl;
  254. Sk2f insideRightPad = pad - tms*tms*tms;
  255. // Solve for the T values where abs(l(T)) = pad.
  256. if (insideLeftPad[0] > 0 && insideRightPad[0] > 0) {
  257. float padT = cbrtf(pad[0]);
  258. Sk2f pts = (tl[0] + Sk2f(-padT, +padT)) / sl[0];
  259. pts.store(chops->push_back_n(2));
  260. }
  261. // Solve for the T values where abs(m(T)) = pad.
  262. if (insideLeftPad[1] > 0 && insideRightPad[1] > 0) {
  263. float padT = cbrtf(pad[1]);
  264. Sk2f pts = (tl[1] + Sk2f(-padT, +padT)) / sl[1];
  265. pts.store(chops->push_back_n(2));
  266. }
  267. }
  268. static inline void swap_if_greater(float& a, float& b) {
  269. if (a > b) {
  270. std::swap(a, b);
  271. }
  272. }
  273. // Finds where to chop a non-loop around its intersection point. The resulting cubic segments will
  274. // be chopped such that a box of radius 'padRadius', centered at any point along the curve segment,
  275. // is guaranteed to not cross the tangent lines at the intersection point (a.k.a lines L & M).
  276. //
  277. // 'chops' will be filled with 0, 2, or 4 T values. The segments between T0..T1 and T2..T3 must be
  278. // drawn with quadratic splines instead of cubics.
  279. //
  280. // A loop intersection falls at two different T values, so this method takes Sk2f and computes the
  281. // padding for both in SIMD.
  282. static inline void find_chops_around_loop_intersection(float padRadius, Sk2f t2, Sk2f s2,
  283. const Sk2f& C0, const Sk2f& C1,
  284. ExcludedTerm skipTerm, float Cdet,
  285. SkSTArray<4, float>* chops) {
  286. SkASSERT(chops->empty());
  287. SkASSERT(padRadius >= 0);
  288. padRadius /= std::abs(Cdet); // Scale this single value rather than all of C^-1 later on.
  289. // The parametric functions for distance from lines L & M are:
  290. //
  291. // l(T) = (T - Td)^2 * (T - Te)
  292. // m(T) = (T - Td) * (T - Te)^2
  293. //
  294. // See "Resolution Independent Curve Rendering using Programmable Graphics Hardware",
  295. // 4.3 Finding klmn:
  296. //
  297. // https://www.microsoft.com/en-us/research/wp-content/uploads/2005/01/p1000-loop.pdf
  298. Sk2f T2 = t2/s2; // T2 is the double root of l(T).
  299. Sk2f T1 = SkNx_shuffle<1,0>(T2); // T1 is the other root of l(T).
  300. // Convert l(T), m(T) to power-basis form:
  301. //
  302. // | 1 1 |
  303. // |l(T) m(T)| = |T^3 T^2 T 1| * | l2 m2 |
  304. // | l1 m1 |
  305. // | l0 m0 |
  306. //
  307. // From here on we use Sk2f with "L" names, but the second lane will be for line M.
  308. Sk2f l2 = SkNx_fma(Sk2f(-2), T2, -T1);
  309. Sk2f l1 = T2 * SkNx_fma(Sk2f(2), T1, T2);
  310. Sk2f l0 = -T2*T2*T1;
  311. // The equation for line L can be found as follows:
  312. //
  313. // L = C^-1 * (l excluding skipTerm)
  314. //
  315. // (See comments for GrPathUtils::calcCubicInverseTransposePowerBasisMatrix.)
  316. // We are only interested in the normal to L, so only need the upper 2x2 of C^-1. And rather
  317. // than divide by determinant(C) here, we have already performed this divide on padRadius.
  318. Sk2f l2or1 = (ExcludedTerm::kLinearTerm == skipTerm) ? l2 : l1;
  319. Sk2f Lx = -C0[1]*l2or1 + C1[1]; // l3 is always 1.
  320. Sk2f Ly = C0[0]*l2or1 - C1[0];
  321. // A box of radius "padRadius" is touching line L if "center dot L" is less than the Manhattan
  322. // with of L. (See rationale in are_collinear.)
  323. Sk2f Lwidth = Lx.abs() + Ly.abs();
  324. Sk2f pad = Lwidth * padRadius;
  325. // Is l(T=0) outside the padding around line L?
  326. Sk2f lT0 = l0; // l(T=0) = |0 0 0 1| dot |1 l2 l1 l0| = l0
  327. Sk2f outsideT0 = lT0.abs() - pad;
  328. // Is l(T=1) outside the padding around line L?
  329. Sk2f lT1 = (Sk2f(1) + l2 + l1 + l0).abs(); // l(T=1) = |1 1 1 1| dot |1 l2 l1 l0|
  330. Sk2f outsideT1 = lT1.abs() - pad;
  331. // Values for solving the cubic.
  332. Sk2f p, q, qqq, discr, numRoots, D;
  333. bool hasDiscr = false;
  334. // Values for calculating one root (rarely needed).
  335. Sk2f R, QQ;
  336. bool hasOneRootVals = false;
  337. // Values for calculating three roots.
  338. Sk2f P, cosTheta3;
  339. bool hasThreeRootVals = false;
  340. // Solve for the T values where l(T) = +pad and m(T) = -pad.
  341. for (int i = 0; i < 2; ++i) {
  342. float T = T2[i]; // T is the point we are chopping around.
  343. if ((T < 0 && outsideT0[i] >= 0) || (T > 1 && outsideT1[i] >= 0)) {
  344. // The padding around T is completely out of range. No point solving for it.
  345. continue;
  346. }
  347. if (!hasDiscr) {
  348. p = Sk2f(+.5f, -.5f) * pad;
  349. q = (1.f/3) * (T2 - T1);
  350. qqq = q*q*q;
  351. discr = qqq*p*2 + p*p;
  352. numRoots = (discr < 0).thenElse(3, 1);
  353. D = T2 - q;
  354. hasDiscr = true;
  355. }
  356. if (1 == numRoots[i]) {
  357. if (!hasOneRootVals) {
  358. Sk2f r = qqq + p;
  359. Sk2f s = r.abs() + discr.sqrt();
  360. R = (r > 0).thenElse(-s, s);
  361. QQ = q*q;
  362. hasOneRootVals = true;
  363. }
  364. float A = cbrtf(R[i]);
  365. float B = A != 0 ? QQ[i]/A : 0;
  366. // When there is only one root, ine L chops from root..1, line M chops from 0..root.
  367. if (1 == i) {
  368. chops->push_back(0);
  369. }
  370. chops->push_back(A + B + D[i]);
  371. if (0 == i) {
  372. chops->push_back(1);
  373. }
  374. continue;
  375. }
  376. if (!hasThreeRootVals) {
  377. P = q.abs() * -2;
  378. cosTheta3 = (q >= 0).thenElse(1, -1) + p / qqq.abs();
  379. hasThreeRootVals = true;
  380. }
  381. static constexpr float k2PiOver3 = 2 * SK_ScalarPI / 3;
  382. float theta = std::acos(cosTheta3[i]) * (1.f/3);
  383. float roots[3] = {P[i] * std::cos(theta) + D[i],
  384. P[i] * std::cos(theta + k2PiOver3) + D[i],
  385. P[i] * std::cos(theta - k2PiOver3) + D[i]};
  386. // Sort the three roots.
  387. swap_if_greater(roots[0], roots[1]);
  388. swap_if_greater(roots[1], roots[2]);
  389. swap_if_greater(roots[0], roots[1]);
  390. // Line L chops around the first 2 roots, line M chops around the second 2.
  391. chops->push_back_n(2, &roots[i]);
  392. }
  393. }
  394. void GrCCFillGeometry::cubicTo(const SkPoint P[4], float inflectPad, float loopIntersectPad) {
  395. SkASSERT(fBuildingContour);
  396. SkASSERT(P[0] == fPoints.back());
  397. // Don't crunch on the curve or inflate geometry if it is nearly flat (or just very small).
  398. // Flat curves can break the math below.
  399. if (are_collinear(P)) {
  400. Sk2f p0 = Sk2f::Load(P);
  401. Sk2f p3 = Sk2f::Load(P+3);
  402. this->appendLine(p0, p3);
  403. return;
  404. }
  405. Sk2f p0 = Sk2f::Load(P);
  406. Sk2f p1 = Sk2f::Load(P+1);
  407. Sk2f p2 = Sk2f::Load(P+2);
  408. Sk2f p3 = Sk2f::Load(P+3);
  409. // Also detect near-quadratics ahead of time.
  410. Sk2f tan0, tan1, c;
  411. get_cubic_tangents(p0, p1, p2, p3, &tan0, &tan1);
  412. if (is_cubic_nearly_quadratic(p0, p1, p2, p3, tan0, tan1, &c)) {
  413. this->appendQuadratics(p0, c, p3);
  414. return;
  415. }
  416. double tt[2], ss[2], D[4];
  417. fCurrCubicType = SkClassifyCubic(P, tt, ss, D);
  418. SkASSERT(!SkCubicIsDegenerate(fCurrCubicType));
  419. Sk2f t = Sk2f(static_cast<float>(tt[0]), static_cast<float>(tt[1]));
  420. Sk2f s = Sk2f(static_cast<float>(ss[0]), static_cast<float>(ss[1]));
  421. ExcludedTerm skipTerm = (std::abs(D[2]) > std::abs(D[1]))
  422. ? ExcludedTerm::kQuadraticTerm
  423. : ExcludedTerm::kLinearTerm;
  424. Sk2f C0 = SkNx_fma(Sk2f(3), p1 - p2, p3 - p0);
  425. Sk2f C1 = (ExcludedTerm::kLinearTerm == skipTerm
  426. ? SkNx_fma(Sk2f(-2), p1, p0 + p2)
  427. : p1 - p0) * 3;
  428. Sk2f C0x1 = C0 * SkNx_shuffle<1,0>(C1);
  429. float Cdet = C0x1[0] - C0x1[1];
  430. SkSTArray<4, float> chops;
  431. if (SkCubicType::kLoop != fCurrCubicType) {
  432. find_chops_around_inflection_points(inflectPad, t, s, C0, C1, skipTerm, Cdet, &chops);
  433. } else {
  434. find_chops_around_loop_intersection(loopIntersectPad, t, s, C0, C1, skipTerm, Cdet, &chops);
  435. }
  436. if (4 == chops.count() && chops[1] >= chops[2]) {
  437. // This just the means the KLM roots are so close that their paddings overlap. We will
  438. // approximate the entire middle section, but still have it chopped midway. For loops this
  439. // chop guarantees the append code only sees convex segments. Otherwise, it means we are (at
  440. // least almost) a cusp and the chop makes sure we get a sharp point.
  441. Sk2f ts = t * SkNx_shuffle<1,0>(s);
  442. chops[1] = chops[2] = (ts[0] + ts[1]) / (2*s[0]*s[1]);
  443. }
  444. #ifdef SK_DEBUG
  445. for (int i = 1; i < chops.count(); ++i) {
  446. SkASSERT(chops[i] >= chops[i - 1]);
  447. }
  448. #endif
  449. this->appendCubics(AppendCubicMode::kLiteral, p0, p1, p2, p3, chops.begin(), chops.count());
  450. }
  451. static inline void chop_cubic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2, const Sk2f& p3,
  452. float T, Sk2f* ab, Sk2f* abc, Sk2f* abcd, Sk2f* bcd, Sk2f* cd) {
  453. Sk2f TT = T;
  454. *ab = lerp(p0, p1, TT);
  455. Sk2f bc = lerp(p1, p2, TT);
  456. *cd = lerp(p2, p3, TT);
  457. *abc = lerp(*ab, bc, TT);
  458. *bcd = lerp(bc, *cd, TT);
  459. *abcd = lerp(*abc, *bcd, TT);
  460. }
  461. void GrCCFillGeometry::appendCubics(AppendCubicMode mode, const Sk2f& p0, const Sk2f& p1,
  462. const Sk2f& p2, const Sk2f& p3, const float chops[],
  463. int numChops, float localT0, float localT1) {
  464. if (numChops) {
  465. SkASSERT(numChops > 0);
  466. int midChopIdx = numChops/2;
  467. float T = chops[midChopIdx];
  468. // Chops alternate between literal and approximate mode.
  469. AppendCubicMode rightMode = (AppendCubicMode)((bool)mode ^ (midChopIdx & 1) ^ 1);
  470. if (T <= localT0) {
  471. // T is outside 0..1. Append the right side only.
  472. this->appendCubics(rightMode, p0, p1, p2, p3, &chops[midChopIdx + 1],
  473. numChops - midChopIdx - 1, localT0, localT1);
  474. return;
  475. }
  476. if (T >= localT1) {
  477. // T is outside 0..1. Append the left side only.
  478. this->appendCubics(mode, p0, p1, p2, p3, chops, midChopIdx, localT0, localT1);
  479. return;
  480. }
  481. float localT = (T - localT0) / (localT1 - localT0);
  482. Sk2f p01, p02, pT, p11, p12;
  483. chop_cubic(p0, p1, p2, p3, localT, &p01, &p02, &pT, &p11, &p12);
  484. this->appendCubics(mode, p0, p01, p02, pT, chops, midChopIdx, localT0, T);
  485. this->appendCubics(rightMode, pT, p11, p12, p3, &chops[midChopIdx + 1],
  486. numChops - midChopIdx - 1, T, localT1);
  487. return;
  488. }
  489. this->appendCubics(mode, p0, p1, p2, p3);
  490. }
  491. void GrCCFillGeometry::appendCubics(AppendCubicMode mode, const Sk2f& p0, const Sk2f& p1,
  492. const Sk2f& p2, const Sk2f& p3, int maxSubdivisions) {
  493. if (SkCubicType::kLoop != fCurrCubicType) {
  494. // Serpentines and cusps are always monotonic after chopping around inflection points.
  495. SkASSERT(!SkCubicIsDegenerate(fCurrCubicType));
  496. if (AppendCubicMode::kApproximate == mode) {
  497. // This section passes through an inflection point, so we can get away with a flat line.
  498. // This can cause some curves to feel slightly more flat when inspected rigorously back
  499. // and forth against another renderer, but for now this seems acceptable given the
  500. // simplicity.
  501. this->appendLine(p0, p3);
  502. return;
  503. }
  504. } else {
  505. Sk2f tan0, tan1;
  506. get_cubic_tangents(p0, p1, p2, p3, &tan0, &tan1);
  507. if (maxSubdivisions && !is_convex_curve_monotonic(p0, tan0, p3, tan1)) {
  508. this->chopAndAppendCubicAtMidTangent(mode, p0, p1, p2, p3, tan0, tan1,
  509. maxSubdivisions - 1);
  510. return;
  511. }
  512. if (AppendCubicMode::kApproximate == mode) {
  513. Sk2f c;
  514. if (!is_cubic_nearly_quadratic(p0, p1, p2, p3, tan0, tan1, &c) && maxSubdivisions) {
  515. this->chopAndAppendCubicAtMidTangent(mode, p0, p1, p2, p3, tan0, tan1,
  516. maxSubdivisions - 1);
  517. return;
  518. }
  519. this->appendMonotonicQuadratic(p0, c, p3);
  520. return;
  521. }
  522. }
  523. // Don't send curves to the GPU if we know they are nearly flat (or just very small).
  524. // Since the cubic segment is known to be convex at this point, our flatness check is simple.
  525. if (are_collinear(p0, (p1 + p2) * .5f, p3)) {
  526. this->appendLine(p0, p3);
  527. return;
  528. }
  529. SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1]));
  530. SkASSERT((p0 != p3).anyTrue());
  531. p1.store(&fPoints.push_back());
  532. p2.store(&fPoints.push_back());
  533. p3.store(&fPoints.push_back());
  534. fVerbs.push_back(Verb::kMonotonicCubicTo);
  535. ++fCurrContourTallies.fCubics;
  536. }
  537. // Given a convex curve segment with the following order-2 tangent function:
  538. //
  539. // |C2x C2y|
  540. // tan = some_scale * |dx/dt dy/dt| = |t^2 t 1| * |C1x C1y|
  541. // |C0x C0y|
  542. //
  543. // This function finds the T value whose tangent angle is halfway between the tangents at T=0 and
  544. // T=1 (tan0 and tan1).
  545. static inline float find_midtangent(const Sk2f& tan0, const Sk2f& tan1,
  546. const Sk2f& C2, const Sk2f& C1, const Sk2f& C0) {
  547. // Tangents point in the direction of increasing T, so tan0 and -tan1 both point toward the
  548. // midtangent. 'n' will therefore bisect tan0 and -tan1, giving us the normal to the midtangent.
  549. //
  550. // n dot midtangent = 0
  551. //
  552. Sk2f n = normalize(tan0) - normalize(tan1);
  553. // Find the T value at the midtangent. This is a simple quadratic equation:
  554. //
  555. // midtangent dot n = 0
  556. //
  557. // (|t^2 t 1| * C) dot n = 0
  558. //
  559. // |t^2 t 1| dot C*n = 0
  560. //
  561. // First find coeffs = C*n.
  562. Sk4f C[2];
  563. Sk2f::Store4(C, C2, C1, C0, 0);
  564. Sk4f coeffs = C[0]*n[0] + C[1]*n[1];
  565. // Now solve the quadratic.
  566. float a = coeffs[0], b = coeffs[1], c = coeffs[2];
  567. float discr = b*b - 4*a*c;
  568. if (discr < 0) {
  569. return 0; // This will only happen if the curve is a line.
  570. }
  571. // The roots are q/a and c/q. Pick the one closer to T=.5.
  572. float q = -.5f * (b + copysignf(std::sqrt(discr), b));
  573. float r = .5f*q*a;
  574. return std::abs(q*q - r) < std::abs(a*c - r) ? q/a : c/q;
  575. }
  576. inline void GrCCFillGeometry::chopAndAppendCubicAtMidTangent(AppendCubicMode mode, const Sk2f& p0,
  577. const Sk2f& p1, const Sk2f& p2,
  578. const Sk2f& p3, const Sk2f& tan0,
  579. const Sk2f& tan1,
  580. int maxFutureSubdivisions) {
  581. float midT = find_midtangent(tan0, tan1, p3 + (p1 - p2)*3 - p0,
  582. (p0 - p1*2 + p2)*2,
  583. p1 - p0);
  584. // Use positive logic since NaN fails comparisons. (However midT should not be NaN since we cull
  585. // near-flat cubics in cubicTo().)
  586. if (!(midT > 0 && midT < 1)) {
  587. // The cubic is flat. Otherwise there would be a real midtangent inside T=0..1.
  588. this->appendLine(p0, p3);
  589. return;
  590. }
  591. Sk2f p01, p02, pT, p11, p12;
  592. chop_cubic(p0, p1, p2, p3, midT, &p01, &p02, &pT, &p11, &p12);
  593. this->appendCubics(mode, p0, p01, p02, pT, maxFutureSubdivisions);
  594. this->appendCubics(mode, pT, p11, p12, p3, maxFutureSubdivisions);
  595. }
  596. void GrCCFillGeometry::conicTo(const SkPoint P[3], float w) {
  597. SkASSERT(fBuildingContour);
  598. SkASSERT(P[0] == fPoints.back());
  599. Sk2f p0 = Sk2f::Load(P);
  600. Sk2f p1 = Sk2f::Load(P+1);
  601. Sk2f p2 = Sk2f::Load(P+2);
  602. Sk2f tan0 = p1 - p0;
  603. Sk2f tan1 = p2 - p1;
  604. if (!is_convex_curve_monotonic(p0, tan0, p2, tan1)) {
  605. // The derivative of a conic has a cumbersome order-4 denominator. However, this isn't
  606. // necessary if we are only interested in a vector in the same *direction* as a given
  607. // tangent line. Since the denominator scales dx and dy uniformly, we can throw it out
  608. // completely after evaluating the derivative with the standard quotient rule. This leaves
  609. // us with a simpler quadratic function that we use to find the midtangent.
  610. float midT = find_midtangent(tan0, tan1, (w - 1) * (p2 - p0),
  611. (p2 - p0) - 2*w*(p1 - p0),
  612. w*(p1 - p0));
  613. // Use positive logic since NaN fails comparisons. (However midT should not be NaN since we
  614. // cull near-linear conics above. And while w=0 is flat, it's not a line and has valid
  615. // midtangents.)
  616. if (!(midT > 0 && midT < 1)) {
  617. // The conic is flat. Otherwise there would be a real midtangent inside T=0..1.
  618. this->appendLine(p0, p2);
  619. return;
  620. }
  621. // Chop the conic at midtangent to produce two monotonic segments.
  622. Sk4f p3d0 = Sk4f(p0[0], p0[1], 1, 0);
  623. Sk4f p3d1 = Sk4f(p1[0], p1[1], 1, 0) * w;
  624. Sk4f p3d2 = Sk4f(p2[0], p2[1], 1, 0);
  625. Sk4f midT4 = midT;
  626. Sk4f p3d01 = lerp(p3d0, p3d1, midT4);
  627. Sk4f p3d12 = lerp(p3d1, p3d2, midT4);
  628. Sk4f p3d012 = lerp(p3d01, p3d12, midT4);
  629. Sk2f midpoint = Sk2f(p3d012[0], p3d012[1]) / p3d012[2];
  630. Sk2f ww = Sk2f(p3d01[2], p3d12[2]) * Sk2f(p3d012[2]).rsqrt();
  631. this->appendMonotonicConic(p0, Sk2f(p3d01[0], p3d01[1]) / p3d01[2], midpoint, ww[0]);
  632. this->appendMonotonicConic(midpoint, Sk2f(p3d12[0], p3d12[1]) / p3d12[2], p2, ww[1]);
  633. return;
  634. }
  635. this->appendMonotonicConic(p0, p1, p2, w);
  636. }
  637. void GrCCFillGeometry::appendMonotonicConic(const Sk2f& p0, const Sk2f& p1, const Sk2f& p2,
  638. float w) {
  639. SkASSERT(w >= 0);
  640. Sk2f base = p2 - p0;
  641. Sk2f baseAbs = base.abs();
  642. float baseWidth = baseAbs[0] + baseAbs[1];
  643. // Find the height of the curve. Max height always occurs at T=.5 for conics.
  644. Sk2f d = (p1 - p0) * SkNx_shuffle<1,0>(base);
  645. float h1 = std::abs(d[1] - d[0]); // Height of p1 above the base.
  646. float ht = h1*w, hs = 1 + w; // Height of the conic = ht/hs.
  647. // i.e. (ht/hs <= baseWidth * kFlatnessThreshold). Use "<=" in case base == 0.
  648. if (ht <= (baseWidth*hs) * kFlatnessThreshold) {
  649. // We are flat. (See rationale in are_collinear.)
  650. this->appendLine(p0, p2);
  651. return;
  652. }
  653. // i.e. (w > 1 && h1 - ht/hs < baseWidth).
  654. if (w > 1 && h1*hs - ht < baseWidth*hs) {
  655. // If we get within 1px of p1 when w > 1, we will pick up artifacts from the implicit
  656. // function's reflection. Chop at max height (T=.5) and draw a triangle instead.
  657. Sk2f p1w = p1*w;
  658. Sk2f ab = p0 + p1w;
  659. Sk2f bc = p1w + p2;
  660. Sk2f highpoint = (ab + bc) / (2*(1 + w));
  661. this->appendLine(p0, highpoint);
  662. this->appendLine(highpoint, p2);
  663. return;
  664. }
  665. SkASSERT(fPoints.back() == SkPoint::Make(p0[0], p0[1]));
  666. SkASSERT((p0 != p2).anyTrue());
  667. p1.store(&fPoints.push_back());
  668. p2.store(&fPoints.push_back());
  669. fConicWeights.push_back(w);
  670. fVerbs.push_back(Verb::kMonotonicConicTo);
  671. ++fCurrContourTallies.fConics;
  672. }
  673. GrCCFillGeometry::PrimitiveTallies GrCCFillGeometry::endContour() {
  674. SkASSERT(fBuildingContour);
  675. SkASSERT(fVerbs.count() >= fCurrContourTallies.fTriangles);
  676. // The fTriangles field currently contains this contour's starting verb index. We can now
  677. // use it to calculate the size of the contour's fan.
  678. int fanSize = fVerbs.count() - fCurrContourTallies.fTriangles;
  679. if (fPoints.back() == fCurrAnchorPoint) {
  680. --fanSize;
  681. fVerbs.push_back(Verb::kEndClosedContour);
  682. } else {
  683. fVerbs.push_back(Verb::kEndOpenContour);
  684. }
  685. fCurrContourTallies.fTriangles = SkTMax(fanSize - 2, 0);
  686. SkDEBUGCODE(fBuildingContour = false);
  687. return fCurrContourTallies;
  688. }