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