Understanding Quaternion equivalence to matrix transform

Question

A quaternion is obviously equivalent to a rotation matrix, but a 4x4 matrix does more than just rotation. It also does translation and scaling.

A matrix for affine transforms can actually be represented with 12 elements because the last row is constant:

a b c d
e f g h
i j k l
0 0 0 1


x' = a*x + b*y + c*z + d
y' = e*x + f*y + g*z + h
z' = i*x + j*y + k*z + l

A full transform therefore takes 9 multiplies and 9 adds. For the three affine transforms: rotation, scale, and translation I would like to know if a quaternion-based system is competitive. I have looked all over and have not found one anywhere.

Given a quaternion p = (w,x,y,z) For rotation, q' = pqp'. I could add a translation vector: t=(tx,ty,tz)

q' = pqp' + t

That is just 7 elements as compared to 12 with matrices, though it is slightly more operations. That still does not support scaling though. Is there a complete equivalent?

Note: If the only answer is to convert the rotation to a matrix, then that is not really an answer. The question is whether a quaternion system can perform affine transform without matrices.

If there is an equivalence, can anyone point me to a java or c++ class so I can see how this works?

Answer 1

Short answer:

For the three affine transforms: rotation, scale, and translation I would like to know if a quaternion-based system is competitive.

Just like you added a translation vector, add a scaling vector. Just take the element-wise product of the intermediate vectors with it. That allows you to scale, rotate, and translate:

v' = q(v*s)q' + t

However, this does not fully reproduce the possible affine transformations, as you can also have shear transformation. But those are not necessarily desirable, so whether this quaternion system is competitive depends on what you are doing. For example, if you want your transform to give you a rectangle out when it is given an axis aligned rectangle in, you cannot do better than this. Or if you want angles to be preserved, then you cannot do better than rotation + translation (unless you also want mirroring). "Competitive" very much depends on what you are actually trying to accomplish.

Longer answer:

A quaternion alone (as you stated) cannot perform any affine transform. It is limited to rotations (and positive uniform scaling if we allow for non-unit quaternions, though note that a lot of the formulas used to evaluate rotations of vectors in terms of quaternions assume that you have unit quaternions). To get a complete equivalent, you need to be able to fully reconstruct the 12 independent components of your affine transform (well, not entirely independent, as the transform must be invertible, which adds a !=0 constraint on determinant the 3x3 part of the matrix). To get an idea of what sorts of transforms are possible, see the Wikipedia list for 2D Affine transformations.

• So with your unit quaternion + translation v' = q v q' + t, you have only 6 independent components: 3 for translation + 3 for rotation + 1 dependent rotation component. These are actually the only possible rigid body transformations, so if you are doing stuff for a physics engine this may be all you want
• Allowing non-normalized quaternions v' = sq v sq' + t gives you 7 components: 3 for translation + 3 for rotation + 1 for uniform positive scale. Uniform scaling is generally well behaved, so for collision shapes in a physics engine this might be preferred to not having scaling, though I'm not sure you save any operations in calculating it by storing scale inside the quaternion
• Allowing, instead, a non-uniform scale by a vector v' = q (v*u) q' + t, we have 9 components: 3 for translation + 3 for rotation + 3 for nonuniform scale (including mirroring). This is as far as many libraries will go in representing transforms (e.g. Unity, Urho3D, etc.), though you can get the additional components by composing multiple transforms with non-uniform scales.

We still need 3 more components to get up to the 12 independent components of our 3D affine transform though. These correspond to shear or skew transformations. I think the easiest way to represent this is with another matrix, though there are only 3 non-constant components in it, so you can store it in a vector [s_yz, s_xz, s_xy].

1 s_xy s_xz
0   1  s_yz
0   0   1

With that, we have 12 independent components, which is enough to represent many 3D affine transforms, with some limitations. If we look at the 2D case, we see how it is limited:

2D equivalent

v' = AFFINE v

[x']   [ a b e ] [x]   [a*x + b*y + e]
[y'] = [ c d f ] [y] = [c*x + d*y + f]
[1 ]   [ 0 0 1 ] [1] = [      1      ]

v' = SHEAR( ROT (v*u) ) + t (I use ROT here as 2D rotation, and then C and S for cos(theta) and sin(theta) since complex numbers does not have the same qvq' form - I will take it we are agreed that quaternions can be converted to a rotation matrix).

[x'] = [1 M][C  S][ux*x] + [tx] = [1 M][ C*ux*x + S*uy*y + tx]
[y']   [0 1][-S C][uy*y] + [ty]   [0 1][-S*ux*x + C*uy*y + ty]
     = [ (C*ux - M*S*ux)*x + (S*uy+M*C*uy)*y + tx]
       [         (-S*ux)*x +        (C*uy)*y + ty]

From this we identify e = tx, f = ty trivially. We thus are only interested in whether the rotation portion can give every independent component. The answer is not always yes.

If we have :

[a b] = [1 0]
[c d]   [N 1] 

Then we have for our alternate transformation (without the translation):

• C*uy = 1

   = [ (C*ux - M*S*ux),  (S/C+M)]
     [         (-S*ux),        1]
  

• -S*ux = N (assuming N!=0)

   = [ (-C/S + M*N), (S/C+M) ]
     [          N,        1]
  

• M = -S/C

   = [ (-C/S - N*S/C), 0 ]
     [            1,   1 ]
  

• Let t = tan(theta) = S/C

   = [ -(1/t + N*t), 0 ]
     [            1,   1 ]
  

• Then we have 1 = -1/t -N*t, which has real solutions only for N<=1/4.

Thus we cannot represent any affine invertible 3x3 matrix with a non-uniform scale followed by a rotation followed by a horizontal shear. Adding additional transforms should allow any transformation, (e.g. add a verticle shear). Possibly just reordering the operations would as well, I have not attempted to work that out.

To gain some intuition about why it does not work out, consider the vector [y*z,x*z,x*y]. While it has 3 independent variables (x,y,z), it is not able to represent any vector [a,b,c], as it is not capable or representing a vector with a single 0 component, only vectors with multiple 0 components.

Conclusion

At this point, I am content with giving up. Unless you are only interested in a limited subset of possible affine transformations (e.g. the rigid/uniform translations I disucssed above in terms of physics engines), you probably will not do any better than just representing it as a 3x3 matrix + vec3 translation (the 3x4 non-constant components of the affine matrix). Any further attempts will result in redundency in your transforms (e.g. Scale->Rotate->Scale) that will cost you more storage and will no longer have the nice property that composing any of the affine transforms results in a single affine transform. How much extra is required? As a guess, I think just adding the remaining 3 possible shear components may be enough, but I am not going to attempt to work it out. Especially as at this point we are basically just back to matrices with nothing in particular to do with quaternions.

  1  s_xy s_xz
s_yx   1  s_yz
s_zx s_zy   1