20 replies to this topic

[george7378]

If I have three vectors which are initially perpendicular to eachother, how can I re-orthogonalise them when I rotate them to make sure they're still perpendicular? I guess it has something to do with checking that the dot product is zero, but I'm not sure beyond that. Thanks!

[Hodgman]

If they were ok before you rotated them, then they should be ok after you rotate them, except for really small numerical errors. These errors are only a problem if you keep applying rotations to a matrix frame after frame, instead of rebuilding it from scratch each time, so most of the time this isn't required.

 

If it is required, you can use the cross product to find a vector that's perpendicular to two others. Pick 2 of your vectors and cross them to regenerate the 3rd. Then use the 1st and the 3rd to regenerate the 2nd. Each time you regenerate one, you can check it's dot product with the original version; it should be very close to 1.0 or -1.0. If it's negative, then flip the regenerated vector so it matches the direction/handedness of the original.

Edited by Hodgman, 13 March 2013 - 09:18 AM.

[Milcho]

If you rotate all three vectors by the same rotation matrix (or any other method), they should preserve their orthogonality.

If you're interested in just verifying that they're still orthogonal, it is as simple as checking the three dot products to see if they're equal to 0.

 

If you want to re-orthogonalize them, you have to do a bit more work. First, you can't arbitrarily re-orthogonalize them. 

here's two general cases, given the three potentiall non-orthogonal vectors A, B and C. (these are the vectors after rotation here)

 

First if A and B are perpendicular ( or A and C, or B and C - these are all equivalent cases), you can calculate the third vector by doing

C = A cross B or B cross A - depending on handedness. Same goes for the case if A and C are perpendicular, or if B and C are perpendicular.

 

Second general case is if no two vectors are perpendicular to each other. If that's the case, you have to pick one vector which you want to remain unchanged - usually this is one vector who's orientation you know is correct. 

 

Let's say you pick vector A as the 'correct' one. 

You can then obtain a new orthogonal vector B' by doing

B' = A cross C

even though C is not perpendicular to A, A cross C will yield a vector that IS perpendicular to A (as well as to C)

Then you can obtain the new C' by doing

C' = A cross B' 

 

In that case your three new vectors are A, B' and C' - which are now orthogonal. You'll also have to keep track of handedness of the system, because otherwise you might end up with a B' or C' that is oriented in the opposite direction of the originals.

Same goes if you pick B and C, just substitute the proper letters above.

 

 

Mind that you might have to re-normalize the vectors if you want to keep them unit and if there's a chance that the rotated vectors are no longer of unit length.

[george7378]

My setup at the moment is that I have an 'orientation' matrix which I update every frame by an incremental amount. I am using it to control the yaw, pitch and roll of an object about its local axes, each of which are defined by a vector (i.e. I have an up, forward and right vector set to define the orientation of the axes). It's these axes that I'm trying to ensure remain perpendicular to eachother. I have to rotate each vector by a different matrix because they are each rotating around eachother (i.e. to pitch forward, I have to rotate around my 'right' vector, then to roll left I have to rotate about my new 'forward' vector, so they all depend on eachother). It's pretty awkward, but it seems to work.

 

I'll take my 'up' axis as always being correct and regenerate each axis around that one. I checked and the deviations are very small (a tiny fraction of a degree which gradually increases over time), but I'd rather do it properly and re-orthogonalise them each time.

[eppo]

If you store the orientation as a quaternion, it's as simple as re-normalizing the quaternion.

[Norman Barrows]

 

 

 

void normalize()

{

/*

Column1=Normalized(CrossProduct(Column2,Column3));

Column2=Normalized(CrossProduct(Column3,Column1));

Column3=Normalized(Column3);

Prot is global player's rotation matix

*/

D3DXVECTOR3 v1,v2,v3,   // 3 original axes

            v4,v5,v6;   // 3 ortho normal axes

v1.x=Prot._11;

v1.y=Prot._21;

v1.z=Prot._31;

v2.x=Prot._12;

v2.y=Prot._22;

v2.z=Prot._32;

v3.x=Prot._13;

v3.y=Prot._23;

v3.z=Prot._33;

D3DXVec3Cross(&v4,&v2,&v3);

D3DXVec3Normalize(&v4,&v4);

D3DXVec3Cross(&v5,&v3,&v4);

D3DXVec3Normalize(&v5,&v5);

D3DXVec3Normalize(&v6,&v3);

Prot._11=v4.x;

Prot._21=v4.y;

Prot._31=v4.z;

Prot._12=v5.x;

Prot._22=v5.y;

Prot._32=v5.z;

Prot._13=v6.x;

Prot._23=v6.y;

Prot._33=v6.z;

}

 

this is gram-schmitt re-ortho-normalization

 

i usually assume the forward vector (local z) to be the correct one. this will eliminate "course drift" due to re-normalization. IE any change in orientation due to re-normalization shows up as a change in roll, not heading.

 

this still doesn't get you pixel perfect rotations at 1600 x 900 with floats. very close, but you don't come back to exactly the same pixel every time when you do a 360 around a local axis when the ship is at an arbitrary starting orientation.

 

I suspect quats are really the way to go for 3 axes of rotational freedom.

 

but i have done flight sims using orientation matrices, and they do work pretty well, if you can get them accurate enough.

[Norman Barrows]

 

 

In prep for a new title planned, i revisited the "how to store orientation" question.

 

I found that the graphics engine uses matrices, movement uses a direction vector, AI (at least mine) uses Euler angles, and turning is most easily done as a matrix multiply or a quaternion multiply. turning has issues with floating point precision and matrices. the REAL question is: are floating point quats more accurate than floating point mats ? i suspect the answer is no. in any case, D3DX has math routines to convert most types to a matrix, and can convert between mats and quats. as for mats vs quats, assuming both are equally inaccurate, quats are less work to re-normalize, maybe. their big bonus seem to be in the ability to easily tween for animation purposes. great if you're doing canned ani's or tweening between last turn's and this turn's position in a frame independent system (which would always cause the graphics to lag behind the simulation, wouldn't it?).

 

in the end, i decided that for the moment, ortho-normalized mats are the way to go to store orientation. you can pass it directly to the graphics engine, the 3rd column vector is your local z axis for movement, and a mat mul followed by the above normalize() routine handles turning within the limits of the precision implemented. it may be possible to store orientation in a long double mat, use that for turning (have to roll your own long double mat mul), then copy the results to a D3DXMATRIX for drawing. but inaccuracies would still eventually creep in. when storing a rotation in radians, a float gets you 6 decimal places of accuracy, a long double gets you 14. with a float you can do maybe 3 360's before your axes are totally whacked.

 

I considered storing orientation as eulers, using mats to turn, then extracting eulers from the mat. but irregardless of what data structure holds the orientation, you have to use floating point matrix multiply  or quaternion multiply to turn. so imprecision will most likely still be an issue. given that every time i see postings on this topic, those of the "quat camp" say "just renormalize" (witness above in this thread), odd are quats are no more precise and also need to need re-normalized. a quick test will determine the truth once and for all. i've seen this issue of how to store orientation debated on formus since compuserv gamedev back in the late 80's. I would think by now the correct answer would be general gamedev knowledge. but 3 degree rotational freedom still seems to be a black art to most gamedevs, probably due to the fact that its only required for the most complex simulators.

 

perhaps i'll take a little time out and test mats vs quats. i have a flight sim engine prototype just for testing such things. it was built to test normalize().

 

i wonder where the drift shows up in a quat. given that a quat conglomerates a unit direction vector and a rotation into a V4, i suspect its spread over all directions.

 

has anyone out there used quats? are they more accurate? can you get pixel perfect 360's at arbitrary rotations with quats?

 

while thinking about it, i determined that about the only thing not in D3DX required for using matrices is a routine to extract Euler angles from a rotation matrix, for use by AI (heading to target, relative heading to target,  in arc of fire, etc).

 

My first big hit game was a space flight sim. it too used fwd, up and right unit vectors to store orientation. it was written before directx existed.

 

here's how to get Euler angles from a matrix:

 

ROTATION MATRIX TO HEADING AND ANGLE:

rotate v1=0,0,1 by ship's rotation matrix to get V2.   // this rotates the local z axis out to v2 where it should be pointing.

heading =atan(v2.x/v2.z)                   //  heading is calculated from the projection of v2 onto the x-z plane.

rotate v2 by -heading just calculated to get v3   // this rotates v2 back into the y-z plane, yielding v3 .

angle = -atan(v3.y/v3.z)      // angle of inclination is calculated from v3, which is v2 rotated back to the y-z plane. note the negative sign. x rotation is down, angle is up.

 

so you store your orientation as a mat, use normalize after a turn, use your 3rd column (local z, or k unit vector) * speed = your displacement vector for moving, pass the mat directly to directx for drawing, and use matrix to heading/angle to get angles for AI calculations.

 

eventually i'll have to test quats. when i do i'll post the results. right now i'm bogged down in designing quest/mission generators for another title.

[Norman Barrows]

From another thread here

 

http://www.gamedev.net/topic/640889-pixel-perfect-local-rotations-and-quats-vs-mats/

 

i've learned that quats also have precision errors, but they do not accumulate as quickly.

 

it looks like fixed point is the way to do it, then convert to mat for drawing.

 

that would mean rolling your own fixed point versions of mat mul or whatever method used to turn.

 

error would eventually creep in most likely.

 

looks like re-ortho normalize is still required.

[Paradigm Shifter]

Everything has precision errors.

 

All that's required if you store orientation as a quaternion is renormalising once per frame. When you construct a matrix from the quat it will be orthonormal (within accuracy limits).

 

Error only "creeps in" if you never renormalise or reorthonormalise.

 

Using fixed point won't solve anything, don't roll your own fixed point functions just to get rounding issues and worse performance.

[george7378]

Hey - I'm interested in using quaternions, but I don't see how I'd do it - at the moment I use 3 vectors to represent up, forward and right, and I rotate incrementally about those axes while also rotating them each time (it's a local yaw, pitch and roll transformation). How could I do local rotations with quaternions?

[Norman Barrows]

Hey - I'm interested in using quaternions, but I don't see how I'd do it - at the moment I use 3 vectors to represent up, forward and right, and I rotate incrementally about those axes while also rotating them each time (it's a local yaw, pitch and roll transformation). How could I do local rotations with quaternions?

 

 

same as with a matrix (at least in D3D)

 

orientation = local_rotation * orientation.   but you use quat mul instead of mat mul. check the docs, it in there, D3DX reference, math functions, as i recall.

 

using quats should cause error to accumulate more slowly. but quats or mats, you'll still need to normalize from time to time.

 

you can use quat to mat routine to get your mat for drawing, and to get your column vectors (i,j,k or right,up,fwd) for movement, or to use the above code to convert to Eulers if needed, etc.

[george7378]

I've read a bit about them and it seems like they hold 4 values only - an axis and an angle. What I don't understand is how I can use a quaternion to hold the entire orientation of my object? Surely I'd still have to use my three local axis vectors, and hence I'd still have the same problems of keeping them orthogonal?

[haegarr]

I've read a bit about them and it seems like they hold 4 values only - an axis and an angle.

Yes: Quaternions are defined by 4 scalars. No: They don't hold an axis and an angle. There is another rotation representation that is called "axis/angle representation" and that actually hold, well, an axis and an angle. IMHO it is best not to try to interpret some geometric meaning into quaternions; look at them as being a mathematical construct in your toolbox.

In fact, each representation has some degree of freedom: In 3D, a rotation matrix has 9, a quaternion has 4, an axis/angle has 4. Because rotation only has 3, you need to enforce some constraints on the representations, or else your representation doesn't mean a pure rotation.

In the case of rotation matrices the column/row vectors are pairwise orthogonal and each one is a unit vector. Hence the process of "re-ortho-normalization", which carries both orthogonalization as well as normalization in its name.

In the case of quaternions they need to be of unit length. Hence, to be precise, one has to talk about "unit-quaternions" and not just quaternions when referring to pure rotation.

Because of this, quaternions are not less prone to numerical errors per se, but they are more stable in that numerical imprecision has less effect on still representing a useable rotation. So re-normalisating quaternions needs to be done less often, and ensuring that single constraint is less work than ensuring the 6 constraints on rotation matrices.

That said, using quaternions and re-normalization (from time to time) and on-the-fly to-matrix conversion would be sufficient for sure.

 

What I don't understand is how I can use a quaternion to hold the entire orientation of my object?

The problem of lacking a geometrical interpretation suitable for humans, doesn't mean that unit-quaternions don't work. A unit-quaternions "holds the entire orientation" by its nature. Use conversions from or into, resp., other rotation representations where meaningful.

Edited by haegarr, 07 April 2013 - 04:20 AM.

[george7378]

OK, so here's my code at the moment for doing local axis rotations:

 

D3DXVec3Cross(&right, &up, &forward); //Reorthogonalise right
D3DXVec3Cross(&forward, &right, &up); //Reorthogonalise forward
D3DXVec3Normalize(&up, &up); D3DXVec3Normalize(&right, &right); D3DXVec3Normalize(&forward, &forward); //Renormalise the vectors
 
D3DXMATRIX matYaw; D3DXMatrixRotationAxis(&matYaw, &up, OrientationDelta.x); //Build a yaw rotation axis
D3DXMATRIX matPitch; D3DXMatrixRotationAxis(&matPitch, &right, OrientationDelta.y); //Build a pitch rotation axis
D3DXMATRIX matRoll; D3DXMatrixRotationAxis(&matRoll, &forward, OrientationDelta.z); //Build a roll rotation axis
 
D3DXVec3TransformCoord(&forward, &forward, &matYaw); D3DXVec3TransformCoord(&right, &right, &matYaw); //Apply the yaw transformation to the relevant vectors
D3DXVec3TransformCoord(&forward, &forward, &matPitch); D3DXVec3TransformCoord(&up, &up, &matPitch); //Apply the pitch transformation to the relevant vectors
D3DXVec3TransformCoord(&right, &right, &matRoll); D3DXVec3TransformCoord(&up, &up, &matRoll); //Apply the roll transformation to the relevant vectors

OrientationMatrix *= matPitch*matYaw*matRoll; //Adjust the orientation matrix

 

So I use 3 vectors - up, right and forward, and rotate them by a small amount  using matrix rotation axes. I don't see how using quaternions would change this. I'd still have to store the three axis vectors, I'd still have to rotate them a small amount each frame, and I'd still have to build a final orientation matrix to rotate my model. Would it help with re-orthogonalising and normalising? What would it improve?

[Norman Barrows]

What I don't understand is how I can use a quaternion to hold the entire orientation of my object?

 

if you look at the definition of a quat, you'll see that they sort of kludge the angle and i,j,k components together. thus they do encapsulate a direction vector and a roll. but as haegarr said, they do not have a direct geometric interpretation that allows one to determine values by inspection, the way you can look at the components of your forward vector, picture in your mind what direction that is and say "ok, i'm pointing this way".   actually, i have yet to inspect the definition in detail, perhaps they do have some semi-intuitive geometric representation in something like spherical coordinates or something.

[haegarr]

Let aside whether using quaternions makes sense in your use case, IMO your code snippet shows a construction flaw:

 

...
D3DXVec3TransformCoord(&forward, &forward, &matYaw); D3DXVec3TransformCoord(&right, &right, &matYaw); //Apply the yaw transformation to the relevant vectors
D3DXVec3TransformCoord(&forward, &forward, &matPitch); D3DXVec3TransformCoord(&up, &up, &matPitch); //Apply the pitch transformation to the relevant vectors
D3DXVec3TransformCoord(&right, &right, &matRoll); D3DXVec3TransformCoord(&up, &up, &matRoll); //Apply the roll transformation to the relevant vectors

OrientationMatrix *= matPitch*matYaw*matRoll; //Adjust the orientation matrix

 

The 3 row vectors of a rotation (row) matrix already define the side, up, and forward vectors of the local frame w.r.t. the parental frame. That means that your vectors right, forward, and up are logically part of your OrientationMatrix.

 

Now, you compute the new OrientationMatrix as:

  OrientationMatrix_n+1 = OrientationMatrix_n * matPitch * matYaw * matRoll

 

But you compute the new vectors as:

  OrientationVectors_n+1 = OrientationVectors_n * matYaw * matPitch * matRoll

 

That is obviously not the same when remembering that matrix multiplications isn't commutative. Hence the both orientation representations you use will be different, although logically they should be the same.

[Norman Barrows]

The 3 row vectors of a rotation (row) matrix already define the side, up, and forward vectors of the local frame w.r.t. the parental frame.

 

is it rows or columns? i can never remember. been way too long since i took linear.

[george7378]

Hi guys,

 

haegarr - I just noticed that yes, there is an error in the order. I really don't know why! Anyway, I've corrected it now.

 

I also looked into what you both said about getting the vectors from the matrix, and it turns out that this works:

 

 

    up = D3DXVECTOR3(OrientationMatrix._21, OrientationMatrix._22, OrientationMatrix._23);
    forward = D3DXVECTOR3(OrientationMatrix._31, OrientationMatrix._32, OrientationMatrix._33);
    right = D3DXVECTOR3(OrientationMatrix._11, OrientationMatrix._12, OrientationMatrix._13);

 

...so it looks like the individual vectors are stored in the rows. At least I think that's how it is - am I right in saying that, for example, _12 corresponds to row 1, column 2? So it turns out that I don't need to store the vectors like I was doing - they're already there! Of course, that doesn't solve the problem of orthonormalising them, although I messed about a bit with quaternions and I came up with this:

 

 

    D3DXVECTOR3 up(OrientationMatrix._21, OrientationMatrix._22, OrientationMatrix._23);
    D3DXVECTOR3 forward(OrientationMatrix._31, OrientationMatrix._32, OrientationMatrix._33);
    D3DXVECTOR3 right(OrientationMatrix._11, OrientationMatrix._12, OrientationMatrix._13);
 
    D3DXQUATERNION quatYaw, quatPitch, quatRoll; //Quaternions to hold local rotation info
    D3DXQuaternionRotationAxis(&quatYaw, &up, OrientationDelta.x); //Build a yaw rotation axis
    D3DXQuaternionRotationAxis(&quatPitch, &right, OrientationDelta.y); //Build a pitch rotation axis
    D3DXQuaternionRotationAxis(&quatRoll, &forward, OrientationDelta.z); //Build a roll rotation axis
    OrientationQuat *= quatYaw*quatPitch*quatRoll; D3DXQuaternionNormalize(&OrientationQuat, &OrientationQuat);
    D3DXMatrixRotationQuaternion(&OrientationMatrix, &OrientationQuat);

 

Is this the sort of thing that I'm after? I removed the current orthogonalising routine I've got (cross products, etc...) and put in the D3DXQuaternionNormalize() part.

Edited by george7378, 07 April 2013 - 02:11 PM.

[Hodgman]

The 3 row vectors of a rotation (row) matrix already define the side, up, and forward vectors of the local frame w.r.t. the parental frame.

is it rows or columns? i can never remember. been way too long since i took linear.

it's either, depending on whether you pretend that a vec3 is a mat3x1 or a mat1x3. The correct transform matrices for each of those arbitrary conventions will be transposed compared to the other.
IIRC, D3DX uses the opposite convention than what mathematicians tend to use, for some strange reason.

[Jason Z]

 

The 3 row vectors of a rotation (row) matrix already define the side, up, and forward vectors of the local frame w.r.t. the parental frame.

is it rows or columns? i can never remember. been way too long since i took linear.

it's either, depending on whether you pretend that a vec3 is a mat3x1 or a mat1x3. The correct transform matrices for each of those arbitrary conventions will be transposed compared to the other.
IIRC, D3DX uses the opposite convention than what mathematicians tend to use, for some strange reason.

If you look at the equations that are in the D3D docs, it is always a vector on the left of the matrix it is being multiplied by.  In mathematic terms, this means that you have something like these sizes:

 

1x4 * 4x4 = 1x4

 

Since there is only one row (the first number is the number of rows) in the vector, they are normally referred to as row vectors.  OpenGL typically uses the opposite convention, so that can be confusing if you aren't watching for it.