1 /* libs/graphics/sgl/SkGeometry.cpp 2 ** 3 ** Copyright 2006, The Android Open Source Project 4 ** 5 ** Licensed under the Apache License, Version 2.0 (the "License"); 6 ** you may not use this file except in compliance with the License. 7 ** You may obtain a copy of the License at 8 ** 9 ** http://www.apache.org/licenses/LICENSE-2.0 10 ** 11 ** Unless required by applicable law or agreed to in writing, software 12 ** distributed under the License is distributed on an "AS IS" BASIS, 13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 ** See the License for the specific language governing permissions and 15 ** limitations under the License. 16 */ 17 18 #include "SkGeometry.h" 19 #include "Sk64.h" 20 #include "SkMatrix.h" 21 22 bool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2]) { 23 // Determine quick discards. 24 // Consider query line going exactly through point 0 to not 25 // intersect, for symmetry with SkXRayCrossesMonotonicCubic. 26 if (pt.fY == pts[0].fY) 27 return false; 28 if (pt.fY < pts[0].fY && pt.fY < pts[1].fY) 29 return false; 30 if (pt.fY > pts[0].fY && pt.fY > pts[1].fY) 31 return false; 32 if (pt.fX > pts[0].fX && pt.fX > pts[1].fX) 33 return false; 34 // Determine degenerate cases 35 if (SkScalarNearlyZero(pts[0].fY - pts[1].fY)) 36 return false; 37 if (SkScalarNearlyZero(pts[0].fX - pts[1].fX)) 38 // We've already determined the query point lies within the 39 // vertical range of the line segment. 40 return pt.fX <= pts[0].fX; 41 // Full line segment evaluation 42 SkScalar delta_y = pts[1].fY - pts[0].fY; 43 SkScalar delta_x = pts[1].fX - pts[0].fX; 44 SkScalar slope = SkScalarDiv(delta_y, delta_x); 45 SkScalar b = pts[0].fY - SkScalarMul(slope, pts[0].fX); 46 // Solve for x coordinate at y = pt.fY 47 SkScalar x = SkScalarDiv(pt.fY - b, slope); 48 return pt.fX <= x; 49 } 50 51 /** If defined, this makes eval_quad and eval_cubic do more setup (sometimes 52 involving integer multiplies by 2 or 3, but fewer calls to SkScalarMul. 53 May also introduce overflow of fixed when we compute our setup. 54 */ 55 #ifdef SK_SCALAR_IS_FIXED 56 #define DIRECT_EVAL_OF_POLYNOMIALS 57 #endif 58 59 //////////////////////////////////////////////////////////////////////// 60 61 #ifdef SK_SCALAR_IS_FIXED 62 static int is_not_monotonic(int a, int b, int c, int d) 63 { 64 return (((a - b) | (b - c) | (c - d)) & ((b - a) | (c - b) | (d - c))) >> 31; 65 } 66 67 static int is_not_monotonic(int a, int b, int c) 68 { 69 return (((a - b) | (b - c)) & ((b - a) | (c - b))) >> 31; 70 } 71 #else 72 static int is_not_monotonic(float a, float b, float c) 73 { 74 float ab = a - b; 75 float bc = b - c; 76 if (ab < 0) 77 bc = -bc; 78 return ab == 0 || bc < 0; 79 } 80 #endif 81 82 //////////////////////////////////////////////////////////////////////// 83 84 static bool is_unit_interval(SkScalar x) 85 { 86 return x > 0 && x < SK_Scalar1; 87 } 88 89 static int valid_unit_divide(SkScalar numer, SkScalar denom, SkScalar* ratio) 90 { 91 SkASSERT(ratio); 92 93 if (numer < 0) 94 { 95 numer = -numer; 96 denom = -denom; 97 } 98 99 if (denom == 0 || numer == 0 || numer >= denom) 100 return 0; 101 102 SkScalar r = SkScalarDiv(numer, denom); 103 if (SkScalarIsNaN(r)) { 104 return 0; 105 } 106 SkASSERT(r >= 0 && r < SK_Scalar1); 107 if (r == 0) // catch underflow if numer <<<< denom 108 return 0; 109 *ratio = r; 110 return 1; 111 } 112 113 /** From Numerical Recipes in C. 114 115 Q = -1/2 (B + sign(B) sqrt[B*B - 4*A*C]) 116 x1 = Q / A 117 x2 = C / Q 118 */ 119 int SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]) 120 { 121 SkASSERT(roots); 122 123 if (A == 0) 124 return valid_unit_divide(-C, B, roots); 125 126 SkScalar* r = roots; 127 128 #ifdef SK_SCALAR_IS_FLOAT 129 float R = B*B - 4*A*C; 130 if (R < 0 || SkScalarIsNaN(R)) { // complex roots 131 return 0; 132 } 133 R = sk_float_sqrt(R); 134 #else 135 Sk64 RR, tmp; 136 137 RR.setMul(B,B); 138 tmp.setMul(A,C); 139 tmp.shiftLeft(2); 140 RR.sub(tmp); 141 if (RR.isNeg()) 142 return 0; 143 SkFixed R = RR.getSqrt(); 144 #endif 145 146 SkScalar Q = (B < 0) ? -(B-R)/2 : -(B+R)/2; 147 r += valid_unit_divide(Q, A, r); 148 r += valid_unit_divide(C, Q, r); 149 if (r - roots == 2) 150 { 151 if (roots[0] > roots[1]) 152 SkTSwap<SkScalar>(roots[0], roots[1]); 153 else if (roots[0] == roots[1]) // nearly-equal? 154 r -= 1; // skip the double root 155 } 156 return (int)(r - roots); 157 } 158 159 #ifdef SK_SCALAR_IS_FIXED 160 /** Trim A/B/C down so that they are all <= 32bits 161 and then call SkFindUnitQuadRoots() 162 */ 163 static int Sk64FindFixedQuadRoots(const Sk64& A, const Sk64& B, const Sk64& C, SkFixed roots[2]) 164 { 165 int na = A.shiftToMake32(); 166 int nb = B.shiftToMake32(); 167 int nc = C.shiftToMake32(); 168 169 int shift = SkMax32(na, SkMax32(nb, nc)); 170 SkASSERT(shift >= 0); 171 172 return SkFindUnitQuadRoots(A.getShiftRight(shift), B.getShiftRight(shift), C.getShiftRight(shift), roots); 173 } 174 #endif 175 176 ///////////////////////////////////////////////////////////////////////////////////// 177 ///////////////////////////////////////////////////////////////////////////////////// 178 179 static SkScalar eval_quad(const SkScalar src[], SkScalar t) 180 { 181 SkASSERT(src); 182 SkASSERT(t >= 0 && t <= SK_Scalar1); 183 184 #ifdef DIRECT_EVAL_OF_POLYNOMIALS 185 SkScalar C = src[0]; 186 SkScalar A = src[4] - 2 * src[2] + C; 187 SkScalar B = 2 * (src[2] - C); 188 return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 189 #else 190 SkScalar ab = SkScalarInterp(src[0], src[2], t); 191 SkScalar bc = SkScalarInterp(src[2], src[4], t); 192 return SkScalarInterp(ab, bc, t); 193 #endif 194 } 195 196 static SkScalar eval_quad_derivative(const SkScalar src[], SkScalar t) 197 { 198 SkScalar A = src[4] - 2 * src[2] + src[0]; 199 SkScalar B = src[2] - src[0]; 200 201 return 2 * SkScalarMulAdd(A, t, B); 202 } 203 204 static SkScalar eval_quad_derivative_at_half(const SkScalar src[]) 205 { 206 SkScalar A = src[4] - 2 * src[2] + src[0]; 207 SkScalar B = src[2] - src[0]; 208 return A + 2 * B; 209 } 210 211 void SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent) 212 { 213 SkASSERT(src); 214 SkASSERT(t >= 0 && t <= SK_Scalar1); 215 216 if (pt) 217 pt->set(eval_quad(&src[0].fX, t), eval_quad(&src[0].fY, t)); 218 if (tangent) 219 tangent->set(eval_quad_derivative(&src[0].fX, t), 220 eval_quad_derivative(&src[0].fY, t)); 221 } 222 223 void SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, SkVector* tangent) 224 { 225 SkASSERT(src); 226 227 if (pt) 228 { 229 SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 230 SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 231 SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 232 SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 233 pt->set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); 234 } 235 if (tangent) 236 tangent->set(eval_quad_derivative_at_half(&src[0].fX), 237 eval_quad_derivative_at_half(&src[0].fY)); 238 } 239 240 static void interp_quad_coords(const SkScalar* src, SkScalar* dst, SkScalar t) 241 { 242 SkScalar ab = SkScalarInterp(src[0], src[2], t); 243 SkScalar bc = SkScalarInterp(src[2], src[4], t); 244 245 dst[0] = src[0]; 246 dst[2] = ab; 247 dst[4] = SkScalarInterp(ab, bc, t); 248 dst[6] = bc; 249 dst[8] = src[4]; 250 } 251 252 void SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t) 253 { 254 SkASSERT(t > 0 && t < SK_Scalar1); 255 256 interp_quad_coords(&src[0].fX, &dst[0].fX, t); 257 interp_quad_coords(&src[0].fY, &dst[0].fY, t); 258 } 259 260 void SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]) 261 { 262 SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 263 SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 264 SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 265 SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 266 267 dst[0] = src[0]; 268 dst[1].set(x01, y01); 269 dst[2].set(SkScalarAve(x01, x12), SkScalarAve(y01, y12)); 270 dst[3].set(x12, y12); 271 dst[4] = src[2]; 272 } 273 274 /** Quad'(t) = At + B, where 275 A = 2(a - 2b + c) 276 B = 2(b - a) 277 Solve for t, only if it fits between 0 < t < 1 278 */ 279 int SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValue[1]) 280 { 281 /* At + B == 0 282 t = -B / A 283 */ 284 #ifdef SK_SCALAR_IS_FIXED 285 return is_not_monotonic(a, b, c) && valid_unit_divide(a - b, a - b - b + c, tValue); 286 #else 287 return valid_unit_divide(a - b, a - b - b + c, tValue); 288 #endif 289 } 290 291 static inline void flatten_double_quad_extrema(SkScalar coords[14]) 292 { 293 coords[2] = coords[6] = coords[4]; 294 } 295 296 /* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 297 stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 298 */ 299 int SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]) 300 { 301 SkASSERT(src); 302 SkASSERT(dst); 303 304 #if 0 305 static bool once = true; 306 if (once) 307 { 308 once = false; 309 SkPoint s[3] = { 0, 26398, 0, 26331, 0, 20621428 }; 310 SkPoint d[6]; 311 312 int n = SkChopQuadAtYExtrema(s, d); 313 SkDebugf("chop=%d, Y=[%x %x %x %x %x %x]\n", n, d[0].fY, d[1].fY, d[2].fY, d[3].fY, d[4].fY, d[5].fY); 314 } 315 #endif 316 317 SkScalar a = src[0].fY; 318 SkScalar b = src[1].fY; 319 SkScalar c = src[2].fY; 320 321 if (is_not_monotonic(a, b, c)) 322 { 323 SkScalar tValue; 324 if (valid_unit_divide(a - b, a - b - b + c, &tValue)) 325 { 326 SkChopQuadAt(src, dst, tValue); 327 flatten_double_quad_extrema(&dst[0].fY); 328 return 1; 329 } 330 // if we get here, we need to force dst to be monotonic, even though 331 // we couldn't compute a unit_divide value (probably underflow). 332 b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 333 } 334 dst[0].set(src[0].fX, a); 335 dst[1].set(src[1].fX, b); 336 dst[2].set(src[2].fX, c); 337 return 0; 338 } 339 340 /* Returns 0 for 1 quad, and 1 for two quads, either way the answer is 341 stored in dst[]. Guarantees that the 1/2 quads will be monotonic. 342 */ 343 int SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]) 344 { 345 SkASSERT(src); 346 SkASSERT(dst); 347 348 SkScalar a = src[0].fX; 349 SkScalar b = src[1].fX; 350 SkScalar c = src[2].fX; 351 352 if (is_not_monotonic(a, b, c)) { 353 SkScalar tValue; 354 if (valid_unit_divide(a - b, a - b - b + c, &tValue)) { 355 SkChopQuadAt(src, dst, tValue); 356 flatten_double_quad_extrema(&dst[0].fX); 357 return 1; 358 } 359 // if we get here, we need to force dst to be monotonic, even though 360 // we couldn't compute a unit_divide value (probably underflow). 361 b = SkScalarAbs(a - b) < SkScalarAbs(b - c) ? a : c; 362 } 363 dst[0].set(a, src[0].fY); 364 dst[1].set(b, src[1].fY); 365 dst[2].set(c, src[2].fY); 366 return 0; 367 } 368 369 // F(t) = a (1 - t) ^ 2 + 2 b t (1 - t) + c t ^ 2 370 // F'(t) = 2 (b - a) + 2 (a - 2b + c) t 371 // F''(t) = 2 (a - 2b + c) 372 // 373 // A = 2 (b - a) 374 // B = 2 (a - 2b + c) 375 // 376 // Maximum curvature for a quadratic means solving 377 // Fx' Fx'' + Fy' Fy'' = 0 378 // 379 // t = - (Ax Bx + Ay By) / (Bx ^ 2 + By ^ 2) 380 // 381 int SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]) 382 { 383 SkScalar Ax = src[1].fX - src[0].fX; 384 SkScalar Ay = src[1].fY - src[0].fY; 385 SkScalar Bx = src[0].fX - src[1].fX - src[1].fX + src[2].fX; 386 SkScalar By = src[0].fY - src[1].fY - src[1].fY + src[2].fY; 387 SkScalar t = 0; // 0 means don't chop 388 389 #ifdef SK_SCALAR_IS_FLOAT 390 (void)valid_unit_divide(-(Ax * Bx + Ay * By), Bx * Bx + By * By, &t); 391 #else 392 // !!! should I use SkFloat here? seems like it 393 Sk64 numer, denom, tmp; 394 395 numer.setMul(Ax, -Bx); 396 tmp.setMul(Ay, -By); 397 numer.add(tmp); 398 399 if (numer.isPos()) // do nothing if numer <= 0 400 { 401 denom.setMul(Bx, Bx); 402 tmp.setMul(By, By); 403 denom.add(tmp); 404 SkASSERT(!denom.isNeg()); 405 if (numer < denom) 406 { 407 t = numer.getFixedDiv(denom); 408 SkASSERT(t >= 0 && t <= SK_Fixed1); // assert that we're numerically stable (ha!) 409 if ((unsigned)t >= SK_Fixed1) // runtime check for numerical stability 410 t = 0; // ignore the chop 411 } 412 } 413 #endif 414 415 if (t == 0) 416 { 417 memcpy(dst, src, 3 * sizeof(SkPoint)); 418 return 1; 419 } 420 else 421 { 422 SkChopQuadAt(src, dst, t); 423 return 2; 424 } 425 } 426 427 void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) 428 { 429 SkScalar two = SkIntToScalar(2); 430 SkScalar one_third = SkScalarDiv(SK_Scalar1, SkIntToScalar(3)); 431 dst[0].set(src[0].fX, src[0].fY); 432 dst[1].set( 433 SkScalarMul(SkScalarMulAdd(src[1].fX, two, src[0].fX), one_third), 434 SkScalarMul(SkScalarMulAdd(src[1].fY, two, src[0].fY), one_third)); 435 dst[2].set( 436 SkScalarMul(SkScalarMulAdd(src[1].fX, two, src[2].fX), one_third), 437 SkScalarMul(SkScalarMulAdd(src[1].fY, two, src[2].fY), one_third)); 438 dst[3].set(src[2].fX, src[2].fY); 439 } 440 441 //////////////////////////////////////////////////////////////////////////////////////// 442 ///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS ///// 443 //////////////////////////////////////////////////////////////////////////////////////// 444 445 static void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4]) 446 { 447 coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0]; 448 coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]); 449 coeff[2] = 3*(pt[2] - pt[0]); 450 coeff[3] = pt[0]; 451 } 452 453 void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]) 454 { 455 SkASSERT(pts); 456 457 if (cx) 458 get_cubic_coeff(&pts[0].fX, cx); 459 if (cy) 460 get_cubic_coeff(&pts[0].fY, cy); 461 } 462 463 static SkScalar eval_cubic(const SkScalar src[], SkScalar t) 464 { 465 SkASSERT(src); 466 SkASSERT(t >= 0 && t <= SK_Scalar1); 467 468 if (t == 0) 469 return src[0]; 470 471 #ifdef DIRECT_EVAL_OF_POLYNOMIALS 472 SkScalar D = src[0]; 473 SkScalar A = src[6] + 3*(src[2] - src[4]) - D; 474 SkScalar B = 3*(src[4] - src[2] - src[2] + D); 475 SkScalar C = 3*(src[2] - D); 476 477 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 478 #else 479 SkScalar ab = SkScalarInterp(src[0], src[2], t); 480 SkScalar bc = SkScalarInterp(src[2], src[4], t); 481 SkScalar cd = SkScalarInterp(src[4], src[6], t); 482 SkScalar abc = SkScalarInterp(ab, bc, t); 483 SkScalar bcd = SkScalarInterp(bc, cd, t); 484 return SkScalarInterp(abc, bcd, t); 485 #endif 486 } 487 488 /** return At^2 + Bt + C 489 */ 490 static SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t) 491 { 492 SkASSERT(t >= 0 && t <= SK_Scalar1); 493 494 return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 495 } 496 497 static SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t) 498 { 499 SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 500 SkScalar B = 2*(src[4] - 2 * src[2] + src[0]); 501 SkScalar C = src[2] - src[0]; 502 503 return eval_quadratic(A, B, C, t); 504 } 505 506 static SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t) 507 { 508 SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 509 SkScalar B = src[4] - 2 * src[2] + src[0]; 510 511 return SkScalarMulAdd(A, t, B); 512 } 513 514 void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, SkVector* tangent, SkVector* curvature) 515 { 516 SkASSERT(src); 517 SkASSERT(t >= 0 && t <= SK_Scalar1); 518 519 if (loc) 520 loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t)); 521 if (tangent) 522 tangent->set(eval_cubic_derivative(&src[0].fX, t), 523 eval_cubic_derivative(&src[0].fY, t)); 524 if (curvature) 525 curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t), 526 eval_cubic_2ndDerivative(&src[0].fY, t)); 527 } 528 529 /** Cubic'(t) = At^2 + Bt + C, where 530 A = 3(-a + 3(b - c) + d) 531 B = 6(a - 2b + c) 532 C = 3(b - a) 533 Solve for t, keeping only those that fit betwee 0 < t < 1 534 */ 535 int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar tValues[2]) 536 { 537 #ifdef SK_SCALAR_IS_FIXED 538 if (!is_not_monotonic(a, b, c, d)) 539 return 0; 540 #endif 541 542 // we divide A,B,C by 3 to simplify 543 SkScalar A = d - a + 3*(b - c); 544 SkScalar B = 2*(a - b - b + c); 545 SkScalar C = b - a; 546 547 return SkFindUnitQuadRoots(A, B, C, tValues); 548 } 549 550 static void interp_cubic_coords(const SkScalar* src, SkScalar* dst, SkScalar t) 551 { 552 SkScalar ab = SkScalarInterp(src[0], src[2], t); 553 SkScalar bc = SkScalarInterp(src[2], src[4], t); 554 SkScalar cd = SkScalarInterp(src[4], src[6], t); 555 SkScalar abc = SkScalarInterp(ab, bc, t); 556 SkScalar bcd = SkScalarInterp(bc, cd, t); 557 SkScalar abcd = SkScalarInterp(abc, bcd, t); 558 559 dst[0] = src[0]; 560 dst[2] = ab; 561 dst[4] = abc; 562 dst[6] = abcd; 563 dst[8] = bcd; 564 dst[10] = cd; 565 dst[12] = src[6]; 566 } 567 568 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t) 569 { 570 SkASSERT(t > 0 && t < SK_Scalar1); 571 572 interp_cubic_coords(&src[0].fX, &dst[0].fX, t); 573 interp_cubic_coords(&src[0].fY, &dst[0].fY, t); 574 } 575 576 /* http://code.google.com/p/skia/issues/detail?id=32 577 578 This test code would fail when we didn't check the return result of 579 valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is 580 that after the first chop, the parameters to valid_unit_divide are equal 581 (thanks to finite float precision and rounding in the subtracts). Thus 582 even though the 2nd tValue looks < 1.0, after we renormalize it, we end 583 up with 1.0, hence the need to check and just return the last cubic as 584 a degenerate clump of 4 points in the sampe place. 585 586 static void test_cubic() { 587 SkPoint src[4] = { 588 { 556.25000, 523.03003 }, 589 { 556.23999, 522.96002 }, 590 { 556.21997, 522.89001 }, 591 { 556.21997, 522.82001 } 592 }; 593 SkPoint dst[10]; 594 SkScalar tval[] = { 0.33333334f, 0.99999994f }; 595 SkChopCubicAt(src, dst, tval, 2); 596 } 597 */ 598 599 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar tValues[], int roots) 600 { 601 #ifdef SK_DEBUG 602 { 603 for (int i = 0; i < roots - 1; i++) 604 { 605 SkASSERT(is_unit_interval(tValues[i])); 606 SkASSERT(is_unit_interval(tValues[i+1])); 607 SkASSERT(tValues[i] < tValues[i+1]); 608 } 609 } 610 #endif 611 612 if (dst) 613 { 614 if (roots == 0) // nothing to chop 615 memcpy(dst, src, 4*sizeof(SkPoint)); 616 else 617 { 618 SkScalar t = tValues[0]; 619 SkPoint tmp[4]; 620 621 for (int i = 0; i < roots; i++) 622 { 623 SkChopCubicAt(src, dst, t); 624 if (i == roots - 1) 625 break; 626 627 dst += 3; 628 // have src point to the remaining cubic (after the chop) 629 memcpy(tmp, dst, 4 * sizeof(SkPoint)); 630 src = tmp; 631 632 // watch out in case the renormalized t isn't in range 633 if (!valid_unit_divide(tValues[i+1] - tValues[i], 634 SK_Scalar1 - tValues[i], &t)) { 635 // if we can't, just create a degenerate cubic 636 dst[4] = dst[5] = dst[6] = src[3]; 637 break; 638 } 639 } 640 } 641 } 642 } 643 644 void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]) 645 { 646 SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 647 SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 648 SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 649 SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 650 SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX); 651 SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY); 652 653 SkScalar x012 = SkScalarAve(x01, x12); 654 SkScalar y012 = SkScalarAve(y01, y12); 655 SkScalar x123 = SkScalarAve(x12, x23); 656 SkScalar y123 = SkScalarAve(y12, y23); 657 658 dst[0] = src[0]; 659 dst[1].set(x01, y01); 660 dst[2].set(x012, y012); 661 dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123)); 662 dst[4].set(x123, y123); 663 dst[5].set(x23, y23); 664 dst[6] = src[3]; 665 } 666 667 static void flatten_double_cubic_extrema(SkScalar coords[14]) 668 { 669 coords[4] = coords[8] = coords[6]; 670 } 671 672 /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 673 the resulting beziers are monotonic in Y. This is called by the scan converter. 674 Depending on what is returned, dst[] is treated as follows 675 0 dst[0..3] is the original cubic 676 1 dst[0..3] and dst[3..6] are the two new cubics 677 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 678 If dst == null, it is ignored and only the count is returned. 679 */ 680 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]) { 681 SkScalar tValues[2]; 682 int roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, 683 src[3].fY, tValues); 684 685 SkChopCubicAt(src, dst, tValues, roots); 686 if (dst && roots > 0) { 687 // we do some cleanup to ensure our Y extrema are flat 688 flatten_double_cubic_extrema(&dst[0].fY); 689 if (roots == 2) { 690 flatten_double_cubic_extrema(&dst[3].fY); 691 } 692 } 693 return roots; 694 } 695 696 int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]) { 697 SkScalar tValues[2]; 698 int roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, 699 src[3].fX, tValues); 700 701 SkChopCubicAt(src, dst, tValues, roots); 702 if (dst && roots > 0) { 703 // we do some cleanup to ensure our Y extrema are flat 704 flatten_double_cubic_extrema(&dst[0].fX); 705 if (roots == 2) { 706 flatten_double_cubic_extrema(&dst[3].fX); 707 } 708 } 709 return roots; 710 } 711 712 /** http://www.faculty.idc.ac.il/arik/quality/appendixA.html 713 714 Inflection means that curvature is zero. 715 Curvature is [F' x F''] / [F'^3] 716 So we solve F'x X F''y - F'y X F''y == 0 717 After some canceling of the cubic term, we get 718 A = b - a 719 B = c - 2b + a 720 C = d - 3c + 3b - a 721 (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0 722 */ 723 int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[]) 724 { 725 SkScalar Ax = src[1].fX - src[0].fX; 726 SkScalar Ay = src[1].fY - src[0].fY; 727 SkScalar Bx = src[2].fX - 2 * src[1].fX + src[0].fX; 728 SkScalar By = src[2].fY - 2 * src[1].fY + src[0].fY; 729 SkScalar Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX; 730 SkScalar Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY; 731 int count; 732 733 #ifdef SK_SCALAR_IS_FLOAT 734 count = SkFindUnitQuadRoots(Bx*Cy - By*Cx, Ax*Cy - Ay*Cx, Ax*By - Ay*Bx, tValues); 735 #else 736 Sk64 A, B, C, tmp; 737 738 A.setMul(Bx, Cy); 739 tmp.setMul(By, Cx); 740 A.sub(tmp); 741 742 B.setMul(Ax, Cy); 743 tmp.setMul(Ay, Cx); 744 B.sub(tmp); 745 746 C.setMul(Ax, By); 747 tmp.setMul(Ay, Bx); 748 C.sub(tmp); 749 750 count = Sk64FindFixedQuadRoots(A, B, C, tValues); 751 #endif 752 753 return count; 754 } 755 756 int SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) 757 { 758 SkScalar tValues[2]; 759 int count = SkFindCubicInflections(src, tValues); 760 761 if (dst) 762 { 763 if (count == 0) 764 memcpy(dst, src, 4 * sizeof(SkPoint)); 765 else 766 SkChopCubicAt(src, dst, tValues, count); 767 } 768 return count + 1; 769 } 770 771 template <typename T> void bubble_sort(T array[], int count) 772 { 773 for (int i = count - 1; i > 0; --i) 774 for (int j = i; j > 0; --j) 775 if (array[j] < array[j-1]) 776 { 777 T tmp(array[j]); 778 array[j] = array[j-1]; 779 array[j-1] = tmp; 780 } 781 } 782 783 #include "SkFP.h" 784 785 // newton refinement 786 #if 0 787 static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root) 788 { 789 // x1 = x0 - f(t) / f'(t) 790 791 SkFP T = SkScalarToFloat(root); 792 SkFP N, D; 793 794 // f' = 3*coeff[0]*T^2 + 2*coeff[1]*T + coeff[2] 795 D = SkFPMul(SkFPMul(coeff[0], SkFPMul(T,T)), 3); 796 D = SkFPAdd(D, SkFPMulInt(SkFPMul(coeff[1], T), 2)); 797 D = SkFPAdd(D, coeff[2]); 798 799 if (D == 0) 800 return root; 801 802 // f = coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 803 N = SkFPMul(SkFPMul(SkFPMul(T, T), T), coeff[0]); 804 N = SkFPAdd(N, SkFPMul(SkFPMul(T, T), coeff[1])); 805 N = SkFPAdd(N, SkFPMul(T, coeff[2])); 806 N = SkFPAdd(N, coeff[3]); 807 808 if (N) 809 { 810 SkScalar delta = SkFPToScalar(SkFPDiv(N, D)); 811 812 if (delta) 813 root -= delta; 814 } 815 return root; 816 } 817 #endif 818 819 #if defined _WIN32 && _MSC_VER >= 1300 && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop 820 #pragma warning ( disable : 4702 ) 821 #endif 822 823 /* Solve coeff(t) == 0, returning the number of roots that 824 lie withing 0 < t < 1. 825 coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] 826 */ 827 static int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3]) 828 { 829 #ifndef SK_SCALAR_IS_FLOAT 830 return 0; // this is not yet implemented for software float 831 #endif 832 833 if (SkScalarNearlyZero(coeff[0])) // we're just a quadratic 834 { 835 return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); 836 } 837 838 SkFP a, b, c, Q, R; 839 840 { 841 SkASSERT(coeff[0] != 0); 842 843 SkFP inva = SkFPInvert(coeff[0]); 844 a = SkFPMul(coeff[1], inva); 845 b = SkFPMul(coeff[2], inva); 846 c = SkFPMul(coeff[3], inva); 847 } 848 Q = SkFPDivInt(SkFPSub(SkFPMul(a,a), SkFPMulInt(b, 3)), 9); 849 // R = (2*a*a*a - 9*a*b + 27*c) / 54; 850 R = SkFPMulInt(SkFPMul(SkFPMul(a, a), a), 2); 851 R = SkFPSub(R, SkFPMulInt(SkFPMul(a, b), 9)); 852 R = SkFPAdd(R, SkFPMulInt(c, 27)); 853 R = SkFPDivInt(R, 54); 854 855 SkFP Q3 = SkFPMul(SkFPMul(Q, Q), Q); 856 SkFP R2MinusQ3 = SkFPSub(SkFPMul(R,R), Q3); 857 SkFP adiv3 = SkFPDivInt(a, 3); 858 859 SkScalar* roots = tValues; 860 SkScalar r; 861 862 if (SkFPLT(R2MinusQ3, 0)) // we have 3 real roots 863 { 864 #ifdef SK_SCALAR_IS_FLOAT 865 float theta = sk_float_acos(R / sk_float_sqrt(Q3)); 866 float neg2RootQ = -2 * sk_float_sqrt(Q); 867 868 r = neg2RootQ * sk_float_cos(theta/3) - adiv3; 869 if (is_unit_interval(r)) 870 *roots++ = r; 871 872 r = neg2RootQ * sk_float_cos((theta + 2*SK_ScalarPI)/3) - adiv3; 873 if (is_unit_interval(r)) 874 *roots++ = r; 875 876 r = neg2RootQ * sk_float_cos((theta - 2*SK_ScalarPI)/3) - adiv3; 877 if (is_unit_interval(r)) 878 *roots++ = r; 879 880 // now sort the roots 881 bubble_sort(tValues, (int)(roots - tValues)); 882 #endif 883 } 884 else // we have 1 real root 885 { 886 SkFP A = SkFPAdd(SkFPAbs(R), SkFPSqrt(R2MinusQ3)); 887 A = SkFPCubeRoot(A); 888 if (SkFPGT(R, 0)) 889 A = SkFPNeg(A); 890 891 if (A != 0) 892 A = SkFPAdd(A, SkFPDiv(Q, A)); 893 r = SkFPToScalar(SkFPSub(A, adiv3)); 894 if (is_unit_interval(r)) 895 *roots++ = r; 896 } 897 898 return (int)(roots - tValues); 899 } 900 901 /* Looking for F' dot F'' == 0 902 903 A = b - a 904 B = c - 2b + a 905 C = d - 3c + 3b - a 906 907 F' = 3Ct^2 + 6Bt + 3A 908 F'' = 6Ct + 6B 909 910 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 911 */ 912 static void formulate_F1DotF2(const SkScalar src[], SkFP coeff[4]) 913 { 914 SkScalar a = src[2] - src[0]; 915 SkScalar b = src[4] - 2 * src[2] + src[0]; 916 SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0]; 917 918 SkFP A = SkScalarToFP(a); 919 SkFP B = SkScalarToFP(b); 920 SkFP C = SkScalarToFP(c); 921 922 coeff[0] = SkFPMul(C, C); 923 coeff[1] = SkFPMulInt(SkFPMul(B, C), 3); 924 coeff[2] = SkFPMulInt(SkFPMul(B, B), 2); 925 coeff[2] = SkFPAdd(coeff[2], SkFPMul(C, A)); 926 coeff[3] = SkFPMul(A, B); 927 } 928 929 // EXPERIMENTAL: can set this to zero to accept all t-values 0 < t < 1 930 //#define kMinTValueForChopping (SK_Scalar1 / 256) 931 #define kMinTValueForChopping 0 932 933 /* Looking for F' dot F'' == 0 934 935 A = b - a 936 B = c - 2b + a 937 C = d - 3c + 3b - a 938 939 F' = 3Ct^2 + 6Bt + 3A 940 F'' = 6Ct + 6B 941 942 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 943 */ 944 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) 945 { 946 SkFP coeffX[4], coeffY[4]; 947 int i; 948 949 formulate_F1DotF2(&src[0].fX, coeffX); 950 formulate_F1DotF2(&src[0].fY, coeffY); 951 952 for (i = 0; i < 4; i++) 953 coeffX[i] = SkFPAdd(coeffX[i],coeffY[i]); 954 955 SkScalar t[3]; 956 int count = solve_cubic_polynomial(coeffX, t); 957 int maxCount = 0; 958 959 // now remove extrema where the curvature is zero (mins) 960 // !!!! need a test for this !!!! 961 for (i = 0; i < count; i++) 962 { 963 // if (not_min_curvature()) 964 if (t[i] > kMinTValueForChopping && t[i] < SK_Scalar1 - kMinTValueForChopping) 965 tValues[maxCount++] = t[i]; 966 } 967 return maxCount; 968 } 969 970 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tValues[3]) 971 { 972 SkScalar t_storage[3]; 973 974 if (tValues == NULL) 975 tValues = t_storage; 976 977 int count = SkFindCubicMaxCurvature(src, tValues); 978 979 if (dst) 980 { 981 if (count == 0) 982 memcpy(dst, src, 4 * sizeof(SkPoint)); 983 else 984 SkChopCubicAt(src, dst, tValues, count); 985 } 986 return count + 1; 987 } 988 989 bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4]) { 990 // Find the minimum and maximum y of the extrema, which are the 991 // first and last points since this cubic is monotonic 992 SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY); 993 SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY); 994 995 if (pt.fY == cubic[0].fY 996 || pt.fY < min_y 997 || pt.fY > max_y) { 998 // The query line definitely does not cross the curve 999 return false; 1000 } 1001 1002 SkScalar min_x = 1003 SkMinScalar( 1004 SkMinScalar( 1005 SkMinScalar(cubic[0].fX, cubic[1].fX), 1006 cubic[2].fX), 1007 cubic[3].fX); 1008 if (pt.fX < min_x) { 1009 // The query line definitely crosses the curve 1010 return true; 1011 } 1012 1013 SkScalar max_x = 1014 SkMaxScalar( 1015 SkMaxScalar( 1016 SkMaxScalar(cubic[0].fX, cubic[1].fX), 1017 cubic[2].fX), 1018 cubic[3].fX); 1019 if (pt.fX > max_x) { 1020 // The query line definitely does not cross the curve 1021 return false; 1022 } 1023 1024 // Do a binary search to find the parameter value which makes y as 1025 // close as possible to the query point. See whether the query 1026 // line's origin is to the left of the associated x coordinate. 1027 1028 // kMaxIter is chosen as the number of mantissa bits for a float, 1029 // since there's no way we are going to get more precision by 1030 // iterating more times than that. 1031 const int kMaxIter = 23; 1032 SkPoint eval; 1033 int iter = 0; 1034 SkScalar upper_t; 1035 SkScalar lower_t; 1036 // Need to invert direction of t parameter if cubic goes up 1037 // instead of down 1038 if (cubic[3].fY > cubic[0].fY) { 1039 upper_t = SK_Scalar1; 1040 lower_t = SkFloatToScalar(0); 1041 } else { 1042 upper_t = SkFloatToScalar(0); 1043 lower_t = SK_Scalar1; 1044 } 1045 do { 1046 SkScalar t = SkScalarAve(upper_t, lower_t); 1047 SkEvalCubicAt(cubic, t, &eval, NULL, NULL); 1048 if (pt.fY > eval.fY) { 1049 lower_t = t; 1050 } else { 1051 upper_t = t; 1052 } 1053 } while (++iter < kMaxIter 1054 && !SkScalarNearlyZero(eval.fY - pt.fY)); 1055 if (pt.fX <= eval.fX) { 1056 return true; 1057 } 1058 return false; 1059 } 1060 1061 int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4]) { 1062 int num_crossings = 0; 1063 SkPoint monotonic_cubics[10]; 1064 int num_monotonic_cubics = SkChopCubicAtYExtrema(cubic, monotonic_cubics); 1065 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[0])) 1066 ++num_crossings; 1067 if (num_monotonic_cubics > 0) 1068 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[3])) 1069 ++num_crossings; 1070 if (num_monotonic_cubics > 1) 1071 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6])) 1072 ++num_crossings; 1073 return num_crossings; 1074 } 1075 1076 //////////////////////////////////////////////////////////////////////////////// 1077 1078 /* Find t value for quadratic [a, b, c] = d. 1079 Return 0 if there is no solution within [0, 1) 1080 */ 1081 static SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d) 1082 { 1083 // At^2 + Bt + C = d 1084 SkScalar A = a - 2 * b + c; 1085 SkScalar B = 2 * (b - a); 1086 SkScalar C = a - d; 1087 1088 SkScalar roots[2]; 1089 int count = SkFindUnitQuadRoots(A, B, C, roots); 1090 1091 SkASSERT(count <= 1); 1092 return count == 1 ? roots[0] : 0; 1093 } 1094 1095 /* given a quad-curve and a point (x,y), chop the quad at that point and return 1096 the new quad's offCurve point. Should only return false if the computed pos 1097 is the start of the curve (i.e. root == 0) 1098 */ 1099 static bool quad_pt2OffCurve(const SkPoint quad[3], SkScalar x, SkScalar y, SkPoint* offCurve) 1100 { 1101 const SkScalar* base; 1102 SkScalar value; 1103 1104 if (SkScalarAbs(x) < SkScalarAbs(y)) { 1105 base = &quad[0].fX; 1106 value = x; 1107 } else { 1108 base = &quad[0].fY; 1109 value = y; 1110 } 1111 1112 // note: this returns 0 if it thinks value is out of range, meaning the 1113 // root might return something outside of [0, 1) 1114 SkScalar t = quad_solve(base[0], base[2], base[4], value); 1115 1116 if (t > 0) 1117 { 1118 SkPoint tmp[5]; 1119 SkChopQuadAt(quad, tmp, t); 1120 *offCurve = tmp[1]; 1121 return true; 1122 } else { 1123 /* t == 0 means either the value triggered a root outside of [0, 1) 1124 For our purposes, we can ignore the <= 0 roots, but we want to 1125 catch the >= 1 roots (which given our caller, will basically mean 1126 a root of 1, give-or-take numerical instability). If we are in the 1127 >= 1 case, return the existing offCurve point. 1128 1129 The test below checks to see if we are close to the "end" of the 1130 curve (near base[4]). Rather than specifying a tolerance, I just 1131 check to see if value is on to the right/left of the middle point 1132 (depending on the direction/sign of the end points). 1133 */ 1134 if ((base[0] < base[4] && value > base[2]) || 1135 (base[0] > base[4] && value < base[2])) // should root have been 1 1136 { 1137 *offCurve = quad[1]; 1138 return true; 1139 } 1140 } 1141 return false; 1142 } 1143 1144 static const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = { 1145 { SK_Scalar1, 0 }, 1146 { SK_Scalar1, SK_ScalarTanPIOver8 }, 1147 { SK_ScalarRoot2Over2, SK_ScalarRoot2Over2 }, 1148 { SK_ScalarTanPIOver8, SK_Scalar1 }, 1149 1150 { 0, SK_Scalar1 }, 1151 { -SK_ScalarTanPIOver8, SK_Scalar1 }, 1152 { -SK_ScalarRoot2Over2, SK_ScalarRoot2Over2 }, 1153 { -SK_Scalar1, SK_ScalarTanPIOver8 }, 1154 1155 { -SK_Scalar1, 0 }, 1156 { -SK_Scalar1, -SK_ScalarTanPIOver8 }, 1157 { -SK_ScalarRoot2Over2, -SK_ScalarRoot2Over2 }, 1158 { -SK_ScalarTanPIOver8, -SK_Scalar1 }, 1159 1160 { 0, -SK_Scalar1 }, 1161 { SK_ScalarTanPIOver8, -SK_Scalar1 }, 1162 { SK_ScalarRoot2Over2, -SK_ScalarRoot2Over2 }, 1163 { SK_Scalar1, -SK_ScalarTanPIOver8 }, 1164 1165 { SK_Scalar1, 0 } 1166 }; 1167 1168 int SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop, 1169 SkRotationDirection dir, const SkMatrix* userMatrix, 1170 SkPoint quadPoints[]) 1171 { 1172 // rotate by x,y so that uStart is (1.0) 1173 SkScalar x = SkPoint::DotProduct(uStart, uStop); 1174 SkScalar y = SkPoint::CrossProduct(uStart, uStop); 1175 1176 SkScalar absX = SkScalarAbs(x); 1177 SkScalar absY = SkScalarAbs(y); 1178 1179 int pointCount; 1180 1181 // check for (effectively) coincident vectors 1182 // this can happen if our angle is nearly 0 or nearly 180 (y == 0) 1183 // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) 1184 if (absY <= SK_ScalarNearlyZero && x > 0 && 1185 ((y >= 0 && kCW_SkRotationDirection == dir) || 1186 (y <= 0 && kCCW_SkRotationDirection == dir))) { 1187 1188 // just return the start-point 1189 quadPoints[0].set(SK_Scalar1, 0); 1190 pointCount = 1; 1191 } else { 1192 if (dir == kCCW_SkRotationDirection) 1193 y = -y; 1194 1195 // what octant (quadratic curve) is [xy] in? 1196 int oct = 0; 1197 bool sameSign = true; 1198 1199 if (0 == y) 1200 { 1201 oct = 4; // 180 1202 SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); 1203 } 1204 else if (0 == x) 1205 { 1206 SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); 1207 if (y > 0) 1208 oct = 2; // 90 1209 else 1210 oct = 6; // 270 1211 } 1212 else 1213 { 1214 if (y < 0) 1215 oct += 4; 1216 if ((x < 0) != (y < 0)) 1217 { 1218 oct += 2; 1219 sameSign = false; 1220 } 1221 if ((absX < absY) == sameSign) 1222 oct += 1; 1223 } 1224 1225 int wholeCount = oct << 1; 1226 memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint)); 1227 1228 const SkPoint* arc = &gQuadCirclePts[wholeCount]; 1229 if (quad_pt2OffCurve(arc, x, y, &quadPoints[wholeCount + 1])) 1230 { 1231 quadPoints[wholeCount + 2].set(x, y); 1232 wholeCount += 2; 1233 } 1234 pointCount = wholeCount + 1; 1235 } 1236 1237 // now handle counter-clockwise and the initial unitStart rotation 1238 SkMatrix matrix; 1239 matrix.setSinCos(uStart.fY, uStart.fX); 1240 if (dir == kCCW_SkRotationDirection) { 1241 matrix.preScale(SK_Scalar1, -SK_Scalar1); 1242 } 1243 if (userMatrix) { 1244 matrix.postConcat(*userMatrix); 1245 } 1246 matrix.mapPoints(quadPoints, pointCount); 1247 return pointCount; 1248 } 1249 1250
