16 replies to this topic

[papalazaru]

Looking for a decent algo for compressing / uncompressing quaternions. I couldn't find anything in the article section, nor anything useful on [google].

[joanusdmentia]

Unless there's something special about your quaternions (eg. they're rotations) then there's not much you can do other than drop bits of precision.

[riku]

What do you want to compress them for? If it's for saving/loading into a file or transmission over a network connection, you could convert your quaternions into euler angles if the quaternion is normalized (ie. it represents a rotation). Euler angles require 3 values (rotX, rotY, rotZ) vs. quaternion's 4 values. You could also look for special rotations, such as no rotation and represent them with a special value.

Then you can drop some precision, perhaps make all your values fixed point values. Check the max ranges of your values and adjust precision accordingly. The values are rather small, so 16 bits will probably do, perhaps even 8. Or try to squeeze the 3 euler angles in a 32 bit integer, using 3.7 or 4.6 precision.

If you're trying to compress them for lower memory usage, it's probably not worth the trouble, you will end up using more memory that way because of all the code needed for the conversions and the temporary values, etc. Perhaps if you have an enormous amount of quaternions you may be able to save some bytes.

Compression usually only wastes time and effort, so it may not be worth the trouble anyway.

-Riku

[papalazaru]

Network transmission, so it is worth the trouble. Converting to Euler, yikes. And yes, they are rotation / orientation quaternions, so normalised. Surely there are some cool tricks one can do to compress them and minimize quantization. I could always convert to axis/angle I suppose, but there must be a better way. 4 bytes should give a nice apporximation.

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

[Trenki]

If your quaternions are always normalized you can drop the last component as you can compute it from the other three values.
So there are three values left to be stored. If you want to only use up 4 bytes you have 10 bits per component to store its value.
For this you probably only need a sign bit and then you can store the fractional part in the other 9 bits (as x, y and z will be less than 1).

[NegativeGeForce]

riku was on the right path. If you really want to get on the small side, use 3 bytes. Each one being the angle for each axis 0-255 degrees. Then you build the quaternion/euler matrix on the client/server side. That should be good enough precision for any game.

If your talking about something like a fantasy mmo, for positional data you could send just 2 bytes, but there would be a limit of 255 units you can move in the world. The server could use the last packet and the current packet to approximate the fraction of a unit so its "good enough".

You could also add an extra byte to indicate which quadrant your on so you can actually represent the 2 position bytes as just an x/y offset in a quadrant. The z component can be computed with gravity/ground collision detection.

struct packet
{
unsigned char x,y,z;
unsigned char x,y;
unsigned char quad;
}

6 bytes to represent orientation and position in a large world, not bad. You could even step it down even further. If you just want to know what direction the player is facing all you need is one byte for the Z rotation.

struct packet
{
unsigned char direction;
unsigned char x,y;
unsigned char quad;
}

4 bytes, :D

[ToohrVyk]

First, there's the consideration of sending quaternions less often (for instance, by using interpolation and dead reckoning).

Second, if lossy compression is acceptable, then you should specify what range your quaternions can be expected to be in (do you only have yaw and pitch, or do you also have roll, and if yes, how often do you have it?) in order to select an adapted range for the various angles.

[Trenki]

I recommend against using euler angles. You can just store the 3 values (x, y, z) of the unit quaternion and compute the fourth using the formula that was already given. If you want to store everything in 4 bytes you can use a 10 bits fixed point format with 1 sign bit and 9 bits for the fractional part as x,y and z will be > -1 and < 1!

[papalazaru]

Yeah, 9 bit precision should be enough. 7-bit precision is far far too small to be of any use. Extract X, Y, Z and re-normalise, that should do the trick.

[johnb]

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.

[papalazaru]

Now that's what I'm talking about. Food for thoughts. Thanks John.

[Dave Eberly]

Consider fitting N quaternions with a B-spline curve with M control points, where M is much smaller than N. You send the M control points, and the receiver uses them either to (approximately) reconstruct the N quaternions from the B-spline curve or to interpolate with the B-spline curve itself to generate quaternions on demand.

The document, Least Squares Fitting of Data with B-Spline Curves. On interpolation, you need to normalize the value returned by the B-spline curve; the fitted curve is close to a curve on the unit hypersphere, but is not exactly on that hypersphere.

This works quite well for compression of animation keyframes. I imagine it will work as well for network transmission, as long as N is large.

If N is small, why not just convert to half-floats? Even for N large, you can do the B-spline fit *and* convert the control points to half-floats.

[Richy2k]

Just multiply up the values by 255 and store in a byte, or multiply them up to 65535 and store in a word for better precision. We store them in a word at work to save on memory - as animation is taking up a lot of memory in our current game - its all mocap.

[TimothyFarrar]

One thing you might want to think about is the perceptional side to compression.

In other words don't just drop bits, but allocate the bits to what will be noticed the most.

Angles near parallel to the current view angle need more precision than angles perpendicular to the current viewing angle....

[kettle]

Consider fitting N quaternions with a B-spline curve with M control points, where M is much smaller than N. You send the M control points, and the receiver uses them either to (approximately) reconstruct the N quaternions from the B-spline curve or to interpolate with the B-spline curve itself to generate quaternions on demand.

The document, Least Squares Fitting of Data with B-Spline Curves. On interpolation, you need to normalize the value returned by the B-spline curve; the fitted curve is close to a curve on the unit hypersphere, but is not exactly on that hypersphere.

This works quite well for compression of animation keyframes. I imagine it will work as well for network transmission, as long as N is large.

If N is small, why not just convert to half-floats? Even for N large, you can do the B-spline fit *and* convert the control points to half-floats.

hi,any details about quaternions fitting with Bezier curve or B-Spline? . i just don't konw how to calculate the control points. in 3-D space, i do it with least square method, thanks

[Dave Eberly]

hi,any details about quaternions fitting with Bezier curve or B-Spline? . i just don't konw how to calculate the control points. in 3-D space, i do it with least square method, thanks

The PDF link is still active, and it discusses the fitting algorithm for N-dimensional quantities (for quaternions, N = 4). It is the same math as for 3-D space (N=3). As mentioned, the fitted curve is close to the unit hypersphere but not always exactly on it, so you can evaluate and then normalize. My website has sample code for fitting in 3D, but the code can be extended easily to quaternions.