Efficient 4x4 matrix inverse (affine transform)?

You should be able to exploit the fact that the matrix is affine to speed things up over a full inverse. Namely, if your matrix looks like this.

You should be able to exploit the fact that the matrix is affine to speed things up over a full inverse. Namely, if your matrix looks like this A = M be 0 1 where A is 4x4, M is 3x3, be is 3x1, and the bottom row is (0,0,0,1), then inv(A) = inv(M) -inv(M) * be 0 1 Depending on your situation, it may be faster to compute the result of inv(A) * x instead of actually forming inv(A). In that case, things simplify to inv(A) * x = inv(M) * (x - b) 1 = 1 where x is a 3x1 vector (usually a 3D point).

Lastly, if M represents a rotation (i.e. Its columns are orthonormal), then you can use the fact that inv(M) = transpose(M). Then computing the inverse of A is just a matter of subtracting the translation component, and multiplying by the transpose of the 3x3 part.

Note that whether or not the matrix is orthonormal is something that you should know from the analysis of the problem. Checking it during runtime would be fairly expensive; although you might want to do it in debug builds to check that your assumptions hold. Hope all of that is clear...

So the first formula you got from "blockwise inversion" (en.wikipedia. Org/wiki/Invertible_matrix)? Or is there another mental trick?

I'm not quite sure about the inv(A) * x = inv(M) * (x - b). First, they're different sizes - do you remove a row from A on the left or add a row on the right? Second, I'm not sure how that equation comes about.

Third, I'm not sure what you're solving for in that equation. Oliver keeps mentioning not computing inverses symbolically, but I don't know what that means - I need the inverse to do inverse transform. If you have time I'd like to know.

– Budric Apr 13 '10 at 15:32 I edited the inv(A) * x formula to make the dimensions clearer. The first formula was from en.wikipedia. Org/wiki/Affine_transformation.

Forgetting about affine transforms for a minute, in general, when you're solving A*x = b, you want the solution inv(A)*b. But often times you don't need to actual form inv(A), just compute what the product would be. Back to affine transforms, in 3D applications, you might not actually need the inverse of the matrix, you just want the inverse transform acting on (multiplying) a vector.

If that's the case, then using the formula might be faster. – celion Apr 13 '10 at 18:22 Even if you do need to store the matrix inverse, you can use the fact that it's affine to reduce the work computing the inverse, since you only need to invert a 3x3 matrix instead of 4x4. And if you know that it's a rotation, computing the transpose is much faster than computing the inverse, and in this case, they're equivalent.

– celion Apr 13 '10 at 18:24 And here's a better explanation of what I meant by computing inv(A) * x: johndcook. Com/blog/2010/01/19/dont-invert-that-matrix (the author is a frequent poster on SO). – celion Apr 13 '10 at 18:38 Clear now.

Very interesting. – Budric Apr 13 '10 at 21:54.

2x2 determinants. Split the matrix in half vertically and compute every 2x2 in both the upper and lower half. One of these smaller determinants is used in every term you'll need for the bigger computation and they each get reused.

Also, don't use a separate determinant function - reuse the sub-determinants you computed for the adjoint to get the determinant. Oh, just found this. There are some improvements you can make knowing its a certain kind of transform too.

Thanks, this saves me a lot of time! – Budric Apr 12 '10 at 19:04 Very fast, good explanation. Appears to work (haven't run it against a full regression test).

Thanks again. – Budric Apr 12 '10 at 20:37 +1 for the link; however, I think it's a mistake to compute those inverses symbolically... you must realize how many unnecessary multiplications/additions you are performing. It's probably ok as long as this part of the code is not the bottleneck.

– Olivier Apr 13 '10 at 13:45 I use 4x4s for a lot of things, so I prefer the generalized inverse. Like I said, you can do better with specific types of transform. The linked paper is still useful for doing the 3x3 inverse the questioner seems to be using.

And you can do even better still if you know the 3x3 is a pure rotation - IIRC it's inverse is the transpose. – phkahler Apr 14 '10 at 13:30.

Just in case someone would like to save some typing, here's an AS3 version I wrote based on page 9 (more efficient version of Laplace Expansion Theorem) of the link posted above by phkahler: public function invert() : Matrix4 { var m : Matrix4 = new Matrix4(); var s0 : Number = i00 * i11 - i10 * i01; var s1 : Number = i00 * i12 - i10 * i02; var s2 : Number = i00 * i13 - i10 * i03; var s3 : Number = i01 * i12 - i11 * i02; var s4 : Number = i01 * i13 - i11 * i03; var s5 : Number = i02 * i13 - i12 * i03; var c5 : Number = i22 * i33 - i32 * i23; var c4 : Number = i21 * i33 - i31 - i23; var c3 : Number = i21 * i32 - i31 * i22; var c2 : Number = i20 * i33 - i30 * i23; var c1 : Number = i20 * i32 - i30 * i22; var c0 : Number = i20 * i31 - i30 * i21; // Should check for 0 determinant var invdet : Number = 1 / (s0 * c5 - s1 * c4 + s2 * c3 + s3 * c2 - s4 * c1 + s5 * c0); m. I00 = (i11 * c5 - i12 * c4 + i13 * c3) * invdet; m. I01 = (-i01 * c5 + i02 * c4 - i03 * c3) * invdet; m.

I02 = (i31 * s5 - i32 * s4 + i33 * s3) * invdet; m. I03 = (-i21 * s5 + i22 * s4 - i23 * s3) * invdet; m. I10 = (-i10 * c5 + i12 * c2 - i13 * c1) * invdet; m.

I11 = (i00 * c5 - i02 * c2 + i03 * c1) * invdet; m. I12 = (-i30 * s5 + i32 * s2 - i33 * s1) * invdet; m. I13 = (i20 * s5 - i22 * s2 + i23 * s1) * invdet; m.

I20 = (i10 * c4 - i11 * c2 + i13 * c0) * invdet; m. I21 = (-i00 * c4 + i01 * c2 - i03 * c0) * invdet; m. I22 = (i30 * s4 - i31 * s2 + i33 * s0) * invdet; m.

I23 = (-i20 * s4 + i21 * s2 - i23 * s0) * invdet; m. I30 = (-i10 * c3 + i11 * c1 - i12 * c0) * invdet; m. I31 = (i00 * c3 - i01 * c1 + i02 * c0) * invdet; m.

I32 = (-i30 * s3 + i31 * s1 - i32 * s0) * invdet; m. I33 = (i20 * s3 - i21 * s1 + i22 * s0) * invdet; return m; } This successfully produced an identity matrix when I multiplied various 3D transformation matrices by the inverse returned from this method. I'm sure you can search/replace to get this into whatever language you'd like.

I believe the only way to compute an inverse is to solve n times the equation: A x = y, where y spans the unit vectors, i.e. , the first one is (1,0,0,0), the second is (0,1,0,0), etc. (Using the cofactors (Cramer's rule) is a bad idea, unless you want a symbolic formula for the inverse.) Most linear algebra libraries will allow you to solve those linear systems, and even to compute an inverse. Example in python (using numpy): from numpy.

Linalg import inv inv(A) # here you go.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.