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