**0**

# Compressed quaternions

###
#3
Members - Reputation: **194**

Posted 23 August 2007 - 12:18 AM

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

###
#4
Crossbones+ - Reputation: **2004**

Posted 23 August 2007 - 12:25 AM

###
#6
Members - Reputation: **341**

Posted 23 August 2007 - 12:58 AM

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

###
#7
Members - Reputation: **229**

Posted 23 August 2007 - 12:58 AM

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

###
#8
Members - Reputation: **1591**

Posted 23 August 2007 - 01:03 AM

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.

###
#9
Members - Reputation: **341**

Posted 23 August 2007 - 01:10 AM

###
#11
Members - Reputation: **347**

Posted 23 August 2007 - 05:34 AM

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.

###
#13
Members - Reputation: **1161**

Posted 23 August 2007 - 02:38 PM

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.

###
#14
Members - Reputation: **313**

Posted 24 August 2007 - 07:27 AM

###
#15
Members - Reputation: **210**

Posted 24 August 2007 - 11:17 AM

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

###
#16
Members - Reputation: **104**

Posted 11 August 2012 - 06:17 AM

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

###
#17
Members - Reputation: **1161**

Posted 14 August 2012 - 12:13 AM

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.