SkMatrix.cpp revision 12a23866fe18e800da1d361d000a359ea36696eb
1/* 2 * Copyright 2006 The Android Open Source Project 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#include "SkMatrix.h" 9#include "Sk64.h" 10#include "SkFloatBits.h" 11#include "SkOnce.h" 12#include "SkScalarCompare.h" 13#include "SkString.h" 14 15#ifdef SK_SCALAR_IS_FLOAT 16 #define kMatrix22Elem SK_Scalar1 17 18 static inline float SkDoubleToFloat(double x) { 19 return static_cast<float>(x); 20 } 21#else 22 #define kMatrix22Elem SK_Fract1 23#endif 24 25/* [scale-x skew-x trans-x] [X] [X'] 26 [skew-y scale-y trans-y] * [Y] = [Y'] 27 [persp-0 persp-1 persp-2] [1] [1 ] 28*/ 29 30void SkMatrix::reset() { 31 fMat[kMScaleX] = fMat[kMScaleY] = SK_Scalar1; 32 fMat[kMSkewX] = fMat[kMSkewY] = 33 fMat[kMTransX] = fMat[kMTransY] = 34 fMat[kMPersp0] = fMat[kMPersp1] = 0; 35 fMat[kMPersp2] = kMatrix22Elem; 36 37 this->setTypeMask(kIdentity_Mask | kRectStaysRect_Mask); 38} 39 40// this guy aligns with the masks, so we can compute a mask from a varaible 0/1 41enum { 42 kTranslate_Shift, 43 kScale_Shift, 44 kAffine_Shift, 45 kPerspective_Shift, 46 kRectStaysRect_Shift 47}; 48 49#ifdef SK_SCALAR_IS_FLOAT 50 static const int32_t kScalar1Int = 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) || 0 == count); 1222 // no partial overlap 1223 SkASSERT(src == dst || &dst[count] <= &src[0] || &src[count] <= &dst[0]); 1224 1225 this->getMapPtsProc()(*this, dst, src, count); 1226} 1227 1228/////////////////////////////////////////////////////////////////////////////// 1229 1230void SkMatrix::mapHomogeneousPoints(SkScalar dst[], const SkScalar src[], int count) const { 1231 SkASSERT((dst && src && count > 0) || 0 == count); 1232 // no partial overlap 1233 SkASSERT(src == dst || SkAbs32((int32_t)(src - dst)) >= 3*count); 1234 1235 if (count > 0) { 1236 if (this->isIdentity()) { 1237 memcpy(dst, src, 3*count*sizeof(SkScalar)); 1238 return; 1239 } 1240 do { 1241 SkScalar sx = src[0]; 1242 SkScalar sy = src[1]; 1243 SkScalar sw = src[2]; 1244 src += 3; 1245 1246 SkScalar x = SkScalarMul(sx, fMat[kMScaleX]) + 1247 SkScalarMul(sy, fMat[kMSkewX]) + 1248 SkScalarMul(sw, fMat[kMTransX]); 1249 SkScalar y = SkScalarMul(sx, fMat[kMSkewY]) + 1250 SkScalarMul(sy, fMat[kMScaleY]) + 1251 SkScalarMul(sw, fMat[kMTransY]); 1252 SkScalar w = SkScalarMul(sx, fMat[kMPersp0]) + 1253 SkScalarMul(sy, fMat[kMPersp1]) + 1254 SkScalarMul(sw, fMat[kMPersp2]); 1255 1256 dst[0] = x; 1257 dst[1] = y; 1258 dst[2] = w; 1259 dst += 3; 1260 } while (--count); 1261 } 1262} 1263 1264/////////////////////////////////////////////////////////////////////////////// 1265 1266void SkMatrix::mapVectors(SkPoint dst[], const SkPoint src[], int count) const { 1267 if (this->hasPerspective()) { 1268 SkPoint origin; 1269 1270 MapXYProc proc = this->getMapXYProc(); 1271 proc(*this, 0, 0, &origin); 1272 1273 for (int i = count - 1; i >= 0; --i) { 1274 SkPoint tmp; 1275 1276 proc(*this, src[i].fX, src[i].fY, &tmp); 1277 dst[i].set(tmp.fX - origin.fX, tmp.fY - origin.fY); 1278 } 1279 } else { 1280 SkMatrix tmp = *this; 1281 1282 tmp.fMat[kMTransX] = tmp.fMat[kMTransY] = 0; 1283 tmp.clearTypeMask(kTranslate_Mask); 1284 tmp.mapPoints(dst, src, count); 1285 } 1286} 1287 1288bool SkMatrix::mapRect(SkRect* dst, const SkRect& src) const { 1289 SkASSERT(dst && &src); 1290 1291 if (this->rectStaysRect()) { 1292 this->mapPoints((SkPoint*)dst, (const SkPoint*)&src, 2); 1293 dst->sort(); 1294 return true; 1295 } else { 1296 SkPoint quad[4]; 1297 1298 src.toQuad(quad); 1299 this->mapPoints(quad, quad, 4); 1300 dst->set(quad, 4); 1301 return false; 1302 } 1303} 1304 1305SkScalar SkMatrix::mapRadius(SkScalar radius) const { 1306 SkVector vec[2]; 1307 1308 vec[0].set(radius, 0); 1309 vec[1].set(0, radius); 1310 this->mapVectors(vec, 2); 1311 1312 SkScalar d0 = vec[0].length(); 1313 SkScalar d1 = vec[1].length(); 1314 1315 return SkScalarMean(d0, d1); 1316} 1317 1318/////////////////////////////////////////////////////////////////////////////// 1319 1320void SkMatrix::Persp_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1321 SkPoint* pt) { 1322 SkASSERT(m.hasPerspective()); 1323 1324 SkScalar x = SkScalarMul(sx, m.fMat[kMScaleX]) + 1325 SkScalarMul(sy, m.fMat[kMSkewX]) + m.fMat[kMTransX]; 1326 SkScalar y = SkScalarMul(sx, m.fMat[kMSkewY]) + 1327 SkScalarMul(sy, m.fMat[kMScaleY]) + m.fMat[kMTransY]; 1328#ifdef SK_SCALAR_IS_FIXED 1329 SkFixed z = SkFractMul(sx, m.fMat[kMPersp0]) + 1330 SkFractMul(sy, m.fMat[kMPersp1]) + 1331 SkFractToFixed(m.fMat[kMPersp2]); 1332#else 1333 float z = SkScalarMul(sx, m.fMat[kMPersp0]) + 1334 SkScalarMul(sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2]; 1335#endif 1336 if (z) { 1337 z = SkScalarFastInvert(z); 1338 } 1339 pt->fX = SkScalarMul(x, z); 1340 pt->fY = SkScalarMul(y, z); 1341} 1342 1343#ifdef SK_SCALAR_IS_FIXED 1344static SkFixed fixmuladdmul(SkFixed a, SkFixed b, SkFixed c, SkFixed d) { 1345 Sk64 tmp, tmp1; 1346 1347 tmp.setMul(a, b); 1348 tmp1.setMul(c, d); 1349 return tmp.addGetFixed(tmp1); 1350// tmp.add(tmp1); 1351// return tmp.getFixed(); 1352} 1353#endif 1354 1355void SkMatrix::RotTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1356 SkPoint* pt) { 1357 SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask)) == kAffine_Mask); 1358 1359#ifdef SK_SCALAR_IS_FIXED 1360 pt->fX = fixmuladdmul(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + 1361 m.fMat[kMTransX]; 1362 pt->fY = fixmuladdmul(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + 1363 m.fMat[kMTransY]; 1364#else 1365 pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]) + 1366 SkScalarMulAdd(sy, m.fMat[kMSkewX], m.fMat[kMTransX]); 1367 pt->fY = SkScalarMul(sx, m.fMat[kMSkewY]) + 1368 SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]); 1369#endif 1370} 1371 1372void SkMatrix::Rot_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1373 SkPoint* pt) { 1374 SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask))== kAffine_Mask); 1375 SkASSERT(0 == m.fMat[kMTransX]); 1376 SkASSERT(0 == m.fMat[kMTransY]); 1377 1378#ifdef SK_SCALAR_IS_FIXED 1379 pt->fX = fixmuladdmul(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]); 1380 pt->fY = fixmuladdmul(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]); 1381#else 1382 pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]) + 1383 SkScalarMulAdd(sy, m.fMat[kMSkewX], m.fMat[kMTransX]); 1384 pt->fY = SkScalarMul(sx, m.fMat[kMSkewY]) + 1385 SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]); 1386#endif 1387} 1388 1389void SkMatrix::ScaleTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1390 SkPoint* pt) { 1391 SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask)) 1392 == kScale_Mask); 1393 1394 pt->fX = SkScalarMulAdd(sx, m.fMat[kMScaleX], m.fMat[kMTransX]); 1395 pt->fY = SkScalarMulAdd(sy, m.fMat[kMScaleY], m.fMat[kMTransY]); 1396} 1397 1398void SkMatrix::Scale_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1399 SkPoint* pt) { 1400 SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask)) 1401 == kScale_Mask); 1402 SkASSERT(0 == m.fMat[kMTransX]); 1403 SkASSERT(0 == m.fMat[kMTransY]); 1404 1405 pt->fX = SkScalarMul(sx, m.fMat[kMScaleX]); 1406 pt->fY = SkScalarMul(sy, m.fMat[kMScaleY]); 1407} 1408 1409void SkMatrix::Trans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1410 SkPoint* pt) { 1411 SkASSERT(m.getType() == kTranslate_Mask); 1412 1413 pt->fX = sx + m.fMat[kMTransX]; 1414 pt->fY = sy + m.fMat[kMTransY]; 1415} 1416 1417void SkMatrix::Identity_xy(const SkMatrix& m, SkScalar sx, SkScalar sy, 1418 SkPoint* pt) { 1419 SkASSERT(0 == m.getType()); 1420 1421 pt->fX = sx; 1422 pt->fY = sy; 1423} 1424 1425const SkMatrix::MapXYProc SkMatrix::gMapXYProcs[] = { 1426 SkMatrix::Identity_xy, SkMatrix::Trans_xy, 1427 SkMatrix::Scale_xy, SkMatrix::ScaleTrans_xy, 1428 SkMatrix::Rot_xy, SkMatrix::RotTrans_xy, 1429 SkMatrix::Rot_xy, SkMatrix::RotTrans_xy, 1430 // repeat the persp proc 8 times 1431 SkMatrix::Persp_xy, SkMatrix::Persp_xy, 1432 SkMatrix::Persp_xy, SkMatrix::Persp_xy, 1433 SkMatrix::Persp_xy, SkMatrix::Persp_xy, 1434 SkMatrix::Persp_xy, SkMatrix::Persp_xy 1435}; 1436 1437/////////////////////////////////////////////////////////////////////////////// 1438 1439// if its nearly zero (just made up 26, perhaps it should be bigger or smaller) 1440#ifdef SK_SCALAR_IS_FIXED 1441 typedef SkFract SkPerspElemType; 1442 #define PerspNearlyZero(x) (SkAbs32(x) < (SK_Fract1 >> 26)) 1443#else 1444 typedef float SkPerspElemType; 1445 #define PerspNearlyZero(x) SkScalarNearlyZero(x, (1.0f / (1 << 26))) 1446#endif 1447 1448bool SkMatrix::fixedStepInX(SkScalar y, SkFixed* stepX, SkFixed* stepY) const { 1449 if (PerspNearlyZero(fMat[kMPersp0])) { 1450 if (stepX || stepY) { 1451 if (PerspNearlyZero(fMat[kMPersp1]) && 1452 PerspNearlyZero(fMat[kMPersp2] - kMatrix22Elem)) { 1453 if (stepX) { 1454 *stepX = SkScalarToFixed(fMat[kMScaleX]); 1455 } 1456 if (stepY) { 1457 *stepY = SkScalarToFixed(fMat[kMSkewY]); 1458 } 1459 } else { 1460#ifdef SK_SCALAR_IS_FIXED 1461 SkFixed z = SkFractMul(y, fMat[kMPersp1]) + 1462 SkFractToFixed(fMat[kMPersp2]); 1463#else 1464 float z = y * fMat[kMPersp1] + fMat[kMPersp2]; 1465#endif 1466 if (stepX) { 1467 *stepX = SkScalarToFixed(SkScalarDiv(fMat[kMScaleX], z)); 1468 } 1469 if (stepY) { 1470 *stepY = SkScalarToFixed(SkScalarDiv(fMat[kMSkewY], z)); 1471 } 1472 } 1473 } 1474 return true; 1475 } 1476 return false; 1477} 1478 1479/////////////////////////////////////////////////////////////////////////////// 1480 1481#include "SkPerspIter.h" 1482 1483SkPerspIter::SkPerspIter(const SkMatrix& m, SkScalar x0, SkScalar y0, int count) 1484 : fMatrix(m), fSX(x0), fSY(y0), fCount(count) { 1485 SkPoint pt; 1486 1487 SkMatrix::Persp_xy(m, x0, y0, &pt); 1488 fX = SkScalarToFixed(pt.fX); 1489 fY = SkScalarToFixed(pt.fY); 1490} 1491 1492int SkPerspIter::next() { 1493 int n = fCount; 1494 1495 if (0 == n) { 1496 return 0; 1497 } 1498 SkPoint pt; 1499 SkFixed x = fX; 1500 SkFixed y = fY; 1501 SkFixed dx, dy; 1502 1503 if (n >= kCount) { 1504 n = kCount; 1505 fSX += SkIntToScalar(kCount); 1506 SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt); 1507 fX = SkScalarToFixed(pt.fX); 1508 fY = SkScalarToFixed(pt.fY); 1509 dx = (fX - x) >> kShift; 1510 dy = (fY - y) >> kShift; 1511 } else { 1512 fSX += SkIntToScalar(n); 1513 SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt); 1514 fX = SkScalarToFixed(pt.fX); 1515 fY = SkScalarToFixed(pt.fY); 1516 dx = (fX - x) / n; 1517 dy = (fY - y) / n; 1518 } 1519 1520 SkFixed* p = fStorage; 1521 for (int i = 0; i < n; i++) { 1522 *p++ = x; x += dx; 1523 *p++ = y; y += dy; 1524 } 1525 1526 fCount -= n; 1527 return n; 1528} 1529 1530/////////////////////////////////////////////////////////////////////////////// 1531 1532#ifdef SK_SCALAR_IS_FIXED 1533 1534static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) { 1535 SkFixed x = SK_Fixed1, y = SK_Fixed1; 1536 SkPoint pt1, pt2; 1537 Sk64 w1, w2; 1538 1539 if (count > 1) { 1540 pt1.fX = poly[1].fX - poly[0].fX; 1541 pt1.fY = poly[1].fY - poly[0].fY; 1542 y = SkPoint::Length(pt1.fX, pt1.fY); 1543 if (y == 0) { 1544 return false; 1545 } 1546 switch (count) { 1547 case 2: 1548 break; 1549 case 3: 1550 pt2.fX = poly[0].fY - poly[2].fY; 1551 pt2.fY = poly[2].fX - poly[0].fX; 1552 goto CALC_X; 1553 default: 1554 pt2.fX = poly[0].fY - poly[3].fY; 1555 pt2.fY = poly[3].fX - poly[0].fX; 1556 CALC_X: 1557 w1.setMul(pt1.fX, pt2.fX); 1558 w2.setMul(pt1.fY, pt2.fY); 1559 w1.add(w2); 1560 w1.div(y, Sk64::kRound_DivOption); 1561 if (!w1.is32()) { 1562 return false; 1563 } 1564 x = w1.get32(); 1565 break; 1566 } 1567 } 1568 pt->set(x, y); 1569 return true; 1570} 1571 1572bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst, 1573 const SkPoint& scalePt) { 1574 // need to check if SkFixedDiv overflows... 1575 1576 const SkFixed scale = scalePt.fY; 1577 dst->fMat[kMScaleX] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale); 1578 dst->fMat[kMSkewY] = SkFixedDiv(srcPt[0].fX - srcPt[1].fX, scale); 1579 dst->fMat[kMPersp0] = 0; 1580 dst->fMat[kMSkewX] = SkFixedDiv(srcPt[1].fX - srcPt[0].fX, scale); 1581 dst->fMat[kMScaleY] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale); 1582 dst->fMat[kMPersp1] = 0; 1583 dst->fMat[kMTransX] = srcPt[0].fX; 1584 dst->fMat[kMTransY] = srcPt[0].fY; 1585 dst->fMat[kMPersp2] = SK_Fract1; 1586 dst->setTypeMask(kUnknown_Mask); 1587 return true; 1588} 1589 1590bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst, 1591 const SkPoint& scale) { 1592 // really, need to check if SkFixedDiv overflow'd 1593 1594 dst->fMat[kMScaleX] = SkFixedDiv(srcPt[2].fX - srcPt[0].fX, scale.fX); 1595 dst->fMat[kMSkewY] = SkFixedDiv(srcPt[2].fY - srcPt[0].fY, scale.fX); 1596 dst->fMat[kMPersp0] = 0; 1597 dst->fMat[kMSkewX] = SkFixedDiv(srcPt[1].fX - srcPt[0].fX, scale.fY); 1598 dst->fMat[kMScaleY] = SkFixedDiv(srcPt[1].fY - srcPt[0].fY, scale.fY); 1599 dst->fMat[kMPersp1] = 0; 1600 dst->fMat[kMTransX] = srcPt[0].fX; 1601 dst->fMat[kMTransY] = srcPt[0].fY; 1602 dst->fMat[kMPersp2] = SK_Fract1; 1603 dst->setTypeMask(kUnknown_Mask); 1604 return true; 1605} 1606 1607bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst, 1608 const SkPoint& scale) { 1609 SkFract a1, a2; 1610 SkFixed x0, y0, x1, y1, x2, y2; 1611 1612 x0 = srcPt[2].fX - srcPt[0].fX; 1613 y0 = srcPt[2].fY - srcPt[0].fY; 1614 x1 = srcPt[2].fX - srcPt[1].fX; 1615 y1 = srcPt[2].fY - srcPt[1].fY; 1616 x2 = srcPt[2].fX - srcPt[3].fX; 1617 y2 = srcPt[2].fY - srcPt[3].fY; 1618 1619 /* check if abs(x2) > abs(y2) */ 1620 if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) { 1621 SkFixed denom = SkMulDiv(x1, y2, x2) - y1; 1622 if (0 == denom) { 1623 return false; 1624 } 1625 a1 = SkFractDiv(SkMulDiv(x0 - x1, y2, x2) - y0 + y1, denom); 1626 } else { 1627 SkFixed denom = x1 - SkMulDiv(y1, x2, y2); 1628 if (0 == denom) { 1629 return false; 1630 } 1631 a1 = SkFractDiv(x0 - x1 - SkMulDiv(y0 - y1, x2, y2), denom); 1632 } 1633 1634 /* check if abs(x1) > abs(y1) */ 1635 if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) { 1636 SkFixed denom = y2 - SkMulDiv(x2, y1, x1); 1637 if (0 == denom) { 1638 return false; 1639 } 1640 a2 = SkFractDiv(y0 - y2 - SkMulDiv(x0 - x2, y1, x1), denom); 1641 } else { 1642 SkFixed denom = SkMulDiv(y2, x1, y1) - x2; 1643 if (0 == denom) { 1644 return false; 1645 } 1646 a2 = SkFractDiv(SkMulDiv(y0 - y2, x1, y1) - x0 + x2, denom); 1647 } 1648 1649 // need to check if SkFixedDiv overflows... 1650 dst->fMat[kMScaleX] = SkFixedDiv(SkFractMul(a2, srcPt[3].fX) + 1651 srcPt[3].fX - srcPt[0].fX, scale.fX); 1652 dst->fMat[kMSkewY] = SkFixedDiv(SkFractMul(a2, srcPt[3].fY) + 1653 srcPt[3].fY - srcPt[0].fY, scale.fX); 1654 dst->fMat[kMPersp0] = SkFixedDiv(a2, scale.fX); 1655 dst->fMat[kMSkewX] = SkFixedDiv(SkFractMul(a1, srcPt[1].fX) + 1656 srcPt[1].fX - srcPt[0].fX, scale.fY); 1657 dst->fMat[kMScaleY] = SkFixedDiv(SkFractMul(a1, srcPt[1].fY) + 1658 srcPt[1].fY - srcPt[0].fY, scale.fY); 1659 dst->fMat[kMPersp1] = SkFixedDiv(a1, scale.fY); 1660 dst->fMat[kMTransX] = srcPt[0].fX; 1661 dst->fMat[kMTransY] = srcPt[0].fY; 1662 dst->fMat[kMPersp2] = SK_Fract1; 1663 dst->setTypeMask(kUnknown_Mask); 1664 return true; 1665} 1666 1667#else /* Scalar is float */ 1668 1669static inline bool checkForZero(float x) { 1670 return x*x == 0; 1671} 1672 1673static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) { 1674 float x = 1, y = 1; 1675 SkPoint pt1, pt2; 1676 1677 if (count > 1) { 1678 pt1.fX = poly[1].fX - poly[0].fX; 1679 pt1.fY = poly[1].fY - poly[0].fY; 1680 y = SkPoint::Length(pt1.fX, pt1.fY); 1681 if (checkForZero(y)) { 1682 return false; 1683 } 1684 switch (count) { 1685 case 2: 1686 break; 1687 case 3: 1688 pt2.fX = poly[0].fY - poly[2].fY; 1689 pt2.fY = poly[2].fX - poly[0].fX; 1690 goto CALC_X; 1691 default: 1692 pt2.fX = poly[0].fY - poly[3].fY; 1693 pt2.fY = poly[3].fX - poly[0].fX; 1694 CALC_X: 1695 x = SkScalarDiv(SkScalarMul(pt1.fX, pt2.fX) + 1696 SkScalarMul(pt1.fY, pt2.fY), y); 1697 break; 1698 } 1699 } 1700 pt->set(x, y); 1701 return true; 1702} 1703 1704bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst, 1705 const SkPoint& scale) { 1706 float invScale = 1 / scale.fY; 1707 1708 dst->fMat[kMScaleX] = (srcPt[1].fY - srcPt[0].fY) * invScale; 1709 dst->fMat[kMSkewY] = (srcPt[0].fX - srcPt[1].fX) * invScale; 1710 dst->fMat[kMPersp0] = 0; 1711 dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale; 1712 dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale; 1713 dst->fMat[kMPersp1] = 0; 1714 dst->fMat[kMTransX] = srcPt[0].fX; 1715 dst->fMat[kMTransY] = srcPt[0].fY; 1716 dst->fMat[kMPersp2] = 1; 1717 dst->setTypeMask(kUnknown_Mask); 1718 return true; 1719} 1720 1721bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst, 1722 const SkPoint& scale) { 1723 float invScale = 1 / scale.fX; 1724 dst->fMat[kMScaleX] = (srcPt[2].fX - srcPt[0].fX) * invScale; 1725 dst->fMat[kMSkewY] = (srcPt[2].fY - srcPt[0].fY) * invScale; 1726 dst->fMat[kMPersp0] = 0; 1727 1728 invScale = 1 / scale.fY; 1729 dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale; 1730 dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale; 1731 dst->fMat[kMPersp1] = 0; 1732 1733 dst->fMat[kMTransX] = srcPt[0].fX; 1734 dst->fMat[kMTransY] = srcPt[0].fY; 1735 dst->fMat[kMPersp2] = 1; 1736 dst->setTypeMask(kUnknown_Mask); 1737 return true; 1738} 1739 1740bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst, 1741 const SkPoint& scale) { 1742 float a1, a2; 1743 float x0, y0, x1, y1, x2, y2; 1744 1745 x0 = srcPt[2].fX - srcPt[0].fX; 1746 y0 = srcPt[2].fY - srcPt[0].fY; 1747 x1 = srcPt[2].fX - srcPt[1].fX; 1748 y1 = srcPt[2].fY - srcPt[1].fY; 1749 x2 = srcPt[2].fX - srcPt[3].fX; 1750 y2 = srcPt[2].fY - srcPt[3].fY; 1751 1752 /* check if abs(x2) > abs(y2) */ 1753 if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) { 1754 float denom = SkScalarMulDiv(x1, y2, x2) - y1; 1755 if (checkForZero(denom)) { 1756 return false; 1757 } 1758 a1 = SkScalarDiv(SkScalarMulDiv(x0 - x1, y2, x2) - y0 + y1, denom); 1759 } else { 1760 float denom = x1 - SkScalarMulDiv(y1, x2, y2); 1761 if (checkForZero(denom)) { 1762 return false; 1763 } 1764 a1 = SkScalarDiv(x0 - x1 - SkScalarMulDiv(y0 - y1, x2, y2), denom); 1765 } 1766 1767 /* check if abs(x1) > abs(y1) */ 1768 if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) { 1769 float denom = y2 - SkScalarMulDiv(x2, y1, x1); 1770 if (checkForZero(denom)) { 1771 return false; 1772 } 1773 a2 = SkScalarDiv(y0 - y2 - SkScalarMulDiv(x0 - x2, y1, x1), denom); 1774 } else { 1775 float denom = SkScalarMulDiv(y2, x1, y1) - x2; 1776 if (checkForZero(denom)) { 1777 return false; 1778 } 1779 a2 = SkScalarDiv(SkScalarMulDiv(y0 - y2, x1, y1) - x0 + x2, denom); 1780 } 1781 1782 float invScale = 1 / scale.fX; 1783 dst->fMat[kMScaleX] = SkScalarMul(SkScalarMul(a2, srcPt[3].fX) + 1784 srcPt[3].fX - srcPt[0].fX, invScale); 1785 dst->fMat[kMSkewY] = SkScalarMul(SkScalarMul(a2, srcPt[3].fY) + 1786 srcPt[3].fY - srcPt[0].fY, invScale); 1787 dst->fMat[kMPersp0] = SkScalarMul(a2, invScale); 1788 invScale = 1 / scale.fY; 1789 dst->fMat[kMSkewX] = SkScalarMul(SkScalarMul(a1, srcPt[1].fX) + 1790 srcPt[1].fX - srcPt[0].fX, invScale); 1791 dst->fMat[kMScaleY] = SkScalarMul(SkScalarMul(a1, srcPt[1].fY) + 1792 srcPt[1].fY - srcPt[0].fY, invScale); 1793 dst->fMat[kMPersp1] = SkScalarMul(a1, invScale); 1794 dst->fMat[kMTransX] = srcPt[0].fX; 1795 dst->fMat[kMTransY] = srcPt[0].fY; 1796 dst->fMat[kMPersp2] = 1; 1797 dst->setTypeMask(kUnknown_Mask); 1798 return true; 1799} 1800 1801#endif 1802 1803typedef bool (*PolyMapProc)(const SkPoint[], SkMatrix*, const SkPoint&); 1804 1805/* Taken from Rob Johnson's original sample code in QuickDraw GX 1806*/ 1807bool SkMatrix::setPolyToPoly(const SkPoint src[], const SkPoint dst[], 1808 int count) { 1809 if ((unsigned)count > 4) { 1810 SkDebugf("--- SkMatrix::setPolyToPoly count out of range %d\n", count); 1811 return false; 1812 } 1813 1814 if (0 == count) { 1815 this->reset(); 1816 return true; 1817 } 1818 if (1 == count) { 1819 this->setTranslate(dst[0].fX - src[0].fX, dst[0].fY - src[0].fY); 1820 return true; 1821 } 1822 1823 SkPoint scale; 1824 if (!poly_to_point(&scale, src, count) || 1825 SkScalarNearlyZero(scale.fX) || 1826 SkScalarNearlyZero(scale.fY)) { 1827 return false; 1828 } 1829 1830 static const PolyMapProc gPolyMapProcs[] = { 1831 SkMatrix::Poly2Proc, SkMatrix::Poly3Proc, SkMatrix::Poly4Proc 1832 }; 1833 PolyMapProc proc = gPolyMapProcs[count - 2]; 1834 1835 SkMatrix tempMap, result; 1836 tempMap.setTypeMask(kUnknown_Mask); 1837 1838 if (!proc(src, &tempMap, scale)) { 1839 return false; 1840 } 1841 if (!tempMap.invert(&result)) { 1842 return false; 1843 } 1844 if (!proc(dst, &tempMap, scale)) { 1845 return false; 1846 } 1847 if (!result.setConcat(tempMap, result)) { 1848 return false; 1849 } 1850 *this = result; 1851 return true; 1852} 1853 1854/////////////////////////////////////////////////////////////////////////////// 1855 1856SkScalar SkMatrix::getMaxStretch() const { 1857 TypeMask mask = this->getType(); 1858 1859 if (this->hasPerspective()) { 1860 return -SK_Scalar1; 1861 } 1862 if (this->isIdentity()) { 1863 return SK_Scalar1; 1864 } 1865 if (!(mask & kAffine_Mask)) { 1866 return SkMaxScalar(SkScalarAbs(fMat[kMScaleX]), 1867 SkScalarAbs(fMat[kMScaleY])); 1868 } 1869 // ignore the translation part of the matrix, just look at 2x2 portion. 1870 // compute singular values, take largest abs value. 1871 // [a b; b c] = A^T*A 1872 SkScalar a = SkScalarMul(fMat[kMScaleX], fMat[kMScaleX]) + 1873 SkScalarMul(fMat[kMSkewY], fMat[kMSkewY]); 1874 SkScalar b = SkScalarMul(fMat[kMScaleX], fMat[kMSkewX]) + 1875 SkScalarMul(fMat[kMScaleY], fMat[kMSkewY]); 1876 SkScalar c = SkScalarMul(fMat[kMSkewX], fMat[kMSkewX]) + 1877 SkScalarMul(fMat[kMScaleY], fMat[kMScaleY]); 1878 // eigenvalues of A^T*A are the squared singular values of A. 1879 // characteristic equation is det((A^T*A) - l*I) = 0 1880 // l^2 - (a + c)l + (ac-b^2) 1881 // solve using quadratic equation (divisor is non-zero since l^2 has 1 coeff 1882 // and roots are guaraunteed to be pos and real). 1883 SkScalar largerRoot; 1884 SkScalar bSqd = SkScalarMul(b,b); 1885 // if upper left 2x2 is orthogonal save some math 1886 if (bSqd <= SK_ScalarNearlyZero*SK_ScalarNearlyZero) { 1887 largerRoot = SkMaxScalar(a, c); 1888 } else { 1889 SkScalar aminusc = a - c; 1890 SkScalar apluscdiv2 = SkScalarHalf(a + c); 1891 SkScalar x = SkScalarHalf(SkScalarSqrt(SkScalarMul(aminusc, aminusc) + 4 * bSqd)); 1892 largerRoot = apluscdiv2 + x; 1893 } 1894 return SkScalarSqrt(largerRoot); 1895} 1896 1897static void reset_identity_matrix(SkMatrix* identity) { 1898 identity->reset(); 1899} 1900 1901const SkMatrix& SkMatrix::I() { 1902 // If you can use C++11 now, you might consider replacing this with a constexpr constructor. 1903 static SkMatrix gIdentity; 1904 SK_DECLARE_STATIC_ONCE(once); 1905 SkOnce(&once, reset_identity_matrix, &gIdentity); 1906 return gIdentity; 1907} 1908 1909const SkMatrix& SkMatrix::InvalidMatrix() { 1910 static SkMatrix gInvalid; 1911 static bool gOnce; 1912 if (!gOnce) { 1913 gInvalid.setAll(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, 1914 SK_ScalarMax, SK_ScalarMax, SK_ScalarMax, 1915 SK_ScalarMax, SK_ScalarMax, SK_ScalarMax); 1916 gInvalid.getType(); // force the type to be computed 1917 gOnce = true; 1918 } 1919 return gInvalid; 1920} 1921 1922/////////////////////////////////////////////////////////////////////////////// 1923 1924uint32_t SkMatrix::writeToMemory(void* buffer) const { 1925 // TODO write less for simple matrices 1926 if (buffer) { 1927 memcpy(buffer, fMat, 9 * sizeof(SkScalar)); 1928 } 1929 return 9 * sizeof(SkScalar); 1930} 1931 1932uint32_t SkMatrix::readFromMemory(const void* buffer) { 1933 if (buffer) { 1934 memcpy(fMat, buffer, 9 * sizeof(SkScalar)); 1935 this->setTypeMask(kUnknown_Mask); 1936 } 1937 return 9 * sizeof(SkScalar); 1938} 1939 1940#ifdef SK_DEVELOPER 1941void SkMatrix::dump() const { 1942 SkString str; 1943 this->toString(&str); 1944 SkDebugf("%s\n", str.c_str()); 1945} 1946 1947void SkMatrix::toString(SkString* str) const { 1948 str->appendf("[%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f]", 1949#ifdef SK_SCALAR_IS_FLOAT 1950 fMat[0], fMat[1], fMat[2], fMat[3], fMat[4], fMat[5], 1951 fMat[6], fMat[7], fMat[8]); 1952#else 1953 SkFixedToFloat(fMat[0]), SkFixedToFloat(fMat[1]), SkFixedToFloat(fMat[2]), 1954 SkFixedToFloat(fMat[3]), SkFixedToFloat(fMat[4]), SkFixedToFloat(fMat[5]), 1955 SkFractToFloat(fMat[6]), SkFractToFloat(fMat[7]), SkFractToFloat(fMat[8])); 1956#endif 1957} 1958#endif 1959 1960/////////////////////////////////////////////////////////////////////////////// 1961 1962#include "SkMatrixUtils.h" 1963 1964bool SkTreatAsSprite(const SkMatrix& mat, int width, int height, 1965 unsigned subpixelBits) { 1966 // quick reject on affine or perspective 1967 if (mat.getType() & ~(SkMatrix::kScale_Mask | SkMatrix::kTranslate_Mask)) { 1968 return false; 1969 } 1970 1971 // quick success check 1972 if (!subpixelBits && !(mat.getType() & ~SkMatrix::kTranslate_Mask)) { 1973 return true; 1974 } 1975 1976 // mapRect supports negative scales, so we eliminate those first 1977 if (mat.getScaleX() < 0 || mat.getScaleY() < 0) { 1978 return false; 1979 } 1980 1981 SkRect dst; 1982 SkIRect isrc = { 0, 0, width, height }; 1983 1984 { 1985 SkRect src; 1986 src.set(isrc); 1987 mat.mapRect(&dst, src); 1988 } 1989 1990 // just apply the translate to isrc 1991 isrc.offset(SkScalarRoundToInt(mat.getTranslateX()), 1992 SkScalarRoundToInt(mat.getTranslateY())); 1993 1994 if (subpixelBits) { 1995 isrc.fLeft <<= subpixelBits; 1996 isrc.fTop <<= subpixelBits; 1997 isrc.fRight <<= subpixelBits; 1998 isrc.fBottom <<= subpixelBits; 1999 2000 const float scale = 1 << subpixelBits; 2001 dst.fLeft *= scale; 2002 dst.fTop *= scale; 2003 dst.fRight *= scale; 2004 dst.fBottom *= scale; 2005 } 2006 2007 SkIRect idst; 2008 dst.round(&idst); 2009 return isrc == idst; 2010} 2011 2012// A square matrix M can be decomposed (via polar decomposition) into two matrices -- 2013// an orthogonal matrix Q and a symmetric matrix S. In turn we can decompose S into U*W*U^T, 2014// where U is another orthogonal matrix and W is a scale matrix. These can be recombined 2015// to give M = (Q*U)*W*U^T, i.e., the product of two orthogonal matrices and a scale matrix. 2016// 2017// The one wrinkle is that traditionally Q may contain a reflection -- the 2018// calculation has been rejiggered to put that reflection into W. 2019bool SkDecomposeUpper2x2(const SkMatrix& matrix, 2020 SkPoint* rotation1, 2021 SkPoint* scale, 2022 SkPoint* rotation2) { 2023 2024 SkScalar A = matrix[SkMatrix::kMScaleX]; 2025 SkScalar B = matrix[SkMatrix::kMSkewX]; 2026 SkScalar C = matrix[SkMatrix::kMSkewY]; 2027 SkScalar D = matrix[SkMatrix::kMScaleY]; 2028 2029 if (is_degenerate_2x2(A, B, C, D)) { 2030 return false; 2031 } 2032 2033 double w1, w2; 2034 SkScalar cos1, sin1; 2035 SkScalar cos2, sin2; 2036 2037 // do polar decomposition (M = Q*S) 2038 SkScalar cosQ, sinQ; 2039 double Sa, Sb, Sd; 2040 // if M is already symmetric (i.e., M = I*S) 2041 if (SkScalarNearlyEqual(B, C)) { 2042 cosQ = SK_Scalar1; 2043 sinQ = 0; 2044 2045 Sa = A; 2046 Sb = B; 2047 Sd = D; 2048 } else { 2049 cosQ = A + D; 2050 sinQ = C - B; 2051 SkScalar reciplen = SK_Scalar1/SkScalarSqrt(cosQ*cosQ + sinQ*sinQ); 2052 cosQ *= reciplen; 2053 sinQ *= reciplen; 2054 2055 // S = Q^-1*M 2056 // we don't calc Sc since it's symmetric 2057 Sa = A*cosQ + C*sinQ; 2058 Sb = B*cosQ + D*sinQ; 2059 Sd = -B*sinQ + D*cosQ; 2060 } 2061 2062 // Now we need to compute eigenvalues of S (our scale factors) 2063 // and eigenvectors (bases for our rotation) 2064 // From this, should be able to reconstruct S as U*W*U^T 2065 if (SkScalarNearlyZero(SkDoubleToScalar(Sb))) { 2066 // already diagonalized 2067 cos1 = SK_Scalar1; 2068 sin1 = 0; 2069 w1 = Sa; 2070 w2 = Sd; 2071 cos2 = cosQ; 2072 sin2 = sinQ; 2073 } else { 2074 double diff = Sa - Sd; 2075 double discriminant = sqrt(diff*diff + 4.0*Sb*Sb); 2076 double trace = Sa + Sd; 2077 if (diff > 0) { 2078 w1 = 0.5*(trace + discriminant); 2079 w2 = 0.5*(trace - discriminant); 2080 } else { 2081 w1 = 0.5*(trace - discriminant); 2082 w2 = 0.5*(trace + discriminant); 2083 } 2084 2085 cos1 = SkDoubleToScalar(Sb); sin1 = SkDoubleToScalar(w1 - Sa); 2086 SkScalar reciplen = SK_Scalar1/SkScalarSqrt(cos1*cos1 + sin1*sin1); 2087 cos1 *= reciplen; 2088 sin1 *= reciplen; 2089 2090 // rotation 2 is composition of Q and U 2091 cos2 = cos1*cosQ - sin1*sinQ; 2092 sin2 = sin1*cosQ + cos1*sinQ; 2093 2094 // rotation 1 is U^T 2095 sin1 = -sin1; 2096 } 2097 2098 if (NULL != scale) { 2099 scale->fX = SkDoubleToScalar(w1); 2100 scale->fY = SkDoubleToScalar(w2); 2101 } 2102 if (NULL != rotation1) { 2103 rotation1->fX = cos1; 2104 rotation1->fY = sin1; 2105 } 2106 if (NULL != rotation2) { 2107 rotation2->fX = cos2; 2108 rotation2->fY = sin2; 2109 } 2110 2111 return true; 2112} 2113