SkMatrix.cpp revision 8f4d2306fa866a26f9448048ff63f692b2ba43aa
1/* 2 * Copyright 2006 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#include "SkMatrix.h" 9#include "Sk64.h" 10#include "SkFloatBits.h" 11#include "SkOnce.h" 12#include "SkString.h" 13 14#define kMatrix22Elem SK_Scalar1 15 16static inline float SkDoubleToFloat(double x) { 17 return static_cast<float>(x); 18} 19 20/* [scale-x skew-x trans-x] [X] [X'] 21 [skew-y scale-y trans-y] * [Y] = [Y'] 22 [persp-0 persp-1 persp-2] [1] [1 ] 23*/ 24 25void SkMatrix::reset() { 26 fMat[kMScaleX] = fMat[kMScaleY] = SK_Scalar1; 27 fMat[kMSkewX] = fMat[kMSkewY] = 28 fMat[kMTransX] = fMat[kMTransY] = 29 fMat[kMPersp0] = fMat[kMPersp1] = 0; 30 fMat[kMPersp2] = kMatrix22Elem; 31 32 this->setTypeMask(kIdentity_Mask | kRectStaysRect_Mask); 33} 34 35// this guy aligns with the masks, so we can compute a mask from a varaible 0/1 36enum { 37 kTranslate_Shift, 38 kScale_Shift, 39 kAffine_Shift, 40 kPerspective_Shift, 41 kRectStaysRect_Shift 42}; 43 44static const int32_t kScalar1Int = 0x3f800000; 45 46uint8_t SkMatrix::computePerspectiveTypeMask() const { 47 // Benchmarking suggests that replacing this set of SkScalarAs2sCompliment 48 // is a win, but replacing those below is not. We don't yet understand 49 // that result. 50 if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 || 51 fMat[kMPersp2] != kMatrix22Elem) { 52 // If this is a perspective transform, we return true for all other 53 // transform flags - this does not disable any optimizations, respects 54 // the rule that the type mask must be conservative, and speeds up 55 // type mask computation. 56 return SkToU8(kORableMasks); 57 } 58 59 return SkToU8(kOnlyPerspectiveValid_Mask | kUnknown_Mask); 60} 61 62uint8_t SkMatrix::computeTypeMask() const { 63 unsigned mask = 0; 64 65 if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 || 66 fMat[kMPersp2] != kMatrix22Elem) { 67 // Once it is determined that that this is a perspective transform, 68 // all other flags are moot as far as optimizations are concerned. 69 return SkToU8(kORableMasks); 70 } 71 72 if (fMat[kMTransX] != 0 || fMat[kMTransY] != 0) { 73 mask |= kTranslate_Mask; 74 } 75 76 int m00 = SkScalarAs2sCompliment(fMat[SkMatrix::kMScaleX]); 77 int m01 = SkScalarAs2sCompliment(fMat[SkMatrix::kMSkewX]); 78 int m10 = SkScalarAs2sCompliment(fMat[SkMatrix::kMSkewY]); 79 int m11 = SkScalarAs2sCompliment(fMat[SkMatrix::kMScaleY]); 80 81 if (m01 | m10) { 82 // The skew components may be scale-inducing, unless we are dealing 83 // with a pure rotation. Testing for a pure rotation is expensive, 84 // so we opt for being conservative by always setting the scale bit. 85 // along with affine. 86 // By doing this, we are also ensuring that matrices have the same 87 // type masks as their inverses. 88 mask |= kAffine_Mask | kScale_Mask; 89 90 // For rectStaysRect, in the affine case, we only need check that 91 // the primary diagonal is all zeros and that the secondary diagonal 92 // is all non-zero. 93 94 // map non-zero to 1 95 m01 = m01 != 0; 96 m10 = m10 != 0; 97 98 int dp0 = 0 == (m00 | m11) ; // true if both are 0 99 int ds1 = m01 & m10; // true if both are 1 100 101 mask |= (dp0 & ds1) << kRectStaysRect_Shift; 102 } else { 103 // Only test for scale explicitly if not affine, since affine sets the 104 // scale bit. 105 if ((m00 - kScalar1Int) | (m11 - kScalar1Int)) { 106 mask |= kScale_Mask; 107 } 108 109 // Not affine, therefore we already know secondary diagonal is 110 // all zeros, so we just need to check that primary diagonal is 111 // all non-zero. 112 113 // map non-zero to 1 114 m00 = m00 != 0; 115 m11 = m11 != 0; 116 117 // record if the (p)rimary diagonal is all non-zero 118 mask |= (m00 & m11) << kRectStaysRect_Shift; 119 } 120 121 return SkToU8(mask); 122} 123 124/////////////////////////////////////////////////////////////////////////////// 125 126bool operator==(const SkMatrix& a, const SkMatrix& b) { 127 const SkScalar* SK_RESTRICT ma = a.fMat; 128 const SkScalar* SK_RESTRICT mb = b.fMat; 129 130 return ma[0] == mb[0] && ma[1] == mb[1] && ma[2] == mb[2] && 131 ma[3] == mb[3] && ma[4] == mb[4] && ma[5] == mb[5] && 132 ma[6] == mb[6] && ma[7] == mb[7] && ma[8] == mb[8]; 133} 134 135/////////////////////////////////////////////////////////////////////////////// 136 137// helper function to determine if upper-left 2x2 of matrix is degenerate 138static inline bool is_degenerate_2x2(SkScalar scaleX, SkScalar skewX, 139 SkScalar skewY, SkScalar scaleY) { 140 SkScalar perp_dot = scaleX*scaleY - skewX*skewY; 141 return SkScalarNearlyZero(perp_dot, SK_ScalarNearlyZero*SK_ScalarNearlyZero); 142} 143 144/////////////////////////////////////////////////////////////////////////////// 145 146bool SkMatrix::isSimilarity(SkScalar tol) const { 147 // if identity or translate matrix 148 TypeMask mask = this->getType(); 149 if (mask <= kTranslate_Mask) { 150 return true; 151 } 152 if (mask & kPerspective_Mask) { 153 return false; 154 } 155 156 SkScalar mx = fMat[kMScaleX]; 157 SkScalar my = fMat[kMScaleY]; 158 // if no skew, can just compare scale factors 159 if (!(mask & kAffine_Mask)) { 160 return !SkScalarNearlyZero(mx) && SkScalarNearlyEqual(SkScalarAbs(mx), SkScalarAbs(my)); 161 } 162 SkScalar sx = fMat[kMSkewX]; 163 SkScalar sy = fMat[kMSkewY]; 164 165 if (is_degenerate_2x2(mx, sx, sy, my)) { 166 return false; 167 } 168 169 // it has scales and skews, but it could also be rotation, check it out. 170 SkVector vec[2]; 171 vec[0].set(mx, sx); 172 vec[1].set(sy, my); 173 174 return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) && 175 SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(), 176 SkScalarSquare(tol)); 177} 178 179bool SkMatrix::preservesRightAngles(SkScalar tol) const { 180 TypeMask mask = this->getType(); 181 182 if (mask <= (SkMatrix::kTranslate_Mask | SkMatrix::kScale_Mask)) { 183 // identity, translate and/or scale 184 return true; 185 } 186 if (mask & kPerspective_Mask) { 187 return false; 188 } 189 190 SkASSERT(mask & kAffine_Mask); 191 192 SkScalar mx = fMat[kMScaleX]; 193 SkScalar my = fMat[kMScaleY]; 194 SkScalar sx = fMat[kMSkewX]; 195 SkScalar sy = fMat[kMSkewY]; 196 197 if (is_degenerate_2x2(mx, sx, sy, my)) { 198 return false; 199 } 200 201 // it has scales and skews, but it could also be rotation, check it out. 202 SkVector vec[2]; 203 vec[0].set(mx, sx); 204 vec[1].set(sy, my); 205 206 return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) && 207 SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(), 208 SkScalarSquare(tol)); 209} 210 211/////////////////////////////////////////////////////////////////////////////// 212 213void SkMatrix::setTranslate(SkScalar dx, SkScalar dy) { 214 if (dx || dy) { 215 fMat[kMTransX] = dx; 216 fMat[kMTransY] = dy; 217 218 fMat[kMScaleX] = fMat[kMScaleY] = SK_Scalar1; 219 fMat[kMSkewX] = fMat[kMSkewY] = 220 fMat[kMPersp0] = fMat[kMPersp1] = 0; 221 fMat[kMPersp2] = kMatrix22Elem; 222 223 this->setTypeMask(kTranslate_Mask | kRectStaysRect_Mask); 224 } else { 225 this->reset(); 226 } 227} 228 229bool SkMatrix::preTranslate(SkScalar dx, SkScalar dy) { 230 if (this->hasPerspective()) { 231 SkMatrix m; 232 m.setTranslate(dx, dy); 233 return this->preConcat(m); 234 } 235 236 if (dx || dy) { 237 fMat[kMTransX] += SkScalarMul(fMat[kMScaleX], dx) + 238 SkScalarMul(fMat[kMSkewX], dy); 239 fMat[kMTransY] += SkScalarMul(fMat[kMSkewY], dx) + 240 SkScalarMul(fMat[kMScaleY], dy); 241 242 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask); 243 } 244 return true; 245} 246 247bool SkMatrix::postTranslate(SkScalar dx, SkScalar dy) { 248 if (this->hasPerspective()) { 249 SkMatrix m; 250 m.setTranslate(dx, dy); 251 return this->postConcat(m); 252 } 253 254 if (dx || dy) { 255 fMat[kMTransX] += dx; 256 fMat[kMTransY] += dy; 257 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask); 258 } 259 return true; 260} 261 262/////////////////////////////////////////////////////////////////////////////// 263 264void SkMatrix::setScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) { 265 if (SK_Scalar1 == sx && SK_Scalar1 == sy) { 266 this->reset(); 267 } else { 268 fMat[kMScaleX] = sx; 269 fMat[kMScaleY] = sy; 270 fMat[kMTransX] = px - SkScalarMul(sx, px); 271 fMat[kMTransY] = py - SkScalarMul(sy, py); 272 fMat[kMPersp2] = kMatrix22Elem; 273 274 fMat[kMSkewX] = fMat[kMSkewY] = 275 fMat[kMPersp0] = fMat[kMPersp1] = 0; 276 277 this->setTypeMask(kScale_Mask | kTranslate_Mask | kRectStaysRect_Mask); 278 } 279} 280 281void SkMatrix::setScale(SkScalar sx, SkScalar sy) { 282 if (SK_Scalar1 == sx && SK_Scalar1 == sy) { 283 this->reset(); 284 } else { 285 fMat[kMScaleX] = sx; 286 fMat[kMScaleY] = sy; 287 fMat[kMPersp2] = kMatrix22Elem; 288 289 fMat[kMTransX] = fMat[kMTransY] = 290 fMat[kMSkewX] = fMat[kMSkewY] = 291 fMat[kMPersp0] = fMat[kMPersp1] = 0; 292 293 this->setTypeMask(kScale_Mask | kRectStaysRect_Mask); 294 } 295} 296 297bool SkMatrix::setIDiv(int divx, int divy) { 298 if (!divx || !divy) { 299 return false; 300 } 301 this->setScale(SK_Scalar1 / divx, SK_Scalar1 / divy); 302 return true; 303} 304 305bool SkMatrix::preScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) { 306 SkMatrix m; 307 m.setScale(sx, sy, px, py); 308 return this->preConcat(m); 309} 310 311bool SkMatrix::preScale(SkScalar sx, SkScalar sy) { 312 if (SK_Scalar1 == sx && SK_Scalar1 == sy) { 313 return true; 314 } 315 316#ifdef SK_SCALAR_IS_FIXED 317 SkMatrix m; 318 m.setScale(sx, sy); 319 return this->preConcat(m); 320#else 321 // the assumption is that these multiplies are very cheap, and that 322 // a full concat and/or just computing the matrix type is more expensive. 323 // Also, the fixed-point case checks for overflow, but the float doesn't, 324 // so we can get away with these blind multiplies. 325 326 fMat[kMScaleX] = SkScalarMul(fMat[kMScaleX], sx); 327 fMat[kMSkewY] = SkScalarMul(fMat[kMSkewY], sx); 328 fMat[kMPersp0] = SkScalarMul(fMat[kMPersp0], sx); 329 330 fMat[kMSkewX] = SkScalarMul(fMat[kMSkewX], sy); 331 fMat[kMScaleY] = SkScalarMul(fMat[kMScaleY], sy); 332 fMat[kMPersp1] = SkScalarMul(fMat[kMPersp1], sy); 333 334 this->orTypeMask(kScale_Mask); 335 return true; 336#endif 337} 338 339bool SkMatrix::postScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) { 340 if (SK_Scalar1 == sx && SK_Scalar1 == sy) { 341 return true; 342 } 343 SkMatrix m; 344 m.setScale(sx, sy, px, py); 345 return this->postConcat(m); 346} 347 348bool SkMatrix::postScale(SkScalar sx, SkScalar sy) { 349 if (SK_Scalar1 == sx && SK_Scalar1 == sy) { 350 return true; 351 } 352 SkMatrix m; 353 m.setScale(sx, sy); 354 return this->postConcat(m); 355} 356 357#ifdef SK_SCALAR_IS_FIXED 358 static inline SkFixed roundidiv(SkFixed numer, int denom) { 359 int ns = numer >> 31; 360 int ds = denom >> 31; 361 numer = (numer ^ ns) - ns; 362 denom = (denom ^ ds) - ds; 363 364 SkFixed answer = (numer + (denom >> 1)) / denom; 365 int as = ns ^ ds; 366 return (answer ^ as) - as; 367 } 368#endif 369 370// this guy perhaps can go away, if we have a fract/high-precision way to 371// scale matrices 372bool SkMatrix::postIDiv(int divx, int divy) { 373 if (divx == 0 || divy == 0) { 374 return false; 375 } 376 377#ifdef SK_SCALAR_IS_FIXED 378 fMat[kMScaleX] = roundidiv(fMat[kMScaleX], divx); 379 fMat[kMSkewX] = roundidiv(fMat[kMSkewX], divx); 380 fMat[kMTransX] = roundidiv(fMat[kMTransX], divx); 381 382 fMat[kMScaleY] = roundidiv(fMat[kMScaleY], divy); 383 fMat[kMSkewY] = roundidiv(fMat[kMSkewY], divy); 384 fMat[kMTransY] = roundidiv(fMat[kMTransY], divy); 385#else 386 const float invX = 1.f / divx; 387 const float invY = 1.f / divy; 388 389 fMat[kMScaleX] *= invX; 390 fMat[kMSkewX] *= invX; 391 fMat[kMTransX] *= invX; 392 393 fMat[kMScaleY] *= invY; 394 fMat[kMSkewY] *= invY; 395 fMat[kMTransY] *= invY; 396#endif 397 398 this->setTypeMask(kUnknown_Mask); 399 return true; 400} 401 402//////////////////////////////////////////////////////////////////////////////////// 403 404void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV, 405 SkScalar px, SkScalar py) { 406 const SkScalar oneMinusCosV = SK_Scalar1 - cosV; 407 408 fMat[kMScaleX] = cosV; 409 fMat[kMSkewX] = -sinV; 410 fMat[kMTransX] = SkScalarMul(sinV, py) + SkScalarMul(oneMinusCosV, px); 411 412 fMat[kMSkewY] = sinV; 413 fMat[kMScaleY] = cosV; 414 fMat[kMTransY] = SkScalarMul(-sinV, px) + SkScalarMul(oneMinusCosV, py); 415 416 fMat[kMPersp0] = fMat[kMPersp1] = 0; 417 fMat[kMPersp2] = kMatrix22Elem; 418 419 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask); 420} 421 422void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV) { 423 fMat[kMScaleX] = cosV; 424 fMat[kMSkewX] = -sinV; 425 fMat[kMTransX] = 0; 426 427 fMat[kMSkewY] = sinV; 428 fMat[kMScaleY] = cosV; 429 fMat[kMTransY] = 0; 430 431 fMat[kMPersp0] = fMat[kMPersp1] = 0; 432 fMat[kMPersp2] = kMatrix22Elem; 433 434 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask); 435} 436 437void SkMatrix::setRotate(SkScalar degrees, SkScalar px, SkScalar py) { 438 SkScalar sinV, cosV; 439 sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV); 440 this->setSinCos(sinV, cosV, px, py); 441} 442 443void SkMatrix::setRotate(SkScalar degrees) { 444 SkScalar sinV, cosV; 445 sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV); 446 this->setSinCos(sinV, cosV); 447} 448 449bool SkMatrix::preRotate(SkScalar degrees, SkScalar px, SkScalar py) { 450 SkMatrix m; 451 m.setRotate(degrees, px, py); 452 return this->preConcat(m); 453} 454 455bool SkMatrix::preRotate(SkScalar degrees) { 456 SkMatrix m; 457 m.setRotate(degrees); 458 return this->preConcat(m); 459} 460 461bool SkMatrix::postRotate(SkScalar degrees, SkScalar px, SkScalar py) { 462 SkMatrix m; 463 m.setRotate(degrees, px, py); 464 return this->postConcat(m); 465} 466 467bool SkMatrix::postRotate(SkScalar degrees) { 468 SkMatrix m; 469 m.setRotate(degrees); 470 return this->postConcat(m); 471} 472 473//////////////////////////////////////////////////////////////////////////////////// 474 475void SkMatrix::setSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) { 476 fMat[kMScaleX] = SK_Scalar1; 477 fMat[kMSkewX] = sx; 478 fMat[kMTransX] = SkScalarMul(-sx, py); 479 480 fMat[kMSkewY] = sy; 481 fMat[kMScaleY] = SK_Scalar1; 482 fMat[kMTransY] = SkScalarMul(-sy, px); 483 484 fMat[kMPersp0] = fMat[kMPersp1] = 0; 485 fMat[kMPersp2] = kMatrix22Elem; 486 487 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask); 488} 489 490void SkMatrix::setSkew(SkScalar sx, SkScalar sy) { 491 fMat[kMScaleX] = SK_Scalar1; 492 fMat[kMSkewX] = sx; 493 fMat[kMTransX] = 0; 494 495 fMat[kMSkewY] = sy; 496 fMat[kMScaleY] = SK_Scalar1; 497 fMat[kMTransY] = 0; 498 499 fMat[kMPersp0] = fMat[kMPersp1] = 0; 500 fMat[kMPersp2] = kMatrix22Elem; 501 502 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask); 503} 504 505bool SkMatrix::preSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) { 506 SkMatrix m; 507 m.setSkew(sx, sy, px, py); 508 return this->preConcat(m); 509} 510 511bool SkMatrix::preSkew(SkScalar sx, SkScalar sy) { 512 SkMatrix m; 513 m.setSkew(sx, sy); 514 return this->preConcat(m); 515} 516 517bool SkMatrix::postSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) { 518 SkMatrix m; 519 m.setSkew(sx, sy, px, py); 520 return this->postConcat(m); 521} 522 523bool SkMatrix::postSkew(SkScalar sx, SkScalar sy) { 524 SkMatrix m; 525 m.setSkew(sx, sy); 526 return this->postConcat(m); 527} 528 529/////////////////////////////////////////////////////////////////////////////// 530 531bool SkMatrix::setRectToRect(const SkRect& src, const SkRect& dst, 532 ScaleToFit align) 533{ 534 if (src.isEmpty()) { 535 this->reset(); 536 return false; 537 } 538 539 if (dst.isEmpty()) { 540 sk_bzero(fMat, 8 * sizeof(SkScalar)); 541 this->setTypeMask(kScale_Mask | kRectStaysRect_Mask); 542 } else { 543 SkScalar tx, sx = SkScalarDiv(dst.width(), src.width()); 544 SkScalar ty, sy = SkScalarDiv(dst.height(), src.height()); 545 bool xLarger = false; 546 547 if (align != kFill_ScaleToFit) { 548 if (sx > sy) { 549 xLarger = true; 550 sx = sy; 551 } else { 552 sy = sx; 553 } 554 } 555 556 tx = dst.fLeft - SkScalarMul(src.fLeft, sx); 557 ty = dst.fTop - SkScalarMul(src.fTop, sy); 558 if (align == kCenter_ScaleToFit || align == kEnd_ScaleToFit) { 559 SkScalar diff; 560 561 if (xLarger) { 562 diff = dst.width() - SkScalarMul(src.width(), sy); 563 } else { 564 diff = dst.height() - SkScalarMul(src.height(), sy); 565 } 566 567 if (align == kCenter_ScaleToFit) { 568 diff = SkScalarHalf(diff); 569 } 570 571 if (xLarger) { 572 tx += diff; 573 } else { 574 ty += diff; 575 } 576 } 577 578 fMat[kMScaleX] = sx; 579 fMat[kMScaleY] = sy; 580 fMat[kMTransX] = tx; 581 fMat[kMTransY] = ty; 582 fMat[kMSkewX] = fMat[kMSkewY] = 583 fMat[kMPersp0] = fMat[kMPersp1] = 0; 584 585 unsigned mask = kRectStaysRect_Mask; 586 if (sx != SK_Scalar1 || sy != SK_Scalar1) { 587 mask |= kScale_Mask; 588 } 589 if (tx || ty) { 590 mask |= kTranslate_Mask; 591 } 592 this->setTypeMask(mask); 593 } 594 // shared cleanup 595 fMat[kMPersp2] = kMatrix22Elem; 596 return true; 597} 598 599/////////////////////////////////////////////////////////////////////////////// 600 601static inline int fixmuladdmul(float a, float b, float c, float d, 602 float* result) { 603 *result = SkDoubleToFloat((double)a * b + (double)c * d); 604 return true; 605} 606 607static inline bool rowcol3(const float row[], const float col[], 608 float* result) { 609 *result = row[0] * col[0] + row[1] * col[3] + row[2] * col[6]; 610 return true; 611} 612 613static inline int negifaddoverflows(float& result, float a, float b) { 614 result = a + b; 615 return 0; 616} 617 618static void normalize_perspective(SkScalar mat[9]) { 619 if (SkScalarAbs(mat[SkMatrix::kMPersp2]) > kMatrix22Elem) { 620 for (int i = 0; i < 9; i++) 621 mat[i] = SkScalarHalf(mat[i]); 622 } 623} 624 625bool SkMatrix::setConcat(const SkMatrix& a, const SkMatrix& b) { 626 TypeMask aType = a.getPerspectiveTypeMaskOnly(); 627 TypeMask bType = b.getPerspectiveTypeMaskOnly(); 628 629 if (a.isTriviallyIdentity()) { 630 *this = b; 631 } else if (b.isTriviallyIdentity()) { 632 *this = a; 633 } else { 634 SkMatrix tmp; 635 636 if ((aType | bType) & kPerspective_Mask) { 637 if (!rowcol3(&a.fMat[0], &b.fMat[0], &tmp.fMat[kMScaleX])) { 638 return false; 639 } 640 if (!rowcol3(&a.fMat[0], &b.fMat[1], &tmp.fMat[kMSkewX])) { 641 return false; 642 } 643 if (!rowcol3(&a.fMat[0], &b.fMat[2], &tmp.fMat[kMTransX])) { 644 return false; 645 } 646 647 if (!rowcol3(&a.fMat[3], &b.fMat[0], &tmp.fMat[kMSkewY])) { 648 return false; 649 } 650 if (!rowcol3(&a.fMat[3], &b.fMat[1], &tmp.fMat[kMScaleY])) { 651 return false; 652 } 653 if (!rowcol3(&a.fMat[3], &b.fMat[2], &tmp.fMat[kMTransY])) { 654 return false; 655 } 656 657 if (!rowcol3(&a.fMat[6], &b.fMat[0], &tmp.fMat[kMPersp0])) { 658 return false; 659 } 660 if (!rowcol3(&a.fMat[6], &b.fMat[1], &tmp.fMat[kMPersp1])) { 661 return false; 662 } 663 if (!rowcol3(&a.fMat[6], &b.fMat[2], &tmp.fMat[kMPersp2])) { 664 return false; 665 } 666 667 normalize_perspective(tmp.fMat); 668 tmp.setTypeMask(kUnknown_Mask); 669 } else { // not perspective 670 if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMScaleX], 671 a.fMat[kMSkewX], b.fMat[kMSkewY], &tmp.fMat[kMScaleX])) { 672 return false; 673 } 674 if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMSkewX], 675 a.fMat[kMSkewX], b.fMat[kMScaleY], &tmp.fMat[kMSkewX])) { 676 return false; 677 } 678 if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMTransX], 679 a.fMat[kMSkewX], b.fMat[kMTransY], &tmp.fMat[kMTransX])) { 680 return false; 681 } 682 if (negifaddoverflows(tmp.fMat[kMTransX], tmp.fMat[kMTransX], 683 a.fMat[kMTransX]) < 0) { 684 return false; 685 } 686 687 if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMScaleX], 688 a.fMat[kMScaleY], b.fMat[kMSkewY], &tmp.fMat[kMSkewY])) { 689 return false; 690 } 691 if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMSkewX], 692 a.fMat[kMScaleY], b.fMat[kMScaleY], &tmp.fMat[kMScaleY])) { 693 return false; 694 } 695 if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMTransX], 696 a.fMat[kMScaleY], b.fMat[kMTransY], &tmp.fMat[kMTransY])) { 697 return false; 698 } 699 if (negifaddoverflows(tmp.fMat[kMTransY], tmp.fMat[kMTransY], 700 a.fMat[kMTransY]) < 0) { 701 return false; 702 } 703 704 tmp.fMat[kMPersp0] = tmp.fMat[kMPersp1] = 0; 705 tmp.fMat[kMPersp2] = kMatrix22Elem; 706 //SkDebugf("Concat mat non-persp type: %d\n", tmp.getType()); 707 //SkASSERT(!(tmp.getType() & kPerspective_Mask)); 708 tmp.setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask); 709 } 710 *this = tmp; 711 } 712 return true; 713} 714 715bool SkMatrix::preConcat(const SkMatrix& mat) { 716 // check for identity first, so we don't do a needless copy of ourselves 717 // to ourselves inside setConcat() 718 return mat.isIdentity() || this->setConcat(*this, mat); 719} 720 721bool SkMatrix::postConcat(const SkMatrix& mat) { 722 // check for identity first, so we don't do a needless copy of ourselves 723 // to ourselves inside setConcat() 724 return mat.isIdentity() || this->setConcat(mat, *this); 725} 726 727/////////////////////////////////////////////////////////////////////////////// 728 729/* Matrix inversion is very expensive, but also the place where keeping 730 precision may be most important (here and matrix concat). Hence to avoid 731 bitmap blitting artifacts when walking the inverse, we use doubles for 732 the intermediate math, even though we know that is more expensive. 733 */ 734 735typedef double SkDetScalar; 736#define SkPerspMul(a, b) SkScalarMul(a, b) 737#define SkScalarMulShift(a, b, s) SkDoubleToFloat((a) * (b)) 738static double sk_inv_determinant(const float mat[9], int isPerspective, 739 int* /* (only used in Fixed case) */) { 740 double det; 741 742 if (isPerspective) { 743 det = mat[SkMatrix::kMScaleX] * ((double)mat[SkMatrix::kMScaleY] * mat[SkMatrix::kMPersp2] - (double)mat[SkMatrix::kMTransY] * mat[SkMatrix::kMPersp1]) + 744 mat[SkMatrix::kMSkewX] * ((double)mat[SkMatrix::kMTransY] * mat[SkMatrix::kMPersp0] - (double)mat[SkMatrix::kMSkewY] * mat[SkMatrix::kMPersp2]) + 745 mat[SkMatrix::kMTransX] * ((double)mat[SkMatrix::kMSkewY] * mat[SkMatrix::kMPersp1] - (double)mat[SkMatrix::kMScaleY] * mat[SkMatrix::kMPersp0]); 746 } else { 747 det = (double)mat[SkMatrix::kMScaleX] * mat[SkMatrix::kMScaleY] - (double)mat[SkMatrix::kMSkewX] * mat[SkMatrix::kMSkewY]; 748 } 749 750 // Since the determinant is on the order of the cube of the matrix members, 751 // compare to the cube of the default nearly-zero constant (although an 752 // estimate of the condition number would be better if it wasn't so expensive). 753 if (SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero * SK_ScalarNearlyZero)) { 754 return 0; 755 } 756 return 1.0 / det; 757} 758// we declar a,b,c,d to all be doubles, because we want to perform 759// double-precision muls and subtract, even though the original values are 760// from the matrix, which are floats. 761static float inline mul_diff_scale(double a, double b, double c, double d, 762 double scale) { 763 return SkDoubleToFloat((a * b - c * d) * scale); 764} 765 766void SkMatrix::SetAffineIdentity(SkScalar affine[6]) { 767 affine[kAScaleX] = SK_Scalar1; 768 affine[kASkewY] = 0; 769 affine[kASkewX] = 0; 770 affine[kAScaleY] = SK_Scalar1; 771 affine[kATransX] = 0; 772 affine[kATransY] = 0; 773} 774 775bool SkMatrix::asAffine(SkScalar affine[6]) const { 776 if (this->hasPerspective()) { 777 return false; 778 } 779 if (affine) { 780 affine[kAScaleX] = this->fMat[kMScaleX]; 781 affine[kASkewY] = this->fMat[kMSkewY]; 782 affine[kASkewX] = this->fMat[kMSkewX]; 783 affine[kAScaleY] = this->fMat[kMScaleY]; 784 affine[kATransX] = this->fMat[kMTransX]; 785 affine[kATransY] = this->fMat[kMTransY]; 786 } 787 return true; 788} 789 790bool SkMatrix::invertNonIdentity(SkMatrix* inv) const { 791 SkASSERT(!this->isIdentity()); 792 793 TypeMask mask = this->getType(); 794 795 if (0 == (mask & ~(kScale_Mask | kTranslate_Mask))) { 796 bool invertible = true; 797 if (inv) { 798 if (mask & kScale_Mask) { 799 SkScalar invX = fMat[kMScaleX]; 800 SkScalar invY = fMat[kMScaleY]; 801 if (0 == invX || 0 == invY) { 802 return false; 803 } 804 invX = SkScalarInvert(invX); 805 invY = SkScalarInvert(invY); 806 807 // Must be careful when writing to inv, since it may be the 808 // same memory as this. 809 810 inv->fMat[kMSkewX] = inv->fMat[kMSkewY] = 811 inv->fMat[kMPersp0] = inv->fMat[kMPersp1] = 0; 812 813 inv->fMat[kMScaleX] = invX; 814 inv->fMat[kMScaleY] = invY; 815 inv->fMat[kMPersp2] = kMatrix22Elem; 816 inv->fMat[kMTransX] = -SkScalarMul(fMat[kMTransX], invX); 817 inv->fMat[kMTransY] = -SkScalarMul(fMat[kMTransY], invY); 818 819 inv->setTypeMask(mask | kRectStaysRect_Mask); 820 } else { 821 // translate only 822 inv->setTranslate(-fMat[kMTransX], -fMat[kMTransY]); 823 } 824 } else { // inv is NULL, just check if we're invertible 825 if (!fMat[kMScaleX] || !fMat[kMScaleY]) { 826 invertible = false; 827 } 828 } 829 return invertible; 830 } 831 832 int isPersp = mask & kPerspective_Mask; 833 int shift; 834 SkDetScalar scale = sk_inv_determinant(fMat, isPersp, &shift); 835 836 if (scale == 0) { // underflow 837 return false; 838 } 839 840 if (inv) { 841 SkMatrix tmp; 842 if (inv == this) { 843 inv = &tmp; 844 } 845 846 if (isPersp) { 847 shift = 61 - shift; 848 inv->fMat[kMScaleX] = SkScalarMulShift(SkPerspMul(fMat[kMScaleY], fMat[kMPersp2]) - SkPerspMul(fMat[kMTransY], fMat[kMPersp1]), scale, shift); 849 inv->fMat[kMSkewX] = SkScalarMulShift(SkPerspMul(fMat[kMTransX], fMat[kMPersp1]) - SkPerspMul(fMat[kMSkewX], fMat[kMPersp2]), scale, shift); 850 inv->fMat[kMTransX] = SkScalarMulShift(SkScalarMul(fMat[kMSkewX], fMat[kMTransY]) - SkScalarMul(fMat[kMTransX], fMat[kMScaleY]), scale, shift); 851 852 inv->fMat[kMSkewY] = SkScalarMulShift(SkPerspMul(fMat[kMTransY], fMat[kMPersp0]) - SkPerspMul(fMat[kMSkewY], fMat[kMPersp2]), scale, shift); 853 inv->fMat[kMScaleY] = SkScalarMulShift(SkPerspMul(fMat[kMScaleX], fMat[kMPersp2]) - SkPerspMul(fMat[kMTransX], fMat[kMPersp0]), scale, shift); 854 inv->fMat[kMTransY] = SkScalarMulShift(SkScalarMul(fMat[kMTransX], fMat[kMSkewY]) - SkScalarMul(fMat[kMScaleX], fMat[kMTransY]), scale, shift); 855 856 inv->fMat[kMPersp0] = SkScalarMulShift(SkScalarMul(fMat[kMSkewY], fMat[kMPersp1]) - SkScalarMul(fMat[kMScaleY], fMat[kMPersp0]), scale, shift); 857 inv->fMat[kMPersp1] = SkScalarMulShift(SkScalarMul(fMat[kMSkewX], fMat[kMPersp0]) - SkScalarMul(fMat[kMScaleX], fMat[kMPersp1]), scale, shift); 858 inv->fMat[kMPersp2] = SkScalarMulShift(SkScalarMul(fMat[kMScaleX], fMat[kMScaleY]) - SkScalarMul(fMat[kMSkewX], fMat[kMSkewY]), scale, shift); 859#ifdef SK_SCALAR_IS_FIXED 860 if (SkAbs32(inv->fMat[kMPersp2]) > SK_Fixed1) { 861 Sk64 tmp; 862 863 tmp.set(SK_Fract1); 864 tmp.shiftLeft(16); 865 tmp.div(inv->fMat[kMPersp2], Sk64::kRound_DivOption); 866 867 SkFract scale = tmp.get32(); 868 869 for (int i = 0; i < 9; i++) { 870 inv->fMat[i] = SkFractMul(inv->fMat[i], scale); 871 } 872 } 873 inv->fMat[kMPersp2] = SkFixedToFract(inv->fMat[kMPersp2]); 874#endif 875 } else { // not perspective 876#ifdef SK_SCALAR_IS_FIXED 877 Sk64 tx, ty; 878 int clzNumer; 879 880 // check the 2x2 for overflow 881 { 882 int32_t value = SkAbs32(fMat[kMScaleY]); 883 value |= SkAbs32(fMat[kMSkewX]); 884 value |= SkAbs32(fMat[kMScaleX]); 885 value |= SkAbs32(fMat[kMSkewY]); 886 clzNumer = SkCLZ(value); 887 if (shift - clzNumer > 31) 888 return false; // overflow 889 } 890 891 set_muladdmul(&tx, fMat[kMSkewX], fMat[kMTransY], -fMat[kMScaleY], fMat[kMTransX]); 892 set_muladdmul(&ty, fMat[kMSkewY], fMat[kMTransX], -fMat[kMScaleX], fMat[kMTransY]); 893 // check tx,ty for overflow 894 clzNumer = SkCLZ(SkAbs32(tx.fHi) | SkAbs32(ty.fHi)); 895 if (shift - clzNumer > 14) { 896 return false; // overflow 897 } 898 899 int fixedShift = 61 - shift; 900 int sk64shift = 44 - shift + clzNumer; 901 902 inv->fMat[kMScaleX] = SkMulShift(fMat[kMScaleY], scale, fixedShift); 903 inv->fMat[kMSkewX] = SkMulShift(-fMat[kMSkewX], scale, fixedShift); 904 inv->fMat[kMTransX] = SkMulShift(tx.getShiftRight(33 - clzNumer), scale, sk64shift); 905 906 inv->fMat[kMSkewY] = SkMulShift(-fMat[kMSkewY], scale, fixedShift); 907 inv->fMat[kMScaleY] = SkMulShift(fMat[kMScaleX], scale, fixedShift); 908 inv->fMat[kMTransY] = SkMulShift(ty.getShiftRight(33 - clzNumer), scale, sk64shift); 909#else 910 inv->fMat[kMScaleX] = SkDoubleToFloat(fMat[kMScaleY] * scale); 911 inv->fMat[kMSkewX] = SkDoubleToFloat(-fMat[kMSkewX] * scale); 912 inv->fMat[kMTransX] = mul_diff_scale(fMat[kMSkewX], fMat[kMTransY], 913 fMat[kMScaleY], fMat[kMTransX], scale); 914 915 inv->fMat[kMSkewY] = SkDoubleToFloat(-fMat[kMSkewY] * scale); 916 inv->fMat[kMScaleY] = SkDoubleToFloat(fMat[kMScaleX] * scale); 917 inv->fMat[kMTransY] = mul_diff_scale(fMat[kMSkewY], fMat[kMTransX], 918 fMat[kMScaleX], fMat[kMTransY], scale); 919#endif 920 inv->fMat[kMPersp0] = 0; 921 inv->fMat[kMPersp1] = 0; 922 inv->fMat[kMPersp2] = kMatrix22Elem; 923 924 } 925 926 inv->setTypeMask(fTypeMask); 927 928 if (inv == &tmp) { 929 *(SkMatrix*)this = tmp; 930 } 931 } 932 return true; 933} 934 935/////////////////////////////////////////////////////////////////////////////// 936 937void SkMatrix::Identity_pts(const SkMatrix& m, SkPoint dst[], 938 const SkPoint src[], int count) { 939 SkASSERT(m.getType() == 0); 940 941 if (dst != src && count > 0) 942 memcpy(dst, src, count * sizeof(SkPoint)); 943} 944 945void SkMatrix::Trans_pts(const SkMatrix& m, SkPoint dst[], 946 const SkPoint src[], int count) { 947 SkASSERT(m.getType() == kTranslate_Mask); 948 949 if (count > 0) { 950 SkScalar tx = m.fMat[kMTransX]; 951 SkScalar ty = m.fMat[kMTransY]; 952 do { 953 dst->fY = src->fY + ty; 954 dst->fX = src->fX + tx; 955 src += 1; 956 dst += 1; 957 } while (--count); 958 } 959} 960 961void SkMatrix::Scale_pts(const SkMatrix& m, SkPoint dst[], 962 const SkPoint src[], int count) { 963 SkASSERT(m.getType() == kScale_Mask); 964 965 if (count > 0) { 966 SkScalar mx = m.fMat[kMScaleX]; 967 SkScalar my = m.fMat[kMScaleY]; 968 do { 969 dst->fY = SkScalarMul(src->fY, my); 970 dst->fX = SkScalarMul(src->fX, mx); 971 src += 1; 972 dst += 1; 973 } while (--count); 974 } 975} 976 977void SkMatrix::ScaleTrans_pts(const SkMatrix& m, SkPoint dst[], 978 const SkPoint src[], int count) { 979 SkASSERT(m.getType() == (kScale_Mask | kTranslate_Mask)); 980 981 if (count > 0) { 982 SkScalar mx = m.fMat[kMScaleX]; 983 SkScalar my = m.fMat[kMScaleY]; 984 SkScalar tx = m.fMat[kMTransX]; 985 SkScalar ty = m.fMat[kMTransY]; 986 do { 987 dst->fY = SkScalarMulAdd(src->fY, my, ty); 988 dst->fX = SkScalarMulAdd(src->fX, mx, tx); 989 src += 1; 990 dst += 1; 991 } while (--count); 992 } 993} 994 995void SkMatrix::Rot_pts(const SkMatrix& m, SkPoint dst[], 996 const SkPoint src[], int count) { 997 SkASSERT((m.getType() & (kPerspective_Mask | kTranslate_Mask)) == 0); 998 999 if (count > 0) { 1000 SkScalar mx = m.fMat[kMScaleX]; 1001 SkScalar my = m.fMat[kMScaleY]; 1002 SkScalar kx = m.fMat[kMSkewX]; 1003 SkScalar ky = m.fMat[kMSkewY]; 1004 do { 1005 SkScalar sy = src->fY; 1006 SkScalar sx = src->fX; 1007 src += 1; 1008 dst->fY = SkScalarMul(sx, ky) + SkScalarMul(sy, my); 1009 dst->fX = SkScalarMul(sx, mx) + SkScalarMul(sy, kx); 1010 dst += 1; 1011 } while (--count); 1012 } 1013} 1014 1015void SkMatrix::RotTrans_pts(const SkMatrix& m, SkPoint dst[], 1016 const SkPoint src[], int count) { 1017 SkASSERT(!m.hasPerspective()); 1018 1019 if (count > 0) { 1020 SkScalar mx = m.fMat[kMScaleX]; 1021 SkScalar my = m.fMat[kMScaleY]; 1022 SkScalar kx = m.fMat[kMSkewX]; 1023 SkScalar ky = m.fMat[kMSkewY]; 1024 SkScalar tx = m.fMat[kMTransX]; 1025 SkScalar ty = m.fMat[kMTransY]; 1026 do { 1027 SkScalar sy = src->fY; 1028 SkScalar sx = src->fX; 1029 src += 1; 1030 dst->fY = SkScalarMul(sx, ky) + SkScalarMulAdd(sy, my, ty); 1031 dst->fX = SkScalarMul(sx, mx) + SkScalarMulAdd(sy, kx, tx); 1032 dst += 1; 1033 } while (--count); 1034 } 1035} 1036 1037void SkMatrix::Persp_pts(const SkMatrix& m, SkPoint dst[], 1038 const SkPoint src[], int count) { 1039 SkASSERT(m.hasPerspective()); 1040 1041#ifdef SK_SCALAR_IS_FIXED 1042 SkFixed persp2 = SkFractToFixed(m.fMat[kMPersp2]); 1043#endif 1044 1045 if (count > 0) { 1046 do { 1047 SkScalar sy = src->fY; 1048 SkScalar sx = src->fX; 1049 src += 1; 1050 1051 SkScalar x = SkScalarMul(sx, m.fMat[kMScaleX]) + 1052 SkScalarMul(sy, m.fMat[kMSkewX]) + m.fMat[kMTransX]; 1053 SkScalar y = SkScalarMul(sx, m.fMat[kMSkewY]) + 1054 SkScalarMul(sy, m.fMat[kMScaleY]) + m.fMat[kMTransY]; 1055#ifdef SK_SCALAR_IS_FIXED 1056 SkFixed z = SkFractMul(sx, m.fMat[kMPersp0]) + 1057 SkFractMul(sy, m.fMat[kMPersp1]) + persp2; 1058#else 1059 float z = SkScalarMul(sx, m.fMat[kMPersp0]) + 1060 SkScalarMulAdd(sy, m.fMat[kMPersp1], m.fMat[kMPersp2]); 1061#endif 1062 if (z) { 1063 z = SkScalarFastInvert(z); 1064 } 1065 1066 dst->fY = SkScalarMul(y, z); 1067 dst->fX = SkScalarMul(x, z); 1068 dst += 1; 1069 } while (--count); 1070 } 1071} 1072 1073const SkMatrix::MapPtsProc SkMatrix::gMapPtsProcs[] = { 1074 SkMatrix::Identity_pts, SkMatrix::Trans_pts, 1075 SkMatrix::Scale_pts, SkMatrix::ScaleTrans_pts, 1076 SkMatrix::Rot_pts, SkMatrix::RotTrans_pts, 1077 SkMatrix::Rot_pts, SkMatrix::RotTrans_pts, 1078 // repeat the persp proc 8 times 1079 SkMatrix::Persp_pts, SkMatrix::Persp_pts, 1080 SkMatrix::Persp_pts, SkMatrix::Persp_pts, 1081 SkMatrix::Persp_pts, SkMatrix::Persp_pts, 1082 SkMatrix::Persp_pts, SkMatrix::Persp_pts 1083}; 1084 1085void SkMatrix::mapPoints(SkPoint dst[], const SkPoint src[], int count) const { 1086 SkASSERT((dst && src && count > 0) || 0 == count); 1087 // no partial overlap 1088 SkASSERT(src == dst || &dst[count] <= &src[0] || &src[count] <= &dst[0]); 1089 1090 this->getMapPtsProc()(*this, dst, src, count); 1091} 1092 1093/////////////////////////////////////////////////////////////////////////////// 1094 1095void SkMatrix::mapHomogeneousPoints(SkScalar dst[], const SkScalar src[], int count) const { 1096 SkASSERT((dst && src && count > 0) || 0 == count); 1097 // no partial overlap 1098 SkASSERT(src == dst || SkAbs32((int32_t)(src - dst)) >= 3*count); 1099 1100 if (count > 0) { 1101 if (this->isIdentity()) { 1102 memcpy(dst, src, 3*count*sizeof(SkScalar)); 1103 return; 1104 } 1105 do { 1106 SkScalar sx = src[0]; 1107 SkScalar sy = src[1]; 1108 SkScalar sw = src[2]; 1109 src += 3; 1110 1111 SkScalar x = SkScalarMul(sx, fMat[kMScaleX]) + 1112 SkScalarMul(sy, fMat[kMSkewX]) + 1113 SkScalarMul(sw, fMat[kMTransX]); 1114 SkScalar y = SkScalarMul(sx, fMat[kMSkewY]) + 1115 SkScalarMul(sy, fMat[kMScaleY]) + 1116 SkScalarMul(sw, fMat[kMTransY]); 1117 SkScalar w = SkScalarMul(sx, fMat[kMPersp0]) + 1118 SkScalarMul(sy, fMat[kMPersp1]) + 1119 SkScalarMul(sw, fMat[kMPersp2]); 1120 1121 dst[0] = x; 1122 dst[1] = y; 1123 dst[2] = w; 1124 dst += 3; 1125 } while (--count); 1126 } 1127} 1128 1129/////////////////////////////////////////////////////////////////////////////// 1130 1131void SkMatrix::mapVectors(SkPoint dst[], const SkPoint src[], int count) const { 1132 if (this->hasPerspective()) { 1133 SkPoint origin; 1134 1135 MapXYProc proc = this->getMapXYProc(); 1136 proc(*this, 0, 0, &origin); 1137 1138 for (int i = count - 1; i >= 0; --i) { 1139 SkPoint tmp; 1140 1141 proc(*this, src[i].fX, src[i].fY, &tmp); 1142 dst[i].set(tmp.fX - origin.fX, tmp.fY - origin.fY); 1143 } 1144 } else { 1145 SkMatrix tmp = *this; 1146 1147 tmp.fMat[kMTransX] = tmp.fMat[kMTransY] = 0; 1148 tmp.clearTypeMask(kTranslate_Mask); 1149 tmp.mapPoints(dst, src, count); 1150 } 1151} 1152 1153bool SkMatrix::mapRect(SkRect* dst, const SkRect& src) const { 1154 SkASSERT(dst && &src); 1155 1156 if (this->rectStaysRect()) { 1157 this->mapPoints((SkPoint*)dst, (const SkPoint*)&src, 2); 1158 dst->sort(); 1159 return true; 1160 } else { 1161 SkPoint quad[4]; 1162 1163 src.toQuad(quad); 1164 this->mapPoints(quad, quad, 4); 1165 dst->set(quad, 4); 1166 return false; 1167 } 1168} 1169 1170SkScalar SkMatrix::mapRadius(SkScalar radius) const { 1171 SkVector vec[2]; 1172 1173 vec[0].set(radius, 0); 1174 vec[1].set(0, radius); 1175 this->mapVectors(vec, 2); 1176 1177 SkScalar d0 = vec[0].length(); 1178 SkScalar d1 = vec[1].length(); 1179 1180 return SkScalarMean(d0, d1); 1181} 1182 1183/////////////////////////////////////////////////////////////////////////////// 1184 1185void SkMatrix::Persp_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1186 SkPoint* pt) { 1187 SkASSERT(m.hasPerspective()); 1188 1189 SkScalar x = SkScalarMul(sx, m.fMat[kMScaleX]) + 1190 SkScalarMul(sy, m.fMat[kMSkewX]) + m.fMat[kMTransX]; 1191 SkScalar y = SkScalarMul(sx, m.fMat[kMSkewY]) + 1192 SkScalarMul(sy, m.fMat[kMScaleY]) + m.fMat[kMTransY]; 1193#ifdef SK_SCALAR_IS_FIXED 1194 SkFixed z = SkFractMul(sx, m.fMat[kMPersp0]) + 1195 SkFractMul(sy, m.fMat[kMPersp1]) + 1196 SkFractToFixed(m.fMat[kMPersp2]); 1197#else 1198 float z = SkScalarMul(sx, m.fMat[kMPersp0]) + 1199 SkScalarMul(sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2]; 1200#endif 1201 if (z) { 1202 z = SkScalarFastInvert(z); 1203 } 1204 pt->fX = SkScalarMul(x, z); 1205 pt->fY = SkScalarMul(y, z); 1206} 1207 1208#ifdef SK_SCALAR_IS_FIXED 1209static SkFixed fixmuladdmul(SkFixed a, SkFixed b, SkFixed c, SkFixed d) { 1210 Sk64 tmp, tmp1; 1211 1212 tmp.setMul(a, b); 1213 tmp1.setMul(c, d); 1214 return tmp.addGetFixed(tmp1); 1215// tmp.add(tmp1); 1216// return tmp.getFixed(); 1217} 1218#endif 1219 1220void SkMatrix::RotTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1221 SkPoint* pt) { 1222 SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask)) == kAffine_Mask); 1223 1224#ifdef SK_SCALAR_IS_FIXED 1225 pt->fX = fixmuladdmul(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + 1226 m.fMat[kMTransX]; 1227 pt->fY = fixmuladdmul(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + 1228 m.fMat[kMTransY]; 1229#else 1230 pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]) + 1231 SkScalarMulAdd(sy, m.fMat[kMSkewX], m.fMat[kMTransX]); 1232 pt->fY = SkScalarMul(sx, m.fMat[kMSkewY]) + 1233 SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]); 1234#endif 1235} 1236 1237void SkMatrix::Rot_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1238 SkPoint* pt) { 1239 SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask))== kAffine_Mask); 1240 SkASSERT(0 == m.fMat[kMTransX]); 1241 SkASSERT(0 == m.fMat[kMTransY]); 1242 1243#ifdef SK_SCALAR_IS_FIXED 1244 pt->fX = fixmuladdmul(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]); 1245 pt->fY = fixmuladdmul(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]); 1246#else 1247 pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]) + 1248 SkScalarMulAdd(sy, m.fMat[kMSkewX], m.fMat[kMTransX]); 1249 pt->fY = SkScalarMul(sx, m.fMat[kMSkewY]) + 1250 SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]); 1251#endif 1252} 1253 1254void SkMatrix::ScaleTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1255 SkPoint* pt) { 1256 SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask)) 1257 == kScale_Mask); 1258 1259 pt->fX = SkScalarMulAdd(sx, m.fMat[kMScaleX], m.fMat[kMTransX]); 1260 pt->fY = SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]); 1261} 1262 1263void SkMatrix::Scale_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1264 SkPoint* pt) { 1265 SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask)) 1266 == kScale_Mask); 1267 SkASSERT(0 == m.fMat[kMTransX]); 1268 SkASSERT(0 == m.fMat[kMTransY]); 1269 1270 pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]); 1271 pt->fY = SkScalarMul(sy, m.fMat[kMScaleY]); 1272} 1273 1274void SkMatrix::Trans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1275 SkPoint* pt) { 1276 SkASSERT(m.getType() == kTranslate_Mask); 1277 1278 pt->fX = sx + m.fMat[kMTransX]; 1279 pt->fY = sy + m.fMat[kMTransY]; 1280} 1281 1282void SkMatrix::Identity_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1283 SkPoint* pt) { 1284 SkASSERT(0 == m.getType()); 1285 1286 pt->fX = sx; 1287 pt->fY = sy; 1288} 1289 1290const SkMatrix::MapXYProc SkMatrix::gMapXYProcs[] = { 1291 SkMatrix::Identity_xy, SkMatrix::Trans_xy, 1292 SkMatrix::Scale_xy, SkMatrix::ScaleTrans_xy, 1293 SkMatrix::Rot_xy, SkMatrix::RotTrans_xy, 1294 SkMatrix::Rot_xy, SkMatrix::RotTrans_xy, 1295 // repeat the persp proc 8 times 1296 SkMatrix::Persp_xy, SkMatrix::Persp_xy, 1297 SkMatrix::Persp_xy, SkMatrix::Persp_xy, 1298 SkMatrix::Persp_xy, SkMatrix::Persp_xy, 1299 SkMatrix::Persp_xy, SkMatrix::Persp_xy 1300}; 1301 1302/////////////////////////////////////////////////////////////////////////////// 1303 1304// if its nearly zero (just made up 26, perhaps it should be bigger or smaller) 1305#ifdef SK_SCALAR_IS_FIXED 1306 typedef SkFract SkPerspElemType; 1307 #define PerspNearlyZero(x) (SkAbs32(x) < (SK_Fract1 >> 26)) 1308#else 1309 typedef float SkPerspElemType; 1310 #define PerspNearlyZero(x) SkScalarNearlyZero(x, (1.0f / (1 << 26))) 1311#endif 1312 1313bool SkMatrix::fixedStepInX(SkScalar y, SkFixed* stepX, SkFixed* stepY) const { 1314 if (PerspNearlyZero(fMat[kMPersp0])) { 1315 if (stepX || stepY) { 1316 if (PerspNearlyZero(fMat[kMPersp1]) && 1317 PerspNearlyZero(fMat[kMPersp2] - kMatrix22Elem)) { 1318 if (stepX) { 1319 *stepX = SkScalarToFixed(fMat[kMScaleX]); 1320 } 1321 if (stepY) { 1322 *stepY = SkScalarToFixed(fMat[kMSkewY]); 1323 } 1324 } else { 1325#ifdef SK_SCALAR_IS_FIXED 1326 SkFixed z = SkFractMul(y, fMat[kMPersp1]) + 1327 SkFractToFixed(fMat[kMPersp2]); 1328#else 1329 float z = y * fMat[kMPersp1] + fMat[kMPersp2]; 1330#endif 1331 if (stepX) { 1332 *stepX = SkScalarToFixed(SkScalarDiv(fMat[kMScaleX], z)); 1333 } 1334 if (stepY) { 1335 *stepY = SkScalarToFixed(SkScalarDiv(fMat[kMSkewY], z)); 1336 } 1337 } 1338 } 1339 return true; 1340 } 1341 return false; 1342} 1343 1344/////////////////////////////////////////////////////////////////////////////// 1345 1346#include "SkPerspIter.h" 1347 1348SkPerspIter::SkPerspIter(const SkMatrix& m, SkScalar x0, SkScalar y0, int count) 1349 : fMatrix(m), fSX(x0), fSY(y0), fCount(count) { 1350 SkPoint pt; 1351 1352 SkMatrix::Persp_xy(m, x0, y0, &pt); 1353 fX = SkScalarToFixed(pt.fX); 1354 fY = SkScalarToFixed(pt.fY); 1355} 1356 1357int SkPerspIter::next() { 1358 int n = fCount; 1359 1360 if (0 == n) { 1361 return 0; 1362 } 1363 SkPoint pt; 1364 SkFixed x = fX; 1365 SkFixed y = fY; 1366 SkFixed dx, dy; 1367 1368 if (n >= kCount) { 1369 n = kCount; 1370 fSX += SkIntToScalar(kCount); 1371 SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt); 1372 fX = SkScalarToFixed(pt.fX); 1373 fY = SkScalarToFixed(pt.fY); 1374 dx = (fX - x) >> kShift; 1375 dy = (fY - y) >> kShift; 1376 } else { 1377 fSX += SkIntToScalar(n); 1378 SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt); 1379 fX = SkScalarToFixed(pt.fX); 1380 fY = SkScalarToFixed(pt.fY); 1381 dx = (fX - x) / n; 1382 dy = (fY - y) / n; 1383 } 1384 1385 SkFixed* p = fStorage; 1386 for (int i = 0; i < n; i++) { 1387 *p++ = x; x += dx; 1388 *p++ = y; y += dy; 1389 } 1390 1391 fCount -= n; 1392 return n; 1393} 1394 1395/////////////////////////////////////////////////////////////////////////////// 1396 1397#ifdef SK_SCALAR_IS_FIXED 1398 1399static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) { 1400 SkFixed x = SK_Fixed1, y = SK_Fixed1; 1401 SkPoint pt1, pt2; 1402 Sk64 w1, w2; 1403 1404 if (count > 1) { 1405 pt1.fX = poly[1].fX - poly[0].fX; 1406 pt1.fY = poly[1].fY - poly[0].fY; 1407 y = SkPoint::Length(pt1.fX, pt1.fY); 1408 if (y == 0) { 1409 return false; 1410 } 1411 switch (count) { 1412 case 2: 1413 break; 1414 case 3: 1415 pt2.fX = poly[0].fY - poly[2].fY; 1416 pt2.fY = poly[2].fX - poly[0].fX; 1417 goto CALC_X; 1418 default: 1419 pt2.fX = poly[0].fY - poly[3].fY; 1420 pt2.fY = poly[3].fX - poly[0].fX; 1421 CALC_X: 1422 w1.setMul(pt1.fX, pt2.fX); 1423 w2.setMul(pt1.fY, pt2.fY); 1424 w1.add(w2); 1425 w1.div(y, Sk64::kRound_DivOption); 1426 if (!w1.is32()) { 1427 return false; 1428 } 1429 x = w1.get32(); 1430 break; 1431 } 1432 } 1433 pt->set(x, y); 1434 return true; 1435} 1436 1437bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst, 1438 const SkPoint& scalePt) { 1439 // need to check if SkFixedDiv overflows... 1440 1441 const SkFixed scale = scalePt.fY; 1442 dst->fMat[kMScaleX] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale); 1443 dst->fMat[kMSkewY] = SkFixedDiv(srcPt[0].fX - srcPt[1].fX, scale); 1444 dst->fMat[kMPersp0] = 0; 1445 dst->fMat[kMSkewX] = SkFixedDiv(srcPt[1].fX - srcPt[0].fX, scale); 1446 dst->fMat[kMScaleY] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale); 1447 dst->fMat[kMPersp1] = 0; 1448 dst->fMat[kMTransX] = srcPt[0].fX; 1449 dst->fMat[kMTransY] = srcPt[0].fY; 1450 dst->fMat[kMPersp2] = SK_Fract1; 1451 dst->setTypeMask(kUnknown_Mask); 1452 return true; 1453} 1454 1455bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst, 1456 const SkPoint& scale) { 1457 // really, need to check if SkFixedDiv overflow'd 1458 1459 dst->fMat[kMScaleX] = SkFixedDiv(srcPt[2].fX - srcPt[0].fX, scale.fX); 1460 dst->fMat[kMSkewY] = SkFixedDiv(srcPt[2].fY - srcPt[0].fY, scale.fX); 1461 dst->fMat[kMPersp0] = 0; 1462 dst->fMat[kMSkewX] = SkFixedDiv(srcPt[1].fX - srcPt[0].fX, scale.fY); 1463 dst->fMat[kMScaleY] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale.fY); 1464 dst->fMat[kMPersp1] = 0; 1465 dst->fMat[kMTransX] = srcPt[0].fX; 1466 dst->fMat[kMTransY] = srcPt[0].fY; 1467 dst->fMat[kMPersp2] = SK_Fract1; 1468 dst->setTypeMask(kUnknown_Mask); 1469 return true; 1470} 1471 1472bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst, 1473 const SkPoint& scale) { 1474 SkFract a1, a2; 1475 SkFixed x0, y0, x1, y1, x2, y2; 1476 1477 x0 = srcPt[2].fX - srcPt[0].fX; 1478 y0 = srcPt[2].fY - srcPt[0].fY; 1479 x1 = srcPt[2].fX - srcPt[1].fX; 1480 y1 = srcPt[2].fY - srcPt[1].fY; 1481 x2 = srcPt[2].fX - srcPt[3].fX; 1482 y2 = srcPt[2].fY - srcPt[3].fY; 1483 1484 /* check if abs(x2) > abs(y2) */ 1485 if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) { 1486 SkFixed denom = SkMulDiv(x1, y2, x2) - y1; 1487 if (0 == denom) { 1488 return false; 1489 } 1490 a1 = SkFractDiv(SkMulDiv(x0 - x1, y2, x2) - y0 + y1, denom); 1491 } else { 1492 SkFixed denom = x1 - SkMulDiv(y1, x2, y2); 1493 if (0 == denom) { 1494 return false; 1495 } 1496 a1 = SkFractDiv(x0 - x1 - SkMulDiv(y0 - y1, x2, y2), denom); 1497 } 1498 1499 /* check if abs(x1) > abs(y1) */ 1500 if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) { 1501 SkFixed denom = y2 - SkMulDiv(x2, y1, x1); 1502 if (0 == denom) { 1503 return false; 1504 } 1505 a2 = SkFractDiv(y0 - y2 - SkMulDiv(x0 - x2, y1, x1), denom); 1506 } else { 1507 SkFixed denom = SkMulDiv(y2, x1, y1) - x2; 1508 if (0 == denom) { 1509 return false; 1510 } 1511 a2 = SkFractDiv(SkMulDiv(y0 - y2, x1, y1) - x0 + x2, denom); 1512 } 1513 1514 // need to check if SkFixedDiv overflows... 1515 dst->fMat[kMScaleX] = SkFixedDiv(SkFractMul(a2, srcPt[3].fX) + 1516 srcPt[3].fX - srcPt[0].fX, scale.fX); 1517 dst->fMat[kMSkewY] = SkFixedDiv(SkFractMul(a2, srcPt[3].fY) + 1518 srcPt[3].fY - srcPt[0].fY, scale.fX); 1519 dst->fMat[kMPersp0] = SkFixedDiv(a2, scale.fX); 1520 dst->fMat[kMSkewX] = SkFixedDiv(SkFractMul(a1, srcPt[1].fX) + 1521 srcPt[1].fX - srcPt[0].fX, scale.fY); 1522 dst->fMat[kMScaleY] = SkFixedDiv(SkFractMul(a1, srcPt[1].fY) + 1523 srcPt[1].fY - srcPt[0].fY, scale.fY); 1524 dst->fMat[kMPersp1] = SkFixedDiv(a1, scale.fY); 1525 dst->fMat[kMTransX] = srcPt[0].fX; 1526 dst->fMat[kMTransY] = srcPt[0].fY; 1527 dst->fMat[kMPersp2] = SK_Fract1; 1528 dst->setTypeMask(kUnknown_Mask); 1529 return true; 1530} 1531 1532#else /* Scalar is float */ 1533 1534static inline bool checkForZero(float x) { 1535 return x*x == 0; 1536} 1537 1538static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) { 1539 float x = 1, y = 1; 1540 SkPoint pt1, pt2; 1541 1542 if (count > 1) { 1543 pt1.fX = poly[1].fX - poly[0].fX; 1544 pt1.fY = poly[1].fY - poly[0].fY; 1545 y = SkPoint::Length(pt1.fX, pt1.fY); 1546 if (checkForZero(y)) { 1547 return false; 1548 } 1549 switch (count) { 1550 case 2: 1551 break; 1552 case 3: 1553 pt2.fX = poly[0].fY - poly[2].fY; 1554 pt2.fY = poly[2].fX - poly[0].fX; 1555 goto CALC_X; 1556 default: 1557 pt2.fX = poly[0].fY - poly[3].fY; 1558 pt2.fY = poly[3].fX - poly[0].fX; 1559 CALC_X: 1560 x = SkScalarDiv(SkScalarMul(pt1.fX, pt2.fX) + 1561 SkScalarMul(pt1.fY, pt2.fY), y); 1562 break; 1563 } 1564 } 1565 pt->set(x, y); 1566 return true; 1567} 1568 1569bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst, 1570 const SkPoint& scale) { 1571 float invScale = 1 / scale.fY; 1572 1573 dst->fMat[kMScaleX] = (srcPt[1].fY - srcPt[0].fY) * invScale; 1574 dst->fMat[kMSkewY] = (srcPt[0].fX - srcPt[1].fX) * invScale; 1575 dst->fMat[kMPersp0] = 0; 1576 dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale; 1577 dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale; 1578 dst->fMat[kMPersp1] = 0; 1579 dst->fMat[kMTransX] = srcPt[0].fX; 1580 dst->fMat[kMTransY] = srcPt[0].fY; 1581 dst->fMat[kMPersp2] = 1; 1582 dst->setTypeMask(kUnknown_Mask); 1583 return true; 1584} 1585 1586bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst, 1587 const SkPoint& scale) { 1588 float invScale = 1 / scale.fX; 1589 dst->fMat[kMScaleX] = (srcPt[2].fX - srcPt[0].fX) * invScale; 1590 dst->fMat[kMSkewY] = (srcPt[2].fY - srcPt[0].fY) * invScale; 1591 dst->fMat[kMPersp0] = 0; 1592 1593 invScale = 1 / scale.fY; 1594 dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale; 1595 dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale; 1596 dst->fMat[kMPersp1] = 0; 1597 1598 dst->fMat[kMTransX] = srcPt[0].fX; 1599 dst->fMat[kMTransY] = srcPt[0].fY; 1600 dst->fMat[kMPersp2] = 1; 1601 dst->setTypeMask(kUnknown_Mask); 1602 return true; 1603} 1604 1605bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst, 1606 const SkPoint& scale) { 1607 float a1, a2; 1608 float x0, y0, x1, y1, x2, y2; 1609 1610 x0 = srcPt[2].fX - srcPt[0].fX; 1611 y0 = srcPt[2].fY - srcPt[0].fY; 1612 x1 = srcPt[2].fX - srcPt[1].fX; 1613 y1 = srcPt[2].fY - srcPt[1].fY; 1614 x2 = srcPt[2].fX - srcPt[3].fX; 1615 y2 = srcPt[2].fY - srcPt[3].fY; 1616 1617 /* check if abs(x2) > abs(y2) */ 1618 if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) { 1619 float denom = SkScalarMulDiv(x1, y2, x2) - y1; 1620 if (checkForZero(denom)) { 1621 return false; 1622 } 1623 a1 = SkScalarDiv(SkScalarMulDiv(x0 - x1, y2, x2) - y0 + y1, denom); 1624 } else { 1625 float denom = x1 - SkScalarMulDiv(y1, x2, y2); 1626 if (checkForZero(denom)) { 1627 return false; 1628 } 1629 a1 = SkScalarDiv(x0 - x1 - SkScalarMulDiv(y0 - y1, x2, y2), denom); 1630 } 1631 1632 /* check if abs(x1) > abs(y1) */ 1633 if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) { 1634 float denom = y2 - SkScalarMulDiv(x2, y1, x1); 1635 if (checkForZero(denom)) { 1636 return false; 1637 } 1638 a2 = SkScalarDiv(y0 - y2 - SkScalarMulDiv(x0 - x2, y1, x1), denom); 1639 } else { 1640 float denom = SkScalarMulDiv(y2, x1, y1) - x2; 1641 if (checkForZero(denom)) { 1642 return false; 1643 } 1644 a2 = SkScalarDiv(SkScalarMulDiv(y0 - y2, x1, y1) - x0 + x2, denom); 1645 } 1646 1647 float invScale = 1 / scale.fX; 1648 dst->fMat[kMScaleX] = SkScalarMul(SkScalarMul(a2, srcPt[3].fX) + 1649 srcPt[3].fX - srcPt[0].fX, invScale); 1650 dst->fMat[kMSkewY] = SkScalarMul(SkScalarMul(a2, srcPt[3].fY) + 1651 srcPt[3].fY - srcPt[0].fY, invScale); 1652 dst->fMat[kMPersp0] = SkScalarMul(a2, invScale); 1653 invScale = 1 / scale.fY; 1654 dst->fMat[kMSkewX] = SkScalarMul(SkScalarMul(a1, srcPt[1].fX) + 1655 srcPt[1].fX - srcPt[0].fX, invScale); 1656 dst->fMat[kMScaleY] = SkScalarMul(SkScalarMul(a1, srcPt[1].fY) + 1657 srcPt[1].fY - srcPt[0].fY, invScale); 1658 dst->fMat[kMPersp1] = SkScalarMul(a1, invScale); 1659 dst->fMat[kMTransX] = srcPt[0].fX; 1660 dst->fMat[kMTransY] = srcPt[0].fY; 1661 dst->fMat[kMPersp2] = 1; 1662 dst->setTypeMask(kUnknown_Mask); 1663 return true; 1664} 1665 1666#endif 1667 1668typedef bool (*PolyMapProc)(const SkPoint[], SkMatrix*, const SkPoint&); 1669 1670/* Taken from Rob Johnson's original sample code in QuickDraw GX 1671*/ 1672bool SkMatrix::setPolyToPoly(const SkPoint src[], const SkPoint dst[], 1673 int count) { 1674 if ((unsigned)count > 4) { 1675 SkDebugf("--- SkMatrix::setPolyToPoly count out of range %d\n", count); 1676 return false; 1677 } 1678 1679 if (0 == count) { 1680 this->reset(); 1681 return true; 1682 } 1683 if (1 == count) { 1684 this->setTranslate(dst[0].fX - src[0].fX, dst[0].fY - src[0].fY); 1685 return true; 1686 } 1687 1688 SkPoint scale; 1689 if (!poly_to_point(&scale, src, count) || 1690 SkScalarNearlyZero(scale.fX) || 1691 SkScalarNearlyZero(scale.fY)) { 1692 return false; 1693 } 1694 1695 static const PolyMapProc gPolyMapProcs[] = { 1696 SkMatrix::Poly2Proc, SkMatrix::Poly3Proc, SkMatrix::Poly4Proc 1697 }; 1698 PolyMapProc proc = gPolyMapProcs[count - 2]; 1699 1700 SkMatrix tempMap, result; 1701 tempMap.setTypeMask(kUnknown_Mask); 1702 1703 if (!proc(src, &tempMap, scale)) { 1704 return false; 1705 } 1706 if (!tempMap.invert(&result)) { 1707 return false; 1708 } 1709 if (!proc(dst, &tempMap, scale)) { 1710 return false; 1711 } 1712 if (!result.setConcat(tempMap, result)) { 1713 return false; 1714 } 1715 *this = result; 1716 return true; 1717} 1718 1719/////////////////////////////////////////////////////////////////////////////// 1720 1721enum MinOrMax { 1722 kMin_MinOrMax, 1723 kMax_MinOrMax 1724}; 1725 1726template <MinOrMax MIN_OR_MAX> SkScalar get_stretch_factor(SkMatrix::TypeMask typeMask, 1727 const SkScalar m[9]) { 1728 if (typeMask & SkMatrix::kPerspective_Mask) { 1729 return -SK_Scalar1; 1730 } 1731 if (SkMatrix::kIdentity_Mask == typeMask) { 1732 return SK_Scalar1; 1733 } 1734 if (!(typeMask & SkMatrix::kAffine_Mask)) { 1735 if (kMin_MinOrMax == MIN_OR_MAX) { 1736 return SkMinScalar(SkScalarAbs(m[SkMatrix::kMScaleX]), 1737 SkScalarAbs(m[SkMatrix::kMScaleY])); 1738 } else { 1739 return SkMaxScalar(SkScalarAbs(m[SkMatrix::kMScaleX]), 1740 SkScalarAbs(m[SkMatrix::kMScaleY])); 1741 } 1742 } 1743 // ignore the translation part of the matrix, just look at 2x2 portion. 1744 // compute singular values, take largest or smallest abs value. 1745 // [a b; b c] = A^T*A 1746 SkScalar a = SkScalarMul(m[SkMatrix::kMScaleX], m[SkMatrix::kMScaleX]) + 1747 SkScalarMul(m[SkMatrix::kMSkewY], m[SkMatrix::kMSkewY]); 1748 SkScalar b = SkScalarMul(m[SkMatrix::kMScaleX], m[SkMatrix::kMSkewX]) + 1749 SkScalarMul(m[SkMatrix::kMScaleY], m[SkMatrix::kMSkewY]); 1750 SkScalar c = SkScalarMul(m[SkMatrix::kMSkewX], m[SkMatrix::kMSkewX]) + 1751 SkScalarMul(m[SkMatrix::kMScaleY], m[SkMatrix::kMScaleY]); 1752 // eigenvalues of A^T*A are the squared singular values of A. 1753 // characteristic equation is det((A^T*A) - l*I) = 0 1754 // l^2 - (a + c)l + (ac-b^2) 1755 // solve using quadratic equation (divisor is non-zero since l^2 has 1 coeff 1756 // and roots are guaranteed to be pos and real). 1757 SkScalar chosenRoot; 1758 SkScalar bSqd = SkScalarMul(b,b); 1759 // if upper left 2x2 is orthogonal save some math 1760 if (bSqd <= SK_ScalarNearlyZero*SK_ScalarNearlyZero) { 1761 if (kMin_MinOrMax == MIN_OR_MAX) { 1762 chosenRoot = SkMinScalar(a, c); 1763 } else { 1764 chosenRoot = SkMaxScalar(a, c); 1765 } 1766 } else { 1767 SkScalar aminusc = a - c; 1768 SkScalar apluscdiv2 = SkScalarHalf(a + c); 1769 SkScalar x = SkScalarHalf(SkScalarSqrt(SkScalarMul(aminusc, aminusc) + 4 * bSqd)); 1770 if (kMin_MinOrMax == MIN_OR_MAX) { 1771 chosenRoot = apluscdiv2 - x; 1772 } else { 1773 chosenRoot = apluscdiv2 + x; 1774 } 1775 } 1776 SkASSERT(chosenRoot >= 0); 1777 return SkScalarSqrt(chosenRoot); 1778} 1779 1780SkScalar SkMatrix::getMinStretch() const { 1781 return get_stretch_factor<kMin_MinOrMax>(this->getType(), fMat); 1782} 1783 1784SkScalar SkMatrix::getMaxStretch() const { 1785 return get_stretch_factor<kMax_MinOrMax>(this->getType(), fMat); 1786} 1787 1788static void reset_identity_matrix(SkMatrix* identity) { 1789 identity->reset(); 1790} 1791 1792const SkMatrix& SkMatrix::I() { 1793 // If you can use C++11 now, you might consider replacing this with a constexpr constructor. 1794 static SkMatrix gIdentity; 1795 SK_DECLARE_STATIC_ONCE(once); 1796 SkOnce(&once, reset_identity_matrix, &gIdentity); 1797 return gIdentity; 1798} 1799 1800const SkMatrix& SkMatrix::InvalidMatrix() { 1801 static SkMatrix gInvalid; 1802 static bool gOnce; 1803 if (!gOnce) { 1804 gInvalid.setAll(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, 1805 SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, 1806 SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1807 gInvalid.getType(); // force the type to be computed 1808 gOnce = true; 1809 } 1810 return gInvalid; 1811} 1812 1813/////////////////////////////////////////////////////////////////////////////// 1814 1815size_t SkMatrix::writeToMemory(void* buffer) const { 1816 // TODO write less for simple matrices 1817 static const size_t sizeInMemory = 9 * sizeof(SkScalar); 1818 if (buffer) { 1819 memcpy(buffer, fMat, sizeInMemory); 1820 } 1821 return sizeInMemory; 1822} 1823 1824size_t SkMatrix::readFromMemory(const void* buffer, size_t length) { 1825 static const size_t sizeInMemory = 9 * sizeof(SkScalar); 1826 if (length < sizeInMemory) { 1827 return 0; 1828 } 1829 if (buffer) { 1830 memcpy(fMat, buffer, sizeInMemory); 1831 this->setTypeMask(kUnknown_Mask); 1832 } 1833 return sizeInMemory; 1834} 1835 1836#ifdef SK_DEVELOPER 1837void SkMatrix::dump() const { 1838 SkString str; 1839 this->toString(&str); 1840 SkDebugf("%s\n", str.c_str()); 1841} 1842 1843void SkMatrix::toString(SkString* str) const { 1844 str->appendf("[%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f]", 1845 fMat[0], fMat[1], fMat[2], fMat[3], fMat[4], fMat[5], 1846 fMat[6], fMat[7], fMat[8]); 1847} 1848#endif 1849 1850/////////////////////////////////////////////////////////////////////////////// 1851 1852#include "SkMatrixUtils.h" 1853 1854bool SkTreatAsSprite(const SkMatrix& mat, int width, int height, 1855 unsigned subpixelBits) { 1856 // quick reject on affine or perspective 1857 if (mat.getType() & ~(SkMatrix::kScale_Mask | SkMatrix::kTranslate_Mask)) { 1858 return false; 1859 } 1860 1861 // quick success check 1862 if (!subpixelBits && !(mat.getType() & ~SkMatrix::kTranslate_Mask)) { 1863 return true; 1864 } 1865 1866 // mapRect supports negative scales, so we eliminate those first 1867 if (mat.getScaleX() < 0 || mat.getScaleY() < 0) { 1868 return false; 1869 } 1870 1871 SkRect dst; 1872 SkIRect isrc = { 0, 0, width, height }; 1873 1874 { 1875 SkRect src; 1876 src.set(isrc); 1877 mat.mapRect(&dst, src); 1878 } 1879 1880 // just apply the translate to isrc 1881 isrc.offset(SkScalarRoundToInt(mat.getTranslateX()), 1882 SkScalarRoundToInt(mat.getTranslateY())); 1883 1884 if (subpixelBits) { 1885 isrc.fLeft <<= subpixelBits; 1886 isrc.fTop <<= subpixelBits; 1887 isrc.fRight <<= subpixelBits; 1888 isrc.fBottom <<= subpixelBits; 1889 1890 const float scale = 1 << subpixelBits; 1891 dst.fLeft *= scale; 1892 dst.fTop *= scale; 1893 dst.fRight *= scale; 1894 dst.fBottom *= scale; 1895 } 1896 1897 SkIRect idst; 1898 dst.round(&idst); 1899 return isrc == idst; 1900} 1901 1902// A square matrix M can be decomposed (via polar decomposition) into two matrices -- 1903// an orthogonal matrix Q and a symmetric matrix S. In turn we can decompose S into U*W*U^T, 1904// where U is another orthogonal matrix and W is a scale matrix. These can be recombined 1905// to give M = (Q*U)*W*U^T, i.e., the product of two orthogonal matrices and a scale matrix. 1906// 1907// The one wrinkle is that traditionally Q may contain a reflection -- the 1908// calculation has been rejiggered to put that reflection into W. 1909bool SkDecomposeUpper2x2(const SkMatrix& matrix, 1910 SkPoint* rotation1, 1911 SkPoint* scale, 1912 SkPoint* rotation2) { 1913 1914 SkScalar A = matrix[SkMatrix::kMScaleX]; 1915 SkScalar B = matrix[SkMatrix::kMSkewX]; 1916 SkScalar C = matrix[SkMatrix::kMSkewY]; 1917 SkScalar D = matrix[SkMatrix::kMScaleY]; 1918 1919 if (is_degenerate_2x2(A, B, C, D)) { 1920 return false; 1921 } 1922 1923 double w1, w2; 1924 SkScalar cos1, sin1; 1925 SkScalar cos2, sin2; 1926 1927 // do polar decomposition (M = Q*S) 1928 SkScalar cosQ, sinQ; 1929 double Sa, Sb, Sd; 1930 // if M is already symmetric (i.e., M = I*S) 1931 if (SkScalarNearlyEqual(B, C)) { 1932 cosQ = SK_Scalar1; 1933 sinQ = 0; 1934 1935 Sa = A; 1936 Sb = B; 1937 Sd = D; 1938 } else { 1939 cosQ = A + D; 1940 sinQ = C - B; 1941 SkScalar reciplen = SK_Scalar1/SkScalarSqrt(cosQ*cosQ + sinQ*sinQ); 1942 cosQ *= reciplen; 1943 sinQ *= reciplen; 1944 1945 // S = Q^-1*M 1946 // we don't calc Sc since it's symmetric 1947 Sa = A*cosQ + C*sinQ; 1948 Sb = B*cosQ + D*sinQ; 1949 Sd = -B*sinQ + D*cosQ; 1950 } 1951 1952 // Now we need to compute eigenvalues of S (our scale factors) 1953 // and eigenvectors (bases for our rotation) 1954 // From this, should be able to reconstruct S as U*W*U^T 1955 if (SkScalarNearlyZero(SkDoubleToScalar(Sb))) { 1956 // already diagonalized 1957 cos1 = SK_Scalar1; 1958 sin1 = 0; 1959 w1 = Sa; 1960 w2 = Sd; 1961 cos2 = cosQ; 1962 sin2 = sinQ; 1963 } else { 1964 double diff = Sa - Sd; 1965 double discriminant = sqrt(diff*diff + 4.0*Sb*Sb); 1966 double trace = Sa + Sd; 1967 if (diff > 0) { 1968 w1 = 0.5*(trace + discriminant); 1969 w2 = 0.5*(trace - discriminant); 1970 } else { 1971 w1 = 0.5*(trace - discriminant); 1972 w2 = 0.5*(trace + discriminant); 1973 } 1974 1975 cos1 = SkDoubleToScalar(Sb); sin1 = SkDoubleToScalar(w1 - Sa); 1976 SkScalar reciplen = SK_Scalar1/SkScalarSqrt(cos1*cos1 + sin1*sin1); 1977 cos1 *= reciplen; 1978 sin1 *= reciplen; 1979 1980 // rotation 2 is composition of Q and U 1981 cos2 = cos1*cosQ - sin1*sinQ; 1982 sin2 = sin1*cosQ + cos1*sinQ; 1983 1984 // rotation 1 is U^T 1985 sin1 = -sin1; 1986 } 1987 1988 if (NULL != scale) { 1989 scale->fX = SkDoubleToScalar(w1); 1990 scale->fY = SkDoubleToScalar(w2); 1991 } 1992 if (NULL != rotation1) { 1993 rotation1->fX = cos1; 1994 rotation1->fY = sin1; 1995 } 1996 if (NULL != rotation2) { 1997 rotation2->fX = cos2; 1998 rotation2->fY = sin2; 1999 } 2000 2001 return true; 2002} 2003