1
2 /*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10 #include "GrPathUtils.h"
11 #include "GrPoint.h"
12 #include "SkGeometry.h"
13
scaleToleranceToSrc(GrScalar devTol,const GrMatrix & viewM,const GrRect & pathBounds)14 GrScalar GrPathUtils::scaleToleranceToSrc(GrScalar devTol,
15 const GrMatrix& viewM,
16 const GrRect& pathBounds) {
17 // In order to tesselate the path we get a bound on how much the matrix can
18 // stretch when mapping to screen coordinates.
19 GrScalar stretch = viewM.getMaxStretch();
20 GrScalar srcTol = devTol;
21
22 if (stretch < 0) {
23 // take worst case mapRadius amoung four corners.
24 // (less than perfect)
25 for (int i = 0; i < 4; ++i) {
26 GrMatrix mat;
27 mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight,
28 (i < 2) ? pathBounds.fTop : pathBounds.fBottom);
29 mat.postConcat(viewM);
30 stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1));
31 }
32 }
33 srcTol = GrScalarDiv(srcTol, stretch);
34 return srcTol;
35 }
36
37 static const int MAX_POINTS_PER_CURVE = 1 << 10;
38 static const GrScalar gMinCurveTol = GrFloatToScalar(0.0001f);
39
quadraticPointCount(const GrPoint points[],GrScalar tol)40 uint32_t GrPathUtils::quadraticPointCount(const GrPoint points[],
41 GrScalar tol) {
42 if (tol < gMinCurveTol) {
43 tol = gMinCurveTol;
44 }
45 GrAssert(tol > 0);
46
47 GrScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
48 if (d <= tol) {
49 return 1;
50 } else {
51 // Each time we subdivide, d should be cut in 4. So we need to
52 // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x)
53 // points.
54 // 2^(log4(x)) = sqrt(x);
55 int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
56 int pow2 = GrNextPow2(temp);
57 // Because of NaNs & INFs we can wind up with a degenerate temp
58 // such that pow2 comes out negative. Also, our point generator
59 // will always output at least one pt.
60 if (pow2 < 1) {
61 pow2 = 1;
62 }
63 return GrMin(pow2, MAX_POINTS_PER_CURVE);
64 }
65 }
66
generateQuadraticPoints(const GrPoint & p0,const GrPoint & p1,const GrPoint & p2,GrScalar tolSqd,GrPoint ** points,uint32_t pointsLeft)67 uint32_t GrPathUtils::generateQuadraticPoints(const GrPoint& p0,
68 const GrPoint& p1,
69 const GrPoint& p2,
70 GrScalar tolSqd,
71 GrPoint** points,
72 uint32_t pointsLeft) {
73 if (pointsLeft < 2 ||
74 (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) {
75 (*points)[0] = p2;
76 *points += 1;
77 return 1;
78 }
79
80 GrPoint q[] = {
81 { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
82 { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
83 };
84 GrPoint r = { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) };
85
86 pointsLeft >>= 1;
87 uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft);
88 uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft);
89 return a + b;
90 }
91
cubicPointCount(const GrPoint points[],GrScalar tol)92 uint32_t GrPathUtils::cubicPointCount(const GrPoint points[],
93 GrScalar tol) {
94 if (tol < gMinCurveTol) {
95 tol = gMinCurveTol;
96 }
97 GrAssert(tol > 0);
98
99 GrScalar d = GrMax(
100 points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]),
101 points[2].distanceToLineSegmentBetweenSqd(points[0], points[3]));
102 d = SkScalarSqrt(d);
103 if (d <= tol) {
104 return 1;
105 } else {
106 int temp = SkScalarCeil(SkScalarSqrt(SkScalarDiv(d, tol)));
107 int pow2 = GrNextPow2(temp);
108 // Because of NaNs & INFs we can wind up with a degenerate temp
109 // such that pow2 comes out negative. Also, our point generator
110 // will always output at least one pt.
111 if (pow2 < 1) {
112 pow2 = 1;
113 }
114 return GrMin(pow2, MAX_POINTS_PER_CURVE);
115 }
116 }
117
generateCubicPoints(const GrPoint & p0,const GrPoint & p1,const GrPoint & p2,const GrPoint & p3,GrScalar tolSqd,GrPoint ** points,uint32_t pointsLeft)118 uint32_t GrPathUtils::generateCubicPoints(const GrPoint& p0,
119 const GrPoint& p1,
120 const GrPoint& p2,
121 const GrPoint& p3,
122 GrScalar tolSqd,
123 GrPoint** points,
124 uint32_t pointsLeft) {
125 if (pointsLeft < 2 ||
126 (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd &&
127 p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) {
128 (*points)[0] = p3;
129 *points += 1;
130 return 1;
131 }
132 GrPoint q[] = {
133 { GrScalarAve(p0.fX, p1.fX), GrScalarAve(p0.fY, p1.fY) },
134 { GrScalarAve(p1.fX, p2.fX), GrScalarAve(p1.fY, p2.fY) },
135 { GrScalarAve(p2.fX, p3.fX), GrScalarAve(p2.fY, p3.fY) }
136 };
137 GrPoint r[] = {
138 { GrScalarAve(q[0].fX, q[1].fX), GrScalarAve(q[0].fY, q[1].fY) },
139 { GrScalarAve(q[1].fX, q[2].fX), GrScalarAve(q[1].fY, q[2].fY) }
140 };
141 GrPoint s = { GrScalarAve(r[0].fX, r[1].fX), GrScalarAve(r[0].fY, r[1].fY) };
142 pointsLeft >>= 1;
143 uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft);
144 uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft);
145 return a + b;
146 }
147
worstCasePointCount(const GrPath & path,int * subpaths,GrScalar tol)148 int GrPathUtils::worstCasePointCount(const GrPath& path, int* subpaths,
149 GrScalar tol) {
150 if (tol < gMinCurveTol) {
151 tol = gMinCurveTol;
152 }
153 GrAssert(tol > 0);
154
155 int pointCount = 0;
156 *subpaths = 1;
157
158 bool first = true;
159
160 SkPath::Iter iter(path, false);
161 GrPathCmd cmd;
162
163 GrPoint pts[4];
164 while ((cmd = (GrPathCmd)iter.next(pts)) != kEnd_PathCmd) {
165
166 switch (cmd) {
167 case kLine_PathCmd:
168 pointCount += 1;
169 break;
170 case kQuadratic_PathCmd:
171 pointCount += quadraticPointCount(pts, tol);
172 break;
173 case kCubic_PathCmd:
174 pointCount += cubicPointCount(pts, tol);
175 break;
176 case kMove_PathCmd:
177 pointCount += 1;
178 if (!first) {
179 ++(*subpaths);
180 }
181 break;
182 default:
183 break;
184 }
185 first = false;
186 }
187 return pointCount;
188 }
189
190 namespace {
191 // The matrix computed for quadDesignSpaceToUVCoordsMatrix should never really
192 // have perspective and we really want to avoid perspective matrix muls.
193 // However, the first two entries of the perspective row may be really close to
194 // 0 and the third may not be 1 due to a scale on the entire matrix.
fixup_matrix(GrMatrix * mat)195 inline void fixup_matrix(GrMatrix* mat) {
196 #ifndef SK_SCALAR_IS_FLOAT
197 GrCrash("Expected scalar is float.");
198 #endif
199 static const GrScalar gTOL = 1.f / 100.f;
200 GrAssert(GrScalarAbs(mat->get(SkMatrix::kMPersp0)) < gTOL);
201 GrAssert(GrScalarAbs(mat->get(SkMatrix::kMPersp1)) < gTOL);
202 float m33 = mat->get(SkMatrix::kMPersp2);
203 if (1.f != m33) {
204 m33 = 1.f / m33;
205 mat->setAll(m33 * mat->get(SkMatrix::kMScaleX),
206 m33 * mat->get(SkMatrix::kMSkewX),
207 m33 * mat->get(SkMatrix::kMTransX),
208 m33 * mat->get(SkMatrix::kMSkewY),
209 m33 * mat->get(SkMatrix::kMScaleY),
210 m33 * mat->get(SkMatrix::kMTransY),
211 0.f, 0.f, 1.f);
212 } else {
213 mat->setPerspX(0);
214 mat->setPerspY(0);
215 }
216 }
217 }
218
219 // Compute a matrix that goes from the 2d space coordinates to UV space where
220 // u^2-v = 0 specifies the quad.
quadDesignSpaceToUVCoordsMatrix(const SkPoint qPts[3],GrMatrix * matrix)221 void GrPathUtils::quadDesignSpaceToUVCoordsMatrix(const SkPoint qPts[3],
222 GrMatrix* matrix) {
223 // can't make this static, no cons :(
224 SkMatrix UVpts;
225 #ifndef SK_SCALAR_IS_FLOAT
226 GrCrash("Expected scalar is float.");
227 #endif
228 // We want M such that M * xy_pt = uv_pt
229 // We know M * control_pts = [0 1/2 1]
230 // [0 0 1]
231 // [1 1 1]
232 // We invert the control pt matrix and post concat to both sides to get M.
233 UVpts.setAll(0, 0.5f, 1.f,
234 0, 0, 1.f,
235 1.f, 1.f, 1.f);
236 matrix->setAll(qPts[0].fX, qPts[1].fX, qPts[2].fX,
237 qPts[0].fY, qPts[1].fY, qPts[2].fY,
238 1.f, 1.f, 1.f);
239 if (!matrix->invert(matrix)) {
240 // The quad is degenerate. Hopefully this is rare. Find the pts that are
241 // farthest apart to compute a line (unless it is really a pt).
242 SkScalar maxD = qPts[0].distanceToSqd(qPts[1]);
243 int maxEdge = 0;
244 SkScalar d = qPts[1].distanceToSqd(qPts[2]);
245 if (d > maxD) {
246 maxD = d;
247 maxEdge = 1;
248 }
249 d = qPts[2].distanceToSqd(qPts[0]);
250 if (d > maxD) {
251 maxD = d;
252 maxEdge = 2;
253 }
254 // We could have a tolerance here, not sure if it would improve anything
255 if (maxD > 0) {
256 // Set the matrix to give (u = 0, v = distance_to_line)
257 GrVec lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge];
258 // when looking from the point 0 down the line we want positive
259 // distances to be to the left. This matches the non-degenerate
260 // case.
261 lineVec.setOrthog(lineVec, GrPoint::kLeft_Side);
262 lineVec.dot(qPts[0]);
263 matrix->setAll(0, 0, 0,
264 lineVec.fX, lineVec.fY, -lineVec.dot(qPts[maxEdge]),
265 0, 0, 1.f);
266 } else {
267 // It's a point. It should cover zero area. Just set the matrix such
268 // that (u, v) will always be far away from the quad.
269 matrix->setAll(0, 0, 100 * SK_Scalar1,
270 0, 0, 100 * SK_Scalar1,
271 0, 0, 1.f);
272 }
273 } else {
274 matrix->postConcat(UVpts);
275 fixup_matrix(matrix);
276 }
277 }
278
279 namespace {
convert_noninflect_cubic_to_quads(const SkPoint p[4],SkScalar tolScale,SkTArray<SkPoint,true> * quads,int sublevel=0)280 void convert_noninflect_cubic_to_quads(const SkPoint p[4],
281 SkScalar tolScale,
282 SkTArray<SkPoint, true>* quads,
283 int sublevel = 0) {
284 SkVector ab = p[1];
285 ab -= p[0];
286 SkVector dc = p[2];
287 dc -= p[3];
288
289 static const SkScalar gLengthScale = 3 * SK_Scalar1 / 2;
290 // base tolerance is 2 pixels in dev coords.
291 const SkScalar distanceSqdTol = SkScalarMul(tolScale, 1 * SK_Scalar1);
292 static const int kMaxSubdivs = 10;
293
294 ab.scale(gLengthScale);
295 dc.scale(gLengthScale);
296
297 SkVector c0 = p[0];
298 c0 += ab;
299 SkVector c1 = p[3];
300 c1 += dc;
301
302 SkScalar dSqd = c0.distanceToSqd(c1);
303 if (sublevel > kMaxSubdivs || dSqd <= distanceSqdTol) {
304 SkPoint cAvg = c0;
305 cAvg += c1;
306 cAvg.scale(SK_ScalarHalf);
307
308 SkPoint* pts = quads->push_back_n(3);
309 pts[0] = p[0];
310 pts[1] = cAvg;
311 pts[2] = p[3];
312
313 return;
314 } else {
315 SkPoint choppedPts[7];
316 SkChopCubicAtHalf(p, choppedPts);
317 convert_noninflect_cubic_to_quads(choppedPts + 0, tolScale,
318 quads, sublevel + 1);
319 convert_noninflect_cubic_to_quads(choppedPts + 3, tolScale,
320 quads, sublevel + 1);
321 }
322 }
323 }
324
convertCubicToQuads(const GrPoint p[4],SkScalar tolScale,SkTArray<SkPoint,true> * quads)325 void GrPathUtils::convertCubicToQuads(const GrPoint p[4],
326 SkScalar tolScale,
327 SkTArray<SkPoint, true>* quads) {
328 SkPoint chopped[10];
329 int count = SkChopCubicAtInflections(p, chopped);
330
331 for (int i = 0; i < count; ++i) {
332 SkPoint* cubic = chopped + 3*i;
333 convert_noninflect_cubic_to_quads(cubic, tolScale, quads);
334 }
335
336 }
337