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