1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/gpu/GrPathUtils.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,868 @@
1.4 +/*
1.5 + * Copyright 2011 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#include "GrPathUtils.h"
1.12 +
1.13 +#include "GrPoint.h"
1.14 +#include "SkGeometry.h"
1.15 +
1.16 +SkScalar GrPathUtils::scaleToleranceToSrc(SkScalar devTol,
1.17 + const SkMatrix& viewM,
1.18 + const SkRect& pathBounds) {
1.19 + // In order to tesselate the path we get a bound on how much the matrix can
1.20 + // stretch when mapping to screen coordinates.
1.21 + SkScalar stretch = viewM.getMaxStretch();
1.22 + SkScalar srcTol = devTol;
1.23 +
1.24 + if (stretch < 0) {
1.25 + // take worst case mapRadius amoung four corners.
1.26 + // (less than perfect)
1.27 + for (int i = 0; i < 4; ++i) {
1.28 + SkMatrix mat;
1.29 + mat.setTranslate((i % 2) ? pathBounds.fLeft : pathBounds.fRight,
1.30 + (i < 2) ? pathBounds.fTop : pathBounds.fBottom);
1.31 + mat.postConcat(viewM);
1.32 + stretch = SkMaxScalar(stretch, mat.mapRadius(SK_Scalar1));
1.33 + }
1.34 + }
1.35 + srcTol = SkScalarDiv(srcTol, stretch);
1.36 + return srcTol;
1.37 +}
1.38 +
1.39 +static const int MAX_POINTS_PER_CURVE = 1 << 10;
1.40 +static const SkScalar gMinCurveTol = 0.0001f;
1.41 +
1.42 +uint32_t GrPathUtils::quadraticPointCount(const GrPoint points[],
1.43 + SkScalar tol) {
1.44 + if (tol < gMinCurveTol) {
1.45 + tol = gMinCurveTol;
1.46 + }
1.47 + SkASSERT(tol > 0);
1.48 +
1.49 + SkScalar d = points[1].distanceToLineSegmentBetween(points[0], points[2]);
1.50 + if (d <= tol) {
1.51 + return 1;
1.52 + } else {
1.53 + // Each time we subdivide, d should be cut in 4. So we need to
1.54 + // subdivide x = log4(d/tol) times. x subdivisions creates 2^(x)
1.55 + // points.
1.56 + // 2^(log4(x)) = sqrt(x);
1.57 + int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol)));
1.58 + int pow2 = GrNextPow2(temp);
1.59 + // Because of NaNs & INFs we can wind up with a degenerate temp
1.60 + // such that pow2 comes out negative. Also, our point generator
1.61 + // will always output at least one pt.
1.62 + if (pow2 < 1) {
1.63 + pow2 = 1;
1.64 + }
1.65 + return GrMin(pow2, MAX_POINTS_PER_CURVE);
1.66 + }
1.67 +}
1.68 +
1.69 +uint32_t GrPathUtils::generateQuadraticPoints(const GrPoint& p0,
1.70 + const GrPoint& p1,
1.71 + const GrPoint& p2,
1.72 + SkScalar tolSqd,
1.73 + GrPoint** points,
1.74 + uint32_t pointsLeft) {
1.75 + if (pointsLeft < 2 ||
1.76 + (p1.distanceToLineSegmentBetweenSqd(p0, p2)) < tolSqd) {
1.77 + (*points)[0] = p2;
1.78 + *points += 1;
1.79 + return 1;
1.80 + }
1.81 +
1.82 + GrPoint q[] = {
1.83 + { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
1.84 + { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
1.85 + };
1.86 + GrPoint r = { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) };
1.87 +
1.88 + pointsLeft >>= 1;
1.89 + uint32_t a = generateQuadraticPoints(p0, q[0], r, tolSqd, points, pointsLeft);
1.90 + uint32_t b = generateQuadraticPoints(r, q[1], p2, tolSqd, points, pointsLeft);
1.91 + return a + b;
1.92 +}
1.93 +
1.94 +uint32_t GrPathUtils::cubicPointCount(const GrPoint points[],
1.95 + SkScalar tol) {
1.96 + if (tol < gMinCurveTol) {
1.97 + tol = gMinCurveTol;
1.98 + }
1.99 + SkASSERT(tol > 0);
1.100 +
1.101 + SkScalar d = GrMax(
1.102 + points[1].distanceToLineSegmentBetweenSqd(points[0], points[3]),
1.103 + points[2].distanceToLineSegmentBetweenSqd(points[0], points[3]));
1.104 + d = SkScalarSqrt(d);
1.105 + if (d <= tol) {
1.106 + return 1;
1.107 + } else {
1.108 + int temp = SkScalarCeilToInt(SkScalarSqrt(SkScalarDiv(d, tol)));
1.109 + int pow2 = GrNextPow2(temp);
1.110 + // Because of NaNs & INFs we can wind up with a degenerate temp
1.111 + // such that pow2 comes out negative. Also, our point generator
1.112 + // will always output at least one pt.
1.113 + if (pow2 < 1) {
1.114 + pow2 = 1;
1.115 + }
1.116 + return GrMin(pow2, MAX_POINTS_PER_CURVE);
1.117 + }
1.118 +}
1.119 +
1.120 +uint32_t GrPathUtils::generateCubicPoints(const GrPoint& p0,
1.121 + const GrPoint& p1,
1.122 + const GrPoint& p2,
1.123 + const GrPoint& p3,
1.124 + SkScalar tolSqd,
1.125 + GrPoint** points,
1.126 + uint32_t pointsLeft) {
1.127 + if (pointsLeft < 2 ||
1.128 + (p1.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd &&
1.129 + p2.distanceToLineSegmentBetweenSqd(p0, p3) < tolSqd)) {
1.130 + (*points)[0] = p3;
1.131 + *points += 1;
1.132 + return 1;
1.133 + }
1.134 + GrPoint q[] = {
1.135 + { SkScalarAve(p0.fX, p1.fX), SkScalarAve(p0.fY, p1.fY) },
1.136 + { SkScalarAve(p1.fX, p2.fX), SkScalarAve(p1.fY, p2.fY) },
1.137 + { SkScalarAve(p2.fX, p3.fX), SkScalarAve(p2.fY, p3.fY) }
1.138 + };
1.139 + GrPoint r[] = {
1.140 + { SkScalarAve(q[0].fX, q[1].fX), SkScalarAve(q[0].fY, q[1].fY) },
1.141 + { SkScalarAve(q[1].fX, q[2].fX), SkScalarAve(q[1].fY, q[2].fY) }
1.142 + };
1.143 + GrPoint s = { SkScalarAve(r[0].fX, r[1].fX), SkScalarAve(r[0].fY, r[1].fY) };
1.144 + pointsLeft >>= 1;
1.145 + uint32_t a = generateCubicPoints(p0, q[0], r[0], s, tolSqd, points, pointsLeft);
1.146 + uint32_t b = generateCubicPoints(s, r[1], q[2], p3, tolSqd, points, pointsLeft);
1.147 + return a + b;
1.148 +}
1.149 +
1.150 +int GrPathUtils::worstCasePointCount(const SkPath& path, int* subpaths,
1.151 + SkScalar tol) {
1.152 + if (tol < gMinCurveTol) {
1.153 + tol = gMinCurveTol;
1.154 + }
1.155 + SkASSERT(tol > 0);
1.156 +
1.157 + int pointCount = 0;
1.158 + *subpaths = 1;
1.159 +
1.160 + bool first = true;
1.161 +
1.162 + SkPath::Iter iter(path, false);
1.163 + SkPath::Verb verb;
1.164 +
1.165 + GrPoint pts[4];
1.166 + while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
1.167 +
1.168 + switch (verb) {
1.169 + case SkPath::kLine_Verb:
1.170 + pointCount += 1;
1.171 + break;
1.172 + case SkPath::kQuad_Verb:
1.173 + pointCount += quadraticPointCount(pts, tol);
1.174 + break;
1.175 + case SkPath::kCubic_Verb:
1.176 + pointCount += cubicPointCount(pts, tol);
1.177 + break;
1.178 + case SkPath::kMove_Verb:
1.179 + pointCount += 1;
1.180 + if (!first) {
1.181 + ++(*subpaths);
1.182 + }
1.183 + break;
1.184 + default:
1.185 + break;
1.186 + }
1.187 + first = false;
1.188 + }
1.189 + return pointCount;
1.190 +}
1.191 +
1.192 +void GrPathUtils::QuadUVMatrix::set(const GrPoint qPts[3]) {
1.193 + SkMatrix m;
1.194 + // We want M such that M * xy_pt = uv_pt
1.195 + // We know M * control_pts = [0 1/2 1]
1.196 + // [0 0 1]
1.197 + // [1 1 1]
1.198 + // And control_pts = [x0 x1 x2]
1.199 + // [y0 y1 y2]
1.200 + // [1 1 1 ]
1.201 + // We invert the control pt matrix and post concat to both sides to get M.
1.202 + // Using the known form of the control point matrix and the result, we can
1.203 + // optimize and improve precision.
1.204 +
1.205 + double x0 = qPts[0].fX;
1.206 + double y0 = qPts[0].fY;
1.207 + double x1 = qPts[1].fX;
1.208 + double y1 = qPts[1].fY;
1.209 + double x2 = qPts[2].fX;
1.210 + double y2 = qPts[2].fY;
1.211 + double det = x0*y1 - y0*x1 + x2*y0 - y2*x0 + x1*y2 - y1*x2;
1.212 +
1.213 + if (!sk_float_isfinite(det)
1.214 + || SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero)) {
1.215 + // The quad is degenerate. Hopefully this is rare. Find the pts that are
1.216 + // farthest apart to compute a line (unless it is really a pt).
1.217 + SkScalar maxD = qPts[0].distanceToSqd(qPts[1]);
1.218 + int maxEdge = 0;
1.219 + SkScalar d = qPts[1].distanceToSqd(qPts[2]);
1.220 + if (d > maxD) {
1.221 + maxD = d;
1.222 + maxEdge = 1;
1.223 + }
1.224 + d = qPts[2].distanceToSqd(qPts[0]);
1.225 + if (d > maxD) {
1.226 + maxD = d;
1.227 + maxEdge = 2;
1.228 + }
1.229 + // We could have a tolerance here, not sure if it would improve anything
1.230 + if (maxD > 0) {
1.231 + // Set the matrix to give (u = 0, v = distance_to_line)
1.232 + GrVec lineVec = qPts[(maxEdge + 1)%3] - qPts[maxEdge];
1.233 + // when looking from the point 0 down the line we want positive
1.234 + // distances to be to the left. This matches the non-degenerate
1.235 + // case.
1.236 + lineVec.setOrthog(lineVec, GrPoint::kLeft_Side);
1.237 + lineVec.dot(qPts[0]);
1.238 + // first row
1.239 + fM[0] = 0;
1.240 + fM[1] = 0;
1.241 + fM[2] = 0;
1.242 + // second row
1.243 + fM[3] = lineVec.fX;
1.244 + fM[4] = lineVec.fY;
1.245 + fM[5] = -lineVec.dot(qPts[maxEdge]);
1.246 + } else {
1.247 + // It's a point. It should cover zero area. Just set the matrix such
1.248 + // that (u, v) will always be far away from the quad.
1.249 + fM[0] = 0; fM[1] = 0; fM[2] = 100.f;
1.250 + fM[3] = 0; fM[4] = 0; fM[5] = 100.f;
1.251 + }
1.252 + } else {
1.253 + double scale = 1.0/det;
1.254 +
1.255 + // compute adjugate matrix
1.256 + double a0, a1, a2, a3, a4, a5, a6, a7, a8;
1.257 + a0 = y1-y2;
1.258 + a1 = x2-x1;
1.259 + a2 = x1*y2-x2*y1;
1.260 +
1.261 + a3 = y2-y0;
1.262 + a4 = x0-x2;
1.263 + a5 = x2*y0-x0*y2;
1.264 +
1.265 + a6 = y0-y1;
1.266 + a7 = x1-x0;
1.267 + a8 = x0*y1-x1*y0;
1.268 +
1.269 + // this performs the uv_pts*adjugate(control_pts) multiply,
1.270 + // then does the scale by 1/det afterwards to improve precision
1.271 + m[SkMatrix::kMScaleX] = (float)((0.5*a3 + a6)*scale);
1.272 + m[SkMatrix::kMSkewX] = (float)((0.5*a4 + a7)*scale);
1.273 + m[SkMatrix::kMTransX] = (float)((0.5*a5 + a8)*scale);
1.274 +
1.275 + m[SkMatrix::kMSkewY] = (float)(a6*scale);
1.276 + m[SkMatrix::kMScaleY] = (float)(a7*scale);
1.277 + m[SkMatrix::kMTransY] = (float)(a8*scale);
1.278 +
1.279 + m[SkMatrix::kMPersp0] = (float)((a0 + a3 + a6)*scale);
1.280 + m[SkMatrix::kMPersp1] = (float)((a1 + a4 + a7)*scale);
1.281 + m[SkMatrix::kMPersp2] = (float)((a2 + a5 + a8)*scale);
1.282 +
1.283 + // The matrix should not have perspective.
1.284 + SkDEBUGCODE(static const SkScalar gTOL = 1.f / 100.f);
1.285 + SkASSERT(SkScalarAbs(m.get(SkMatrix::kMPersp0)) < gTOL);
1.286 + SkASSERT(SkScalarAbs(m.get(SkMatrix::kMPersp1)) < gTOL);
1.287 +
1.288 + // It may not be normalized to have 1.0 in the bottom right
1.289 + float m33 = m.get(SkMatrix::kMPersp2);
1.290 + if (1.f != m33) {
1.291 + m33 = 1.f / m33;
1.292 + fM[0] = m33 * m.get(SkMatrix::kMScaleX);
1.293 + fM[1] = m33 * m.get(SkMatrix::kMSkewX);
1.294 + fM[2] = m33 * m.get(SkMatrix::kMTransX);
1.295 + fM[3] = m33 * m.get(SkMatrix::kMSkewY);
1.296 + fM[4] = m33 * m.get(SkMatrix::kMScaleY);
1.297 + fM[5] = m33 * m.get(SkMatrix::kMTransY);
1.298 + } else {
1.299 + fM[0] = m.get(SkMatrix::kMScaleX);
1.300 + fM[1] = m.get(SkMatrix::kMSkewX);
1.301 + fM[2] = m.get(SkMatrix::kMTransX);
1.302 + fM[3] = m.get(SkMatrix::kMSkewY);
1.303 + fM[4] = m.get(SkMatrix::kMScaleY);
1.304 + fM[5] = m.get(SkMatrix::kMTransY);
1.305 + }
1.306 + }
1.307 +}
1.308 +
1.309 +////////////////////////////////////////////////////////////////////////////////
1.310 +
1.311 +// k = (y2 - y0, x0 - x2, (x2 - x0)*y0 - (y2 - y0)*x0 )
1.312 +// l = (2*w * (y1 - y0), 2*w * (x0 - x1), 2*w * (x1*y0 - x0*y1))
1.313 +// m = (2*w * (y2 - y1), 2*w * (x1 - x2), 2*w * (x2*y1 - x1*y2))
1.314 +void GrPathUtils::getConicKLM(const SkPoint p[3], const SkScalar weight, SkScalar klm[9]) {
1.315 + const SkScalar w2 = 2.f * weight;
1.316 + klm[0] = p[2].fY - p[0].fY;
1.317 + klm[1] = p[0].fX - p[2].fX;
1.318 + klm[2] = (p[2].fX - p[0].fX) * p[0].fY - (p[2].fY - p[0].fY) * p[0].fX;
1.319 +
1.320 + klm[3] = w2 * (p[1].fY - p[0].fY);
1.321 + klm[4] = w2 * (p[0].fX - p[1].fX);
1.322 + klm[5] = w2 * (p[1].fX * p[0].fY - p[0].fX * p[1].fY);
1.323 +
1.324 + klm[6] = w2 * (p[2].fY - p[1].fY);
1.325 + klm[7] = w2 * (p[1].fX - p[2].fX);
1.326 + klm[8] = w2 * (p[2].fX * p[1].fY - p[1].fX * p[2].fY);
1.327 +
1.328 + // scale the max absolute value of coeffs to 10
1.329 + SkScalar scale = 0.f;
1.330 + for (int i = 0; i < 9; ++i) {
1.331 + scale = SkMaxScalar(scale, SkScalarAbs(klm[i]));
1.332 + }
1.333 + SkASSERT(scale > 0.f);
1.334 + scale = 10.f / scale;
1.335 + for (int i = 0; i < 9; ++i) {
1.336 + klm[i] *= scale;
1.337 + }
1.338 +}
1.339 +
1.340 +////////////////////////////////////////////////////////////////////////////////
1.341 +
1.342 +namespace {
1.343 +
1.344 +// a is the first control point of the cubic.
1.345 +// ab is the vector from a to the second control point.
1.346 +// dc is the vector from the fourth to the third control point.
1.347 +// d is the fourth control point.
1.348 +// p is the candidate quadratic control point.
1.349 +// this assumes that the cubic doesn't inflect and is simple
1.350 +bool is_point_within_cubic_tangents(const SkPoint& a,
1.351 + const SkVector& ab,
1.352 + const SkVector& dc,
1.353 + const SkPoint& d,
1.354 + SkPath::Direction dir,
1.355 + const SkPoint p) {
1.356 + SkVector ap = p - a;
1.357 + SkScalar apXab = ap.cross(ab);
1.358 + if (SkPath::kCW_Direction == dir) {
1.359 + if (apXab > 0) {
1.360 + return false;
1.361 + }
1.362 + } else {
1.363 + SkASSERT(SkPath::kCCW_Direction == dir);
1.364 + if (apXab < 0) {
1.365 + return false;
1.366 + }
1.367 + }
1.368 +
1.369 + SkVector dp = p - d;
1.370 + SkScalar dpXdc = dp.cross(dc);
1.371 + if (SkPath::kCW_Direction == dir) {
1.372 + if (dpXdc < 0) {
1.373 + return false;
1.374 + }
1.375 + } else {
1.376 + SkASSERT(SkPath::kCCW_Direction == dir);
1.377 + if (dpXdc > 0) {
1.378 + return false;
1.379 + }
1.380 + }
1.381 + return true;
1.382 +}
1.383 +
1.384 +void convert_noninflect_cubic_to_quads(const SkPoint p[4],
1.385 + SkScalar toleranceSqd,
1.386 + bool constrainWithinTangents,
1.387 + SkPath::Direction dir,
1.388 + SkTArray<SkPoint, true>* quads,
1.389 + int sublevel = 0) {
1.390 +
1.391 + // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is
1.392 + // 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].
1.393 +
1.394 + SkVector ab = p[1] - p[0];
1.395 + SkVector dc = p[2] - p[3];
1.396 +
1.397 + if (ab.isZero()) {
1.398 + if (dc.isZero()) {
1.399 + SkPoint* degQuad = quads->push_back_n(3);
1.400 + degQuad[0] = p[0];
1.401 + degQuad[1] = p[0];
1.402 + degQuad[2] = p[3];
1.403 + return;
1.404 + }
1.405 + ab = p[2] - p[0];
1.406 + }
1.407 + if (dc.isZero()) {
1.408 + dc = p[1] - p[3];
1.409 + }
1.410 +
1.411 + // When the ab and cd tangents are nearly parallel with vector from d to a the constraint that
1.412 + // the quad point falls between the tangents becomes hard to enforce and we are likely to hit
1.413 + // the max subdivision count. However, in this case the cubic is approaching a line and the
1.414 + // accuracy of the quad point isn't so important. We check if the two middle cubic control
1.415 + // points are very close to the baseline vector. If so then we just pick quadratic points on the
1.416 + // control polygon.
1.417 +
1.418 + if (constrainWithinTangents) {
1.419 + SkVector da = p[0] - p[3];
1.420 + SkScalar invDALengthSqd = da.lengthSqd();
1.421 + if (invDALengthSqd > SK_ScalarNearlyZero) {
1.422 + invDALengthSqd = SkScalarInvert(invDALengthSqd);
1.423 + // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a.
1.424 + // same goed for point c using vector cd.
1.425 + SkScalar detABSqd = ab.cross(da);
1.426 + detABSqd = SkScalarSquare(detABSqd);
1.427 + SkScalar detDCSqd = dc.cross(da);
1.428 + detDCSqd = SkScalarSquare(detDCSqd);
1.429 + if (SkScalarMul(detABSqd, invDALengthSqd) < toleranceSqd &&
1.430 + SkScalarMul(detDCSqd, invDALengthSqd) < toleranceSqd) {
1.431 + SkPoint b = p[0] + ab;
1.432 + SkPoint c = p[3] + dc;
1.433 + SkPoint mid = b + c;
1.434 + mid.scale(SK_ScalarHalf);
1.435 + // Insert two quadratics to cover the case when ab points away from d and/or dc
1.436 + // points away from a.
1.437 + if (SkVector::DotProduct(da, dc) < 0 || SkVector::DotProduct(ab,da) > 0) {
1.438 + SkPoint* qpts = quads->push_back_n(6);
1.439 + qpts[0] = p[0];
1.440 + qpts[1] = b;
1.441 + qpts[2] = mid;
1.442 + qpts[3] = mid;
1.443 + qpts[4] = c;
1.444 + qpts[5] = p[3];
1.445 + } else {
1.446 + SkPoint* qpts = quads->push_back_n(3);
1.447 + qpts[0] = p[0];
1.448 + qpts[1] = mid;
1.449 + qpts[2] = p[3];
1.450 + }
1.451 + return;
1.452 + }
1.453 + }
1.454 + }
1.455 +
1.456 + static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2;
1.457 + static const int kMaxSubdivs = 10;
1.458 +
1.459 + ab.scale(kLengthScale);
1.460 + dc.scale(kLengthScale);
1.461 +
1.462 + // e0 and e1 are extrapolations along vectors ab and dc.
1.463 + SkVector c0 = p[0];
1.464 + c0 += ab;
1.465 + SkVector c1 = p[3];
1.466 + c1 += dc;
1.467 +
1.468 + SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : c0.distanceToSqd(c1);
1.469 + if (dSqd < toleranceSqd) {
1.470 + SkPoint cAvg = c0;
1.471 + cAvg += c1;
1.472 + cAvg.scale(SK_ScalarHalf);
1.473 +
1.474 + bool subdivide = false;
1.475 +
1.476 + if (constrainWithinTangents &&
1.477 + !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) {
1.478 + // choose a new cAvg that is the intersection of the two tangent lines.
1.479 + ab.setOrthog(ab);
1.480 + SkScalar z0 = -ab.dot(p[0]);
1.481 + dc.setOrthog(dc);
1.482 + SkScalar z1 = -dc.dot(p[3]);
1.483 + cAvg.fX = SkScalarMul(ab.fY, z1) - SkScalarMul(z0, dc.fY);
1.484 + cAvg.fY = SkScalarMul(z0, dc.fX) - SkScalarMul(ab.fX, z1);
1.485 + SkScalar z = SkScalarMul(ab.fX, dc.fY) - SkScalarMul(ab.fY, dc.fX);
1.486 + z = SkScalarInvert(z);
1.487 + cAvg.fX *= z;
1.488 + cAvg.fY *= z;
1.489 + if (sublevel <= kMaxSubdivs) {
1.490 + SkScalar d0Sqd = c0.distanceToSqd(cAvg);
1.491 + SkScalar d1Sqd = c1.distanceToSqd(cAvg);
1.492 + // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know
1.493 + // the distances and tolerance can't be negative.
1.494 + // (d0 + d1)^2 > toleranceSqd
1.495 + // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd
1.496 + SkScalar d0d1 = SkScalarSqrt(SkScalarMul(d0Sqd, d1Sqd));
1.497 + subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd;
1.498 + }
1.499 + }
1.500 + if (!subdivide) {
1.501 + SkPoint* pts = quads->push_back_n(3);
1.502 + pts[0] = p[0];
1.503 + pts[1] = cAvg;
1.504 + pts[2] = p[3];
1.505 + return;
1.506 + }
1.507 + }
1.508 + SkPoint choppedPts[7];
1.509 + SkChopCubicAtHalf(p, choppedPts);
1.510 + convert_noninflect_cubic_to_quads(choppedPts + 0,
1.511 + toleranceSqd,
1.512 + constrainWithinTangents,
1.513 + dir,
1.514 + quads,
1.515 + sublevel + 1);
1.516 + convert_noninflect_cubic_to_quads(choppedPts + 3,
1.517 + toleranceSqd,
1.518 + constrainWithinTangents,
1.519 + dir,
1.520 + quads,
1.521 + sublevel + 1);
1.522 +}
1.523 +}
1.524 +
1.525 +void GrPathUtils::convertCubicToQuads(const GrPoint p[4],
1.526 + SkScalar tolScale,
1.527 + bool constrainWithinTangents,
1.528 + SkPath::Direction dir,
1.529 + SkTArray<SkPoint, true>* quads) {
1.530 + SkPoint chopped[10];
1.531 + int count = SkChopCubicAtInflections(p, chopped);
1.532 +
1.533 + // base tolerance is 1 pixel.
1.534 + static const SkScalar kTolerance = SK_Scalar1;
1.535 + const SkScalar tolSqd = SkScalarSquare(SkScalarMul(tolScale, kTolerance));
1.536 +
1.537 + for (int i = 0; i < count; ++i) {
1.538 + SkPoint* cubic = chopped + 3*i;
1.539 + convert_noninflect_cubic_to_quads(cubic, tolSqd, constrainWithinTangents, dir, quads);
1.540 + }
1.541 +
1.542 +}
1.543 +
1.544 +////////////////////////////////////////////////////////////////////////////////
1.545 +
1.546 +enum CubicType {
1.547 + kSerpentine_CubicType,
1.548 + kCusp_CubicType,
1.549 + kLoop_CubicType,
1.550 + kQuadratic_CubicType,
1.551 + kLine_CubicType,
1.552 + kPoint_CubicType
1.553 +};
1.554 +
1.555 +// discr(I) = d0^2 * (3*d1^2 - 4*d0*d2)
1.556 +// Classification:
1.557 +// discr(I) > 0 Serpentine
1.558 +// discr(I) = 0 Cusp
1.559 +// discr(I) < 0 Loop
1.560 +// d0 = d1 = 0 Quadratic
1.561 +// d0 = d1 = d2 = 0 Line
1.562 +// p0 = p1 = p2 = p3 Point
1.563 +static CubicType classify_cubic(const SkPoint p[4], const SkScalar d[3]) {
1.564 + if (p[0] == p[1] && p[0] == p[2] && p[0] == p[3]) {
1.565 + return kPoint_CubicType;
1.566 + }
1.567 + const SkScalar discr = d[0] * d[0] * (3.f * d[1] * d[1] - 4.f * d[0] * d[2]);
1.568 + if (discr > SK_ScalarNearlyZero) {
1.569 + return kSerpentine_CubicType;
1.570 + } else if (discr < -SK_ScalarNearlyZero) {
1.571 + return kLoop_CubicType;
1.572 + } else {
1.573 + if (0.f == d[0] && 0.f == d[1]) {
1.574 + return (0.f == d[2] ? kLine_CubicType : kQuadratic_CubicType);
1.575 + } else {
1.576 + return kCusp_CubicType;
1.577 + }
1.578 + }
1.579 +}
1.580 +
1.581 +// Assumes the third component of points is 1.
1.582 +// Calcs p0 . (p1 x p2)
1.583 +static SkScalar calc_dot_cross_cubic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
1.584 + const SkScalar xComp = p0.fX * (p1.fY - p2.fY);
1.585 + const SkScalar yComp = p0.fY * (p2.fX - p1.fX);
1.586 + const SkScalar wComp = p1.fX * p2.fY - p1.fY * p2.fX;
1.587 + return (xComp + yComp + wComp);
1.588 +}
1.589 +
1.590 +// Solves linear system to extract klm
1.591 +// P.K = k (similarly for l, m)
1.592 +// Where P is matrix of control points
1.593 +// K is coefficients for the line K
1.594 +// k is vector of values of K evaluated at the control points
1.595 +// Solving for K, thus K = P^(-1) . k
1.596 +static void calc_cubic_klm(const SkPoint p[4], const SkScalar controlK[4],
1.597 + const SkScalar controlL[4], const SkScalar controlM[4],
1.598 + SkScalar k[3], SkScalar l[3], SkScalar m[3]) {
1.599 + SkMatrix matrix;
1.600 + matrix.setAll(p[0].fX, p[0].fY, 1.f,
1.601 + p[1].fX, p[1].fY, 1.f,
1.602 + p[2].fX, p[2].fY, 1.f);
1.603 + SkMatrix inverse;
1.604 + if (matrix.invert(&inverse)) {
1.605 + inverse.mapHomogeneousPoints(k, controlK, 1);
1.606 + inverse.mapHomogeneousPoints(l, controlL, 1);
1.607 + inverse.mapHomogeneousPoints(m, controlM, 1);
1.608 + }
1.609 +
1.610 +}
1.611 +
1.612 +static void set_serp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
1.613 + SkScalar tempSqrt = SkScalarSqrt(9.f * d[1] * d[1] - 12.f * d[0] * d[2]);
1.614 + SkScalar ls = 3.f * d[1] - tempSqrt;
1.615 + SkScalar lt = 6.f * d[0];
1.616 + SkScalar ms = 3.f * d[1] + tempSqrt;
1.617 + SkScalar mt = 6.f * d[0];
1.618 +
1.619 + k[0] = ls * ms;
1.620 + k[1] = (3.f * ls * ms - ls * mt - lt * ms) / 3.f;
1.621 + k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f;
1.622 + k[3] = (lt - ls) * (mt - ms);
1.623 +
1.624 + l[0] = ls * ls * ls;
1.625 + const SkScalar lt_ls = lt - ls;
1.626 + l[1] = ls * ls * lt_ls * -1.f;
1.627 + l[2] = lt_ls * lt_ls * ls;
1.628 + l[3] = -1.f * lt_ls * lt_ls * lt_ls;
1.629 +
1.630 + m[0] = ms * ms * ms;
1.631 + const SkScalar mt_ms = mt - ms;
1.632 + m[1] = ms * ms * mt_ms * -1.f;
1.633 + m[2] = mt_ms * mt_ms * ms;
1.634 + m[3] = -1.f * mt_ms * mt_ms * mt_ms;
1.635 +
1.636 + // If d0 < 0 we need to flip the orientation of our curve
1.637 + // This is done by negating the k and l values
1.638 + // We want negative distance values to be on the inside
1.639 + if ( d[0] > 0) {
1.640 + for (int i = 0; i < 4; ++i) {
1.641 + k[i] = -k[i];
1.642 + l[i] = -l[i];
1.643 + }
1.644 + }
1.645 +}
1.646 +
1.647 +static void set_loop_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
1.648 + SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
1.649 + SkScalar ls = d[1] - tempSqrt;
1.650 + SkScalar lt = 2.f * d[0];
1.651 + SkScalar ms = d[1] + tempSqrt;
1.652 + SkScalar mt = 2.f * d[0];
1.653 +
1.654 + k[0] = ls * ms;
1.655 + k[1] = (3.f * ls*ms - ls * mt - lt * ms) / 3.f;
1.656 + k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f;
1.657 + k[3] = (lt - ls) * (mt - ms);
1.658 +
1.659 + l[0] = ls * ls * ms;
1.660 + l[1] = (ls * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/-3.f;
1.661 + l[2] = ((lt - ls) * (ls * (2.f * mt - 3.f * ms) + lt * ms))/3.f;
1.662 + l[3] = -1.f * (lt - ls) * (lt - ls) * (mt - ms);
1.663 +
1.664 + m[0] = ls * ms * ms;
1.665 + m[1] = (ms * (ls * (2.f * mt - 3.f * ms) + lt * ms))/-3.f;
1.666 + m[2] = ((mt - ms) * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/3.f;
1.667 + m[3] = -1.f * (lt - ls) * (mt - ms) * (mt - ms);
1.668 +
1.669 +
1.670 + // If (d0 < 0 && sign(k1) > 0) || (d0 > 0 && sign(k1) < 0),
1.671 + // we need to flip the orientation of our curve.
1.672 + // This is done by negating the k and l values
1.673 + if ( (d[0] < 0 && k[1] > 0) || (d[0] > 0 && k[1] < 0)) {
1.674 + for (int i = 0; i < 4; ++i) {
1.675 + k[i] = -k[i];
1.676 + l[i] = -l[i];
1.677 + }
1.678 + }
1.679 +}
1.680 +
1.681 +static void set_cusp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
1.682 + const SkScalar ls = d[2];
1.683 + const SkScalar lt = 3.f * d[1];
1.684 +
1.685 + k[0] = ls;
1.686 + k[1] = ls - lt / 3.f;
1.687 + k[2] = ls - 2.f * lt / 3.f;
1.688 + k[3] = ls - lt;
1.689 +
1.690 + l[0] = ls * ls * ls;
1.691 + const SkScalar ls_lt = ls - lt;
1.692 + l[1] = ls * ls * ls_lt;
1.693 + l[2] = ls_lt * ls_lt * ls;
1.694 + l[3] = ls_lt * ls_lt * ls_lt;
1.695 +
1.696 + m[0] = 1.f;
1.697 + m[1] = 1.f;
1.698 + m[2] = 1.f;
1.699 + m[3] = 1.f;
1.700 +}
1.701 +
1.702 +// For the case when a cubic is actually a quadratic
1.703 +// M =
1.704 +// 0 0 0
1.705 +// 1/3 0 1/3
1.706 +// 2/3 1/3 2/3
1.707 +// 1 1 1
1.708 +static void set_quadratic_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) {
1.709 + k[0] = 0.f;
1.710 + k[1] = 1.f/3.f;
1.711 + k[2] = 2.f/3.f;
1.712 + k[3] = 1.f;
1.713 +
1.714 + l[0] = 0.f;
1.715 + l[1] = 0.f;
1.716 + l[2] = 1.f/3.f;
1.717 + l[3] = 1.f;
1.718 +
1.719 + m[0] = 0.f;
1.720 + m[1] = 1.f/3.f;
1.721 + m[2] = 2.f/3.f;
1.722 + m[3] = 1.f;
1.723 +
1.724 + // If d2 < 0 we need to flip the orientation of our curve
1.725 + // This is done by negating the k and l values
1.726 + if ( d[2] > 0) {
1.727 + for (int i = 0; i < 4; ++i) {
1.728 + k[i] = -k[i];
1.729 + l[i] = -l[i];
1.730 + }
1.731 + }
1.732 +}
1.733 +
1.734 +// Calc coefficients of I(s,t) where roots of I are inflection points of curve
1.735 +// I(s,t) = t*(3*d0*s^2 - 3*d1*s*t + d2*t^2)
1.736 +// d0 = a1 - 2*a2+3*a3
1.737 +// d1 = -a2 + 3*a3
1.738 +// d2 = 3*a3
1.739 +// a1 = p0 . (p3 x p2)
1.740 +// a2 = p1 . (p0 x p3)
1.741 +// a3 = p2 . (p1 x p0)
1.742 +// Places the values of d1, d2, d3 in array d passed in
1.743 +static void calc_cubic_inflection_func(const SkPoint p[4], SkScalar d[3]) {
1.744 + SkScalar a1 = calc_dot_cross_cubic(p[0], p[3], p[2]);
1.745 + SkScalar a2 = calc_dot_cross_cubic(p[1], p[0], p[3]);
1.746 + SkScalar a3 = calc_dot_cross_cubic(p[2], p[1], p[0]);
1.747 +
1.748 + // need to scale a's or values in later calculations will grow to high
1.749 + SkScalar max = SkScalarAbs(a1);
1.750 + max = SkMaxScalar(max, SkScalarAbs(a2));
1.751 + max = SkMaxScalar(max, SkScalarAbs(a3));
1.752 + max = 1.f/max;
1.753 + a1 = a1 * max;
1.754 + a2 = a2 * max;
1.755 + a3 = a3 * max;
1.756 +
1.757 + d[2] = 3.f * a3;
1.758 + d[1] = d[2] - a2;
1.759 + d[0] = d[1] - a2 + a1;
1.760 +}
1.761 +
1.762 +int GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkScalar klm[9],
1.763 + SkScalar klm_rev[3]) {
1.764 + // Variable to store the two parametric values at the loop double point
1.765 + SkScalar smallS = 0.f;
1.766 + SkScalar largeS = 0.f;
1.767 +
1.768 + SkScalar d[3];
1.769 + calc_cubic_inflection_func(src, d);
1.770 +
1.771 + CubicType cType = classify_cubic(src, d);
1.772 +
1.773 + int chop_count = 0;
1.774 + if (kLoop_CubicType == cType) {
1.775 + SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]);
1.776 + SkScalar ls = d[1] - tempSqrt;
1.777 + SkScalar lt = 2.f * d[0];
1.778 + SkScalar ms = d[1] + tempSqrt;
1.779 + SkScalar mt = 2.f * d[0];
1.780 + ls = ls / lt;
1.781 + ms = ms / mt;
1.782 + // need to have t values sorted since this is what is expected by SkChopCubicAt
1.783 + if (ls <= ms) {
1.784 + smallS = ls;
1.785 + largeS = ms;
1.786 + } else {
1.787 + smallS = ms;
1.788 + largeS = ls;
1.789 + }
1.790 +
1.791 + SkScalar chop_ts[2];
1.792 + if (smallS > 0.f && smallS < 1.f) {
1.793 + chop_ts[chop_count++] = smallS;
1.794 + }
1.795 + if (largeS > 0.f && largeS < 1.f) {
1.796 + chop_ts[chop_count++] = largeS;
1.797 + }
1.798 + if(dst) {
1.799 + SkChopCubicAt(src, dst, chop_ts, chop_count);
1.800 + }
1.801 + } else {
1.802 + if (dst) {
1.803 + memcpy(dst, src, sizeof(SkPoint) * 4);
1.804 + }
1.805 + }
1.806 +
1.807 + if (klm && klm_rev) {
1.808 + // Set klm_rev to to match the sub_section of cubic that needs to have its orientation
1.809 + // flipped. This will always be the section that is the "loop"
1.810 + if (2 == chop_count) {
1.811 + klm_rev[0] = 1.f;
1.812 + klm_rev[1] = -1.f;
1.813 + klm_rev[2] = 1.f;
1.814 + } else if (1 == chop_count) {
1.815 + if (smallS < 0.f) {
1.816 + klm_rev[0] = -1.f;
1.817 + klm_rev[1] = 1.f;
1.818 + } else {
1.819 + klm_rev[0] = 1.f;
1.820 + klm_rev[1] = -1.f;
1.821 + }
1.822 + } else {
1.823 + if (smallS < 0.f && largeS > 1.f) {
1.824 + klm_rev[0] = -1.f;
1.825 + } else {
1.826 + klm_rev[0] = 1.f;
1.827 + }
1.828 + }
1.829 + SkScalar controlK[4];
1.830 + SkScalar controlL[4];
1.831 + SkScalar controlM[4];
1.832 +
1.833 + if (kSerpentine_CubicType == cType || (kCusp_CubicType == cType && 0.f != d[0])) {
1.834 + set_serp_klm(d, controlK, controlL, controlM);
1.835 + } else if (kLoop_CubicType == cType) {
1.836 + set_loop_klm(d, controlK, controlL, controlM);
1.837 + } else if (kCusp_CubicType == cType) {
1.838 + SkASSERT(0.f == d[0]);
1.839 + set_cusp_klm(d, controlK, controlL, controlM);
1.840 + } else if (kQuadratic_CubicType == cType) {
1.841 + set_quadratic_klm(d, controlK, controlL, controlM);
1.842 + }
1.843 +
1.844 + calc_cubic_klm(src, controlK, controlL, controlM, klm, &klm[3], &klm[6]);
1.845 + }
1.846 + return chop_count + 1;
1.847 +}
1.848 +
1.849 +void GrPathUtils::getCubicKLM(const SkPoint p[4], SkScalar klm[9]) {
1.850 + SkScalar d[3];
1.851 + calc_cubic_inflection_func(p, d);
1.852 +
1.853 + CubicType cType = classify_cubic(p, d);
1.854 +
1.855 + SkScalar controlK[4];
1.856 + SkScalar controlL[4];
1.857 + SkScalar controlM[4];
1.858 +
1.859 + if (kSerpentine_CubicType == cType || (kCusp_CubicType == cType && 0.f != d[0])) {
1.860 + set_serp_klm(d, controlK, controlL, controlM);
1.861 + } else if (kLoop_CubicType == cType) {
1.862 + set_loop_klm(d, controlK, controlL, controlM);
1.863 + } else if (kCusp_CubicType == cType) {
1.864 + SkASSERT(0.f == d[0]);
1.865 + set_cusp_klm(d, controlK, controlL, controlM);
1.866 + } else if (kQuadratic_CubicType == cType) {
1.867 + set_quadratic_klm(d, controlK, controlL, controlM);
1.868 + }
1.869 +
1.870 + calc_cubic_klm(p, controlK, controlL, controlM, klm, &klm[3], &klm[6]);
1.871 +}
