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 */ 41enum SegSide { 42 kLeft_SegSide = -1, 43 kOn_SegSide = 0, 44 kRight_SegSide = 1, 45 kNA_SegSide = 2, 46}; 47 48struct 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 60struct DPoint { 61 double fX, fY; 62 63 static DPoint Make(double x, double y) { 64 DPoint pt; 65 pt.set(x, y); 66 return pt; 67 } 68 69 double x() const { return fX; } 70 double y() const { return fY; } 71 72 void set(double x, double y) { fX = x; fY = y; } 73 74 /** Returns the euclidian distance from (0,0) to (x,y) 75 */ 76 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 */ 82 static double Distance(const DPoint& a, const DPoint& b) { 83 return Length(a.fX - b.fX, a.fY - b.fY); 84 } 85 86 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). 95class DAffineMatrix { 96public: 97 double operator[](int index) const { 98 SkASSERT((unsigned)index < 6); 99 return fMat[index]; 100 } 101 102 double& operator[](int index) { 103 SkASSERT((unsigned)index < 6); 104 return fMat[index]; 105 } 106 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 */ 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() 126 void setIdentity() { this->reset(); } 127 128 DPoint mapPoint(const SkPoint& src) const { 129 DPoint pt = DPoint::Make(src.x(), src.y()); 130 return this->mapPoint(pt); 131 } 132 133 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 } 137private: 138 double fMat[6]; 139}; 140 141/////////////////////////////////////////////////////////////////////////////// 142 143static const double kClose = (SK_Scalar1 / 16.0); 144static const double kCloseSqd = kClose * kClose; 145static const double kNearlyZero = (SK_Scalar1 / (1 << 18)); 146static const double kTangentTolerance = (SK_Scalar1 / (1 << 11)); 147static const float kConicTolerance = 0.25f; 148 149static 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 171static 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 186static inline bool nearly_zero(double x, double tolerance = kNearlyZero) { 187 SkASSERT(tolerance >= 0.0); 188 return fabs(x) <= tolerance; 189} 190 191static 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 201static inline double sign_of(const double &val) { 202 return (val < 0.0) ? -1.0 : 1.0; 203} 204 205static 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 210class PathSegment { 211public: 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 231 int countPoints() { 232 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad); 233 return fType + 2; 234 } 235 236 const SkPoint& endPt() const { 237 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad); 238 return fPts[fType + 1]; 239 } 240}; 241 242typedef SkTArray<PathSegment, true> PathSegmentArray; 243 244void 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 350static 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 361static 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 371static 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 393static 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 403static 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. 442struct 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 466void 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 523SegSide 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 585static 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 644static 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 723template <int distanceMagnitude> 724static 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 739bool 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