Solution to matrix creep.
Author
In a project I am working on we are busy sorting out the physics engine, and integrating it. There is one horrible bug we have already gotten so far though - Matrix creep. You spin a box for a while, and it will be rotated with an invalid matrix, causing it to misshape horrible and either grow or shrink.
I have read somewhere (where I forgot) that making the matrix orthogonal will be the solution, but the algorithm to do this (Gram-Schmidt) doesn't seem very good due to it being iterative, and I'm looking for something fast. Since its the 3x3 matrix that is causing the problem, would I be right in thinking Quaternions can be the solution? They appear to be a fair amount easier to normalize that matrices are, although I'm unsure if its worth while due to the fact you use a square root to accomplish it.
Anyone else got any possible solutions, work arounds, or other algorithms out there?
You won't (normally) need to correct the matrix after every single modification so in practice you could (probably) get away with checking/correcting each matrix every N physics updates (and experiment to find N, which could evern be dependant on the angular velocity etc).
If you use quaternions the normalization will be cheaper, but every time you apply the transformation (quaternion or matrix) to a vector the quaternion transformation is substantially more expensive. Unless you're chaining a lot of transformations together (e.g. inside an animation system), or are very pushed for memory, matrix with occasional ortho-normalisation is probably faster. In my opinion...
If you use quaternions the normalization will be cheaper, but every time you apply the transformation (quaternion or matrix) to a vector the quaternion transformation is substantially more expensive. Unless you're chaining a lot of transformations together (e.g. inside an animation system), or are very pushed for memory, matrix with occasional ortho-normalisation is probably faster. In my opinion...
Quote:Original post by MrRowl
matrix with occasional ortho-normalisation is probably faster. In my opinion...
Probably....
However, quaternions have other properties that might make them desirable....
BTW: I use quaternions in my physics system, normalize them every frame, and convert them to a matrix before sending the transforms to the rendering system.
Ortho-normalization of matrices is _much_ more costly (see e.g. Gram-Schmitt) than normalization of quaternions. Applying a quaternion to a point is slightly more costly than applying a matrix. However, applying many points, or else concatenating several affine trafos one should convert the quat into a matrix (which produces an overhead normally neglectible w.r.t. the overall computational effort). I personally prefer quats for storing and computing rotations, but perform almost all transformations later by matrices.
There's a discussion of this with some operation counts for the transformations here.
However, it is actually possible to formulate the quaternion-vector transformation in 30 flops (18 mults + 12 adds), not 40 as Dave Eberly has, by doing a bit of algebra first. This compares with 15 flops for matrix transformation - so quite a big difference. I don't know about actual timing differences - the smaller quaternion size is probably more cache friendly etc.
However, it is actually possible to formulate the quaternion-vector transformation in 30 flops (18 mults + 12 adds), not 40 as Dave Eberly has, by doing a bit of algebra first. This compares with 15 flops for matrix transformation - so quite a big difference. I don't know about actual timing differences - the smaller quaternion size is probably more cache friendly etc.
Another option might be a simple cross-product orthogonalization:
Vector3 x,y,z;matrix.GetBasisVectors(x,y,z);z.Normalize();y = z.Cross(x);y.Normalize();x = y.Cross(z);matrix.LoadBasisVectors(x,y,z);
If you seperate the rotation then you can just extract the axis-angle then build a new axis-angle rotation matrix.
Quote:Original post by haegarr
Ortho-normalization of matrices is _much_ more costly (see e.g. Gram-Schmitt) than normalization of quaternions.
Also it can sometimes be difficult to implement Gram-Schmitt because it can become numerically unstable because of the rounding errors.
Re-normalization of a matrix is a problem in both, efficiency and stability, I agree. The way jyk proposed above is good in efficiency, right you are, but it relies in that the z axis (or which ever) is correctly aligned, and alignes the other axes accordingly to this assumption. Gram-Schmidt suffers less on this problem due to its iterative nature, if I remember correctly, but may suffer from numerical stability, as etothex has mentioned correctly (and, of course, it is costly).
So IMHO quaternions are somewhere in-between. Most physics engines I know use quaternions for representing rotations, also because they cost less when performing integration.
So IMHO quaternions are somewhere in-between. Most physics engines I know use quaternions for representing rotations, also because they cost less when performing integration.
Another solution may be the following: The deformed rotation matrix could be seen as a concatenation of the (wanted) rotation matrix and a "stretch" matrix.
To decompose a general linear matrix (i.e. the 3x3 matrix that may show a rotation, scaling, and shearing when thinking in affine transformations) one of the methods that may be applied is the so-called Polar Decomposition.
This decomposition results in
Q * aI * S
where the rotation R could be simply determined from the matrix Q and the scalar a (which will be either +1 or -1, if I remember right).
Polar Decomposition is more costly than quaternion normalization, of course. I don't know an efficiency comparison of the Polar Decomposition and the Gram-Schmidt orthonormalization. I only know that Polar Decompostion is both a more efficient and a more meaningful way in comparison to some other decompositions (like SVD).
However, could anybody here comment this way as a possibility of normalization, and complete the information with efficiency and numerical stability issues of Polar Decomposition?
To decompose a general linear matrix (i.e. the 3x3 matrix that may show a rotation, scaling, and shearing when thinking in affine transformations) one of the methods that may be applied is the so-called Polar Decomposition.
This decomposition results in
Q * aI * S
where the rotation R could be simply determined from the matrix Q and the scalar a (which will be either +1 or -1, if I remember right).
Polar Decomposition is more costly than quaternion normalization, of course. I don't know an efficiency comparison of the Polar Decomposition and the Gram-Schmidt orthonormalization. I only know that Polar Decompostion is both a more efficient and a more meaningful way in comparison to some other decompositions (like SVD).
However, could anybody here comment this way as a possibility of normalization, and complete the information with efficiency and numerical stability issues of Polar Decomposition?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
