GrDistanceFieldGenFromVector.cpp 31 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879
  1. /*
  2. * Copyright 2017 ARM Ltd.
  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/core/SkDistanceFieldGen.h"
  8. #include "src/gpu/GrDistanceFieldGenFromVector.h"
  9. #include "include/core/SkMatrix.h"
  10. #include "include/gpu/GrConfig.h"
  11. #include "include/pathops/SkPathOps.h"
  12. #include "src/core/SkAutoMalloc.h"
  13. #include "src/core/SkGeometry.h"
  14. #include "src/core/SkPointPriv.h"
  15. #include "src/core/SkRectPriv.h"
  16. #include "src/gpu/geometry/GrPathUtils.h"
  17. /**
  18. * If a scanline (a row of texel) cross from the kRight_SegSide
  19. * of a segment to the kLeft_SegSide, the winding score should
  20. * add 1.
  21. * And winding score should subtract 1 if the scanline cross
  22. * from kLeft_SegSide to kRight_SegSide.
  23. * Always return kNA_SegSide if the scanline does not cross over
  24. * the segment. Winding score should be zero in this case.
  25. * You can get the winding number for each texel of the scanline
  26. * by adding the winding score from left to right.
  27. * Assuming we always start from outside, so the winding number
  28. * should always start from zero.
  29. * ________ ________
  30. * | | | |
  31. * ...R|L......L|R.....L|R......R|L..... <= Scanline & side of segment
  32. * |+1 |-1 |-1 |+1 <= Winding score
  33. * 0 | 1 ^ 0 ^ -1 |0 <= Winding number
  34. * |________| |________|
  35. *
  36. * .......NA................NA..........
  37. * 0 0
  38. */
  39. enum SegSide {
  40. kLeft_SegSide = -1,
  41. kOn_SegSide = 0,
  42. kRight_SegSide = 1,
  43. kNA_SegSide = 2,
  44. };
  45. struct DFData {
  46. float fDistSq; // distance squared to nearest (so far) edge
  47. int fDeltaWindingScore; // +1 or -1 whenever a scanline cross over a segment
  48. };
  49. ///////////////////////////////////////////////////////////////////////////////
  50. /*
  51. * Type definition for double precision DPoint and DAffineMatrix
  52. */
  53. // Point with double precision
  54. struct DPoint {
  55. double fX, fY;
  56. static DPoint Make(double x, double y) {
  57. DPoint pt;
  58. pt.set(x, y);
  59. return pt;
  60. }
  61. double x() const { return fX; }
  62. double y() const { return fY; }
  63. void set(double x, double y) { fX = x; fY = y; }
  64. /** Returns the euclidian distance from (0,0) to (x,y)
  65. */
  66. static double Length(double x, double y) {
  67. return sqrt(x * x + y * y);
  68. }
  69. /** Returns the euclidian distance between a and b
  70. */
  71. static double Distance(const DPoint& a, const DPoint& b) {
  72. return Length(a.fX - b.fX, a.fY - b.fY);
  73. }
  74. double distanceToSqd(const DPoint& pt) const {
  75. double dx = fX - pt.fX;
  76. double dy = fY - pt.fY;
  77. return dx * dx + dy * dy;
  78. }
  79. };
  80. // Matrix with double precision for affine transformation.
  81. // We don't store row 3 because its always (0, 0, 1).
  82. class DAffineMatrix {
  83. public:
  84. double operator[](int index) const {
  85. SkASSERT((unsigned)index < 6);
  86. return fMat[index];
  87. }
  88. double& operator[](int index) {
  89. SkASSERT((unsigned)index < 6);
  90. return fMat[index];
  91. }
  92. void setAffine(double m11, double m12, double m13,
  93. double m21, double m22, double m23) {
  94. fMat[0] = m11;
  95. fMat[1] = m12;
  96. fMat[2] = m13;
  97. fMat[3] = m21;
  98. fMat[4] = m22;
  99. fMat[5] = m23;
  100. }
  101. /** Set the matrix to identity
  102. */
  103. void reset() {
  104. fMat[0] = fMat[4] = 1.0;
  105. fMat[1] = fMat[3] =
  106. fMat[2] = fMat[5] = 0.0;
  107. }
  108. // alias for reset()
  109. void setIdentity() { this->reset(); }
  110. DPoint mapPoint(const SkPoint& src) const {
  111. DPoint pt = DPoint::Make(src.x(), src.y());
  112. return this->mapPoint(pt);
  113. }
  114. DPoint mapPoint(const DPoint& src) const {
  115. return DPoint::Make(fMat[0] * src.x() + fMat[1] * src.y() + fMat[2],
  116. fMat[3] * src.x() + fMat[4] * src.y() + fMat[5]);
  117. }
  118. private:
  119. double fMat[6];
  120. };
  121. ///////////////////////////////////////////////////////////////////////////////
  122. static const double kClose = (SK_Scalar1 / 16.0);
  123. static const double kCloseSqd = kClose * kClose;
  124. static const double kNearlyZero = (SK_Scalar1 / (1 << 18));
  125. static const double kTangentTolerance = (SK_Scalar1 / (1 << 11));
  126. static const float kConicTolerance = 0.25f;
  127. static inline bool between_closed_open(double a, double b, double c,
  128. double tolerance = 0.0,
  129. bool xformToleranceToX = false) {
  130. SkASSERT(tolerance >= 0.0);
  131. double tolB = tolerance;
  132. double tolC = tolerance;
  133. if (xformToleranceToX) {
  134. // Canonical space is y = x^2 and the derivative of x^2 is 2x.
  135. // So the slope of the tangent line at point (x, x^2) is 2x.
  136. //
  137. // /|
  138. // sqrt(2x * 2x + 1 * 1) / | 2x
  139. // /__|
  140. // 1
  141. tolB = tolerance / sqrt(4.0 * b * b + 1.0);
  142. tolC = tolerance / sqrt(4.0 * c * c + 1.0);
  143. }
  144. return b < c ? (a >= b - tolB && a < c - tolC) :
  145. (a >= c - tolC && a < b - tolB);
  146. }
  147. static inline bool between_closed(double a, double b, double c,
  148. double tolerance = 0.0,
  149. bool xformToleranceToX = false) {
  150. SkASSERT(tolerance >= 0.0);
  151. double tolB = tolerance;
  152. double tolC = tolerance;
  153. if (xformToleranceToX) {
  154. tolB = tolerance / sqrt(4.0 * b * b + 1.0);
  155. tolC = tolerance / sqrt(4.0 * c * c + 1.0);
  156. }
  157. return b < c ? (a >= b - tolB && a <= c + tolC) :
  158. (a >= c - tolC && a <= b + tolB);
  159. }
  160. static inline bool nearly_zero(double x, double tolerance = kNearlyZero) {
  161. SkASSERT(tolerance >= 0.0);
  162. return fabs(x) <= tolerance;
  163. }
  164. static inline bool nearly_equal(double x, double y,
  165. double tolerance = kNearlyZero,
  166. bool xformToleranceToX = false) {
  167. SkASSERT(tolerance >= 0.0);
  168. if (xformToleranceToX) {
  169. tolerance = tolerance / sqrt(4.0 * y * y + 1.0);
  170. }
  171. return fabs(x - y) <= tolerance;
  172. }
  173. static inline double sign_of(const double &val) {
  174. return (val < 0.0) ? -1.0 : 1.0;
  175. }
  176. static bool is_colinear(const SkPoint pts[3]) {
  177. return nearly_zero((pts[1].y() - pts[0].y()) * (pts[1].x() - pts[2].x()) -
  178. (pts[1].y() - pts[2].y()) * (pts[1].x() - pts[0].x()), kCloseSqd);
  179. }
  180. class PathSegment {
  181. public:
  182. enum {
  183. // These enum values are assumed in member functions below.
  184. kLine = 0,
  185. kQuad = 1,
  186. } fType;
  187. // line uses 2 pts, quad uses 3 pts
  188. SkPoint fPts[3];
  189. DPoint fP0T, fP2T;
  190. DAffineMatrix fXformMatrix;
  191. double fScalingFactor;
  192. double fScalingFactorSqd;
  193. double fNearlyZeroScaled;
  194. double fTangentTolScaledSqd;
  195. SkRect fBoundingBox;
  196. void init();
  197. int countPoints() {
  198. GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
  199. return fType + 2;
  200. }
  201. const SkPoint& endPt() const {
  202. GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
  203. return fPts[fType + 1];
  204. }
  205. };
  206. typedef SkTArray<PathSegment, true> PathSegmentArray;
  207. void PathSegment::init() {
  208. const DPoint p0 = DPoint::Make(fPts[0].x(), fPts[0].y());
  209. const DPoint p2 = DPoint::Make(this->endPt().x(), this->endPt().y());
  210. const double p0x = p0.x();
  211. const double p0y = p0.y();
  212. const double p2x = p2.x();
  213. const double p2y = p2.y();
  214. fBoundingBox.set(fPts[0], this->endPt());
  215. if (fType == PathSegment::kLine) {
  216. fScalingFactorSqd = fScalingFactor = 1.0;
  217. double hypotenuse = DPoint::Distance(p0, p2);
  218. const double cosTheta = (p2x - p0x) / hypotenuse;
  219. const double sinTheta = (p2y - p0y) / hypotenuse;
  220. fXformMatrix.setAffine(
  221. cosTheta, sinTheta, -(cosTheta * p0x) - (sinTheta * p0y),
  222. -sinTheta, cosTheta, (sinTheta * p0x) - (cosTheta * p0y)
  223. );
  224. } else {
  225. SkASSERT(fType == PathSegment::kQuad);
  226. // Calculate bounding box
  227. const SkPoint _P1mP0 = fPts[1] - fPts[0];
  228. SkPoint t = _P1mP0 - fPts[2] + fPts[1];
  229. t.fX = _P1mP0.x() / t.x();
  230. t.fY = _P1mP0.y() / t.y();
  231. t.fX = SkScalarClampMax(t.x(), 1.0);
  232. t.fY = SkScalarClampMax(t.y(), 1.0);
  233. t.fX = _P1mP0.x() * t.x();
  234. t.fY = _P1mP0.y() * t.y();
  235. const SkPoint m = fPts[0] + t;
  236. SkRectPriv::GrowToInclude(&fBoundingBox, m);
  237. const double p1x = fPts[1].x();
  238. const double p1y = fPts[1].y();
  239. const double p0xSqd = p0x * p0x;
  240. const double p0ySqd = p0y * p0y;
  241. const double p2xSqd = p2x * p2x;
  242. const double p2ySqd = p2y * p2y;
  243. const double p1xSqd = p1x * p1x;
  244. const double p1ySqd = p1y * p1y;
  245. const double p01xProd = p0x * p1x;
  246. const double p02xProd = p0x * p2x;
  247. const double b12xProd = p1x * p2x;
  248. const double p01yProd = p0y * p1y;
  249. const double p02yProd = p0y * p2y;
  250. const double b12yProd = p1y * p2y;
  251. const double sqrtA = p0y - (2.0 * p1y) + p2y;
  252. const double a = sqrtA * sqrtA;
  253. const double h = -1.0 * (p0y - (2.0 * p1y) + p2y) * (p0x - (2.0 * p1x) + p2x);
  254. const double sqrtB = p0x - (2.0 * p1x) + p2x;
  255. const double b = sqrtB * sqrtB;
  256. const double c = (p0xSqd * p2ySqd) - (4.0 * p01xProd * b12yProd)
  257. - (2.0 * p02xProd * p02yProd) + (4.0 * p02xProd * p1ySqd)
  258. + (4.0 * p1xSqd * p02yProd) - (4.0 * b12xProd * p01yProd)
  259. + (p2xSqd * p0ySqd);
  260. const double g = (p0x * p02yProd) - (2.0 * p0x * p1ySqd)
  261. + (2.0 * p0x * b12yProd) - (p0x * p2ySqd)
  262. + (2.0 * p1x * p01yProd) - (4.0 * p1x * p02yProd)
  263. + (2.0 * p1x * b12yProd) - (p2x * p0ySqd)
  264. + (2.0 * p2x * p01yProd) + (p2x * p02yProd)
  265. - (2.0 * p2x * p1ySqd);
  266. const double f = -((p0xSqd * p2y) - (2.0 * p01xProd * p1y)
  267. - (2.0 * p01xProd * p2y) - (p02xProd * p0y)
  268. + (4.0 * p02xProd * p1y) - (p02xProd * p2y)
  269. + (2.0 * p1xSqd * p0y) + (2.0 * p1xSqd * p2y)
  270. - (2.0 * b12xProd * p0y) - (2.0 * b12xProd * p1y)
  271. + (p2xSqd * p0y));
  272. const double cosTheta = sqrt(a / (a + b));
  273. const double sinTheta = -1.0 * sign_of((a + b) * h) * sqrt(b / (a + b));
  274. const double gDef = cosTheta * g - sinTheta * f;
  275. const double fDef = sinTheta * g + cosTheta * f;
  276. const double x0 = gDef / (a + b);
  277. const double y0 = (1.0 / (2.0 * fDef)) * (c - (gDef * gDef / (a + b)));
  278. const double lambda = -1.0 * ((a + b) / (2.0 * fDef));
  279. fScalingFactor = fabs(1.0 / lambda);
  280. fScalingFactorSqd = fScalingFactor * fScalingFactor;
  281. const double lambda_cosTheta = lambda * cosTheta;
  282. const double lambda_sinTheta = lambda * sinTheta;
  283. fXformMatrix.setAffine(
  284. lambda_cosTheta, -lambda_sinTheta, lambda * x0,
  285. lambda_sinTheta, lambda_cosTheta, lambda * y0
  286. );
  287. }
  288. fNearlyZeroScaled = kNearlyZero / fScalingFactor;
  289. fTangentTolScaledSqd = kTangentTolerance * kTangentTolerance / fScalingFactorSqd;
  290. fP0T = fXformMatrix.mapPoint(p0);
  291. fP2T = fXformMatrix.mapPoint(p2);
  292. }
  293. static void init_distances(DFData* data, int size) {
  294. DFData* currData = data;
  295. for (int i = 0; i < size; ++i) {
  296. // init distance to "far away"
  297. currData->fDistSq = SK_DistanceFieldMagnitude * SK_DistanceFieldMagnitude;
  298. currData->fDeltaWindingScore = 0;
  299. ++currData;
  300. }
  301. }
  302. static inline void add_line_to_segment(const SkPoint pts[2],
  303. PathSegmentArray* segments) {
  304. segments->push_back();
  305. segments->back().fType = PathSegment::kLine;
  306. segments->back().fPts[0] = pts[0];
  307. segments->back().fPts[1] = pts[1];
  308. segments->back().init();
  309. }
  310. static inline void add_quad_segment(const SkPoint pts[3],
  311. PathSegmentArray* segments) {
  312. if (SkPointPriv::DistanceToSqd(pts[0], pts[1]) < kCloseSqd ||
  313. SkPointPriv::DistanceToSqd(pts[1], pts[2]) < kCloseSqd ||
  314. is_colinear(pts)) {
  315. if (pts[0] != pts[2]) {
  316. SkPoint line_pts[2];
  317. line_pts[0] = pts[0];
  318. line_pts[1] = pts[2];
  319. add_line_to_segment(line_pts, segments);
  320. }
  321. } else {
  322. segments->push_back();
  323. segments->back().fType = PathSegment::kQuad;
  324. segments->back().fPts[0] = pts[0];
  325. segments->back().fPts[1] = pts[1];
  326. segments->back().fPts[2] = pts[2];
  327. segments->back().init();
  328. }
  329. }
  330. static inline void add_cubic_segments(const SkPoint pts[4],
  331. PathSegmentArray* segments) {
  332. SkSTArray<15, SkPoint, true> quads;
  333. GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, &quads);
  334. int count = quads.count();
  335. for (int q = 0; q < count; q += 3) {
  336. add_quad_segment(&quads[q], segments);
  337. }
  338. }
  339. static float calculate_nearest_point_for_quad(
  340. const PathSegment& segment,
  341. const DPoint &xFormPt) {
  342. static const float kThird = 0.33333333333f;
  343. static const float kTwentySeventh = 0.037037037f;
  344. const float a = 0.5f - (float)xFormPt.y();
  345. const float b = -0.5f * (float)xFormPt.x();
  346. const float a3 = a * a * a;
  347. const float b2 = b * b;
  348. const float c = (b2 * 0.25f) + (a3 * kTwentySeventh);
  349. if (c >= 0.f) {
  350. const float sqrtC = sqrt(c);
  351. const float result = (float)cbrt((-b * 0.5f) + sqrtC) + (float)cbrt((-b * 0.5f) - sqrtC);
  352. return result;
  353. } else {
  354. const float cosPhi = (float)sqrt((b2 * 0.25f) * (-27.f / a3)) * ((b > 0) ? -1.f : 1.f);
  355. const float phi = (float)acos(cosPhi);
  356. float result;
  357. if (xFormPt.x() > 0.f) {
  358. result = 2.f * (float)sqrt(-a * kThird) * (float)cos(phi * kThird);
  359. if (!between_closed(result, segment.fP0T.x(), segment.fP2T.x())) {
  360. result = 2.f * (float)sqrt(-a * kThird) * (float)cos((phi * kThird) + (SK_ScalarPI * 2.f * kThird));
  361. }
  362. } else {
  363. result = 2.f * (float)sqrt(-a * kThird) * (float)cos((phi * kThird) + (SK_ScalarPI * 2.f * kThird));
  364. if (!between_closed(result, segment.fP0T.x(), segment.fP2T.x())) {
  365. result = 2.f * (float)sqrt(-a * kThird) * (float)cos(phi * kThird);
  366. }
  367. }
  368. return result;
  369. }
  370. }
  371. // This structure contains some intermediate values shared by the same row.
  372. // It is used to calculate segment side of a quadratic bezier.
  373. struct RowData {
  374. // The intersection type of a scanline and y = x * x parabola in canonical space.
  375. enum IntersectionType {
  376. kNoIntersection,
  377. kVerticalLine,
  378. kTangentLine,
  379. kTwoPointsIntersect
  380. } fIntersectionType;
  381. // The direction of the quadratic segment/scanline in the canonical space.
  382. // 1: The quadratic segment/scanline going from negative x-axis to positive x-axis.
  383. // 0: The scanline is a vertical line in the canonical space.
  384. // -1: The quadratic segment/scanline going from positive x-axis to negative x-axis.
  385. int fQuadXDirection;
  386. int fScanlineXDirection;
  387. // The y-value(equal to x*x) of intersection point for the kVerticalLine intersection type.
  388. double fYAtIntersection;
  389. // The x-value for two intersection points.
  390. double fXAtIntersection1;
  391. double fXAtIntersection2;
  392. };
  393. void precomputation_for_row(
  394. RowData *rowData,
  395. const PathSegment& segment,
  396. const SkPoint& pointLeft,
  397. const SkPoint& pointRight
  398. ) {
  399. if (segment.fType != PathSegment::kQuad) {
  400. return;
  401. }
  402. const DPoint& xFormPtLeft = segment.fXformMatrix.mapPoint(pointLeft);
  403. const DPoint& xFormPtRight = segment.fXformMatrix.mapPoint(pointRight);
  404. rowData->fQuadXDirection = (int)sign_of(segment.fP2T.x() - segment.fP0T.x());
  405. rowData->fScanlineXDirection = (int)sign_of(xFormPtRight.x() - xFormPtLeft.x());
  406. const double x1 = xFormPtLeft.x();
  407. const double y1 = xFormPtLeft.y();
  408. const double x2 = xFormPtRight.x();
  409. const double y2 = xFormPtRight.y();
  410. if (nearly_equal(x1, x2, segment.fNearlyZeroScaled, true)) {
  411. rowData->fIntersectionType = RowData::kVerticalLine;
  412. rowData->fYAtIntersection = x1 * x1;
  413. rowData->fScanlineXDirection = 0;
  414. return;
  415. }
  416. // Line y = mx + b
  417. const double m = (y2 - y1) / (x2 - x1);
  418. const double b = -m * x1 + y1;
  419. const double m2 = m * m;
  420. const double c = m2 + 4.0 * b;
  421. const double tol = 4.0 * segment.fTangentTolScaledSqd / (m2 + 1.0);
  422. // Check if the scanline is the tangent line of the curve,
  423. // and the curve start or end at the same y-coordinate of the scanline
  424. if ((rowData->fScanlineXDirection == 1 &&
  425. (segment.fPts[0].y() == pointLeft.y() ||
  426. segment.fPts[2].y() == pointLeft.y())) &&
  427. nearly_zero(c, tol)) {
  428. rowData->fIntersectionType = RowData::kTangentLine;
  429. rowData->fXAtIntersection1 = m / 2.0;
  430. rowData->fXAtIntersection2 = m / 2.0;
  431. } else if (c <= 0.0) {
  432. rowData->fIntersectionType = RowData::kNoIntersection;
  433. return;
  434. } else {
  435. rowData->fIntersectionType = RowData::kTwoPointsIntersect;
  436. const double d = sqrt(c);
  437. rowData->fXAtIntersection1 = (m + d) / 2.0;
  438. rowData->fXAtIntersection2 = (m - d) / 2.0;
  439. }
  440. }
  441. SegSide calculate_side_of_quad(
  442. const PathSegment& segment,
  443. const SkPoint& point,
  444. const DPoint& xFormPt,
  445. const RowData& rowData) {
  446. SegSide side = kNA_SegSide;
  447. if (RowData::kVerticalLine == rowData.fIntersectionType) {
  448. side = (SegSide)(int)(sign_of(xFormPt.y() - rowData.fYAtIntersection) * rowData.fQuadXDirection);
  449. }
  450. else if (RowData::kTwoPointsIntersect == rowData.fIntersectionType) {
  451. const double p1 = rowData.fXAtIntersection1;
  452. const double p2 = rowData.fXAtIntersection2;
  453. int signP1 = (int)sign_of(p1 - xFormPt.x());
  454. bool includeP1 = true;
  455. bool includeP2 = true;
  456. if (rowData.fScanlineXDirection == 1) {
  457. if ((rowData.fQuadXDirection == -1 && segment.fPts[0].y() <= point.y() &&
  458. nearly_equal(segment.fP0T.x(), p1, segment.fNearlyZeroScaled, true)) ||
  459. (rowData.fQuadXDirection == 1 && segment.fPts[2].y() <= point.y() &&
  460. nearly_equal(segment.fP2T.x(), p1, segment.fNearlyZeroScaled, true))) {
  461. includeP1 = false;
  462. }
  463. if ((rowData.fQuadXDirection == -1 && segment.fPts[2].y() <= point.y() &&
  464. nearly_equal(segment.fP2T.x(), p2, segment.fNearlyZeroScaled, true)) ||
  465. (rowData.fQuadXDirection == 1 && segment.fPts[0].y() <= point.y() &&
  466. nearly_equal(segment.fP0T.x(), p2, segment.fNearlyZeroScaled, true))) {
  467. includeP2 = false;
  468. }
  469. }
  470. if (includeP1 && between_closed(p1, segment.fP0T.x(), segment.fP2T.x(),
  471. segment.fNearlyZeroScaled, true)) {
  472. side = (SegSide)(signP1 * rowData.fQuadXDirection);
  473. }
  474. if (includeP2 && between_closed(p2, segment.fP0T.x(), segment.fP2T.x(),
  475. segment.fNearlyZeroScaled, true)) {
  476. int signP2 = (int)sign_of(p2 - xFormPt.x());
  477. if (side == kNA_SegSide || signP2 == 1) {
  478. side = (SegSide)(-signP2 * rowData.fQuadXDirection);
  479. }
  480. }
  481. } else if (RowData::kTangentLine == rowData.fIntersectionType) {
  482. // The scanline is the tangent line of current quadratic segment.
  483. const double p = rowData.fXAtIntersection1;
  484. int signP = (int)sign_of(p - xFormPt.x());
  485. if (rowData.fScanlineXDirection == 1) {
  486. // The path start or end at the tangent point.
  487. if (segment.fPts[0].y() == point.y()) {
  488. side = (SegSide)(signP);
  489. } else if (segment.fPts[2].y() == point.y()) {
  490. side = (SegSide)(-signP);
  491. }
  492. }
  493. }
  494. return side;
  495. }
  496. static float distance_to_segment(const SkPoint& point,
  497. const PathSegment& segment,
  498. const RowData& rowData,
  499. SegSide* side) {
  500. SkASSERT(side);
  501. const DPoint xformPt = segment.fXformMatrix.mapPoint(point);
  502. if (segment.fType == PathSegment::kLine) {
  503. float result = SK_DistanceFieldPad * SK_DistanceFieldPad;
  504. if (between_closed(xformPt.x(), segment.fP0T.x(), segment.fP2T.x())) {
  505. result = (float)(xformPt.y() * xformPt.y());
  506. } else if (xformPt.x() < segment.fP0T.x()) {
  507. result = (float)(xformPt.x() * xformPt.x() + xformPt.y() * xformPt.y());
  508. } else {
  509. result = (float)((xformPt.x() - segment.fP2T.x()) * (xformPt.x() - segment.fP2T.x())
  510. + xformPt.y() * xformPt.y());
  511. }
  512. if (between_closed_open(point.y(), segment.fBoundingBox.top(),
  513. segment.fBoundingBox.bottom())) {
  514. *side = (SegSide)(int)sign_of(xformPt.y());
  515. } else {
  516. *side = kNA_SegSide;
  517. }
  518. return result;
  519. } else {
  520. SkASSERT(segment.fType == PathSegment::kQuad);
  521. const float nearestPoint = calculate_nearest_point_for_quad(segment, xformPt);
  522. float dist;
  523. if (between_closed(nearestPoint, segment.fP0T.x(), segment.fP2T.x())) {
  524. DPoint x = DPoint::Make(nearestPoint, nearestPoint * nearestPoint);
  525. dist = (float)xformPt.distanceToSqd(x);
  526. } else {
  527. const float distToB0T = (float)xformPt.distanceToSqd(segment.fP0T);
  528. const float distToB2T = (float)xformPt.distanceToSqd(segment.fP2T);
  529. if (distToB0T < distToB2T) {
  530. dist = distToB0T;
  531. } else {
  532. dist = distToB2T;
  533. }
  534. }
  535. if (between_closed_open(point.y(), segment.fBoundingBox.top(),
  536. segment.fBoundingBox.bottom())) {
  537. *side = calculate_side_of_quad(segment, point, xformPt, rowData);
  538. } else {
  539. *side = kNA_SegSide;
  540. }
  541. return (float)(dist * segment.fScalingFactorSqd);
  542. }
  543. }
  544. static void calculate_distance_field_data(PathSegmentArray* segments,
  545. DFData* dataPtr,
  546. int width, int height) {
  547. int count = segments->count();
  548. for (int a = 0; a < count; ++a) {
  549. PathSegment& segment = (*segments)[a];
  550. const SkRect& segBB = segment.fBoundingBox.makeOutset(
  551. SK_DistanceFieldPad, SK_DistanceFieldPad);
  552. int startColumn = (int)segBB.left();
  553. int endColumn = SkScalarCeilToInt(segBB.right());
  554. int startRow = (int)segBB.top();
  555. int endRow = SkScalarCeilToInt(segBB.bottom());
  556. SkASSERT((startColumn >= 0) && "StartColumn < 0!");
  557. SkASSERT((endColumn <= width) && "endColumn > width!");
  558. SkASSERT((startRow >= 0) && "StartRow < 0!");
  559. SkASSERT((endRow <= height) && "EndRow > height!");
  560. // Clip inside the distance field to avoid overflow
  561. startColumn = SkTMax(startColumn, 0);
  562. endColumn = SkTMin(endColumn, width);
  563. startRow = SkTMax(startRow, 0);
  564. endRow = SkTMin(endRow, height);
  565. for (int row = startRow; row < endRow; ++row) {
  566. SegSide prevSide = kNA_SegSide;
  567. const float pY = row + 0.5f;
  568. RowData rowData;
  569. const SkPoint pointLeft = SkPoint::Make((SkScalar)startColumn, pY);
  570. const SkPoint pointRight = SkPoint::Make((SkScalar)endColumn, pY);
  571. if (between_closed_open(pY, segment.fBoundingBox.top(),
  572. segment.fBoundingBox.bottom())) {
  573. precomputation_for_row(&rowData, segment, pointLeft, pointRight);
  574. }
  575. for (int col = startColumn; col < endColumn; ++col) {
  576. int idx = (row * width) + col;
  577. const float pX = col + 0.5f;
  578. const SkPoint point = SkPoint::Make(pX, pY);
  579. const float distSq = dataPtr[idx].fDistSq;
  580. int dilation = distSq < 1.5 * 1.5 ? 1 :
  581. distSq < 2.5 * 2.5 ? 2 :
  582. distSq < 3.5 * 3.5 ? 3 : SK_DistanceFieldPad;
  583. if (dilation > SK_DistanceFieldPad) {
  584. dilation = SK_DistanceFieldPad;
  585. }
  586. // Optimisation for not calculating some points.
  587. if (dilation != SK_DistanceFieldPad && !segment.fBoundingBox.roundOut()
  588. .makeOutset(dilation, dilation).contains(col, row)) {
  589. continue;
  590. }
  591. SegSide side = kNA_SegSide;
  592. int deltaWindingScore = 0;
  593. float currDistSq = distance_to_segment(point, segment, rowData, &side);
  594. if (prevSide == kLeft_SegSide && side == kRight_SegSide) {
  595. deltaWindingScore = -1;
  596. } else if (prevSide == kRight_SegSide && side == kLeft_SegSide) {
  597. deltaWindingScore = 1;
  598. }
  599. prevSide = side;
  600. if (currDistSq < distSq) {
  601. dataPtr[idx].fDistSq = currDistSq;
  602. }
  603. dataPtr[idx].fDeltaWindingScore += deltaWindingScore;
  604. }
  605. }
  606. }
  607. }
  608. template <int distanceMagnitude>
  609. static unsigned char pack_distance_field_val(float dist) {
  610. // The distance field is constructed as unsigned char values, so that the zero value is at 128,
  611. // Beside 128, we have 128 values in range [0, 128), but only 127 values in range (128, 255].
  612. // So we multiply distanceMagnitude by 127/128 at the latter range to avoid overflow.
  613. dist = SkScalarPin(-dist, -distanceMagnitude, distanceMagnitude * 127.0f / 128.0f);
  614. // Scale into the positive range for unsigned distance.
  615. dist += distanceMagnitude;
  616. // Scale into unsigned char range.
  617. // Round to place negative and positive values as equally as possible around 128
  618. // (which represents zero).
  619. return (unsigned char)SkScalarRoundToInt(dist / (2 * distanceMagnitude) * 256.0f);
  620. }
  621. bool GrGenerateDistanceFieldFromPath(unsigned char* distanceField,
  622. const SkPath& path, const SkMatrix& drawMatrix,
  623. int width, int height, size_t rowBytes) {
  624. SkASSERT(distanceField);
  625. #ifdef SK_DEBUG
  626. SkPath xformPath;
  627. path.transform(drawMatrix, &xformPath);
  628. SkIRect pathBounds = xformPath.getBounds().roundOut();
  629. SkIRect expectPathBounds =
  630. SkIRect::MakeWH(width - 2 * SK_DistanceFieldPad, height - 2 * SK_DistanceFieldPad);
  631. #endif
  632. SkASSERT(expectPathBounds.isEmpty() ||
  633. expectPathBounds.contains(pathBounds.x(), pathBounds.y()));
  634. SkASSERT(expectPathBounds.isEmpty() || pathBounds.isEmpty() ||
  635. expectPathBounds.contains(pathBounds));
  636. SkPath simplifiedPath;
  637. SkPath workingPath;
  638. if (Simplify(path, &simplifiedPath)) {
  639. workingPath = simplifiedPath;
  640. } else {
  641. workingPath = path;
  642. }
  643. if (!IsDistanceFieldSupportedFillType(workingPath.getFillType())) {
  644. return false;
  645. }
  646. workingPath.transform(drawMatrix);
  647. SkDEBUGCODE(pathBounds = workingPath.getBounds().roundOut());
  648. SkASSERT(expectPathBounds.isEmpty() ||
  649. expectPathBounds.contains(pathBounds.x(), pathBounds.y()));
  650. SkASSERT(expectPathBounds.isEmpty() || pathBounds.isEmpty() ||
  651. expectPathBounds.contains(pathBounds));
  652. // translate path to offset (SK_DistanceFieldPad, SK_DistanceFieldPad)
  653. SkMatrix dfMatrix;
  654. dfMatrix.setTranslate(SK_DistanceFieldPad, SK_DistanceFieldPad);
  655. workingPath.transform(dfMatrix);
  656. // create temp data
  657. size_t dataSize = width * height * sizeof(DFData);
  658. SkAutoSMalloc<1024> dfStorage(dataSize);
  659. DFData* dataPtr = (DFData*) dfStorage.get();
  660. // create initial distance data
  661. init_distances(dataPtr, width * height);
  662. SkPath::Iter iter(workingPath, true);
  663. SkSTArray<15, PathSegment, true> segments;
  664. for (;;) {
  665. SkPoint pts[4];
  666. SkPath::Verb verb = iter.next(pts);
  667. switch (verb) {
  668. case SkPath::kMove_Verb:
  669. break;
  670. case SkPath::kLine_Verb: {
  671. add_line_to_segment(pts, &segments);
  672. break;
  673. }
  674. case SkPath::kQuad_Verb:
  675. add_quad_segment(pts, &segments);
  676. break;
  677. case SkPath::kConic_Verb: {
  678. SkScalar weight = iter.conicWeight();
  679. SkAutoConicToQuads converter;
  680. const SkPoint* quadPts = converter.computeQuads(pts, weight, kConicTolerance);
  681. for (int i = 0; i < converter.countQuads(); ++i) {
  682. add_quad_segment(quadPts + 2*i, &segments);
  683. }
  684. break;
  685. }
  686. case SkPath::kCubic_Verb: {
  687. add_cubic_segments(pts, &segments);
  688. break;
  689. }
  690. default:
  691. break;
  692. }
  693. if (verb == SkPath::kDone_Verb) {
  694. break;
  695. }
  696. }
  697. calculate_distance_field_data(&segments, dataPtr, width, height);
  698. for (int row = 0; row < height; ++row) {
  699. int windingNumber = 0; // Winding number start from zero for each scanline
  700. for (int col = 0; col < width; ++col) {
  701. int idx = (row * width) + col;
  702. windingNumber += dataPtr[idx].fDeltaWindingScore;
  703. enum DFSign {
  704. kInside = -1,
  705. kOutside = 1
  706. } dfSign;
  707. if (workingPath.getFillType() == SkPath::kWinding_FillType) {
  708. dfSign = windingNumber ? kInside : kOutside;
  709. } else if (workingPath.getFillType() == SkPath::kInverseWinding_FillType) {
  710. dfSign = windingNumber ? kOutside : kInside;
  711. } else if (workingPath.getFillType() == SkPath::kEvenOdd_FillType) {
  712. dfSign = (windingNumber % 2) ? kInside : kOutside;
  713. } else {
  714. SkASSERT(workingPath.getFillType() == SkPath::kInverseEvenOdd_FillType);
  715. dfSign = (windingNumber % 2) ? kOutside : kInside;
  716. }
  717. // The winding number at the end of a scanline should be zero.
  718. SkASSERT(((col != width - 1) || (windingNumber == 0)) &&
  719. "Winding number should be zero at the end of a scan line.");
  720. // Fallback to use SkPath::contains to determine the sign of pixel in release build.
  721. if (col == width - 1 && windingNumber != 0) {
  722. for (int col = 0; col < width; ++col) {
  723. int idx = (row * width) + col;
  724. dfSign = workingPath.contains(col + 0.5, row + 0.5) ? kInside : kOutside;
  725. const float miniDist = sqrt(dataPtr[idx].fDistSq);
  726. const float dist = dfSign * miniDist;
  727. unsigned char pixelVal = pack_distance_field_val<SK_DistanceFieldMagnitude>(dist);
  728. distanceField[(row * rowBytes) + col] = pixelVal;
  729. }
  730. continue;
  731. }
  732. const float miniDist = sqrt(dataPtr[idx].fDistSq);
  733. const float dist = dfSign * miniDist;
  734. unsigned char pixelVal = pack_distance_field_val<SK_DistanceFieldMagnitude>(dist);
  735. distanceField[(row * rowBytes) + col] = pixelVal;
  736. }
  737. }
  738. return true;
  739. }