Compressed quaternions
Author
Looking for a decent algo for compressing / uncompressing quaternions. I couldn't find anything in the article section, nor anything useful on [google].
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.
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
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
Author
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.
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.
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).
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).
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
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
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.
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.
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!
Author
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
