1 /*
2 * Copyright 2011 Google Inc.
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 "GrPathUtils.h"
9
10 #include "GrTypes.h"
11 #include "SkGeometry.h"
12
scaleToleranceToSrc(SkScalar devTol,const SkMatrix & viewM,const SkRect & pathBounds)13 SkScalar GrPathUtils::scaleToleranceToSrc(SkScalar devTol,
14 const SkMatrix& viewM,
15 const SkRect& pathBounds) {
16 // In order to tesselate the path we get a bound on how much the matrix can
17 // scale when mapping to screen coordinates.
18 SkScalar stretch = viewM.getMaxScale();
19 SkScalar srcTol = devTol;
20
21 if (stretch < 0) {
22 // take worst case mapRadius amoung four corners.
23 // (less than perfect)
24 for (int i = 0; i < 4; ++i) {
25 SkMatrix mat;
26 mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight,
27 (i < 2) ? pathBounds.fTop : pathBounds.fBottom);
28 mat.postConcat(viewM);
29 stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1));
30 }
31 }
32 return srcTol / stretch;
33 }
34
35 static const int MAX_POINTS_PER_CURVE = 1 << 10;
36 static const SkScalar gMinCurveTol = 0.0001f;
37
quadraticPointCount(const SkPoint points[],SkScalar tol)38 uint32_t GrPathUtils::quadraticPointCount(const SkPoint points[],
39 SkScalar tol) {
40 if (tol < gMinCurveTol) {
41 tol = gMinCurveTol;
42 }
43 SkASSERT(tol > 0);
44
45 SkScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
46 if (d <= tol) {
47 return 1;
48 } else {
49 // Each time we subdivide, d should be cut in 4. So we need to
50 // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x)
51 // points.
52 // 2^(log4(x)) = sqrt(x);
53 SkScalar divSqrt = SkScalarSqrt(d / tol);
54 if (((SkScalar)SK_MaxS32) <= divSqrt) {
55 return MAX_POINTS_PER_CURVE;
56 } else {
57 int temp = SkScalarCeilToInt(divSqrt);
58 int pow2 = GrNextPow2(temp);
59 // Because of NaNs & INFs we can wind up with a degenerate temp
60 // such that pow2 comes out negative. Also, our point generator
61 // will always output at least one pt.
62 if (pow2 < 1) {
63 pow2 = 1;
64 }
65 return SkTMin(pow2, MAX_POINTS_PER_CURVE);
66 }
67 }
68 }
69
generateQuadraticPoints(const SkPoint & p0,const SkPoint & p1,const SkPoint & p2,SkScalar tolSqd,SkPoint ** points,uint32_t pointsLeft)70 uint32_t GrPathUtils::generateQuadraticPoints(const SkPoint& p0,
71 const SkPoint& p1,
72 const SkPoint& p2,
73 SkScalar tolSqd,
74 SkPoint** points,
75 uint32_t pointsLeft) {
76 if (pointsLeft < 2 ||
77 (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) {
78 (*points)[0] = p2;
79 *points += 1;
80 return 1;
81 }
82
83 SkPoint q[] = {
84 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
85 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
86 };
87 SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) };
88
89 pointsLeft >>= 1;
90 uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft);
91 uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft);
92 return a + b;
93 }
94
cubicPointCount(const SkPoint points[],SkScalar tol)95 uint32_t GrPathUtils::cubicPointCount(const SkPoint points[],
96 SkScalar tol) {
97 if (tol < gMinCurveTol) {
98 tol = gMinCurveTol;
99 }
100 SkASSERT(tol > 0);
101
102 SkScalar d = SkTMax(
103 points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]),
104 points[2].distanceToLineSegmentBetweenSqd(points[0], points[3]));
105 d = SkScalarSqrt(d);
106 if (d <= tol) {
107 return 1;
108 } else {
109 SkScalar divSqrt = SkScalarSqrt(d / tol);
110 if (((SkScalar)SK_MaxS32) <= divSqrt) {
111 return MAX_POINTS_PER_CURVE;
112 } else {
113 int temp = SkScalarCeilToInt(SkScalarSqrt(d / tol));
114 int pow2 = GrNextPow2(temp);
115 // Because of NaNs & INFs we can wind up with a degenerate temp
116 // such that pow2 comes out negative. Also, our point generator
117 // will always output at least one pt.
118 if (pow2 < 1) {
119 pow2 = 1;
120 }
121 return SkTMin(pow2, MAX_POINTS_PER_CURVE);
122 }
123 }
124 }
125
generateCubicPoints(const SkPoint & p0,const SkPoint & p1,const SkPoint & p2,const SkPoint & p3,SkScalar tolSqd,SkPoint ** points,uint32_t pointsLeft)126 uint32_t GrPathUtils::generateCubicPoints(const SkPoint& p0,
127 const SkPoint& p1,
128 const SkPoint& p2,
129 const SkPoint& p3,
130 SkScalar tolSqd,
131 SkPoint** points,
132 uint32_t pointsLeft) {
133 if (pointsLeft < 2 ||
134 (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd &&
135 p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) {
136 (*points)[0] = p3;
137 *points += 1;
138 return 1;
139 }
140 SkPoint q[] = {
141 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
142 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
143 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
144 };
145 SkPoint r[] = {
146 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
147 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
148 };
149 SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) };
150 pointsLeft >>= 1;
151 uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft);
152 uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft);
153 return a + b;
154 }
155
worstCasePointCount(const SkPath & path,int * subpaths,SkScalar tol)156 int GrPathUtils::worstCasePointCount(const SkPath& path, int* subpaths,
157 SkScalar tol) {
158 if (tol < gMinCurveTol) {
159 tol = gMinCurveTol;
160 }
161 SkASSERT(tol > 0);
162
163 int pointCount = 0;
164 *subpaths = 1;
165
166 bool first = true;
167
168 SkPath::Iter iter(path, false);
169 SkPath::Verb verb;
170
171 SkPoint pts[4];
172 while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
173
174 switch (verb) {
175 case SkPath::kLine_Verb:
176 pointCount += 1;
177 break;
178 case SkPath::kConic_Verb: {
179 SkScalar weight = iter.conicWeight();
180 SkAutoConicToQuads converter;
181 const SkPoint* quadPts = converter.computeQuads(pts, weight, 0.25f);
182 for (int i = 0; i < converter.countQuads(); ++i) {
183 pointCount += quadraticPointCount(quadPts + 2*i, tol);
184 }
185 }
186 case SkPath::kQuad_Verb:
187 pointCount += quadraticPointCount(pts, tol);
188 break;
189 case SkPath::kCubic_Verb:
190 pointCount += cubicPointCount(pts, tol);
191 break;
192 case SkPath::kMove_Verb:
193 pointCount += 1;
194 if (!first) {
195 ++(*subpaths);
196 }
197 break;
198 default:
199 break;
200 }
201 first = false;
202 }
203 return pointCount;
204 }
205
set(const SkPoint qPts[3])206 void GrPathUtils::QuadUVMatrix::set(const SkPoint qPts[3]) {
207 SkMatrix m;
208 // We want M such that M * xy_pt = uv_pt
209 // We know M * control_pts = [0 1/2 1]
210 // [0 0 1]
211 // [1 1 1]
212 // And control_pts = [x0 x1 x2]
213 // [y0 y1 y2]
214 // [1 1 1 ]
215 // We invert the control pt matrix and post concat to both sides to get M.
216 // Using the known form of the control point matrix and the result, we can
217 // optimize and improve precision.
218
219 double x0 = qPts[0].fX;
220 double y0 = qPts[0].fY;
221 double x1 = qPts[1].fX;
222 double y1 = qPts[1].fY;
223 double x2 = qPts[2].fX;
224 double y2 = qPts[2].fY;
225 double det = x0*y1 - y0*x1 + x2*y0 - y2*x0 + x1*y2 - y1*x2;
226
227 if (!sk_float_isfinite(det)
228 || SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero)) {
229 // The quad is degenerate. Hopefully this is rare. Find the pts that are
230 // farthest apart to compute a line (unless it is really a pt).
231 SkScalar maxD = qPts[0].distanceToSqd(qPts[1]);
232 int maxEdge = 0;
233 SkScalar d = qPts[1].distanceToSqd(qPts[2]);
234 if (d > maxD) {
235 maxD = d;
236 maxEdge = 1;
237 }
238 d = qPts[2].distanceToSqd(qPts[0]);
239 if (d > maxD) {
240 maxD = d;
241 maxEdge = 2;
242 }
243 // We could have a tolerance here, not sure if it would improve anything
244 if (maxD > 0) {
245 // Set the matrix to give (u = 0, v = distance_to_line)
246 SkVector lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge];
247 // when looking from the point 0 down the line we want positive
248 // distances to be to the left. This matches the non-degenerate
249 // case.
250 lineVec.setOrthog(lineVec, SkPoint::kLeft_Side);
251 lineVec.dot(qPts[0]);
252 // first row
253 fM[0] = 0;
254 fM[1] = 0;
255 fM[2] = 0;
256 // second row
257 fM[3] = lineVec.fX;
258 fM[4] = lineVec.fY;
259 fM[5] = -lineVec.dot(qPts[maxEdge]);
260 } else {
261 // It's a point. It should cover zero area. Just set the matrix such
262 // that (u, v) will always be far away from the quad.
263 fM[0] = 0; fM[1] = 0; fM[2] = 100.f;
264 fM[3] = 0; fM[4] = 0; fM[5] = 100.f;
265 }
266 } else {
267 double scale = 1.0/det;
268
269 // compute adjugate matrix
270 double a0, a1, a2, a3, a4, a5, a6, a7, a8;
271 a0 = y1-y2;
272 a1 = x2-x1;
273 a2 = x1*y2-x2*y1;
274
275 a3 = y2-y0;
276 a4 = x0-x2;
277 a5 = x2*y0-x0*y2;
278
279 a6 = y0-y1;
280 a7 = x1-x0;
281 a8 = x0*y1-x1*y0;
282
283 // this performs the uv_pts*adjugate(control_pts) multiply,
284 // then does the scale by 1/det afterwards to improve precision
285 m[SkMatrix::kMScaleX] = (float)((0.5*a3 + a6)*scale);
286 m[SkMatrix::kMSkewX] = (float)((0.5*a4 + a7)*scale);
287 m[SkMatrix::kMTransX] = (float)((0.5*a5 + a8)*scale);
288
289 m[SkMatrix::kMSkewY] = (float)(a6*scale);
290 m[SkMatrix::kMScaleY] = (float)(a7*scale);
291 m[SkMatrix::kMTransY] = (float)(a8*scale);
292
293 m[SkMatrix::kMPersp0] = (float)((a0 + a3 + a6)*scale);
294 m[SkMatrix::kMPersp1] = (float)((a1 + a4 + a7)*scale);
295 m[SkMatrix::kMPersp2] = (float)((a2 + a5 + a8)*scale);
296
297 // The matrix should not have perspective.
298 SkDEBUGCODE(static const SkScalar gTOL = 1.f / 100.f);
299 SkASSERT(SkScalarAbs(m.get(SkMatrix::kMPersp0)) < gTOL);
300 SkASSERT(SkScalarAbs(m.get(SkMatrix::kMPersp1)) < gTOL);
301
302 // It may not be normalized to have 1.0 in the bottom right
303 float m33 = m.get(SkMatrix::kMPersp2);
304 if (1.f != m33) {
305 m33 = 1.f / m33;
306 fM[0] = m33 * m.get(SkMatrix::kMScaleX);
307 fM[1] = m33 * m.get(SkMatrix::kMSkewX);
308 fM[2] = m33 * m.get(SkMatrix::kMTransX);
309 fM[3] = m33 * m.get(SkMatrix::kMSkewY);
310 fM[4] = m33 * m.get(SkMatrix::kMScaleY);
311 fM[5] = m33 * m.get(SkMatrix::kMTransY);
312 } else {
313 fM[0] = m.get(SkMatrix::kMScaleX);
314 fM[1] = m.get(SkMatrix::kMSkewX);
315 fM[2] = m.get(SkMatrix::kMTransX);
316 fM[3] = m.get(SkMatrix::kMSkewY);
317 fM[4] = m.get(SkMatrix::kMScaleY);
318 fM[5] = m.get(SkMatrix::kMTransY);
319 }
320 }
321 }
322
323 ////////////////////////////////////////////////////////////////////////////////
324
325 // k = (y2 - y0, x0 - x2, (x2 - x0)*y0 - (y2 - y0)*x0 )
326 // l = (2*w * (y1 - y0), 2*w * (x0 - x1), 2*w * (x1*y0 - x0*y1))
327 // m = (2*w * (y2 - y1), 2*w * (x1 - x2), 2*w * (x2*y1 - x1*y2))
getConicKLM(const SkPoint p[3],const SkScalar weight,SkScalar klm[9])328 void GrPathUtils::getConicKLM(const SkPoint p[3], const SkScalar weight, SkScalar klm[9]) {
329 const SkScalar w2 = 2.f * weight;
330 klm[0] = p[2].fY - p[0].fY;
331 klm[1] = p[0].fX - p[2].fX;
332 klm[2] = (p[2].fX - p[0].fX) * p[0].fY - (p[2].fY - p[0].fY) * p[0].fX;
333
334 klm[3] = w2 * (p[1].fY - p[0].fY);
335 klm[4] = w2 * (p[0].fX - p[1].fX);
336 klm[5] = w2 * (p[1].fX * p[0].fY - p[0].fX * p[1].fY);
337
338 klm[6] = w2 * (p[2].fY - p[1].fY);
339 klm[7] = w2 * (p[1].fX - p[2].fX);
340 klm[8] = w2 * (p[2].fX * p[1].fY - p[1].fX * p[2].fY);
341
342 // scale the max absolute value of coeffs to 10
343 SkScalar scale = 0.f;
344 for (int i = 0; i < 9; ++i) {
345 scale = SkMaxScalar(scale, SkScalarAbs(klm[i]));
346 }
347 SkASSERT(scale > 0.f);
348 scale = 10.f / scale;
349 for (int i = 0; i < 9; ++i) {
350 klm[i] *= scale;
351 }
352 }
353
354 ////////////////////////////////////////////////////////////////////////////////
355
356 namespace {
357
358 // a is the first control point of the cubic.
359 // ab is the vector from a to the second control point.
360 // dc is the vector from the fourth to the third control point.
361 // d is the fourth control point.
362 // p is the candidate quadratic control point.
363 // this assumes that the cubic doesn't inflect and is simple
is_point_within_cubic_tangents(const SkPoint & a,const SkVector & ab,const SkVector & dc,const SkPoint & d,SkPathPriv::FirstDirection dir,const SkPoint p)364 bool is_point_within_cubic_tangents(const SkPoint& a,
365 const SkVector& ab,
366 const SkVector& dc,
367 const SkPoint& d,
368 SkPathPriv::FirstDirection dir,
369 const SkPoint p) {
370 SkVector ap = p - a;
371 SkScalar apXab = ap.cross(ab);
372 if (SkPathPriv::kCW_FirstDirection == dir) {
373 if (apXab > 0) {
374 return false;
375 }
376 } else {
377 SkASSERT(SkPathPriv::kCCW_FirstDirection == dir);
378 if (apXab < 0) {
379 return false;
380 }
381 }
382
383 SkVector dp = p - d;
384 SkScalar dpXdc = dp.cross(dc);
385 if (SkPathPriv::kCW_FirstDirection == dir) {
386 if (dpXdc < 0) {
387 return false;
388 }
389 } else {
390 SkASSERT(SkPathPriv::kCCW_FirstDirection == dir);
391 if (dpXdc > 0) {
392 return false;
393 }
394 }
395 return true;
396 }
397
convert_noninflect_cubic_to_quads(const SkPoint p[4],SkScalar toleranceSqd,bool constrainWithinTangents,SkPathPriv::FirstDirection dir,SkTArray<SkPoint,true> * quads,int sublevel=0)398 void convert_noninflect_cubic_to_quads(const SkPoint p[4],
399 SkScalar toleranceSqd,
400 bool constrainWithinTangents,
401 SkPathPriv::FirstDirection dir,
402 SkTArray<SkPoint, true>* quads,
403 int sublevel = 0) {
404
405 // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is
406 // p[2]. Point d is always p[3]. Point c is p[2] unless p[2] == p[3], in which case it is p[1].
407
408 SkVector ab = p[1] - p[0];
409 SkVector dc = p[2] - p[3];
410
411 if (ab.lengthSqd() < SK_ScalarNearlyZero) {
412 if (dc.lengthSqd() < SK_ScalarNearlyZero) {
413 SkPoint* degQuad = quads->push_back_n(3);
414 degQuad[0] = p[0];
415 degQuad[1] = p[0];
416 degQuad[2] = p[3];
417 return;
418 }
419 ab = p[2] - p[0];
420 }
421 if (dc.lengthSqd() < SK_ScalarNearlyZero) {
422 dc = p[1] - p[3];
423 }
424
425 // When the ab and cd tangents are degenerate or nearly parallel with vector from d to a the
426 // constraint that the quad point falls between the tangents becomes hard to enforce and we are
427 // likely to hit the max subdivision count. However, in this case the cubic is approaching a
428 // line and the accuracy of the quad point isn't so important. We check if the two middle cubic
429 // control points are very close to the baseline vector. If so then we just pick quadratic
430 // points on the control polygon.
431
432 if (constrainWithinTangents) {
433 SkVector da = p[0] - p[3];
434 bool doQuads = dc.lengthSqd() < SK_ScalarNearlyZero ||
435 ab.lengthSqd() < SK_ScalarNearlyZero;
436 if (!doQuads) {
437 SkScalar invDALengthSqd = da.lengthSqd();
438 if (invDALengthSqd > SK_ScalarNearlyZero) {
439 invDALengthSqd = SkScalarInvert(invDALengthSqd);
440 // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a.
441 // same goes for point c using vector cd.
442 SkScalar detABSqd = ab.cross(da);
443 detABSqd = SkScalarSquare(detABSqd);
444 SkScalar detDCSqd = dc.cross(da);
445 detDCSqd = SkScalarSquare(detDCSqd);
446 if (SkScalarMul(detABSqd, invDALengthSqd) < toleranceSqd &&
447 SkScalarMul(detDCSqd, invDALengthSqd) < toleranceSqd) {
448 doQuads = true;
449 }
450 }
451 }
452 if (doQuads) {
453 SkPoint b = p[0] + ab;
454 SkPoint c = p[3] + dc;
455 SkPoint mid = b + c;
456 mid.scale(SK_ScalarHalf);
457 // Insert two quadratics to cover the case when ab points away from d and/or dc
458 // points away from a.
459 if (SkVector::DotProduct(da, dc) < 0 || SkVector::DotProduct(ab,da) > 0) {
460 SkPoint* qpts = quads->push_back_n(6);
461 qpts[0] = p[0];
462 qpts[1] = b;
463 qpts[2] = mid;
464 qpts[3] = mid;
465 qpts[4] = c;
466 qpts[5] = p[3];
467 } else {
468 SkPoint* qpts = quads->push_back_n(3);
469 qpts[0] = p[0];
470 qpts[1] = mid;
471 qpts[2] = p[3];
472 }
473 return;
474 }
475 }
476
477 static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
478 static const int kMaxSubdivs = 10;
479
480 ab.scale(kLengthScale);
481 dc.scale(kLengthScale);
482
483 // e0 and e1 are extrapolations along vectors ab and dc.
484 SkVector c0 = p[0];
485 c0 += ab;
486 SkVector c1 = p[3];
487 c1 += dc;
488
489 SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : c0.distanceToSqd(c1);
490 if (dSqd < toleranceSqd) {
491 SkPoint cAvg = c0;
492 cAvg += c1;
493 cAvg.scale(SK_ScalarHalf);
494
495 bool subdivide = false;
496
497 if (constrainWithinTangents &&
498 !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) {
499 // choose a new cAvg that is the intersection of the two tangent lines.
500 ab.setOrthog(ab);
501 SkScalar z0 = -ab.dot(p[0]);
502 dc.setOrthog(dc);
503 SkScalar z1 = -dc.dot(p[3]);
504 cAvg.fX = SkScalarMul(ab.fY, z1) - SkScalarMul(z0, dc.fY);
505 cAvg.fY = SkScalarMul(z0, dc.fX) - SkScalarMul(ab.fX, z1);
506 SkScalar z = SkScalarMul(ab.fX, dc.fY) - SkScalarMul(ab.fY, dc.fX);
507 z = SkScalarInvert(z);
508 cAvg.fX *= z;
509 cAvg.fY *= z;
510 if (sublevel <= kMaxSubdivs) {
511 SkScalar d0Sqd = c0.distanceToSqd(cAvg);
512 SkScalar d1Sqd = c1.distanceToSqd(cAvg);
513 // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know
514 // the distances and tolerance can't be negative.
515 // (d0 + d1)^2 > toleranceSqd
516 // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd
517 SkScalar d0d1 = SkScalarSqrt(SkScalarMul(d0Sqd, d1Sqd));
518 subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd;
519 }
520 }
521 if (!subdivide) {
522 SkPoint* pts = quads->push_back_n(3);
523 pts[0] = p[0];
524 pts[1] = cAvg;
525 pts[2] = p[3];
526 return;
527 }
528 }
529 SkPoint choppedPts[7];
530 SkChopCubicAtHalf(p, choppedPts);
531 convert_noninflect_cubic_to_quads(choppedPts + 0,
532 toleranceSqd,
533 constrainWithinTangents,
534 dir,
535 quads,
536 sublevel + 1);
537 convert_noninflect_cubic_to_quads(choppedPts + 3,
538 toleranceSqd,
539 constrainWithinTangents,
540 dir,
541 quads,
542 sublevel + 1);
543 }
544 }
545
convertCubicToQuads(const SkPoint p[4],SkScalar tolScale,SkTArray<SkPoint,true> * quads)546 void GrPathUtils::convertCubicToQuads(const SkPoint p[4],
547 SkScalar tolScale,
548 SkTArray<SkPoint, true>* quads) {
549 SkPoint chopped[10];
550 int count = SkChopCubicAtInflections(p, chopped);
551
552 const SkScalar tolSqd = SkScalarSquare(tolScale);
553
554 for (int i = 0; i < count; ++i) {
555 SkPoint* cubic = chopped + 3*i;
556 // The direction param is ignored if the third param is false.
557 convert_noninflect_cubic_to_quads(cubic, tolSqd, false,
558 SkPathPriv::kCCW_FirstDirection, quads);
559 }
560 }
561
convertCubicToQuadsConstrainToTangents(const SkPoint p[4],SkScalar tolScale,SkPathPriv::FirstDirection dir,SkTArray<SkPoint,true> * quads)562 void GrPathUtils::convertCubicToQuadsConstrainToTangents(const SkPoint p[4],
563 SkScalar tolScale,
564 SkPathPriv::FirstDirection dir,
565 SkTArray<SkPoint, true>* quads) {
566 SkPoint chopped[10];
567 int count = SkChopCubicAtInflections(p, chopped);
568
569 const SkScalar tolSqd = SkScalarSquare(tolScale);
570
571 for (int i = 0; i < count; ++i) {
572 SkPoint* cubic = chopped + 3*i;
573 convert_noninflect_cubic_to_quads(cubic, tolSqd, true, dir, quads);
574 }
575 }
576
577 ////////////////////////////////////////////////////////////////////////////////
578
579 // Solves linear system to extract klm
580 // P.K = k (similarly for l, m)
581 // Where P is matrix of control points
582 // K is coefficients for the line K
583 // k is vector of values of K evaluated at the control points
584 // Solving for K, thus K = P^(-1) . k
calc_cubic_klm(const SkPoint p[4],const SkScalar controlK[4],const SkScalar controlL[4],const SkScalar controlM[4],SkScalar k[3],SkScalar l[3],SkScalar m[3])585 static void calc_cubic_klm(const SkPoint p[4], const SkScalar controlK[4],
586 const SkScalar controlL[4], const SkScalar controlM[4],
587 SkScalar k[3], SkScalar l[3], SkScalar m[3]) {
588 SkMatrix matrix;
589 matrix.setAll(p[0].fX, p[0].fY, 1.f,
590 p[1].fX, p[1].fY, 1.f,
591 p[2].fX, p[2].fY, 1.f);
592 SkMatrix inverse;
593 if (matrix.invert(&inverse)) {
594 inverse.mapHomogeneousPoints(k, controlK, 1);
595 inverse.mapHomogeneousPoints(l, controlL, 1);
596 inverse.mapHomogeneousPoints(m, controlM, 1);
597 }
598
599 }
600
set_serp_klm(const SkScalar d[3],SkScalar k[4],SkScalar l[4],SkScalar m[4])601 static void set_serp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
602 SkScalar tempSqrt = SkScalarSqrt(9.f * d[1] * d[1] - 12.f * d[0] * d[2]);
603 SkScalar ls = 3.f * d[1] - tempSqrt;
604 SkScalar lt = 6.f * d[0];
605 SkScalar ms = 3.f * d[1] + tempSqrt;
606 SkScalar mt = 6.f * d[0];
607
608 k[0] = ls * ms;
609 k[1] = (3.f * ls * ms - ls * mt - lt * ms) / 3.f;
610 k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f;
611 k[3] = (lt - ls) * (mt - ms);
612
613 l[0] = ls * ls * ls;
614 const SkScalar lt_ls = lt - ls;
615 l[1] = ls * ls * lt_ls * -1.f;
616 l[2] = lt_ls * lt_ls * ls;
617 l[3] = -1.f * lt_ls * lt_ls * lt_ls;
618
619 m[0] = ms * ms * ms;
620 const SkScalar mt_ms = mt - ms;
621 m[1] = ms * ms * mt_ms * -1.f;
622 m[2] = mt_ms * mt_ms * ms;
623 m[3] = -1.f * mt_ms * mt_ms * mt_ms;
624
625 // If d0 < 0 we need to flip the orientation of our curve
626 // This is done by negating the k and l values
627 // We want negative distance values to be on the inside
628 if ( d[0] > 0) {
629 for (int i = 0; i < 4; ++i) {
630 k[i] = -k[i];
631 l[i] = -l[i];
632 }
633 }
634 }
635
set_loop_klm(const SkScalar d[3],SkScalar k[4],SkScalar l[4],SkScalar m[4])636 static void set_loop_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
637 SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
638 SkScalar ls = d[1] - tempSqrt;
639 SkScalar lt = 2.f * d[0];
640 SkScalar ms = d[1] + tempSqrt;
641 SkScalar mt = 2.f * d[0];
642
643 k[0] = ls * ms;
644 k[1] = (3.f * ls*ms - ls * mt - lt * ms) / 3.f;
645 k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f;
646 k[3] = (lt - ls) * (mt - ms);
647
648 l[0] = ls * ls * ms;
649 l[1] = (ls * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/-3.f;
650 l[2] = ((lt - ls) * (ls * (2.f * mt - 3.f * ms) + lt * ms))/3.f;
651 l[3] = -1.f * (lt - ls) * (lt - ls) * (mt - ms);
652
653 m[0] = ls * ms * ms;
654 m[1] = (ms * (ls * (2.f * mt - 3.f * ms) + lt * ms))/-3.f;
655 m[2] = ((mt - ms) * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/3.f;
656 m[3] = -1.f * (lt - ls) * (mt - ms) * (mt - ms);
657
658
659 // If (d0 < 0 && sign(k1) > 0) || (d0 > 0 && sign(k1) < 0),
660 // we need to flip the orientation of our curve.
661 // This is done by negating the k and l values
662 if ( (d[0] < 0 && k[1] > 0) || (d[0] > 0 && k[1] < 0)) {
663 for (int i = 0; i < 4; ++i) {
664 k[i] = -k[i];
665 l[i] = -l[i];
666 }
667 }
668 }
669
set_cusp_klm(const SkScalar d[3],SkScalar k[4],SkScalar l[4],SkScalar m[4])670 static void set_cusp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
671 const SkScalar ls = d[2];
672 const SkScalar lt = 3.f * d[1];
673
674 k[0] = ls;
675 k[1] = ls - lt / 3.f;
676 k[2] = ls - 2.f * lt / 3.f;
677 k[3] = ls - lt;
678
679 l[0] = ls * ls * ls;
680 const SkScalar ls_lt = ls - lt;
681 l[1] = ls * ls * ls_lt;
682 l[2] = ls_lt * ls_lt * ls;
683 l[3] = ls_lt * ls_lt * ls_lt;
684
685 m[0] = 1.f;
686 m[1] = 1.f;
687 m[2] = 1.f;
688 m[3] = 1.f;
689 }
690
691 // For the case when a cubic is actually a quadratic
692 // M =
693 // 0 0 0
694 // 1/3 0 1/3
695 // 2/3 1/3 2/3
696 // 1 1 1
set_quadratic_klm(const SkScalar d[3],SkScalar k[4],SkScalar l[4],SkScalar m[4])697 static void set_quadratic_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
698 k[0] = 0.f;
699 k[1] = 1.f/3.f;
700 k[2] = 2.f/3.f;
701 k[3] = 1.f;
702
703 l[0] = 0.f;
704 l[1] = 0.f;
705 l[2] = 1.f/3.f;
706 l[3] = 1.f;
707
708 m[0] = 0.f;
709 m[1] = 1.f/3.f;
710 m[2] = 2.f/3.f;
711 m[3] = 1.f;
712
713 // If d2 < 0 we need to flip the orientation of our curve
714 // This is done by negating the k and l values
715 if ( d[2] > 0) {
716 for (int i = 0; i < 4; ++i) {
717 k[i] = -k[i];
718 l[i] = -l[i];
719 }
720 }
721 }
722
chopCubicAtLoopIntersection(const SkPoint src[4],SkPoint dst[10],SkScalar klm[9],SkScalar klm_rev[3])723 int GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkScalar klm[9],
724 SkScalar klm_rev[3]) {
725 // Variable to store the two parametric values at the loop double point
726 SkScalar smallS = 0.f;
727 SkScalar largeS = 0.f;
728
729 SkScalar d[3];
730 SkCubicType cType = SkClassifyCubic(src, d);
731
732 int chop_count = 0;
733 if (kLoop_SkCubicType == cType) {
734 SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
735 SkScalar ls = d[1] - tempSqrt;
736 SkScalar lt = 2.f * d[0];
737 SkScalar ms = d[1] + tempSqrt;
738 SkScalar mt = 2.f * d[0];
739 ls = ls / lt;
740 ms = ms / mt;
741 // need to have t values sorted since this is what is expected by SkChopCubicAt
742 if (ls <= ms) {
743 smallS = ls;
744 largeS = ms;
745 } else {
746 smallS = ms;
747 largeS = ls;
748 }
749
750 SkScalar chop_ts[2];
751 if (smallS > 0.f && smallS < 1.f) {
752 chop_ts[chop_count++] = smallS;
753 }
754 if (largeS > 0.f && largeS < 1.f) {
755 chop_ts[chop_count++] = largeS;
756 }
757 if(dst) {
758 SkChopCubicAt(src, dst, chop_ts, chop_count);
759 }
760 } else {
761 if (dst) {
762 memcpy(dst, src, sizeof(SkPoint) * 4);
763 }
764 }
765
766 if (klm && klm_rev) {
767 // Set klm_rev to to match the sub_section of cubic that needs to have its orientation
768 // flipped. This will always be the section that is the "loop"
769 if (2 == chop_count) {
770 klm_rev[0] = 1.f;
771 klm_rev[1] = -1.f;
772 klm_rev[2] = 1.f;
773 } else if (1 == chop_count) {
774 if (smallS < 0.f) {
775 klm_rev[0] = -1.f;
776 klm_rev[1] = 1.f;
777 } else {
778 klm_rev[0] = 1.f;
779 klm_rev[1] = -1.f;
780 }
781 } else {
782 if (smallS < 0.f && largeS > 1.f) {
783 klm_rev[0] = -1.f;
784 } else {
785 klm_rev[0] = 1.f;
786 }
787 }
788 SkScalar controlK[4];
789 SkScalar controlL[4];
790 SkScalar controlM[4];
791
792 if (kSerpentine_SkCubicType == cType || (kCusp_SkCubicType == cType && 0.f != d[0])) {
793 set_serp_klm(d, controlK, controlL, controlM);
794 } else if (kLoop_SkCubicType == cType) {
795 set_loop_klm(d, controlK, controlL, controlM);
796 } else if (kCusp_SkCubicType == cType) {
797 SkASSERT(0.f == d[0]);
798 set_cusp_klm(d, controlK, controlL, controlM);
799 } else if (kQuadratic_SkCubicType == cType) {
800 set_quadratic_klm(d, controlK, controlL, controlM);
801 }
802
803 calc_cubic_klm(src, controlK, controlL, controlM, klm, &klm[3], &klm[6]);
804 }
805 return chop_count + 1;
806 }
807
getCubicKLM(const SkPoint p[4],SkScalar klm[9])808 void GrPathUtils::getCubicKLM(const SkPoint p[4], SkScalar klm[9]) {
809 SkScalar d[3];
810 SkCubicType cType = SkClassifyCubic(p, d);
811
812 SkScalar controlK[4];
813 SkScalar controlL[4];
814 SkScalar controlM[4];
815
816 if (kSerpentine_SkCubicType == cType || (kCusp_SkCubicType == cType && 0.f != d[0])) {
817 set_serp_klm(d, controlK, controlL, controlM);
818 } else if (kLoop_SkCubicType == cType) {
819 set_loop_klm(d, controlK, controlL, controlM);
820 } else if (kCusp_SkCubicType == cType) {
821 SkASSERT(0.f == d[0]);
822 set_cusp_klm(d, controlK, controlL, controlM);
823 } else if (kQuadratic_SkCubicType == cType) {
824 set_quadratic_klm(d, controlK, controlL, controlM);
825 }
826
827 calc_cubic_klm(p, controlK, controlL, controlM, klm, &klm[3], &klm[6]);
828 }
829