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