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 "src/gpu/ganesh/geometry/GrPathUtils.h"
9
10#include "include/gpu/GrTypes.h"
11#include "include/private/base/SkFloatingPoint.h"
12#include "src/base/SkMathPriv.h"
13#include "src/base/SkUtils.h"
14#include "src/core/SkPointPriv.h"
15#include "src/gpu/tessellate/WangsFormula.h"
16
17using namespace skia_private;
18
19static const SkScalar kMinCurveTol = 0.0001f;
20
21static float tolerance_to_wangs_precision(float srcTol) {
22 // You should have called scaleToleranceToSrc, which guarantees this
23 SkASSERT(srcTol >= kMinCurveTol);
24
25 // The GrPathUtil API defines tolerance as the max distance the linear segment can be from
26 // the real curve. Wang's formula guarantees the linear segments will be within 1/precision
27 // of the true curve, so precision = 1/srcTol
28 return 1.f / srcTol;
29}
30
31uint32_t max_bezier_vertices(uint32_t chopCount) {
32 static constexpr uint32_t kMaxChopsPerCurve = 10;
33 static_assert((1 << kMaxChopsPerCurve) == GrPathUtils::kMaxPointsPerCurve);
34 return 1 << std::min(a: chopCount, b: kMaxChopsPerCurve);
35}
36
37SkScalar GrPathUtils::scaleToleranceToSrc(SkScalar devTol,
38 const SkMatrix& viewM,
39 const SkRect& pathBounds) {
40 // In order to tesselate the path we get a bound on how much the matrix can
41 // scale when mapping to screen coordinates.
42 SkScalar stretch = viewM.getMaxScale();
43
44 if (stretch < 0) {
45 // take worst case mapRadius amoung four corners.
46 // (less than perfect)
47 for (int i = 0; i < 4; ++i) {
48 SkMatrix mat;
49 mat.setTranslate(dx: (i % 2) ? pathBounds.fLeft : pathBounds.fRight,
50 dy: (i < 2) ? pathBounds.fTop : pathBounds.fBottom);
51 mat.postConcat(other: viewM);
52 stretch = std::max(a: stretch, b: mat.mapRadius(SK_Scalar1));
53 }
54 }
55 SkScalar srcTol = 0;
56 if (stretch <= 0) {
57 // We have degenerate bounds or some degenerate matrix. Thus we set the tolerance to be the
58 // max of the path pathBounds width and height.
59 srcTol = std::max(a: pathBounds.width(), b: pathBounds.height());
60 } else {
61 srcTol = devTol / stretch;
62 }
63 if (srcTol < kMinCurveTol) {
64 srcTol = kMinCurveTol;
65 }
66 return srcTol;
67}
68
69uint32_t GrPathUtils::quadraticPointCount(const SkPoint points[], SkScalar tol) {
70 return max_bezier_vertices(chopCount: skgpu::wangs_formula::quadratic_log2(
71 precision: tolerance_to_wangs_precision(srcTol: tol), pts: points));
72}
73
74uint32_t GrPathUtils::generateQuadraticPoints(const SkPoint& p0,
75 const SkPoint& p1,
76 const SkPoint& p2,
77 SkScalar tolSqd,
78 SkPoint** points,
79 uint32_t pointsLeft) {
80 if (pointsLeft < 2 ||
81 (SkPointPriv::DistanceToLineSegmentBetweenSqd(pt: p1, a: p0, b: p2)) < tolSqd) {
82 (*points)[0] = p2;
83 *points += 1;
84 return 1;
85 }
86
87 SkPoint q[] = {
88 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
89 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
90 };
91 SkPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) };
92
93 pointsLeft >>= 1;
94 uint32_t a = generateQuadraticPoints(p0, p1: q[0], p2: r, tolSqd, points, pointsLeft);
95 uint32_t b = generateQuadraticPoints(p0: r, p1: q[1], p2, tolSqd, points, pointsLeft);
96 return a + b;
97}
98
99uint32_t GrPathUtils::cubicPointCount(const SkPoint points[], SkScalar tol) {
100 return max_bezier_vertices(chopCount: skgpu::wangs_formula::cubic_log2(
101 precision: tolerance_to_wangs_precision(srcTol: tol), pts: points));
102}
103
104uint32_t GrPathUtils::generateCubicPoints(const SkPoint& p0,
105 const SkPoint& p1,
106 const SkPoint& p2,
107 const SkPoint& p3,
108 SkScalar tolSqd,
109 SkPoint** points,
110 uint32_t pointsLeft) {
111 if (pointsLeft < 2 ||
112 (SkPointPriv::DistanceToLineSegmentBetweenSqd(pt: p1, a: p0, b: p3) < tolSqd &&
113 SkPointPriv::DistanceToLineSegmentBetweenSqd(pt: p2, a: p0, b: p3) < tolSqd)) {
114 (*points)[0] = p3;
115 *points += 1;
116 return 1;
117 }
118 SkPoint q[] = {
119 { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
120 { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
121 { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
122 };
123 SkPoint r[] = {
124 { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
125 { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
126 };
127 SkPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) };
128 pointsLeft >>= 1;
129 uint32_t a = generateCubicPoints(p0, p1: q[0], p2: r[0], p3: s, tolSqd, points, pointsLeft);
130 uint32_t b = generateCubicPoints(p0: s, p1: r[1], p2: q[2], p3, tolSqd, points, pointsLeft);
131 return a + b;
132}
133
134void GrPathUtils::QuadUVMatrix::set(const SkPoint qPts[3]) {
135 // We want M such that M * xy_pt = uv_pt
136 // We know M * control_pts = [0 1/2 1]
137 // [0 0 1]
138 // [1 1 1]
139 // And control_pts = [x0 x1 x2]
140 // [y0 y1 y2]
141 // [1 1 1 ]
142 // We invert the control pt matrix and post concat to both sides to get M.
143 // Using the known form of the control point matrix and the result, we can
144 // optimize and improve precision.
145
146 double x0 = qPts[0].fX;
147 double y0 = qPts[0].fY;
148 double x1 = qPts[1].fX;
149 double y1 = qPts[1].fY;
150 double x2 = qPts[2].fX;
151 double y2 = qPts[2].fY;
152
153 // pre-calculate some adjugate matrix factors for determinant
154 double a2 = x1*y2-x2*y1;
155 double a5 = x2*y0-x0*y2;
156 double a8 = x0*y1-x1*y0;
157 double det = a2 + a5 + a8;
158
159 if (!sk_float_isfinite(x: det)
160 || SkScalarNearlyZero(x: (float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero)) {
161 // The quad is degenerate. Hopefully this is rare. Find the pts that are
162 // farthest apart to compute a line (unless it is really a pt).
163 SkScalar maxD = SkPointPriv::DistanceToSqd(pt: qPts[0], a: qPts[1]);
164 int maxEdge = 0;
165 SkScalar d = SkPointPriv::DistanceToSqd(pt: qPts[1], a: qPts[2]);
166 if (d > maxD) {
167 maxD = d;
168 maxEdge = 1;
169 }
170 d = SkPointPriv::DistanceToSqd(pt: qPts[2], a: qPts[0]);
171 if (d > maxD) {
172 maxD = d;
173 maxEdge = 2;
174 }
175 // We could have a tolerance here, not sure if it would improve anything
176 if (maxD > 0) {
177 // Set the matrix to give (u = 0, v = distance_to_line)
178 SkVector lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge];
179 // when looking from the point 0 down the line we want positive
180 // distances to be to the left. This matches the non-degenerate
181 // case.
182 lineVec = SkPointPriv::MakeOrthog(vec: lineVec, side: SkPointPriv::kLeft_Side);
183 // first row
184 fM[0] = 0;
185 fM[1] = 0;
186 fM[2] = 0;
187 // second row
188 fM[3] = lineVec.fX;
189 fM[4] = lineVec.fY;
190 fM[5] = -lineVec.dot(vec: qPts[maxEdge]);
191 } else {
192 // It's a point. It should cover zero area. Just set the matrix such
193 // that (u, v) will always be far away from the quad.
194 fM[0] = 0; fM[1] = 0; fM[2] = 100.f;
195 fM[3] = 0; fM[4] = 0; fM[5] = 100.f;
196 }
197 } else {
198 double scale = 1.0/det;
199
200 // compute adjugate matrix
201 double a3, a4, a6, a7;
202 a3 = y2-y0;
203 a4 = x0-x2;
204
205 a6 = y0-y1;
206 a7 = x1-x0;
207
208 // this performs the uv_pts*adjugate(control_pts) multiply,
209 // then does the scale by 1/det afterwards to improve precision
210 fM[0] = (float)((0.5*a3 + a6)*scale);
211 fM[1] = (float)((0.5*a4 + a7)*scale);
212 fM[2] = (float)((0.5*a5 + a8)*scale);
213 fM[3] = (float)(a6*scale);
214 fM[4] = (float)(a7*scale);
215 fM[5] = (float)(a8*scale);
216 }
217}
218
219////////////////////////////////////////////////////////////////////////////////
220
221// k = (y2 - y0, x0 - x2, x2*y0 - x0*y2)
222// l = (y1 - y0, x0 - x1, x1*y0 - x0*y1) * 2*w
223// m = (y2 - y1, x1 - x2, x2*y1 - x1*y2) * 2*w
224void GrPathUtils::getConicKLM(const SkPoint p[3], const SkScalar weight, SkMatrix* out) {
225 SkMatrix& klm = *out;
226 const SkScalar w2 = 2.f * weight;
227 klm[0] = p[2].fY - p[0].fY;
228 klm[1] = p[0].fX - p[2].fX;
229 klm[2] = p[2].fX * p[0].fY - p[0].fX * p[2].fY;
230
231 klm[3] = w2 * (p[1].fY - p[0].fY);
232 klm[4] = w2 * (p[0].fX - p[1].fX);
233 klm[5] = w2 * (p[1].fX * p[0].fY - p[0].fX * p[1].fY);
234
235 klm[6] = w2 * (p[2].fY - p[1].fY);
236 klm[7] = w2 * (p[1].fX - p[2].fX);
237 klm[8] = w2 * (p[2].fX * p[1].fY - p[1].fX * p[2].fY);
238
239 // scale the max absolute value of coeffs to 10
240 SkScalar scale = 0.f;
241 for (int i = 0; i < 9; ++i) {
242 scale = std::max(a: scale, SkScalarAbs(klm[i]));
243 }
244 SkASSERT(scale > 0.f);
245 scale = 10.f / scale;
246 for (int i = 0; i < 9; ++i) {
247 klm[i] *= scale;
248 }
249}
250
251////////////////////////////////////////////////////////////////////////////////
252
253namespace {
254
255// a is the first control point of the cubic.
256// ab is the vector from a to the second control point.
257// dc is the vector from the fourth to the third control point.
258// d is the fourth control point.
259// p is the candidate quadratic control point.
260// this assumes that the cubic doesn't inflect and is simple
261bool is_point_within_cubic_tangents(const SkPoint& a,
262 const SkVector& ab,
263 const SkVector& dc,
264 const SkPoint& d,
265 SkPathFirstDirection dir,
266 const SkPoint p) {
267 SkVector ap = p - a;
268 SkScalar apXab = ap.cross(vec: ab);
269 if (SkPathFirstDirection::kCW == dir) {
270 if (apXab > 0) {
271 return false;
272 }
273 } else {
274 SkASSERT(SkPathFirstDirection::kCCW == dir);
275 if (apXab < 0) {
276 return false;
277 }
278 }
279
280 SkVector dp = p - d;
281 SkScalar dpXdc = dp.cross(vec: dc);
282 if (SkPathFirstDirection::kCW == dir) {
283 if (dpXdc < 0) {
284 return false;
285 }
286 } else {
287 SkASSERT(SkPathFirstDirection::kCCW == dir);
288 if (dpXdc > 0) {
289 return false;
290 }
291 }
292 return true;
293}
294
295void convert_noninflect_cubic_to_quads(const SkPoint p[4],
296 SkScalar toleranceSqd,
297 TArray<SkPoint, true>* quads,
298 int sublevel = 0,
299 bool preserveFirstTangent = true,
300 bool preserveLastTangent = true) {
301 // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is
302 // 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].
303 SkVector ab = p[1] - p[0];
304 SkVector dc = p[2] - p[3];
305
306 if (SkPointPriv::LengthSqd(pt: ab) < SK_ScalarNearlyZero) {
307 if (SkPointPriv::LengthSqd(pt: dc) < SK_ScalarNearlyZero) {
308 SkPoint* degQuad = quads->push_back_n(n: 3);
309 degQuad[0] = p[0];
310 degQuad[1] = p[0];
311 degQuad[2] = p[3];
312 return;
313 }
314 ab = p[2] - p[0];
315 }
316 if (SkPointPriv::LengthSqd(pt: dc) < SK_ScalarNearlyZero) {
317 dc = p[1] - p[3];
318 }
319
320 static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
321 static const int kMaxSubdivs = 10;
322
323 ab.scale(value: kLengthScale);
324 dc.scale(value: kLengthScale);
325
326 // c0 and c1 are extrapolations along vectors ab and dc.
327 SkPoint c0 = p[0] + ab;
328 SkPoint c1 = p[3] + dc;
329
330 SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : SkPointPriv::DistanceToSqd(pt: c0, a: c1);
331 if (dSqd < toleranceSqd) {
332 SkPoint newC;
333 if (preserveFirstTangent == preserveLastTangent) {
334 // We used to force a split when both tangents need to be preserved and c0 != c1.
335 // This introduced a large performance regression for tiny paths for no noticeable
336 // quality improvement. However, we aren't quite fulfilling our contract of guaranteeing
337 // the two tangent vectors and this could introduce a missed pixel in
338 // AAHairlinePathRenderer.
339 newC = (c0 + c1) * 0.5f;
340 } else if (preserveFirstTangent) {
341 newC = c0;
342 } else {
343 newC = c1;
344 }
345
346 SkPoint* pts = quads->push_back_n(n: 3);
347 pts[0] = p[0];
348 pts[1] = newC;
349 pts[2] = p[3];
350 return;
351 }
352 SkPoint choppedPts[7];
353 SkChopCubicAtHalf(src: p, dst: choppedPts);
354 convert_noninflect_cubic_to_quads(
355 p: choppedPts + 0, toleranceSqd, quads, sublevel: sublevel + 1, preserveFirstTangent, preserveLastTangent: false);
356 convert_noninflect_cubic_to_quads(
357 p: choppedPts + 3, toleranceSqd, quads, sublevel: sublevel + 1, preserveFirstTangent: false, preserveLastTangent);
358}
359
360void convert_noninflect_cubic_to_quads_with_constraint(const SkPoint p[4],
361 SkScalar toleranceSqd,
362 SkPathFirstDirection dir,
363 TArray<SkPoint, true>* quads,
364 int sublevel = 0) {
365 // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is
366 // 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].
367
368 SkVector ab = p[1] - p[0];
369 SkVector dc = p[2] - p[3];
370
371 if (SkPointPriv::LengthSqd(pt: ab) < SK_ScalarNearlyZero) {
372 if (SkPointPriv::LengthSqd(pt: dc) < SK_ScalarNearlyZero) {
373 SkPoint* degQuad = quads->push_back_n(n: 3);
374 degQuad[0] = p[0];
375 degQuad[1] = p[0];
376 degQuad[2] = p[3];
377 return;
378 }
379 ab = p[2] - p[0];
380 }
381 if (SkPointPriv::LengthSqd(pt: dc) < SK_ScalarNearlyZero) {
382 dc = p[1] - p[3];
383 }
384
385 // When the ab and cd tangents are degenerate or nearly parallel with vector from d to a the
386 // constraint that the quad point falls between the tangents becomes hard to enforce and we are
387 // likely to hit the max subdivision count. However, in this case the cubic is approaching a
388 // line and the accuracy of the quad point isn't so important. We check if the two middle cubic
389 // control points are very close to the baseline vector. If so then we just pick quadratic
390 // points on the control polygon.
391
392 SkVector da = p[0] - p[3];
393 bool doQuads = SkPointPriv::LengthSqd(pt: dc) < SK_ScalarNearlyZero ||
394 SkPointPriv::LengthSqd(pt: ab) < SK_ScalarNearlyZero;
395 if (!doQuads) {
396 SkScalar invDALengthSqd = SkPointPriv::LengthSqd(pt: da);
397 if (invDALengthSqd > SK_ScalarNearlyZero) {
398 invDALengthSqd = SkScalarInvert(invDALengthSqd);
399 // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a.
400 // same goes for point c using vector cd.
401 SkScalar detABSqd = ab.cross(vec: da);
402 detABSqd = SkScalarSquare(x: detABSqd);
403 SkScalar detDCSqd = dc.cross(vec: da);
404 detDCSqd = SkScalarSquare(x: detDCSqd);
405 if (detABSqd * invDALengthSqd < toleranceSqd &&
406 detDCSqd * invDALengthSqd < toleranceSqd) {
407 doQuads = true;
408 }
409 }
410 }
411 if (doQuads) {
412 SkPoint b = p[0] + ab;
413 SkPoint c = p[3] + dc;
414 SkPoint mid = b + c;
415 mid.scale(SK_ScalarHalf);
416 // Insert two quadratics to cover the case when ab points away from d and/or dc
417 // points away from a.
418 if (SkVector::DotProduct(a: da, b: dc) < 0 || SkVector::DotProduct(a: ab, b: da) > 0) {
419 SkPoint* qpts = quads->push_back_n(n: 6);
420 qpts[0] = p[0];
421 qpts[1] = b;
422 qpts[2] = mid;
423 qpts[3] = mid;
424 qpts[4] = c;
425 qpts[5] = p[3];
426 } else {
427 SkPoint* qpts = quads->push_back_n(n: 3);
428 qpts[0] = p[0];
429 qpts[1] = mid;
430 qpts[2] = p[3];
431 }
432 return;
433 }
434
435 static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
436 static const int kMaxSubdivs = 10;
437
438 ab.scale(value: kLengthScale);
439 dc.scale(value: kLengthScale);
440
441 // c0 and c1 are extrapolations along vectors ab and dc.
442 SkVector c0 = p[0] + ab;
443 SkVector c1 = p[3] + dc;
444
445 SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : SkPointPriv::DistanceToSqd(pt: c0, a: c1);
446 if (dSqd < toleranceSqd) {
447 SkPoint cAvg = (c0 + c1) * 0.5f;
448 bool subdivide = false;
449
450 if (!is_point_within_cubic_tangents(a: p[0], ab, dc, d: p[3], dir, p: cAvg)) {
451 // choose a new cAvg that is the intersection of the two tangent lines.
452 ab = SkPointPriv::MakeOrthog(vec: ab);
453 SkScalar z0 = -ab.dot(vec: p[0]);
454 dc = SkPointPriv::MakeOrthog(vec: dc);
455 SkScalar z1 = -dc.dot(vec: p[3]);
456 cAvg.fX = ab.fY * z1 - z0 * dc.fY;
457 cAvg.fY = z0 * dc.fX - ab.fX * z1;
458 SkScalar z = ab.fX * dc.fY - ab.fY * dc.fX;
459 z = sk_ieee_float_divide(numer: 1.0f, denom: z);
460 cAvg.fX *= z;
461 cAvg.fY *= z;
462 if (sublevel <= kMaxSubdivs) {
463 SkScalar d0Sqd = SkPointPriv::DistanceToSqd(pt: c0, a: cAvg);
464 SkScalar d1Sqd = SkPointPriv::DistanceToSqd(pt: c1, a: cAvg);
465 // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know
466 // the distances and tolerance can't be negative.
467 // (d0 + d1)^2 > toleranceSqd
468 // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd
469 SkScalar d0d1 = SkScalarSqrt(d0Sqd * d1Sqd);
470 subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd;
471 }
472 }
473 if (!subdivide) {
474 SkPoint* pts = quads->push_back_n(n: 3);
475 pts[0] = p[0];
476 pts[1] = cAvg;
477 pts[2] = p[3];
478 return;
479 }
480 }
481 SkPoint choppedPts[7];
482 SkChopCubicAtHalf(src: p, dst: choppedPts);
483 convert_noninflect_cubic_to_quads_with_constraint(
484 p: choppedPts + 0, toleranceSqd, dir, quads, sublevel: sublevel + 1);
485 convert_noninflect_cubic_to_quads_with_constraint(
486 p: choppedPts + 3, toleranceSqd, dir, quads, sublevel: sublevel + 1);
487}
488} // namespace
489
490void GrPathUtils::convertCubicToQuads(const SkPoint p[4],
491 SkScalar tolScale,
492 TArray<SkPoint, true>* quads) {
493 if (!p[0].isFinite() || !p[1].isFinite() || !p[2].isFinite() || !p[3].isFinite()) {
494 return;
495 }
496 if (!SkScalarIsFinite(x: tolScale)) {
497 return;
498 }
499 SkPoint chopped[10];
500 int count = SkChopCubicAtInflections(src: p, dst: chopped);
501
502 const SkScalar tolSqd = SkScalarSquare(x: tolScale);
503
504 for (int i = 0; i < count; ++i) {
505 SkPoint* cubic = chopped + 3*i;
506 convert_noninflect_cubic_to_quads(p: cubic, toleranceSqd: tolSqd, quads);
507 }
508}
509
510void GrPathUtils::convertCubicToQuadsConstrainToTangents(const SkPoint p[4],
511 SkScalar tolScale,
512 SkPathFirstDirection dir,
513 TArray<SkPoint, true>* quads) {
514 if (!p[0].isFinite() || !p[1].isFinite() || !p[2].isFinite() || !p[3].isFinite()) {
515 return;
516 }
517 if (!SkScalarIsFinite(x: tolScale)) {
518 return;
519 }
520 SkPoint chopped[10];
521 int count = SkChopCubicAtInflections(src: p, dst: chopped);
522
523 const SkScalar tolSqd = SkScalarSquare(x: tolScale);
524
525 for (int i = 0; i < count; ++i) {
526 SkPoint* cubic = chopped + 3*i;
527 convert_noninflect_cubic_to_quads_with_constraint(p: cubic, toleranceSqd: tolSqd, dir, quads);
528 }
529}
530

Provided by KDAB

Privacy Policy
Learn more about Flutter for embedded and desktop on industrialflutter.com

source code of flutter_engine/third_party/skia/src/gpu/ganesh/geometry/GrPathUtils.cpp