Improve performance of matrix inversion.

src/utils/SkMatrix44.cpp

 /*
  * Copyright 2011 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkMatrix44.h"
 
 static inline bool eq4(const SkMScalar* SK_RESTRICT a,
@@ skipping 464 matching lines @@
         }
         return true;
     }
     if (this->isScaleTranslate()) {
         if (0 == fMat[0][0] * fMat[1][1] * fMat[2][2]) {
             return false;
         }
         if (inverse) {
             sk_bzero(inverse->fMat, sizeof(inverse->fMat));
 
-            inverse->fMat[3][0] = -fMat[3][0] / fMat[0][0];
-            inverse->fMat[3][1] = -fMat[3][1] / fMat[1][1];
-            inverse->fMat[3][2] = -fMat[3][2] / fMat[2][2];
+            double invXScale = 1 / fMat[0][0];
+            double invYScale = 1 / fMat[1][1];
+            double invZScale = 1 / fMat[2][2];
 
-            inverse->fMat[0][0] = 1 / fMat[0][0];
-            inverse->fMat[1][1] = 1 / fMat[1][1];
-            inverse->fMat[2][2] = 1 / fMat[2][2];
+            inverse->fMat[3][0] = -fMat[3][0] * invXScale;
+            inverse->fMat[3][1] = -fMat[3][1] * invYScale;
+            inverse->fMat[3][2] = -fMat[3][2] * invZScale;
+
+            inverse->fMat[0][0] = invXScale;
+            inverse->fMat[1][1] = invYScale;
+            inverse->fMat[2][2] = invZScale;
             inverse->fMat[3][3] = 1;
 
             inverse->setTypeMask(this->getType());
         }
         return true;
     }
 
     double a00 = fMat[0][0];
     double a01 = fMat[0][1];
     double a02 = fMat[0][2];
     double a03 = fMat[0][3];
     double a10 = fMat[1][0];
     double a11 = fMat[1][1];
     double a12 = fMat[1][2];
     double a13 = fMat[1][3];
     double a20 = fMat[2][0];
     double a21 = fMat[2][1];
     double a22 = fMat[2][2];
     double a23 = fMat[2][3];
     double a30 = fMat[3][0];
     double a31 = fMat[3][1];
     double a32 = fMat[3][2];
     double a33 = fMat[3][3];
 
+    if (!(this->getType() & kPerspective_Mask)) {

[reed1, 2013/08/20 15:14:13]

At some point we should consider breaking each of the (somewhat long) sections
into helper functions (that get inlined), just to make the code more readable.

e.g.
   invert3x4()
   invertpersp()

Not public functions, just ways to organize our impl

+        // If we know the matrix has no perspective,
+        // then its bottom row is (0, 0, 0, 1).

[jvanverth1, 2013/08/20 14:16:54]

Assuming our indexing is (row, column) this should be right-most column instead
of bottom row.

+        // We can use this information to save a lot
+        // of arithmetic that would be used to compute
+        // the inverse of a general matrix.
+
+        SkASSERT(a03 == 0);
+        SkASSERT(a13 == 0);
+        SkASSERT(a23 == 0);
+        SkASSERT(a33 == 1);
+
+        double b00 = a00 * a11 - a01 * a10;
+        double b01 = a00 * a12 - a02 * a10;
+        double b03 = a01 * a12 - a02 * a11;
+        double b06 = a20 * a31 - a21 * a30;
+        double b07 = a20 * a32 - a22 * a30;
+        double b08 = a20;
+        double b09 = a21 * a32 - a22 * a31;
+        double b10 = a21;
+        double b11 = a22;
+
+        // Calculate the determinant
+        double det = b00 * b11 - b01 * b10 + b03 * b08;
+
+        if (dabs(det) < TOO_SMALL_FOR_DETERMINANT) {
+            return false;
+        }
+        if (NULL == inverse) {
+            return true;
+        }
+        double invdet = 1.0 / det;
+
+        b00 *= invdet;
+        b01 *= invdet;
+        b03 *= invdet;
+        b06 *= invdet;
+        b07 *= invdet;
+        b08 *= invdet;
+        b09 *= invdet;
+        b10 *= invdet;
+        b11 *= invdet;
+
+        inverse->fMat[0][0] = SkDoubleToMScalar(a11 * b11 - a12 * b10);
+        inverse->fMat[0][1] = SkDoubleToMScalar(a02 * b10 - a01 * b11);
+        inverse->fMat[0][2] = SkDoubleToMScalar(b03);
+        inverse->fMat[0][3] = 0;
+        inverse->fMat[1][0] = SkDoubleToMScalar(a12 * b08 - a10 * b11);
+        inverse->fMat[1][1] = SkDoubleToMScalar(a00 * b11 - a02 * b08);
+        inverse->fMat[1][2] = SkDoubleToMScalar(-b01);
+        inverse->fMat[1][3] = 0;
+        inverse->fMat[2][0] = SkDoubleToMScalar(a10 * b10 - a11 * b08);
+        inverse->fMat[2][1] = SkDoubleToMScalar(a01 * b08 - a00 * b10);
+        inverse->fMat[2][2] = SkDoubleToMScalar(b00);
+        inverse->fMat[2][3] = 0;
+        inverse->fMat[3][0] = SkDoubleToMScalar(a11 * b07 - a10 * b09 - a12 * b06);
+        inverse->fMat[3][1] = SkDoubleToMScalar(a00 * b09 - a01 * b07 + a02 * b06);
+        inverse->fMat[3][2] = SkDoubleToMScalar(a31 * b01 - a30 * b03 - a32 * b00);
+        inverse->fMat[3][3] = 1;
+
+        inverse->setTypeMask(this->getType());
+        return true;
+    }
+
     double b00 = a00 * a11 - a01 * a10;
     double b01 = a00 * a12 - a02 * a10;
     double b02 = a00 * a13 - a03 * a10;
     double b03 = a01 * a12 - a02 * a11;
     double b04 = a01 * a13 - a03 * a11;
     double b05 = a02 * a13 - a03 * a12;
     double b06 = a20 * a31 - a21 * a30;
     double b07 = a20 * a32 - a22 * a30;
     double b08 = a20 * a33 - a23 * a30;
     double b09 = a21 * a32 - a22 * a31;
@@ skipping 33 matching lines @@
     inverse->fMat[1][2] = SkDoubleToMScalar(a32 * b02 - a30 * b05 - a33 * b01);
     inverse->fMat[1][3] = SkDoubleToMScalar(a20 * b05 - a22 * b02 + a23 * b01);
     inverse->fMat[2][0] = SkDoubleToMScalar(a10 * b10 - a11 * b08 + a13 * b06);
     inverse->fMat[2][1] = SkDoubleToMScalar(a01 * b08 - a00 * b10 - a03 * b06);
     inverse->fMat[2][2] = SkDoubleToMScalar(a30 * b04 - a31 * b02 + a33 * b00);
     inverse->fMat[2][3] = SkDoubleToMScalar(a21 * b02 - a20 * b04 - a23 * b00);
     inverse->fMat[3][0] = SkDoubleToMScalar(a11 * b07 - a10 * b09 - a12 * b06);
     inverse->fMat[3][1] = SkDoubleToMScalar(a00 * b09 - a01 * b07 + a02 * b06);
     inverse->fMat[3][2] = SkDoubleToMScalar(a31 * b01 - a30 * b03 - a32 * b00);
     inverse->fMat[3][3] = SkDoubleToMScalar(a20 * b03 - a21 * b01 + a22 * b00);
-    inverse->dirtyTypeMask();
-
+    
     inverse->dirtyTypeMask();
     return true;
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
 void SkMatrix44::transpose() {
     SkTSwap(fMat[0][1], fMat[1][0]);
     SkTSwap(fMat[0][2], fMat[2][0]);
     SkTSwap(fMat[0][3], fMat[3][0]);
@@ skipping 264 matching lines @@
     dst[SkMatrix::kMScaleX]  = SkMScalarToScalar(fMat[0][0]);
     dst[SkMatrix::kMSkewX]  = SkMScalarToScalar(fMat[1][0]);
     dst[SkMatrix::kMTransX] = SkMScalarToScalar(fMat[3][0]);
 
     dst[SkMatrix::kMSkewY]  = SkMScalarToScalar(fMat[0][1]);
     dst[SkMatrix::kMScaleY] = SkMScalarToScalar(fMat[1][1]);
     dst[SkMatrix::kMTransY] = SkMScalarToScalar(fMat[3][1]);
 
     return dst;
 }