Jump to content
  • Advertisement
Sign in to follow this  
Richy2k

Solution to matrix creep.

This topic is 4703 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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...

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.


Share this post


Link to post
Share on other sites
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);
Or some variation thereof. It doesn't have the same behavior as iterative Gram-Schmidt, but it might compare favorably performance-wise if that's your concern.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!