Quote:Original post by Promethium
Doom 3's MD5 file format stores unit quaternions as 3 floats: x, y and z. Using those three it's easy to find the fourth since x*x + y*y + z*z + w*w = 1.
There are a couple of issues with this. First you need an additional sign bit to distinguish between w being posive and negative, both of which are possible. You can avoid this though by checking the sign of w before compressing and if it's negative multiply the whole quaternion by -1, so w is always positive and you take the positive square root when decompressing. But this can cause problems for some data - e.g. by introducing jumps into a sequence of keyframes of an animation, requiring extra checks when interpolating them.
Another issue is the formula
w = sqrt( 1 - x^2 + y^2 + z^2 )
In not uniformly accurate - the larger D^2 = (x^2 + y^2 + z^2) is, and the smaller w is, the worse the error. you can show this numerically but the easiest way is to consider the derivate, e.g. of w with respect to x
dw/dx = -x / sqrt( 1 - D^2)
If D^2 = 0.25, x= 0.5
dw/dx = -2/3
if D^2 = 0.99, x = 0.5
dw/dx = 50
This means the rate of change of w with respect to x (or y or z) increases significantly as w approaches zero. This impacts the accuracy of it, as fp and rounding errors are multiplied by this, so near zero calculations of w are increasingly inaccurate. One solution is to store X, Y and z more accurately, using e.g. doubles, but this is not much use for compression.
A better solution is to store the smallest three of X, Y, Z and W, with a couple of bits to say which you've stored. In 32 bits this needs 10 bits per float, 2 bits to select the largest and so which three are stored, by e.g. describing how many times {X, Y, Z, W} needs to be permuted after decompression.