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