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