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