• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
gaimplay

Rotation matrix ortho-normalization

40 posts in this topic

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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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


0

Share this post


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

Share this post


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

Share this post


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

0

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Good luck using those quaternions for everything.

good luck using stawman tactics for everything.
0

Share this post


Link to post
Share on other sites
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.32+0.52+0.52+0.52 = 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
0

Share this post


Link to post
Share on other sites
Quote:
Original post by Eelco
good luck using stawman tactics for everything.


explain: "stawman tactics"
0

Share this post


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


0

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  
Followers 0