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