Improve performance of matrix inversion.

src/utils/SkMatrix44.cpp

Index: src/utils/SkMatrix44.cpp
===================================================================
--- src/utils/SkMatrix44.cpp	(revision 10801)
+++ src/utils/SkMatrix44.cpp	(working copy)
@@ -482,13 +482,17 @@
         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());
@@ -513,6 +517,70 @@
     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;
@@ -566,9 +634,8 @@
     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;
 }