Faster matrix inversion by using additional knowledge
Needs ReviewPublic
Actions

Authored by Jacques Lucke (JacquesLucke) on Jun 4 2018, 12:50 PM.

Details

Reviewers

Summary

I saw this commit recently: rB01c75c3765eb305b1a99b794c1d40ad224b071c6
When digging into the code I was surprised that in many (all?) cases a full inverse of a 4x4 matrix is calculated although that is not really necessary. Very often additional knowledge can make calculating the inverse easier. E.g. most matrices that are inverted are just transformation/affine matrices, so the fourth row is just (0 0 0 1).

This patch includes two utility math functions for matrix inversion. I did not test them extensively yet (mainly because I don't know a good way to test them in Blenders source code atm...). First I wanted to ask if this is something that should be included into Blender.

It might also be possible to find a better inversion function for matrices that just contain translation, rotation and scale (no shearing etc).

https://math.stackexchange.com/questions/152462/inverse-of-transformation-matrix

Diff Detail

Repository: rB Blender

Event Timeline

Jacques Lucke (JacquesLucke) created this revision.Jun 4 2018, 12:50 PM

Jacques Lucke (JacquesLucke) edited the summary of this revision. (Show Details)

That's a good idea!

I expect that auto-detecting if the matrix is affine in invert_m4_m4 and then using this faster code would preserve most of the speedup. Then we can immediately benchmark and benefit from it.

source/blender/blenlib/intern/math_matrix.c
941	I wouldn't bother with this one. For the other commit I looked for places where we can be sure the matrix is orthonormal, and they are quite difficult to find. So I don't expect this to improve performance enough to justify the code complexity / potential for bugs.

This revision now requires changes to proceed.Jun 5 2018, 3:45 PM

Thanks for the feedback, I'll change the code for the invert_m4_m4 function later today.

I was thinking about how this could be improved even more. Ideally we could calculate the inverse directly from the loc/rot/scale in some cases (from my experience, calculating a real inverse just based on a matrix is rarely necessary in practice).

I just found that an object already already has (two?) imat attributes. My suggestion is that we always update this matrix whenever the obmat matrix is updated. Calculating the inverse at that point should be fairly cheap. Even more so because we already have the sine/cosine of the angles of the rotation. The same might be true for bones, haven't checked that yet. With that change many of the calls to invert_m4_m4 can be removed.

Here is how to calculate the inverse based on translation (T), rotation (R) and scale (S):
(T * R * S)^-1 = S^-1 * R^-1 * T^-1 = S^-1 * R^T * T^-1

S^-1 is fast to calculate, just put the reciprocal of the axis scales into the diagonal.
R^T is fast to calculate because we already have the sin/cos of the angles (btw: calculating the sin of a value when you already have the cos of that value can be made faster under the assumption that sqrt is faster than cos (sin^2 x + cos^2 x = 1))
T^-1 is fast to calculate, just put the negated axis translations into the last column of the matrix.

Now the only thing that's left are two matrix products which can also be optimized if necessary because the matrices contain many zeros.

The invert_m4_m4 checks if the matrix is affine and chooses which invert function to use.
I don't know how to test the performance in Blender, so you'll have to do this. Maybe the invert_m3_m3 matrix should also use the Eigen implementation?

Jacques Lucke (JacquesLucke) marked an inline comment as done.Jun 6 2018, 3:49 PM

Jacques Lucke (JacquesLucke) mentioned this in D4285: Fix T60996: Dyntopo flood fill fails due to missing ob->imat.Jan 30 2019, 5:51 PM