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