Rotation matrix ortho-normalization

google gramm schmidth ortogonalization (spelling is probably boxxored, so that could be a problem with google...)

basicly it comes down to picking one vector as base direction, then substract all from the second vector that isnt orthonormal to the first, and substract from the third the parts that are not normal to the first aswell as the second, then normalize everything, and there you go.

Consider storing dynamic referentials (where you accumulate transfos) as Quaternions, AxisAngle or EulerAngles if possible. Renormalizing matrices will necessarilly be more unstable. Then use conversions when required to pass something to DX9 for instance.

Quote:

Original post by gaimplay I'm trying to figure out how to orthonormalize a rotation matrix so that the basis vectors would be unit length and perpendicular. This is to combat floating point precision errors that accumulate in the matrix. The way I figured it, all you need to do is take a unit vector, transform it by your current rotation matrix, then inspect the resulting vector and build a some kind of a scaling matrix that makes the resulting vector unit length, then concatenate this matrix with your current one to fix it. If I'm way off course, it would be great if someone could post some pseudo code or actual code to demonstate the correct algorithm. I'm currently using DX9 but can't find a built-in function to do this kind of thing. Any help appreciated.

As others have said, use quaternions. Anyway, it can be done as

Column1=Normalized(CrossProduct(Column2,Column3));
Column2=Normalized(CrossProduct(Column3,Column1));
// and ther you don't really need to Column3=Normalized(CrossProduct(Column1,Column2));
Column3=Normalized(Column3);

Where ColumnN contains nth column of 3x3 rotation matrix as vector. If you use 4x4 matrix, it's submatrix in top-left corner.
You can do the same with rows if you want.
Note that one column/row may be selected to be distorted the least.

Also, don't do it when matrix is unchanged, or your things might start slowly turn.

Quote:

Original post by Charles B Consider storing dynamic referentials (where you accumulate transfos) as Quaternions, AxisAngle or EulerAngles if possible. Renormalizing matrices will necessarilly be more unstable. Then use conversions when required to pass something to DX9 for instance.

/agree.

quaternions are a much better way to store orientations than matrices. the only thing matrices are best for is transforming coordinates actually, so they should only be generated just before transforming your stuff ideally.

Quote:

Original post by Anonymous Poster Gramm-Schmidt Orthogonalization Too complicated, the two cross product much faster and practical Column1=Normalized(CrossProduct(Column2,Column3)); Column2=Normalized(CrossProduct(Column3,Column1)); Not need to renormalize Column3 as it is already part of the matrix. Elco quote: "quaternions are a much better way to store orientations than matrices. the only thing matrices are best for is transforming coordinates actually, so they should only be generated just before transforming your stuff ideally." You should disclaim this by saying is you opnion not a fact. Quatenions are good for key frame interpolation and physics but they are in fact a terrible way to store transformation matrices. Just think of a scene graph with tenth of children in which the application have to transform and rotate vectors several time. Rotation of a vector by a quaternion while it is possible it is about 8 time more expensive than rotation by the matrix equivalent. If you do not belief me then you look and two mayor graphics apis OpneGL and direct3d they use matrices to form matrix stack, not quaternion.

1: it's needed to normalize 3rd column, like i said. Otherwise it will not be unit-length.

1: matrices VS quaternions:
You're mixing apples with oranges.
Matrices is good to store arbitrary transforms, including rotation. It's their power and weakness. If you apply many transforms, matrices becomes non-orthonormal. Quaternions is good for storing variable rotations, because them can store only rotation and scale, and therefore CAN'T store unwanted transform (and one normalization it's everything you need).
Before doing transformation, quaternions is usually converted to matrices. In my math lib, there's even no function for rotating vector using quaternion.
Also,quaternion*quaternion multiplication is fast. It's faster to obtain inverse rotation with quaternion.

Quote:

Original post by Anonymous Poster Gramm-Schmidt Orthogonalization Too complicated, the two cross product much faster and practical Column1=Normalized(CrossProduct(Column2,Column3)); Column2=Normalized(CrossProduct(Column3,Column1)); Not need to renormalize Column3 as it is already part of the matrix. Elco quote: "quaternions are a much better way to store orientations than matrices. the only thing matrices are best for is transforming coordinates actually, so they should only be generated just before transforming your stuff ideally." You should disclaim this by saying is you opnion not a fact. Quatenions are good for key frame interpolation and physics but they are in fact a terrible way to store transformation matrices. Just think of a scene graph with tenth of children in which the application have to transform and rotate vectors several time. Rotation of a vector by a quaternion while it is possible it is about 8 time more expensive than rotation by the matrix equivalent. If you do not belief me then you look and two mayor graphics apis OpneGL and direct3d they use matrices to form matrix stack, not quaternion.

actually transforming a vector with a quad is only about twice as slow. but you wont be doing that anyway. generating a matrix from a quad is rather easy. so thats why im saying: store rotations as quaternions, for each primitive group, calc the transform matrix after traversing bone hierachies and such, and use this to transform everything. since quat*quat is faster than matrix*matrix this is probably faster aswell even while taking into account the quattomatrix.

the reason apis and videocards dont work that way is because they have to provide more flexibility than just rotation. however, things like scaling can be added in a quaternion based engine just aswell, and in the end youre still using less memory than with a matrix.

Quote:

Original post by Anonymous Poster The same lost of orthogonality that happens to matrices when you multiplying then together also happen to quaternions. You said yourself when you mention “and one normalization it's everything you need”

?
a quat is always ortho, if not unit length. the problem of loss of orthogonality comes from rotationmatrices being overdefined. a quaternion hence cant suffer from this by definition.

and one normalization is quite a lot faster than renomalizing and reothogonizing a matrix.

AP, I didn't quite follow all of your argument against quats, but I'm not sure if they're very well founded. Others have explained the advantages, but I'll reiterate a couple of them.

Yes, quats also need to be re-normalized occasionally. But renormalizing a quaternion is considerably less expensive than re-orthonormalizing a matrix. So quats are a win no matter what.

Quats concatentate rotations just like (3x3) matrices do. And, quaternion multiplication is cheaper than matrix multiplication. If you have a series of rotations to concatenate (such as in a skeletal system), quats are again a win.

Also, interpolating quaternions is easier and more elegant than interpolating matrices. Slerp is invaluable in cases such as keyframe animation or inverse kinematics. Even without all the other factors, this by itself is a sufficient selling point for quaternions.

They also take up less space - 4 floats instead of 9 for orientation information. This can make a difference on certain platforms, if you're dealing with numerous keyframes.

As far as I know, no one rotates vectors directly with quaternions, so the speed of that operation is more or less irrelevant. Instead, you convert the quat to a matrix, but only when you need it. And the conversion is fairly fast as well - less expensive (I think - I'd have to check) than a matrix multiplication.

Anyway, those are some arguments in favor of quats. Pretty much anything you can do with a quaternion you can do with a matrix. But in my experience it's generally easier, faster and more elegant to use a quaternion.

1:There's no such thing as non-orthonormal quaternion.
Quaternion may only be not unit length. It only have to be re-normalized exactly like 4d vector.

If quaternion is not unit-length, and quaternion-to-matrix conversion is done correctly , you'll get matrix that not only rotate but also scale by |q|² . For camera, it doesn't matter to have precisely unit-length quaternion, because scaling only affect your z-buffer values a bit. So quaternion can be normalized using fast inaccurate inverse square root that costs as much as addition.

2: quaternion (0.5,0.5,0.5,0.5) is perfectly valid unit-length quaternion that stores rotation around axis 1,1,1 by 120 degrees. I instantly computed that in mind without any trouble. It's yet another adwantage of quaternions.
For example,
Quaternion(1,1,1,1)
rotates around same axis by same angle and also scales 4 times.

3: i don't have to choose something as building block. I use quaternions where apporiate, and use matrices where apporiate.
If i need rotation only, i use quaternion. If i need rotation and translation, i use "coordsys". If i need angular velocity, i use vector. If i need arbitrary linear transform on 3d space i use 3x4 matrix. If i need arbitrary projection transform(transform with division), i use 4x4 matrix.

Quote:

Original post by Anonymous Poster “a quat is always ortho, if not unit length.” Not really, take quaternion a(0.5, 0.5, 0.5, 0.5) When multiplied repeatedly by another quat say b(cos(a/2), 0, sin(a/2), 0) Will introduces and error of the same nature than the product of the equivalent matrices, So in both case normalization is required. In the case of quaternion what you get is not longer a quaternion, it is forced to map into a neighbor quaternion by the normalization which nothing than a projection. So quaternions, just like orthonormal matrices, do lose orthogonality as result of round of errors.

youre confusion orthonomality with unit length. a completely random quat just also might cause scaling, nothing more to it. since a quat only defines rotation (3 DOF's) and uniform scaling (one DOF), and has 4 components, there is no overdefinition, hence EVERY possible quaternion is a valid and orthonomal one, although only a subset is also non-scaling.

Quote:

“and one normalization is quite a lot faster than renomalizing and reothogonizing a matrix.” True, but you have to take the whole picture. The normalization in faster on a single quaternion, but given that this lost of orthogonality can only happens as the result of a multiplication by anther quaternion. When you need to get the product of two matrices from two quaternions the operation is up to 5 to 6 time slower

i really dont get what youre saying here. could you give a more concrete exmaple of how error supposedly builds up faster in quats, making things a whopping 5 to 6 times slower? if i do my math correct, that would imply quats need to be normalized 20 times as much as matrices! (assuming quat normalization is 3-4 times as fast as matrix fixing, which is reasonable)

Quote:

My point is: quaternions are good for storing rotations and to encode animations, but there are not practical as build block for a graphic engine. I am not saying quaternions cannot be used to represent rotations, but if you are going to recomend that option you need to explain everything not just a bias opinion.

sorry i still think i have defended my position better than you did yours.

if youre not interested in shearing (almost never) or nonuniform rotation, quats are simply > *. but even if you are, i still think its more elegant to keep these things seperated in quats for rotation, and vectors for shearing, translation and scaling, but i admit that might just be a personal thing due to my hang for elegance, and not really be more efficient.

Quote:

Original post by Anonymous Poster Try to get a matrix from this quat q(0.3, 0.5, 0.5, 0.5) and tell me what you get.

i fail how to see its relevant, but it simply will be some perfectly orthogonal rotationmatrix with a slight downscale.

why?

Quote:

Try to get the aiming vector from a bone way down a skeleton with all transformations are encoded as quaternion, and do the same with matrices.

what the aiming vector? ive never heard the term before. but anyway forward aswell as backward transformations are very possible with quaternions, if thats your concern. easier than with matrices btw.

Quote:

“i still think its more elegant to keep these things seperated in quats for rotation, and vectors for shearing, translation and scaling, but i admit that might just be a personal thing due to my hang for elegance, and not really be more efficient.” I already proved quaternion are by no mean faster for transformation manipulation and elegance is in the eye of the beholder, I personally think and a quaternion and a position is less elegant and less efficient, than a single transformation matrix. (one operation, one member representaion for a matrix) Apparently all video card manufactures, Microsoft directx, Opengl, not to mention all graphic packages like Max, soft image, Maya, Softimage XSI ect. Agree with me.

you did no such thing in this thread. all you did was spouting some random stats (x is 6 times faster than y, is that your idea of a proof?), which were way off btw, and misinterpreted aswell.

we also went over the apis already. in short: they have to stick with matrices because they cant limit themselves to rotation and scaling only. the difference being that a gameengine can, and is flexible enough to adapt in the rare case more is needed.

Also, all those API's don't implement physics, collisions, and other things, even including cameras. Read my other reply on these boards about quaternions for camera. It's so simple to do timebased camera rotation with quaternion, yet it isn't simple with matrices.

And, 0.3,0.5,0.5,0.5 .
It rotates around axis 1,1,1 by angle 2*atan(sqrt(3)/0.6) (with some time i can even find angle without using calculator)
, and scales by 0.84
Again, computed in mind.

It's not like "they use quaternions because they don't know matrices". Nothing like that, we know how to work with matrices and how to work with quaternions, and we use quaternions where apporiate. Eelco recently even made thread where said that storing rotation velocity in quaternions sucks , and i totally agreed, rotation velocity should be storen in vector, or vector and angle.
Bot storing rotation in quaternions is good and elegant.

(Dmytry)"...computed in mind..."

My math teacher could calc arbitrary divisions down to the 5th decimal in his mind with little effort ;) That said, not all (actually few) have this talent, so don't take that for granted.

AP: Good luck with matrix camera, btw [grin]
Can you implement camera like in my The Galaxy?

Quaternion it's just more elegant way to store orthogonal transform. I use quaternions in places where if i woulda have used matrix i woulda need to reorthonormalize.

Quote:

Original post by Anonymous Poster Good luck using those quaternions for everything.

good luck using stawman tactics for everything.

Quote:

Original post by MichaelT (Dmytry)"...computed in mind..." My math teacher could calc arbitrary divisions down to the 5th decimal in his mind with little effort ;) That said, not all (actually few) have this talent, so don't take that for granted.

In this case it's easy. It scales by it's length squared;
0.3²+0.5²+0.5²+0.5² = 0.09+0.75 = 0.84

Tangent of half of angle is
sqrt(0.75)/0.3 = sqrt(3/4)/0.3 = sqrt(3)/2/0.3 = sqrt(3)/0.6

Quote:

Original post by Eelco good luck using stawman tactics for everything.

explain: "stawman tactics"

/**
create a nonunit quaternion from rotation matrix
martix must contain only rotation (not scale or shear)
the result quaternion length is numerical stable
*/
inline void from_matrix( const matrix33& mtx )
{
typedef float mtx_elm[3][3];
const mtx_elm& m = mtx.m;
float tr = m[0][0] + m[1][1] + m[2][2]; // trace of martix
if (tr > 0.0f){ // if trace positive than "w" is biggest component
set( m[1][2] - m[2][1], m[2][0] - m[0][2], m[0][1] - m[1][0], tr + 1.0f );
}else // Some of vector components is bigger
if( (m[0][0] > m[1][1] ) && ( m[0][0] > m[2][2]) ) {
set( 1.0f + m[0][0] - m[1][1] - m[2][2], m[1][0] + m[0][1],
m[2][0] + m[0][2], m[1][2] - m[2][1] );
}else
if ( m[1][1] > m[2][2] ){
set( m[1][0] + m[0][1], 1.0f + m[1][1] - m[0][0] - m[2][2],
m[2][1] + m[1][2], m[2][0] - m[0][2] );
}else{
set( m[2][0] + m[0][2], m[2][1] + m[1][2],
1.0f + m[2][2] - m[0][0] - m[1][1], m[0][1] - m[1][0] );
}
}



/**
set the rotation to matrix
*/
inline void to_matrix( matrix33& m )const {
float wx, wy, wz, xx, yy, yz, xy, xz, zz, x2, y2, z2;
float s = 2.0f/norm(); // 4 mul 3 add 1 div
x2 = x * s; y2 = y * s; z2 = z * s;
xx = x * x2; xy = x * y2; xz = x * z2;
yy = y * y2; yz = y * z2; zz = z * z2;
wx = w * x2; wy = w * y2; wz = w * z2;

m.m[0][0] = 1.0f - (yy + zz);
m.m[1][0] = xy - wz;
m.m[2][0] = xz + wy;

m.m[0][1] = xy + wz;
m.m[1][1] = 1.0f - (xx + zz);
m.m[2][1] = yz - wx;

m.m[0][2] = xz - wy;
m.m[1][2] = yz + wx;
m.m[2][2] = 1.0f - (xx + yy);
}


http://www.gamedev.ru/articles/graph/20040603.zip

Quote:

Original post by MichaelT Quote: Original post by Eelco good luck using stawman tactics for everything. explain: "stawman tactics"

i think he meant strawman arguments...

BTW, minorlogic: Privet, videl tvoi formuli kasatelno quaternionov na euclideanspace.com, kruto i vnushaet! (Hello, man! Readed your quaternion derivations on euclideanspace.com, pretty impressive!)