Line data Source code
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 : #include "SkMathPriv.h"
13 :
14 0 : SkScalar GrPathUtils::scaleToleranceToSrc(SkScalar devTol,
15 : const SkMatrix& viewM,
16 : const SkRect& pathBounds) {
17 : // In order to tesselate the path we get a bound on how much the matrix can
18 : // scale when mapping to screen coordinates.
19 0 : SkScalar stretch = viewM.getMaxScale();
20 0 : SkScalar srcTol = devTol;
21 :
22 0 : if (stretch < 0) {
23 : // take worst case mapRadius amoung four corners.
24 : // (less than perfect)
25 0 : for (int i = 0; i < 4; ++i) {
26 : SkMatrix mat;
27 0 : mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight,
28 0 : (i < 2) ? pathBounds.fTop : pathBounds.fBottom);
29 0 : mat.postConcat(viewM);
30 0 : stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1));
31 : }
32 : }
33 0 : return srcTol / stretch;
34 : }
35 :
36 : static const int MAX_POINTS_PER_CURVE = 1 << 10;
37 : static const SkScalar gMinCurveTol = 0.0001f;
38 :
39 0 : uint32_t GrPathUtils::quadraticPointCount(const SkPoint points[], SkScalar tol) {
40 0 : if (tol < gMinCurveTol) {
41 0 : tol = gMinCurveTol;
42 : }
43 0 : SkASSERT(tol > 0);
44 :
45 0 : SkScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
46 0 : if (!SkScalarIsFinite(d)) {
47 0 : return MAX_POINTS_PER_CURVE;
48 0 : } else if (d <= tol) {
49 0 : 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 0 : SkScalar divSqrt = SkScalarSqrt(d / tol);
56 0 : if (((SkScalar)SK_MaxS32) <= divSqrt) {
57 0 : return MAX_POINTS_PER_CURVE;
58 : } else {
59 0 : int temp = SkScalarCeilToInt(divSqrt);
60 0 : int pow2 = GrNextPow2(temp);
61 : // Because of NaNs & INFs we can wind up with a degenerate temp
62 : // such that pow2 comes out negative. Also, our point generator
63 : // will always output at least one pt.
64 0 : if (pow2 < 1) {
65 0 : pow2 = 1;
66 : }
67 0 : return SkTMin(pow2, MAX_POINTS_PER_CURVE);
68 : }
69 : }
70 : }
71 :
72 0 : uint32_t GrPathUtils::generateQuadraticPoints(const SkPoint& p0,
73 : const SkPoint& p1,
74 : const SkPoint& p2,
75 : SkScalar tolSqd,
76 : SkPoint** points,
77 : uint32_t pointsLeft) {
78 0 : if (pointsLeft < 2 ||
79 0 : (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) {
80 0 : (*points)[0] = p2;
81 0 : *points += 1;
82 0 : return 1;
83 : }
84 :
85 : SkPoint q[] = {
86 0 : { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
87 0 : { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
88 0 : };
89 0 : SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) };
90 :
91 0 : pointsLeft >>= 1;
92 0 : uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft);
93 0 : uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft);
94 0 : return a + b;
95 : }
96 :
97 0 : uint32_t GrPathUtils::cubicPointCount(const SkPoint points[],
98 : SkScalar tol) {
99 0 : if (tol < gMinCurveTol) {
100 0 : tol = gMinCurveTol;
101 : }
102 0 : SkASSERT(tol > 0);
103 :
104 : SkScalar d = SkTMax(
105 0 : points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]),
106 0 : points[2].distanceToLineSegmentBetweenSqd(points[0], points[3]));
107 0 : d = SkScalarSqrt(d);
108 0 : if (!SkScalarIsFinite(d)) {
109 0 : return MAX_POINTS_PER_CURVE;
110 0 : } else if (d <= tol) {
111 0 : return 1;
112 : } else {
113 0 : SkScalar divSqrt = SkScalarSqrt(d / tol);
114 0 : if (((SkScalar)SK_MaxS32) <= divSqrt) {
115 0 : return MAX_POINTS_PER_CURVE;
116 : } else {
117 0 : int temp = SkScalarCeilToInt(SkScalarSqrt(d / tol));
118 0 : int pow2 = GrNextPow2(temp);
119 : // Because of NaNs & INFs we can wind up with a degenerate temp
120 : // such that pow2 comes out negative. Also, our point generator
121 : // will always output at least one pt.
122 0 : if (pow2 < 1) {
123 0 : pow2 = 1;
124 : }
125 0 : return SkTMin(pow2, MAX_POINTS_PER_CURVE);
126 : }
127 : }
128 : }
129 :
130 0 : uint32_t GrPathUtils::generateCubicPoints(const SkPoint& p0,
131 : const SkPoint& p1,
132 : const SkPoint& p2,
133 : const SkPoint& p3,
134 : SkScalar tolSqd,
135 : SkPoint** points,
136 : uint32_t pointsLeft) {
137 0 : if (pointsLeft < 2 ||
138 0 : (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd &&
139 0 : p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) {
140 0 : (*points)[0] = p3;
141 0 : *points += 1;
142 0 : return 1;
143 : }
144 : SkPoint q[] = {
145 0 : { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
146 0 : { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
147 0 : { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
148 0 : };
149 : SkPoint r[] = {
150 0 : { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
151 0 : { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
152 0 : };
153 0 : SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) };
154 0 : pointsLeft >>= 1;
155 0 : uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft);
156 0 : uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft);
157 0 : return a + b;
158 : }
159 :
160 0 : int GrPathUtils::worstCasePointCount(const SkPath& path, int* subpaths, SkScalar tol) {
161 0 : if (tol < gMinCurveTol) {
162 0 : tol = gMinCurveTol;
163 : }
164 0 : SkASSERT(tol > 0);
165 :
166 0 : int pointCount = 0;
167 0 : *subpaths = 1;
168 :
169 0 : bool first = true;
170 :
171 0 : SkPath::Iter iter(path, false);
172 : SkPath::Verb verb;
173 :
174 : SkPoint pts[4];
175 0 : while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
176 :
177 0 : switch (verb) {
178 : case SkPath::kLine_Verb:
179 0 : pointCount += 1;
180 0 : break;
181 : case SkPath::kConic_Verb: {
182 0 : SkScalar weight = iter.conicWeight();
183 0 : SkAutoConicToQuads converter;
184 0 : const SkPoint* quadPts = converter.computeQuads(pts, weight, tol);
185 0 : for (int i = 0; i < converter.countQuads(); ++i) {
186 0 : pointCount += quadraticPointCount(quadPts + 2*i, tol);
187 : }
188 : }
189 : case SkPath::kQuad_Verb:
190 0 : pointCount += quadraticPointCount(pts, tol);
191 0 : break;
192 : case SkPath::kCubic_Verb:
193 0 : pointCount += cubicPointCount(pts, tol);
194 0 : break;
195 : case SkPath::kMove_Verb:
196 0 : pointCount += 1;
197 0 : if (!first) {
198 0 : ++(*subpaths);
199 : }
200 0 : break;
201 : default:
202 0 : break;
203 : }
204 0 : first = false;
205 : }
206 0 : return pointCount;
207 : }
208 :
209 0 : void GrPathUtils::QuadUVMatrix::set(const SkPoint qPts[3]) {
210 : SkMatrix m;
211 : // We want M such that M * xy_pt = uv_pt
212 : // We know M * control_pts = [0 1/2 1]
213 : // [0 0 1]
214 : // [1 1 1]
215 : // And control_pts = [x0 x1 x2]
216 : // [y0 y1 y2]
217 : // [1 1 1 ]
218 : // We invert the control pt matrix and post concat to both sides to get M.
219 : // Using the known form of the control point matrix and the result, we can
220 : // optimize and improve precision.
221 :
222 0 : double x0 = qPts[0].fX;
223 0 : double y0 = qPts[0].fY;
224 0 : double x1 = qPts[1].fX;
225 0 : double y1 = qPts[1].fY;
226 0 : double x2 = qPts[2].fX;
227 0 : double y2 = qPts[2].fY;
228 0 : double det = x0*y1 - y0*x1 + x2*y0 - y2*x0 + x1*y2 - y1*x2;
229 :
230 0 : if (!sk_float_isfinite(det)
231 0 : || SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero)) {
232 : // The quad is degenerate. Hopefully this is rare. Find the pts that are
233 : // farthest apart to compute a line (unless it is really a pt).
234 0 : SkScalar maxD = qPts[0].distanceToSqd(qPts[1]);
235 0 : int maxEdge = 0;
236 0 : SkScalar d = qPts[1].distanceToSqd(qPts[2]);
237 0 : if (d > maxD) {
238 0 : maxD = d;
239 0 : maxEdge = 1;
240 : }
241 0 : d = qPts[2].distanceToSqd(qPts[0]);
242 0 : if (d > maxD) {
243 0 : maxD = d;
244 0 : maxEdge = 2;
245 : }
246 : // We could have a tolerance here, not sure if it would improve anything
247 0 : if (maxD > 0) {
248 : // Set the matrix to give (u = 0, v = distance_to_line)
249 0 : SkVector lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge];
250 : // when looking from the point 0 down the line we want positive
251 : // distances to be to the left. This matches the non-degenerate
252 : // case.
253 0 : lineVec.setOrthog(lineVec, SkPoint::kLeft_Side);
254 : // first row
255 0 : fM[0] = 0;
256 0 : fM[1] = 0;
257 0 : fM[2] = 0;
258 : // second row
259 0 : fM[3] = lineVec.fX;
260 0 : fM[4] = lineVec.fY;
261 0 : fM[5] = -lineVec.dot(qPts[maxEdge]);
262 : } else {
263 : // It's a point. It should cover zero area. Just set the matrix such
264 : // that (u, v) will always be far away from the quad.
265 0 : fM[0] = 0; fM[1] = 0; fM[2] = 100.f;
266 0 : fM[3] = 0; fM[4] = 0; fM[5] = 100.f;
267 : }
268 : } else {
269 0 : double scale = 1.0/det;
270 :
271 : // compute adjugate matrix
272 : double a2, a3, a4, a5, a6, a7, a8;
273 0 : a2 = x1*y2-x2*y1;
274 :
275 0 : a3 = y2-y0;
276 0 : a4 = x0-x2;
277 0 : a5 = x2*y0-x0*y2;
278 :
279 0 : a6 = y0-y1;
280 0 : a7 = x1-x0;
281 0 : 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 0 : m[SkMatrix::kMScaleX] = (float)((0.5*a3 + a6)*scale);
286 0 : m[SkMatrix::kMSkewX] = (float)((0.5*a4 + a7)*scale);
287 0 : m[SkMatrix::kMTransX] = (float)((0.5*a5 + a8)*scale);
288 :
289 0 : m[SkMatrix::kMSkewY] = (float)(a6*scale);
290 0 : m[SkMatrix::kMScaleY] = (float)(a7*scale);
291 0 : m[SkMatrix::kMTransY] = (float)(a8*scale);
292 :
293 : // kMPersp0 & kMPersp1 should algebraically be zero
294 0 : m[SkMatrix::kMPersp0] = 0.0f;
295 0 : m[SkMatrix::kMPersp1] = 0.0f;
296 0 : m[SkMatrix::kMPersp2] = (float)((a2 + a5 + a8)*scale);
297 :
298 : // It may not be normalized to have 1.0 in the bottom right
299 0 : float m33 = m.get(SkMatrix::kMPersp2);
300 0 : if (1.f != m33) {
301 0 : m33 = 1.f / m33;
302 0 : fM[0] = m33 * m.get(SkMatrix::kMScaleX);
303 0 : fM[1] = m33 * m.get(SkMatrix::kMSkewX);
304 0 : fM[2] = m33 * m.get(SkMatrix::kMTransX);
305 0 : fM[3] = m33 * m.get(SkMatrix::kMSkewY);
306 0 : fM[4] = m33 * m.get(SkMatrix::kMScaleY);
307 0 : fM[5] = m33 * m.get(SkMatrix::kMTransY);
308 : } else {
309 0 : fM[0] = m.get(SkMatrix::kMScaleX);
310 0 : fM[1] = m.get(SkMatrix::kMSkewX);
311 0 : fM[2] = m.get(SkMatrix::kMTransX);
312 0 : fM[3] = m.get(SkMatrix::kMSkewY);
313 0 : fM[4] = m.get(SkMatrix::kMScaleY);
314 0 : fM[5] = m.get(SkMatrix::kMTransY);
315 : }
316 : }
317 0 : }
318 :
319 : ////////////////////////////////////////////////////////////////////////////////
320 :
321 : // k = (y2 - y0, x0 - x2, x2*y0 - x0*y2)
322 : // l = (y1 - y0, x0 - x1, x1*y0 - x0*y1) * 2*w
323 : // m = (y2 - y1, x1 - x2, x2*y1 - x1*y2) * 2*w
324 0 : void GrPathUtils::getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* out) {
325 0 : SkMatrix& klm = *out;
326 0 : const SkScalar w2 = 2.f * weight;
327 0 : klm[0] = p[2].fY - p[0].fY;
328 0 : klm[1] = p[0].fX - p[2].fX;
329 0 : klm[2] = p[2].fX * p[0].fY - p[0].fX * p[2].fY;
330 :
331 0 : klm[3] = w2 * (p[1].fY - p[0].fY);
332 0 : klm[4] = w2 * (p[0].fX - p[1].fX);
333 0 : klm[5] = w2 * (p[1].fX * p[0].fY - p[0].fX * p[1].fY);
334 :
335 0 : klm[6] = w2 * (p[2].fY - p[1].fY);
336 0 : klm[7] = w2 * (p[1].fX - p[2].fX);
337 0 : klm[8] = w2 * (p[2].fX * p[1].fY - p[1].fX * p[2].fY);
338 :
339 : // scale the max absolute value of coeffs to 10
340 0 : SkScalar scale = 0.f;
341 0 : for (int i = 0; i < 9; ++i) {
342 0 : scale = SkMaxScalar(scale, SkScalarAbs(klm[i]));
343 : }
344 0 : SkASSERT(scale > 0.f);
345 0 : scale = 10.f / scale;
346 0 : for (int i = 0; i < 9; ++i) {
347 0 : klm[i] *= scale;
348 : }
349 0 : }
350 :
351 : ////////////////////////////////////////////////////////////////////////////////
352 :
353 : namespace {
354 :
355 : // a is the first control point of the cubic.
356 : // ab is the vector from a to the second control point.
357 : // dc is the vector from the fourth to the third control point.
358 : // d is the fourth control point.
359 : // p is the candidate quadratic control point.
360 : // this assumes that the cubic doesn't inflect and is simple
361 0 : bool is_point_within_cubic_tangents(const SkPoint& a,
362 : const SkVector& ab,
363 : const SkVector& dc,
364 : const SkPoint& d,
365 : SkPathPriv::FirstDirection dir,
366 : const SkPoint p) {
367 0 : SkVector ap = p - a;
368 0 : SkScalar apXab = ap.cross(ab);
369 0 : if (SkPathPriv::kCW_FirstDirection == dir) {
370 0 : if (apXab > 0) {
371 0 : return false;
372 : }
373 : } else {
374 0 : SkASSERT(SkPathPriv::kCCW_FirstDirection == dir);
375 0 : if (apXab < 0) {
376 0 : return false;
377 : }
378 : }
379 :
380 0 : SkVector dp = p - d;
381 0 : SkScalar dpXdc = dp.cross(dc);
382 0 : if (SkPathPriv::kCW_FirstDirection == dir) {
383 0 : if (dpXdc < 0) {
384 0 : return false;
385 : }
386 : } else {
387 0 : SkASSERT(SkPathPriv::kCCW_FirstDirection == dir);
388 0 : if (dpXdc > 0) {
389 0 : return false;
390 : }
391 : }
392 0 : return true;
393 : }
394 :
395 0 : void convert_noninflect_cubic_to_quads(const SkPoint p[4],
396 : SkScalar toleranceSqd,
397 : bool constrainWithinTangents,
398 : SkPathPriv::FirstDirection dir,
399 : SkTArray<SkPoint, true>* quads,
400 : int sublevel = 0) {
401 :
402 : // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is
403 : // 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].
404 :
405 0 : SkVector ab = p[1] - p[0];
406 0 : SkVector dc = p[2] - p[3];
407 :
408 0 : if (ab.lengthSqd() < SK_ScalarNearlyZero) {
409 0 : if (dc.lengthSqd() < SK_ScalarNearlyZero) {
410 0 : SkPoint* degQuad = quads->push_back_n(3);
411 0 : degQuad[0] = p[0];
412 0 : degQuad[1] = p[0];
413 0 : degQuad[2] = p[3];
414 0 : return;
415 : }
416 0 : ab = p[2] - p[0];
417 : }
418 0 : if (dc.lengthSqd() < SK_ScalarNearlyZero) {
419 0 : dc = p[1] - p[3];
420 : }
421 :
422 : // When the ab and cd tangents are degenerate or nearly parallel with vector from d to a the
423 : // constraint that the quad point falls between the tangents becomes hard to enforce and we are
424 : // likely to hit the max subdivision count. However, in this case the cubic is approaching a
425 : // line and the accuracy of the quad point isn't so important. We check if the two middle cubic
426 : // control points are very close to the baseline vector. If so then we just pick quadratic
427 : // points on the control polygon.
428 :
429 0 : if (constrainWithinTangents) {
430 0 : SkVector da = p[0] - p[3];
431 0 : bool doQuads = dc.lengthSqd() < SK_ScalarNearlyZero ||
432 0 : ab.lengthSqd() < SK_ScalarNearlyZero;
433 0 : if (!doQuads) {
434 0 : SkScalar invDALengthSqd = da.lengthSqd();
435 0 : if (invDALengthSqd > SK_ScalarNearlyZero) {
436 0 : invDALengthSqd = SkScalarInvert(invDALengthSqd);
437 : // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a.
438 : // same goes for point c using vector cd.
439 0 : SkScalar detABSqd = ab.cross(da);
440 0 : detABSqd = SkScalarSquare(detABSqd);
441 0 : SkScalar detDCSqd = dc.cross(da);
442 0 : detDCSqd = SkScalarSquare(detDCSqd);
443 0 : if (detABSqd * invDALengthSqd < toleranceSqd &&
444 0 : detDCSqd * invDALengthSqd < toleranceSqd)
445 : {
446 0 : doQuads = true;
447 : }
448 : }
449 : }
450 0 : if (doQuads) {
451 0 : SkPoint b = p[0] + ab;
452 0 : SkPoint c = p[3] + dc;
453 0 : SkPoint mid = b + c;
454 0 : mid.scale(SK_ScalarHalf);
455 : // Insert two quadratics to cover the case when ab points away from d and/or dc
456 : // points away from a.
457 0 : if (SkVector::DotProduct(da, dc) < 0 || SkVector::DotProduct(ab,da) > 0) {
458 0 : SkPoint* qpts = quads->push_back_n(6);
459 0 : qpts[0] = p[0];
460 0 : qpts[1] = b;
461 0 : qpts[2] = mid;
462 0 : qpts[3] = mid;
463 0 : qpts[4] = c;
464 0 : qpts[5] = p[3];
465 : } else {
466 0 : SkPoint* qpts = quads->push_back_n(3);
467 0 : qpts[0] = p[0];
468 0 : qpts[1] = mid;
469 0 : qpts[2] = p[3];
470 : }
471 0 : return;
472 : }
473 : }
474 :
475 : static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
476 : static const int kMaxSubdivs = 10;
477 :
478 0 : ab.scale(kLengthScale);
479 0 : dc.scale(kLengthScale);
480 :
481 : // e0 and e1 are extrapolations along vectors ab and dc.
482 0 : SkVector c0 = p[0];
483 0 : c0 += ab;
484 0 : SkVector c1 = p[3];
485 0 : c1 += dc;
486 :
487 0 : SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : c0.distanceToSqd(c1);
488 0 : if (dSqd < toleranceSqd) {
489 0 : SkPoint cAvg = c0;
490 0 : cAvg += c1;
491 0 : cAvg.scale(SK_ScalarHalf);
492 :
493 0 : bool subdivide = false;
494 :
495 0 : if (constrainWithinTangents &&
496 0 : !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) {
497 : // choose a new cAvg that is the intersection of the two tangent lines.
498 0 : ab.setOrthog(ab);
499 0 : SkScalar z0 = -ab.dot(p[0]);
500 0 : dc.setOrthog(dc);
501 0 : SkScalar z1 = -dc.dot(p[3]);
502 0 : cAvg.fX = ab.fY * z1 - z0 * dc.fY;
503 0 : cAvg.fY = z0 * dc.fX - ab.fX * z1;
504 0 : SkScalar z = ab.fX * dc.fY - ab.fY * dc.fX;
505 0 : z = SkScalarInvert(z);
506 0 : cAvg.fX *= z;
507 0 : cAvg.fY *= z;
508 0 : if (sublevel <= kMaxSubdivs) {
509 0 : SkScalar d0Sqd = c0.distanceToSqd(cAvg);
510 0 : SkScalar d1Sqd = c1.distanceToSqd(cAvg);
511 : // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know
512 : // the distances and tolerance can't be negative.
513 : // (d0 + d1)^2 > toleranceSqd
514 : // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd
515 0 : SkScalar d0d1 = SkScalarSqrt(d0Sqd * d1Sqd);
516 0 : subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd;
517 : }
518 : }
519 0 : if (!subdivide) {
520 0 : SkPoint* pts = quads->push_back_n(3);
521 0 : pts[0] = p[0];
522 0 : pts[1] = cAvg;
523 0 : pts[2] = p[3];
524 0 : return;
525 : }
526 : }
527 : SkPoint choppedPts[7];
528 0 : SkChopCubicAtHalf(p, choppedPts);
529 0 : convert_noninflect_cubic_to_quads(choppedPts + 0,
530 : toleranceSqd,
531 : constrainWithinTangents,
532 : dir,
533 : quads,
534 0 : sublevel + 1);
535 0 : convert_noninflect_cubic_to_quads(choppedPts + 3,
536 : toleranceSqd,
537 : constrainWithinTangents,
538 : dir,
539 : quads,
540 0 : sublevel + 1);
541 : }
542 : }
543 :
544 0 : void GrPathUtils::convertCubicToQuads(const SkPoint p[4],
545 : SkScalar tolScale,
546 : SkTArray<SkPoint, true>* quads) {
547 : SkPoint chopped[10];
548 0 : int count = SkChopCubicAtInflections(p, chopped);
549 :
550 0 : const SkScalar tolSqd = SkScalarSquare(tolScale);
551 :
552 0 : for (int i = 0; i < count; ++i) {
553 0 : SkPoint* cubic = chopped + 3*i;
554 : // The direction param is ignored if the third param is false.
555 : convert_noninflect_cubic_to_quads(cubic, tolSqd, false,
556 0 : SkPathPriv::kCCW_FirstDirection, quads);
557 : }
558 0 : }
559 :
560 0 : void GrPathUtils::convertCubicToQuadsConstrainToTangents(const SkPoint p[4],
561 : SkScalar tolScale,
562 : SkPathPriv::FirstDirection dir,
563 : SkTArray<SkPoint, true>* quads) {
564 : SkPoint chopped[10];
565 0 : int count = SkChopCubicAtInflections(p, chopped);
566 :
567 0 : const SkScalar tolSqd = SkScalarSquare(tolScale);
568 :
569 0 : for (int i = 0; i < count; ++i) {
570 0 : SkPoint* cubic = chopped + 3*i;
571 0 : convert_noninflect_cubic_to_quads(cubic, tolSqd, true, dir, quads);
572 : }
573 0 : }
574 :
575 : ////////////////////////////////////////////////////////////////////////////////
576 :
577 : /**
578 : * Computes an SkMatrix that can find the cubic KLM functionals as follows:
579 : *
580 : * | ..K.. | | ..kcoeffs.. |
581 : * | ..L.. | = | ..lcoeffs.. | * inverse_transpose_power_basis_matrix
582 : * | ..M.. | | ..mcoeffs.. |
583 : *
584 : * 'kcoeffs' are the power basis coefficients to a scalar valued cubic function that returns the
585 : * signed distance to line K from a given point on the curve:
586 : *
587 : * k(t,s) = C(t,s) * K [C(t,s) is defined in the following comment]
588 : *
589 : * The same applies for lcoeffs and mcoeffs. These are found separately, depending on the type of
590 : * curve. There are 4 coefficients but 3 rows in the matrix, so in order to do this calculation the
591 : * caller must first remove a specific column of coefficients.
592 : *
593 : * @return which column of klm coefficients to exclude from the calculation.
594 : */
595 0 : static int calc_inverse_transpose_power_basis_matrix(const SkPoint pts[4], SkMatrix* out) {
596 : using SkScalar4 = SkNx<4, SkScalar>;
597 :
598 : // First we convert the bezier coordinates 'pts' to power basis coefficients X,Y,W=[0 0 0 1].
599 : // M3 is the matrix that does this conversion. The homogeneous equation for the cubic becomes:
600 : //
601 : // | X Y 0 |
602 : // C(t,s) = [t^3 t^2*s t*s^2 s^3] * | . . 0 |
603 : // | . . 0 |
604 : // | . . 1 |
605 : //
606 : const SkScalar4 M3[3] = {SkScalar4(-1, 3, -3, 1),
607 : SkScalar4(3, -6, 3, 0),
608 0 : SkScalar4(-3, 3, 0, 0)};
609 : // 4th column of M3 = SkScalar4(1, 0, 0, 0)};
610 0 : SkScalar4 X(pts[3].x(), 0, 0, 0);
611 0 : SkScalar4 Y(pts[3].y(), 0, 0, 0);
612 0 : for (int i = 2; i >= 0; --i) {
613 0 : X += M3[i] * pts[i].x();
614 0 : Y += M3[i] * pts[i].y();
615 : }
616 :
617 : // The matrix is 3x4. In order to invert it, we first need to make it square by throwing out one
618 : // of the top three rows. We toss the row that leaves us with the largest absolute determinant.
619 : // Since the right column will be [0 0 1], the determinant reduces to x0*y1 - y0*x1.
620 : SkScalar absDet[4];
621 0 : const SkScalar4 DETX1 = SkNx_shuffle<1,0,0,3>(X), DETY1 = SkNx_shuffle<1,0,0,3>(Y);
622 0 : const SkScalar4 DETX2 = SkNx_shuffle<2,2,1,3>(X), DETY2 = SkNx_shuffle<2,2,1,3>(Y);
623 0 : const SkScalar4 DET = DETX1 * DETY2 - DETY1 * DETX2;
624 0 : DET.abs().store(absDet);
625 0 : const int skipRow = absDet[0] > absDet[2] ? (absDet[0] > absDet[1] ? 0 : 1)
626 0 : : (absDet[1] > absDet[2] ? 1 : 2);
627 0 : const SkScalar rdet = 1 / DET[skipRow];
628 0 : const int row0 = (0 != skipRow) ? 0 : 1;
629 0 : const int row1 = (2 == skipRow) ? 1 : 2;
630 :
631 : // Compute the inverse-transpose of the power basis matrix with the 'skipRow'th row removed.
632 : // Since W=[0 0 0 1], it follows that our corresponding solution will be equal to:
633 : //
634 : // | y1 -x1 x1*y2 - y1*x2 |
635 : // 1/det * | -y0 x0 -x0*y2 + y0*x2 |
636 : // | 0 0 det |
637 : //
638 : const SkScalar4 R(rdet, rdet, rdet, 1);
639 : X *= R;
640 : Y *= R;
641 :
642 : SkScalar x[4], y[4], z[4];
643 : X.store(x);
644 : Y.store(y);
645 0 : (X * SkNx_shuffle<3,3,3,3>(Y) - Y * SkNx_shuffle<3,3,3,3>(X)).store(z);
646 :
647 0 : out->setAll( y[row1], -x[row1], z[row1],
648 0 : -y[row0], x[row0], -z[row0],
649 0 : 0, 0, 1);
650 :
651 0 : return skipRow;
652 : }
653 :
654 0 : static void negate_kl(SkMatrix* klm) {
655 : // We could use klm->postScale(-1, -1), but it ends up doing a full matrix multiply.
656 0 : for (int i = 0; i < 6; ++i) {
657 0 : (*klm)[i] = -(*klm)[i];
658 : }
659 0 : }
660 :
661 0 : static void calc_serp_klm(const SkPoint pts[4], const SkScalar d[3], SkMatrix* klm) {
662 : SkMatrix CIT;
663 0 : int skipCol = calc_inverse_transpose_power_basis_matrix(pts, &CIT);
664 :
665 0 : const SkScalar root = SkScalarSqrt(9 * d[1] * d[1] - 12 * d[0] * d[2]);
666 :
667 0 : const SkScalar tl = 3 * d[1] + root;
668 0 : const SkScalar sl = 6 * d[0];
669 0 : const SkScalar tm = 3 * d[1] - root;
670 0 : const SkScalar sm = 6 * d[0];
671 :
672 : SkMatrix klmCoeffs;
673 0 : int col = 0;
674 0 : if (0 != skipCol) {
675 0 : klmCoeffs[0] = 0;
676 0 : klmCoeffs[3] = -sl * sl * sl;
677 0 : klmCoeffs[6] = -sm * sm * sm;
678 0 : ++col;
679 : }
680 0 : if (1 != skipCol) {
681 0 : klmCoeffs[col + 0] = sl * sm;
682 0 : klmCoeffs[col + 3] = 3 * sl * sl * tl;
683 0 : klmCoeffs[col + 6] = 3 * sm * sm * tm;
684 0 : ++col;
685 : }
686 0 : if (2 != skipCol) {
687 0 : klmCoeffs[col + 0] = -tl * sm - tm * sl;
688 0 : klmCoeffs[col + 3] = -3 * sl * tl * tl;
689 0 : klmCoeffs[col + 6] = -3 * sm * tm * tm;
690 0 : ++col;
691 : }
692 :
693 0 : SkASSERT(2 == col);
694 0 : klmCoeffs[2] = tl * tm;
695 0 : klmCoeffs[5] = tl * tl * tl;
696 0 : klmCoeffs[8] = tm * tm * tm;
697 :
698 0 : klm->setConcat(klmCoeffs, CIT);
699 :
700 : // If d0 > 0 we need to flip the orientation of our curve
701 : // This is done by negating the k and l values
702 : // We want negative distance values to be on the inside
703 0 : if (d[0] > 0) {
704 0 : negate_kl(klm);
705 : }
706 0 : }
707 :
708 0 : static void calc_loop_klm(const SkPoint pts[4], SkScalar d1, SkScalar td, SkScalar sd,
709 : SkScalar te, SkScalar se, SkMatrix* klm) {
710 : SkMatrix CIT;
711 0 : int skipCol = calc_inverse_transpose_power_basis_matrix(pts, &CIT);
712 :
713 0 : const SkScalar tesd = te * sd;
714 0 : const SkScalar tdse = td * se;
715 :
716 : SkMatrix klmCoeffs;
717 0 : int col = 0;
718 0 : if (0 != skipCol) {
719 0 : klmCoeffs[0] = 0;
720 0 : klmCoeffs[3] = -sd * sd * se;
721 0 : klmCoeffs[6] = -se * se * sd;
722 0 : ++col;
723 : }
724 0 : if (1 != skipCol) {
725 0 : klmCoeffs[col + 0] = sd * se;
726 0 : klmCoeffs[col + 3] = sd * (2 * tdse + tesd);
727 0 : klmCoeffs[col + 6] = se * (2 * tesd + tdse);
728 0 : ++col;
729 : }
730 0 : if (2 != skipCol) {
731 0 : klmCoeffs[col + 0] = -tdse - tesd;
732 0 : klmCoeffs[col + 3] = -td * (tdse + 2 * tesd);
733 0 : klmCoeffs[col + 6] = -te * (tesd + 2 * tdse);
734 0 : ++col;
735 : }
736 :
737 0 : SkASSERT(2 == col);
738 0 : klmCoeffs[2] = td * te;
739 0 : klmCoeffs[5] = td * td * te;
740 0 : klmCoeffs[8] = te * te * td;
741 :
742 0 : klm->setConcat(klmCoeffs, CIT);
743 :
744 : // For the general loop curve, we flip the orientation in the same pattern as the serp case
745 : // above. Thus we only check d1. Technically we should check the value of the hessian as well
746 : // cause we care about the sign of d1*Hessian. However, the Hessian is always negative outside
747 : // the loop section and positive inside. We take care of the flipping for the loop sections
748 : // later on.
749 0 : if (d1 > 0) {
750 0 : negate_kl(klm);
751 : }
752 0 : }
753 :
754 : // For the case when we have a cusp at a parameter value of infinity (discr == 0, d1 == 0).
755 0 : static void calc_inf_cusp_klm(const SkPoint pts[4], SkScalar d2, SkScalar d3, SkMatrix* klm) {
756 : SkMatrix CIT;
757 0 : int skipCol = calc_inverse_transpose_power_basis_matrix(pts, &CIT);
758 :
759 0 : const SkScalar tn = d3;
760 0 : const SkScalar sn = 3 * d2;
761 :
762 : SkMatrix klmCoeffs;
763 0 : int col = 0;
764 0 : if (0 != skipCol) {
765 0 : klmCoeffs[0] = 0;
766 0 : klmCoeffs[3] = -sn * sn * sn;
767 0 : ++col;
768 : }
769 0 : if (1 != skipCol) {
770 0 : klmCoeffs[col + 0] = 0;
771 0 : klmCoeffs[col + 3] = 3 * sn * sn * tn;
772 0 : ++col;
773 : }
774 0 : if (2 != skipCol) {
775 0 : klmCoeffs[col + 0] = -sn;
776 0 : klmCoeffs[col + 3] = -3 * sn * tn * tn;
777 0 : ++col;
778 : }
779 :
780 0 : SkASSERT(2 == col);
781 0 : klmCoeffs[2] = tn;
782 0 : klmCoeffs[5] = tn * tn * tn;
783 :
784 0 : klmCoeffs[6] = 0;
785 0 : klmCoeffs[7] = 0;
786 0 : klmCoeffs[8] = 1;
787 :
788 0 : klm->setConcat(klmCoeffs, CIT);
789 0 : }
790 :
791 : // For the case when a cubic bezier is actually a quadratic. We duplicate k in l so that the
792 : // implicit becomes:
793 : //
794 : // k^3 - l*m == k^3 - l*k == k * (k^2 - l)
795 : //
796 : // In the quadratic case we can simply assign fixed values at each control point:
797 : //
798 : // | ..K.. | | pts[0] pts[1] pts[2] pts[3] | | 0 1/3 2/3 1 |
799 : // | ..L.. | * | . . . . | == | 0 0 1/3 1 |
800 : // | ..K.. | | 1 1 1 1 | | 0 1/3 2/3 1 |
801 : //
802 0 : static void calc_quadratic_klm(const SkPoint pts[4], SkScalar d3, SkMatrix* klm) {
803 : SkMatrix klmAtPts;
804 : klmAtPts.setAll(0, 1.f/3, 1,
805 : 0, 0, 1,
806 0 : 0, 1.f/3, 1);
807 :
808 : SkMatrix inversePts;
809 0 : inversePts.setAll(pts[0].x(), pts[1].x(), pts[3].x(),
810 : pts[0].y(), pts[1].y(), pts[3].y(),
811 0 : 1, 1, 1);
812 0 : SkAssertResult(inversePts.invert(&inversePts));
813 :
814 0 : klm->setConcat(klmAtPts, inversePts);
815 :
816 : // If d3 > 0 we need to flip the orientation of our curve
817 : // This is done by negating the k and l values
818 0 : if (d3 > 0) {
819 0 : negate_kl(klm);
820 : }
821 0 : }
822 :
823 : // For the case when a cubic bezier is actually a line. We set K=0, L=1, M=-line, which results in
824 : // the following implicit:
825 : //
826 : // k^3 - l*m == 0^3 - 1*(-line) == -(-line) == line
827 : //
828 0 : static void calc_line_klm(const SkPoint pts[4], SkMatrix* klm) {
829 0 : SkScalar ny = pts[0].x() - pts[3].x();
830 0 : SkScalar nx = pts[3].y() - pts[0].y();
831 0 : SkScalar k = nx * pts[0].x() + ny * pts[0].y();
832 0 : klm->setAll( 0, 0, 0,
833 : 0, 0, 1,
834 0 : -nx, -ny, k);
835 0 : }
836 :
837 0 : int GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkMatrix* klm,
838 : int* loopIndex) {
839 : // Variables to store the two parametric values at the loop double point.
840 0 : SkScalar t1 = 0, t2 = 0;
841 :
842 : // Homogeneous parametric values at the loop double point.
843 : SkScalar td, sd, te, se;
844 :
845 : SkScalar d[3];
846 0 : SkCubicType cType = SkClassifyCubic(src, d);
847 :
848 0 : int chop_count = 0;
849 0 : if (kLoop_SkCubicType == cType) {
850 0 : SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
851 0 : td = d[1] + tempSqrt;
852 0 : sd = 2.f * d[0];
853 0 : te = d[1] - tempSqrt;
854 0 : se = 2.f * d[0];
855 :
856 0 : t1 = td / sd;
857 0 : t2 = te / se;
858 : // need to have t values sorted since this is what is expected by SkChopCubicAt
859 0 : if (t1 > t2) {
860 0 : SkTSwap(t1, t2);
861 : }
862 :
863 : SkScalar chop_ts[2];
864 0 : if (t1 > 0.f && t1 < 1.f) {
865 0 : chop_ts[chop_count++] = t1;
866 : }
867 0 : if (t2 > 0.f && t2 < 1.f) {
868 0 : chop_ts[chop_count++] = t2;
869 : }
870 0 : if(dst) {
871 0 : SkChopCubicAt(src, dst, chop_ts, chop_count);
872 : }
873 : } else {
874 0 : if (dst) {
875 0 : memcpy(dst, src, sizeof(SkPoint) * 4);
876 : }
877 : }
878 :
879 0 : if (loopIndex) {
880 0 : if (2 == chop_count) {
881 0 : *loopIndex = 1;
882 0 : } else if (1 == chop_count) {
883 0 : if (t1 < 0.f) {
884 0 : *loopIndex = 0;
885 : } else {
886 0 : *loopIndex = 1;
887 : }
888 : } else {
889 0 : if (t1 < 0.f && t2 > 1.f) {
890 0 : *loopIndex = 0;
891 : } else {
892 0 : *loopIndex = -1;
893 : }
894 : }
895 : }
896 :
897 0 : if (klm) {
898 0 : switch (cType) {
899 : case kSerpentine_SkCubicType:
900 0 : calc_serp_klm(src, d, klm);
901 0 : break;
902 : case kLoop_SkCubicType:
903 0 : calc_loop_klm(src, d[0], td, sd, te, se, klm);
904 0 : break;
905 : case kCusp_SkCubicType:
906 0 : if (0 != d[0]) {
907 : // FIXME: SkClassifyCubic has a tolerance, but we need an exact classification
908 : // here to be sure we won't get a negative in the square root.
909 0 : calc_serp_klm(src, d, klm);
910 : } else {
911 0 : calc_inf_cusp_klm(src, d[1], d[2], klm);
912 : }
913 0 : break;
914 : case kQuadratic_SkCubicType:
915 0 : calc_quadratic_klm(src, d[2], klm);
916 0 : break;
917 : case kLine_SkCubicType:
918 : case kPoint_SkCubicType:
919 0 : calc_line_klm(src, klm);
920 0 : break;
921 : };
922 : }
923 0 : return chop_count + 1;
924 : }
|
