🔒 Locked

calculating the "difference" between two transform matrices?

Started by ejtosage Dec 29, 2009 at 9:38 PM 2 replies 29.3k views

Original Post

Dec 29, 2009 at 9:38 PM

I'm reading a book on preprocessing models for a game, and I've got a question about one of the techniques described. The author suggests collapsing a model's hierarchy if two nodes are static relative to one another, to reduce the number of draw calls. This makes sense: if two nodes never move or always move together, there's no need for them to be two separate draw calls. Then he suggests that when creating a lower LOD version of the mesh, you may want to take things a step further, and merge nodes if they move separately, but you won't notice. For example, one might want to merge a characters upper arm and lower arm together. Even if they move separately, at a low LOD the player is not likely to notice. This makes sense too, but I get tripped on on the math of how to calculate if two nodes are "imperceptibly different." The book suggests calculating a "difference transformation" for every frame of animation. This is a matrix that maps from the space of one node to the space of another. So far so good. It then says that you should calculate the "maximum difference between these." This maximum difference is then compared to a threshold, and if it is less, the nodes can be merged. Logically, this makes sense. I'm trying to find the frame of animation where the two nodes are most different, and then check to see if that difference is less than my threshold. If so, I can merge them. So, apparently I'm meant to be calculating a scalar value from two matrices that represents how "different" the two are. How is this done? For example, one difference transformation might be a translation of (100,0,0), and another might be a translation of (0,100,0). I suppose "difference" could be the average distance between the unit x y and z vectors transformed through each of the two matrices. Or maybe the average "error" of each vert in the two nodes, were they merged together? I've read and reread the book, and it's still not clicking. Any suggestions?

Nanoha

Dec 30, 2009 at 7:29 AM

I would say this would be an artists job. You can create lods programatically but I'm sure an artist could do this much better. Same for your animations.

Is there any difference between progratically creating lower detailed animations for merged model parts? Sounds to me like a very difficult task where as an artist could probably make lower detailed models (with fewer moving parts where needs be) and appropriate animations.

I have no experience with anyhitng like this so take what I say with a grain of salt. Also when was this book published?

As for your original problem, if you only have rotation matrices (no scaling/translating, easy enough to remove the translation part I think) then you could convert that to an axis angle. You can then use the angle as your single value (if somehting only moves 1 degree maybes it not noticable but if it moves 90 degrees it would be).

cache_hit

Dec 30, 2009 at 9:59 AM

Call the matrices M1 and M2. Compute the matrix required to take an object from reference frame M1 to reference frame M2. This can be computed as Inverse(M1)*M2. If M1 and M2 are rigid, then so is this, which is convenient. Anyway, that matrix is made up of some combination of rotations, transforms, and scalings. Decompose the matrix into it's rotation, scaling, and transform parts and use some heuristic defined by you to compute a number out of that.

A simple heuristic would be this:

The rotation will be somewhere in the range [0,360) degrees. Based on the actual rotation you compute (the axis doesn't really matter), linearly interpolate from 1 (which corresponds to a rotation of 0), to some value I (which corresponds to a value of 360). Here, I is an importance factor which I'll discuss in a second.

Translation will be somewhere from 0 units to infinity. Again, interpolate from 1 (0 translation) to some value J (anything over some threshold).

Similarly for scaling, 1 to K.

These values I,J,K define the relative importance of each operation versus each other. What values of translation and rotation produce an equally "different" object, when taken in isolation? You can determine where the scalar function should match up on different values of rotation, scaling, and translation, and then choose the I,J,K appropriately so the result of the interpolation satisfies that equality

haegarr

Dec 30, 2009 at 11:04 AM

Assume there are 2 parts of the model, with the local co-ordinate frame matrices A and B. Then a common reference frame is to be chosen, e.g. the model's local frame, and the both matrices are to be re-computed w.r.t. that reference frame. Let's assume for the following that A and B are already given w.r.t. the model's local frame.

Then expressing the part A in the space of part B is done by the matrix
M := B^-1 * A
in the case of using column vectors, as cache_hit has already posted, or else
M := A * B^-1
in the case of using row vectors. It makes no differences whether A in B or B in A is used.

Then compute the said matrix for each animation step and compute the difference of pairs of them
D_i,j := M_i - M_j for all i,j; i!=j
For 2 identical matrices, D would become the zero matrix 0. The author suggests to use the maximum of all difference matrices. A way to do so is to compute a matrix norm (see e.g. wiki.org) from each D, so that
d_i,j := ||D_i,j||
and the maximum will be the matrix with indices {i,j} where
d_i,j == max{ d_i,j for all i,j }

The simplest norm would perhaps be the Maximum norm, but I think that the Frobenius norm would be better suited. It is comparable to the length of a vector. However, if the maximum norm value is above a threshold, the both parts should not be merged together.

Of course you can apply the above algorithm separately to the rotational, scaling (or rotational/scaling together) and translational sub-matrices. In that case you can use different thresholds to weight the one or other kind of transformation higher than the others.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.