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