Forum discussion about conversion of matrix to quaternion here.

geometeer

2012-03-09 22:24:24 PST

The opening of page matrixToQuaternion has two major errors. It explains two conditions, saying ● the matrix is orthoginal (det(matrix)=1) ● trace = m00 + m11 + m22 + 1 > 0 (the matrix is special orthogonal which cannot represent a reflection component) completely wrongly. A 3×3 matrix is orthogonal (not 'orthoginal') if each of its columns is a unit vector (dot product with itself is 1) and any two disticnt ones are orthogonal (they have dot product 0). This implies that the determinant is +1 or -1, but the determinant can be 1 for a non-othogonal matrix: for instance, ⎡ 1 1 1 ⎤ ⎢ 0 1 1 ⎢ ⎣ 0 0 1 ⎦ has det = 1 but is not orthogonal. A _special_ orthogonal matrix -- describing a rotation -- has determinant +1, not -1 like reflections. You cannot separate these possibilities using trace: for instance, ⎡ -1 0 0 ⎤ ⎢ 0 1 1 ⎢ ⎣ 0 0 1 ⎦ and ⎡ 0 -1 0 ⎤ ⎢ 1 0 0 ⎢ ⎣ 0 0 1 ⎦ are both orthogonal, and both have trace +1, but the first (reflection in the yz plane) has det=-1, while the second (a quarter-turn around the z-axis) has det=+1. I have not checked whether the code works in spite of these errors, but they make me very, very cautious.

martinbaker

2012-03-10 01:36:01 PST

Thanks very much for these corrections, I'm sure you are right to be very, very cautious. I have corrected the page, I hope it is correct now? The reason for introducing trace is to select the most accurate algorithm, but somehow this got mixed up with the condition for being a pure rotation matrix, sorry about that. Martin

geometeer

2012-03-10 03:01:46 PST

The page still gives (det(matrix)=1) as an explanation (?) of orthogonality, which it is not. Orthogonality means that the columns (or -- equivalent condition -- the rows) are an orthonormal set. It does not imply that the determinant is +1, since it might be -1. The condtion for being _special_ orthogonal cannot be a condition on the trace alone, by the example I gave. The condition for being a pure rotation matrix is that (A) the columns are orthonormal m00×m00 + m10×m10 + m20×m20 = 1 m01×m01 + m11×m11 + m21×m21 = 1 m02×m02 + m12×m12 + m22×m22 = 1 [orthogonal] m00×m01 + m10×m11 + m20×m21 = 0 m00×m02 + m10×m12 + m20×m22 = 0 m01×m02 + m11×m12 + m21×m22 = 0 and that the determinant(matrix) = +1 [orientation-preserving] It is actually true for any special orthogonal matrix that m00 + m11 + m22 + 1 ≥ 0 -- not strictly greater ">", since the half-turn rotation ⎡ -1 0 0 ⎤ ⎢ 0 -1 1 ⎢ ⎣ 0 0 1 ⎦ about the z-axis is special orthogonal -- so if the algorithm needs that property, it can safely be assumed true of a 3D rotation matrix. But as a _test_ for being a 3D rotation matrix, that property is no use at all, since reflections have it too. You could give the condition [orthogonal]+[orientation-preserving] as a test for being a rotation, and then point out the trace consequence (that is easily proved by loking at 2D rotations, once you know that every 3D rotation has an axis). But does the algorithm work for the case m00 + m11 + m22 + 1 = 0 which happens whenever the matrix describes a half-turn, about any axis? (It gives a 'pure quaternion', with no real part.) If it fails there, then it will be numerically untrustworthy for small values of m00 + m11 + m22 + 1 . Tim

martinbaker

2012-03-10 07:36:03 PST

Hi Tim, On Saturday 10 Mar 2012 11:01:46 you wrote: > Read and respond to this message > By: geometeer > > The page still gives (det(matrix)=1) as an explanation (?) of > orthogonality, which it is not. That was not the intention, that page is intended to be purely about the conversion from matrix to quaternion. The only reason for mentioning it is that the algorithm is only valid if we start with a matrix representing a pure rotation. So in some cases programmers might need to add a test for (special) orthogonality before the algorithm is used. That’s why I have a link to the page which specifically covers orthogonality here: https://www.euclideanspace.com/maths/algebra/matrix/orthogonal/ So all I am trying to say is that at the start the matrix should be not only orthogonal but also special orthogonal. I guess I need to make the wording clearer? > The condtion for being _special_ orthogonal cannot be a condition on the > trace alone, by the example I gave. I know that’s what the page originally said (I really should not have made such an error, I do know better, honestly!), but I thought the revised page removed that error? The reason for including trace is nothing to do with orthogonality but to avoid singularities. That is, although there is a smooth mapping from matrix to quaternion, I can't find a single set of equations that express that mapping without singularities. For instance the equations: qw= √(1 + m00 + m11 + m22) /2 qx = (m21 - m12)/( 4 *qw) qy = (m02 - m20)/( 4 *qw) qz = (m10 - m01)/( 4 *qw) have a singularity at, the example you gave, at half-turn rotation. So I am using trace only to patch in alternative equations avoid these singularities and nothing to do with testing for (special) orthogonality. Martin

geometeer

2012-03-10 08:26:26 PST

The only revision I can see is "orthoginal" changed to "orthogonal". It still explains "m00 + m11 + m22 + 1 > 0" by "(the matrix is special orthogonal which cannot represent a reflection component)" and this trace condition is _not_ what special orthogonal means. Insisting on "m00 + m11 + m22 + 1 > 0" does not rule out reflections (which all have m00 + m11 + m22 + 1 = 2), but it does rule out perfectly good rotations, the half-turns, which you cannot safely exclude. In a game or animation it will be quite common for a changing rotation to be through values like 179.5°, 179.8°, 180.1°, 180.4°, ..., about a slowly changing axis, so the w in your "Simple Code" give will pass through very small values, and (x,y,z) will try to go through infinity. Expect big rounding-error problems! The "Simple Code" should come with a big warning, Only For Small Rotations, comfortably less than 180°. Since "The reason for including trace is nothing to do with orthogonality but to avoid singularities", why mention special orthogonal and reflection in the context of the trace condition? It is in fact impossible to avoid discontinuities. If we continuously do a full 360° turn around any axis from the identity matrix I and back to I, choosing the quaternion 1+i0+j0+k0 at the start and insisting that it changes continuously, it will end with -1+i0+j0+k0. Any code that from a rotation matrix M gives just one quaternion must have places where the result jumps from Q to a value near -Q. This is topologically inevitable, so one just has to make sure of avoiding numerical errors around such places, and avoid assuming Q(t) is jump-free just because M(t) is. It is easy to assume continuity without noticing, and consequences can be nasty.

martinbaker

2012-03-10 09:07:08 PST

Tim, > The only revision I can see is "orthoginal" changed to "orthogonal". > It still explains "m00 + m11 + m22 + 1 > 0" by > "(the matrix is special orthogonal which cannot represent a reflection > component)" OK, I originally removed the erroneous connection between trace and orthogonality in the first section, and since you mentioned this I found another one I missed at the end of the page under 'Issues'. It is quite a long page, I'll have to read it through more carefully to see if I missed any more. > Insisting on "m00 + m11 + m22 + 1 > 0" does not rule out reflections (which > all have m00 + m11 + m22 + 1 = 2), > but it does rule out perfectly good rotations, the half-turns, which you > cannot safely exclude. As I said before, I'm not ruling this out, I'm just using this test to switch to a different set of equations where the singularity is not near the part of space where we are doing the translation. > The "Simple Code" should come with a big warning, > Only For Small Rotations, comfortably less than 180°. I thought I had made that warning, perhaps I need to make the wording stronger? > Since "The reason for including trace is nothing to do with orthogonality > but to avoid singularities", > why mention special orthogonal and reflection in the context of the trace > condition? I originally made an error in several places on the page sometime in the past (I don't know what came over me! It was a few years ago that I wrote that page, but even then, I still knew better). Thank you for pointing it out. > It is in fact impossible to avoid discontinuities. > If we continuously do a full 360° turn around any axis from the identity > matrix I and back to I, > choosing the quaternion 1+i0+j0+k0 at the start and insisting that it > changes continuously, > it will end with -1+i0+j0+k0. Any code that from a rotation matrix M gives > just one quaternion > must have places where the result jumps from Q to a value near -Q. > This is topologically inevitable, so one just has to make sure of avoiding > numerical errors > around such places, and avoid assuming Q(t) is jump-free just because M(t) > is. It is easy to assume continuity without noticing, and consequences can > be nasty. This is all true but the code on this page is only defining an algorithm from matrix to quaternion at one point at a time. So its perfectly possible to switch in a set of equations that work smoothly around that point in space. Thanks again for pointing out my original error. Martin

geometeer

2012-03-10 16:32:00 PST

Yes, around any particular rotation one can perfecly choose a nice continuous matrix->quaternion function. But faced with a non-small succession of matrices (frequent in applications!), one has to either jump, or accept that sometimes the same matrix will give q, sometimes -q. All the code you give will jump, which is OK for some purposes -- the rotation itself doesn't jump -- but problematic for others, such as if somebody is trying to find a _rate_ of rotation in the quaternion framework. A warning would be useful to readers who expect a unique answer to behave continuously everywhere.

martinbaker

2012-03-11 00:50:09 PST

Tim, On Sunday 11 Mar 2012 00:32:00 you wrote: > Yes, around any particular rotation one can perfecly choose a nice > continuous matrix->quaternion function. > But faced with a non-small succession of matrices (frequent in > applications!), one has to either jump, Yes, good point, I have just added this note in 'issues' section near the end of the page but perhaps I should make it more prominent. "2) Both matrices and quaternions avoid the singularities and discontinuities involved with rotation in 3 dimensions by adding extra dimensions. This has the effect that different values could represent the same rotation, for example quaternion q and -q represent the same rotation. It is therefore possible that, if we are converting a rotation sequence, our output may jump between these equivalent forms. This could cause problems where subsequent operations such as differentiation is done on this data. So programmers need to be aware of this issue." I guess we could get round this particular case by always converting the quaternion output to some 'canonical form' for example: if real part is negative then q = -q if real part is zero then { if i part is negative then q = -q if i part is zero then { if j part is negative then q = -q ... }} Martin

geometeer

2012-03-11 01:23:04 PST

Right! In fact it is not merely possible but inevitable that in any scheme that always gives the same quaternion for the same matrix, independent of history, there will sometimes be sign change discontinuities. The canonical form you give doesn't get round that so much as regularize it, fixing exactly where the discontinuities will happen: at the ±180° rotations around any axis. Rotate past a half-turn, and (just like labelling angles as between -180° and +180°), the assigned q will change sign. There was a fly-by-wire US fighter that due to essential discontinuities in the Euler angle labelling of rotations, the first time that it flew past the Equator, started flying upside down. These topological issues are very real engineering ones. )Tim

martinbaker

2012-03-11 10:00:38 PDT

Tim, OK thanks, this is a very interesting topic and I think it would be of interest to other readers of the web page, would it be alright with you if I linked from the page to a copy of this thread? Martin