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