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