Line data Source code
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 : */
41 : enum SegSide {
42 : kLeft_SegSide = -1,
43 : kOn_SegSide = 0,
44 : kRight_SegSide = 1,
45 : kNA_SegSide = 2,
46 : };
47 :
48 : struct 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
60 : struct DPoint {
61 : double fX, fY;
62 :
63 0 : static DPoint Make(double x, double y) {
64 : DPoint pt;
65 0 : pt.set(x, y);
66 0 : return pt;
67 : }
68 :
69 0 : double x() const { return fX; }
70 0 : double y() const { return fY; }
71 :
72 0 : void set(double x, double y) { fX = x; fY = y; }
73 :
74 : /** Returns the euclidian distance from (0,0) to (x,y)
75 : */
76 0 : static double Length(double x, double y) {
77 0 : return sqrt(x * x + y * y);
78 : }
79 :
80 : /** Returns the euclidian distance between a and b
81 : */
82 0 : static double Distance(const DPoint& a, const DPoint& b) {
83 0 : return Length(a.fX - b.fX, a.fY - b.fY);
84 : }
85 :
86 0 : double distanceToSqd(const DPoint& pt) const {
87 0 : double dx = fX - pt.fX;
88 0 : double dy = fY - pt.fY;
89 0 : 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).
95 : class DAffineMatrix {
96 : public:
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 0 : void setAffine(double m11, double m12, double m13,
108 : double m21, double m22, double m23) {
109 0 : fMat[0] = m11;
110 0 : fMat[1] = m12;
111 0 : fMat[2] = m13;
112 0 : fMat[3] = m21;
113 0 : fMat[4] = m22;
114 0 : fMat[5] = m23;
115 0 : }
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 0 : DPoint mapPoint(const SkPoint& src) const {
129 0 : DPoint pt = DPoint::Make(src.x(), src.y());
130 0 : return this->mapPoint(pt);
131 : }
132 :
133 0 : DPoint mapPoint(const DPoint& src) const {
134 0 : return DPoint::Make(fMat[0] * src.x() + fMat[1] * src.y() + fMat[2],
135 0 : fMat[3] * src.x() + fMat[4] * src.y() + fMat[5]);
136 : }
137 : private:
138 : double fMat[6];
139 : };
140 :
141 : ///////////////////////////////////////////////////////////////////////////////
142 :
143 : static const double kClose = (SK_Scalar1 / 16.0);
144 : static const double kCloseSqd = kClose * kClose;
145 : static const double kNearlyZero = (SK_Scalar1 / (1 << 18));
146 : static const double kTangentTolerance = (SK_Scalar1 / (1 << 11));
147 : static const float kConicTolerance = 0.25f;
148 :
149 0 : static inline bool between_closed_open(double a, double b, double c,
150 : double tolerance = 0.0,
151 : bool xformToleranceToX = false) {
152 0 : SkASSERT(tolerance >= 0.0);
153 0 : double tolB = tolerance;
154 0 : double tolC = tolerance;
155 :
156 0 : 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 0 : tolB = tolerance / sqrt(4.0 * b * b + 1.0);
165 0 : tolC = tolerance / sqrt(4.0 * c * c + 1.0);
166 : }
167 0 : return b < c ? (a >= b - tolB && a < c - tolC) :
168 0 : (a >= c - tolC && a < b - tolB);
169 : }
170 :
171 0 : static inline bool between_closed(double a, double b, double c,
172 : double tolerance = 0.0,
173 : bool xformToleranceToX = false) {
174 0 : SkASSERT(tolerance >= 0.0);
175 0 : double tolB = tolerance;
176 0 : double tolC = tolerance;
177 :
178 0 : if (xformToleranceToX) {
179 0 : tolB = tolerance / sqrt(4.0 * b * b + 1.0);
180 0 : tolC = tolerance / sqrt(4.0 * c * c + 1.0);
181 : }
182 0 : return b < c ? (a >= b - tolB && a <= c + tolC) :
183 0 : (a >= c - tolC && a <= b + tolB);
184 : }
185 :
186 0 : static inline bool nearly_zero(double x, double tolerance = kNearlyZero) {
187 0 : SkASSERT(tolerance >= 0.0);
188 0 : return fabs(x) <= tolerance;
189 : }
190 :
191 0 : static inline bool nearly_equal(double x, double y,
192 : double tolerance = kNearlyZero,
193 : bool xformToleranceToX = false) {
194 0 : SkASSERT(tolerance >= 0.0);
195 0 : if (xformToleranceToX) {
196 0 : tolerance = tolerance / sqrt(4.0 * y * y + 1.0);
197 : }
198 0 : return fabs(x - y) <= tolerance;
199 : }
200 :
201 0 : static inline double sign_of(const double &val) {
202 0 : return (val < 0.0) ? -1.0 : 1.0;
203 : }
204 :
205 0 : static bool is_colinear(const SkPoint pts[3]) {
206 0 : return nearly_zero((pts[1].y() - pts[0].y()) * (pts[1].x() - pts[2].x()) -
207 0 : (pts[1].y() - pts[2].y()) * (pts[1].x() - pts[0].x()), kCloseSqd);
208 : }
209 :
210 : class PathSegment {
211 : public:
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 0 : const SkPoint& endPt() const {
237 : GR_STATIC_ASSERT(0 == kLine && 1 == kQuad);
238 0 : return fPts[fType + 1];
239 : }
240 : };
241 :
242 : typedef SkTArray<PathSegment, true> PathSegmentArray;
243 :
244 0 : void PathSegment::init() {
245 0 : const DPoint p0 = DPoint::Make(fPts[0].x(), fPts[0].y());
246 0 : const DPoint p2 = DPoint::Make(this->endPt().x(), this->endPt().y());
247 0 : const double p0x = p0.x();
248 0 : const double p0y = p0.y();
249 0 : const double p2x = p2.x();
250 0 : const double p2y = p2.y();
251 :
252 0 : fBoundingBox.set(fPts[0], this->endPt());
253 :
254 0 : if (fType == PathSegment::kLine) {
255 0 : fScalingFactorSqd = fScalingFactor = 1.0;
256 0 : double hypotenuse = DPoint::Distance(p0, p2);
257 :
258 0 : const double cosTheta = (p2x - p0x) / hypotenuse;
259 0 : const double sinTheta = (p2y - p0y) / hypotenuse;
260 :
261 0 : fXformMatrix.setAffine(
262 0 : cosTheta, sinTheta, -(cosTheta * p0x) - (sinTheta * p0y),
263 0 : -sinTheta, cosTheta, (sinTheta * p0x) - (cosTheta * p0y)
264 0 : );
265 : } else {
266 0 : SkASSERT(fType == PathSegment::kQuad);
267 :
268 : // Calculate bounding box
269 0 : const SkPoint _P1mP0 = fPts[1] - fPts[0];
270 0 : SkPoint t = _P1mP0 - fPts[2] + fPts[1];
271 0 : t.fX = _P1mP0.x() / t.x();
272 0 : t.fY = _P1mP0.y() / t.y();
273 0 : t.fX = SkScalarClampMax(t.x(), 1.0);
274 0 : t.fY = SkScalarClampMax(t.y(), 1.0);
275 0 : t.fX = _P1mP0.x() * t.x();
276 0 : t.fY = _P1mP0.y() * t.y();
277 0 : const SkPoint m = fPts[0] + t;
278 0 : fBoundingBox.growToInclude(&m, 1);
279 :
280 0 : const double p1x = fPts[1].x();
281 0 : const double p1y = fPts[1].y();
282 :
283 0 : const double p0xSqd = p0x * p0x;
284 0 : const double p0ySqd = p0y * p0y;
285 0 : const double p2xSqd = p2x * p2x;
286 0 : const double p2ySqd = p2y * p2y;
287 0 : const double p1xSqd = p1x * p1x;
288 0 : const double p1ySqd = p1y * p1y;
289 :
290 0 : const double p01xProd = p0x * p1x;
291 0 : const double p02xProd = p0x * p2x;
292 0 : const double b12xProd = p1x * p2x;
293 0 : const double p01yProd = p0y * p1y;
294 0 : const double p02yProd = p0y * p2y;
295 0 : const double b12yProd = p1y * p2y;
296 :
297 0 : const double sqrtA = p0y - (2.0 * p1y) + p2y;
298 0 : const double a = sqrtA * sqrtA;
299 0 : const double h = -1.0 * (p0y - (2.0 * p1y) + p2y) * (p0x - (2.0 * p1x) + p2x);
300 0 : const double sqrtB = p0x - (2.0 * p1x) + p2x;
301 0 : const double b = sqrtB * sqrtB;
302 0 : const double c = (p0xSqd * p2ySqd) - (4.0 * p01xProd * b12yProd)
303 0 : - (2.0 * p02xProd * p02yProd) + (4.0 * p02xProd * p1ySqd)
304 0 : + (4.0 * p1xSqd * p02yProd) - (4.0 * b12xProd * p01yProd)
305 0 : + (p2xSqd * p0ySqd);
306 0 : const double g = (p0x * p02yProd) - (2.0 * p0x * p1ySqd)
307 0 : + (2.0 * p0x * b12yProd) - (p0x * p2ySqd)
308 0 : + (2.0 * p1x * p01yProd) - (4.0 * p1x * p02yProd)
309 0 : + (2.0 * p1x * b12yProd) - (p2x * p0ySqd)
310 0 : + (2.0 * p2x * p01yProd) + (p2x * p02yProd)
311 0 : - (2.0 * p2x * p1ySqd);
312 0 : const double f = -((p0xSqd * p2y) - (2.0 * p01xProd * p1y)
313 0 : - (2.0 * p01xProd * p2y) - (p02xProd * p0y)
314 0 : + (4.0 * p02xProd * p1y) - (p02xProd * p2y)
315 0 : + (2.0 * p1xSqd * p0y) + (2.0 * p1xSqd * p2y)
316 0 : - (2.0 * b12xProd * p0y) - (2.0 * b12xProd * p1y)
317 0 : + (p2xSqd * p0y));
318 :
319 0 : const double cosTheta = sqrt(a / (a + b));
320 0 : const double sinTheta = -1.0 * sign_of((a + b) * h) * sqrt(b / (a + b));
321 :
322 0 : const double gDef = cosTheta * g - sinTheta * f;
323 0 : const double fDef = sinTheta * g + cosTheta * f;
324 :
325 :
326 0 : const double x0 = gDef / (a + b);
327 0 : const double y0 = (1.0 / (2.0 * fDef)) * (c - (gDef * gDef / (a + b)));
328 :
329 :
330 0 : const double lambda = -1.0 * ((a + b) / (2.0 * fDef));
331 0 : fScalingFactor = fabs(1.0 / lambda);
332 0 : fScalingFactorSqd = fScalingFactor * fScalingFactor;
333 :
334 0 : const double lambda_cosTheta = lambda * cosTheta;
335 0 : const double lambda_sinTheta = lambda * sinTheta;
336 :
337 0 : fXformMatrix.setAffine(
338 : lambda_cosTheta, -lambda_sinTheta, lambda * x0,
339 : lambda_sinTheta, lambda_cosTheta, lambda * y0
340 0 : );
341 : }
342 :
343 0 : fNearlyZeroScaled = kNearlyZero / fScalingFactor;
344 0 : fTangentTolScaledSqd = kTangentTolerance * kTangentTolerance / fScalingFactorSqd;
345 :
346 0 : fP0T = fXformMatrix.mapPoint(p0);
347 0 : fP2T = fXformMatrix.mapPoint(p2);
348 0 : }
349 :
350 0 : static void init_distances(DFData* data, int size) {
351 0 : DFData* currData = data;
352 :
353 0 : for (int i = 0; i < size; ++i) {
354 : // init distance to "far away"
355 0 : currData->fDistSq = SK_DistanceFieldMagnitude * SK_DistanceFieldMagnitude;
356 0 : currData->fDeltaWindingScore = 0;
357 0 : ++currData;
358 : }
359 0 : }
360 :
361 0 : static inline void add_line_to_segment(const SkPoint pts[2],
362 : PathSegmentArray* segments) {
363 0 : segments->push_back();
364 0 : segments->back().fType = PathSegment::kLine;
365 0 : segments->back().fPts[0] = pts[0];
366 0 : segments->back().fPts[1] = pts[1];
367 :
368 0 : segments->back().init();
369 0 : }
370 :
371 0 : static inline void add_quad_segment(const SkPoint pts[3],
372 : PathSegmentArray* segments) {
373 0 : if (pts[0].distanceToSqd(pts[1]) < kCloseSqd ||
374 0 : pts[1].distanceToSqd(pts[2]) < kCloseSqd ||
375 0 : is_colinear(pts)) {
376 0 : if (pts[0] != pts[2]) {
377 : SkPoint line_pts[2];
378 0 : line_pts[0] = pts[0];
379 0 : line_pts[1] = pts[2];
380 0 : add_line_to_segment(line_pts, segments);
381 : }
382 : } else {
383 0 : segments->push_back();
384 0 : segments->back().fType = PathSegment::kQuad;
385 0 : segments->back().fPts[0] = pts[0];
386 0 : segments->back().fPts[1] = pts[1];
387 0 : segments->back().fPts[2] = pts[2];
388 :
389 0 : segments->back().init();
390 : }
391 0 : }
392 :
393 0 : static inline void add_cubic_segments(const SkPoint pts[4],
394 : PathSegmentArray* segments) {
395 0 : SkSTArray<15, SkPoint, true> quads;
396 0 : GrPathUtils::convertCubicToQuads(pts, SK_Scalar1, &quads);
397 0 : int count = quads.count();
398 0 : for (int q = 0; q < count; q += 3) {
399 0 : add_quad_segment(&quads[q], segments);
400 : }
401 0 : }
402 :
403 0 : static 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 0 : const float a = 0.5f - (float)xFormPt.y();
410 0 : const float b = -0.5f * (float)xFormPt.x();
411 :
412 0 : const float a3 = a * a * a;
413 0 : const float b2 = b * b;
414 :
415 0 : const float c = (b2 * 0.25f) + (a3 * kTwentySeventh);
416 :
417 0 : if (c >= 0.f) {
418 0 : const float sqrtC = sqrt(c);
419 0 : const float result = (float)cbrt((-b * 0.5f) + sqrtC) + (float)cbrt((-b * 0.5f) - sqrtC);
420 0 : return result;
421 : } else {
422 0 : const float cosPhi = (float)sqrt((b2 * 0.25f) * (-27.f / a3)) * ((b > 0) ? -1.f : 1.f);
423 0 : const float phi = (float)acos(cosPhi);
424 : float result;
425 0 : if (xFormPt.x() > 0.f) {
426 0 : result = 2.f * (float)sqrt(-a * kThird) * (float)cos(phi * kThird);
427 0 : if (!between_closed(result, segment.fP0T.x(), segment.fP2T.x())) {
428 0 : result = 2.f * (float)sqrt(-a * kThird) * (float)cos((phi * kThird) + (SK_ScalarPI * 2.f * kThird));
429 : }
430 : } else {
431 0 : result = 2.f * (float)sqrt(-a * kThird) * (float)cos((phi * kThird) + (SK_ScalarPI * 2.f * kThird));
432 0 : if (!between_closed(result, segment.fP0T.x(), segment.fP2T.x())) {
433 0 : result = 2.f * (float)sqrt(-a * kThird) * (float)cos(phi * kThird);
434 : }
435 : }
436 0 : 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.
442 : struct 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 :
466 0 : void precomputation_for_row(
467 : RowData *rowData,
468 : const PathSegment& segment,
469 : const SkPoint& pointLeft,
470 : const SkPoint& pointRight
471 : ) {
472 0 : if (segment.fType != PathSegment::kQuad) {
473 0 : return;
474 : }
475 :
476 0 : const DPoint& xFormPtLeft = segment.fXformMatrix.mapPoint(pointLeft);
477 0 : const DPoint& xFormPtRight = segment.fXformMatrix.mapPoint(pointRight);;
478 :
479 0 : rowData->fQuadXDirection = (int)sign_of(segment.fP2T.x() - segment.fP0T.x());
480 0 : rowData->fScanlineXDirection = (int)sign_of(xFormPtRight.x() - xFormPtLeft.x());
481 :
482 0 : const double x1 = xFormPtLeft.x();
483 0 : const double y1 = xFormPtLeft.y();
484 0 : const double x2 = xFormPtRight.x();
485 0 : const double y2 = xFormPtRight.y();
486 :
487 0 : if (nearly_equal(x1, x2, segment.fNearlyZeroScaled, true)) {
488 0 : rowData->fIntersectionType = RowData::kVerticalLine;
489 0 : rowData->fYAtIntersection = x1 * x1;
490 0 : rowData->fScanlineXDirection = 0;
491 0 : return;
492 : }
493 :
494 : // Line y = mx + b
495 0 : const double m = (y2 - y1) / (x2 - x1);
496 0 : const double b = -m * x1 + y1;
497 :
498 0 : const double m2 = m * m;
499 0 : const double c = m2 + 4.0 * b;
500 :
501 0 : 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 0 : if ((rowData->fScanlineXDirection == 1 &&
506 0 : (segment.fPts[0].y() == pointLeft.y() ||
507 0 : segment.fPts[2].y() == pointLeft.y())) &&
508 0 : nearly_zero(c, tol)) {
509 0 : rowData->fIntersectionType = RowData::kTangentLine;
510 0 : rowData->fXAtIntersection1 = m / 2.0;
511 0 : rowData->fXAtIntersection2 = m / 2.0;
512 0 : } else if (c <= 0.0) {
513 0 : rowData->fIntersectionType = RowData::kNoIntersection;
514 0 : return;
515 : } else {
516 0 : rowData->fIntersectionType = RowData::kTwoPointsIntersect;
517 0 : const double d = sqrt(c);
518 0 : rowData->fXAtIntersection1 = (m + d) / 2.0;
519 0 : rowData->fXAtIntersection2 = (m - d) / 2.0;
520 : }
521 : }
522 :
523 0 : SegSide calculate_side_of_quad(
524 : const PathSegment& segment,
525 : const SkPoint& point,
526 : const DPoint& xFormPt,
527 : const RowData& rowData) {
528 0 : SegSide side = kNA_SegSide;
529 :
530 0 : if (RowData::kVerticalLine == rowData.fIntersectionType) {
531 0 : side = (SegSide)(int)(sign_of(xFormPt.y() - rowData.fYAtIntersection) * rowData.fQuadXDirection);
532 : }
533 0 : else if (RowData::kTwoPointsIntersect == rowData.fIntersectionType) {
534 0 : const double p1 = rowData.fXAtIntersection1;
535 0 : const double p2 = rowData.fXAtIntersection2;
536 :
537 0 : int signP1 = (int)sign_of(p1 - xFormPt.x());
538 0 : bool includeP1 = true;
539 0 : bool includeP2 = true;
540 :
541 0 : if (rowData.fScanlineXDirection == 1) {
542 0 : if ((rowData.fQuadXDirection == -1 && segment.fPts[0].y() <= point.y() &&
543 0 : nearly_equal(segment.fP0T.x(), p1, segment.fNearlyZeroScaled, true)) ||
544 0 : (rowData.fQuadXDirection == 1 && segment.fPts[2].y() <= point.y() &&
545 0 : nearly_equal(segment.fP2T.x(), p1, segment.fNearlyZeroScaled, true))) {
546 0 : includeP1 = false;
547 : }
548 0 : if ((rowData.fQuadXDirection == -1 && segment.fPts[2].y() <= point.y() &&
549 0 : nearly_equal(segment.fP2T.x(), p2, segment.fNearlyZeroScaled, true)) ||
550 0 : (rowData.fQuadXDirection == 1 && segment.fPts[0].y() <= point.y() &&
551 0 : nearly_equal(segment.fP0T.x(), p2, segment.fNearlyZeroScaled, true))) {
552 0 : includeP2 = false;
553 : }
554 : }
555 :
556 0 : if (includeP1 && between_closed(p1, segment.fP0T.x(), segment.fP2T.x(),
557 0 : segment.fNearlyZeroScaled, true)) {
558 0 : side = (SegSide)(signP1 * rowData.fQuadXDirection);
559 : }
560 0 : if (includeP2 && between_closed(p2, segment.fP0T.x(), segment.fP2T.x(),
561 0 : segment.fNearlyZeroScaled, true)) {
562 0 : int signP2 = (int)sign_of(p2 - xFormPt.x());
563 0 : if (side == kNA_SegSide || signP2 == 1) {
564 0 : side = (SegSide)(-signP2 * rowData.fQuadXDirection);
565 : }
566 : }
567 0 : } else if (RowData::kTangentLine == rowData.fIntersectionType) {
568 : // The scanline is the tangent line of current quadratic segment.
569 :
570 0 : const double p = rowData.fXAtIntersection1;
571 0 : int signP = (int)sign_of(p - xFormPt.x());
572 0 : if (rowData.fScanlineXDirection == 1) {
573 : // The path start or end at the tangent point.
574 0 : if (segment.fPts[0].y() == point.y()) {
575 0 : side = (SegSide)(signP);
576 0 : } else if (segment.fPts[2].y() == point.y()) {
577 0 : side = (SegSide)(-signP);
578 : }
579 : }
580 : }
581 :
582 0 : return side;
583 : }
584 :
585 0 : static float distance_to_segment(const SkPoint& point,
586 : const PathSegment& segment,
587 : const RowData& rowData,
588 : SegSide* side) {
589 0 : SkASSERT(side);
590 :
591 0 : const DPoint xformPt = segment.fXformMatrix.mapPoint(point);
592 :
593 0 : if (segment.fType == PathSegment::kLine) {
594 0 : float result = SK_DistanceFieldPad * SK_DistanceFieldPad;
595 :
596 0 : if (between_closed(xformPt.x(), segment.fP0T.x(), segment.fP2T.x())) {
597 0 : result = (float)(xformPt.y() * xformPt.y());
598 0 : } else if (xformPt.x() < segment.fP0T.x()) {
599 0 : result = (float)(xformPt.x() * xformPt.x() + xformPt.y() * xformPt.y());
600 : } else {
601 0 : result = (float)((xformPt.x() - segment.fP2T.x()) * (xformPt.x() - segment.fP2T.x())
602 0 : + xformPt.y() * xformPt.y());
603 : }
604 :
605 0 : if (between_closed_open(point.y(), segment.fBoundingBox.top(),
606 0 : segment.fBoundingBox.bottom())) {
607 0 : *side = (SegSide)(int)sign_of(xformPt.y());
608 : } else {
609 0 : *side = kNA_SegSide;
610 : }
611 0 : return result;
612 : } else {
613 0 : SkASSERT(segment.fType == PathSegment::kQuad);
614 :
615 0 : const float nearestPoint = calculate_nearest_point_for_quad(segment, xformPt);
616 :
617 : float dist;
618 :
619 0 : if (between_closed(nearestPoint, segment.fP0T.x(), segment.fP2T.x())) {
620 0 : DPoint x = DPoint::Make(nearestPoint, nearestPoint * nearestPoint);
621 0 : dist = (float)xformPt.distanceToSqd(x);
622 : } else {
623 0 : const float distToB0T = (float)xformPt.distanceToSqd(segment.fP0T);
624 0 : const float distToB2T = (float)xformPt.distanceToSqd(segment.fP2T);
625 :
626 0 : if (distToB0T < distToB2T) {
627 0 : dist = distToB0T;
628 : } else {
629 0 : dist = distToB2T;
630 : }
631 : }
632 :
633 0 : if (between_closed_open(point.y(), segment.fBoundingBox.top(),
634 0 : segment.fBoundingBox.bottom())) {
635 0 : *side = calculate_side_of_quad(segment, point, xformPt, rowData);
636 : } else {
637 0 : *side = kNA_SegSide;
638 : }
639 :
640 0 : return (float)(dist * segment.fScalingFactorSqd);
641 : }
642 : }
643 :
644 0 : static void calculate_distance_field_data(PathSegmentArray* segments,
645 : DFData* dataPtr,
646 : int width, int height) {
647 0 : int count = segments->count();
648 0 : for (int a = 0; a < count; ++a) {
649 0 : PathSegment& segment = (*segments)[a];
650 : const SkRect& segBB = segment.fBoundingBox.makeOutset(
651 0 : SK_DistanceFieldPad, SK_DistanceFieldPad);
652 0 : int startColumn = (int)segBB.left();
653 0 : int endColumn = SkScalarCeilToInt(segBB.right());
654 :
655 0 : int startRow = (int)segBB.top();
656 0 : int endRow = SkScalarCeilToInt(segBB.bottom());
657 :
658 0 : SkASSERT((startColumn >= 0) && "StartColumn < 0!");
659 0 : SkASSERT((endColumn <= width) && "endColumn > width!");
660 0 : SkASSERT((startRow >= 0) && "StartRow < 0!");
661 0 : SkASSERT((endRow <= height) && "EndRow > height!");
662 :
663 : // Clip inside the distance field to avoid overflow
664 0 : startColumn = SkTMax(startColumn, 0);
665 0 : endColumn = SkTMin(endColumn, width);
666 0 : startRow = SkTMax(startRow, 0);
667 0 : endRow = SkTMin(endRow, height);
668 :
669 0 : for (int row = startRow; row < endRow; ++row) {
670 0 : SegSide prevSide = kNA_SegSide;
671 0 : const float pY = row + 0.5f;
672 : RowData rowData;
673 :
674 0 : const SkPoint pointLeft = SkPoint::Make((SkScalar)startColumn, pY);
675 0 : const SkPoint pointRight = SkPoint::Make((SkScalar)endColumn, pY);
676 :
677 0 : if (between_closed_open(pY, segment.fBoundingBox.top(),
678 0 : segment.fBoundingBox.bottom())) {
679 0 : precomputation_for_row(&rowData, segment, pointLeft, pointRight);
680 : }
681 :
682 0 : for (int col = startColumn; col < endColumn; ++col) {
683 0 : int idx = (row * width) + col;
684 :
685 0 : const float pX = col + 0.5f;
686 0 : const SkPoint point = SkPoint::Make(pX, pY);
687 :
688 0 : const float distSq = dataPtr[idx].fDistSq;
689 0 : int dilation = distSq < 1.5 * 1.5 ? 1 :
690 0 : distSq < 2.5 * 2.5 ? 2 :
691 0 : distSq < 3.5 * 3.5 ? 3 : SK_DistanceFieldPad;
692 0 : if (dilation > SK_DistanceFieldPad) {
693 0 : dilation = SK_DistanceFieldPad;
694 : }
695 :
696 : // Optimisation for not calculating some points.
697 0 : if (dilation != SK_DistanceFieldPad && !segment.fBoundingBox.roundOut()
698 0 : .makeOutset(dilation, dilation).contains(col, row)) {
699 0 : continue;
700 : }
701 :
702 0 : SegSide side = kNA_SegSide;
703 0 : int deltaWindingScore = 0;
704 0 : float currDistSq = distance_to_segment(point, segment, rowData, &side);
705 0 : if (prevSide == kLeft_SegSide && side == kRight_SegSide) {
706 0 : deltaWindingScore = -1;
707 0 : } else if (prevSide == kRight_SegSide && side == kLeft_SegSide) {
708 0 : deltaWindingScore = 1;
709 : }
710 :
711 0 : prevSide = side;
712 :
713 0 : if (currDistSq < distSq) {
714 0 : dataPtr[idx].fDistSq = currDistSq;
715 : }
716 :
717 0 : dataPtr[idx].fDeltaWindingScore += deltaWindingScore;
718 : }
719 : }
720 : }
721 0 : }
722 :
723 : template <int distanceMagnitude>
724 0 : static 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 0 : dist = SkScalarPin(-dist, -distanceMagnitude, distanceMagnitude * 127.0f / 128.0f);
729 :
730 : // Scale into the positive range for unsigned distance.
731 0 : 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 0 : return (unsigned char)SkScalarRoundToInt(dist / (2 * distanceMagnitude) * 256.0f);
737 : }
738 :
739 0 : bool GrGenerateDistanceFieldFromPath(unsigned char* distanceField,
740 : const SkPath& path, const SkMatrix& drawMatrix,
741 : int width, int height, size_t rowBytes) {
742 0 : SkASSERT(distanceField);
743 :
744 0 : SkDEBUGCODE(SkPath xformPath;);
745 0 : SkDEBUGCODE(path.transform(drawMatrix, &xformPath));
746 0 : SkDEBUGCODE(SkIRect pathBounds = xformPath.getBounds().roundOut());
747 0 : SkDEBUGCODE(SkIRect expectPathBounds = SkIRect::MakeWH(width - 2 * SK_DistanceFieldPad,
748 : height - 2 * SK_DistanceFieldPad));
749 0 : SkASSERT(expectPathBounds.isEmpty() ||
750 : expectPathBounds.contains(pathBounds.x(), pathBounds.y()));
751 0 : SkASSERT(expectPathBounds.isEmpty() || pathBounds.isEmpty() ||
752 : expectPathBounds.contains(pathBounds));
753 :
754 0 : SkPath simplifiedPath;
755 0 : SkPath workingPath;
756 0 : if (Simplify(path, &simplifiedPath)) {
757 0 : workingPath = simplifiedPath;
758 : } else {
759 0 : workingPath = path;
760 : }
761 :
762 0 : if (!IsDistanceFieldSupportedFillType(workingPath.getFillType())) {
763 0 : return false;
764 : }
765 :
766 0 : workingPath.transform(drawMatrix);
767 :
768 0 : SkDEBUGCODE(pathBounds = workingPath.getBounds().roundOut());
769 0 : SkASSERT(expectPathBounds.isEmpty() ||
770 : expectPathBounds.contains(pathBounds.x(), pathBounds.y()));
771 0 : SkASSERT(expectPathBounds.isEmpty() || pathBounds.isEmpty() ||
772 : expectPathBounds.contains(pathBounds));
773 :
774 : // translate path to offset (SK_DistanceFieldPad, SK_DistanceFieldPad)
775 : SkMatrix dfMatrix;
776 0 : dfMatrix.setTranslate(SK_DistanceFieldPad, SK_DistanceFieldPad);
777 0 : workingPath.transform(dfMatrix);
778 :
779 : // create temp data
780 0 : size_t dataSize = width * height * sizeof(DFData);
781 0 : SkAutoSMalloc<1024> dfStorage(dataSize);
782 0 : DFData* dataPtr = (DFData*) dfStorage.get();
783 :
784 : // create initial distance data
785 0 : init_distances(dataPtr, width * height);
786 :
787 0 : SkPath::Iter iter(workingPath, true);
788 0 : SkSTArray<15, PathSegment, true> segments;
789 :
790 : for (;;) {
791 : SkPoint pts[4];
792 0 : SkPath::Verb verb = iter.next(pts);
793 0 : switch (verb) {
794 : case SkPath::kMove_Verb:
795 0 : break;
796 : case SkPath::kLine_Verb: {
797 0 : add_line_to_segment(pts, &segments);
798 0 : break;
799 : }
800 : case SkPath::kQuad_Verb:
801 0 : add_quad_segment(pts, &segments);
802 0 : break;
803 : case SkPath::kConic_Verb: {
804 0 : SkScalar weight = iter.conicWeight();
805 0 : SkAutoConicToQuads converter;
806 0 : const SkPoint* quadPts = converter.computeQuads(pts, weight, kConicTolerance);
807 0 : for (int i = 0; i < converter.countQuads(); ++i) {
808 0 : add_quad_segment(quadPts + 2*i, &segments);
809 : }
810 0 : break;
811 : }
812 : case SkPath::kCubic_Verb: {
813 0 : add_cubic_segments(pts, &segments);
814 0 : break;
815 : };
816 : default:
817 0 : break;
818 : }
819 0 : if (verb == SkPath::kDone_Verb) {
820 0 : break;
821 : }
822 0 : }
823 :
824 0 : calculate_distance_field_data(&segments, dataPtr, width, height);
825 :
826 0 : for (int row = 0; row < height; ++row) {
827 0 : int windingNumber = 0; // Winding number start from zero for each scanline
828 0 : for (int col = 0; col < width; ++col) {
829 0 : int idx = (row * width) + col;
830 0 : windingNumber += dataPtr[idx].fDeltaWindingScore;
831 :
832 : enum DFSign {
833 : kInside = -1,
834 : kOutside = 1
835 : } dfSign;
836 :
837 0 : if (workingPath.getFillType() == SkPath::kWinding_FillType) {
838 0 : dfSign = windingNumber ? kInside : kOutside;
839 0 : } else if (workingPath.getFillType() == SkPath::kInverseWinding_FillType) {
840 0 : dfSign = windingNumber ? kOutside : kInside;
841 0 : } else if (workingPath.getFillType() == SkPath::kEvenOdd_FillType) {
842 0 : dfSign = (windingNumber % 2) ? kInside : kOutside;
843 : } else {
844 0 : SkASSERT(workingPath.getFillType() == SkPath::kInverseEvenOdd_FillType);
845 0 : dfSign = (windingNumber % 2) ? kOutside : kInside;
846 : }
847 :
848 : // The winding number at the end of a scanline should be zero.
849 0 : 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 0 : if (col == width - 1 && windingNumber != 0) {
853 0 : for (int col = 0; col < width; ++col) {
854 0 : int idx = (row * width) + col;
855 0 : dfSign = workingPath.contains(col + 0.5, row + 0.5) ? kInside : kOutside;
856 0 : const float miniDist = sqrt(dataPtr[idx].fDistSq);
857 0 : const float dist = dfSign * miniDist;
858 :
859 0 : unsigned char pixelVal = pack_distance_field_val<SK_DistanceFieldMagnitude>(dist);
860 :
861 0 : distanceField[(row * rowBytes) + col] = pixelVal;
862 : }
863 0 : continue;
864 : }
865 :
866 0 : const float miniDist = sqrt(dataPtr[idx].fDistSq);
867 0 : const float dist = dfSign * miniDist;
868 :
869 0 : unsigned char pixelVal = pack_distance_field_val<SK_DistanceFieldMagnitude>(dist);
870 :
871 0 : distanceField[(row * rowBytes) + col] = pixelVal;
872 : }
873 : }
874 0 : return true;
875 : }
|
