gfx/skia/trunk/src/core/SkMatrix.cpp@129ffea94266
gfx/skia/trunk/src/core/SkMatrix.cpp
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
1 /*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
8 #include "SkMatrix.h"
9 #include "SkFloatBits.h"
10 #include "SkOnce.h"
11 #include "SkString.h"
13 // In a few places, we performed the following
14 // a * b + c * d + e
15 // as
16 // a * b + (c * d + e)
17 //
18 // sdot and scross are indended to capture these compound operations into a
19 // function, with an eye toward considering upscaling the intermediates to
20 // doubles for more precision (as we do in concat and invert).
21 //
22 // However, these few lines that performed the last add before the "dot", cause
23 // tiny image differences, so we guard that change until we see the impact on
24 // chrome's layouttests.
25 //
26 #define SK_LEGACY_MATRIX_MATH_ORDER
28 static inline float SkDoubleToFloat(double x) {
29 return static_cast<float>(x);
30 }
32 /* [scale-x skew-x trans-x] [X] [X']
33 [skew-y scale-y trans-y] * [Y] = [Y']
34 [persp-0 persp-1 persp-2] [1] [1 ]
35 */
37 void SkMatrix::reset() {
38 fMat[kMScaleX] = fMat[kMScaleY] = fMat[kMPersp2] = 1;
39 fMat[kMSkewX] = fMat[kMSkewY] =
40 fMat[kMTransX] = fMat[kMTransY] =
41 fMat[kMPersp0] = fMat[kMPersp1] = 0;
43 this->setTypeMask(kIdentity_Mask | kRectStaysRect_Mask);
44 }
46 // this guy aligns with the masks, so we can compute a mask from a varaible 0/1
47 enum {
48 kTranslate_Shift,
49 kScale_Shift,
50 kAffine_Shift,
51 kPerspective_Shift,
52 kRectStaysRect_Shift
53 };
55 static const int32_t kScalar1Int = 0x3f800000;
57 uint8_t SkMatrix::computePerspectiveTypeMask() const {
58 // Benchmarking suggests that replacing this set of SkScalarAs2sCompliment
59 // is a win, but replacing those below is not. We don't yet understand
60 // that result.
61 if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 || fMat[kMPersp2] != 1) {
62 // If this is a perspective transform, we return true for all other
63 // transform flags - this does not disable any optimizations, respects
64 // the rule that the type mask must be conservative, and speeds up
65 // type mask computation.
66 return SkToU8(kORableMasks);
67 }
69 return SkToU8(kOnlyPerspectiveValid_Mask | kUnknown_Mask);
70 }
72 uint8_t SkMatrix::computeTypeMask() const {
73 unsigned mask = 0;
75 if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 || fMat[kMPersp2] != 1) {
76 // Once it is determined that that this is a perspective transform,
77 // all other flags are moot as far as optimizations are concerned.
78 return SkToU8(kORableMasks);
79 }
81 if (fMat[kMTransX] != 0 || fMat[kMTransY] != 0) {
82 mask |= kTranslate_Mask;
83 }
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]);
90 if (m01 | m10) {
91 // The skew components may be scale-inducing, unless we are dealing
92 // with a pure rotation. Testing for a pure rotation is expensive,
93 // so we opt for being conservative by always setting the scale bit.
94 // along with affine.
95 // By doing this, we are also ensuring that matrices have the same
96 // type masks as their inverses.
97 mask |= kAffine_Mask | kScale_Mask;
99 // For rectStaysRect, in the affine case, we only need check that
100 // the primary diagonal is all zeros and that the secondary diagonal
101 // is all non-zero.
103 // map non-zero to 1
104 m01 = m01 != 0;
105 m10 = m10 != 0;
107 int dp0 = 0 == (m00 | m11) ; // true if both are 0
108 int ds1 = m01 & m10; // true if both are 1
110 mask |= (dp0 & ds1) << kRectStaysRect_Shift;
111 } else {
112 // Only test for scale explicitly if not affine, since affine sets the
113 // scale bit.
114 if ((m00 - kScalar1Int) | (m11 - kScalar1Int)) {
115 mask |= kScale_Mask;
116 }
118 // Not affine, therefore we already know secondary diagonal is
119 // all zeros, so we just need to check that primary diagonal is
120 // all non-zero.
122 // map non-zero to 1
123 m00 = m00 != 0;
124 m11 = m11 != 0;
126 // record if the (p)rimary diagonal is all non-zero
127 mask |= (m00 & m11) << kRectStaysRect_Shift;
128 }
130 return SkToU8(mask);
131 }
133 ///////////////////////////////////////////////////////////////////////////////
135 bool operator==(const SkMatrix& a, const SkMatrix& b) {
136 const SkScalar* SK_RESTRICT ma = a.fMat;
137 const SkScalar* SK_RESTRICT mb = b.fMat;
139 return ma[0] == mb[0] && ma[1] == mb[1] && ma[2] == mb[2] &&
140 ma[3] == mb[3] && ma[4] == mb[4] && ma[5] == mb[5] &&
141 ma[6] == mb[6] && ma[7] == mb[7] && ma[8] == mb[8];
142 }
144 ///////////////////////////////////////////////////////////////////////////////
146 // helper function to determine if upper-left 2x2 of matrix is degenerate
147 static inline bool is_degenerate_2x2(SkScalar scaleX, SkScalar skewX,
148 SkScalar skewY, SkScalar scaleY) {
149 SkScalar perp_dot = scaleX*scaleY - skewX*skewY;
150 return SkScalarNearlyZero(perp_dot, SK_ScalarNearlyZero*SK_ScalarNearlyZero);
151 }
153 ///////////////////////////////////////////////////////////////////////////////
155 bool SkMatrix::isSimilarity(SkScalar tol) const {
156 // if identity or translate matrix
157 TypeMask mask = this->getType();
158 if (mask <= kTranslate_Mask) {
159 return true;
160 }
161 if (mask & kPerspective_Mask) {
162 return false;
163 }
165 SkScalar mx = fMat[kMScaleX];
166 SkScalar my = fMat[kMScaleY];
167 // if no skew, can just compare scale factors
168 if (!(mask & kAffine_Mask)) {
169 return !SkScalarNearlyZero(mx) && SkScalarNearlyEqual(SkScalarAbs(mx), SkScalarAbs(my));
170 }
171 SkScalar sx = fMat[kMSkewX];
172 SkScalar sy = fMat[kMSkewY];
174 if (is_degenerate_2x2(mx, sx, sy, my)) {
175 return false;
176 }
178 // it has scales and skews, but it could also be rotation, check it out.
179 SkVector vec[2];
180 vec[0].set(mx, sx);
181 vec[1].set(sy, my);
183 return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) &&
184 SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(),
185 SkScalarSquare(tol));
186 }
188 bool SkMatrix::preservesRightAngles(SkScalar tol) const {
189 TypeMask mask = this->getType();
191 if (mask <= (SkMatrix::kTranslate_Mask | SkMatrix::kScale_Mask)) {
192 // identity, translate and/or scale
193 return true;
194 }
195 if (mask & kPerspective_Mask) {
196 return false;
197 }
199 SkASSERT(mask & kAffine_Mask);
201 SkScalar mx = fMat[kMScaleX];
202 SkScalar my = fMat[kMScaleY];
203 SkScalar sx = fMat[kMSkewX];
204 SkScalar sy = fMat[kMSkewY];
206 if (is_degenerate_2x2(mx, sx, sy, my)) {
207 return false;
208 }
210 // it has scales and skews, but it could also be rotation, check it out.
211 SkVector vec[2];
212 vec[0].set(mx, sx);
213 vec[1].set(sy, my);
215 return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) &&
216 SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(),
217 SkScalarSquare(tol));
218 }
220 ///////////////////////////////////////////////////////////////////////////////
222 static inline SkScalar sdot(SkScalar a, SkScalar b, SkScalar c, SkScalar d) {
223 return a * b + c * d;
224 }
226 static inline SkScalar sdot(SkScalar a, SkScalar b, SkScalar c, SkScalar d,
227 SkScalar e, SkScalar f) {
228 return a * b + c * d + e * f;
229 }
231 static inline SkScalar scross(SkScalar a, SkScalar b, SkScalar c, SkScalar d) {
232 return a * b - c * d;
233 }
235 void SkMatrix::setTranslate(SkScalar dx, SkScalar dy) {
236 if (dx || dy) {
237 fMat[kMTransX] = dx;
238 fMat[kMTransY] = dy;
240 fMat[kMScaleX] = fMat[kMScaleY] = fMat[kMPersp2] = 1;
241 fMat[kMSkewX] = fMat[kMSkewY] =
242 fMat[kMPersp0] = fMat[kMPersp1] = 0;
244 this->setTypeMask(kTranslate_Mask | kRectStaysRect_Mask);
245 } else {
246 this->reset();
247 }
248 }
250 bool SkMatrix::preTranslate(SkScalar dx, SkScalar dy) {
251 if (this->hasPerspective()) {
252 SkMatrix m;
253 m.setTranslate(dx, dy);
254 return this->preConcat(m);
255 }
257 if (dx || dy) {
258 fMat[kMTransX] += sdot(fMat[kMScaleX], dx, fMat[kMSkewX], dy);
259 fMat[kMTransY] += sdot(fMat[kMSkewY], dx, fMat[kMScaleY], dy);
261 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
262 }
263 return true;
264 }
266 bool SkMatrix::postTranslate(SkScalar dx, SkScalar dy) {
267 if (this->hasPerspective()) {
268 SkMatrix m;
269 m.setTranslate(dx, dy);
270 return this->postConcat(m);
271 }
273 if (dx || dy) {
274 fMat[kMTransX] += dx;
275 fMat[kMTransY] += dy;
276 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
277 }
278 return true;
279 }
281 ///////////////////////////////////////////////////////////////////////////////
283 void SkMatrix::setScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
284 if (1 == sx && 1 == sy) {
285 this->reset();
286 } else {
287 fMat[kMScaleX] = sx;
288 fMat[kMScaleY] = sy;
289 fMat[kMTransX] = px - sx * px;
290 fMat[kMTransY] = py - sy * py;
291 fMat[kMPersp2] = 1;
293 fMat[kMSkewX] = fMat[kMSkewY] =
294 fMat[kMPersp0] = fMat[kMPersp1] = 0;
296 this->setTypeMask(kScale_Mask | kTranslate_Mask | kRectStaysRect_Mask);
297 }
298 }
300 void SkMatrix::setScale(SkScalar sx, SkScalar sy) {
301 if (1 == sx && 1 == sy) {
302 this->reset();
303 } else {
304 fMat[kMScaleX] = sx;
305 fMat[kMScaleY] = sy;
306 fMat[kMPersp2] = 1;
308 fMat[kMTransX] = fMat[kMTransY] =
309 fMat[kMSkewX] = fMat[kMSkewY] =
310 fMat[kMPersp0] = fMat[kMPersp1] = 0;
312 this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
313 }
314 }
316 bool SkMatrix::setIDiv(int divx, int divy) {
317 if (!divx || !divy) {
318 return false;
319 }
320 this->setScale(SkScalarInvert(divx), SkScalarInvert(divy));
321 return true;
322 }
324 bool SkMatrix::preScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
325 SkMatrix m;
326 m.setScale(sx, sy, px, py);
327 return this->preConcat(m);
328 }
330 bool SkMatrix::preScale(SkScalar sx, SkScalar sy) {
331 if (1 == sx && 1 == sy) {
332 return true;
333 }
335 // the assumption is that these multiplies are very cheap, and that
336 // a full concat and/or just computing the matrix type is more expensive.
337 // Also, the fixed-point case checks for overflow, but the float doesn't,
338 // so we can get away with these blind multiplies.
340 fMat[kMScaleX] *= sx;
341 fMat[kMSkewY] *= sx;
342 fMat[kMPersp0] *= sx;
344 fMat[kMSkewX] *= sy;
345 fMat[kMScaleY] *= sy;
346 fMat[kMPersp1] *= sy;
348 this->orTypeMask(kScale_Mask);
349 return true;
350 }
352 bool SkMatrix::postScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
353 if (1 == sx && 1 == sy) {
354 return true;
355 }
356 SkMatrix m;
357 m.setScale(sx, sy, px, py);
358 return this->postConcat(m);
359 }
361 bool SkMatrix::postScale(SkScalar sx, SkScalar sy) {
362 if (1 == sx && 1 == sy) {
363 return true;
364 }
365 SkMatrix m;
366 m.setScale(sx, sy);
367 return this->postConcat(m);
368 }
370 // this guy perhaps can go away, if we have a fract/high-precision way to
371 // scale matrices
372 bool SkMatrix::postIDiv(int divx, int divy) {
373 if (divx == 0 || divy == 0) {
374 return false;
375 }
377 const float invX = 1.f / divx;
378 const float invY = 1.f / divy;
380 fMat[kMScaleX] *= invX;
381 fMat[kMSkewX] *= invX;
382 fMat[kMTransX] *= invX;
384 fMat[kMScaleY] *= invY;
385 fMat[kMSkewY] *= invY;
386 fMat[kMTransY] *= invY;
388 this->setTypeMask(kUnknown_Mask);
389 return true;
390 }
392 ////////////////////////////////////////////////////////////////////////////////////
394 void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV,
395 SkScalar px, SkScalar py) {
396 const SkScalar oneMinusCosV = 1 - cosV;
398 fMat[kMScaleX] = cosV;
399 fMat[kMSkewX] = -sinV;
400 fMat[kMTransX] = sdot(sinV, py, oneMinusCosV, px);
402 fMat[kMSkewY] = sinV;
403 fMat[kMScaleY] = cosV;
404 fMat[kMTransY] = sdot(-sinV, px, oneMinusCosV, py);
406 fMat[kMPersp0] = fMat[kMPersp1] = 0;
407 fMat[kMPersp2] = 1;
409 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
410 }
412 void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV) {
413 fMat[kMScaleX] = cosV;
414 fMat[kMSkewX] = -sinV;
415 fMat[kMTransX] = 0;
417 fMat[kMSkewY] = sinV;
418 fMat[kMScaleY] = cosV;
419 fMat[kMTransY] = 0;
421 fMat[kMPersp0] = fMat[kMPersp1] = 0;
422 fMat[kMPersp2] = 1;
424 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
425 }
427 void SkMatrix::setRotate(SkScalar degrees, SkScalar px, SkScalar py) {
428 SkScalar sinV, cosV;
429 sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
430 this->setSinCos(sinV, cosV, px, py);
431 }
433 void SkMatrix::setRotate(SkScalar degrees) {
434 SkScalar sinV, cosV;
435 sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
436 this->setSinCos(sinV, cosV);
437 }
439 bool SkMatrix::preRotate(SkScalar degrees, SkScalar px, SkScalar py) {
440 SkMatrix m;
441 m.setRotate(degrees, px, py);
442 return this->preConcat(m);
443 }
445 bool SkMatrix::preRotate(SkScalar degrees) {
446 SkMatrix m;
447 m.setRotate(degrees);
448 return this->preConcat(m);
449 }
451 bool SkMatrix::postRotate(SkScalar degrees, SkScalar px, SkScalar py) {
452 SkMatrix m;
453 m.setRotate(degrees, px, py);
454 return this->postConcat(m);
455 }
457 bool SkMatrix::postRotate(SkScalar degrees) {
458 SkMatrix m;
459 m.setRotate(degrees);
460 return this->postConcat(m);
461 }
463 ////////////////////////////////////////////////////////////////////////////////////
465 void SkMatrix::setSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
466 fMat[kMScaleX] = 1;
467 fMat[kMSkewX] = sx;
468 fMat[kMTransX] = -sx * py;
470 fMat[kMSkewY] = sy;
471 fMat[kMScaleY] = 1;
472 fMat[kMTransY] = -sy * px;
474 fMat[kMPersp0] = fMat[kMPersp1] = 0;
475 fMat[kMPersp2] = 1;
477 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
478 }
480 void SkMatrix::setSkew(SkScalar sx, SkScalar sy) {
481 fMat[kMScaleX] = 1;
482 fMat[kMSkewX] = sx;
483 fMat[kMTransX] = 0;
485 fMat[kMSkewY] = sy;
486 fMat[kMScaleY] = 1;
487 fMat[kMTransY] = 0;
489 fMat[kMPersp0] = fMat[kMPersp1] = 0;
490 fMat[kMPersp2] = 1;
492 this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
493 }
495 bool SkMatrix::preSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
496 SkMatrix m;
497 m.setSkew(sx, sy, px, py);
498 return this->preConcat(m);
499 }
501 bool SkMatrix::preSkew(SkScalar sx, SkScalar sy) {
502 SkMatrix m;
503 m.setSkew(sx, sy);
504 return this->preConcat(m);
505 }
507 bool SkMatrix::postSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
508 SkMatrix m;
509 m.setSkew(sx, sy, px, py);
510 return this->postConcat(m);
511 }
513 bool SkMatrix::postSkew(SkScalar sx, SkScalar sy) {
514 SkMatrix m;
515 m.setSkew(sx, sy);
516 return this->postConcat(m);
517 }
519 ///////////////////////////////////////////////////////////////////////////////
521 bool SkMatrix::setRectToRect(const SkRect& src, const SkRect& dst,
522 ScaleToFit align)
523 {
524 if (src.isEmpty()) {
525 this->reset();
526 return false;
527 }
529 if (dst.isEmpty()) {
530 sk_bzero(fMat, 8 * sizeof(SkScalar));
531 this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
532 } else {
533 SkScalar tx, sx = dst.width() / src.width();
534 SkScalar ty, sy = dst.height() / src.height();
535 bool xLarger = false;
537 if (align != kFill_ScaleToFit) {
538 if (sx > sy) {
539 xLarger = true;
540 sx = sy;
541 } else {
542 sy = sx;
543 }
544 }
546 tx = dst.fLeft - src.fLeft * sx;
547 ty = dst.fTop - src.fTop * sy;
548 if (align == kCenter_ScaleToFit || align == kEnd_ScaleToFit) {
549 SkScalar diff;
551 if (xLarger) {
552 diff = dst.width() - src.width() * sy;
553 } else {
554 diff = dst.height() - src.height() * sy;
555 }
557 if (align == kCenter_ScaleToFit) {
558 diff = SkScalarHalf(diff);
559 }
561 if (xLarger) {
562 tx += diff;
563 } else {
564 ty += diff;
565 }
566 }
568 fMat[kMScaleX] = sx;
569 fMat[kMScaleY] = sy;
570 fMat[kMTransX] = tx;
571 fMat[kMTransY] = ty;
572 fMat[kMSkewX] = fMat[kMSkewY] =
573 fMat[kMPersp0] = fMat[kMPersp1] = 0;
575 unsigned mask = kRectStaysRect_Mask;
576 if (sx != 1 || sy != 1) {
577 mask |= kScale_Mask;
578 }
579 if (tx || ty) {
580 mask |= kTranslate_Mask;
581 }
582 this->setTypeMask(mask);
583 }
584 // shared cleanup
585 fMat[kMPersp2] = 1;
586 return true;
587 }
589 ///////////////////////////////////////////////////////////////////////////////
591 static inline int fixmuladdmul(float a, float b, float c, float d,
592 float* result) {
593 *result = SkDoubleToFloat((double)a * b + (double)c * d);
594 return true;
595 }
597 static inline bool rowcol3(const float row[], const float col[],
598 float* result) {
599 *result = row[0] * col[0] + row[1] * col[3] + row[2] * col[6];
600 return true;
601 }
603 static inline int negifaddoverflows(float& result, float a, float b) {
604 result = a + b;
605 return 0;
606 }
608 static void normalize_perspective(SkScalar mat[9]) {
609 if (SkScalarAbs(mat[SkMatrix::kMPersp2]) > 1) {
610 for (int i = 0; i < 9; i++)
611 mat[i] = SkScalarHalf(mat[i]);
612 }
613 }
615 bool SkMatrix::setConcat(const SkMatrix& a, const SkMatrix& b) {
616 TypeMask aType = a.getPerspectiveTypeMaskOnly();
617 TypeMask bType = b.getPerspectiveTypeMaskOnly();
619 if (a.isTriviallyIdentity()) {
620 *this = b;
621 } else if (b.isTriviallyIdentity()) {
622 *this = a;
623 } else {
624 SkMatrix tmp;
626 if ((aType | bType) & kPerspective_Mask) {
627 if (!rowcol3(&a.fMat[0], &b.fMat[0], &tmp.fMat[kMScaleX])) {
628 return false;
629 }
630 if (!rowcol3(&a.fMat[0], &b.fMat[1], &tmp.fMat[kMSkewX])) {
631 return false;
632 }
633 if (!rowcol3(&a.fMat[0], &b.fMat[2], &tmp.fMat[kMTransX])) {
634 return false;
635 }
637 if (!rowcol3(&a.fMat[3], &b.fMat[0], &tmp.fMat[kMSkewY])) {
638 return false;
639 }
640 if (!rowcol3(&a.fMat[3], &b.fMat[1], &tmp.fMat[kMScaleY])) {
641 return false;
642 }
643 if (!rowcol3(&a.fMat[3], &b.fMat[2], &tmp.fMat[kMTransY])) {
644 return false;
645 }
647 if (!rowcol3(&a.fMat[6], &b.fMat[0], &tmp.fMat[kMPersp0])) {
648 return false;
649 }
650 if (!rowcol3(&a.fMat[6], &b.fMat[1], &tmp.fMat[kMPersp1])) {
651 return false;
652 }
653 if (!rowcol3(&a.fMat[6], &b.fMat[2], &tmp.fMat[kMPersp2])) {
654 return false;
655 }
657 normalize_perspective(tmp.fMat);
658 tmp.setTypeMask(kUnknown_Mask);
659 } else { // not perspective
660 if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMScaleX],
661 a.fMat[kMSkewX], b.fMat[kMSkewY], &tmp.fMat[kMScaleX])) {
662 return false;
663 }
664 if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMSkewX],
665 a.fMat[kMSkewX], b.fMat[kMScaleY], &tmp.fMat[kMSkewX])) {
666 return false;
667 }
668 if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMTransX],
669 a.fMat[kMSkewX], b.fMat[kMTransY], &tmp.fMat[kMTransX])) {
670 return false;
671 }
672 if (negifaddoverflows(tmp.fMat[kMTransX], tmp.fMat[kMTransX],
673 a.fMat[kMTransX]) < 0) {
674 return false;
675 }
677 if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMScaleX],
678 a.fMat[kMScaleY], b.fMat[kMSkewY], &tmp.fMat[kMSkewY])) {
679 return false;
680 }
681 if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMSkewX],
682 a.fMat[kMScaleY], b.fMat[kMScaleY], &tmp.fMat[kMScaleY])) {
683 return false;
684 }
685 if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMTransX],
686 a.fMat[kMScaleY], b.fMat[kMTransY], &tmp.fMat[kMTransY])) {
687 return false;
688 }
689 if (negifaddoverflows(tmp.fMat[kMTransY], tmp.fMat[kMTransY],
690 a.fMat[kMTransY]) < 0) {
691 return false;
692 }
694 tmp.fMat[kMPersp0] = tmp.fMat[kMPersp1] = 0;
695 tmp.fMat[kMPersp2] = 1;
696 //SkDebugf("Concat mat non-persp type: %d\n", tmp.getType());
697 //SkASSERT(!(tmp.getType() & kPerspective_Mask));
698 tmp.setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
699 }
700 *this = tmp;
701 }
702 return true;
703 }
705 bool SkMatrix::preConcat(const SkMatrix& mat) {
706 // check for identity first, so we don't do a needless copy of ourselves
707 // to ourselves inside setConcat()
708 return mat.isIdentity() || this->setConcat(*this, mat);
709 }
711 bool SkMatrix::postConcat(const SkMatrix& mat) {
712 // check for identity first, so we don't do a needless copy of ourselves
713 // to ourselves inside setConcat()
714 return mat.isIdentity() || this->setConcat(mat, *this);
715 }
717 ///////////////////////////////////////////////////////////////////////////////
719 /* Matrix inversion is very expensive, but also the place where keeping
720 precision may be most important (here and matrix concat). Hence to avoid
721 bitmap blitting artifacts when walking the inverse, we use doubles for
722 the intermediate math, even though we know that is more expensive.
723 */
725 static inline SkScalar scross_dscale(SkScalar a, SkScalar b,
726 SkScalar c, SkScalar d, double scale) {
727 return SkDoubleToScalar(scross(a, b, c, d) * scale);
728 }
730 static inline double dcross(double a, double b, double c, double d) {
731 return a * b - c * d;
732 }
734 static inline SkScalar dcross_dscale(double a, double b,
735 double c, double d, double scale) {
736 return SkDoubleToScalar(dcross(a, b, c, d) * scale);
737 }
739 static double sk_inv_determinant(const float mat[9], int isPerspective) {
740 double det;
742 if (isPerspective) {
743 det = mat[SkMatrix::kMScaleX] *
744 dcross(mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp2],
745 mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp1])
746 +
747 mat[SkMatrix::kMSkewX] *
748 dcross(mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp0],
749 mat[SkMatrix::kMSkewY], mat[SkMatrix::kMPersp2])
750 +
751 mat[SkMatrix::kMTransX] *
752 dcross(mat[SkMatrix::kMSkewY], mat[SkMatrix::kMPersp1],
753 mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp0]);
754 } else {
755 det = dcross(mat[SkMatrix::kMScaleX], mat[SkMatrix::kMScaleY],
756 mat[SkMatrix::kMSkewX], mat[SkMatrix::kMSkewY]);
757 }
759 // Since the determinant is on the order of the cube of the matrix members,
760 // compare to the cube of the default nearly-zero constant (although an
761 // estimate of the condition number would be better if it wasn't so expensive).
762 if (SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero * SK_ScalarNearlyZero)) {
763 return 0;
764 }
765 return 1.0 / det;
766 }
768 void SkMatrix::SetAffineIdentity(SkScalar affine[6]) {
769 affine[kAScaleX] = 1;
770 affine[kASkewY] = 0;
771 affine[kASkewX] = 0;
772 affine[kAScaleY] = 1;
773 affine[kATransX] = 0;
774 affine[kATransY] = 0;
775 }
777 bool SkMatrix::asAffine(SkScalar affine[6]) const {
778 if (this->hasPerspective()) {
779 return false;
780 }
781 if (affine) {
782 affine[kAScaleX] = this->fMat[kMScaleX];
783 affine[kASkewY] = this->fMat[kMSkewY];
784 affine[kASkewX] = this->fMat[kMSkewX];
785 affine[kAScaleY] = this->fMat[kMScaleY];
786 affine[kATransX] = this->fMat[kMTransX];
787 affine[kATransY] = this->fMat[kMTransY];
788 }
789 return true;
790 }
792 bool SkMatrix::invertNonIdentity(SkMatrix* inv) const {
793 SkASSERT(!this->isIdentity());
795 TypeMask mask = this->getType();
797 if (0 == (mask & ~(kScale_Mask | kTranslate_Mask))) {
798 bool invertible = true;
799 if (inv) {
800 if (mask & kScale_Mask) {
801 SkScalar invX = fMat[kMScaleX];
802 SkScalar invY = fMat[kMScaleY];
803 if (0 == invX || 0 == invY) {
804 return false;
805 }
806 invX = SkScalarInvert(invX);
807 invY = SkScalarInvert(invY);
809 // Must be careful when writing to inv, since it may be the
810 // same memory as this.
812 inv->fMat[kMSkewX] = inv->fMat[kMSkewY] =
813 inv->fMat[kMPersp0] = inv->fMat[kMPersp1] = 0;
815 inv->fMat[kMScaleX] = invX;
816 inv->fMat[kMScaleY] = invY;
817 inv->fMat[kMPersp2] = 1;
818 inv->fMat[kMTransX] = -fMat[kMTransX] * invX;
819 inv->fMat[kMTransY] = -fMat[kMTransY] * invY;
821 inv->setTypeMask(mask | kRectStaysRect_Mask);
822 } else {
823 // translate only
824 inv->setTranslate(-fMat[kMTransX], -fMat[kMTransY]);
825 }
826 } else { // inv is NULL, just check if we're invertible
827 if (!fMat[kMScaleX] || !fMat[kMScaleY]) {
828 invertible = false;
829 }
830 }
831 return invertible;
832 }
834 int isPersp = mask & kPerspective_Mask;
835 double scale = sk_inv_determinant(fMat, isPersp);
837 if (scale == 0) { // underflow
838 return false;
839 }
841 if (inv) {
842 SkMatrix tmp;
843 if (inv == this) {
844 inv = &tmp;
845 }
847 if (isPersp) {
848 inv->fMat[kMScaleX] = scross_dscale(fMat[kMScaleY], fMat[kMPersp2], fMat[kMTransY], fMat[kMPersp1], scale);
849 inv->fMat[kMSkewX] = scross_dscale(fMat[kMTransX], fMat[kMPersp1], fMat[kMSkewX], fMat[kMPersp2], scale);
850 inv->fMat[kMTransX] = scross_dscale(fMat[kMSkewX], fMat[kMTransY], fMat[kMTransX], fMat[kMScaleY], scale);
852 inv->fMat[kMSkewY] = scross_dscale(fMat[kMTransY], fMat[kMPersp0], fMat[kMSkewY], fMat[kMPersp2], scale);
853 inv->fMat[kMScaleY] = scross_dscale(fMat[kMScaleX], fMat[kMPersp2], fMat[kMTransX], fMat[kMPersp0], scale);
854 inv->fMat[kMTransY] = scross_dscale(fMat[kMTransX], fMat[kMSkewY], fMat[kMScaleX], fMat[kMTransY], scale);
856 inv->fMat[kMPersp0] = scross_dscale(fMat[kMSkewY], fMat[kMPersp1], fMat[kMScaleY], fMat[kMPersp0], scale);
857 inv->fMat[kMPersp1] = scross_dscale(fMat[kMSkewX], fMat[kMPersp0], fMat[kMScaleX], fMat[kMPersp1], scale);
858 inv->fMat[kMPersp2] = scross_dscale(fMat[kMScaleX], fMat[kMScaleY], fMat[kMSkewX], fMat[kMSkewY], scale);
859 } else { // not perspective
860 inv->fMat[kMScaleX] = SkDoubleToScalar(fMat[kMScaleY] * scale);
861 inv->fMat[kMSkewX] = SkDoubleToScalar(-fMat[kMSkewX] * scale);
862 inv->fMat[kMTransX] = dcross_dscale(fMat[kMSkewX], fMat[kMTransY], fMat[kMScaleY], fMat[kMTransX], scale);
864 inv->fMat[kMSkewY] = SkDoubleToScalar(-fMat[kMSkewY] * scale);
865 inv->fMat[kMScaleY] = SkDoubleToScalar(fMat[kMScaleX] * scale);
866 inv->fMat[kMTransY] = dcross_dscale(fMat[kMSkewY], fMat[kMTransX], fMat[kMScaleX], fMat[kMTransY], scale);
868 inv->fMat[kMPersp0] = 0;
869 inv->fMat[kMPersp1] = 0;
870 inv->fMat[kMPersp2] = 1;
871 }
873 inv->setTypeMask(fTypeMask);
875 if (inv == &tmp) {
876 *(SkMatrix*)this = tmp;
877 }
878 }
879 return true;
880 }
882 ///////////////////////////////////////////////////////////////////////////////
884 void SkMatrix::Identity_pts(const SkMatrix& m, SkPoint dst[],
885 const SkPoint src[], int count) {
886 SkASSERT(m.getType() == 0);
888 if (dst != src && count > 0)
889 memcpy(dst, src, count * sizeof(SkPoint));
890 }
892 void SkMatrix::Trans_pts(const SkMatrix& m, SkPoint dst[],
893 const SkPoint src[], int count) {
894 SkASSERT(m.getType() == kTranslate_Mask);
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 }
908 void SkMatrix::Scale_pts(const SkMatrix& m, SkPoint dst[],
909 const SkPoint src[], int count) {
910 SkASSERT(m.getType() == kScale_Mask);
912 if (count > 0) {
913 SkScalar mx = m.fMat[kMScaleX];
914 SkScalar my = m.fMat[kMScaleY];
915 do {
916 dst->fY = src->fY * my;
917 dst->fX = src->fX * mx;
918 src += 1;
919 dst += 1;
920 } while (--count);
921 }
922 }
924 void SkMatrix::ScaleTrans_pts(const SkMatrix& m, SkPoint dst[],
925 const SkPoint src[], int count) {
926 SkASSERT(m.getType() == (kScale_Mask | kTranslate_Mask));
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 = src->fY * my + ty;
935 dst->fX = src->fX * mx + tx;
936 src += 1;
937 dst += 1;
938 } while (--count);
939 }
940 }
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);
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 = sdot(sx, ky, sy, my);
956 dst->fX = sdot(sx, mx, sy, kx);
957 dst += 1;
958 } while (--count);
959 }
960 }
962 void SkMatrix::RotTrans_pts(const SkMatrix& m, SkPoint dst[],
963 const SkPoint src[], int count) {
964 SkASSERT(!m.hasPerspective());
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 #ifdef SK_LEGACY_MATRIX_MATH_ORDER
978 dst->fY = sx * ky + (sy * my + ty);
979 dst->fX = sx * mx + (sy * kx + tx);
980 #else
981 dst->fY = sdot(sx, ky, sy, my) + ty;
982 dst->fX = sdot(sx, mx, sy, kx) + tx;
983 #endif
984 dst += 1;
985 } while (--count);
986 }
987 }
989 void SkMatrix::Persp_pts(const SkMatrix& m, SkPoint dst[],
990 const SkPoint src[], int count) {
991 SkASSERT(m.hasPerspective());
993 if (count > 0) {
994 do {
995 SkScalar sy = src->fY;
996 SkScalar sx = src->fX;
997 src += 1;
999 SkScalar x = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1000 SkScalar y = sdot(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1001 #ifdef SK_LEGACY_MATRIX_MATH_ORDER
1002 SkScalar z = sx * m.fMat[kMPersp0] + (sy * m.fMat[kMPersp1] + m.fMat[kMPersp2]);
1003 #else
1004 SkScalar z = sdot(sx, m.fMat[kMPersp0], sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2];
1005 #endif
1006 if (z) {
1007 z = SkScalarFastInvert(z);
1008 }
1010 dst->fY = y * z;
1011 dst->fX = x * z;
1012 dst += 1;
1013 } while (--count);
1014 }
1015 }
1017 const SkMatrix::MapPtsProc SkMatrix::gMapPtsProcs[] = {
1018 SkMatrix::Identity_pts, SkMatrix::Trans_pts,
1019 SkMatrix::Scale_pts, SkMatrix::ScaleTrans_pts,
1020 SkMatrix::Rot_pts, SkMatrix::RotTrans_pts,
1021 SkMatrix::Rot_pts, SkMatrix::RotTrans_pts,
1022 // repeat the persp proc 8 times
1023 SkMatrix::Persp_pts, SkMatrix::Persp_pts,
1024 SkMatrix::Persp_pts, SkMatrix::Persp_pts,
1025 SkMatrix::Persp_pts, SkMatrix::Persp_pts,
1026 SkMatrix::Persp_pts, SkMatrix::Persp_pts
1027 };
1029 void SkMatrix::mapPoints(SkPoint dst[], const SkPoint src[], int count) const {
1030 SkASSERT((dst && src && count > 0) || 0 == count);
1031 // no partial overlap
1032 SkASSERT(src == dst || &dst[count] <= &src[0] || &src[count] <= &dst[0]);
1034 this->getMapPtsProc()(*this, dst, src, count);
1035 }
1037 ///////////////////////////////////////////////////////////////////////////////
1039 void SkMatrix::mapHomogeneousPoints(SkScalar dst[], const SkScalar src[], int count) const {
1040 SkASSERT((dst && src && count > 0) || 0 == count);
1041 // no partial overlap
1042 SkASSERT(src == dst || SkAbs32((int32_t)(src - dst)) >= 3*count);
1044 if (count > 0) {
1045 if (this->isIdentity()) {
1046 memcpy(dst, src, 3*count*sizeof(SkScalar));
1047 return;
1048 }
1049 do {
1050 SkScalar sx = src[0];
1051 SkScalar sy = src[1];
1052 SkScalar sw = src[2];
1053 src += 3;
1055 SkScalar x = sdot(sx, fMat[kMScaleX], sy, fMat[kMSkewX], sw, fMat[kMTransX]);
1056 SkScalar y = sdot(sx, fMat[kMSkewY], sy, fMat[kMScaleY], sw, fMat[kMTransY]);
1057 SkScalar w = sdot(sx, fMat[kMPersp0], sy, fMat[kMPersp1], sw, fMat[kMPersp2]);
1059 dst[0] = x;
1060 dst[1] = y;
1061 dst[2] = w;
1062 dst += 3;
1063 } while (--count);
1064 }
1065 }
1067 ///////////////////////////////////////////////////////////////////////////////
1069 void SkMatrix::mapVectors(SkPoint dst[], const SkPoint src[], int count) const {
1070 if (this->hasPerspective()) {
1071 SkPoint origin;
1073 MapXYProc proc = this->getMapXYProc();
1074 proc(*this, 0, 0, &origin);
1076 for (int i = count - 1; i >= 0; --i) {
1077 SkPoint tmp;
1079 proc(*this, src[i].fX, src[i].fY, &tmp);
1080 dst[i].set(tmp.fX - origin.fX, tmp.fY - origin.fY);
1081 }
1082 } else {
1083 SkMatrix tmp = *this;
1085 tmp.fMat[kMTransX] = tmp.fMat[kMTransY] = 0;
1086 tmp.clearTypeMask(kTranslate_Mask);
1087 tmp.mapPoints(dst, src, count);
1088 }
1089 }
1091 bool SkMatrix::mapRect(SkRect* dst, const SkRect& src) const {
1092 SkASSERT(dst && &src);
1094 if (this->rectStaysRect()) {
1095 this->mapPoints((SkPoint*)dst, (const SkPoint*)&src, 2);
1096 dst->sort();
1097 return true;
1098 } else {
1099 SkPoint quad[4];
1101 src.toQuad(quad);
1102 this->mapPoints(quad, quad, 4);
1103 dst->set(quad, 4);
1104 return false;
1105 }
1106 }
1108 SkScalar SkMatrix::mapRadius(SkScalar radius) const {
1109 SkVector vec[2];
1111 vec[0].set(radius, 0);
1112 vec[1].set(0, radius);
1113 this->mapVectors(vec, 2);
1115 SkScalar d0 = vec[0].length();
1116 SkScalar d1 = vec[1].length();
1118 // return geometric mean
1119 return SkScalarSqrt(d0 * d1);
1120 }
1122 ///////////////////////////////////////////////////////////////////////////////
1124 void SkMatrix::Persp_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1125 SkPoint* pt) {
1126 SkASSERT(m.hasPerspective());
1128 SkScalar x = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1129 SkScalar y = sdot(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1130 SkScalar z = sdot(sx, m.fMat[kMPersp0], sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2];
1131 if (z) {
1132 z = SkScalarFastInvert(z);
1133 }
1134 pt->fX = x * z;
1135 pt->fY = y * z;
1136 }
1138 void SkMatrix::RotTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1139 SkPoint* pt) {
1140 SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask)) == kAffine_Mask);
1142 #ifdef SK_LEGACY_MATRIX_MATH_ORDER
1143 pt->fX = sx * m.fMat[kMScaleX] + (sy * m.fMat[kMSkewX] + m.fMat[kMTransX]);
1144 pt->fY = sx * m.fMat[kMSkewY] + (sy * m.fMat[kMScaleY] + m.fMat[kMTransY]);
1145 #else
1146 pt->fX = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1147 pt->fY = sdot(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1148 #endif
1149 }
1151 void SkMatrix::Rot_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1152 SkPoint* pt) {
1153 SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask))== kAffine_Mask);
1154 SkASSERT(0 == m.fMat[kMTransX]);
1155 SkASSERT(0 == m.fMat[kMTransY]);
1157 #ifdef SK_LEGACY_MATRIX_MATH_ORDER
1158 pt->fX = sx * m.fMat[kMScaleX] + (sy * m.fMat[kMSkewX] + m.fMat[kMTransX]);
1159 pt->fY = sx * m.fMat[kMSkewY] + (sy * m.fMat[kMScaleY] + m.fMat[kMTransY]);
1160 #else
1161 pt->fX = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX]) + m.fMat[kMTransX];
1162 pt->fY = sdot(sx, m.fMat[kMSkewY], sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
1163 #endif
1164 }
1166 void SkMatrix::ScaleTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1167 SkPoint* pt) {
1168 SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
1169 == kScale_Mask);
1171 pt->fX = sx * m.fMat[kMScaleX] + m.fMat[kMTransX];
1172 pt->fY = sy * m.fMat[kMScaleY] + m.fMat[kMTransY];
1173 }
1175 void SkMatrix::Scale_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1176 SkPoint* pt) {
1177 SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
1178 == kScale_Mask);
1179 SkASSERT(0 == m.fMat[kMTransX]);
1180 SkASSERT(0 == m.fMat[kMTransY]);
1182 pt->fX = sx * m.fMat[kMScaleX];
1183 pt->fY = sy * m.fMat[kMScaleY];
1184 }
1186 void SkMatrix::Trans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1187 SkPoint* pt) {
1188 SkASSERT(m.getType() == kTranslate_Mask);
1190 pt->fX = sx + m.fMat[kMTransX];
1191 pt->fY = sy + m.fMat[kMTransY];
1192 }
1194 void SkMatrix::Identity_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
1195 SkPoint* pt) {
1196 SkASSERT(0 == m.getType());
1198 pt->fX = sx;
1199 pt->fY = sy;
1200 }
1202 const SkMatrix::MapXYProc SkMatrix::gMapXYProcs[] = {
1203 SkMatrix::Identity_xy, SkMatrix::Trans_xy,
1204 SkMatrix::Scale_xy, SkMatrix::ScaleTrans_xy,
1205 SkMatrix::Rot_xy, SkMatrix::RotTrans_xy,
1206 SkMatrix::Rot_xy, SkMatrix::RotTrans_xy,
1207 // repeat the persp proc 8 times
1208 SkMatrix::Persp_xy, SkMatrix::Persp_xy,
1209 SkMatrix::Persp_xy, SkMatrix::Persp_xy,
1210 SkMatrix::Persp_xy, SkMatrix::Persp_xy,
1211 SkMatrix::Persp_xy, SkMatrix::Persp_xy
1212 };
1214 ///////////////////////////////////////////////////////////////////////////////
1216 // if its nearly zero (just made up 26, perhaps it should be bigger or smaller)
1217 #define PerspNearlyZero(x) SkScalarNearlyZero(x, (1.0f / (1 << 26)))
1219 bool SkMatrix::fixedStepInX(SkScalar y, SkFixed* stepX, SkFixed* stepY) const {
1220 if (PerspNearlyZero(fMat[kMPersp0])) {
1221 if (stepX || stepY) {
1222 if (PerspNearlyZero(fMat[kMPersp1]) &&
1223 PerspNearlyZero(fMat[kMPersp2] - 1)) {
1224 if (stepX) {
1225 *stepX = SkScalarToFixed(fMat[kMScaleX]);
1226 }
1227 if (stepY) {
1228 *stepY = SkScalarToFixed(fMat[kMSkewY]);
1229 }
1230 } else {
1231 SkScalar z = y * fMat[kMPersp1] + fMat[kMPersp2];
1232 if (stepX) {
1233 *stepX = SkScalarToFixed(fMat[kMScaleX] / z);
1234 }
1235 if (stepY) {
1236 *stepY = SkScalarToFixed(fMat[kMSkewY] / z);
1237 }
1238 }
1239 }
1240 return true;
1241 }
1242 return false;
1243 }
1245 ///////////////////////////////////////////////////////////////////////////////
1247 #include "SkPerspIter.h"
1249 SkPerspIter::SkPerspIter(const SkMatrix& m, SkScalar x0, SkScalar y0, int count)
1250 : fMatrix(m), fSX(x0), fSY(y0), fCount(count) {
1251 SkPoint pt;
1253 SkMatrix::Persp_xy(m, x0, y0, &pt);
1254 fX = SkScalarToFixed(pt.fX);
1255 fY = SkScalarToFixed(pt.fY);
1256 }
1258 int SkPerspIter::next() {
1259 int n = fCount;
1261 if (0 == n) {
1262 return 0;
1263 }
1264 SkPoint pt;
1265 SkFixed x = fX;
1266 SkFixed y = fY;
1267 SkFixed dx, dy;
1269 if (n >= kCount) {
1270 n = kCount;
1271 fSX += SkIntToScalar(kCount);
1272 SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
1273 fX = SkScalarToFixed(pt.fX);
1274 fY = SkScalarToFixed(pt.fY);
1275 dx = (fX - x) >> kShift;
1276 dy = (fY - y) >> kShift;
1277 } else {
1278 fSX += SkIntToScalar(n);
1279 SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
1280 fX = SkScalarToFixed(pt.fX);
1281 fY = SkScalarToFixed(pt.fY);
1282 dx = (fX - x) / n;
1283 dy = (fY - y) / n;
1284 }
1286 SkFixed* p = fStorage;
1287 for (int i = 0; i < n; i++) {
1288 *p++ = x; x += dx;
1289 *p++ = y; y += dy;
1290 }
1292 fCount -= n;
1293 return n;
1294 }
1296 ///////////////////////////////////////////////////////////////////////////////
1298 static inline bool checkForZero(float x) {
1299 return x*x == 0;
1300 }
1302 static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) {
1303 float x = 1, y = 1;
1304 SkPoint pt1, pt2;
1306 if (count > 1) {
1307 pt1.fX = poly[1].fX - poly[0].fX;
1308 pt1.fY = poly[1].fY - poly[0].fY;
1309 y = SkPoint::Length(pt1.fX, pt1.fY);
1310 if (checkForZero(y)) {
1311 return false;
1312 }
1313 switch (count) {
1314 case 2:
1315 break;
1316 case 3:
1317 pt2.fX = poly[0].fY - poly[2].fY;
1318 pt2.fY = poly[2].fX - poly[0].fX;
1319 goto CALC_X;
1320 default:
1321 pt2.fX = poly[0].fY - poly[3].fY;
1322 pt2.fY = poly[3].fX - poly[0].fX;
1323 CALC_X:
1324 x = sdot(pt1.fX, pt2.fX, pt1.fY, pt2.fY) / y;
1325 break;
1326 }
1327 }
1328 pt->set(x, y);
1329 return true;
1330 }
1332 bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst,
1333 const SkPoint& scale) {
1334 float invScale = 1 / scale.fY;
1336 dst->fMat[kMScaleX] = (srcPt[1].fY - srcPt[0].fY) * invScale;
1337 dst->fMat[kMSkewY] = (srcPt[0].fX - srcPt[1].fX) * invScale;
1338 dst->fMat[kMPersp0] = 0;
1339 dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
1340 dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
1341 dst->fMat[kMPersp1] = 0;
1342 dst->fMat[kMTransX] = srcPt[0].fX;
1343 dst->fMat[kMTransY] = srcPt[0].fY;
1344 dst->fMat[kMPersp2] = 1;
1345 dst->setTypeMask(kUnknown_Mask);
1346 return true;
1347 }
1349 bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst,
1350 const SkPoint& scale) {
1351 float invScale = 1 / scale.fX;
1352 dst->fMat[kMScaleX] = (srcPt[2].fX - srcPt[0].fX) * invScale;
1353 dst->fMat[kMSkewY] = (srcPt[2].fY - srcPt[0].fY) * invScale;
1354 dst->fMat[kMPersp0] = 0;
1356 invScale = 1 / scale.fY;
1357 dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
1358 dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
1359 dst->fMat[kMPersp1] = 0;
1361 dst->fMat[kMTransX] = srcPt[0].fX;
1362 dst->fMat[kMTransY] = srcPt[0].fY;
1363 dst->fMat[kMPersp2] = 1;
1364 dst->setTypeMask(kUnknown_Mask);
1365 return true;
1366 }
1368 bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst,
1369 const SkPoint& scale) {
1370 float a1, a2;
1371 float x0, y0, x1, y1, x2, y2;
1373 x0 = srcPt[2].fX - srcPt[0].fX;
1374 y0 = srcPt[2].fY - srcPt[0].fY;
1375 x1 = srcPt[2].fX - srcPt[1].fX;
1376 y1 = srcPt[2].fY - srcPt[1].fY;
1377 x2 = srcPt[2].fX - srcPt[3].fX;
1378 y2 = srcPt[2].fY - srcPt[3].fY;
1380 /* check if abs(x2) > abs(y2) */
1381 if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) {
1382 float denom = SkScalarMulDiv(x1, y2, x2) - y1;
1383 if (checkForZero(denom)) {
1384 return false;
1385 }
1386 a1 = (SkScalarMulDiv(x0 - x1, y2, x2) - y0 + y1) / denom;
1387 } else {
1388 float denom = x1 - SkScalarMulDiv(y1, x2, y2);
1389 if (checkForZero(denom)) {
1390 return false;
1391 }
1392 a1 = (x0 - x1 - SkScalarMulDiv(y0 - y1, x2, y2)) / denom;
1393 }
1395 /* check if abs(x1) > abs(y1) */
1396 if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) {
1397 float denom = y2 - SkScalarMulDiv(x2, y1, x1);
1398 if (checkForZero(denom)) {
1399 return false;
1400 }
1401 a2 = (y0 - y2 - SkScalarMulDiv(x0 - x2, y1, x1)) / denom;
1402 } else {
1403 float denom = SkScalarMulDiv(y2, x1, y1) - x2;
1404 if (checkForZero(denom)) {
1405 return false;
1406 }
1407 a2 = (SkScalarMulDiv(y0 - y2, x1, y1) - x0 + x2) / denom;
1408 }
1410 float invScale = SkScalarInvert(scale.fX);
1411 dst->fMat[kMScaleX] = (a2 * srcPt[3].fX + srcPt[3].fX - srcPt[0].fX) * invScale;
1412 dst->fMat[kMSkewY] = (a2 * srcPt[3].fY + srcPt[3].fY - srcPt[0].fY) * invScale;
1413 dst->fMat[kMPersp0] = a2 * invScale;
1415 invScale = SkScalarInvert(scale.fY);
1416 dst->fMat[kMSkewX] = (a1 * srcPt[1].fX + srcPt[1].fX - srcPt[0].fX) * invScale;
1417 dst->fMat[kMScaleY] = (a1 * srcPt[1].fY + srcPt[1].fY - srcPt[0].fY) * invScale;
1418 dst->fMat[kMPersp1] = a1 * invScale;
1420 dst->fMat[kMTransX] = srcPt[0].fX;
1421 dst->fMat[kMTransY] = srcPt[0].fY;
1422 dst->fMat[kMPersp2] = 1;
1423 dst->setTypeMask(kUnknown_Mask);
1424 return true;
1425 }
1427 typedef bool (*PolyMapProc)(const SkPoint[], SkMatrix*, const SkPoint&);
1429 /* Taken from Rob Johnson's original sample code in QuickDraw GX
1430 */
1431 bool SkMatrix::setPolyToPoly(const SkPoint src[], const SkPoint dst[],
1432 int count) {
1433 if ((unsigned)count > 4) {
1434 SkDebugf("--- SkMatrix::setPolyToPoly count out of range %d\n", count);
1435 return false;
1436 }
1438 if (0 == count) {
1439 this->reset();
1440 return true;
1441 }
1442 if (1 == count) {
1443 this->setTranslate(dst[0].fX - src[0].fX, dst[0].fY - src[0].fY);
1444 return true;
1445 }
1447 SkPoint scale;
1448 if (!poly_to_point(&scale, src, count) ||
1449 SkScalarNearlyZero(scale.fX) ||
1450 SkScalarNearlyZero(scale.fY)) {
1451 return false;
1452 }
1454 static const PolyMapProc gPolyMapProcs[] = {
1455 SkMatrix::Poly2Proc, SkMatrix::Poly3Proc, SkMatrix::Poly4Proc
1456 };
1457 PolyMapProc proc = gPolyMapProcs[count - 2];
1459 SkMatrix tempMap, result;
1460 tempMap.setTypeMask(kUnknown_Mask);
1462 if (!proc(src, &tempMap, scale)) {
1463 return false;
1464 }
1465 if (!tempMap.invert(&result)) {
1466 return false;
1467 }
1468 if (!proc(dst, &tempMap, scale)) {
1469 return false;
1470 }
1471 if (!result.setConcat(tempMap, result)) {
1472 return false;
1473 }
1474 *this = result;
1475 return true;
1476 }
1478 ///////////////////////////////////////////////////////////////////////////////
1480 enum MinOrMax {
1481 kMin_MinOrMax,
1482 kMax_MinOrMax
1483 };
1485 template <MinOrMax MIN_OR_MAX> SkScalar get_stretch_factor(SkMatrix::TypeMask typeMask,
1486 const SkScalar m[9]) {
1487 if (typeMask & SkMatrix::kPerspective_Mask) {
1488 return -1;
1489 }
1490 if (SkMatrix::kIdentity_Mask == typeMask) {
1491 return 1;
1492 }
1493 if (!(typeMask & SkMatrix::kAffine_Mask)) {
1494 if (kMin_MinOrMax == MIN_OR_MAX) {
1495 return SkMinScalar(SkScalarAbs(m[SkMatrix::kMScaleX]),
1496 SkScalarAbs(m[SkMatrix::kMScaleY]));
1497 } else {
1498 return SkMaxScalar(SkScalarAbs(m[SkMatrix::kMScaleX]),
1499 SkScalarAbs(m[SkMatrix::kMScaleY]));
1500 }
1501 }
1502 // ignore the translation part of the matrix, just look at 2x2 portion.
1503 // compute singular values, take largest or smallest abs value.
1504 // [a b; b c] = A^T*A
1505 SkScalar a = sdot(m[SkMatrix::kMScaleX], m[SkMatrix::kMScaleX],
1506 m[SkMatrix::kMSkewY], m[SkMatrix::kMSkewY]);
1507 SkScalar b = sdot(m[SkMatrix::kMScaleX], m[SkMatrix::kMSkewX],
1508 m[SkMatrix::kMScaleY], m[SkMatrix::kMSkewY]);
1509 SkScalar c = sdot(m[SkMatrix::kMSkewX], m[SkMatrix::kMSkewX],
1510 m[SkMatrix::kMScaleY], m[SkMatrix::kMScaleY]);
1511 // eigenvalues of A^T*A are the squared singular values of A.
1512 // characteristic equation is det((A^T*A) - l*I) = 0
1513 // l^2 - (a + c)l + (ac-b^2)
1514 // solve using quadratic equation (divisor is non-zero since l^2 has 1 coeff
1515 // and roots are guaranteed to be pos and real).
1516 SkScalar chosenRoot;
1517 SkScalar bSqd = b * b;
1518 // if upper left 2x2 is orthogonal save some math
1519 if (bSqd <= SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
1520 if (kMin_MinOrMax == MIN_OR_MAX) {
1521 chosenRoot = SkMinScalar(a, c);
1522 } else {
1523 chosenRoot = SkMaxScalar(a, c);
1524 }
1525 } else {
1526 SkScalar aminusc = a - c;
1527 SkScalar apluscdiv2 = SkScalarHalf(a + c);
1528 SkScalar x = SkScalarHalf(SkScalarSqrt(aminusc * aminusc + 4 * bSqd));
1529 if (kMin_MinOrMax == MIN_OR_MAX) {
1530 chosenRoot = apluscdiv2 - x;
1531 } else {
1532 chosenRoot = apluscdiv2 + x;
1533 }
1534 }
1535 SkASSERT(chosenRoot >= 0);
1536 return SkScalarSqrt(chosenRoot);
1537 }
1539 SkScalar SkMatrix::getMinStretch() const {
1540 return get_stretch_factor<kMin_MinOrMax>(this->getType(), fMat);
1541 }
1543 SkScalar SkMatrix::getMaxStretch() const {
1544 return get_stretch_factor<kMax_MinOrMax>(this->getType(), fMat);
1545 }
1547 static void reset_identity_matrix(SkMatrix* identity) {
1548 identity->reset();
1549 }
1551 const SkMatrix& SkMatrix::I() {
1552 // If you can use C++11 now, you might consider replacing this with a constexpr constructor.
1553 static SkMatrix gIdentity;
1554 SK_DECLARE_STATIC_ONCE(once);
1555 SkOnce(&once, reset_identity_matrix, &gIdentity);
1556 return gIdentity;
1557 }
1559 const SkMatrix& SkMatrix::InvalidMatrix() {
1560 static SkMatrix gInvalid;
1561 static bool gOnce;
1562 if (!gOnce) {
1563 gInvalid.setAll(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax,
1564 SK_ScalarMax, SK_ScalarMax, SK_ScalarMax,
1565 SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
1566 gInvalid.getType(); // force the type to be computed
1567 gOnce = true;
1568 }
1569 return gInvalid;
1570 }
1572 ///////////////////////////////////////////////////////////////////////////////
1574 size_t SkMatrix::writeToMemory(void* buffer) const {
1575 // TODO write less for simple matrices
1576 static const size_t sizeInMemory = 9 * sizeof(SkScalar);
1577 if (buffer) {
1578 memcpy(buffer, fMat, sizeInMemory);
1579 }
1580 return sizeInMemory;
1581 }
1583 size_t SkMatrix::readFromMemory(const void* buffer, size_t length) {
1584 static const size_t sizeInMemory = 9 * sizeof(SkScalar);
1585 if (length < sizeInMemory) {
1586 return 0;
1587 }
1588 if (buffer) {
1589 memcpy(fMat, buffer, sizeInMemory);
1590 this->setTypeMask(kUnknown_Mask);
1591 }
1592 return sizeInMemory;
1593 }
1595 #ifdef SK_DEVELOPER
1596 void SkMatrix::dump() const {
1597 SkString str;
1598 this->toString(&str);
1599 SkDebugf("%s\n", str.c_str());
1600 }
1601 #endif
1603 #ifndef SK_IGNORE_TO_STRING
1604 void SkMatrix::toString(SkString* str) const {
1605 str->appendf("[%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f]",
1606 fMat[0], fMat[1], fMat[2], fMat[3], fMat[4], fMat[5],
1607 fMat[6], fMat[7], fMat[8]);
1608 }
1609 #endif
1611 ///////////////////////////////////////////////////////////////////////////////
1613 #include "SkMatrixUtils.h"
1615 bool SkTreatAsSprite(const SkMatrix& mat, int width, int height,
1616 unsigned subpixelBits) {
1617 // quick reject on affine or perspective
1618 if (mat.getType() & ~(SkMatrix::kScale_Mask | SkMatrix::kTranslate_Mask)) {
1619 return false;
1620 }
1622 // quick success check
1623 if (!subpixelBits && !(mat.getType() & ~SkMatrix::kTranslate_Mask)) {
1624 return true;
1625 }
1627 // mapRect supports negative scales, so we eliminate those first
1628 if (mat.getScaleX() < 0 || mat.getScaleY() < 0) {
1629 return false;
1630 }
1632 SkRect dst;
1633 SkIRect isrc = { 0, 0, width, height };
1635 {
1636 SkRect src;
1637 src.set(isrc);
1638 mat.mapRect(&dst, src);
1639 }
1641 // just apply the translate to isrc
1642 isrc.offset(SkScalarRoundToInt(mat.getTranslateX()),
1643 SkScalarRoundToInt(mat.getTranslateY()));
1645 if (subpixelBits) {
1646 isrc.fLeft <<= subpixelBits;
1647 isrc.fTop <<= subpixelBits;
1648 isrc.fRight <<= subpixelBits;
1649 isrc.fBottom <<= subpixelBits;
1651 const float scale = 1 << subpixelBits;
1652 dst.fLeft *= scale;
1653 dst.fTop *= scale;
1654 dst.fRight *= scale;
1655 dst.fBottom *= scale;
1656 }
1658 SkIRect idst;
1659 dst.round(&idst);
1660 return isrc == idst;
1661 }
1663 // A square matrix M can be decomposed (via polar decomposition) into two matrices --
1664 // an orthogonal matrix Q and a symmetric matrix S. In turn we can decompose S into U*W*U^T,
1665 // where U is another orthogonal matrix and W is a scale matrix. These can be recombined
1666 // to give M = (Q*U)*W*U^T, i.e., the product of two orthogonal matrices and a scale matrix.
1667 //
1668 // The one wrinkle is that traditionally Q may contain a reflection -- the
1669 // calculation has been rejiggered to put that reflection into W.
1670 bool SkDecomposeUpper2x2(const SkMatrix& matrix,
1671 SkPoint* rotation1,
1672 SkPoint* scale,
1673 SkPoint* rotation2) {
1675 SkScalar A = matrix[SkMatrix::kMScaleX];
1676 SkScalar B = matrix[SkMatrix::kMSkewX];
1677 SkScalar C = matrix[SkMatrix::kMSkewY];
1678 SkScalar D = matrix[SkMatrix::kMScaleY];
1680 if (is_degenerate_2x2(A, B, C, D)) {
1681 return false;
1682 }
1684 double w1, w2;
1685 SkScalar cos1, sin1;
1686 SkScalar cos2, sin2;
1688 // do polar decomposition (M = Q*S)
1689 SkScalar cosQ, sinQ;
1690 double Sa, Sb, Sd;
1691 // if M is already symmetric (i.e., M = I*S)
1692 if (SkScalarNearlyEqual(B, C)) {
1693 cosQ = 1;
1694 sinQ = 0;
1696 Sa = A;
1697 Sb = B;
1698 Sd = D;
1699 } else {
1700 cosQ = A + D;
1701 sinQ = C - B;
1702 SkScalar reciplen = SkScalarInvert(SkScalarSqrt(cosQ*cosQ + sinQ*sinQ));
1703 cosQ *= reciplen;
1704 sinQ *= reciplen;
1706 // S = Q^-1*M
1707 // we don't calc Sc since it's symmetric
1708 Sa = A*cosQ + C*sinQ;
1709 Sb = B*cosQ + D*sinQ;
1710 Sd = -B*sinQ + D*cosQ;
1711 }
1713 // Now we need to compute eigenvalues of S (our scale factors)
1714 // and eigenvectors (bases for our rotation)
1715 // From this, should be able to reconstruct S as U*W*U^T
1716 if (SkScalarNearlyZero(SkDoubleToScalar(Sb))) {
1717 // already diagonalized
1718 cos1 = 1;
1719 sin1 = 0;
1720 w1 = Sa;
1721 w2 = Sd;
1722 cos2 = cosQ;
1723 sin2 = sinQ;
1724 } else {
1725 double diff = Sa - Sd;
1726 double discriminant = sqrt(diff*diff + 4.0*Sb*Sb);
1727 double trace = Sa + Sd;
1728 if (diff > 0) {
1729 w1 = 0.5*(trace + discriminant);
1730 w2 = 0.5*(trace - discriminant);
1731 } else {
1732 w1 = 0.5*(trace - discriminant);
1733 w2 = 0.5*(trace + discriminant);
1734 }
1736 cos1 = SkDoubleToScalar(Sb); sin1 = SkDoubleToScalar(w1 - Sa);
1737 SkScalar reciplen = SkScalarInvert(SkScalarSqrt(cos1*cos1 + sin1*sin1));
1738 cos1 *= reciplen;
1739 sin1 *= reciplen;
1741 // rotation 2 is composition of Q and U
1742 cos2 = cos1*cosQ - sin1*sinQ;
1743 sin2 = sin1*cosQ + cos1*sinQ;
1745 // rotation 1 is U^T
1746 sin1 = -sin1;
1747 }
1749 if (NULL != scale) {
1750 scale->fX = SkDoubleToScalar(w1);
1751 scale->fY = SkDoubleToScalar(w2);
1752 }
1753 if (NULL != rotation1) {
1754 rotation1->fX = cos1;
1755 rotation1->fY = sin1;
1756 }
1757 if (NULL != rotation2) {
1758 rotation2->fX = cos2;
1759 rotation2->fY = sin2;
1760 }
1762 return true;
1763 }
