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], 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 108 static bool is_unit_interval(SkScalar x) 109 { 110 return x > 0 && x < SK_Scalar1; 111 } 112 113 static 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 */ 143 int 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 */ 187 static 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 203 static 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 220 static 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 228 static 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 235 void 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 247 void 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 264 static 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 276 void 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 284 void 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 */ 303 int 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 315 static 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 */ 323 int 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 */ 367 int 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 // 405 int 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 void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]) 452 { 453 SkScalar two = SkIntToScalar(2); 454 SkScalar one_third = SkScalarDiv(SK_Scalar1, SkIntToScalar(3)); 455 dst[0].set(src[0].fX, src[0].fY); 456 dst[1].set( 457 SkScalarMul(SkScalarMulAdd(src[1].fX, two, src[0].fX), one_third), 458 SkScalarMul(SkScalarMulAdd(src[1].fY, two, src[0].fY), one_third)); 459 dst[2].set( 460 SkScalarMul(SkScalarMulAdd(src[1].fX, two, src[2].fX), one_third), 461 SkScalarMul(SkScalarMulAdd(src[1].fY, two, src[2].fY), one_third)); 462 dst[3].set(src[2].fX, src[2].fY); 463 } 464 465 //////////////////////////////////////////////////////////////////////////////////////// 466 ///// CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS // CUBICS ///// 467 //////////////////////////////////////////////////////////////////////////////////////// 468 469 static void get_cubic_coeff(const SkScalar pt[], SkScalar coeff[4]) 470 { 471 coeff[0] = pt[6] + 3*(pt[2] - pt[4]) - pt[0]; 472 coeff[1] = 3*(pt[4] - pt[2] - pt[2] + pt[0]); 473 coeff[2] = 3*(pt[2] - pt[0]); 474 coeff[3] = pt[0]; 475 } 476 477 void SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]) 478 { 479 SkASSERT(pts); 480 481 if (cx) 482 get_cubic_coeff(&pts[0].fX, cx); 483 if (cy) 484 get_cubic_coeff(&pts[0].fY, cy); 485 } 486 487 static SkScalar eval_cubic(const SkScalar src[], SkScalar t) 488 { 489 SkASSERT(src); 490 SkASSERT(t >= 0 && t <= SK_Scalar1); 491 492 if (t == 0) 493 return src[0]; 494 495 #ifdef DIRECT_EVAL_OF_POLYNOMIALS 496 SkScalar D = src[0]; 497 SkScalar A = src[6] + 3*(src[2] - src[4]) - D; 498 SkScalar B = 3*(src[4] - src[2] - src[2] + D); 499 SkScalar C = 3*(src[2] - D); 500 501 return SkScalarMulAdd(SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C), t, D); 502 #else 503 SkScalar ab = SkScalarInterp(src[0], src[2], t); 504 SkScalar bc = SkScalarInterp(src[2], src[4], t); 505 SkScalar cd = SkScalarInterp(src[4], src[6], t); 506 SkScalar abc = SkScalarInterp(ab, bc, t); 507 SkScalar bcd = SkScalarInterp(bc, cd, t); 508 return SkScalarInterp(abc, bcd, t); 509 #endif 510 } 511 512 /** return At^2 + Bt + C 513 */ 514 static SkScalar eval_quadratic(SkScalar A, SkScalar B, SkScalar C, SkScalar t) 515 { 516 SkASSERT(t >= 0 && t <= SK_Scalar1); 517 518 return SkScalarMulAdd(SkScalarMulAdd(A, t, B), t, C); 519 } 520 521 static SkScalar eval_cubic_derivative(const SkScalar src[], SkScalar t) 522 { 523 SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 524 SkScalar B = 2*(src[4] - 2 * src[2] + src[0]); 525 SkScalar C = src[2] - src[0]; 526 527 return eval_quadratic(A, B, C, t); 528 } 529 530 static SkScalar eval_cubic_2ndDerivative(const SkScalar src[], SkScalar t) 531 { 532 SkScalar A = src[6] + 3*(src[2] - src[4]) - src[0]; 533 SkScalar B = src[4] - 2 * src[2] + src[0]; 534 535 return SkScalarMulAdd(A, t, B); 536 } 537 538 void SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* loc, SkVector* tangent, SkVector* curvature) 539 { 540 SkASSERT(src); 541 SkASSERT(t >= 0 && t <= SK_Scalar1); 542 543 if (loc) 544 loc->set(eval_cubic(&src[0].fX, t), eval_cubic(&src[0].fY, t)); 545 if (tangent) 546 tangent->set(eval_cubic_derivative(&src[0].fX, t), 547 eval_cubic_derivative(&src[0].fY, t)); 548 if (curvature) 549 curvature->set(eval_cubic_2ndDerivative(&src[0].fX, t), 550 eval_cubic_2ndDerivative(&src[0].fY, t)); 551 } 552 553 /** Cubic'(t) = At^2 + Bt + C, where 554 A = 3(-a + 3(b - c) + d) 555 B = 6(a - 2b + c) 556 C = 3(b - a) 557 Solve for t, keeping only those that fit betwee 0 < t < 1 558 */ 559 int SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, SkScalar tValues[2]) 560 { 561 #ifdef SK_SCALAR_IS_FIXED 562 if (!is_not_monotonic(a, b, c, d)) 563 return 0; 564 #endif 565 566 // we divide A,B,C by 3 to simplify 567 SkScalar A = d - a + 3*(b - c); 568 SkScalar B = 2*(a - b - b + c); 569 SkScalar C = b - a; 570 571 return SkFindUnitQuadRoots(A, B, C, tValues); 572 } 573 574 static void interp_cubic_coords(const SkScalar* src, SkScalar* dst, SkScalar t) 575 { 576 SkScalar ab = SkScalarInterp(src[0], src[2], t); 577 SkScalar bc = SkScalarInterp(src[2], src[4], t); 578 SkScalar cd = SkScalarInterp(src[4], src[6], t); 579 SkScalar abc = SkScalarInterp(ab, bc, t); 580 SkScalar bcd = SkScalarInterp(bc, cd, t); 581 SkScalar abcd = SkScalarInterp(abc, bcd, t); 582 583 dst[0] = src[0]; 584 dst[2] = ab; 585 dst[4] = abc; 586 dst[6] = abcd; 587 dst[8] = bcd; 588 dst[10] = cd; 589 dst[12] = src[6]; 590 } 591 592 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t) 593 { 594 SkASSERT(t > 0 && t < SK_Scalar1); 595 596 interp_cubic_coords(&src[0].fX, &dst[0].fX, t); 597 interp_cubic_coords(&src[0].fY, &dst[0].fY, t); 598 } 599 600 /* http://code.google.com/p/skia/issues/detail?id=32 601 602 This test code would fail when we didn't check the return result of 603 valid_unit_divide in SkChopCubicAt(... tValues[], int roots). The reason is 604 that after the first chop, the parameters to valid_unit_divide are equal 605 (thanks to finite float precision and rounding in the subtracts). Thus 606 even though the 2nd tValue looks < 1.0, after we renormalize it, we end 607 up with 1.0, hence the need to check and just return the last cubic as 608 a degenerate clump of 4 points in the sampe place. 609 610 static void test_cubic() { 611 SkPoint src[4] = { 612 { 556.25000, 523.03003 }, 613 { 556.23999, 522.96002 }, 614 { 556.21997, 522.89001 }, 615 { 556.21997, 522.82001 } 616 }; 617 SkPoint dst[10]; 618 SkScalar tval[] = { 0.33333334f, 0.99999994f }; 619 SkChopCubicAt(src, dst, tval, 2); 620 } 621 */ 622 623 void SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar tValues[], int roots) 624 { 625 #ifdef SK_DEBUG 626 { 627 for (int i = 0; i < roots - 1; i++) 628 { 629 SkASSERT(is_unit_interval(tValues[i])); 630 SkASSERT(is_unit_interval(tValues[i+1])); 631 SkASSERT(tValues[i] < tValues[i+1]); 632 } 633 } 634 #endif 635 636 if (dst) 637 { 638 if (roots == 0) // nothing to chop 639 memcpy(dst, src, 4*sizeof(SkPoint)); 640 else 641 { 642 SkScalar t = tValues[0]; 643 SkPoint tmp[4]; 644 645 for (int i = 0; i < roots; i++) 646 { 647 SkChopCubicAt(src, dst, t); 648 if (i == roots - 1) 649 break; 650 651 dst += 3; 652 // have src point to the remaining cubic (after the chop) 653 memcpy(tmp, dst, 4 * sizeof(SkPoint)); 654 src = tmp; 655 656 // watch out in case the renormalized t isn't in range 657 if (!valid_unit_divide(tValues[i+1] - tValues[i], 658 SK_Scalar1 - tValues[i], &t)) { 659 // if we can't, just create a degenerate cubic 660 dst[4] = dst[5] = dst[6] = src[3]; 661 break; 662 } 663 } 664 } 665 } 666 } 667 668 void SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]) 669 { 670 SkScalar x01 = SkScalarAve(src[0].fX, src[1].fX); 671 SkScalar y01 = SkScalarAve(src[0].fY, src[1].fY); 672 SkScalar x12 = SkScalarAve(src[1].fX, src[2].fX); 673 SkScalar y12 = SkScalarAve(src[1].fY, src[2].fY); 674 SkScalar x23 = SkScalarAve(src[2].fX, src[3].fX); 675 SkScalar y23 = SkScalarAve(src[2].fY, src[3].fY); 676 677 SkScalar x012 = SkScalarAve(x01, x12); 678 SkScalar y012 = SkScalarAve(y01, y12); 679 SkScalar x123 = SkScalarAve(x12, x23); 680 SkScalar y123 = SkScalarAve(y12, y23); 681 682 dst[0] = src[0]; 683 dst[1].set(x01, y01); 684 dst[2].set(x012, y012); 685 dst[3].set(SkScalarAve(x012, x123), SkScalarAve(y012, y123)); 686 dst[4].set(x123, y123); 687 dst[5].set(x23, y23); 688 dst[6] = src[3]; 689 } 690 691 static void flatten_double_cubic_extrema(SkScalar coords[14]) 692 { 693 coords[4] = coords[8] = coords[6]; 694 } 695 696 /** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 697 the resulting beziers are monotonic in Y. This is called by the scan converter. 698 Depending on what is returned, dst[] is treated as follows 699 0 dst[0..3] is the original cubic 700 1 dst[0..3] and dst[3..6] are the two new cubics 701 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 702 If dst == null, it is ignored and only the count is returned. 703 */ 704 int SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]) { 705 SkScalar tValues[2]; 706 int roots = SkFindCubicExtrema(src[0].fY, src[1].fY, src[2].fY, 707 src[3].fY, tValues); 708 709 SkChopCubicAt(src, dst, tValues, roots); 710 if (dst && roots > 0) { 711 // we do some cleanup to ensure our Y extrema are flat 712 flatten_double_cubic_extrema(&dst[0].fY); 713 if (roots == 2) { 714 flatten_double_cubic_extrema(&dst[3].fY); 715 } 716 } 717 return roots; 718 } 719 720 int SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]) { 721 SkScalar tValues[2]; 722 int roots = SkFindCubicExtrema(src[0].fX, src[1].fX, src[2].fX, 723 src[3].fX, tValues); 724 725 SkChopCubicAt(src, dst, tValues, roots); 726 if (dst && roots > 0) { 727 // we do some cleanup to ensure our Y extrema are flat 728 flatten_double_cubic_extrema(&dst[0].fX); 729 if (roots == 2) { 730 flatten_double_cubic_extrema(&dst[3].fX); 731 } 732 } 733 return roots; 734 } 735 736 /** http://www.faculty.idc.ac.il/arik/quality/appendixA.html 737 738 Inflection means that curvature is zero. 739 Curvature is [F' x F''] / [F'^3] 740 So we solve F'x X F''y - F'y X F''y == 0 741 After some canceling of the cubic term, we get 742 A = b - a 743 B = c - 2b + a 744 C = d - 3c + 3b - a 745 (BxCy - ByCx)t^2 + (AxCy - AyCx)t + AxBy - AyBx == 0 746 */ 747 int SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[]) 748 { 749 SkScalar Ax = src[1].fX - src[0].fX; 750 SkScalar Ay = src[1].fY - src[0].fY; 751 SkScalar Bx = src[2].fX - 2 * src[1].fX + src[0].fX; 752 SkScalar By = src[2].fY - 2 * src[1].fY + src[0].fY; 753 SkScalar Cx = src[3].fX + 3 * (src[1].fX - src[2].fX) - src[0].fX; 754 SkScalar Cy = src[3].fY + 3 * (src[1].fY - src[2].fY) - src[0].fY; 755 int count; 756 757 #ifdef SK_SCALAR_IS_FLOAT 758 count = SkFindUnitQuadRoots(Bx*Cy - By*Cx, Ax*Cy - Ay*Cx, Ax*By - Ay*Bx, tValues); 759 #else 760 Sk64 A, B, C, tmp; 761 762 A.setMul(Bx, Cy); 763 tmp.setMul(By, Cx); 764 A.sub(tmp); 765 766 B.setMul(Ax, Cy); 767 tmp.setMul(Ay, Cx); 768 B.sub(tmp); 769 770 C.setMul(Ax, By); 771 tmp.setMul(Ay, Bx); 772 C.sub(tmp); 773 774 count = Sk64FindFixedQuadRoots(A, B, C, tValues); 775 #endif 776 777 return count; 778 } 779 780 int SkChopCubicAtInflections(const SkPoint src[], SkPoint dst[10]) 781 { 782 SkScalar tValues[2]; 783 int count = SkFindCubicInflections(src, tValues); 784 785 if (dst) 786 { 787 if (count == 0) 788 memcpy(dst, src, 4 * sizeof(SkPoint)); 789 else 790 SkChopCubicAt(src, dst, tValues, count); 791 } 792 return count + 1; 793 } 794 795 template <typename T> void bubble_sort(T array[], int count) 796 { 797 for (int i = count - 1; i > 0; --i) 798 for (int j = i; j > 0; --j) 799 if (array[j] < array[j-1]) 800 { 801 T tmp(array[j]); 802 array[j] = array[j-1]; 803 array[j-1] = tmp; 804 } 805 } 806 807 #include "SkFP.h" 808 809 // newton refinement 810 #if 0 811 static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root) 812 { 813 // x1 = x0 - f(t) / f'(t) 814 815 SkFP T = SkScalarToFloat(root); 816 SkFP N, D; 817 818 // f' = 3*coeff[0]*T^2 + 2*coeff[1]*T + coeff[2] 819 D = SkFPMul(SkFPMul(coeff[0], SkFPMul(T,T)), 3); 820 D = SkFPAdd(D, SkFPMulInt(SkFPMul(coeff[1], T), 2)); 821 D = SkFPAdd(D, coeff[2]); 822 823 if (D == 0) 824 return root; 825 826 // f = coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 827 N = SkFPMul(SkFPMul(SkFPMul(T, T), T), coeff[0]); 828 N = SkFPAdd(N, SkFPMul(SkFPMul(T, T), coeff[1])); 829 N = SkFPAdd(N, SkFPMul(T, coeff[2])); 830 N = SkFPAdd(N, coeff[3]); 831 832 if (N) 833 { 834 SkScalar delta = SkFPToScalar(SkFPDiv(N, D)); 835 836 if (delta) 837 root -= delta; 838 } 839 return root; 840 } 841 #endif 842 843 #if defined _WIN32 && _MSC_VER >= 1300 && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop 844 #pragma warning ( disable : 4702 ) 845 #endif 846 847 /* Solve coeff(t) == 0, returning the number of roots that 848 lie withing 0 < t < 1. 849 coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3] 850 */ 851 static int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3]) 852 { 853 #ifndef SK_SCALAR_IS_FLOAT 854 return 0; // this is not yet implemented for software float 855 #endif 856 857 if (SkScalarNearlyZero(coeff[0])) // we're just a quadratic 858 { 859 return SkFindUnitQuadRoots(coeff[1], coeff[2], coeff[3], tValues); 860 } 861 862 SkFP a, b, c, Q, R; 863 864 { 865 SkASSERT(coeff[0] != 0); 866 867 SkFP inva = SkFPInvert(coeff[0]); 868 a = SkFPMul(coeff[1], inva); 869 b = SkFPMul(coeff[2], inva); 870 c = SkFPMul(coeff[3], inva); 871 } 872 Q = SkFPDivInt(SkFPSub(SkFPMul(a,a), SkFPMulInt(b, 3)), 9); 873 // R = (2*a*a*a - 9*a*b + 27*c) / 54; 874 R = SkFPMulInt(SkFPMul(SkFPMul(a, a), a), 2); 875 R = SkFPSub(R, SkFPMulInt(SkFPMul(a, b), 9)); 876 R = SkFPAdd(R, SkFPMulInt(c, 27)); 877 R = SkFPDivInt(R, 54); 878 879 SkFP Q3 = SkFPMul(SkFPMul(Q, Q), Q); 880 SkFP R2MinusQ3 = SkFPSub(SkFPMul(R,R), Q3); 881 SkFP adiv3 = SkFPDivInt(a, 3); 882 883 SkScalar* roots = tValues; 884 SkScalar r; 885 886 if (SkFPLT(R2MinusQ3, 0)) // we have 3 real roots 887 { 888 #ifdef SK_SCALAR_IS_FLOAT 889 float theta = sk_float_acos(R / sk_float_sqrt(Q3)); 890 float neg2RootQ = -2 * sk_float_sqrt(Q); 891 892 r = neg2RootQ * sk_float_cos(theta/3) - adiv3; 893 if (is_unit_interval(r)) 894 *roots++ = r; 895 896 r = neg2RootQ * sk_float_cos((theta + 2*SK_ScalarPI)/3) - adiv3; 897 if (is_unit_interval(r)) 898 *roots++ = r; 899 900 r = neg2RootQ * sk_float_cos((theta - 2*SK_ScalarPI)/3) - adiv3; 901 if (is_unit_interval(r)) 902 *roots++ = r; 903 904 // now sort the roots 905 bubble_sort(tValues, (int)(roots - tValues)); 906 #endif 907 } 908 else // we have 1 real root 909 { 910 SkFP A = SkFPAdd(SkFPAbs(R), SkFPSqrt(R2MinusQ3)); 911 A = SkFPCubeRoot(A); 912 if (SkFPGT(R, 0)) 913 A = SkFPNeg(A); 914 915 if (A != 0) 916 A = SkFPAdd(A, SkFPDiv(Q, A)); 917 r = SkFPToScalar(SkFPSub(A, adiv3)); 918 if (is_unit_interval(r)) 919 *roots++ = r; 920 } 921 922 return (int)(roots - tValues); 923 } 924 925 /* Looking for F' dot F'' == 0 926 927 A = b - a 928 B = c - 2b + a 929 C = d - 3c + 3b - a 930 931 F' = 3Ct^2 + 6Bt + 3A 932 F'' = 6Ct + 6B 933 934 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 935 */ 936 static void formulate_F1DotF2(const SkScalar src[], SkFP coeff[4]) 937 { 938 SkScalar a = src[2] - src[0]; 939 SkScalar b = src[4] - 2 * src[2] + src[0]; 940 SkScalar c = src[6] + 3 * (src[2] - src[4]) - src[0]; 941 942 SkFP A = SkScalarToFP(a); 943 SkFP B = SkScalarToFP(b); 944 SkFP C = SkScalarToFP(c); 945 946 coeff[0] = SkFPMul(C, C); 947 coeff[1] = SkFPMulInt(SkFPMul(B, C), 3); 948 coeff[2] = SkFPMulInt(SkFPMul(B, B), 2); 949 coeff[2] = SkFPAdd(coeff[2], SkFPMul(C, A)); 950 coeff[3] = SkFPMul(A, B); 951 } 952 953 // EXPERIMENTAL: can set this to zero to accept all t-values 0 < t < 1 954 //#define kMinTValueForChopping (SK_Scalar1 / 256) 955 #define kMinTValueForChopping 0 956 957 /* Looking for F' dot F'' == 0 958 959 A = b - a 960 B = c - 2b + a 961 C = d - 3c + 3b - a 962 963 F' = 3Ct^2 + 6Bt + 3A 964 F'' = 6Ct + 6B 965 966 F' dot F'' -> CCt^3 + 3BCt^2 + (2BB + CA)t + AB 967 */ 968 int SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]) 969 { 970 SkFP coeffX[4], coeffY[4]; 971 int i; 972 973 formulate_F1DotF2(&src[0].fX, coeffX); 974 formulate_F1DotF2(&src[0].fY, coeffY); 975 976 for (i = 0; i < 4; i++) 977 coeffX[i] = SkFPAdd(coeffX[i],coeffY[i]); 978 979 SkScalar t[3]; 980 int count = solve_cubic_polynomial(coeffX, t); 981 int maxCount = 0; 982 983 // now remove extrema where the curvature is zero (mins) 984 // !!!! need a test for this !!!! 985 for (i = 0; i < count; i++) 986 { 987 // if (not_min_curvature()) 988 if (t[i] > kMinTValueForChopping && t[i] < SK_Scalar1 - kMinTValueForChopping) 989 tValues[maxCount++] = t[i]; 990 } 991 return maxCount; 992 } 993 994 int SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], SkScalar tValues[3]) 995 { 996 SkScalar t_storage[3]; 997 998 if (tValues == NULL) 999 tValues = t_storage; 1000 1001 int count = SkFindCubicMaxCurvature(src, tValues); 1002 1003 if (dst) 1004 { 1005 if (count == 0) 1006 memcpy(dst, src, 4 * sizeof(SkPoint)); 1007 else 1008 SkChopCubicAt(src, dst, tValues, count); 1009 } 1010 return count + 1; 1011 } 1012 1013 bool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) { 1014 if (ambiguous) { 1015 *ambiguous = false; 1016 } 1017 1018 // Find the minimum and maximum y of the extrema, which are the 1019 // first and last points since this cubic is monotonic 1020 SkScalar min_y = SkMinScalar(cubic[0].fY, cubic[3].fY); 1021 SkScalar max_y = SkMaxScalar(cubic[0].fY, cubic[3].fY); 1022 1023 if (pt.fY == cubic[0].fY 1024 || pt.fY < min_y 1025 || pt.fY > max_y) { 1026 // The query line definitely does not cross the curve 1027 if (ambiguous) { 1028 *ambiguous = (pt.fY == cubic[0].fY); 1029 } 1030 return false; 1031 } 1032 1033 bool pt_at_extremum = (pt.fY == cubic[3].fY); 1034 1035 SkScalar min_x = 1036 SkMinScalar( 1037 SkMinScalar( 1038 SkMinScalar(cubic[0].fX, cubic[1].fX), 1039 cubic[2].fX), 1040 cubic[3].fX); 1041 if (pt.fX < min_x) { 1042 // The query line definitely crosses the curve 1043 if (ambiguous) { 1044 *ambiguous = pt_at_extremum; 1045 } 1046 return true; 1047 } 1048 1049 SkScalar max_x = 1050 SkMaxScalar( 1051 SkMaxScalar( 1052 SkMaxScalar(cubic[0].fX, cubic[1].fX), 1053 cubic[2].fX), 1054 cubic[3].fX); 1055 if (pt.fX > max_x) { 1056 // The query line definitely does not cross the curve 1057 return false; 1058 } 1059 1060 // Do a binary search to find the parameter value which makes y as 1061 // close as possible to the query point. See whether the query 1062 // line's origin is to the left of the associated x coordinate. 1063 1064 // kMaxIter is chosen as the number of mantissa bits for a float, 1065 // since there's no way we are going to get more precision by 1066 // iterating more times than that. 1067 const int kMaxIter = 23; 1068 SkPoint eval; 1069 int iter = 0; 1070 SkScalar upper_t; 1071 SkScalar lower_t; 1072 // Need to invert direction of t parameter if cubic goes up 1073 // instead of down 1074 if (cubic[3].fY > cubic[0].fY) { 1075 upper_t = SK_Scalar1; 1076 lower_t = SkFloatToScalar(0); 1077 } else { 1078 upper_t = SkFloatToScalar(0); 1079 lower_t = SK_Scalar1; 1080 } 1081 do { 1082 SkScalar t = SkScalarAve(upper_t, lower_t); 1083 SkEvalCubicAt(cubic, t, &eval, NULL, NULL); 1084 if (pt.fY > eval.fY) { 1085 lower_t = t; 1086 } else { 1087 upper_t = t; 1088 } 1089 } while (++iter < kMaxIter 1090 && !SkScalarNearlyZero(eval.fY - pt.fY)); 1091 if (pt.fX <= eval.fX) { 1092 if (ambiguous) { 1093 *ambiguous = pt_at_extremum; 1094 } 1095 return true; 1096 } 1097 return false; 1098 } 1099 1100 int SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], bool* ambiguous) { 1101 int num_crossings = 0; 1102 SkPoint monotonic_cubics[10]; 1103 int num_monotonic_cubics = SkChopCubicAtYExtrema(cubic, monotonic_cubics); 1104 if (ambiguous) { 1105 *ambiguous = false; 1106 } 1107 bool locally_ambiguous; 1108 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[0], &locally_ambiguous)) 1109 ++num_crossings; 1110 if (ambiguous) { 1111 *ambiguous |= locally_ambiguous; 1112 } 1113 if (num_monotonic_cubics > 0) 1114 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[3], &locally_ambiguous)) 1115 ++num_crossings; 1116 if (ambiguous) { 1117 *ambiguous |= locally_ambiguous; 1118 } 1119 if (num_monotonic_cubics > 1) 1120 if (SkXRayCrossesMonotonicCubic(pt, &monotonic_cubics[6], &locally_ambiguous)) 1121 ++num_crossings; 1122 if (ambiguous) { 1123 *ambiguous |= locally_ambiguous; 1124 } 1125 return num_crossings; 1126 } 1127 1128 //////////////////////////////////////////////////////////////////////////////// 1129 1130 /* Find t value for quadratic [a, b, c] = d. 1131 Return 0 if there is no solution within [0, 1) 1132 */ 1133 static SkScalar quad_solve(SkScalar a, SkScalar b, SkScalar c, SkScalar d) 1134 { 1135 // At^2 + Bt + C = d 1136 SkScalar A = a - 2 * b + c; 1137 SkScalar B = 2 * (b - a); 1138 SkScalar C = a - d; 1139 1140 SkScalar roots[2]; 1141 int count = SkFindUnitQuadRoots(A, B, C, roots); 1142 1143 SkASSERT(count <= 1); 1144 return count == 1 ? roots[0] : 0; 1145 } 1146 1147 /* given a quad-curve and a point (x,y), chop the quad at that point and return 1148 the new quad's offCurve point. Should only return false if the computed pos 1149 is the start of the curve (i.e. root == 0) 1150 */ 1151 static bool quad_pt2OffCurve(const SkPoint quad[3], SkScalar x, SkScalar y, SkPoint* offCurve) 1152 { 1153 const SkScalar* base; 1154 SkScalar value; 1155 1156 if (SkScalarAbs(x) < SkScalarAbs(y)) { 1157 base = &quad[0].fX; 1158 value = x; 1159 } else { 1160 base = &quad[0].fY; 1161 value = y; 1162 } 1163 1164 // note: this returns 0 if it thinks value is out of range, meaning the 1165 // root might return something outside of [0, 1) 1166 SkScalar t = quad_solve(base[0], base[2], base[4], value); 1167 1168 if (t > 0) 1169 { 1170 SkPoint tmp[5]; 1171 SkChopQuadAt(quad, tmp, t); 1172 *offCurve = tmp[1]; 1173 return true; 1174 } else { 1175 /* t == 0 means either the value triggered a root outside of [0, 1) 1176 For our purposes, we can ignore the <= 0 roots, but we want to 1177 catch the >= 1 roots (which given our caller, will basically mean 1178 a root of 1, give-or-take numerical instability). If we are in the 1179 >= 1 case, return the existing offCurve point. 1180 1181 The test below checks to see if we are close to the "end" of the 1182 curve (near base[4]). Rather than specifying a tolerance, I just 1183 check to see if value is on to the right/left of the middle point 1184 (depending on the direction/sign of the end points). 1185 */ 1186 if ((base[0] < base[4] && value > base[2]) || 1187 (base[0] > base[4] && value < base[2])) // should root have been 1 1188 { 1189 *offCurve = quad[1]; 1190 return true; 1191 } 1192 } 1193 return false; 1194 } 1195 1196 static const SkPoint gQuadCirclePts[kSkBuildQuadArcStorage] = { 1197 { SK_Scalar1, 0 }, 1198 { SK_Scalar1, SK_ScalarTanPIOver8 }, 1199 { SK_ScalarRoot2Over2, SK_ScalarRoot2Over2 }, 1200 { SK_ScalarTanPIOver8, SK_Scalar1 }, 1201 1202 { 0, SK_Scalar1 }, 1203 { -SK_ScalarTanPIOver8, SK_Scalar1 }, 1204 { -SK_ScalarRoot2Over2, SK_ScalarRoot2Over2 }, 1205 { -SK_Scalar1, SK_ScalarTanPIOver8 }, 1206 1207 { -SK_Scalar1, 0 }, 1208 { -SK_Scalar1, -SK_ScalarTanPIOver8 }, 1209 { -SK_ScalarRoot2Over2, -SK_ScalarRoot2Over2 }, 1210 { -SK_ScalarTanPIOver8, -SK_Scalar1 }, 1211 1212 { 0, -SK_Scalar1 }, 1213 { SK_ScalarTanPIOver8, -SK_Scalar1 }, 1214 { SK_ScalarRoot2Over2, -SK_ScalarRoot2Over2 }, 1215 { SK_Scalar1, -SK_ScalarTanPIOver8 }, 1216 1217 { SK_Scalar1, 0 } 1218 }; 1219 1220 int SkBuildQuadArc(const SkVector& uStart, const SkVector& uStop, 1221 SkRotationDirection dir, const SkMatrix* userMatrix, 1222 SkPoint quadPoints[]) 1223 { 1224 // rotate by x,y so that uStart is (1.0) 1225 SkScalar x = SkPoint::DotProduct(uStart, uStop); 1226 SkScalar y = SkPoint::CrossProduct(uStart, uStop); 1227 1228 SkScalar absX = SkScalarAbs(x); 1229 SkScalar absY = SkScalarAbs(y); 1230 1231 int pointCount; 1232 1233 // check for (effectively) coincident vectors 1234 // this can happen if our angle is nearly 0 or nearly 180 (y == 0) 1235 // ... we use the dot-prod to distinguish between 0 and 180 (x > 0) 1236 if (absY <= SK_ScalarNearlyZero && x > 0 && 1237 ((y >= 0 && kCW_SkRotationDirection == dir) || 1238 (y <= 0 && kCCW_SkRotationDirection == dir))) { 1239 1240 // just return the start-point 1241 quadPoints[0].set(SK_Scalar1, 0); 1242 pointCount = 1; 1243 } else { 1244 if (dir == kCCW_SkRotationDirection) 1245 y = -y; 1246 1247 // what octant (quadratic curve) is [xy] in? 1248 int oct = 0; 1249 bool sameSign = true; 1250 1251 if (0 == y) 1252 { 1253 oct = 4; // 180 1254 SkASSERT(SkScalarAbs(x + SK_Scalar1) <= SK_ScalarNearlyZero); 1255 } 1256 else if (0 == x) 1257 { 1258 SkASSERT(absY - SK_Scalar1 <= SK_ScalarNearlyZero); 1259 if (y > 0) 1260 oct = 2; // 90 1261 else 1262 oct = 6; // 270 1263 } 1264 else 1265 { 1266 if (y < 0) 1267 oct += 4; 1268 if ((x < 0) != (y < 0)) 1269 { 1270 oct += 2; 1271 sameSign = false; 1272 } 1273 if ((absX < absY) == sameSign) 1274 oct += 1; 1275 } 1276 1277 int wholeCount = oct << 1; 1278 memcpy(quadPoints, gQuadCirclePts, (wholeCount + 1) * sizeof(SkPoint)); 1279 1280 const SkPoint* arc = &gQuadCirclePts[wholeCount]; 1281 if (quad_pt2OffCurve(arc, x, y, &quadPoints[wholeCount + 1])) 1282 { 1283 quadPoints[wholeCount + 2].set(x, y); 1284 wholeCount += 2; 1285 } 1286 pointCount = wholeCount + 1; 1287 } 1288 1289 // now handle counter-clockwise and the initial unitStart rotation 1290 SkMatrix matrix; 1291 matrix.setSinCos(uStart.fY, uStart.fX); 1292 if (dir == kCCW_SkRotationDirection) { 1293 matrix.preScale(SK_Scalar1, -SK_Scalar1); 1294 } 1295 if (userMatrix) { 1296 matrix.postConcat(*userMatrix); 1297 } 1298 matrix.mapPoints(quadPoints, pointCount); 1299 return pointCount; 1300 } 1301 1302
