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 64 static DPoint Make(double x, double y) { 65 DPoint pt; 66 pt.set(x, y); 67 return pt; 68 } 69 70 double x() const { return fX; } 71 double y() const { return fY; } 72 73 void set(double x, double y) { fX = x; fY = y; } 74 75 /** Returns the euclidian distance from (0,0) to (x,y) 76 */ 77 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 */ 83 static double Distance(const DPoint& a, const DPoint& b) { 84 return Length(a.fX - b.fX, a.fY - b.fY); 85 } 86 87 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: 98 double operator[](int index) const { 99 SkASSERT((unsigned)index < 6); 100 return fMat[index]; 101 } 102 103 double& operator[](int index) { 104 SkASSERT((unsigned)index < 6); 105 return fMat[index]; 106 } 107 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 */ 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() 127 void setIdentity() { this->reset(); } 128 129 DPoint mapPoint(const SkPoint& src) const { 130 DPoint pt = DPoint::Make(src.x(), src.y()); 131 return this->mapPoint(pt); 132 } 133 134 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 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 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 187 static inline bool nearly_zero(double x, double tolerance = kNearlyZero) { 188 SkASSERT(tolerance >= 0.0); 189 return fabs(x) <= tolerance; 190 } 191 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 202 static inline double sign_of(const double &val) { 203 return (val < 0.0) ? -1.0 : 1.0; 204 } 205 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 232 int countPoints() { 233 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad); 234 return fType + 2; 235 } 236 237 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 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 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 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 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 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 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 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 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 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 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> 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 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 SkDEBUGCODE(SkPath xformPath;); 746 SkDEBUGCODE(path.transform(drawMatrix, &xformPath)); 747 SkDEBUGCODE(SkIRect pathBounds = xformPath.getBounds().roundOut()); 748 SkDEBUGCODE(SkIRect expectPathBounds = SkIRect::MakeWH(width - 2 * SK_DistanceFieldPad, 749 height - 2 * SK_DistanceFieldPad)); 750 SkASSERT(expectPathBounds.isEmpty() || 751 expectPathBounds.contains(pathBounds.x(), pathBounds.y())); 752 SkASSERT(expectPathBounds.isEmpty() || pathBounds.isEmpty() || 753 expectPathBounds.contains(pathBounds)); 754 755 SkPath simplifiedPath; 756 SkPath workingPath; 757 if (Simplify(path, &simplifiedPath)) { 758 workingPath = simplifiedPath; 759 } else { 760 workingPath = path; 761 } 762 763 if (!IsDistanceFieldSupportedFillType(workingPath.getFillType())) { 764 return false; 765 } 766 767 workingPath.transform(drawMatrix); 768 769 SkDEBUGCODE(pathBounds = workingPath.getBounds().roundOut()); 770 SkASSERT(expectPathBounds.isEmpty() || 771 expectPathBounds.contains(pathBounds.x(), pathBounds.y())); 772 SkASSERT(expectPathBounds.isEmpty() || pathBounds.isEmpty() || 773 expectPathBounds.contains(pathBounds)); 774 775 // translate path to offset (SK_DistanceFieldPad, SK_DistanceFieldPad) 776 SkMatrix dfMatrix; 777 dfMatrix.setTranslate(SK_DistanceFieldPad, SK_DistanceFieldPad); 778 workingPath.transform(dfMatrix); 779 780 // create temp data 781 size_t dataSize = width * height * sizeof(DFData); 782 SkAutoSMalloc<1024> dfStorage(dataSize); 783 DFData* dataPtr = (DFData*) dfStorage.get(); 784 785 // create initial distance data 786 init_distances(dataPtr, width * height); 787 788 SkPath::Iter iter(workingPath, true); 789 SkSTArray<15, PathSegment, true> segments; 790 791 for (;;) { 792 SkPoint pts[4]; 793 SkPath::Verb verb = iter.next(pts); 794 switch (verb) { 795 case SkPath::kMove_Verb: 796 break; 797 case SkPath::kLine_Verb: { 798 add_line_to_segment(pts, &segments); 799 break; 800 } 801 case SkPath::kQuad_Verb: 802 add_quad_segment(pts, &segments); 803 break; 804 case SkPath::kConic_Verb: { 805 SkScalar weight = iter.conicWeight(); 806 SkAutoConicToQuads converter; 807 const SkPoint* quadPts = converter.computeQuads(pts, weight, kConicTolerance); 808 for (int i = 0; i < converter.countQuads(); ++i) { 809 add_quad_segment(quadPts + 2*i, &segments); 810 } 811 break; 812 } 813 case SkPath::kCubic_Verb: { 814 add_cubic_segments(pts, &segments); 815 break; 816 }; 817 default: 818 break; 819 } 820 if (verb == SkPath::kDone_Verb) { 821 break; 822 } 823 } 824 825 calculate_distance_field_data(&segments, dataPtr, width, height); 826 827 for (int row = 0; row < height; ++row) { 828 int windingNumber = 0; // Winding number start from zero for each scanline 829 for (int col = 0; col < width; ++col) { 830 int idx = (row * width) + col; 831 windingNumber += dataPtr[idx].fDeltaWindingScore; 832 833 enum DFSign { 834 kInside = -1, 835 kOutside = 1 836 } dfSign; 837 838 if (workingPath.getFillType() == SkPath::kWinding_FillType) { 839 dfSign = windingNumber ? kInside : kOutside; 840 } else if (workingPath.getFillType() == SkPath::kInverseWinding_FillType) { 841 dfSign = windingNumber ? kOutside : kInside; 842 } else if (workingPath.getFillType() == SkPath::kEvenOdd_FillType) { 843 dfSign = (windingNumber % 2) ? kInside : kOutside; 844 } else { 845 SkASSERT(workingPath.getFillType() == SkPath::kInverseEvenOdd_FillType); 846 dfSign = (windingNumber % 2) ? kOutside : kInside; 847 } 848 849 // The winding number at the end of a scanline should be zero. 850 SkASSERT(((col != width - 1) || (windingNumber == 0)) && 851 "Winding number should be zero at the end of a scan line."); 852 // Fallback to use SkPath::contains to determine the sign of pixel in release build. 853 if (col == width - 1 && windingNumber != 0) { 854 for (int col = 0; col < width; ++col) { 855 int idx = (row * width) + col; 856 dfSign = workingPath.contains(col + 0.5, row + 0.5) ? kInside : kOutside; 857 const float miniDist = sqrt(dataPtr[idx].fDistSq); 858 const float dist = dfSign * miniDist; 859 860 unsigned char pixelVal = pack_distance_field_val<SK_DistanceFieldMagnitude>(dist); 861 862 distanceField[(row * rowBytes) + col] = pixelVal; 863 } 864 continue; 865 } 866 867 const float miniDist = sqrt(dataPtr[idx].fDistSq); 868 const float dist = dfSign * miniDist; 869 870 unsigned char pixelVal = pack_distance_field_val<SK_DistanceFieldMagnitude>(dist); 871 872 distanceField[(row * rowBytes) + col] = pixelVal; 873 } 874 } 875 return true; 876 } 877
