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