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 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 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 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 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 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 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 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)) 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 364 bool is_point_within_cubic_tangents(const SkPoint& a, 365 const SkVector& ab, 366 const SkVector& dc, 367 const SkPoint& d, 368 SkPathPriv::FirstDirection dir, 369 const SkPoint p) { 370 SkVector ap = p - a; 371 SkScalar apXab = ap.cross(ab); 372 if (SkPathPriv::kCW_FirstDirection == dir) { 373 if (apXab > 0) { 374 return false; 375 } 376 } else { 377 SkASSERT(SkPathPriv::kCCW_FirstDirection == dir); 378 if (apXab < 0) { 379 return false; 380 } 381 } 382 383 SkVector dp = p - d; 384 SkScalar dpXdc = dp.cross(dc); 385 if (SkPathPriv::kCW_FirstDirection == dir) { 386 if (dpXdc < 0) { 387 return false; 388 } 389 } else { 390 SkASSERT(SkPathPriv::kCCW_FirstDirection == dir); 391 if (dpXdc > 0) { 392 return false; 393 } 394 } 395 return true; 396 } 397 398 void convert_noninflect_cubic_to_quads(const SkPoint p[4], 399 SkScalar toleranceSqd, 400 bool constrainWithinTangents, 401 SkPathPriv::FirstDirection dir, 402 SkTArray<SkPoint, true>* quads, 403 int sublevel = 0) { 404 405 // Notation: Point a is always p[0]. Point b is p[1] unless p[1] == p[0], in which case it is 406 // p[2]. Point d is always p[3]. Point c is p[2] unless p[2] == p[3], in which case it is p[1]. 407 408 SkVector ab = p[1] - p[0]; 409 SkVector dc = p[2] - p[3]; 410 411 if (ab.lengthSqd() < SK_ScalarNearlyZero) { 412 if (dc.lengthSqd() < SK_ScalarNearlyZero) { 413 SkPoint* degQuad = quads->push_back_n(3); 414 degQuad[0] = p[0]; 415 degQuad[1] = p[0]; 416 degQuad[2] = p[3]; 417 return; 418 } 419 ab = p[2] - p[0]; 420 } 421 if (dc.lengthSqd() < SK_ScalarNearlyZero) { 422 dc = p[1] - p[3]; 423 } 424 425 // When the ab and cd tangents are degenerate or nearly parallel with vector from d to a the 426 // constraint that the quad point falls between the tangents becomes hard to enforce and we are 427 // likely to hit the max subdivision count. However, in this case the cubic is approaching a 428 // line and the accuracy of the quad point isn't so important. We check if the two middle cubic 429 // control points are very close to the baseline vector. If so then we just pick quadratic 430 // points on the control polygon. 431 432 if (constrainWithinTangents) { 433 SkVector da = p[0] - p[3]; 434 bool doQuads = dc.lengthSqd() < SK_ScalarNearlyZero || 435 ab.lengthSqd() < SK_ScalarNearlyZero; 436 if (!doQuads) { 437 SkScalar invDALengthSqd = da.lengthSqd(); 438 if (invDALengthSqd > SK_ScalarNearlyZero) { 439 invDALengthSqd = SkScalarInvert(invDALengthSqd); 440 // cross(ab, da)^2/length(da)^2 == sqd distance from b to line from d to a. 441 // same goes for point c using vector cd. 442 SkScalar detABSqd = ab.cross(da); 443 detABSqd = SkScalarSquare(detABSqd); 444 SkScalar detDCSqd = dc.cross(da); 445 detDCSqd = SkScalarSquare(detDCSqd); 446 if (SkScalarMul(detABSqd, invDALengthSqd) < toleranceSqd && 447 SkScalarMul(detDCSqd, invDALengthSqd) < toleranceSqd) { 448 doQuads = true; 449 } 450 } 451 } 452 if (doQuads) { 453 SkPoint b = p[0] + ab; 454 SkPoint c = p[3] + dc; 455 SkPoint mid = b + c; 456 mid.scale(SK_ScalarHalf); 457 // Insert two quadratics to cover the case when ab points away from d and/or dc 458 // points away from a. 459 if (SkVector::DotProduct(da, dc) < 0 || SkVector::DotProduct(ab,da) > 0) { 460 SkPoint* qpts = quads->push_back_n(6); 461 qpts[0] = p[0]; 462 qpts[1] = b; 463 qpts[2] = mid; 464 qpts[3] = mid; 465 qpts[4] = c; 466 qpts[5] = p[3]; 467 } else { 468 SkPoint* qpts = quads->push_back_n(3); 469 qpts[0] = p[0]; 470 qpts[1] = mid; 471 qpts[2] = p[3]; 472 } 473 return; 474 } 475 } 476 477 static const SkScalar kLengthScale = 3 * SK_Scalar1 / 2; 478 static const int kMaxSubdivs = 10; 479 480 ab.scale(kLengthScale); 481 dc.scale(kLengthScale); 482 483 // e0 and e1 are extrapolations along vectors ab and dc. 484 SkVector c0 = p[0]; 485 c0 += ab; 486 SkVector c1 = p[3]; 487 c1 += dc; 488 489 SkScalar dSqd = sublevel > kMaxSubdivs ? 0 : c0.distanceToSqd(c1); 490 if (dSqd < toleranceSqd) { 491 SkPoint cAvg = c0; 492 cAvg += c1; 493 cAvg.scale(SK_ScalarHalf); 494 495 bool subdivide = false; 496 497 if (constrainWithinTangents && 498 !is_point_within_cubic_tangents(p[0], ab, dc, p[3], dir, cAvg)) { 499 // choose a new cAvg that is the intersection of the two tangent lines. 500 ab.setOrthog(ab); 501 SkScalar z0 = -ab.dot(p[0]); 502 dc.setOrthog(dc); 503 SkScalar z1 = -dc.dot(p[3]); 504 cAvg.fX = SkScalarMul(ab.fY, z1) - SkScalarMul(z0, dc.fY); 505 cAvg.fY = SkScalarMul(z0, dc.fX) - SkScalarMul(ab.fX, z1); 506 SkScalar z = SkScalarMul(ab.fX, dc.fY) - SkScalarMul(ab.fY, dc.fX); 507 z = SkScalarInvert(z); 508 cAvg.fX *= z; 509 cAvg.fY *= z; 510 if (sublevel <= kMaxSubdivs) { 511 SkScalar d0Sqd = c0.distanceToSqd(cAvg); 512 SkScalar d1Sqd = c1.distanceToSqd(cAvg); 513 // We need to subdivide if d0 + d1 > tolerance but we have the sqd values. We know 514 // the distances and tolerance can't be negative. 515 // (d0 + d1)^2 > toleranceSqd 516 // d0Sqd + 2*d0*d1 + d1Sqd > toleranceSqd 517 SkScalar d0d1 = SkScalarSqrt(SkScalarMul(d0Sqd, d1Sqd)); 518 subdivide = 2 * d0d1 + d0Sqd + d1Sqd > toleranceSqd; 519 } 520 } 521 if (!subdivide) { 522 SkPoint* pts = quads->push_back_n(3); 523 pts[0] = p[0]; 524 pts[1] = cAvg; 525 pts[2] = p[3]; 526 return; 527 } 528 } 529 SkPoint choppedPts[7]; 530 SkChopCubicAtHalf(p, choppedPts); 531 convert_noninflect_cubic_to_quads(choppedPts + 0, 532 toleranceSqd, 533 constrainWithinTangents, 534 dir, 535 quads, 536 sublevel + 1); 537 convert_noninflect_cubic_to_quads(choppedPts + 3, 538 toleranceSqd, 539 constrainWithinTangents, 540 dir, 541 quads, 542 sublevel + 1); 543 } 544 } 545 546 void GrPathUtils::convertCubicToQuads(const SkPoint p[4], 547 SkScalar tolScale, 548 SkTArray<SkPoint, true>* quads) { 549 SkPoint chopped[10]; 550 int count = SkChopCubicAtInflections(p, chopped); 551 552 const SkScalar tolSqd = SkScalarSquare(tolScale); 553 554 for (int i = 0; i < count; ++i) { 555 SkPoint* cubic = chopped + 3*i; 556 // The direction param is ignored if the third param is false. 557 convert_noninflect_cubic_to_quads(cubic, tolSqd, false, 558 SkPathPriv::kCCW_FirstDirection, quads); 559 } 560 } 561 562 void GrPathUtils::convertCubicToQuadsConstrainToTangents(const SkPoint p[4], 563 SkScalar tolScale, 564 SkPathPriv::FirstDirection dir, 565 SkTArray<SkPoint, true>* quads) { 566 SkPoint chopped[10]; 567 int count = SkChopCubicAtInflections(p, chopped); 568 569 const SkScalar tolSqd = SkScalarSquare(tolScale); 570 571 for (int i = 0; i < count; ++i) { 572 SkPoint* cubic = chopped + 3*i; 573 convert_noninflect_cubic_to_quads(cubic, tolSqd, true, dir, quads); 574 } 575 } 576 577 //////////////////////////////////////////////////////////////////////////////// 578 579 // Solves linear system to extract klm 580 // P.K = k (similarly for l, m) 581 // Where P is matrix of control points 582 // K is coefficients for the line K 583 // k is vector of values of K evaluated at the control points 584 // Solving for K, thus K = P^(-1) . k 585 static void calc_cubic_klm(const SkPoint p[4], const SkScalar controlK[4], 586 const SkScalar controlL[4], const SkScalar controlM[4], 587 SkScalar k[3], SkScalar l[3], SkScalar m[3]) { 588 SkMatrix matrix; 589 matrix.setAll(p[0].fX, p[0].fY, 1.f, 590 p[1].fX, p[1].fY, 1.f, 591 p[2].fX, p[2].fY, 1.f); 592 SkMatrix inverse; 593 if (matrix.invert(&inverse)) { 594 inverse.mapHomogeneousPoints(k, controlK, 1); 595 inverse.mapHomogeneousPoints(l, controlL, 1); 596 inverse.mapHomogeneousPoints(m, controlM, 1); 597 } 598 599 } 600 601 static void set_serp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 602 SkScalar tempSqrt = SkScalarSqrt(9.f * d[1] * d[1] - 12.f * d[0] * d[2]); 603 SkScalar ls = 3.f * d[1] - tempSqrt; 604 SkScalar lt = 6.f * d[0]; 605 SkScalar ms = 3.f * d[1] + tempSqrt; 606 SkScalar mt = 6.f * d[0]; 607 608 k[0] = ls * ms; 609 k[1] = (3.f * ls * ms - ls * mt - lt * ms) / 3.f; 610 k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f; 611 k[3] = (lt - ls) * (mt - ms); 612 613 l[0] = ls * ls * ls; 614 const SkScalar lt_ls = lt - ls; 615 l[1] = ls * ls * lt_ls * -1.f; 616 l[2] = lt_ls * lt_ls * ls; 617 l[3] = -1.f * lt_ls * lt_ls * lt_ls; 618 619 m[0] = ms * ms * ms; 620 const SkScalar mt_ms = mt - ms; 621 m[1] = ms * ms * mt_ms * -1.f; 622 m[2] = mt_ms * mt_ms * ms; 623 m[3] = -1.f * mt_ms * mt_ms * mt_ms; 624 625 // If d0 < 0 we need to flip the orientation of our curve 626 // This is done by negating the k and l values 627 // We want negative distance values to be on the inside 628 if ( d[0] > 0) { 629 for (int i = 0; i < 4; ++i) { 630 k[i] = -k[i]; 631 l[i] = -l[i]; 632 } 633 } 634 } 635 636 static void set_loop_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 637 SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]); 638 SkScalar ls = d[1] - tempSqrt; 639 SkScalar lt = 2.f * d[0]; 640 SkScalar ms = d[1] + tempSqrt; 641 SkScalar mt = 2.f * d[0]; 642 643 k[0] = ls * ms; 644 k[1] = (3.f * ls*ms - ls * mt - lt * ms) / 3.f; 645 k[2] = (lt * (mt - 2.f * ms) + ls * (3.f * ms - 2.f * mt)) / 3.f; 646 k[3] = (lt - ls) * (mt - ms); 647 648 l[0] = ls * ls * ms; 649 l[1] = (ls * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/-3.f; 650 l[2] = ((lt - ls) * (ls * (2.f * mt - 3.f * ms) + lt * ms))/3.f; 651 l[3] = -1.f * (lt - ls) * (lt - ls) * (mt - ms); 652 653 m[0] = ls * ms * ms; 654 m[1] = (ms * (ls * (2.f * mt - 3.f * ms) + lt * ms))/-3.f; 655 m[2] = ((mt - ms) * (ls * (mt - 3.f * ms) + 2.f * lt * ms))/3.f; 656 m[3] = -1.f * (lt - ls) * (mt - ms) * (mt - ms); 657 658 659 // If (d0 < 0 && sign(k1) > 0) || (d0 > 0 && sign(k1) < 0), 660 // we need to flip the orientation of our curve. 661 // This is done by negating the k and l values 662 if ( (d[0] < 0 && k[1] > 0) || (d[0] > 0 && k[1] < 0)) { 663 for (int i = 0; i < 4; ++i) { 664 k[i] = -k[i]; 665 l[i] = -l[i]; 666 } 667 } 668 } 669 670 static void set_cusp_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 671 const SkScalar ls = d[2]; 672 const SkScalar lt = 3.f * d[1]; 673 674 k[0] = ls; 675 k[1] = ls - lt / 3.f; 676 k[2] = ls - 2.f * lt / 3.f; 677 k[3] = ls - lt; 678 679 l[0] = ls * ls * ls; 680 const SkScalar ls_lt = ls - lt; 681 l[1] = ls * ls * ls_lt; 682 l[2] = ls_lt * ls_lt * ls; 683 l[3] = ls_lt * ls_lt * ls_lt; 684 685 m[0] = 1.f; 686 m[1] = 1.f; 687 m[2] = 1.f; 688 m[3] = 1.f; 689 } 690 691 // For the case when a cubic is actually a quadratic 692 // M = 693 // 0 0 0 694 // 1/3 0 1/3 695 // 2/3 1/3 2/3 696 // 1 1 1 697 static void set_quadratic_klm(const SkScalar d[3], SkScalar k[4], SkScalar l[4], SkScalar m[4]) { 698 k[0] = 0.f; 699 k[1] = 1.f/3.f; 700 k[2] = 2.f/3.f; 701 k[3] = 1.f; 702 703 l[0] = 0.f; 704 l[1] = 0.f; 705 l[2] = 1.f/3.f; 706 l[3] = 1.f; 707 708 m[0] = 0.f; 709 m[1] = 1.f/3.f; 710 m[2] = 2.f/3.f; 711 m[3] = 1.f; 712 713 // If d2 < 0 we need to flip the orientation of our curve 714 // This is done by negating the k and l values 715 if ( d[2] > 0) { 716 for (int i = 0; i < 4; ++i) { 717 k[i] = -k[i]; 718 l[i] = -l[i]; 719 } 720 } 721 } 722 723 int GrPathUtils::chopCubicAtLoopIntersection(const SkPoint src[4], SkPoint dst[10], SkScalar klm[9], 724 SkScalar klm_rev[3]) { 725 // Variable to store the two parametric values at the loop double point 726 SkScalar smallS = 0.f; 727 SkScalar largeS = 0.f; 728 729 SkScalar d[3]; 730 SkCubicType cType = SkClassifyCubic(src, d); 731 732 int chop_count = 0; 733 if (kLoop_SkCubicType == cType) { 734 SkScalar tempSqrt = SkScalarSqrt(4.f * d[0] * d[2] - 3.f * d[1] * d[1]); 735 SkScalar ls = d[1] - tempSqrt; 736 SkScalar lt = 2.f * d[0]; 737 SkScalar ms = d[1] + tempSqrt; 738 SkScalar mt = 2.f * d[0]; 739 ls = ls / lt; 740 ms = ms / mt; 741 // need to have t values sorted since this is what is expected by SkChopCubicAt 742 if (ls <= ms) { 743 smallS = ls; 744 largeS = ms; 745 } else { 746 smallS = ms; 747 largeS = ls; 748 } 749 750 SkScalar chop_ts[2]; 751 if (smallS > 0.f && smallS < 1.f) { 752 chop_ts[chop_count++] = smallS; 753 } 754 if (largeS > 0.f && largeS < 1.f) { 755 chop_ts[chop_count++] = largeS; 756 } 757 if(dst) { 758 SkChopCubicAt(src, dst, chop_ts, chop_count); 759 } 760 } else { 761 if (dst) { 762 memcpy(dst, src, sizeof(SkPoint) * 4); 763 } 764 } 765 766 if (klm && klm_rev) { 767 // Set klm_rev to to match the sub_section of cubic that needs to have its orientation 768 // flipped. This will always be the section that is the "loop" 769 if (2 == chop_count) { 770 klm_rev[0] = 1.f; 771 klm_rev[1] = -1.f; 772 klm_rev[2] = 1.f; 773 } else if (1 == chop_count) { 774 if (smallS < 0.f) { 775 klm_rev[0] = -1.f; 776 klm_rev[1] = 1.f; 777 } else { 778 klm_rev[0] = 1.f; 779 klm_rev[1] = -1.f; 780 } 781 } else { 782 if (smallS < 0.f && largeS > 1.f) { 783 klm_rev[0] = -1.f; 784 } else { 785 klm_rev[0] = 1.f; 786 } 787 } 788 SkScalar controlK[4]; 789 SkScalar controlL[4]; 790 SkScalar controlM[4]; 791 792 if (kSerpentine_SkCubicType == cType || (kCusp_SkCubicType == cType && 0.f != d[0])) { 793 set_serp_klm(d, controlK, controlL, controlM); 794 } else if (kLoop_SkCubicType == cType) { 795 set_loop_klm(d, controlK, controlL, controlM); 796 } else if (kCusp_SkCubicType == cType) { 797 SkASSERT(0.f == d[0]); 798 set_cusp_klm(d, controlK, controlL, controlM); 799 } else if (kQuadratic_SkCubicType == cType) { 800 set_quadratic_klm(d, controlK, controlL, controlM); 801 } 802 803 calc_cubic_klm(src, controlK, controlL, controlM, klm, &klm[3], &klm[6]); 804 } 805 return chop_count + 1; 806 } 807 808 void GrPathUtils::getCubicKLM(const SkPoint p[4], SkScalar klm[9]) { 809 SkScalar d[3]; 810 SkCubicType cType = SkClassifyCubic(p, d); 811 812 SkScalar controlK[4]; 813 SkScalar controlL[4]; 814 SkScalar controlM[4]; 815 816 if (kSerpentine_SkCubicType == cType || (kCusp_SkCubicType == cType && 0.f != d[0])) { 817 set_serp_klm(d, controlK, controlL, controlM); 818 } else if (kLoop_SkCubicType == cType) { 819 set_loop_klm(d, controlK, controlL, controlM); 820 } else if (kCusp_SkCubicType == cType) { 821 SkASSERT(0.f == d[0]); 822 set_cusp_klm(d, controlK, controlL, controlM); 823 } else if (kQuadratic_SkCubicType == cType) { 824 set_quadratic_klm(d, controlK, controlL, controlM); 825 } 826 827 calc_cubic_klm(p, controlK, controlL, controlM, klm, &klm[3], &klm[6]); 828 } 829
