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,SkPath::Direction 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 SkPath::Direction dir,
369 const SkPoint p) {
370 SkVector ap = p - a;
371 SkScalar apXab = ap.cross(ab);
372 if (SkPath::kCW_Direction == dir) {
373 if (apXab > 0) {
374 return false;
375 }
376 } else {
377 SkASSERT(SkPath::kCCW_Direction == dir);
378 if (apXab < 0) {
379 return false;
380 }
381 }
382
383 SkVector dp = p - d;
384 SkScalar dpXdc = dp.cross(dc);
385 if (SkPath::kCW_Direction == dir) {
386 if (dpXdc < 0) {
387 return false;
388 }
389 } else {
390 SkASSERT(SkPath::kCCW_Direction == 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,SkPath::Direction 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 SkPath::Direction 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.isZero()) {
412 if (dc.isZero()) {
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.isZero()) {
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,bool constrainWithinTangents,SkPath::Direction dir,SkTArray<SkPoint,true> * quads)546 void GrPathUtils::convertCubicToQuads(const SkPoint p[4],
547 SkScalar tolScale,
548 bool constrainWithinTangents,
549 SkPath::Direction dir,
550 SkTArray<SkPoint, true>* quads) {
551 SkPoint chopped[10];
552 int count = SkChopCubicAtInflections(p, chopped);
553
554 // base tolerance is 1 pixel.
555 static const SkScalar kTolerance = SK_Scalar1;
556 const SkScalar tolSqd = SkScalarSquare(SkScalarMul(tolScale, kTolerance));
557
558 for (int i = 0; i < count; ++i) {
559 SkPoint* cubic = chopped + 3*i;
560 convert_noninflect_cubic_to_quads(cubic, tolSqd, constrainWithinTangents, dir, quads);
561 }
562
563 }
564
565 ////////////////////////////////////////////////////////////////////////////////
566
567 // Solves linear system to extract klm
568 // P.K = k (similarly for l, m)
569 // Where P is matrix of control points
570 // K is coefficients for the line K
571 // k is vector of values of K evaluated at the control points
572 // 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])573 static void calc_cubic_klm(const SkPoint p[4], const SkScalar controlK[4],
574 const SkScalar controlL[4], const SkScalar controlM[4],
575 SkScalar k[3], SkScalar l[3], SkScalar m[3]) {
576 SkMatrix matrix;
577 matrix.setAll(p[0].fX, p[0].fY, 1.f,
578 p[1].fX, p[1].fY, 1.f,
579 p[2].fX, p[2].fY, 1.f);
580 SkMatrix inverse;
581 if (matrix.invert(&inverse)) {
582 inverse.mapHomogeneousPoints(k, controlK, 1);
583 inverse.mapHomogeneousPoints(l, controlL, 1);
584 inverse.mapHomogeneousPoints(m, controlM, 1);
585 }
586
587 }
588
set_serp_klm(const SkScalar d[3],SkScalar k[4],SkScalar l[4],SkScalar m[4])589 static void set_serp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
590 SkScalar tempSqrt = SkScalarSqrt(9.f * d[1] * d[1] - 12.f * d[0] * d[2]);
591 SkScalar ls = 3.f * d[1] - tempSqrt;
592 SkScalar lt = 6.f * d[0];
593 SkScalar ms = 3.f * d[1] + tempSqrt;
594 SkScalar mt = 6.f * d[0];
595
596 k[0] = ls * ms;
597 k[1] = (3.f * ls * ms - ls * mt - lt * ms) / 3.f;
598 k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f;
599 k[3] = (lt - ls) * (mt - ms);
600
601 l[0] = ls * ls * ls;
602 const SkScalar lt_ls = lt - ls;
603 l[1] = ls * ls * lt_ls * -1.f;
604 l[2] = lt_ls * lt_ls * ls;
605 l[3] = -1.f * lt_ls * lt_ls * lt_ls;
606
607 m[0] = ms * ms * ms;
608 const SkScalar mt_ms = mt - ms;
609 m[1] = ms * ms * mt_ms * -1.f;
610 m[2] = mt_ms * mt_ms * ms;
611 m[3] = -1.f * mt_ms * mt_ms * mt_ms;
612
613 // If d0 < 0 we need to flip the orientation of our curve
614 // This is done by negating the k and l values
615 // We want negative distance values to be on the inside
616 if ( d[0] > 0) {
617 for (int i = 0; i < 4; ++i) {
618 k[i] = -k[i];
619 l[i] = -l[i];
620 }
621 }
622 }
623
set_loop_klm(const SkScalar d[3],SkScalar k[4],SkScalar l[4],SkScalar m[4])624 static void set_loop_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
625 SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
626 SkScalar ls = d[1] - tempSqrt;
627 SkScalar lt = 2.f * d[0];
628 SkScalar ms = d[1] + tempSqrt;
629 SkScalar mt = 2.f * d[0];
630
631 k[0] = ls * ms;
632 k[1] = (3.f * ls*ms - ls * mt - lt * ms) / 3.f;
633 k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f;
634 k[3] = (lt - ls) * (mt - ms);
635
636 l[0] = ls * ls * ms;
637 l[1] = (ls * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/-3.f;
638 l[2] = ((lt - ls) * (ls * (2.f * mt - 3.f * ms) + lt * ms))/3.f;
639 l[3] = -1.f * (lt - ls) * (lt - ls) * (mt - ms);
640
641 m[0] = ls * ms * ms;
642 m[1] = (ms * (ls * (2.f * mt - 3.f * ms) + lt * ms))/-3.f;
643 m[2] = ((mt - ms) * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/3.f;
644 m[3] = -1.f * (lt - ls) * (mt - ms) * (mt - ms);
645
646
647 // If (d0 < 0 && sign(k1) > 0) || (d0 > 0 && sign(k1) < 0),
648 // we need to flip the orientation of our curve.
649 // This is done by negating the k and l values
650 if ( (d[0] < 0 && k[1] > 0) || (d[0] > 0 && k[1] < 0)) {
651 for (int i = 0; i < 4; ++i) {
652 k[i] = -k[i];
653 l[i] = -l[i];
654 }
655 }
656 }
657
set_cusp_klm(const SkScalar d[3],SkScalar k[4],SkScalar l[4],SkScalar m[4])658 static void set_cusp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
659 const SkScalar ls = d[2];
660 const SkScalar lt = 3.f * d[1];
661
662 k[0] = ls;
663 k[1] = ls - lt / 3.f;
664 k[2] = ls - 2.f * lt / 3.f;
665 k[3] = ls - lt;
666
667 l[0] = ls * ls * ls;
668 const SkScalar ls_lt = ls - lt;
669 l[1] = ls * ls * ls_lt;
670 l[2] = ls_lt * ls_lt * ls;
671 l[3] = ls_lt * ls_lt * ls_lt;
672
673 m[0] = 1.f;
674 m[1] = 1.f;
675 m[2] = 1.f;
676 m[3] = 1.f;
677 }
678
679 // For the case when a cubic is actually a quadratic
680 // M =
681 // 0 0 0
682 // 1/3 0 1/3
683 // 2/3 1/3 2/3
684 // 1 1 1
set_quadratic_klm(const SkScalar d[3],SkScalar k[4],SkScalar l[4],SkScalar m[4])685 static void set_quadratic_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
686 k[0] = 0.f;
687 k[1] = 1.f/3.f;
688 k[2] = 2.f/3.f;
689 k[3] = 1.f;
690
691 l[0] = 0.f;
692 l[1] = 0.f;
693 l[2] = 1.f/3.f;
694 l[3] = 1.f;
695
696 m[0] = 0.f;
697 m[1] = 1.f/3.f;
698 m[2] = 2.f/3.f;
699 m[3] = 1.f;
700
701 // If d2 < 0 we need to flip the orientation of our curve
702 // This is done by negating the k and l values
703 if ( d[2] > 0) {
704 for (int i = 0; i < 4; ++i) {
705 k[i] = -k[i];
706 l[i] = -l[i];
707 }
708 }
709 }
710
chopCubicAtLoopIntersection(const SkPoint src[4],SkPoint dst[10],SkScalar klm[9],SkScalar klm_rev[3])711 int GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkScalar klm[9],
712 SkScalar klm_rev[3]) {
713 // Variable to store the two parametric values at the loop double point
714 SkScalar smallS = 0.f;
715 SkScalar largeS = 0.f;
716
717 SkScalar d[3];
718 SkCubicType cType = SkClassifyCubic(src, d);
719
720 int chop_count = 0;
721 if (kLoop_SkCubicType == cType) {
722 SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
723 SkScalar ls = d[1] - tempSqrt;
724 SkScalar lt = 2.f * d[0];
725 SkScalar ms = d[1] + tempSqrt;
726 SkScalar mt = 2.f * d[0];
727 ls = ls / lt;
728 ms = ms / mt;
729 // need to have t values sorted since this is what is expected by SkChopCubicAt
730 if (ls <= ms) {
731 smallS = ls;
732 largeS = ms;
733 } else {
734 smallS = ms;
735 largeS = ls;
736 }
737
738 SkScalar chop_ts[2];
739 if (smallS > 0.f && smallS < 1.f) {
740 chop_ts[chop_count++] = smallS;
741 }
742 if (largeS > 0.f && largeS < 1.f) {
743 chop_ts[chop_count++] = largeS;
744 }
745 if(dst) {
746 SkChopCubicAt(src, dst, chop_ts, chop_count);
747 }
748 } else {
749 if (dst) {
750 memcpy(dst, src, sizeof(SkPoint) * 4);
751 }
752 }
753
754 if (klm && klm_rev) {
755 // Set klm_rev to to match the sub_section of cubic that needs to have its orientation
756 // flipped. This will always be the section that is the "loop"
757 if (2 == chop_count) {
758 klm_rev[0] = 1.f;
759 klm_rev[1] = -1.f;
760 klm_rev[2] = 1.f;
761 } else if (1 == chop_count) {
762 if (smallS < 0.f) {
763 klm_rev[0] = -1.f;
764 klm_rev[1] = 1.f;
765 } else {
766 klm_rev[0] = 1.f;
767 klm_rev[1] = -1.f;
768 }
769 } else {
770 if (smallS < 0.f && largeS > 1.f) {
771 klm_rev[0] = -1.f;
772 } else {
773 klm_rev[0] = 1.f;
774 }
775 }
776 SkScalar controlK[4];
777 SkScalar controlL[4];
778 SkScalar controlM[4];
779
780 if (kSerpentine_SkCubicType == cType || (kCusp_SkCubicType == cType && 0.f != d[0])) {
781 set_serp_klm(d, controlK, controlL, controlM);
782 } else if (kLoop_SkCubicType == cType) {
783 set_loop_klm(d, controlK, controlL, controlM);
784 } else if (kCusp_SkCubicType == cType) {
785 SkASSERT(0.f == d[0]);
786 set_cusp_klm(d, controlK, controlL, controlM);
787 } else if (kQuadratic_SkCubicType == cType) {
788 set_quadratic_klm(d, controlK, controlL, controlM);
789 }
790
791 calc_cubic_klm(src, controlK, controlL, controlM, klm, &klm[3], &klm[6]);
792 }
793 return chop_count + 1;
794 }
795
getCubicKLM(const SkPoint p[4],SkScalar klm[9])796 void GrPathUtils::getCubicKLM(const SkPoint p[4], SkScalar klm[9]) {
797 SkScalar d[3];
798 SkCubicType cType = SkClassifyCubic(p, d);
799
800 SkScalar controlK[4];
801 SkScalar controlL[4];
802 SkScalar controlM[4];
803
804 if (kSerpentine_SkCubicType == cType || (kCusp_SkCubicType == cType && 0.f != d[0])) {
805 set_serp_klm(d, controlK, controlL, controlM);
806 } else if (kLoop_SkCubicType == cType) {
807 set_loop_klm(d, controlK, controlL, controlM);
808 } else if (kCusp_SkCubicType == cType) {
809 SkASSERT(0.f == d[0]);
810 set_cusp_klm(d, controlK, controlL, controlM);
811 } else if (kQuadratic_SkCubicType == cType) {
812 set_quadratic_klm(d, controlK, controlL, controlM);
813 }
814
815 calc_cubic_klm(p, controlK, controlL, controlM, klm, &klm[3], &klm[6]);
816 }
817