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