• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
oliii

Compressed quaternions

16 posts in this topic

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

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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).
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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.

0

Share this post


Link to post
Share on other sites
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!
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
2

Share this post


Link to post
Share on other sites
Now that's what I'm talking about. Food for thoughts. Thanks John.
0

Share this post


Link to post
Share on other sites
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.
1

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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....

0

Share this post


Link to post
Share on other sites
[quote name='Dave Eberly' timestamp='1187901520' post='4041864']
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, [url="http://www.geometrictools.com/Documentation/BSplineLeastSquaresFit.pdf"]Least Squares Fitting of Data with B-Spline Curves[/url]. 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.
[/quote]

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
0

Share this post


Link to post
Share on other sites
[quote name='kettle' timestamp='1344687439' post='4968395']
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
[/quote]

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0