Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(23)

Side by Side Diff: src/gpu/GrDistanceFieldGenFromVector.cpp

Issue 2435753002: Revert of Generate Signed Distance Field directly from vector path (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 4 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(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 << 20));
142
143 static inline bool between_closed_open(double a, double b, double c,
144 double tolerance = 0.0,
145 bool xformToleranceToX = false) {
146 SkASSERT(tolerance >= 0.0);
147 double tolB = tolerance;
148 double tolC = tolerance;
149
150 if (xformToleranceToX) {
151 // Canonical space is y = x^2 and the derivative of x^2 is 2x.
152 // So the slope of the tangent line at point (x, x^2) is 2x.
153 //
154 // /|
155 // sqrt(2x * 2x + 1 * 1) / | 2x
156 // /__|
157 // 1
158 tolB = tolerance / sqrt(4.0 * b * b + 1.0);
159 tolC = tolerance / sqrt(4.0 * c * c + 1.0);
160 }
161 return b < c ? (a >= b - tolB && a < c - tolC) :
162 (a >= c - tolC && a < b - tolB);
163 }
164
165 static inline bool between_closed(double a, double b, double c,
166 double tolerance = 0.0,
167 bool xformToleranceToX = false) {
168 SkASSERT(tolerance >= 0.0);
169 double tolB = tolerance;
170 double tolC = tolerance;
171
172 if (xformToleranceToX) {
173 tolB = tolerance / sqrt(4.0 * b * b + 1.0);
174 tolC = tolerance / sqrt(4.0 * c * c + 1.0);
175 }
176 return b < c ? (a >= b - tolB && a <= c + tolC) :
177 (a >= c - tolC && a <= b + tolB);
178 }
179
180 static inline bool nearly_zero(double x, double tolerance = kNearlyZero) {
181 SkASSERT(tolerance >= 0.0);
182 return fabs(x) <= tolerance;
183 }
184
185 static inline bool nearly_equal(double x, double y,
186 double tolerance = kNearlyZero,
187 bool xformToleranceToX = false) {
188 SkASSERT(tolerance >= 0.0);
189 if (xformToleranceToX) {
190 tolerance = tolerance / sqrt(4.0 * y * y + 1.0);
191 }
192 return fabs(x - y) <= tolerance;
193 }
194
195 static inline double sign_of(const double &val) {
196 return (val < 0.0) ? -1.0 : 1.0;
197 }
198
199 static bool is_colinear(const SkPoint pts[3]) {
200 return nearly_zero((pts[1].y() - pts[0].y()) * (pts[1].x() - pts[2].x()) -
201 (pts[1].y() - pts[2].y()) * (pts[1].x() - pts[0].x()), kC loseSqd);
202 }
203
204 class PathSegment {
205 public:
206 enum {
207 // These enum values are assumed in member functions below.
208 kLine = 0,
209 kQuad = 1,
210 } fType;
211
212 // line uses 2 pts, quad uses 3 pts
213 SkPoint fPts[3];
214
215 DPoint fP0T, fP2T;
216 DAffineMatrix fXformMatrix;
217 double fScalingFactor;
218 double fScalingFactorSqd;
219 double fNearlyZeroScaled;
220 SkRect fBoundingBox;
221
222 void init();
223
224 int countPoints() {
225 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
226 return fType + 2;
227 }
228
229 const SkPoint& endPt() const {
230 GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
231 return fPts[fType + 1];
232 }
233 };
234
235 typedef SkTArray<PathSegment, true> PathSegmentArray;
236
237 void PathSegment::init() {
238 const DPoint p0 = DPoint::Make(fPts[0].x(), fPts[0].y());
239 const DPoint p2 = DPoint::Make(this->endPt().x(), this->endPt().y());
240 const double p0x = p0.x();
241 const double p0y = p0.y();
242 const double p2x = p2.x();
243 const double p2y = p2.y();
244
245 fBoundingBox.set(fPts[0], this->endPt());
246
247 if (fType == PathSegment::kLine) {
248 fScalingFactorSqd = fScalingFactor = 1.0;
249 double hypotenuse = DPoint::Distance(p0, p2);
250
251 const double cosTheta = (p2x - p0x) / hypotenuse;
252 const double sinTheta = (p2y - p0y) / hypotenuse;
253
254 fXformMatrix.setAffine(
255 cosTheta, sinTheta, -(cosTheta * p0x) - (sinTheta * p0y),
256 -sinTheta, cosTheta, (sinTheta * p0x) - (cosTheta * p0y)
257 );
258 } else {
259 SkASSERT(fType == PathSegment::kQuad);
260
261 // Calculate bounding box
262 const SkPoint _P1mP0 = fPts[1] - fPts[0];
263 SkPoint t = _P1mP0 - fPts[2] + fPts[1];
264 t.fX = _P1mP0.x() / t.x();
265 t.fY = _P1mP0.y() / t.y();
266 t.fX = SkScalarClampMax(t.x(), 1.0);
267 t.fY = SkScalarClampMax(t.y(), 1.0);
268 t.fX = _P1mP0.x() * t.x();
269 t.fY = _P1mP0.y() * t.y();
270 const SkPoint m = fPts[0] + t;
271 fBoundingBox.growToInclude(&m, 1);
272
273 const double p1x = fPts[1].x();
274 const double p1y = fPts[1].y();
275
276 const double p0xSqd = p0x * p0x;
277 const double p0ySqd = p0y * p0y;
278 const double p2xSqd = p2x * p2x;
279 const double p2ySqd = p2y * p2y;
280 const double p1xSqd = p1x * p1x;
281 const double p1ySqd = p1y * p1y;
282
283 const double p01xProd = p0x * p1x;
284 const double p02xProd = p0x * p2x;
285 const double b12xProd = p1x * p2x;
286 const double p01yProd = p0y * p1y;
287 const double p02yProd = p0y * p2y;
288 const double b12yProd = p1y * p2y;
289
290 const double sqrtA = p0y - (2.0 * p1y) + p2y;
291 const double a = sqrtA * sqrtA;
292 const double h = -1.0 * (p0y - (2.0 * p1y) + p2y) * (p0x - (2.0 * p1x) + p2x);
293 const double sqrtB = p0x - (2.0 * p1x) + p2x;
294 const double b = sqrtB * sqrtB;
295 const double c = (p0xSqd * p2ySqd) - (4.0 * p01xProd * b12yProd)
296 - (2.0 * p02xProd * p02yProd) + (4.0 * p02xProd * p1ySqd)
297 + (4.0 * p1xSqd * p02yProd) - (4.0 * b12xProd * p01yProd)
298 + (p2xSqd * p0ySqd);
299 const double g = (p0x * p02yProd) - (2.0 * p0x * p1ySqd)
300 + (2.0 * p0x * b12yProd) - (p0x * p2ySqd)
301 + (2.0 * p1x * p01yProd) - (4.0 * p1x * p02yProd)
302 + (2.0 * p1x * b12yProd) - (p2x * p0ySqd)
303 + (2.0 * p2x * p01yProd) + (p2x * p02yProd)
304 - (2.0 * p2x * p1ySqd);
305 const double f = -((p0xSqd * p2y) - (2.0 * p01xProd * p1y)
306 - (2.0 * p01xProd * p2y) - (p02xProd * p0y)
307 + (4.0 * p02xProd * p1y) - (p02xProd * p2y)
308 + (2.0 * p1xSqd * p0y) + (2.0 * p1xSqd * p2y)
309 - (2.0 * b12xProd * p0y) - (2.0 * b12xProd * p1y)
310 + (p2xSqd * p0y));
311
312 const double cosTheta = sqrt(a / (a + b));
313 const double sinTheta = -1.0 * sign_of((a + b) * h) * sqrt(b / (a + b));
314
315 const double gDef = cosTheta * g - sinTheta * f;
316 const double fDef = sinTheta * g + cosTheta * f;
317
318
319 const double x0 = gDef / (a + b);
320 const double y0 = (1.0 / (2.0 * fDef)) * (c - (gDef * gDef / (a + b)));
321
322
323 const double lambda = -1.0 * ((a + b) / (2.0 * fDef));
324 fScalingFactor = fabs(1.0 / lambda);
325 fScalingFactorSqd = fScalingFactor * fScalingFactor;
326
327 const double lambda_cosTheta = lambda * cosTheta;
328 const double lambda_sinTheta = lambda * sinTheta;
329
330 fXformMatrix.setAffine(
331 lambda_cosTheta, -lambda_sinTheta, lambda * x0,
332 lambda_sinTheta, lambda_cosTheta, lambda * y0
333 );
334 }
335
336 fNearlyZeroScaled = kNearlyZero / fScalingFactor;
337
338 fP0T = fXformMatrix.mapPoint(p0);
339 fP2T = fXformMatrix.mapPoint(p2);
340 }
341
342 static void init_distances(DFData* data, int size) {
343 DFData* currData = data;
344
345 for (int i = 0; i < size; ++i) {
346 // init distance to "far away"
347 currData->fDistSq = SK_DistanceFieldMagnitude * SK_DistanceFieldMagnitud e;
348 currData->fDeltaWindingScore = 0;
349 ++currData;
350 }
351 }
352
353 static inline void add_line_to_segment(const SkPoint pts[2],
354 PathSegmentArray* segments) {
355 segments->push_back();
356 segments->back().fType = PathSegment::kLine;
357 segments->back().fPts[0] = pts[0];
358 segments->back().fPts[1] = pts[1];
359
360 segments->back().init();
361 }
362
363 static inline void add_quad_segment(const SkPoint pts[3],
364 PathSegmentArray* segments) {
365 if (pts[0].distanceToSqd(pts[1]) < kCloseSqd ||
366 pts[1].distanceToSqd(pts[2]) < kCloseSqd ||
367 is_colinear(pts)) {
368 if (pts[0] != pts[2]) {
369 SkPoint line_pts[2];
370 line_pts[0] = pts[0];
371 line_pts[1] = pts[2];
372 add_line_to_segment(line_pts, segments);
373 }
374 } else {
375 segments->push_back();
376 segments->back().fType = PathSegment::kQuad;
377 segments->back().fPts[0] = pts[0];
378 segments->back().fPts[1] = pts[1];
379 segments->back().fPts[2] = pts[2];
380
381 segments->back().init();
382 }
383 }
384
385 static inline void add_cubic_segments(const SkPoint pts[4],
386 PathSegmentArray* segments) {
387 SkSTArray<15, SkPoint, true> quads;
388 GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, &quads);
389 int count = quads.count();
390 for (int q = 0; q < count; q += 3) {
391 add_quad_segment(&quads[q], segments);
392 }
393 }
394
395 static float calculate_nearest_point_for_quad(
396 const PathSegment& segment,
397 const DPoint &xFormPt) {
398 static const float kThird = 0.33333333333f;
399 static const float kTwentySeventh = 0.037037037f;
400
401 const float a = 0.5f - (float)xFormPt.y();
402 const float b = -0.5f * (float)xFormPt.x();
403
404 const float a3 = a * a * a;
405 const float b2 = b * b;
406
407 const float c = (b2 * 0.25f) + (a3 * kTwentySeventh);
408
409 if (c >= 0.f) {
410 const float sqrtC = sqrt(c);
411 const float result = (float)cbrt((-b * 0.5f) + sqrtC) + (float)cbrt((-b * 0.5f) - sqrtC);
412 return result;
413 } else {
414 const float cosPhi = (float)sqrt((b2 * 0.25f) * (-27.f / a3)) * ((b > 0) ? -1.f : 1.f);
415 const float phi = (float)acos(cosPhi);
416 float result;
417 if (xFormPt.x() > 0.f) {
418 result = 2.f * (float)sqrt(-a * kThird) * (float)cos(phi * kThird);
419 if (!between_closed(result, segment.fP0T.x(), segment.fP2T.x())) {
420 result = 2.f * (float)sqrt(-a * kThird) * (float)cos((phi * kThi rd) + (SK_ScalarPI * 2.f * kThird));
421 }
422 } else {
423 result = 2.f * (float)sqrt(-a * kThird) * (float)cos((phi * kThird) + (SK_ScalarPI * 2.f * kThird));
424 if (!between_closed(result, segment.fP0T.x(), segment.fP2T.x())) {
425 result = 2.f * (float)sqrt(-a * kThird) * (float)cos(phi * kThir d);
426 }
427 }
428 return result;
429 }
430 }
431
432 // This structure contains some intermediate values shared by the same row.
433 // It is used to calculate segment side of a quadratic bezier.
434 struct RowData {
435 // The intersection type of a scanline and y = x * x parabola in canonical s pace.
436 enum IntersectionType {
437 kNoIntersection,
438 kVerticalLine,
439 kTangentLine,
440 kTwoPointsIntersect
441 } fIntersectionType;
442
443 // The direction of the quadratic segment/scanline in the canonical space.
444 // 1: The quadratic segment/scanline going from negative x-axis to positive x-axis.
445 // 0: The scanline is a vertical line in the canonical space.
446 // -1: The quadratic segment/scanline going from positive x-axis to negative x-axis.
447 int fQuadXDirection;
448 int fScanlineXDirection;
449
450 // The y-value(equal to x*x) of intersection point for the kVerticalLine int ersection type.
451 double fYAtIntersection;
452
453 // The x-value for two intersection points.
454 double fXAtIntersection1;
455 double fXAtIntersection2;
456 };
457
458 void precomputation_for_row(
459 RowData *rowData,
460 const PathSegment& segment,
461 const SkPoint& pointLeft,
462 const SkPoint& pointRight
463 ) {
464 if (segment.fType != PathSegment::kQuad) {
465 return;
466 }
467
468 const DPoint& xFormPtLeft = segment.fXformMatrix.mapPoint(pointLeft);
469 const DPoint& xFormPtRight = segment.fXformMatrix.mapPoint(pointRight);;
470
471 rowData->fQuadXDirection = (int)sign_of(segment.fP2T.x() - segment.fP0T.x()) ;
472 rowData->fScanlineXDirection = (int)sign_of(xFormPtRight.x() - xFormPtLeft.x ());
473
474 const double x1 = xFormPtLeft.x();
475 const double y1 = xFormPtLeft.y();
476 const double x2 = xFormPtRight.x();
477 const double y2 = xFormPtRight.y();
478
479 if (nearly_equal(x1, x2)) {
480 rowData->fIntersectionType = RowData::kVerticalLine;
481 rowData->fYAtIntersection = x1 * x1;
482 rowData->fScanlineXDirection = 0;
483 return;
484 }
485
486 // Line y = mx + b
487 const double m = (y2 - y1) / (x2 - x1);
488 const double b = -m * x1 + y1;
489
490 const double c = m * m + 4.0 * b;
491
492 if (nearly_zero(c, 4.0 * kNearlyZero * kNearlyZero)) {
493 rowData->fIntersectionType = RowData::kTangentLine;
494 rowData->fXAtIntersection1 = m / 2.0;
495 rowData->fXAtIntersection2 = m / 2.0;
496 } else if (c < 0.0) {
497 rowData->fIntersectionType = RowData::kNoIntersection;
498 return;
499 } else {
500 rowData->fIntersectionType = RowData::kTwoPointsIntersect;
501 const double d = sqrt(c);
502 rowData->fXAtIntersection1 = (m + d) / 2.0;
503 rowData->fXAtIntersection2 = (m - d) / 2.0;
504 }
505 }
506
507 SegSide calculate_side_of_quad(
508 const PathSegment& segment,
509 const SkPoint& point,
510 const DPoint& xFormPt,
511 const RowData& rowData) {
512 SegSide side = kNA_SegSide;
513
514 if (RowData::kVerticalLine == rowData.fIntersectionType) {
515 side = (SegSide)(int)(sign_of(rowData.fYAtIntersection - xFormPt.y()) * rowData.fQuadXDirection);
516 }
517 else if (RowData::kTwoPointsIntersect == rowData.fIntersectionType) {
518 const double p1 = rowData.fXAtIntersection1;
519 const double p2 = rowData.fXAtIntersection2;
520
521 int signP1 = (int)sign_of(p1 - xFormPt.x());
522 bool includeP1 = true;
523 bool includeP2 = true;
524
525 if ((nearly_equal(p1, segment.fP0T.x(), segment.fNearlyZeroScaled, true) &&
526 rowData.fQuadXDirection * rowData.fScanlineXDirection == -1) ||
527 (nearly_equal(p1, segment.fP2T.x(), segment.fNearlyZeroScaled, true) &&
528 rowData.fQuadXDirection * rowData.fScanlineXDirection == 1)) {
529 includeP1 = false;
530 }
531 if ((nearly_equal(p2, segment.fP0T.x(), segment.fNearlyZeroScaled, true) &&
532 rowData.fQuadXDirection * rowData.fScanlineXDirection == 1) ||
533 (nearly_equal(p2, segment.fP2T.x(), segment.fNearlyZeroScaled, true) &&
534 rowData.fQuadXDirection * rowData.fScanlineXDirection == -1)) {
535 includeP2 = false;
536 }
537
538 if (includeP1 && between_closed(p1, segment.fP0T.x(), segment.fP2T.x(),
539 segment.fNearlyZeroScaled, true)) {
540 side = (SegSide)((-signP1) * rowData.fQuadXDirection);
541 }
542 if (includeP2 && between_closed(p2, segment.fP0T.x(), segment.fP2T.x(),
543 segment.fNearlyZeroScaled, true)) {
544 int signP2 = (int)sign_of(p2 - xFormPt.x());
545 if (side == kNA_SegSide || signP2 == 1) {
546 side = (SegSide)(signP2 * rowData.fQuadXDirection);
547 }
548 }
549 } else if (RowData::kTangentLine == rowData.fIntersectionType) {
550 // The scanline is the tangent line of current quadratic segment.
551
552 const double p = rowData.fXAtIntersection1;
553 int signP = (int)sign_of(p - xFormPt.x());
554 if (rowData.fScanlineXDirection == 1 &&
555 // The path start or end at the tangent point.
556 (nearly_equal(p, segment.fP0T.x(), segment.fNearlyZeroScaled, true) ||
557 nearly_equal(p, segment.fP2T.x(), segment.fNearlyZeroScaled, true)) ) {
558 side = (SegSide)(signP * rowData.fQuadXDirection);
559 }
560 }
561
562 return side;
563 }
564
565 static float distance_to_segment(const SkPoint& point,
566 const PathSegment& segment,
567 const RowData& rowData,
568 SegSide* side) {
569 SkASSERT(side);
570
571 const DPoint xformPt = segment.fXformMatrix.mapPoint(point);
572
573 if (segment.fType == PathSegment::kLine) {
574 float result = SK_DistanceFieldPad * SK_DistanceFieldPad;
575
576 if (between_closed(xformPt.x(), segment.fP0T.x(), segment.fP2T.x())) {
577 result = (float)(xformPt.y() * xformPt.y());
578 } else if (xformPt.x() < segment.fP0T.x()) {
579 result = (float)(xformPt.x() * xformPt.x() + xformPt.y() * xformPt.y ());
580 } else {
581 result = (float)((xformPt.x() - segment.fP2T.x()) * (xformPt.x() - s egment.fP2T.x())
582 + xformPt.y() * xformPt.y());
583 }
584
585 if (between_closed_open(point.y(), segment.fBoundingBox.top(),
586 segment.fBoundingBox.bottom())) {
587 *side = (SegSide)(int)sign_of(-xformPt.y());
588 } else {
589 *side = kNA_SegSide;
590 }
591 return result;
592 } else {
593 SkASSERT(segment.fType == PathSegment::kQuad);
594
595 const float nearestPoint = calculate_nearest_point_for_quad(segment, xfo rmPt);
596
597 float dist;
598
599 if (between_closed(nearestPoint, segment.fP0T.x(), segment.fP2T.x())) {
600 DPoint x = DPoint::Make(nearestPoint, nearestPoint * nearestPoint);
601 dist = (float)xformPt.distanceToSqd(x);
602 } else {
603 const float distToB0T = (float)xformPt.distanceToSqd(segment.fP0T);
604 const float distToB2T = (float)xformPt.distanceToSqd(segment.fP2T);
605
606 if (distToB0T < distToB2T) {
607 dist = distToB0T;
608 } else {
609 dist = distToB2T;
610 }
611 }
612
613 if (between_closed_open(point.y(), segment.fBoundingBox.top(),
614 segment.fBoundingBox.bottom())) {
615 *side = calculate_side_of_quad(segment, point, xformPt, rowData);
616 } else {
617 *side = kNA_SegSide;
618 }
619
620 return (float)(dist * segment.fScalingFactorSqd);
621 }
622 }
623
624 static void calculate_distance_field_data(PathSegmentArray* segments,
625 DFData* dataPtr,
626 int width, int height) {
627 int count = segments->count();
628 for (int a = 0; a < count; ++a) {
629 PathSegment& segment = (*segments)[a];
630 const SkRect& segBB = segment.fBoundingBox.makeOutset(
631 SK_DistanceFieldPad, SK_DistanceFieldPad);
632 int startColumn = (int)segBB.left();
633 int endColumn = SkScalarCeilToInt(segBB.right());
634
635 int startRow = (int)segBB.top();
636 int endRow = SkScalarCeilToInt(segBB.bottom());
637
638 SkASSERT((startColumn >= 0) && "StartColumn < 0!");
639 SkASSERT((endColumn <= width) && "endColumn > width!");
640 SkASSERT((startRow >= 0) && "StartRow < 0!");
641 SkASSERT((endRow <= height) && "EndRow > height!");
642
643 for (int row = startRow; row < endRow; ++row) {
644 SegSide prevSide = kNA_SegSide;
645 const float pY = row + 0.5f;
646 RowData rowData;
647
648 const SkPoint pointLeft = SkPoint::Make((SkScalar)startColumn, pY);
649 const SkPoint pointRight = SkPoint::Make((SkScalar)endColumn, pY);
650
651 precomputation_for_row(&rowData, segment, pointLeft, pointRight);
652
653 for (int col = startColumn; col < endColumn; ++col) {
654 int idx = (row * width) + col;
655
656 const float pX = col + 0.5f;
657 const SkPoint point = SkPoint::Make(pX, pY);
658
659 const float distSq = dataPtr[idx].fDistSq;
660 int dilation = distSq < 1.5 * 1.5 ? 1 :
661 distSq < 2.5 * 2.5 ? 2 :
662 distSq < 3.5 * 3.5 ? 3 : SK_DistanceFieldPad;
663 if (dilation > SK_DistanceFieldPad) {
664 dilation = SK_DistanceFieldPad;
665 }
666
667 // Optimisation for not calculating some points.
668 if (dilation != SK_DistanceFieldPad && !segment.fBoundingBox.rou ndOut()
669 .makeOutset(dilation, dilation).contains(col, row)) {
670 continue;
671 }
672
673 SegSide side = kNA_SegSide;
674 int deltaWindingScore = 0;
675 float currDistSq = distance_to_segment(point, segment, rowData , &side);
676 if (prevSide == kLeft_SegSide && side == kRight_SegSide) {
677 deltaWindingScore = -1;
678 } else if (prevSide == kRight_SegSide && side == kLeft_SegSide) {
679 deltaWindingScore = 1;
680 }
681
682 prevSide = side;
683
684 if (currDistSq < distSq) {
685 dataPtr[idx].fDistSq = currDistSq;
686 }
687
688 dataPtr[idx].fDeltaWindingScore += deltaWindingScore;
689 }
690 }
691 }
692 }
693
694 template <int distanceMagnitude>
695 static unsigned char pack_distance_field_val(float dist) {
696 // The distance field is constructed as unsigned char values, so that the ze ro value is at 128,
697 // Beside 128, we have 128 values in range [0, 128), but only 127 values in range (128, 255].
698 // So we multiply distanceMagnitude by 127/128 at the latter range to avoid overflow.
699 dist = SkScalarPin(-dist, -distanceMagnitude, distanceMagnitude * 127.0f / 1 28.0f);
700
701 // Scale into the positive range for unsigned distance.
702 dist += distanceMagnitude;
703
704 // Scale into unsigned char range.
705 // Round to place negative and positive values as equally as possible around 128
706 // (which represents zero).
707 return (unsigned char)SkScalarRoundToInt(dist / (2 * distanceMagnitude) * 25 6.0f);
708 }
709
710 bool GrGenerateDistanceFieldFromPath(unsigned char* distanceField,
711 const SkPath& path, const SkMatrix& drawMat rix,
712 int width, int height, size_t rowBytes) {
713 SkASSERT(distanceField);
714
715 SkPath simplifiedPath;
716 const SkPath* workingPath;
717 if (Simplify(path, &simplifiedPath)) {
718 workingPath = &simplifiedPath;
719 } else {
720 workingPath = &path;
721 }
722
723 if (!IsDistanceFieldSupportedFillType(workingPath->getFillType())) {
724 return false;
725 }
726
727 SkMatrix m = drawMatrix;
728 m.postTranslate(SK_DistanceFieldPad, SK_DistanceFieldPad);
729
730 // create temp data
731 size_t dataSize = width * height * sizeof(DFData);
732 SkAutoSMalloc<1024> dfStorage(dataSize);
733 DFData* dataPtr = (DFData*) dfStorage.get();
734
735 // create initial distance data
736 init_distances(dataPtr, width * height);
737
738 SkPath::Iter iter(simplifiedPath, true);
739 SkSTArray<15, PathSegment, true> segments;
740
741 for (;;) {
742 SkPoint pts[4];
743 SkPath::Verb verb = iter.next(pts);
744 switch (verb) {
745 case SkPath::kMove_Verb:
746 // m.mapPoints(pts, 1);
747 break;
748 case SkPath::kLine_Verb: {
749 m.mapPoints(pts, 2);
750 add_line_to_segment(pts, &segments);
751 break;
752 }
753 case SkPath::kQuad_Verb:
754 m.mapPoints(pts, 3);
755 add_quad_segment(pts, &segments);
756 break;
757 case SkPath::kConic_Verb: {
758 m.mapPoints(pts, 3);
759 SkScalar weight = iter.conicWeight();
760 SkAutoConicToQuads converter;
761 const SkPoint* quadPts = converter.computeQuads(pts, weight, 0.5 f);
762 for (int i = 0; i < converter.countQuads(); ++i) {
763 add_quad_segment(quadPts + 2*i, &segments);
764 }
765 break;
766 }
767 case SkPath::kCubic_Verb: {
768 m.mapPoints(pts, 4);
769 add_cubic_segments(pts, &segments);
770 break;
771 };
772 default:
773 break;
774 }
775 if (verb == SkPath::kDone_Verb) {
776 break;
777 }
778 }
779
780 calculate_distance_field_data(&segments, dataPtr, width, height);
781
782 for (int row = 0; row < height; ++row) {
783 int windingNumber = 0; // Winding number start from zero for each scanli ne
784 for (int col = 0; col < width; ++col) {
785 int idx = (row * width) + col;
786 windingNumber += dataPtr[idx].fDeltaWindingScore;
787
788 enum DFSign {
789 kInside = -1,
790 kOutside = 1
791 } dfSign;
792
793 if (workingPath->getFillType() == SkPath::kWinding_FillType) {
794 dfSign = windingNumber ? kInside : kOutside;
795 } else if (workingPath->getFillType() == SkPath::kInverseWinding_Fil lType) {
796 dfSign = windingNumber ? kOutside : kInside;
797 } else if (workingPath->getFillType() == SkPath::kEvenOdd_FillType) {
798 dfSign = (windingNumber % 2) ? kInside : kOutside;
799 } else {
800 SkASSERT(workingPath->getFillType() == SkPath::kInverseEvenOdd_F illType);
801 dfSign = (windingNumber % 2) ? kOutside : kInside;
802 }
803
804 // The winding number at the end of a scanline should be zero.
805 SkASSERT(((col != width - 1) || (windingNumber == 0)) &&
806 "Winding number should be zero at the end of a scan line.");
807
808 const float miniDist = sqrt(dataPtr[idx].fDistSq);
809 const float dist = dfSign * miniDist;
810
811 unsigned char pixelVal = pack_distance_field_val<SK_DistanceFieldMag nitude>(dist);
812
813 distanceField[(row * rowBytes) + col] = pixelVal;
814 }
815 }
816 return true;
817 }
OLDNEW
« no previous file with comments | « src/gpu/GrDistanceFieldGenFromVector.h ('k') | src/gpu/batches/GrAADistanceFieldPathRenderer.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698