• 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
Norman Barrows

pixel perfect local rotations and quats vs mats

13 posts in this topic

ok, who out there uses quaternions?

 

can you get pixel perfect rotations about local axes at arbitrary orientations? or does floating point error creep in and spoil the fun the way it does with matrices?

 

lets say incremental turns around local y by 1/10th degree per turn (3600 turns to do a 360), and 1600 x 900 screen resolution. can a floating point quat, starting from any orientation, come back to exactly the same pixel every time after doing a 360?

 

 

 

 

0

Share this post


Link to post
Share on other sites
If it contains floating point it's prone to precision error; doesn't matter what data structure you use, you must do your calculations in a manner that deals with or compensates for this error instead. Re: quaternions, and even if you do use them for rotation, at some time you're going to need to put that rotation in a matrix anyway as you'll be wanting to do translation/projection/etc too, and quaternions can't do those.
0

Share this post


Link to post
Share on other sites

You would not do incremental turns of 1/10 degree with any representation you use, that is inefficient, it is not how graphics APIs work, and it's unwise because of accumulating error.

 

You do not throw an "object" at OpenGL or Direct3D which it "remembers", and later you can tell it to rotate by 1/10 degree a few times. It doesn't work that way.

 

Instead, you would do a single rotation from a neutral position to whatever orientation you want every frame when you draw your object. This is a single transform (note, however, that a unit quaternion can rotate at most +/-180°, so you need a little bit more thought). Since you do not accumulate a thousand tiny rotations, the rounding issue does not arise.

 

That being said, unit quaternions are none "worse" than orthonormal matrices. On the contrary, a quaternion (unit or not) has fewer degrees of freedom (i.e. fewer "numbers") and is thus not as much "over-defined" as a matrix for performing a rotation. Therefore, you reasonably expect fewer rounding issues.

 

The obvious advantage of a matrix is that you can do translation, scaling, and shear as well whereas a (unit) quaternion does no such thing. But since you're only interested in a rotation, that doesn't matter.

Edited by samoth
1

Share this post


Link to post
Share on other sites

Instead, you would do a single rotation from a neutral position to whatever orientation you want every frame when you draw your object. This is a single transform (note, however, that a unit quaternion can rotate at most +/-180°, so you need a little bit more thought).

 

They can rotate objects +/- 360 degrees (although simplistic SLERP implementations usually use a dot + negate to artifically restrict the quats to +/-180)

Edited by RobTheBloke
0

Share this post


Link to post
Share on other sites

Effectively, yes, but actually no. At least I wouldn't know how you'd do that.

 

A quaternion stores [tt]cos(½?)[/tt] as one of its components, and the cosine function has a period of [tt]2?[/tt].

Which means you can unambiguously represent a rotation of [tt]+/- ½·2?  =  +/- ?[/tt]   or +/- 180°.

 

But of course rotating by -1° is the same orientation as rotating by +359° so effectively you can get any orientation.

0

Share this post


Link to post
Share on other sites

nstead, you would do a single rotation from a neutral position to whatever orientation you want every frame when you draw your object.

 

i guess it wasn't clear in my original post, i'm not talking about drawing objects, i'm talking about storing their orientation and rotating them about local axes by incremental amounts.  once that's done, you have an orientation in a matrix or quat, and use that to draw. 

Edited by Norman Barrows
0

Share this post


Link to post
Share on other sites

ok, given float inaccuracies, how does one achieve pixel perfect rotations at high resolutions? I've been able to do it in the past, but at 640 x 480, not 1600 x 900. there i used D3DXMATRIX, and gram-shmitt re-ortho-normalize.

 

i guess one would have to implement the data structure at high accuracy, such as long long fixed point. and then copy the accurate info to a less accurate matrix for drawing.

0

Share this post


Link to post
Share on other sites

you can compute double on CPU but shaders need float . I do not see why float matricies in shaders would not result in pixel precise rotations. What do you mean by pixel precise rotation and why you think you are not having it?

0

Share this post


Link to post
Share on other sites

Effectively, yes, but actually no. At least I wouldn't know how you'd do that.

 

A quaternion stores [tt]cos(½?)[/tt] as one of its components, and the cosine function has a period of [tt]2?[/tt].

Which means you can unambiguously represent a rotation of [tt]+/- ½·2?  =  +/- ?[/tt]   or +/- 180°.

 

But of course rotating by -1° is the same orientation as rotating by +359° so effectively you can get any orientation.

 

 

Ok. So given an XY coordinate that lies on a circle, is it possible to determine the angle? Applying your logic, the answer would be no, because:

 

angle = acos( X )

 

And that would only give you +/-90 degrees.... whereas the correct answer is yes, so long as you use both components, i.e. atan2(Y, X).

 

So sure, if you're going to completely ignore the existence of the sin(angle / 2) in addition to cos(angle / 2), then you will indeed be able to ignore the fact that a quat can represent +/-360 degrees. But you know, as I said before, if you use a crap SLERP implementation that performs a quat-negate when the dot product is less than zero, then you will not be aware of the other half of the hemisphere. If you were to change your slerp from:

 

if( dot(Q1, Q2) < 0 )

 

to

 

if( dot(Q1, Q2) > 0 )

 

your quats will always take the longest path, i.e. the one greater than 180 degrees. FYI, if you have a quat Q, that represents a rotation of 1 degree, it's negate represents the rotation of -359.

0

Share this post


Link to post
Share on other sites
 

I do not see why float matricies in shaders would not result in pixel precise rotations. What do you mean by pixel precise rotation and why you think you are not having it?
 
accumulated error from incremental turns about local axes. think flight sim, 3 degrees rotational freedom. orientation can be stored as Eulers, matrix, quaternion, direction vector and roll, etc.
 
pixel perfect means i'm at some arbitrary orientation, say 17 degrees x rotation, 23 degrees y rotation, 38 degrees z rotation (left hand system). now i do a 360 around my local y axis, in 3600 steps of 0.1 degree each. when i'm done turning,  i "should" have the same pixel in the center of my screen. 
 
when you rotate a matrix (orientation = local rotation * orientation), floating point error causes the column vectors (your local right, up, and forward axes) to become non-orthogonal. gram shmitt re-orthogonalizes them. but due to rounding error, some "drift" is introduced. gram-shmidtt re-othogonalizes by moving two of the vectors (such as up and right) slightly. thus the "drift". so when you're in your space fighter, and you're looking directly at the enemy starbase, and you hit your joystick left and do a 360, when you come back around, you're not looking directly at the starbase anymore, you're aimed a little above or below, by a few pixels. 
 
i was wondering if this is the case with quats as well.
 
rotations about local axes can be performed 5 ways (to my knowledge): mat muls, quat muls, rotation about world axis (with a lot of unrotating and re-rotating), rotation about an arbitrary axis formula,  and possibly skew.
 
but the precision of the implementation can be an issue.   my big question is are float quats more accurate than float mats?
Edited by Norman Barrows
0

Share this post


Link to post
Share on other sites

accumulated error from incremental turns about local axes. think flight sim, 3 degrees rotational freedom. orientation can be stored as Eulers, matrix, quaternion, direction vector and roll, etc.

 
pixel perfect means i'm at some arbitrary orientation, say 17 degrees x rotation, 23 degrees y rotation, 38 degrees z rotation (left hand system). now i do a 360 around my local y axis, in 3600 steps of 0.1 degree each. when i'm done turning,  i "should" have the same pixel in the center of my screen.
This is generally not possible with any representation, for the simple reason that 0.1° ? 0.0062831853, which is not representable using IEEE 754 math. Also, its cosine is not representable. Therefore, error must occur, and error must accumulate.
 
Quaternion multiplication has fewer operations, and quaternions have fewer components, so there is less opportunity for error to accumulate, but still they cannot be "perfectly accurate" if you combine a thousand of them. But even if you only keep adding very small values to a single [tt]float[/tt], and convert the accumulated value, you will see error accumulation.
 
The most accurate solution to your specific problem (doing 1000 little rotations around the y axis, or some axis) would be to use fixed point math to store the intermediate angles of rotation around a vector (in that case [0,1,0]), and convert these to either matrix or quaternion at ever frame just for the purpose of doing the model transform when rendering. Adding up the integer 1 a thousand times gives exactly 1,000 (with very few, entirely irrelevant exceptions!), and doing 1,000 or 100,000 little rotations will be "pixel perfect", except for unavoidable rounding errors.
The unavoidable rounding errors are the ones occuring during the calculation of the cosine and due to the cosine usually not being exactly representable as float, and rounding errors that occur while the GPU does the transform, on which you have little or no influence.
 
Fixed point works perfectly for rotating around any single axis, but for combining rotations around a large of different vectors it isn't too useful (that's another problem though, and I don't think there exists a precise solution for this).
 
Fixed-point has the apparent disadvantage of not being able to rotate smaller steps than some previously chosen minimum, but you cannot do math with "normal sized" and "some arbitrarily small" float values, either. In fact, you can -- it just doesn't work as you expect (which is much worse, in my opinion). So, this really isn't a disadvantage, but an advantage.
If you choose something like 1/1,000 or 1/10,000 (or some power of two, such as 1/220 to allow the compiler to use shifts), it should be accurate enough for most people (nobody can possibly tell a difference of 1/1,048,576°).
Edited by samoth
1

Share this post


Link to post
Share on other sites

This is generally not possible with any representation, for the simple reason that 0.1° ? 0.0062831853, which is not representable using IEEE 754 math. Also, its cosine is not representable. Therefore, error must occur, and error must accumulate.
 
Quaternion multiplication has fewer operations, and quaternions have fewer components, so there is less opportunity for error to accumulate, but still they cannot be "perfectly accurate" if you combine a thousand of them. But even if you only keep adding very small values to a single float, and convert the accumulated value, you will see error accumulation.
 
The most accurate solution to your specific problem (doing 1000 little rotations around the y axis, or some axis) would be to use fixed point math to store the intermediate angles of rotation around a vector (in that case [0,1,0]), and convert these to either matrix or quaternion at ever frame just for the purpose of doing the model transform when rendering. Adding up the integer 1 a thousand times gives exactly 1,000 (with very few, entirely irrelevant exceptions!), and doing 1,000 or 100,000 little rotations will be "pixel perfect", except for unavoidable rounding errors.
The unavoidable rounding errors are the ones occuring during the calculation of the cosine and due to the cosine usually not being exactly representable as float, and rounding errors that occur while the GPU does the transform, on which you have little or no influence.

 

 

cool. thats the info i needed. thanks!

 

saved me some time messing with quats for improved accuracy.

 

i've been doing games on and off for over 20 years. it sucks that after all that time you still have to worry about numerical precision and use stuff like fixed point. the more things change, the more they stay the same...

 

shifted bit fixed point, i feel like i'm back tuning assembly code blitters for sprite based 3d engines (a la wing commander 2).

0

Share this post


Link to post
Share on other sites

You're still going to get rounding error if you use fixed point and rotate around local axes... it's the same as using a quaternion and quantising your orientation really... and fixed point is slower than floating point these days...

 

If you are only using pitch and yaw fixed point would be exact (but again not as efficient). And you get the nasty singularities looking straight up or down.

 

I challenge you to turn your car around exactly 360.0000 degrees though, and that's just with one axis of rotation.

0

Share this post


Link to post
Share on other sites

You're still going to get rounding error if you use fixed point and rotate around local axes... it's the same as using a quaternion and quantising your orientation really... and fixed point is slower than floating point these days...

 

yes, i just thought of that in this related thread (which inspired this  thread)...

 

http://www.gamedev.net/topic/640230-how-to-re-orthogonalise-vectors/

 

If you are only using pitch and yaw fixed point would be exact (but again not as efficient). And you get the nasty singularities looking straight up or down.

 

Yes, i remember that technique from "Building a flight simulator in C".

 

I challenge you to turn your car around exactly 360.0000 degrees though, and that's just with one axis of rotation.

 

this is what i'm counting on - that the drift and inaccuracy won't be too bad.   while you may be a few pixels high or low after doing a 360 in your X-wing, odds are you'll have better things to do than notice.   and as long as the drift is small, the player can still "know" the target is 120 degrees left (around local y) from situational awareness, turn 120 left, and shoot, without going "how'd it get up there / down there? it should be right in front of me!".

 

by situational awareness, i mean the way that every good fighter jock carries around a local coordinate system in their head, and they track (or estimate) targets in it, even when out of view. so when i see my opponent fly past me over my left shoulder, based on his angle and speed and time elapsed, i can track him (estimate his position) in my mental coordinate system (my mental picture of the battlefield space) despite his not being in view. that how i "know" he's about 120 degrees left.  if the drift from "turning blind" like that is too great, then the player's mental representation of the battlespace and the simulation's representation will no longer match up sufficiently, because physics works perfectly in the player's mind, but the simlation's physics suffer from numerical inaccuracy when turning.    this disconnect between the two, if too great, can ruin a flight sim.

0

Share this post


Link to post
Share on other sites

As soon as you use the term "he's about 120 degrees left" you admit innacuracy.

 

It's not worth the pain of fixed point (I know, I used to do PS1 games) for a performance drop and no overall gain in accuracy.

 

If fixed point was a panacea it would be implemented in hardware as standard.

0

Share this post


Link to post
Share on other sites

Actually, thinking about it, you can accumulate an exact 360.000000000° quaternion or rotation matrix using fixed-point to accumulate the rotation angle, assuming the math library works.

 

The integer value 360 is exactly precise thanks to using fixed point (obviously), and [tt]float[/tt] can represent integers smaller than 223 precisely. 360.0 is quite a bit smaller than 223. Therefore, there is no accurracy loss when converting the accumulated value to [tt]float[/tt].

 

Incidentially, the cosine is exactly 1.0 at 2pi, and the sine is exactly 0.0, and both these numbers are exactly representable as floats. A math library that is worth its salt should not produce any result different from exactly 1.0 and 0.0 for these.

 

Thus, all in all, as far as you have an influence, you can make it perfectly accurate in this special case. But still, the matrix multiplication that happens on the GPU will (or may) have a rounding error, no matter what. And of course,

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