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