GrPathUtils.cpp 32 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859
  1. /*
  2. * Copyright 2011 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/geometry/GrPathUtils.h"
  8. #include "include/gpu/GrTypes.h"
  9. #include "src/core/SkMathPriv.h"
  10. #include "src/core/SkPointPriv.h"
  11. static const SkScalar gMinCurveTol = 0.0001f;
  12. SkScalar GrPathUtils::scaleToleranceToSrc(SkScalar devTol,
  13. const SkMatrix& viewM,
  14. const SkRect& pathBounds) {
  15. // In order to tesselate the path we get a bound on how much the matrix can
  16. // scale when mapping to screen coordinates.
  17. SkScalar stretch = viewM.getMaxScale();
  18. if (stretch < 0) {
  19. // take worst case mapRadius amoung four corners.
  20. // (less than perfect)
  21. for (int i = 0; i < 4; ++i) {
  22. SkMatrix mat;
  23. mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight,
  24. (i < 2) ? pathBounds.fTop : pathBounds.fBottom);
  25. mat.postConcat(viewM);
  26. stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1));
  27. }
  28. }
  29. SkScalar srcTol = 0;
  30. if (stretch <= 0) {
  31. // We have degenerate bounds or some degenerate matrix. Thus we set the tolerance to be the
  32. // max of the path pathBounds width and height.
  33. srcTol = SkTMax(pathBounds.width(), pathBounds.height());
  34. } else {
  35. srcTol = devTol / stretch;
  36. }
  37. if (srcTol < gMinCurveTol) {
  38. srcTol = gMinCurveTol;
  39. }
  40. return srcTol;
  41. }
  42. uint32_t GrPathUtils::quadraticPointCount(const SkPoint points[], SkScalar tol) {
  43. // You should have called scaleToleranceToSrc, which guarantees this
  44. SkASSERT(tol >= gMinCurveTol);
  45. SkScalar d = SkPointPriv::DistanceToLineSegmentBetween(points[1], points[0], points[2]);
  46. if (!SkScalarIsFinite(d)) {
  47. return kMaxPointsPerCurve;
  48. } else if (d <= tol) {
  49. return 1;
  50. } else {
  51. // Each time we subdivide, d should be cut in 4. So we need to
  52. // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x)
  53. // points.
  54. // 2^(log4(x)) = sqrt(x);
  55. SkScalar divSqrt = SkScalarSqrt(d / tol);
  56. if (((SkScalar)SK_MaxS32) <= divSqrt) {
  57. return kMaxPointsPerCurve;
  58. } else {
  59. int temp = SkScalarCeilToInt(divSqrt);
  60. int pow2 = GrNextPow2(temp);
  61. // Because of NaNs & INFs we can wind up with a degenerate temp
  62. // such that pow2 comes out negative. Also, our point generator
  63. // will always output at least one pt.
  64. if (pow2 < 1) {
  65. pow2 = 1;
  66. }
  67. return SkTMin(pow2, kMaxPointsPerCurve);
  68. }
  69. }
  70. }
  71. uint32_t GrPathUtils::generateQuadraticPoints(const SkPoint& p0,
  72. const SkPoint& p1,
  73. const SkPoint& p2,
  74. SkScalar tolSqd,
  75. SkPoint** points,
  76. uint32_t pointsLeft) {
  77. if (pointsLeft < 2 ||
  78. (SkPointPriv::DistanceToLineSegmentBetweenSqd(p1, p0, p2)) < tolSqd) {
  79. (*points)[0] = p2;
  80. *points += 1;
  81. return 1;
  82. }
  83. SkPoint q[] = {
  84. { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
  85. { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
  86. };
  87. SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) };
  88. pointsLeft >>= 1;
  89. uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft);
  90. uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft);
  91. return a + b;
  92. }
  93. uint32_t GrPathUtils::cubicPointCount(const SkPoint points[],
  94. SkScalar tol) {
  95. // You should have called scaleToleranceToSrc, which guarantees this
  96. SkASSERT(tol >= gMinCurveTol);
  97. SkScalar d = SkTMax(
  98. SkPointPriv::DistanceToLineSegmentBetweenSqd(points[1], points[0], points[3]),
  99. SkPointPriv::DistanceToLineSegmentBetweenSqd(points[2], points[0], points[3]));
  100. d = SkScalarSqrt(d);
  101. if (!SkScalarIsFinite(d)) {
  102. return kMaxPointsPerCurve;
  103. } else if (d <= tol) {
  104. return 1;
  105. } else {
  106. SkScalar divSqrt = SkScalarSqrt(d / tol);
  107. if (((SkScalar)SK_MaxS32) <= divSqrt) {
  108. return kMaxPointsPerCurve;
  109. } else {
  110. int temp = SkScalarCeilToInt(SkScalarSqrt(d / tol));
  111. int pow2 = GrNextPow2(temp);
  112. // Because of NaNs & INFs we can wind up with a degenerate temp
  113. // such that pow2 comes out negative. Also, our point generator
  114. // will always output at least one pt.
  115. if (pow2 < 1) {
  116. pow2 = 1;
  117. }
  118. return SkTMin(pow2, kMaxPointsPerCurve);
  119. }
  120. }
  121. }
  122. uint32_t GrPathUtils::generateCubicPoints(const SkPoint& p0,
  123. const SkPoint& p1,
  124. const SkPoint& p2,
  125. const SkPoint& p3,
  126. SkScalar tolSqd,
  127. SkPoint** points,
  128. uint32_t pointsLeft) {
  129. if (pointsLeft < 2 ||
  130. (SkPointPriv::DistanceToLineSegmentBetweenSqd(p1, p0, p3) < tolSqd &&
  131. SkPointPriv::DistanceToLineSegmentBetweenSqd(p2, p0, p3) < tolSqd)) {
  132. (*points)[0] = p3;
  133. *points += 1;
  134. return 1;
  135. }
  136. SkPoint q[] = {
  137. { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
  138. { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
  139. { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
  140. };
  141. SkPoint r[] = {
  142. { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
  143. { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
  144. };
  145. SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) };
  146. pointsLeft >>= 1;
  147. uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft);
  148. uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft);
  149. return a + b;
  150. }
  151. int GrPathUtils::worstCasePointCount(const SkPath& path, int* subpaths, SkScalar tol) {
  152. // You should have called scaleToleranceToSrc, which guarantees this
  153. SkASSERT(tol >= gMinCurveTol);
  154. int pointCount = 0;
  155. *subpaths = 1;
  156. bool first = true;
  157. SkPath::Iter iter(path, false);
  158. SkPath::Verb verb;
  159. SkPoint pts[4];
  160. while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
  161. switch (verb) {
  162. case SkPath::kLine_Verb:
  163. pointCount += 1;
  164. break;
  165. case SkPath::kConic_Verb: {
  166. SkScalar weight = iter.conicWeight();
  167. SkAutoConicToQuads converter;
  168. const SkPoint* quadPts = converter.computeQuads(pts, weight, tol);
  169. for (int i = 0; i < converter.countQuads(); ++i) {
  170. pointCount += quadraticPointCount(quadPts + 2*i, tol);
  171. }
  172. }
  173. case SkPath::kQuad_Verb:
  174. pointCount += quadraticPointCount(pts, tol);
  175. break;
  176. case SkPath::kCubic_Verb:
  177. pointCount += cubicPointCount(pts, tol);
  178. break;
  179. case SkPath::kMove_Verb:
  180. pointCount += 1;
  181. if (!first) {
  182. ++(*subpaths);
  183. }
  184. break;
  185. default:
  186. break;
  187. }
  188. first = false;
  189. }
  190. return pointCount;
  191. }
  192. void GrPathUtils::QuadUVMatrix::set(const SkPoint qPts[3]) {
  193. SkMatrix m;
  194. // We want M such that M * xy_pt = uv_pt
  195. // We know M * control_pts = [0 1/2 1]
  196. // [0 0 1]
  197. // [1 1 1]
  198. // And control_pts = [x0 x1 x2]
  199. // [y0 y1 y2]
  200. // [1 1 1 ]
  201. // We invert the control pt matrix and post concat to both sides to get M.
  202. // Using the known form of the control point matrix and the result, we can
  203. // optimize and improve precision.
  204. double x0 = qPts[0].fX;
  205. double y0 = qPts[0].fY;
  206. double x1 = qPts[1].fX;
  207. double y1 = qPts[1].fY;
  208. double x2 = qPts[2].fX;
  209. double y2 = qPts[2].fY;
  210. double det = x0*y1 - y0*x1 + x2*y0 - y2*x0 + x1*y2 - y1*x2;
  211. if (!sk_float_isfinite(det)
  212. || SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero)) {
  213. // The quad is degenerate. Hopefully this is rare. Find the pts that are
  214. // farthest apart to compute a line (unless it is really a pt).
  215. SkScalar maxD = SkPointPriv::DistanceToSqd(qPts[0], qPts[1]);
  216. int maxEdge = 0;
  217. SkScalar d = SkPointPriv::DistanceToSqd(qPts[1], qPts[2]);
  218. if (d > maxD) {
  219. maxD = d;
  220. maxEdge = 1;
  221. }
  222. d = SkPointPriv::DistanceToSqd(qPts[2], qPts[0]);
  223. if (d > maxD) {
  224. maxD = d;
  225. maxEdge = 2;
  226. }
  227. // We could have a tolerance here, not sure if it would improve anything
  228. if (maxD > 0) {
  229. // Set the matrix to give (u = 0, v = distance_to_line)
  230. SkVector lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge];
  231. // when looking from the point 0 down the line we want positive
  232. // distances to be to the left. This matches the non-degenerate
  233. // case.
  234. lineVec = SkPointPriv::MakeOrthog(lineVec, SkPointPriv::kLeft_Side);
  235. // first row
  236. fM[0] = 0;
  237. fM[1] = 0;
  238. fM[2] = 0;
  239. // second row
  240. fM[3] = lineVec.fX;
  241. fM[4] = lineVec.fY;
  242. fM[5] = -lineVec.dot(qPts[maxEdge]);
  243. } else {
  244. // It's a point. It should cover zero area. Just set the matrix such
  245. // that (u, v) will always be far away from the quad.
  246. fM[0] = 0; fM[1] = 0; fM[2] = 100.f;
  247. fM[3] = 0; fM[4] = 0; fM[5] = 100.f;
  248. }
  249. } else {
  250. double scale = 1.0/det;
  251. // compute adjugate matrix
  252. double a2, a3, a4, a5, a6, a7, a8;
  253. a2 = x1*y2-x2*y1;
  254. a3 = y2-y0;
  255. a4 = x0-x2;
  256. a5 = x2*y0-x0*y2;
  257. a6 = y0-y1;
  258. a7 = x1-x0;
  259. a8 = x0*y1-x1*y0;
  260. // this performs the uv_pts*adjugate(control_pts) multiply,
  261. // then does the scale by 1/det afterwards to improve precision
  262. m[SkMatrix::kMScaleX] = (float)((0.5*a3 + a6)*scale);
  263. m[SkMatrix::kMSkewX] = (float)((0.5*a4 + a7)*scale);
  264. m[SkMatrix::kMTransX] = (float)((0.5*a5 + a8)*scale);
  265. m[SkMatrix::kMSkewY] = (float)(a6*scale);
  266. m[SkMatrix::kMScaleY] = (float)(a7*scale);
  267. m[SkMatrix::kMTransY] = (float)(a8*scale);
  268. // kMPersp0 & kMPersp1 should algebraically be zero
  269. m[SkMatrix::kMPersp0] = 0.0f;
  270. m[SkMatrix::kMPersp1] = 0.0f;
  271. m[SkMatrix::kMPersp2] = (float)((a2 + a5 + a8)*scale);
  272. // It may not be normalized to have 1.0 in the bottom right
  273. float m33 = m.get(SkMatrix::kMPersp2);
  274. if (1.f != m33) {
  275. m33 = 1.f / m33;
  276. fM[0] = m33 * m.get(SkMatrix::kMScaleX);
  277. fM[1] = m33 * m.get(SkMatrix::kMSkewX);
  278. fM[2] = m33 * m.get(SkMatrix::kMTransX);
  279. fM[3] = m33 * m.get(SkMatrix::kMSkewY);
  280. fM[4] = m33 * m.get(SkMatrix::kMScaleY);
  281. fM[5] = m33 * m.get(SkMatrix::kMTransY);
  282. } else {
  283. fM[0] = m.get(SkMatrix::kMScaleX);
  284. fM[1] = m.get(SkMatrix::kMSkewX);
  285. fM[2] = m.get(SkMatrix::kMTransX);
  286. fM[3] = m.get(SkMatrix::kMSkewY);
  287. fM[4] = m.get(SkMatrix::kMScaleY);
  288. fM[5] = m.get(SkMatrix::kMTransY);
  289. }
  290. }
  291. }
  292. ////////////////////////////////////////////////////////////////////////////////
  293. // k = (y2 - y0, x0 - x2, x2*y0 - x0*y2)
  294. // l = (y1 - y0, x0 - x1, x1*y0 - x0*y1) * 2*w
  295. // m = (y2 - y1, x1 - x2, x2*y1 - x1*y2) * 2*w
  296. void GrPathUtils::getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* out) {
  297. SkMatrix& klm = *out;
  298. const SkScalar w2 = 2.f * weight;
  299. klm[0] = p[2].fY - p[0].fY;
  300. klm[1] = p[0].fX - p[2].fX;
  301. klm[2] = p[2].fX * p[0].fY - p[0].fX * p[2].fY;
  302. klm[3] = w2 * (p[1].fY - p[0].fY);
  303. klm[4] = w2 * (p[0].fX - p[1].fX);
  304. klm[5] = w2 * (p[1].fX * p[0].fY - p[0].fX * p[1].fY);
  305. klm[6] = w2 * (p[2].fY - p[1].fY);
  306. klm[7] = w2 * (p[1].fX - p[2].fX);
  307. klm[8] = w2 * (p[2].fX * p[1].fY - p[1].fX * p[2].fY);
  308. // scale the max absolute value of coeffs to 10
  309. SkScalar scale = 0.f;
  310. for (int i = 0; i < 9; ++i) {
  311. scale = SkMaxScalar(scale, SkScalarAbs(klm[i]));
  312. }
  313. SkASSERT(scale > 0.f);
  314. scale = 10.f / scale;
  315. for (int i = 0; i < 9; ++i) {
  316. klm[i] *= scale;
  317. }
  318. }
  319. ////////////////////////////////////////////////////////////////////////////////
  320. namespace {
  321. // a is the first control point of the cubic.
  322. // ab is the vector from a to the second control point.
  323. // dc is the vector from the fourth to the third control point.
  324. // d is the fourth control point.
  325. // p is the candidate quadratic control point.
  326. // this assumes that the cubic doesn't inflect and is simple
  327. bool is_point_within_cubic_tangents(const SkPoint& a,
  328. const SkVector& ab,
  329. const SkVector& dc,
  330. const SkPoint& d,
  331. SkPathPriv::FirstDirection dir,
  332. const SkPoint p) {
  333. SkVector ap = p - a;
  334. SkScalar apXab = ap.cross(ab);
  335. if (SkPathPriv::kCW_FirstDirection == dir) {
  336. if (apXab > 0) {
  337. return false;
  338. }
  339. } else {
  340. SkASSERT(SkPathPriv::kCCW_FirstDirection == dir);
  341. if (apXab < 0) {
  342. return false;
  343. }
  344. }
  345. SkVector dp = p - d;
  346. SkScalar dpXdc = dp.cross(dc);
  347. if (SkPathPriv::kCW_FirstDirection == dir) {
  348. if (dpXdc < 0) {
  349. return false;
  350. }
  351. } else {
  352. SkASSERT(SkPathPriv::kCCW_FirstDirection == dir);
  353. if (dpXdc > 0) {
  354. return false;
  355. }
  356. }
  357. return true;
  358. }
  359. void convert_noninflect_cubic_to_quads(const SkPoint p[4],
  360. SkScalar toleranceSqd,
  361. SkTArray<SkPoint, true>* quads,
  362. int sublevel = 0,
  363. bool preserveFirstTangent = true,
  364. bool preserveLastTangent = true) {
  365. // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is
  366. // p[2]. Point d is always p[3]. Point c is p[2] unless p[2] == p[3], in which case it is p[1].
  367. SkVector ab = p[1] - p[0];
  368. SkVector dc = p[2] - p[3];
  369. if (SkPointPriv::LengthSqd(ab) < SK_ScalarNearlyZero) {
  370. if (SkPointPriv::LengthSqd(dc) < SK_ScalarNearlyZero) {
  371. SkPoint* degQuad = quads->push_back_n(3);
  372. degQuad[0] = p[0];
  373. degQuad[1] = p[0];
  374. degQuad[2] = p[3];
  375. return;
  376. }
  377. ab = p[2] - p[0];
  378. }
  379. if (SkPointPriv::LengthSqd(dc) < SK_ScalarNearlyZero) {
  380. dc = p[1] - p[3];
  381. }
  382. static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
  383. static const int kMaxSubdivs = 10;
  384. ab.scale(kLengthScale);
  385. dc.scale(kLengthScale);
  386. // c0 and c1 are extrapolations along vectors ab and dc.
  387. SkPoint c0 = p[0] + ab;
  388. SkPoint c1 = p[3] + dc;
  389. SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : SkPointPriv::DistanceToSqd(c0, c1);
  390. if (dSqd < toleranceSqd) {
  391. SkPoint newC;
  392. if (preserveFirstTangent == preserveLastTangent) {
  393. // We used to force a split when both tangents need to be preserved and c0 != c1.
  394. // This introduced a large performance regression for tiny paths for no noticeable
  395. // quality improvement. However, we aren't quite fulfilling our contract of guaranteeing
  396. // the two tangent vectors and this could introduce a missed pixel in
  397. // GrAAHairlinePathRenderer.
  398. newC = (c0 + c1) * 0.5f;
  399. } else if (preserveFirstTangent) {
  400. newC = c0;
  401. } else {
  402. newC = c1;
  403. }
  404. SkPoint* pts = quads->push_back_n(3);
  405. pts[0] = p[0];
  406. pts[1] = newC;
  407. pts[2] = p[3];
  408. return;
  409. }
  410. SkPoint choppedPts[7];
  411. SkChopCubicAtHalf(p, choppedPts);
  412. convert_noninflect_cubic_to_quads(
  413. choppedPts + 0, toleranceSqd, quads, sublevel + 1, preserveFirstTangent, false);
  414. convert_noninflect_cubic_to_quads(
  415. choppedPts + 3, toleranceSqd, quads, sublevel + 1, false, preserveLastTangent);
  416. }
  417. void convert_noninflect_cubic_to_quads_with_constraint(const SkPoint p[4],
  418. SkScalar toleranceSqd,
  419. SkPathPriv::FirstDirection dir,
  420. SkTArray<SkPoint, true>* quads,
  421. int sublevel = 0) {
  422. // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is
  423. // p[2]. Point d is always p[3]. Point c is p[2] unless p[2] == p[3], in which case it is p[1].
  424. SkVector ab = p[1] - p[0];
  425. SkVector dc = p[2] - p[3];
  426. if (SkPointPriv::LengthSqd(ab) < SK_ScalarNearlyZero) {
  427. if (SkPointPriv::LengthSqd(dc) < SK_ScalarNearlyZero) {
  428. SkPoint* degQuad = quads->push_back_n(3);
  429. degQuad[0] = p[0];
  430. degQuad[1] = p[0];
  431. degQuad[2] = p[3];
  432. return;
  433. }
  434. ab = p[2] - p[0];
  435. }
  436. if (SkPointPriv::LengthSqd(dc) < SK_ScalarNearlyZero) {
  437. dc = p[1] - p[3];
  438. }
  439. // When the ab and cd tangents are degenerate or nearly parallel with vector from d to a the
  440. // constraint that the quad point falls between the tangents becomes hard to enforce and we are
  441. // likely to hit the max subdivision count. However, in this case the cubic is approaching a
  442. // line and the accuracy of the quad point isn't so important. We check if the two middle cubic
  443. // control points are very close to the baseline vector. If so then we just pick quadratic
  444. // points on the control polygon.
  445. SkVector da = p[0] - p[3];
  446. bool doQuads = SkPointPriv::LengthSqd(dc) < SK_ScalarNearlyZero ||
  447. SkPointPriv::LengthSqd(ab) < SK_ScalarNearlyZero;
  448. if (!doQuads) {
  449. SkScalar invDALengthSqd = SkPointPriv::LengthSqd(da);
  450. if (invDALengthSqd > SK_ScalarNearlyZero) {
  451. invDALengthSqd = SkScalarInvert(invDALengthSqd);
  452. // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a.
  453. // same goes for point c using vector cd.
  454. SkScalar detABSqd = ab.cross(da);
  455. detABSqd = SkScalarSquare(detABSqd);
  456. SkScalar detDCSqd = dc.cross(da);
  457. detDCSqd = SkScalarSquare(detDCSqd);
  458. if (detABSqd * invDALengthSqd < toleranceSqd &&
  459. detDCSqd * invDALengthSqd < toleranceSqd) {
  460. doQuads = true;
  461. }
  462. }
  463. }
  464. if (doQuads) {
  465. SkPoint b = p[0] + ab;
  466. SkPoint c = p[3] + dc;
  467. SkPoint mid = b + c;
  468. mid.scale(SK_ScalarHalf);
  469. // Insert two quadratics to cover the case when ab points away from d and/or dc
  470. // points away from a.
  471. if (SkVector::DotProduct(da, dc) < 0 || SkVector::DotProduct(ab, da) > 0) {
  472. SkPoint* qpts = quads->push_back_n(6);
  473. qpts[0] = p[0];
  474. qpts[1] = b;
  475. qpts[2] = mid;
  476. qpts[3] = mid;
  477. qpts[4] = c;
  478. qpts[5] = p[3];
  479. } else {
  480. SkPoint* qpts = quads->push_back_n(3);
  481. qpts[0] = p[0];
  482. qpts[1] = mid;
  483. qpts[2] = p[3];
  484. }
  485. return;
  486. }
  487. static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
  488. static const int kMaxSubdivs = 10;
  489. ab.scale(kLengthScale);
  490. dc.scale(kLengthScale);
  491. // c0 and c1 are extrapolations along vectors ab and dc.
  492. SkVector c0 = p[0] + ab;
  493. SkVector c1 = p[3] + dc;
  494. SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : SkPointPriv::DistanceToSqd(c0, c1);
  495. if (dSqd < toleranceSqd) {
  496. SkPoint cAvg = (c0 + c1) * 0.5f;
  497. bool subdivide = false;
  498. if (!is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) {
  499. // choose a new cAvg that is the intersection of the two tangent lines.
  500. ab = SkPointPriv::MakeOrthog(ab);
  501. SkScalar z0 = -ab.dot(p[0]);
  502. dc = SkPointPriv::MakeOrthog(dc);
  503. SkScalar z1 = -dc.dot(p[3]);
  504. cAvg.fX = ab.fY * z1 - z0 * dc.fY;
  505. cAvg.fY = z0 * dc.fX - ab.fX * z1;
  506. SkScalar z = ab.fX * dc.fY - ab.fY * dc.fX;
  507. z = SkScalarInvert(z);
  508. cAvg.fX *= z;
  509. cAvg.fY *= z;
  510. if (sublevel <= kMaxSubdivs) {
  511. SkScalar d0Sqd = SkPointPriv::DistanceToSqd(c0, cAvg);
  512. SkScalar d1Sqd = SkPointPriv::DistanceToSqd(c1, cAvg);
  513. // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know
  514. // the distances and tolerance can't be negative.
  515. // (d0 + d1)^2 > toleranceSqd
  516. // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd
  517. SkScalar d0d1 = SkScalarSqrt(d0Sqd * d1Sqd);
  518. subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd;
  519. }
  520. }
  521. if (!subdivide) {
  522. SkPoint* pts = quads->push_back_n(3);
  523. pts[0] = p[0];
  524. pts[1] = cAvg;
  525. pts[2] = p[3];
  526. return;
  527. }
  528. }
  529. SkPoint choppedPts[7];
  530. SkChopCubicAtHalf(p, choppedPts);
  531. convert_noninflect_cubic_to_quads_with_constraint(
  532. choppedPts + 0, toleranceSqd, dir, quads, sublevel + 1);
  533. convert_noninflect_cubic_to_quads_with_constraint(
  534. choppedPts + 3, toleranceSqd, dir, quads, sublevel + 1);
  535. }
  536. }
  537. void GrPathUtils::convertCubicToQuads(const SkPoint p[4],
  538. SkScalar tolScale,
  539. SkTArray<SkPoint, true>* quads) {
  540. if (!p[0].isFinite() || !p[1].isFinite() || !p[2].isFinite() || !p[3].isFinite()) {
  541. return;
  542. }
  543. if (!SkScalarIsFinite(tolScale)) {
  544. return;
  545. }
  546. SkPoint chopped[10];
  547. int count = SkChopCubicAtInflections(p, chopped);
  548. const SkScalar tolSqd = SkScalarSquare(tolScale);
  549. for (int i = 0; i < count; ++i) {
  550. SkPoint* cubic = chopped + 3*i;
  551. convert_noninflect_cubic_to_quads(cubic, tolSqd, quads);
  552. }
  553. }
  554. void GrPathUtils::convertCubicToQuadsConstrainToTangents(const SkPoint p[4],
  555. SkScalar tolScale,
  556. SkPathPriv::FirstDirection dir,
  557. SkTArray<SkPoint, true>* quads) {
  558. if (!p[0].isFinite() || !p[1].isFinite() || !p[2].isFinite() || !p[3].isFinite()) {
  559. return;
  560. }
  561. if (!SkScalarIsFinite(tolScale)) {
  562. return;
  563. }
  564. SkPoint chopped[10];
  565. int count = SkChopCubicAtInflections(p, chopped);
  566. const SkScalar tolSqd = SkScalarSquare(tolScale);
  567. for (int i = 0; i < count; ++i) {
  568. SkPoint* cubic = chopped + 3*i;
  569. convert_noninflect_cubic_to_quads_with_constraint(cubic, tolSqd, dir, quads);
  570. }
  571. }
  572. ////////////////////////////////////////////////////////////////////////////////
  573. using ExcludedTerm = GrPathUtils::ExcludedTerm;
  574. ExcludedTerm GrPathUtils::calcCubicInverseTransposePowerBasisMatrix(const SkPoint p[4],
  575. SkMatrix* out) {
  576. GR_STATIC_ASSERT(SK_SCALAR_IS_FLOAT);
  577. // First convert the bezier coordinates p[0..3] to power basis coefficients X,Y(,W=[0 0 0 1]).
  578. // M3 is the matrix that does this conversion. The homogeneous equation for the cubic becomes:
  579. //
  580. // | X Y 0 |
  581. // C(t,s) = [t^3 t^2*s t*s^2 s^3] * | . . 0 |
  582. // | . . 0 |
  583. // | . . 1 |
  584. //
  585. const Sk4f M3[3] = {Sk4f(-1, 3, -3, 1),
  586. Sk4f(3, -6, 3, 0),
  587. Sk4f(-3, 3, 0, 0)};
  588. // 4th col of M3 = Sk4f(1, 0, 0, 0)};
  589. Sk4f X(p[3].x(), 0, 0, 0);
  590. Sk4f Y(p[3].y(), 0, 0, 0);
  591. for (int i = 2; i >= 0; --i) {
  592. X += M3[i] * p[i].x();
  593. Y += M3[i] * p[i].y();
  594. }
  595. // The matrix is 3x4. In order to invert it, we first need to make it square by throwing out one
  596. // of the middle two rows. We toss the row that leaves us with the largest absolute determinant.
  597. // Since the right column will be [0 0 1], the respective determinants reduce to x0*y2 - y0*x2
  598. // and x0*y1 - y0*x1.
  599. SkScalar dets[4];
  600. Sk4f D = SkNx_shuffle<0,0,2,1>(X) * SkNx_shuffle<2,1,0,0>(Y);
  601. D -= SkNx_shuffle<2,3,0,1>(D);
  602. D.store(dets);
  603. ExcludedTerm skipTerm = SkScalarAbs(dets[0]) > SkScalarAbs(dets[1]) ?
  604. ExcludedTerm::kQuadraticTerm : ExcludedTerm::kLinearTerm;
  605. SkScalar det = dets[ExcludedTerm::kQuadraticTerm == skipTerm ? 0 : 1];
  606. if (0 == det) {
  607. return ExcludedTerm::kNonInvertible;
  608. }
  609. SkScalar rdet = 1 / det;
  610. // Compute the inverse-transpose of the power basis matrix with the 'skipRow'th row removed.
  611. // Since W=[0 0 0 1], it follows that our corresponding solution will be equal to:
  612. //
  613. // | y1 -x1 x1*y2 - y1*x2 |
  614. // 1/det * | -y0 x0 -x0*y2 + y0*x2 |
  615. // | 0 0 det |
  616. //
  617. SkScalar x[4], y[4], z[4];
  618. X.store(x);
  619. Y.store(y);
  620. (X * SkNx_shuffle<3,3,3,3>(Y) - Y * SkNx_shuffle<3,3,3,3>(X)).store(z);
  621. int middleRow = ExcludedTerm::kQuadraticTerm == skipTerm ? 2 : 1;
  622. out->setAll( y[middleRow] * rdet, -x[middleRow] * rdet, z[middleRow] * rdet,
  623. -y[0] * rdet, x[0] * rdet, -z[0] * rdet,
  624. 0, 0, 1);
  625. return skipTerm;
  626. }
  627. inline static void calc_serp_kcoeffs(SkScalar tl, SkScalar sl, SkScalar tm, SkScalar sm,
  628. ExcludedTerm skipTerm, SkScalar outCoeffs[3]) {
  629. SkASSERT(ExcludedTerm::kQuadraticTerm == skipTerm || ExcludedTerm::kLinearTerm == skipTerm);
  630. outCoeffs[0] = 0;
  631. outCoeffs[1] = (ExcludedTerm::kLinearTerm == skipTerm) ? sl*sm : -tl*sm - tm*sl;
  632. outCoeffs[2] = tl*tm;
  633. }
  634. inline static void calc_serp_lmcoeffs(SkScalar t, SkScalar s, ExcludedTerm skipTerm,
  635. SkScalar outCoeffs[3]) {
  636. SkASSERT(ExcludedTerm::kQuadraticTerm == skipTerm || ExcludedTerm::kLinearTerm == skipTerm);
  637. outCoeffs[0] = -s*s*s;
  638. outCoeffs[1] = (ExcludedTerm::kLinearTerm == skipTerm) ? 3*s*s*t : -3*s*t*t;
  639. outCoeffs[2] = t*t*t;
  640. }
  641. inline static void calc_loop_kcoeffs(SkScalar td, SkScalar sd, SkScalar te, SkScalar se,
  642. SkScalar tdse, SkScalar tesd, ExcludedTerm skipTerm,
  643. SkScalar outCoeffs[3]) {
  644. SkASSERT(ExcludedTerm::kQuadraticTerm == skipTerm || ExcludedTerm::kLinearTerm == skipTerm);
  645. outCoeffs[0] = 0;
  646. outCoeffs[1] = (ExcludedTerm::kLinearTerm == skipTerm) ? sd*se : -tdse - tesd;
  647. outCoeffs[2] = td*te;
  648. }
  649. inline static void calc_loop_lmcoeffs(SkScalar t2, SkScalar s2, SkScalar t1, SkScalar s1,
  650. SkScalar t2s1, SkScalar t1s2, ExcludedTerm skipTerm,
  651. SkScalar outCoeffs[3]) {
  652. SkASSERT(ExcludedTerm::kQuadraticTerm == skipTerm || ExcludedTerm::kLinearTerm == skipTerm);
  653. outCoeffs[0] = -s2*s2*s1;
  654. outCoeffs[1] = (ExcludedTerm::kLinearTerm == skipTerm) ? s2 * (2*t2s1 + t1s2)
  655. : -t2 * (t2s1 + 2*t1s2);
  656. outCoeffs[2] = t2*t2*t1;
  657. }
  658. // For the case when a cubic bezier is actually a quadratic. We duplicate k in l so that the
  659. // implicit becomes:
  660. //
  661. // k^3 - l*m == k^3 - l*k == k * (k^2 - l)
  662. //
  663. // In the quadratic case we can simply assign fixed values at each control point:
  664. //
  665. // | ..K.. | | pts[0] pts[1] pts[2] pts[3] | | 0 1/3 2/3 1 |
  666. // | ..L.. | * | . . . . | == | 0 0 1/3 1 |
  667. // | ..K.. | | 1 1 1 1 | | 0 1/3 2/3 1 |
  668. //
  669. static void calc_quadratic_klm(const SkPoint pts[4], double d3, SkMatrix* klm) {
  670. SkMatrix klmAtPts;
  671. klmAtPts.setAll(0, 1.f/3, 1,
  672. 0, 0, 1,
  673. 0, 1.f/3, 1);
  674. SkMatrix inversePts;
  675. inversePts.setAll(pts[0].x(), pts[1].x(), pts[3].x(),
  676. pts[0].y(), pts[1].y(), pts[3].y(),
  677. 1, 1, 1);
  678. SkAssertResult(inversePts.invert(&inversePts));
  679. klm->setConcat(klmAtPts, inversePts);
  680. // If d3 > 0 we need to flip the orientation of our curve
  681. // This is done by negating the k and l values
  682. if (d3 > 0) {
  683. klm->postScale(-1, -1);
  684. }
  685. }
  686. // For the case when a cubic bezier is actually a line. We set K=0, L=1, M=-line, which results in
  687. // the following implicit:
  688. //
  689. // k^3 - l*m == 0^3 - 1*(-line) == -(-line) == line
  690. //
  691. static void calc_line_klm(const SkPoint pts[4], SkMatrix* klm) {
  692. SkScalar ny = pts[0].x() - pts[3].x();
  693. SkScalar nx = pts[3].y() - pts[0].y();
  694. SkScalar k = nx * pts[0].x() + ny * pts[0].y();
  695. klm->setAll( 0, 0, 0,
  696. 0, 0, 1,
  697. -nx, -ny, k);
  698. }
  699. SkCubicType GrPathUtils::getCubicKLM(const SkPoint src[4], SkMatrix* klm, double tt[2],
  700. double ss[2]) {
  701. double d[4];
  702. SkCubicType type = SkClassifyCubic(src, tt, ss, d);
  703. if (SkCubicType::kLineOrPoint == type) {
  704. calc_line_klm(src, klm);
  705. return SkCubicType::kLineOrPoint;
  706. }
  707. if (SkCubicType::kQuadratic == type) {
  708. calc_quadratic_klm(src, d[3], klm);
  709. return SkCubicType::kQuadratic;
  710. }
  711. SkMatrix CIT;
  712. ExcludedTerm skipTerm = calcCubicInverseTransposePowerBasisMatrix(src, &CIT);
  713. if (ExcludedTerm::kNonInvertible == skipTerm) {
  714. // This could technically also happen if the curve were quadratic, but SkClassifyCubic
  715. // should have detected that case already with tolerance.
  716. calc_line_klm(src, klm);
  717. return SkCubicType::kLineOrPoint;
  718. }
  719. const SkScalar t0 = static_cast<SkScalar>(tt[0]), t1 = static_cast<SkScalar>(tt[1]),
  720. s0 = static_cast<SkScalar>(ss[0]), s1 = static_cast<SkScalar>(ss[1]);
  721. SkMatrix klmCoeffs;
  722. switch (type) {
  723. case SkCubicType::kCuspAtInfinity:
  724. SkASSERT(1 == t1 && 0 == s1); // Infinity.
  725. // fallthru.
  726. case SkCubicType::kLocalCusp:
  727. case SkCubicType::kSerpentine:
  728. calc_serp_kcoeffs(t0, s0, t1, s1, skipTerm, &klmCoeffs[0]);
  729. calc_serp_lmcoeffs(t0, s0, skipTerm, &klmCoeffs[3]);
  730. calc_serp_lmcoeffs(t1, s1, skipTerm, &klmCoeffs[6]);
  731. break;
  732. case SkCubicType::kLoop: {
  733. const SkScalar tdse = t0 * s1;
  734. const SkScalar tesd = t1 * s0;
  735. calc_loop_kcoeffs(t0, s0, t1, s1, tdse, tesd, skipTerm, &klmCoeffs[0]);
  736. calc_loop_lmcoeffs(t0, s0, t1, s1, tdse, tesd, skipTerm, &klmCoeffs[3]);
  737. calc_loop_lmcoeffs(t1, s1, t0, s0, tesd, tdse, skipTerm, &klmCoeffs[6]);
  738. break;
  739. }
  740. default:
  741. SK_ABORT("Unexpected cubic type.");
  742. break;
  743. }
  744. klm->setConcat(klmCoeffs, CIT);
  745. return type;
  746. }
  747. int GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm,
  748. int* loopIndex) {
  749. SkSTArray<2, SkScalar> chops;
  750. *loopIndex = -1;
  751. double t[2], s[2];
  752. if (SkCubicType::kLoop == GrPathUtils::getCubicKLM(src, klm, t, s)) {
  753. SkScalar t0 = static_cast<SkScalar>(t[0] / s[0]);
  754. SkScalar t1 = static_cast<SkScalar>(t[1] / s[1]);
  755. SkASSERT(t0 <= t1); // Technically t0 != t1 in a loop, but there may be FP error.
  756. if (t0 < 1 && t1 > 0) {
  757. *loopIndex = 0;
  758. if (t0 > 0) {
  759. chops.push_back(t0);
  760. *loopIndex = 1;
  761. }
  762. if (t1 < 1) {
  763. chops.push_back(t1);
  764. *loopIndex = chops.count() - 1;
  765. }
  766. }
  767. }
  768. SkChopCubicAt(src, dst, chops.begin(), chops.count());
  769. return chops.count() + 1;
  770. }