Jump to content

  • Log In with Google      Sign In   
  • Create Account


Rotation matrix ortho-normalization


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
40 replies to this topic

#1 gaimplay   Members   -  Reputation: 122

Like
0Likes
Like

Posted 25 October 2004 - 01:04 AM

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.

Sponsor:

#2 Eelco   Members   -  Reputation: 301

Like
0Likes
Like

Posted 25 October 2004 - 01:13 AM

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.

#3 Charles B   Members   -  Reputation: 863

Like
0Likes
Like

Posted 25 October 2004 - 04:20 AM

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.


#4 Dmytry   Members   -  Reputation: 1147

Like
1Likes
Like

Posted 25 October 2004 - 04:29 AM

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.

#5 Eelco   Members   -  Reputation: 301

Like
0Likes
Like

Posted 25 October 2004 - 04:41 AM

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.

#6 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 25 October 2004 - 06:31 AM

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.




#7 Dmytry   Members   -  Reputation: 1147

Like
0Likes
Like

Posted 25 October 2004 - 06:56 AM

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.

#8 Eelco   Members   -  Reputation: 301

Like
0Likes
Like

Posted 25 October 2004 - 07:31 AM

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.

#9 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 25 October 2004 - 07:48 AM

As I understood the matrix was loosing orthogonality. But yes you are correct normalizing the third row will make it more robust.

In your second point I think you are one mixing the oranges and the apples not me.
Quaternions are not transformation matrices and they are not rotation matrices.

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”

You also mention the product of two quaternion is easy and fast, however that meaning less operation for most graphics application.

Say you have rotation Matrices A, B, C;
And a quaternion function M = f(q) where q is a quaternion and M in a rotation matrix

if equality 1) A = B * C is true
and 2) qa = qb * qc is also true

this lead to 3) A = f(qb) * f(qc) which is true

if you calculate the matrix M = f(qa) you will see that it is different than matrix A

so you get f(qa) != A
f(qb * qc) != f(qb) * f(qc)

The rotation matrix mapped by the product of two quaternion is different that the product of the matrices mapped by the quaternions. So hinting that the product of two quaternions is fast as a replacement of matrix multiplication is just wrong and misleading.

Finally who say that scaling can not be apply to matrices?



#10 Eelco   Members   -  Reputation: 301

Like
0Likes
Like

Posted 25 October 2004 - 08:42 AM

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.

#11 scgames   Members   -  Reputation: 1973

Like
0Likes
Like

Posted 25 October 2004 - 09:02 AM

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.

#12 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 25 October 2004 - 09:09 AM

“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.

“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

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.


#13 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 25 October 2004 - 09:19 AM

“AP, I didn't quite follow all of your argument against quats, but I'm not sure if they're very well founded”

I gave you a mathematical prove of what I said, operations with quaternion are not a win in turns of floating point operation, they are convenient for interpolating matrices, and also they take less space. But they are not practical for transformation manipulations.

If you chose then as your building block, that’s fine, but recommending then as the superior solution to general transformation matrices is just wrong


#14 Dmytry   Members   -  Reputation: 1147

Like
0Likes
Like

Posted 25 October 2004 - 09:21 AM

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|2 . 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.

#15 Eelco   Members   -  Reputation: 301

Like
0Likes
Like

Posted 25 October 2004 - 09:29 AM

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.

#16 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 25 October 2004 - 09:48 AM

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

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.

“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.


#17 Eelco   Members   -  Reputation: 301

Like
0Likes
Like

Posted 25 October 2004 - 10:41 AM

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.

#18 Dmytry   Members   -  Reputation: 1147

Like
0Likes
Like

Posted 25 October 2004 - 10:58 AM

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.

#19 MichaelT   Members   -  Reputation: 214

Like
0Likes
Like

Posted 25 October 2004 - 11:11 AM

(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.


#20 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 25 October 2004 - 11:18 AM

Well, I am not trying to convince you or anyone to not using quaternion. You can used quaternion all you want, just don¡¦t expresses your opinions as facts.

I do too used quats for what they are good for, but fortunately I had ground the point when quats are the panacea to all transformation problems.

I did proved my points mathematically you did not get it, I also stated neither quaternion nor matrices are superior to each other, but influencing the community with you ideas is just wrong.

Btw camera is one of those things you do not want to use quats. ļ

Good luck using those quaternions for everything.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS