Sign in to follow this  
Richy2k

Solution to matrix creep.

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
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
Quote:
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.
You are absolutely right about that. If the angular displacement isn't too great this can be a reasonable approximation. (For example, I think the Doom 3 physics library uses this method for 3x3 matrix orthogonalization.) For the sake of simplicity I gave the example using a 'fixed forward' axis. In my own code however, the orthogonalization function is set up to perform n steps of iterative Gram-Schmidt first, where n is an argument and can be zero, and then finalizes with the cross-product method. For this latter step (which is the only step if n is zero), the caller can specify which of the three axis' direction is unchanged. For example, if the object is a spaceship you might choose to leave its forward direction unchanged by the orthogonalization.

As this thread shows, there are various ways to do it, and I may switch to something else in the future. But for now I like the above method as it gives the option of quick 'n dirty if you don't mind the approximation, or iterative if for some reason you need to converge on the solution.

Share this post


Link to post
Share on other sites
An interesting method is Eric Raible's Matrix Orthogonalization from Graphics Gems I. His methods iterates and finds a new orthogonal ("orthonormal") matrix close to the original matrix.

Converting a distorted matrix to a quaternion and back to a matrix can also work OK (though for physics applications, it's best to use quaternions and convert once to matrix for point transformations).

An untried idea to prevent bias when using the cross-product (or Gram-Schmidt dot-projections) would be to interpolate the old matrix (basis vectors) to the new orthogonal matrix using weights based on axis order: the first axis would be used directly, the next axis would get a large weight, and the last axis would get a smaller weight (as it will have changed the most).

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
in my opinion, simply not using matricies for repeated computation is preferable. in my experience, most time spent in physics is not in matricies or integration, but in collision detection and response, so regenerating a couple matricies from euler angles (or quats) each frame is not an unbearable overhead, and saves you the successive numerical errors which inevitably creep into successive matrix concatenations.

james

Share this post


Link to post
Share on other sites
It seems that using quaternions has given excellent results, little creep at all, even without normalising. Tried using orthogonalising the matrices....but that didn't do an aweful lot at all, just adds more overhead.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this