michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "SkMatrix.h"
michael@0: #include "SkFloatBits.h"
michael@0: #include "SkOnce.h"
michael@0: #include "SkString.h"
michael@0: 
michael@0: // In a few places, we performed the following
michael@0: //      a * b + c * d + e
michael@0: // as
michael@0: //      a * b + (c * d + e)
michael@0: //
michael@0: // sdot and scross are indended to capture these compound operations into a
michael@0: // function, with an eye toward considering upscaling the intermediates to
michael@0: // doubles for more precision (as we do in concat and invert).
michael@0: //
michael@0: // However, these few lines that performed the last add before the "dot", cause
michael@0: // tiny image differences, so we guard that change until we see the impact on
michael@0: // chrome's layouttests.
michael@0: //
michael@0: #define SK_LEGACY_MATRIX_MATH_ORDER
michael@0: 
michael@0: static inline float SkDoubleToFloat(double x) {
michael@0:     return static_cast<float>(x);
michael@0: }
michael@0: 
michael@0: /*      [scale-x    skew-x      trans-x]   [X]   [X']
michael@0:         [skew-y     scale-y     trans-y] * [Y] = [Y']
michael@0:         [persp-0    persp-1     persp-2]   [1]   [1 ]
michael@0: */
michael@0: 
michael@0: void SkMatrix::reset() {
michael@0:     fMat[kMScaleX] = fMat[kMScaleY] = fMat[kMPersp2] = 1;
michael@0:     fMat[kMSkewX]  = fMat[kMSkewY] =
michael@0:     fMat[kMTransX] = fMat[kMTransY] =
michael@0:     fMat[kMPersp0] = fMat[kMPersp1] = 0;
michael@0: 
michael@0:     this->setTypeMask(kIdentity_Mask | kRectStaysRect_Mask);
michael@0: }
michael@0: 
michael@0: // this guy aligns with the masks, so we can compute a mask from a varaible 0/1
michael@0: enum {
michael@0:     kTranslate_Shift,
michael@0:     kScale_Shift,
michael@0:     kAffine_Shift,
michael@0:     kPerspective_Shift,
michael@0:     kRectStaysRect_Shift
michael@0: };
michael@0: 
michael@0: static const int32_t kScalar1Int = 0x3f800000;
michael@0: 
michael@0: uint8_t SkMatrix::computePerspectiveTypeMask() const {
michael@0:     // Benchmarking suggests that replacing this set of SkScalarAs2sCompliment
michael@0:     // is a win, but replacing those below is not. We don't yet understand
michael@0:     // that result.
michael@0:     if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 || fMat[kMPersp2] != 1) {
michael@0:         // If this is a perspective transform, we return true for all other
michael@0:         // transform flags - this does not disable any optimizations, respects
michael@0:         // the rule that the type mask must be conservative, and speeds up
michael@0:         // type mask computation.
michael@0:         return SkToU8(kORableMasks);
michael@0:     }
michael@0: 
michael@0:     return SkToU8(kOnlyPerspectiveValid_Mask | kUnknown_Mask);
michael@0: }
michael@0: 
michael@0: uint8_t SkMatrix::computeTypeMask() const {
michael@0:     unsigned mask = 0;
michael@0: 
michael@0:     if (fMat[kMPersp0] != 0 || fMat[kMPersp1] != 0 || fMat[kMPersp2] != 1) {
michael@0:         // Once it is determined that that this is a perspective transform,
michael@0:         // all other flags are moot as far as optimizations are concerned.
michael@0:         return SkToU8(kORableMasks);
michael@0:     }
michael@0: 
michael@0:     if (fMat[kMTransX] != 0 || fMat[kMTransY] != 0) {
michael@0:         mask |= kTranslate_Mask;
michael@0:     }
michael@0: 
michael@0:     int m00 = SkScalarAs2sCompliment(fMat[SkMatrix::kMScaleX]);
michael@0:     int m01 = SkScalarAs2sCompliment(fMat[SkMatrix::kMSkewX]);
michael@0:     int m10 = SkScalarAs2sCompliment(fMat[SkMatrix::kMSkewY]);
michael@0:     int m11 = SkScalarAs2sCompliment(fMat[SkMatrix::kMScaleY]);
michael@0: 
michael@0:     if (m01 | m10) {
michael@0:         // The skew components may be scale-inducing, unless we are dealing
michael@0:         // with a pure rotation.  Testing for a pure rotation is expensive,
michael@0:         // so we opt for being conservative by always setting the scale bit.
michael@0:         // along with affine.
michael@0:         // By doing this, we are also ensuring that matrices have the same
michael@0:         // type masks as their inverses.
michael@0:         mask |= kAffine_Mask | kScale_Mask;
michael@0: 
michael@0:         // For rectStaysRect, in the affine case, we only need check that
michael@0:         // the primary diagonal is all zeros and that the secondary diagonal
michael@0:         // is all non-zero.
michael@0: 
michael@0:         // map non-zero to 1
michael@0:         m01 = m01 != 0;
michael@0:         m10 = m10 != 0;
michael@0: 
michael@0:         int dp0 = 0 == (m00 | m11) ;  // true if both are 0
michael@0:         int ds1 = m01 & m10;        // true if both are 1
michael@0: 
michael@0:         mask |= (dp0 & ds1) << kRectStaysRect_Shift;
michael@0:     } else {
michael@0:         // Only test for scale explicitly if not affine, since affine sets the
michael@0:         // scale bit.
michael@0:         if ((m00 - kScalar1Int) | (m11 - kScalar1Int)) {
michael@0:             mask |= kScale_Mask;
michael@0:         }
michael@0: 
michael@0:         // Not affine, therefore we already know secondary diagonal is
michael@0:         // all zeros, so we just need to check that primary diagonal is
michael@0:         // all non-zero.
michael@0: 
michael@0:         // map non-zero to 1
michael@0:         m00 = m00 != 0;
michael@0:         m11 = m11 != 0;
michael@0: 
michael@0:         // record if the (p)rimary diagonal is all non-zero
michael@0:         mask |= (m00 & m11) << kRectStaysRect_Shift;
michael@0:     }
michael@0: 
michael@0:     return SkToU8(mask);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: bool operator==(const SkMatrix& a, const SkMatrix& b) {
michael@0:     const SkScalar* SK_RESTRICT ma = a.fMat;
michael@0:     const SkScalar* SK_RESTRICT mb = b.fMat;
michael@0: 
michael@0:     return  ma[0] == mb[0] && ma[1] == mb[1] && ma[2] == mb[2] &&
michael@0:             ma[3] == mb[3] && ma[4] == mb[4] && ma[5] == mb[5] &&
michael@0:             ma[6] == mb[6] && ma[7] == mb[7] && ma[8] == mb[8];
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: // helper function to determine if upper-left 2x2 of matrix is degenerate
michael@0: static inline bool is_degenerate_2x2(SkScalar scaleX, SkScalar skewX,
michael@0:                                      SkScalar skewY,  SkScalar scaleY) {
michael@0:     SkScalar perp_dot = scaleX*scaleY - skewX*skewY;
michael@0:     return SkScalarNearlyZero(perp_dot, SK_ScalarNearlyZero*SK_ScalarNearlyZero);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: bool SkMatrix::isSimilarity(SkScalar tol) const {
michael@0:     // if identity or translate matrix
michael@0:     TypeMask mask = this->getType();
michael@0:     if (mask <= kTranslate_Mask) {
michael@0:         return true;
michael@0:     }
michael@0:     if (mask & kPerspective_Mask) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     SkScalar mx = fMat[kMScaleX];
michael@0:     SkScalar my = fMat[kMScaleY];
michael@0:     // if no skew, can just compare scale factors
michael@0:     if (!(mask & kAffine_Mask)) {
michael@0:         return !SkScalarNearlyZero(mx) && SkScalarNearlyEqual(SkScalarAbs(mx), SkScalarAbs(my));
michael@0:     }
michael@0:     SkScalar sx = fMat[kMSkewX];
michael@0:     SkScalar sy = fMat[kMSkewY];
michael@0: 
michael@0:     if (is_degenerate_2x2(mx, sx, sy, my)) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     // it has scales and skews, but it could also be rotation, check it out.
michael@0:     SkVector vec[2];
michael@0:     vec[0].set(mx, sx);
michael@0:     vec[1].set(sy, my);
michael@0: 
michael@0:     return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) &&
michael@0:            SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(),
michael@0:                                SkScalarSquare(tol));
michael@0: }
michael@0: 
michael@0: bool SkMatrix::preservesRightAngles(SkScalar tol) const {
michael@0:     TypeMask mask = this->getType();
michael@0: 
michael@0:     if (mask <= (SkMatrix::kTranslate_Mask | SkMatrix::kScale_Mask)) {
michael@0:         // identity, translate and/or scale
michael@0:         return true;
michael@0:     }
michael@0:     if (mask & kPerspective_Mask) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     SkASSERT(mask & kAffine_Mask);
michael@0: 
michael@0:     SkScalar mx = fMat[kMScaleX];
michael@0:     SkScalar my = fMat[kMScaleY];
michael@0:     SkScalar sx = fMat[kMSkewX];
michael@0:     SkScalar sy = fMat[kMSkewY];
michael@0: 
michael@0:     if (is_degenerate_2x2(mx, sx, sy, my)) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     // it has scales and skews, but it could also be rotation, check it out.
michael@0:     SkVector vec[2];
michael@0:     vec[0].set(mx, sx);
michael@0:     vec[1].set(sy, my);
michael@0: 
michael@0:     return SkScalarNearlyZero(vec[0].dot(vec[1]), SkScalarSquare(tol)) &&
michael@0:            SkScalarNearlyEqual(vec[0].lengthSqd(), vec[1].lengthSqd(),
michael@0:                                SkScalarSquare(tol));
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static inline SkScalar sdot(SkScalar a, SkScalar b, SkScalar c, SkScalar d) {
michael@0:     return a * b + c * d;
michael@0: }
michael@0: 
michael@0: static inline SkScalar sdot(SkScalar a, SkScalar b, SkScalar c, SkScalar d,
michael@0:                              SkScalar e, SkScalar f) {
michael@0:     return a * b + c * d + e * f;
michael@0: }
michael@0: 
michael@0: static inline SkScalar scross(SkScalar a, SkScalar b, SkScalar c, SkScalar d) {
michael@0:     return a * b - c * d;
michael@0: }
michael@0: 
michael@0: void SkMatrix::setTranslate(SkScalar dx, SkScalar dy) {
michael@0:     if (dx || dy) {
michael@0:         fMat[kMTransX] = dx;
michael@0:         fMat[kMTransY] = dy;
michael@0: 
michael@0:         fMat[kMScaleX] = fMat[kMScaleY] = fMat[kMPersp2] = 1;
michael@0:         fMat[kMSkewX]  = fMat[kMSkewY] =
michael@0:         fMat[kMPersp0] = fMat[kMPersp1] = 0;
michael@0: 
michael@0:         this->setTypeMask(kTranslate_Mask | kRectStaysRect_Mask);
michael@0:     } else {
michael@0:         this->reset();
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool SkMatrix::preTranslate(SkScalar dx, SkScalar dy) {
michael@0:     if (this->hasPerspective()) {
michael@0:         SkMatrix    m;
michael@0:         m.setTranslate(dx, dy);
michael@0:         return this->preConcat(m);
michael@0:     }
michael@0: 
michael@0:     if (dx || dy) {
michael@0:         fMat[kMTransX] += sdot(fMat[kMScaleX], dx, fMat[kMSkewX], dy);
michael@0:         fMat[kMTransY] += sdot(fMat[kMSkewY], dx, fMat[kMScaleY], dy);
michael@0: 
michael@0:         this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkMatrix::postTranslate(SkScalar dx, SkScalar dy) {
michael@0:     if (this->hasPerspective()) {
michael@0:         SkMatrix    m;
michael@0:         m.setTranslate(dx, dy);
michael@0:         return this->postConcat(m);
michael@0:     }
michael@0: 
michael@0:     if (dx || dy) {
michael@0:         fMat[kMTransX] += dx;
michael@0:         fMat[kMTransY] += dy;
michael@0:         this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: void SkMatrix::setScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
michael@0:     if (1 == sx && 1 == sy) {
michael@0:         this->reset();
michael@0:     } else {
michael@0:         fMat[kMScaleX] = sx;
michael@0:         fMat[kMScaleY] = sy;
michael@0:         fMat[kMTransX] = px - sx * px;
michael@0:         fMat[kMTransY] = py - sy * py;
michael@0:         fMat[kMPersp2] = 1;
michael@0: 
michael@0:         fMat[kMSkewX]  = fMat[kMSkewY] =
michael@0:         fMat[kMPersp0] = fMat[kMPersp1] = 0;
michael@0: 
michael@0:         this->setTypeMask(kScale_Mask | kTranslate_Mask | kRectStaysRect_Mask);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkMatrix::setScale(SkScalar sx, SkScalar sy) {
michael@0:     if (1 == sx && 1 == sy) {
michael@0:         this->reset();
michael@0:     } else {
michael@0:         fMat[kMScaleX] = sx;
michael@0:         fMat[kMScaleY] = sy;
michael@0:         fMat[kMPersp2] = 1;
michael@0: 
michael@0:         fMat[kMTransX] = fMat[kMTransY] =
michael@0:         fMat[kMSkewX]  = fMat[kMSkewY] =
michael@0:         fMat[kMPersp0] = fMat[kMPersp1] = 0;
michael@0: 
michael@0:         this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool SkMatrix::setIDiv(int divx, int divy) {
michael@0:     if (!divx || !divy) {
michael@0:         return false;
michael@0:     }
michael@0:     this->setScale(SkScalarInvert(divx), SkScalarInvert(divy));
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkMatrix::preScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
michael@0:     SkMatrix    m;
michael@0:     m.setScale(sx, sy, px, py);
michael@0:     return this->preConcat(m);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::preScale(SkScalar sx, SkScalar sy) {
michael@0:     if (1 == sx && 1 == sy) {
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // the assumption is that these multiplies are very cheap, and that
michael@0:     // a full concat and/or just computing the matrix type is more expensive.
michael@0:     // Also, the fixed-point case checks for overflow, but the float doesn't,
michael@0:     // so we can get away with these blind multiplies.
michael@0: 
michael@0:     fMat[kMScaleX] *= sx;
michael@0:     fMat[kMSkewY]  *= sx;
michael@0:     fMat[kMPersp0] *= sx;
michael@0: 
michael@0:     fMat[kMSkewX]  *= sy;
michael@0:     fMat[kMScaleY] *= sy;
michael@0:     fMat[kMPersp1] *= sy;
michael@0: 
michael@0:     this->orTypeMask(kScale_Mask);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkMatrix::postScale(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
michael@0:     if (1 == sx && 1 == sy) {
michael@0:         return true;
michael@0:     }
michael@0:     SkMatrix    m;
michael@0:     m.setScale(sx, sy, px, py);
michael@0:     return this->postConcat(m);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::postScale(SkScalar sx, SkScalar sy) {
michael@0:     if (1 == sx && 1 == sy) {
michael@0:         return true;
michael@0:     }
michael@0:     SkMatrix    m;
michael@0:     m.setScale(sx, sy);
michael@0:     return this->postConcat(m);
michael@0: }
michael@0: 
michael@0: // this guy perhaps can go away, if we have a fract/high-precision way to
michael@0: // scale matrices
michael@0: bool SkMatrix::postIDiv(int divx, int divy) {
michael@0:     if (divx == 0 || divy == 0) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     const float invX = 1.f / divx;
michael@0:     const float invY = 1.f / divy;
michael@0: 
michael@0:     fMat[kMScaleX] *= invX;
michael@0:     fMat[kMSkewX]  *= invX;
michael@0:     fMat[kMTransX] *= invX;
michael@0: 
michael@0:     fMat[kMScaleY] *= invY;
michael@0:     fMat[kMSkewY]  *= invY;
michael@0:     fMat[kMTransY] *= invY;
michael@0: 
michael@0:     this->setTypeMask(kUnknown_Mask);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV,
michael@0:                          SkScalar px, SkScalar py) {
michael@0:     const SkScalar oneMinusCosV = 1 - cosV;
michael@0: 
michael@0:     fMat[kMScaleX]  = cosV;
michael@0:     fMat[kMSkewX]   = -sinV;
michael@0:     fMat[kMTransX]  = sdot(sinV, py, oneMinusCosV, px);
michael@0: 
michael@0:     fMat[kMSkewY]   = sinV;
michael@0:     fMat[kMScaleY]  = cosV;
michael@0:     fMat[kMTransY]  = sdot(-sinV, px, oneMinusCosV, py);
michael@0: 
michael@0:     fMat[kMPersp0] = fMat[kMPersp1] = 0;
michael@0:     fMat[kMPersp2] = 1;
michael@0: 
michael@0:     this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
michael@0: }
michael@0: 
michael@0: void SkMatrix::setSinCos(SkScalar sinV, SkScalar cosV) {
michael@0:     fMat[kMScaleX]  = cosV;
michael@0:     fMat[kMSkewX]   = -sinV;
michael@0:     fMat[kMTransX]  = 0;
michael@0: 
michael@0:     fMat[kMSkewY]   = sinV;
michael@0:     fMat[kMScaleY]  = cosV;
michael@0:     fMat[kMTransY]  = 0;
michael@0: 
michael@0:     fMat[kMPersp0] = fMat[kMPersp1] = 0;
michael@0:     fMat[kMPersp2] = 1;
michael@0: 
michael@0:     this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
michael@0: }
michael@0: 
michael@0: void SkMatrix::setRotate(SkScalar degrees, SkScalar px, SkScalar py) {
michael@0:     SkScalar sinV, cosV;
michael@0:     sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
michael@0:     this->setSinCos(sinV, cosV, px, py);
michael@0: }
michael@0: 
michael@0: void SkMatrix::setRotate(SkScalar degrees) {
michael@0:     SkScalar sinV, cosV;
michael@0:     sinV = SkScalarSinCos(SkDegreesToRadians(degrees), &cosV);
michael@0:     this->setSinCos(sinV, cosV);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::preRotate(SkScalar degrees, SkScalar px, SkScalar py) {
michael@0:     SkMatrix    m;
michael@0:     m.setRotate(degrees, px, py);
michael@0:     return this->preConcat(m);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::preRotate(SkScalar degrees) {
michael@0:     SkMatrix    m;
michael@0:     m.setRotate(degrees);
michael@0:     return this->preConcat(m);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::postRotate(SkScalar degrees, SkScalar px, SkScalar py) {
michael@0:     SkMatrix    m;
michael@0:     m.setRotate(degrees, px, py);
michael@0:     return this->postConcat(m);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::postRotate(SkScalar degrees) {
michael@0:     SkMatrix    m;
michael@0:     m.setRotate(degrees);
michael@0:     return this->postConcat(m);
michael@0: }
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: void SkMatrix::setSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
michael@0:     fMat[kMScaleX]  = 1;
michael@0:     fMat[kMSkewX]   = sx;
michael@0:     fMat[kMTransX]  = -sx * py;
michael@0: 
michael@0:     fMat[kMSkewY]   = sy;
michael@0:     fMat[kMScaleY]  = 1;
michael@0:     fMat[kMTransY]  = -sy * px;
michael@0: 
michael@0:     fMat[kMPersp0] = fMat[kMPersp1] = 0;
michael@0:     fMat[kMPersp2] = 1;
michael@0: 
michael@0:     this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
michael@0: }
michael@0: 
michael@0: void SkMatrix::setSkew(SkScalar sx, SkScalar sy) {
michael@0:     fMat[kMScaleX]  = 1;
michael@0:     fMat[kMSkewX]   = sx;
michael@0:     fMat[kMTransX]  = 0;
michael@0: 
michael@0:     fMat[kMSkewY]   = sy;
michael@0:     fMat[kMScaleY]  = 1;
michael@0:     fMat[kMTransY]  = 0;
michael@0: 
michael@0:     fMat[kMPersp0] = fMat[kMPersp1] = 0;
michael@0:     fMat[kMPersp2] = 1;
michael@0: 
michael@0:     this->setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::preSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
michael@0:     SkMatrix    m;
michael@0:     m.setSkew(sx, sy, px, py);
michael@0:     return this->preConcat(m);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::preSkew(SkScalar sx, SkScalar sy) {
michael@0:     SkMatrix    m;
michael@0:     m.setSkew(sx, sy);
michael@0:     return this->preConcat(m);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::postSkew(SkScalar sx, SkScalar sy, SkScalar px, SkScalar py) {
michael@0:     SkMatrix    m;
michael@0:     m.setSkew(sx, sy, px, py);
michael@0:     return this->postConcat(m);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::postSkew(SkScalar sx, SkScalar sy) {
michael@0:     SkMatrix    m;
michael@0:     m.setSkew(sx, sy);
michael@0:     return this->postConcat(m);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: bool SkMatrix::setRectToRect(const SkRect& src, const SkRect& dst,
michael@0:                              ScaleToFit align)
michael@0: {
michael@0:     if (src.isEmpty()) {
michael@0:         this->reset();
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     if (dst.isEmpty()) {
michael@0:         sk_bzero(fMat, 8 * sizeof(SkScalar));
michael@0:         this->setTypeMask(kScale_Mask | kRectStaysRect_Mask);
michael@0:     } else {
michael@0:         SkScalar    tx, sx = dst.width() / src.width();
michael@0:         SkScalar    ty, sy = dst.height() / src.height();
michael@0:         bool        xLarger = false;
michael@0: 
michael@0:         if (align != kFill_ScaleToFit) {
michael@0:             if (sx > sy) {
michael@0:                 xLarger = true;
michael@0:                 sx = sy;
michael@0:             } else {
michael@0:                 sy = sx;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         tx = dst.fLeft - src.fLeft * sx;
michael@0:         ty = dst.fTop - src.fTop * sy;
michael@0:         if (align == kCenter_ScaleToFit || align == kEnd_ScaleToFit) {
michael@0:             SkScalar diff;
michael@0: 
michael@0:             if (xLarger) {
michael@0:                 diff = dst.width() - src.width() * sy;
michael@0:             } else {
michael@0:                 diff = dst.height() - src.height() * sy;
michael@0:             }
michael@0: 
michael@0:             if (align == kCenter_ScaleToFit) {
michael@0:                 diff = SkScalarHalf(diff);
michael@0:             }
michael@0: 
michael@0:             if (xLarger) {
michael@0:                 tx += diff;
michael@0:             } else {
michael@0:                 ty += diff;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         fMat[kMScaleX] = sx;
michael@0:         fMat[kMScaleY] = sy;
michael@0:         fMat[kMTransX] = tx;
michael@0:         fMat[kMTransY] = ty;
michael@0:         fMat[kMSkewX]  = fMat[kMSkewY] =
michael@0:         fMat[kMPersp0] = fMat[kMPersp1] = 0;
michael@0: 
michael@0:         unsigned mask = kRectStaysRect_Mask;
michael@0:         if (sx != 1 || sy != 1) {
michael@0:             mask |= kScale_Mask;
michael@0:         }
michael@0:         if (tx || ty) {
michael@0:             mask |= kTranslate_Mask;
michael@0:         }
michael@0:         this->setTypeMask(mask);
michael@0:     }
michael@0:     // shared cleanup
michael@0:     fMat[kMPersp2] = 1;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static inline int fixmuladdmul(float a, float b, float c, float d,
michael@0:                                float* result) {
michael@0:     *result = SkDoubleToFloat((double)a * b + (double)c * d);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static inline bool rowcol3(const float row[], const float col[],
michael@0:                            float* result) {
michael@0:     *result = row[0] * col[0] + row[1] * col[3] + row[2] * col[6];
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: static inline int negifaddoverflows(float& result, float a, float b) {
michael@0:     result = a + b;
michael@0:     return 0;
michael@0: }
michael@0: 
michael@0: static void normalize_perspective(SkScalar mat[9]) {
michael@0:     if (SkScalarAbs(mat[SkMatrix::kMPersp2]) > 1) {
michael@0:         for (int i = 0; i < 9; i++)
michael@0:             mat[i] = SkScalarHalf(mat[i]);
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool SkMatrix::setConcat(const SkMatrix& a, const SkMatrix& b) {
michael@0:     TypeMask aType = a.getPerspectiveTypeMaskOnly();
michael@0:     TypeMask bType = b.getPerspectiveTypeMaskOnly();
michael@0: 
michael@0:     if (a.isTriviallyIdentity()) {
michael@0:         *this = b;
michael@0:     } else if (b.isTriviallyIdentity()) {
michael@0:         *this = a;
michael@0:     } else {
michael@0:         SkMatrix tmp;
michael@0: 
michael@0:         if ((aType | bType) & kPerspective_Mask) {
michael@0:             if (!rowcol3(&a.fMat[0], &b.fMat[0], &tmp.fMat[kMScaleX])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!rowcol3(&a.fMat[0], &b.fMat[1], &tmp.fMat[kMSkewX])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!rowcol3(&a.fMat[0], &b.fMat[2], &tmp.fMat[kMTransX])) {
michael@0:                 return false;
michael@0:             }
michael@0: 
michael@0:             if (!rowcol3(&a.fMat[3], &b.fMat[0], &tmp.fMat[kMSkewY])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!rowcol3(&a.fMat[3], &b.fMat[1], &tmp.fMat[kMScaleY])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!rowcol3(&a.fMat[3], &b.fMat[2], &tmp.fMat[kMTransY])) {
michael@0:                 return false;
michael@0:             }
michael@0: 
michael@0:             if (!rowcol3(&a.fMat[6], &b.fMat[0], &tmp.fMat[kMPersp0])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!rowcol3(&a.fMat[6], &b.fMat[1], &tmp.fMat[kMPersp1])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!rowcol3(&a.fMat[6], &b.fMat[2], &tmp.fMat[kMPersp2])) {
michael@0:                 return false;
michael@0:             }
michael@0: 
michael@0:             normalize_perspective(tmp.fMat);
michael@0:             tmp.setTypeMask(kUnknown_Mask);
michael@0:         } else {    // not perspective
michael@0:             if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMScaleX],
michael@0:                     a.fMat[kMSkewX], b.fMat[kMSkewY], &tmp.fMat[kMScaleX])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMSkewX],
michael@0:                       a.fMat[kMSkewX], b.fMat[kMScaleY], &tmp.fMat[kMSkewX])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!fixmuladdmul(a.fMat[kMScaleX], b.fMat[kMTransX],
michael@0:                       a.fMat[kMSkewX], b.fMat[kMTransY], &tmp.fMat[kMTransX])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (negifaddoverflows(tmp.fMat[kMTransX], tmp.fMat[kMTransX],
michael@0:                                   a.fMat[kMTransX]) < 0) {
michael@0:                 return false;
michael@0:             }
michael@0: 
michael@0:             if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMScaleX],
michael@0:                       a.fMat[kMScaleY], b.fMat[kMSkewY], &tmp.fMat[kMSkewY])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMSkewX],
michael@0:                     a.fMat[kMScaleY], b.fMat[kMScaleY], &tmp.fMat[kMScaleY])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (!fixmuladdmul(a.fMat[kMSkewY], b.fMat[kMTransX],
michael@0:                      a.fMat[kMScaleY], b.fMat[kMTransY], &tmp.fMat[kMTransY])) {
michael@0:                 return false;
michael@0:             }
michael@0:             if (negifaddoverflows(tmp.fMat[kMTransY], tmp.fMat[kMTransY],
michael@0:                                   a.fMat[kMTransY]) < 0) {
michael@0:                 return false;
michael@0:             }
michael@0: 
michael@0:             tmp.fMat[kMPersp0] = tmp.fMat[kMPersp1] = 0;
michael@0:             tmp.fMat[kMPersp2] = 1;
michael@0:             //SkDebugf("Concat mat non-persp type: %d\n", tmp.getType());
michael@0:             //SkASSERT(!(tmp.getType() & kPerspective_Mask));
michael@0:             tmp.setTypeMask(kUnknown_Mask | kOnlyPerspectiveValid_Mask);
michael@0:         }
michael@0:         *this = tmp;
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkMatrix::preConcat(const SkMatrix& mat) {
michael@0:     // check for identity first, so we don't do a needless copy of ourselves
michael@0:     // to ourselves inside setConcat()
michael@0:     return mat.isIdentity() || this->setConcat(*this, mat);
michael@0: }
michael@0: 
michael@0: bool SkMatrix::postConcat(const SkMatrix& mat) {
michael@0:     // check for identity first, so we don't do a needless copy of ourselves
michael@0:     // to ourselves inside setConcat()
michael@0:     return mat.isIdentity() || this->setConcat(mat, *this);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: /*  Matrix inversion is very expensive, but also the place where keeping
michael@0:     precision may be most important (here and matrix concat). Hence to avoid
michael@0:     bitmap blitting artifacts when walking the inverse, we use doubles for
michael@0:     the intermediate math, even though we know that is more expensive.
michael@0:  */
michael@0: 
michael@0: static inline SkScalar scross_dscale(SkScalar a, SkScalar b,
michael@0:                                      SkScalar c, SkScalar d, double scale) {
michael@0:     return SkDoubleToScalar(scross(a, b, c, d) * scale);
michael@0: }
michael@0: 
michael@0: static inline double dcross(double a, double b, double c, double d) {
michael@0:     return a * b - c * d;
michael@0: }
michael@0: 
michael@0: static inline SkScalar dcross_dscale(double a, double b,
michael@0:                                      double c, double d, double scale) {
michael@0:     return SkDoubleToScalar(dcross(a, b, c, d) * scale);
michael@0: }
michael@0: 
michael@0: static double sk_inv_determinant(const float mat[9], int isPerspective) {
michael@0:     double det;
michael@0: 
michael@0:     if (isPerspective) {
michael@0:         det = mat[SkMatrix::kMScaleX] *
michael@0:               dcross(mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp2],
michael@0:                      mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp1])
michael@0:               +
michael@0:               mat[SkMatrix::kMSkewX]  *
michael@0:               dcross(mat[SkMatrix::kMTransY], mat[SkMatrix::kMPersp0],
michael@0:                      mat[SkMatrix::kMSkewY],  mat[SkMatrix::kMPersp2])
michael@0:               +
michael@0:               mat[SkMatrix::kMTransX] *
michael@0:               dcross(mat[SkMatrix::kMSkewY],  mat[SkMatrix::kMPersp1],
michael@0:                      mat[SkMatrix::kMScaleY], mat[SkMatrix::kMPersp0]);
michael@0:     } else {
michael@0:         det = dcross(mat[SkMatrix::kMScaleX], mat[SkMatrix::kMScaleY],
michael@0:                      mat[SkMatrix::kMSkewX], mat[SkMatrix::kMSkewY]);
michael@0:     }
michael@0: 
michael@0:     // Since the determinant is on the order of the cube of the matrix members,
michael@0:     // compare to the cube of the default nearly-zero constant (although an
michael@0:     // estimate of the condition number would be better if it wasn't so expensive).
michael@0:     if (SkScalarNearlyZero((float)det, SK_ScalarNearlyZero * SK_ScalarNearlyZero * SK_ScalarNearlyZero)) {
michael@0:         return 0;
michael@0:     }
michael@0:     return 1.0 / det;
michael@0: }
michael@0: 
michael@0: void SkMatrix::SetAffineIdentity(SkScalar affine[6]) {
michael@0:     affine[kAScaleX] = 1;
michael@0:     affine[kASkewY] = 0;
michael@0:     affine[kASkewX] = 0;
michael@0:     affine[kAScaleY] = 1;
michael@0:     affine[kATransX] = 0;
michael@0:     affine[kATransY] = 0;
michael@0: }
michael@0: 
michael@0: bool SkMatrix::asAffine(SkScalar affine[6]) const {
michael@0:     if (this->hasPerspective()) {
michael@0:         return false;
michael@0:     }
michael@0:     if (affine) {
michael@0:         affine[kAScaleX] = this->fMat[kMScaleX];
michael@0:         affine[kASkewY] = this->fMat[kMSkewY];
michael@0:         affine[kASkewX] = this->fMat[kMSkewX];
michael@0:         affine[kAScaleY] = this->fMat[kMScaleY];
michael@0:         affine[kATransX] = this->fMat[kMTransX];
michael@0:         affine[kATransY] = this->fMat[kMTransY];
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkMatrix::invertNonIdentity(SkMatrix* inv) const {
michael@0:     SkASSERT(!this->isIdentity());
michael@0: 
michael@0:     TypeMask mask = this->getType();
michael@0: 
michael@0:     if (0 == (mask & ~(kScale_Mask | kTranslate_Mask))) {
michael@0:         bool invertible = true;
michael@0:         if (inv) {
michael@0:             if (mask & kScale_Mask) {
michael@0:                 SkScalar invX = fMat[kMScaleX];
michael@0:                 SkScalar invY = fMat[kMScaleY];
michael@0:                 if (0 == invX || 0 == invY) {
michael@0:                     return false;
michael@0:                 }
michael@0:                 invX = SkScalarInvert(invX);
michael@0:                 invY = SkScalarInvert(invY);
michael@0: 
michael@0:                 // Must be careful when writing to inv, since it may be the
michael@0:                 // same memory as this.
michael@0: 
michael@0:                 inv->fMat[kMSkewX] = inv->fMat[kMSkewY] =
michael@0:                 inv->fMat[kMPersp0] = inv->fMat[kMPersp1] = 0;
michael@0: 
michael@0:                 inv->fMat[kMScaleX] = invX;
michael@0:                 inv->fMat[kMScaleY] = invY;
michael@0:                 inv->fMat[kMPersp2] = 1;
michael@0:                 inv->fMat[kMTransX] = -fMat[kMTransX] * invX;
michael@0:                 inv->fMat[kMTransY] = -fMat[kMTransY] * invY;
michael@0: 
michael@0:                 inv->setTypeMask(mask | kRectStaysRect_Mask);
michael@0:             } else {
michael@0:                 // translate only
michael@0:                 inv->setTranslate(-fMat[kMTransX], -fMat[kMTransY]);
michael@0:             }
michael@0:         } else {    // inv is NULL, just check if we're invertible
michael@0:             if (!fMat[kMScaleX] || !fMat[kMScaleY]) {
michael@0:                 invertible = false;
michael@0:             }
michael@0:         }
michael@0:         return invertible;
michael@0:     }
michael@0: 
michael@0:     int    isPersp = mask & kPerspective_Mask;
michael@0:     double scale = sk_inv_determinant(fMat, isPersp);
michael@0: 
michael@0:     if (scale == 0) { // underflow
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     if (inv) {
michael@0:         SkMatrix tmp;
michael@0:         if (inv == this) {
michael@0:             inv = &tmp;
michael@0:         }
michael@0: 
michael@0:         if (isPersp) {
michael@0:             inv->fMat[kMScaleX] = scross_dscale(fMat[kMScaleY], fMat[kMPersp2], fMat[kMTransY], fMat[kMPersp1], scale);
michael@0:             inv->fMat[kMSkewX]  = scross_dscale(fMat[kMTransX], fMat[kMPersp1], fMat[kMSkewX],  fMat[kMPersp2], scale);
michael@0:             inv->fMat[kMTransX] = scross_dscale(fMat[kMSkewX],  fMat[kMTransY], fMat[kMTransX], fMat[kMScaleY], scale);
michael@0: 
michael@0:             inv->fMat[kMSkewY]  = scross_dscale(fMat[kMTransY], fMat[kMPersp0], fMat[kMSkewY],  fMat[kMPersp2], scale);
michael@0:             inv->fMat[kMScaleY] = scross_dscale(fMat[kMScaleX], fMat[kMPersp2], fMat[kMTransX], fMat[kMPersp0], scale);
michael@0:             inv->fMat[kMTransY] = scross_dscale(fMat[kMTransX], fMat[kMSkewY],  fMat[kMScaleX], fMat[kMTransY], scale);
michael@0: 
michael@0:             inv->fMat[kMPersp0] = scross_dscale(fMat[kMSkewY],  fMat[kMPersp1], fMat[kMScaleY], fMat[kMPersp0], scale);
michael@0:             inv->fMat[kMPersp1] = scross_dscale(fMat[kMSkewX],  fMat[kMPersp0], fMat[kMScaleX], fMat[kMPersp1], scale);
michael@0:             inv->fMat[kMPersp2] = scross_dscale(fMat[kMScaleX], fMat[kMScaleY], fMat[kMSkewX],  fMat[kMSkewY],  scale);
michael@0:         } else {   // not perspective
michael@0:             inv->fMat[kMScaleX] = SkDoubleToScalar(fMat[kMScaleY] * scale);
michael@0:             inv->fMat[kMSkewX]  = SkDoubleToScalar(-fMat[kMSkewX] * scale);
michael@0:             inv->fMat[kMTransX] = dcross_dscale(fMat[kMSkewX], fMat[kMTransY], fMat[kMScaleY], fMat[kMTransX], scale);
michael@0: 
michael@0:             inv->fMat[kMSkewY]  = SkDoubleToScalar(-fMat[kMSkewY] * scale);
michael@0:             inv->fMat[kMScaleY] = SkDoubleToScalar(fMat[kMScaleX] * scale);
michael@0:             inv->fMat[kMTransY] = dcross_dscale(fMat[kMSkewY], fMat[kMTransX], fMat[kMScaleX], fMat[kMTransY], scale);
michael@0: 
michael@0:             inv->fMat[kMPersp0] = 0;
michael@0:             inv->fMat[kMPersp1] = 0;
michael@0:             inv->fMat[kMPersp2] = 1;
michael@0:         }
michael@0: 
michael@0:         inv->setTypeMask(fTypeMask);
michael@0: 
michael@0:         if (inv == &tmp) {
michael@0:             *(SkMatrix*)this = tmp;
michael@0:         }
michael@0:     }
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: void SkMatrix::Identity_pts(const SkMatrix& m, SkPoint dst[],
michael@0:                             const SkPoint src[], int count) {
michael@0:     SkASSERT(m.getType() == 0);
michael@0: 
michael@0:     if (dst != src && count > 0)
michael@0:         memcpy(dst, src, count * sizeof(SkPoint));
michael@0: }
michael@0: 
michael@0: void SkMatrix::Trans_pts(const SkMatrix& m, SkPoint dst[],
michael@0:                          const SkPoint src[], int count) {
michael@0:     SkASSERT(m.getType() == kTranslate_Mask);
michael@0: 
michael@0:     if (count > 0) {
michael@0:         SkScalar tx = m.fMat[kMTransX];
michael@0:         SkScalar ty = m.fMat[kMTransY];
michael@0:         do {
michael@0:             dst->fY = src->fY + ty;
michael@0:             dst->fX = src->fX + tx;
michael@0:             src += 1;
michael@0:             dst += 1;
michael@0:         } while (--count);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkMatrix::Scale_pts(const SkMatrix& m, SkPoint dst[],
michael@0:                          const SkPoint src[], int count) {
michael@0:     SkASSERT(m.getType() == kScale_Mask);
michael@0: 
michael@0:     if (count > 0) {
michael@0:         SkScalar mx = m.fMat[kMScaleX];
michael@0:         SkScalar my = m.fMat[kMScaleY];
michael@0:         do {
michael@0:             dst->fY = src->fY * my;
michael@0:             dst->fX = src->fX * mx;
michael@0:             src += 1;
michael@0:             dst += 1;
michael@0:         } while (--count);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkMatrix::ScaleTrans_pts(const SkMatrix& m, SkPoint dst[],
michael@0:                               const SkPoint src[], int count) {
michael@0:     SkASSERT(m.getType() == (kScale_Mask | kTranslate_Mask));
michael@0: 
michael@0:     if (count > 0) {
michael@0:         SkScalar mx = m.fMat[kMScaleX];
michael@0:         SkScalar my = m.fMat[kMScaleY];
michael@0:         SkScalar tx = m.fMat[kMTransX];
michael@0:         SkScalar ty = m.fMat[kMTransY];
michael@0:         do {
michael@0:             dst->fY = src->fY * my + ty;
michael@0:             dst->fX = src->fX * mx + tx;
michael@0:             src += 1;
michael@0:             dst += 1;
michael@0:         } while (--count);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkMatrix::Rot_pts(const SkMatrix& m, SkPoint dst[],
michael@0:                        const SkPoint src[], int count) {
michael@0:     SkASSERT((m.getType() & (kPerspective_Mask | kTranslate_Mask)) == 0);
michael@0: 
michael@0:     if (count > 0) {
michael@0:         SkScalar mx = m.fMat[kMScaleX];
michael@0:         SkScalar my = m.fMat[kMScaleY];
michael@0:         SkScalar kx = m.fMat[kMSkewX];
michael@0:         SkScalar ky = m.fMat[kMSkewY];
michael@0:         do {
michael@0:             SkScalar sy = src->fY;
michael@0:             SkScalar sx = src->fX;
michael@0:             src += 1;
michael@0:             dst->fY = sdot(sx, ky, sy, my);
michael@0:             dst->fX = sdot(sx, mx, sy, kx);
michael@0:             dst += 1;
michael@0:         } while (--count);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkMatrix::RotTrans_pts(const SkMatrix& m, SkPoint dst[],
michael@0:                             const SkPoint src[], int count) {
michael@0:     SkASSERT(!m.hasPerspective());
michael@0: 
michael@0:     if (count > 0) {
michael@0:         SkScalar mx = m.fMat[kMScaleX];
michael@0:         SkScalar my = m.fMat[kMScaleY];
michael@0:         SkScalar kx = m.fMat[kMSkewX];
michael@0:         SkScalar ky = m.fMat[kMSkewY];
michael@0:         SkScalar tx = m.fMat[kMTransX];
michael@0:         SkScalar ty = m.fMat[kMTransY];
michael@0:         do {
michael@0:             SkScalar sy = src->fY;
michael@0:             SkScalar sx = src->fX;
michael@0:             src += 1;
michael@0: #ifdef SK_LEGACY_MATRIX_MATH_ORDER
michael@0:             dst->fY = sx * ky + (sy * my + ty);
michael@0:             dst->fX = sx * mx + (sy * kx + tx);
michael@0: #else
michael@0:             dst->fY = sdot(sx, ky, sy, my) + ty;
michael@0:             dst->fX = sdot(sx, mx, sy, kx) + tx;
michael@0: #endif
michael@0:             dst += 1;
michael@0:         } while (--count);
michael@0:     }
michael@0: }
michael@0: 
michael@0: void SkMatrix::Persp_pts(const SkMatrix& m, SkPoint dst[],
michael@0:                          const SkPoint src[], int count) {
michael@0:     SkASSERT(m.hasPerspective());
michael@0: 
michael@0:     if (count > 0) {
michael@0:         do {
michael@0:             SkScalar sy = src->fY;
michael@0:             SkScalar sx = src->fX;
michael@0:             src += 1;
michael@0: 
michael@0:             SkScalar x = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX])  + m.fMat[kMTransX];
michael@0:             SkScalar y = sdot(sx, m.fMat[kMSkewY],  sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
michael@0: #ifdef SK_LEGACY_MATRIX_MATH_ORDER
michael@0:             SkScalar z = sx * m.fMat[kMPersp0] + (sy * m.fMat[kMPersp1] + m.fMat[kMPersp2]);
michael@0: #else
michael@0:             SkScalar z = sdot(sx, m.fMat[kMPersp0], sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2];
michael@0: #endif
michael@0:             if (z) {
michael@0:                 z = SkScalarFastInvert(z);
michael@0:             }
michael@0: 
michael@0:             dst->fY = y * z;
michael@0:             dst->fX = x * z;
michael@0:             dst += 1;
michael@0:         } while (--count);
michael@0:     }
michael@0: }
michael@0: 
michael@0: const SkMatrix::MapPtsProc SkMatrix::gMapPtsProcs[] = {
michael@0:     SkMatrix::Identity_pts, SkMatrix::Trans_pts,
michael@0:     SkMatrix::Scale_pts,    SkMatrix::ScaleTrans_pts,
michael@0:     SkMatrix::Rot_pts,      SkMatrix::RotTrans_pts,
michael@0:     SkMatrix::Rot_pts,      SkMatrix::RotTrans_pts,
michael@0:     // repeat the persp proc 8 times
michael@0:     SkMatrix::Persp_pts,    SkMatrix::Persp_pts,
michael@0:     SkMatrix::Persp_pts,    SkMatrix::Persp_pts,
michael@0:     SkMatrix::Persp_pts,    SkMatrix::Persp_pts,
michael@0:     SkMatrix::Persp_pts,    SkMatrix::Persp_pts
michael@0: };
michael@0: 
michael@0: void SkMatrix::mapPoints(SkPoint dst[], const SkPoint src[], int count) const {
michael@0:     SkASSERT((dst && src && count > 0) || 0 == count);
michael@0:     // no partial overlap
michael@0:     SkASSERT(src == dst || &dst[count] <= &src[0] || &src[count] <= &dst[0]);
michael@0: 
michael@0:     this->getMapPtsProc()(*this, dst, src, count);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: void SkMatrix::mapHomogeneousPoints(SkScalar dst[], const SkScalar src[], int count) const {
michael@0:     SkASSERT((dst && src && count > 0) || 0 == count);
michael@0:     // no partial overlap
michael@0:     SkASSERT(src == dst || SkAbs32((int32_t)(src - dst)) >= 3*count);
michael@0: 
michael@0:     if (count > 0) {
michael@0:         if (this->isIdentity()) {
michael@0:             memcpy(dst, src, 3*count*sizeof(SkScalar));
michael@0:             return;
michael@0:         }
michael@0:         do {
michael@0:             SkScalar sx = src[0];
michael@0:             SkScalar sy = src[1];
michael@0:             SkScalar sw = src[2];
michael@0:             src += 3;
michael@0: 
michael@0:             SkScalar x = sdot(sx, fMat[kMScaleX], sy, fMat[kMSkewX],  sw, fMat[kMTransX]);
michael@0:             SkScalar y = sdot(sx, fMat[kMSkewY],  sy, fMat[kMScaleY], sw, fMat[kMTransY]);
michael@0:             SkScalar w = sdot(sx, fMat[kMPersp0], sy, fMat[kMPersp1], sw, fMat[kMPersp2]);
michael@0: 
michael@0:             dst[0] = x;
michael@0:             dst[1] = y;
michael@0:             dst[2] = w;
michael@0:             dst += 3;
michael@0:         } while (--count);
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: void SkMatrix::mapVectors(SkPoint dst[], const SkPoint src[], int count) const {
michael@0:     if (this->hasPerspective()) {
michael@0:         SkPoint origin;
michael@0: 
michael@0:         MapXYProc proc = this->getMapXYProc();
michael@0:         proc(*this, 0, 0, &origin);
michael@0: 
michael@0:         for (int i = count - 1; i >= 0; --i) {
michael@0:             SkPoint tmp;
michael@0: 
michael@0:             proc(*this, src[i].fX, src[i].fY, &tmp);
michael@0:             dst[i].set(tmp.fX - origin.fX, tmp.fY - origin.fY);
michael@0:         }
michael@0:     } else {
michael@0:         SkMatrix tmp = *this;
michael@0: 
michael@0:         tmp.fMat[kMTransX] = tmp.fMat[kMTransY] = 0;
michael@0:         tmp.clearTypeMask(kTranslate_Mask);
michael@0:         tmp.mapPoints(dst, src, count);
michael@0:     }
michael@0: }
michael@0: 
michael@0: bool SkMatrix::mapRect(SkRect* dst, const SkRect& src) const {
michael@0:     SkASSERT(dst && &src);
michael@0: 
michael@0:     if (this->rectStaysRect()) {
michael@0:         this->mapPoints((SkPoint*)dst, (const SkPoint*)&src, 2);
michael@0:         dst->sort();
michael@0:         return true;
michael@0:     } else {
michael@0:         SkPoint quad[4];
michael@0: 
michael@0:         src.toQuad(quad);
michael@0:         this->mapPoints(quad, quad, 4);
michael@0:         dst->set(quad, 4);
michael@0:         return false;
michael@0:     }
michael@0: }
michael@0: 
michael@0: SkScalar SkMatrix::mapRadius(SkScalar radius) const {
michael@0:     SkVector    vec[2];
michael@0: 
michael@0:     vec[0].set(radius, 0);
michael@0:     vec[1].set(0, radius);
michael@0:     this->mapVectors(vec, 2);
michael@0: 
michael@0:     SkScalar d0 = vec[0].length();
michael@0:     SkScalar d1 = vec[1].length();
michael@0: 
michael@0:     // return geometric mean
michael@0:     return SkScalarSqrt(d0 * d1);
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: void SkMatrix::Persp_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
michael@0:                         SkPoint* pt) {
michael@0:     SkASSERT(m.hasPerspective());
michael@0: 
michael@0:     SkScalar x = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX])  + m.fMat[kMTransX];
michael@0:     SkScalar y = sdot(sx, m.fMat[kMSkewY],  sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
michael@0:     SkScalar z = sdot(sx, m.fMat[kMPersp0], sy, m.fMat[kMPersp1]) + m.fMat[kMPersp2];
michael@0:     if (z) {
michael@0:         z = SkScalarFastInvert(z);
michael@0:     }
michael@0:     pt->fX = x * z;
michael@0:     pt->fY = y * z;
michael@0: }
michael@0: 
michael@0: void SkMatrix::RotTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
michael@0:                            SkPoint* pt) {
michael@0:     SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask)) == kAffine_Mask);
michael@0: 
michael@0: #ifdef SK_LEGACY_MATRIX_MATH_ORDER
michael@0:     pt->fX = sx * m.fMat[kMScaleX] + (sy * m.fMat[kMSkewX]  +  m.fMat[kMTransX]);
michael@0:     pt->fY = sx * m.fMat[kMSkewY]  + (sy * m.fMat[kMScaleY] + m.fMat[kMTransY]);
michael@0: #else
michael@0:     pt->fX = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX])  + m.fMat[kMTransX];
michael@0:     pt->fY = sdot(sx, m.fMat[kMSkewY],  sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
michael@0: #endif
michael@0: }
michael@0: 
michael@0: void SkMatrix::Rot_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
michael@0:                       SkPoint* pt) {
michael@0:     SkASSERT((m.getType() & (kAffine_Mask | kPerspective_Mask))== kAffine_Mask);
michael@0:     SkASSERT(0 == m.fMat[kMTransX]);
michael@0:     SkASSERT(0 == m.fMat[kMTransY]);
michael@0: 
michael@0: #ifdef SK_LEGACY_MATRIX_MATH_ORDER
michael@0:     pt->fX = sx * m.fMat[kMScaleX] + (sy * m.fMat[kMSkewX]  + m.fMat[kMTransX]);
michael@0:     pt->fY = sx * m.fMat[kMSkewY]  + (sy * m.fMat[kMScaleY] + m.fMat[kMTransY]);
michael@0: #else
michael@0:     pt->fX = sdot(sx, m.fMat[kMScaleX], sy, m.fMat[kMSkewX])  + m.fMat[kMTransX];
michael@0:     pt->fY = sdot(sx, m.fMat[kMSkewY],  sy, m.fMat[kMScaleY]) + m.fMat[kMTransY];
michael@0: #endif
michael@0: }
michael@0: 
michael@0: void SkMatrix::ScaleTrans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
michael@0:                              SkPoint* pt) {
michael@0:     SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
michael@0:              == kScale_Mask);
michael@0: 
michael@0:     pt->fX = sx * m.fMat[kMScaleX] + m.fMat[kMTransX];
michael@0:     pt->fY = sy * m.fMat[kMScaleY] + m.fMat[kMTransY];
michael@0: }
michael@0: 
michael@0: void SkMatrix::Scale_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
michael@0:                         SkPoint* pt) {
michael@0:     SkASSERT((m.getType() & (kScale_Mask | kAffine_Mask | kPerspective_Mask))
michael@0:              == kScale_Mask);
michael@0:     SkASSERT(0 == m.fMat[kMTransX]);
michael@0:     SkASSERT(0 == m.fMat[kMTransY]);
michael@0: 
michael@0:     pt->fX = sx * m.fMat[kMScaleX];
michael@0:     pt->fY = sy * m.fMat[kMScaleY];
michael@0: }
michael@0: 
michael@0: void SkMatrix::Trans_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
michael@0:                         SkPoint* pt) {
michael@0:     SkASSERT(m.getType() == kTranslate_Mask);
michael@0: 
michael@0:     pt->fX = sx + m.fMat[kMTransX];
michael@0:     pt->fY = sy + m.fMat[kMTransY];
michael@0: }
michael@0: 
michael@0: void SkMatrix::Identity_xy(const SkMatrix& m, SkScalar sx, SkScalar sy,
michael@0:                            SkPoint* pt) {
michael@0:     SkASSERT(0 == m.getType());
michael@0: 
michael@0:     pt->fX = sx;
michael@0:     pt->fY = sy;
michael@0: }
michael@0: 
michael@0: const SkMatrix::MapXYProc SkMatrix::gMapXYProcs[] = {
michael@0:     SkMatrix::Identity_xy, SkMatrix::Trans_xy,
michael@0:     SkMatrix::Scale_xy,    SkMatrix::ScaleTrans_xy,
michael@0:     SkMatrix::Rot_xy,      SkMatrix::RotTrans_xy,
michael@0:     SkMatrix::Rot_xy,      SkMatrix::RotTrans_xy,
michael@0:     // repeat the persp proc 8 times
michael@0:     SkMatrix::Persp_xy,    SkMatrix::Persp_xy,
michael@0:     SkMatrix::Persp_xy,    SkMatrix::Persp_xy,
michael@0:     SkMatrix::Persp_xy,    SkMatrix::Persp_xy,
michael@0:     SkMatrix::Persp_xy,    SkMatrix::Persp_xy
michael@0: };
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: // if its nearly zero (just made up 26, perhaps it should be bigger or smaller)
michael@0: #define PerspNearlyZero(x)  SkScalarNearlyZero(x, (1.0f / (1 << 26)))
michael@0: 
michael@0: bool SkMatrix::fixedStepInX(SkScalar y, SkFixed* stepX, SkFixed* stepY) const {
michael@0:     if (PerspNearlyZero(fMat[kMPersp0])) {
michael@0:         if (stepX || stepY) {
michael@0:             if (PerspNearlyZero(fMat[kMPersp1]) &&
michael@0:                     PerspNearlyZero(fMat[kMPersp2] - 1)) {
michael@0:                 if (stepX) {
michael@0:                     *stepX = SkScalarToFixed(fMat[kMScaleX]);
michael@0:                 }
michael@0:                 if (stepY) {
michael@0:                     *stepY = SkScalarToFixed(fMat[kMSkewY]);
michael@0:                 }
michael@0:             } else {
michael@0:                 SkScalar z = y * fMat[kMPersp1] + fMat[kMPersp2];
michael@0:                 if (stepX) {
michael@0:                     *stepX = SkScalarToFixed(fMat[kMScaleX] / z);
michael@0:                 }
michael@0:                 if (stepY) {
michael@0:                     *stepY = SkScalarToFixed(fMat[kMSkewY] / z);
michael@0:                 }
michael@0:             }
michael@0:         }
michael@0:         return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #include "SkPerspIter.h"
michael@0: 
michael@0: SkPerspIter::SkPerspIter(const SkMatrix& m, SkScalar x0, SkScalar y0, int count)
michael@0:         : fMatrix(m), fSX(x0), fSY(y0), fCount(count) {
michael@0:     SkPoint pt;
michael@0: 
michael@0:     SkMatrix::Persp_xy(m, x0, y0, &pt);
michael@0:     fX = SkScalarToFixed(pt.fX);
michael@0:     fY = SkScalarToFixed(pt.fY);
michael@0: }
michael@0: 
michael@0: int SkPerspIter::next() {
michael@0:     int n = fCount;
michael@0: 
michael@0:     if (0 == n) {
michael@0:         return 0;
michael@0:     }
michael@0:     SkPoint pt;
michael@0:     SkFixed x = fX;
michael@0:     SkFixed y = fY;
michael@0:     SkFixed dx, dy;
michael@0: 
michael@0:     if (n >= kCount) {
michael@0:         n = kCount;
michael@0:         fSX += SkIntToScalar(kCount);
michael@0:         SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
michael@0:         fX = SkScalarToFixed(pt.fX);
michael@0:         fY = SkScalarToFixed(pt.fY);
michael@0:         dx = (fX - x) >> kShift;
michael@0:         dy = (fY - y) >> kShift;
michael@0:     } else {
michael@0:         fSX += SkIntToScalar(n);
michael@0:         SkMatrix::Persp_xy(fMatrix, fSX, fSY, &pt);
michael@0:         fX = SkScalarToFixed(pt.fX);
michael@0:         fY = SkScalarToFixed(pt.fY);
michael@0:         dx = (fX - x) / n;
michael@0:         dy = (fY - y) / n;
michael@0:     }
michael@0: 
michael@0:     SkFixed* p = fStorage;
michael@0:     for (int i = 0; i < n; i++) {
michael@0:         *p++ = x; x += dx;
michael@0:         *p++ = y; y += dy;
michael@0:     }
michael@0: 
michael@0:     fCount -= n;
michael@0:     return n;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static inline bool checkForZero(float x) {
michael@0:     return x*x == 0;
michael@0: }
michael@0: 
michael@0: static inline bool poly_to_point(SkPoint* pt, const SkPoint poly[], int count) {
michael@0:     float   x = 1, y = 1;
michael@0:     SkPoint pt1, pt2;
michael@0: 
michael@0:     if (count > 1) {
michael@0:         pt1.fX = poly[1].fX - poly[0].fX;
michael@0:         pt1.fY = poly[1].fY - poly[0].fY;
michael@0:         y = SkPoint::Length(pt1.fX, pt1.fY);
michael@0:         if (checkForZero(y)) {
michael@0:             return false;
michael@0:         }
michael@0:         switch (count) {
michael@0:             case 2:
michael@0:                 break;
michael@0:             case 3:
michael@0:                 pt2.fX = poly[0].fY - poly[2].fY;
michael@0:                 pt2.fY = poly[2].fX - poly[0].fX;
michael@0:                 goto CALC_X;
michael@0:             default:
michael@0:                 pt2.fX = poly[0].fY - poly[3].fY;
michael@0:                 pt2.fY = poly[3].fX - poly[0].fX;
michael@0:             CALC_X:
michael@0:                 x = sdot(pt1.fX, pt2.fX, pt1.fY, pt2.fY) / y;
michael@0:                 break;
michael@0:         }
michael@0:     }
michael@0:     pt->set(x, y);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkMatrix::Poly2Proc(const SkPoint srcPt[], SkMatrix* dst,
michael@0:                          const SkPoint& scale) {
michael@0:     float invScale = 1 / scale.fY;
michael@0: 
michael@0:     dst->fMat[kMScaleX] = (srcPt[1].fY - srcPt[0].fY) * invScale;
michael@0:     dst->fMat[kMSkewY] = (srcPt[0].fX - srcPt[1].fX) * invScale;
michael@0:     dst->fMat[kMPersp0] = 0;
michael@0:     dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
michael@0:     dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
michael@0:     dst->fMat[kMPersp1] = 0;
michael@0:     dst->fMat[kMTransX] = srcPt[0].fX;
michael@0:     dst->fMat[kMTransY] = srcPt[0].fY;
michael@0:     dst->fMat[kMPersp2] = 1;
michael@0:     dst->setTypeMask(kUnknown_Mask);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkMatrix::Poly3Proc(const SkPoint srcPt[], SkMatrix* dst,
michael@0:                          const SkPoint& scale) {
michael@0:     float invScale = 1 / scale.fX;
michael@0:     dst->fMat[kMScaleX] = (srcPt[2].fX - srcPt[0].fX) * invScale;
michael@0:     dst->fMat[kMSkewY] = (srcPt[2].fY - srcPt[0].fY) * invScale;
michael@0:     dst->fMat[kMPersp0] = 0;
michael@0: 
michael@0:     invScale = 1 / scale.fY;
michael@0:     dst->fMat[kMSkewX] = (srcPt[1].fX - srcPt[0].fX) * invScale;
michael@0:     dst->fMat[kMScaleY] = (srcPt[1].fY - srcPt[0].fY) * invScale;
michael@0:     dst->fMat[kMPersp1] = 0;
michael@0: 
michael@0:     dst->fMat[kMTransX] = srcPt[0].fX;
michael@0:     dst->fMat[kMTransY] = srcPt[0].fY;
michael@0:     dst->fMat[kMPersp2] = 1;
michael@0:     dst->setTypeMask(kUnknown_Mask);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: bool SkMatrix::Poly4Proc(const SkPoint srcPt[], SkMatrix* dst,
michael@0:                          const SkPoint& scale) {
michael@0:     float   a1, a2;
michael@0:     float   x0, y0, x1, y1, x2, y2;
michael@0: 
michael@0:     x0 = srcPt[2].fX - srcPt[0].fX;
michael@0:     y0 = srcPt[2].fY - srcPt[0].fY;
michael@0:     x1 = srcPt[2].fX - srcPt[1].fX;
michael@0:     y1 = srcPt[2].fY - srcPt[1].fY;
michael@0:     x2 = srcPt[2].fX - srcPt[3].fX;
michael@0:     y2 = srcPt[2].fY - srcPt[3].fY;
michael@0: 
michael@0:     /* check if abs(x2) > abs(y2) */
michael@0:     if ( x2 > 0 ? y2 > 0 ? x2 > y2 : x2 > -y2 : y2 > 0 ? -x2 > y2 : x2 < y2) {
michael@0:         float denom = SkScalarMulDiv(x1, y2, x2) - y1;
michael@0:         if (checkForZero(denom)) {
michael@0:             return false;
michael@0:         }
michael@0:         a1 = (SkScalarMulDiv(x0 - x1, y2, x2) - y0 + y1) / denom;
michael@0:     } else {
michael@0:         float denom = x1 - SkScalarMulDiv(y1, x2, y2);
michael@0:         if (checkForZero(denom)) {
michael@0:             return false;
michael@0:         }
michael@0:         a1 = (x0 - x1 - SkScalarMulDiv(y0 - y1, x2, y2)) / denom;
michael@0:     }
michael@0: 
michael@0:     /* check if abs(x1) > abs(y1) */
michael@0:     if ( x1 > 0 ? y1 > 0 ? x1 > y1 : x1 > -y1 : y1 > 0 ? -x1 > y1 : x1 < y1) {
michael@0:         float denom = y2 - SkScalarMulDiv(x2, y1, x1);
michael@0:         if (checkForZero(denom)) {
michael@0:             return false;
michael@0:         }
michael@0:         a2 = (y0 - y2 - SkScalarMulDiv(x0 - x2, y1, x1)) / denom;
michael@0:     } else {
michael@0:         float denom = SkScalarMulDiv(y2, x1, y1) - x2;
michael@0:         if (checkForZero(denom)) {
michael@0:             return false;
michael@0:         }
michael@0:         a2 = (SkScalarMulDiv(y0 - y2, x1, y1) - x0 + x2) / denom;
michael@0:     }
michael@0: 
michael@0:     float invScale = SkScalarInvert(scale.fX);
michael@0:     dst->fMat[kMScaleX] = (a2 * srcPt[3].fX + srcPt[3].fX - srcPt[0].fX) * invScale;
michael@0:     dst->fMat[kMSkewY]  = (a2 * srcPt[3].fY + srcPt[3].fY - srcPt[0].fY) * invScale;
michael@0:     dst->fMat[kMPersp0] = a2 * invScale;
michael@0: 
michael@0:     invScale = SkScalarInvert(scale.fY);
michael@0:     dst->fMat[kMSkewX]  = (a1 * srcPt[1].fX + srcPt[1].fX - srcPt[0].fX) * invScale;
michael@0:     dst->fMat[kMScaleY] = (a1 * srcPt[1].fY + srcPt[1].fY - srcPt[0].fY) * invScale;
michael@0:     dst->fMat[kMPersp1] = a1 * invScale;
michael@0: 
michael@0:     dst->fMat[kMTransX] = srcPt[0].fX;
michael@0:     dst->fMat[kMTransY] = srcPt[0].fY;
michael@0:     dst->fMat[kMPersp2] = 1;
michael@0:     dst->setTypeMask(kUnknown_Mask);
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: typedef bool (*PolyMapProc)(const SkPoint[], SkMatrix*, const SkPoint&);
michael@0: 
michael@0: /*  Taken from Rob Johnson's original sample code in QuickDraw GX
michael@0: */
michael@0: bool SkMatrix::setPolyToPoly(const SkPoint src[], const SkPoint dst[],
michael@0:                              int count) {
michael@0:     if ((unsigned)count > 4) {
michael@0:         SkDebugf("--- SkMatrix::setPolyToPoly count out of range %d\n", count);
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     if (0 == count) {
michael@0:         this->reset();
michael@0:         return true;
michael@0:     }
michael@0:     if (1 == count) {
michael@0:         this->setTranslate(dst[0].fX - src[0].fX, dst[0].fY - src[0].fY);
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     SkPoint scale;
michael@0:     if (!poly_to_point(&scale, src, count) ||
michael@0:             SkScalarNearlyZero(scale.fX) ||
michael@0:             SkScalarNearlyZero(scale.fY)) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     static const PolyMapProc gPolyMapProcs[] = {
michael@0:         SkMatrix::Poly2Proc, SkMatrix::Poly3Proc, SkMatrix::Poly4Proc
michael@0:     };
michael@0:     PolyMapProc proc = gPolyMapProcs[count - 2];
michael@0: 
michael@0:     SkMatrix tempMap, result;
michael@0:     tempMap.setTypeMask(kUnknown_Mask);
michael@0: 
michael@0:     if (!proc(src, &tempMap, scale)) {
michael@0:         return false;
michael@0:     }
michael@0:     if (!tempMap.invert(&result)) {
michael@0:         return false;
michael@0:     }
michael@0:     if (!proc(dst, &tempMap, scale)) {
michael@0:         return false;
michael@0:     }
michael@0:     if (!result.setConcat(tempMap, result)) {
michael@0:         return false;
michael@0:     }
michael@0:     *this = result;
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: enum MinOrMax {
michael@0:     kMin_MinOrMax,
michael@0:     kMax_MinOrMax
michael@0: };
michael@0: 
michael@0: template <MinOrMax MIN_OR_MAX> SkScalar get_stretch_factor(SkMatrix::TypeMask typeMask,
michael@0:                                                            const SkScalar m[9]) {
michael@0:     if (typeMask & SkMatrix::kPerspective_Mask) {
michael@0:         return -1;
michael@0:     }
michael@0:     if (SkMatrix::kIdentity_Mask == typeMask) {
michael@0:         return 1;
michael@0:     }
michael@0:     if (!(typeMask & SkMatrix::kAffine_Mask)) {
michael@0:         if (kMin_MinOrMax == MIN_OR_MAX) {
michael@0:              return SkMinScalar(SkScalarAbs(m[SkMatrix::kMScaleX]),
michael@0:                                 SkScalarAbs(m[SkMatrix::kMScaleY]));
michael@0:         } else {
michael@0:              return SkMaxScalar(SkScalarAbs(m[SkMatrix::kMScaleX]),
michael@0:                                 SkScalarAbs(m[SkMatrix::kMScaleY]));
michael@0:         }
michael@0:     }
michael@0:     // ignore the translation part of the matrix, just look at 2x2 portion.
michael@0:     // compute singular values, take largest or smallest abs value.
michael@0:     // [a b; b c] = A^T*A
michael@0:     SkScalar a = sdot(m[SkMatrix::kMScaleX], m[SkMatrix::kMScaleX],
michael@0:                       m[SkMatrix::kMSkewY],  m[SkMatrix::kMSkewY]);
michael@0:     SkScalar b = sdot(m[SkMatrix::kMScaleX], m[SkMatrix::kMSkewX],
michael@0:                       m[SkMatrix::kMScaleY], m[SkMatrix::kMSkewY]);
michael@0:     SkScalar c = sdot(m[SkMatrix::kMSkewX],  m[SkMatrix::kMSkewX],
michael@0:                       m[SkMatrix::kMScaleY], m[SkMatrix::kMScaleY]);
michael@0:     // eigenvalues of A^T*A are the squared singular values of A.
michael@0:     // characteristic equation is det((A^T*A) - l*I) = 0
michael@0:     // l^2 - (a + c)l + (ac-b^2)
michael@0:     // solve using quadratic equation (divisor is non-zero since l^2 has 1 coeff
michael@0:     // and roots are guaranteed to be pos and real).
michael@0:     SkScalar chosenRoot;
michael@0:     SkScalar bSqd = b * b;
michael@0:     // if upper left 2x2 is orthogonal save some math
michael@0:     if (bSqd <= SK_ScalarNearlyZero*SK_ScalarNearlyZero) {
michael@0:         if (kMin_MinOrMax == MIN_OR_MAX) {
michael@0:             chosenRoot = SkMinScalar(a, c);
michael@0:         } else {
michael@0:             chosenRoot = SkMaxScalar(a, c);
michael@0:         }
michael@0:     } else {
michael@0:         SkScalar aminusc = a - c;
michael@0:         SkScalar apluscdiv2 = SkScalarHalf(a + c);
michael@0:         SkScalar x = SkScalarHalf(SkScalarSqrt(aminusc * aminusc + 4 * bSqd));
michael@0:         if (kMin_MinOrMax == MIN_OR_MAX) {
michael@0:             chosenRoot = apluscdiv2 - x;
michael@0:         } else {
michael@0:             chosenRoot = apluscdiv2 + x;
michael@0:         }
michael@0:     }
michael@0:     SkASSERT(chosenRoot >= 0);
michael@0:     return SkScalarSqrt(chosenRoot);
michael@0: }
michael@0: 
michael@0: SkScalar SkMatrix::getMinStretch() const {
michael@0:     return get_stretch_factor<kMin_MinOrMax>(this->getType(), fMat);
michael@0: }
michael@0: 
michael@0: SkScalar SkMatrix::getMaxStretch() const {
michael@0:     return get_stretch_factor<kMax_MinOrMax>(this->getType(), fMat);
michael@0: }
michael@0: 
michael@0: static void reset_identity_matrix(SkMatrix* identity) {
michael@0:     identity->reset();
michael@0: }
michael@0: 
michael@0: const SkMatrix& SkMatrix::I() {
michael@0:     // If you can use C++11 now, you might consider replacing this with a constexpr constructor.
michael@0:     static SkMatrix gIdentity;
michael@0:     SK_DECLARE_STATIC_ONCE(once);
michael@0:     SkOnce(&once, reset_identity_matrix, &gIdentity);
michael@0:     return gIdentity;
michael@0: }
michael@0: 
michael@0: const SkMatrix& SkMatrix::InvalidMatrix() {
michael@0:     static SkMatrix gInvalid;
michael@0:     static bool gOnce;
michael@0:     if (!gOnce) {
michael@0:         gInvalid.setAll(SK_ScalarMax, SK_ScalarMax, SK_ScalarMax,
michael@0:                         SK_ScalarMax, SK_ScalarMax, SK_ScalarMax,
michael@0:                         SK_ScalarMax, SK_ScalarMax, SK_ScalarMax);
michael@0:         gInvalid.getType(); // force the type to be computed
michael@0:         gOnce = true;
michael@0:     }
michael@0:     return gInvalid;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: size_t SkMatrix::writeToMemory(void* buffer) const {
michael@0:     // TODO write less for simple matrices
michael@0:     static const size_t sizeInMemory = 9 * sizeof(SkScalar);
michael@0:     if (buffer) {
michael@0:         memcpy(buffer, fMat, sizeInMemory);
michael@0:     }
michael@0:     return sizeInMemory;
michael@0: }
michael@0: 
michael@0: size_t SkMatrix::readFromMemory(const void* buffer, size_t length) {
michael@0:     static const size_t sizeInMemory = 9 * sizeof(SkScalar);
michael@0:     if (length < sizeInMemory) {
michael@0:         return 0;
michael@0:     }
michael@0:     if (buffer) {
michael@0:         memcpy(fMat, buffer, sizeInMemory);
michael@0:         this->setTypeMask(kUnknown_Mask);
michael@0:     }
michael@0:     return sizeInMemory;
michael@0: }
michael@0: 
michael@0: #ifdef SK_DEVELOPER
michael@0: void SkMatrix::dump() const {
michael@0:     SkString str;
michael@0:     this->toString(&str);
michael@0:     SkDebugf("%s\n", str.c_str());
michael@0: }
michael@0: #endif
michael@0: 
michael@0: #ifndef SK_IGNORE_TO_STRING
michael@0: void SkMatrix::toString(SkString* str) const {
michael@0:     str->appendf("[%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f][%8.4f %8.4f %8.4f]",
michael@0:              fMat[0], fMat[1], fMat[2], fMat[3], fMat[4], fMat[5],
michael@0:              fMat[6], fMat[7], fMat[8]);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: #include "SkMatrixUtils.h"
michael@0: 
michael@0: bool SkTreatAsSprite(const SkMatrix& mat, int width, int height,
michael@0:                      unsigned subpixelBits) {
michael@0:     // quick reject on affine or perspective
michael@0:     if (mat.getType() & ~(SkMatrix::kScale_Mask | SkMatrix::kTranslate_Mask)) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     // quick success check
michael@0:     if (!subpixelBits && !(mat.getType() & ~SkMatrix::kTranslate_Mask)) {
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     // mapRect supports negative scales, so we eliminate those first
michael@0:     if (mat.getScaleX() < 0 || mat.getScaleY() < 0) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     SkRect dst;
michael@0:     SkIRect isrc = { 0, 0, width, height };
michael@0: 
michael@0:     {
michael@0:         SkRect src;
michael@0:         src.set(isrc);
michael@0:         mat.mapRect(&dst, src);
michael@0:     }
michael@0: 
michael@0:     // just apply the translate to isrc
michael@0:     isrc.offset(SkScalarRoundToInt(mat.getTranslateX()),
michael@0:                 SkScalarRoundToInt(mat.getTranslateY()));
michael@0: 
michael@0:     if (subpixelBits) {
michael@0:         isrc.fLeft <<= subpixelBits;
michael@0:         isrc.fTop <<= subpixelBits;
michael@0:         isrc.fRight <<= subpixelBits;
michael@0:         isrc.fBottom <<= subpixelBits;
michael@0: 
michael@0:         const float scale = 1 << subpixelBits;
michael@0:         dst.fLeft *= scale;
michael@0:         dst.fTop *= scale;
michael@0:         dst.fRight *= scale;
michael@0:         dst.fBottom *= scale;
michael@0:     }
michael@0: 
michael@0:     SkIRect idst;
michael@0:     dst.round(&idst);
michael@0:     return isrc == idst;
michael@0: }
michael@0: 
michael@0: // A square matrix M can be decomposed (via polar decomposition) into two matrices --
michael@0: // an orthogonal matrix Q and a symmetric matrix S. In turn we can decompose S into U*W*U^T,
michael@0: // where U is another orthogonal matrix and W is a scale matrix. These can be recombined
michael@0: // to give M = (Q*U)*W*U^T, i.e., the product of two orthogonal matrices and a scale matrix.
michael@0: //
michael@0: // The one wrinkle is that traditionally Q may contain a reflection -- the
michael@0: // calculation has been rejiggered to put that reflection into W.
michael@0: bool SkDecomposeUpper2x2(const SkMatrix& matrix,
michael@0:                          SkPoint* rotation1,
michael@0:                          SkPoint* scale,
michael@0:                          SkPoint* rotation2) {
michael@0: 
michael@0:     SkScalar A = matrix[SkMatrix::kMScaleX];
michael@0:     SkScalar B = matrix[SkMatrix::kMSkewX];
michael@0:     SkScalar C = matrix[SkMatrix::kMSkewY];
michael@0:     SkScalar D = matrix[SkMatrix::kMScaleY];
michael@0: 
michael@0:     if (is_degenerate_2x2(A, B, C, D)) {
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0:     double w1, w2;
michael@0:     SkScalar cos1, sin1;
michael@0:     SkScalar cos2, sin2;
michael@0: 
michael@0:     // do polar decomposition (M = Q*S)
michael@0:     SkScalar cosQ, sinQ;
michael@0:     double Sa, Sb, Sd;
michael@0:     // if M is already symmetric (i.e., M = I*S)
michael@0:     if (SkScalarNearlyEqual(B, C)) {
michael@0:         cosQ = 1;
michael@0:         sinQ = 0;
michael@0: 
michael@0:         Sa = A;
michael@0:         Sb = B;
michael@0:         Sd = D;
michael@0:     } else {
michael@0:         cosQ = A + D;
michael@0:         sinQ = C - B;
michael@0:         SkScalar reciplen = SkScalarInvert(SkScalarSqrt(cosQ*cosQ + sinQ*sinQ));
michael@0:         cosQ *= reciplen;
michael@0:         sinQ *= reciplen;
michael@0: 
michael@0:         // S = Q^-1*M
michael@0:         // we don't calc Sc since it's symmetric
michael@0:         Sa = A*cosQ + C*sinQ;
michael@0:         Sb = B*cosQ + D*sinQ;
michael@0:         Sd = -B*sinQ + D*cosQ;
michael@0:     }
michael@0: 
michael@0:     // Now we need to compute eigenvalues of S (our scale factors)
michael@0:     // and eigenvectors (bases for our rotation)
michael@0:     // From this, should be able to reconstruct S as U*W*U^T
michael@0:     if (SkScalarNearlyZero(SkDoubleToScalar(Sb))) {
michael@0:         // already diagonalized
michael@0:         cos1 = 1;
michael@0:         sin1 = 0;
michael@0:         w1 = Sa;
michael@0:         w2 = Sd;
michael@0:         cos2 = cosQ;
michael@0:         sin2 = sinQ;
michael@0:     } else {
michael@0:         double diff = Sa - Sd;
michael@0:         double discriminant = sqrt(diff*diff + 4.0*Sb*Sb);
michael@0:         double trace = Sa + Sd;
michael@0:         if (diff > 0) {
michael@0:             w1 = 0.5*(trace + discriminant);
michael@0:             w2 = 0.5*(trace - discriminant);
michael@0:         } else {
michael@0:             w1 = 0.5*(trace - discriminant);
michael@0:             w2 = 0.5*(trace + discriminant);
michael@0:         }
michael@0: 
michael@0:         cos1 = SkDoubleToScalar(Sb); sin1 = SkDoubleToScalar(w1 - Sa);
michael@0:         SkScalar reciplen = SkScalarInvert(SkScalarSqrt(cos1*cos1 + sin1*sin1));
michael@0:         cos1 *= reciplen;
michael@0:         sin1 *= reciplen;
michael@0: 
michael@0:         // rotation 2 is composition of Q and U
michael@0:         cos2 = cos1*cosQ - sin1*sinQ;
michael@0:         sin2 = sin1*cosQ + cos1*sinQ;
michael@0: 
michael@0:         // rotation 1 is U^T
michael@0:         sin1 = -sin1;
michael@0:     }
michael@0: 
michael@0:     if (NULL != scale) {
michael@0:         scale->fX = SkDoubleToScalar(w1);
michael@0:         scale->fY = SkDoubleToScalar(w2);
michael@0:     }
michael@0:     if (NULL != rotation1) {
michael@0:         rotation1->fX = cos1;
michael@0:         rotation1->fY = sin1;
michael@0:     }
michael@0:     if (NULL != rotation2) {
michael@0:         rotation2->fX = cos2;
michael@0:         rotation2->fY = sin2;
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }