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