Jump to content

  • Log In with Google      Sign In   
  • Create Account

pixel perfect local rotations and quats vs mats


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
17 replies to this topic

#1 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
0Likes
Like

Posted 26 March 2013 - 01:51 PM

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?

 

 

 

 


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


Sponsor:

#2 mhagain   Crossbones+   -  Reputation: 7979

Like
0Likes
Like

Posted 26 March 2013 - 02:10 PM

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.

It appears that the gentleman thought C++ was extremely difficult and he was overjoyed that the machine was absorbing it; he understood that good C++ is difficult but the best C++ is well-nigh unintelligible.


#3 samoth   Crossbones+   -  Reputation: 4783

Like
1Likes
Like

Posted 26 March 2013 - 02:55 PM

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, 26 March 2013 - 03:00 PM.


#4 RobTheBloke   Crossbones+   -  Reputation: 2342

Like
0Likes
Like

Posted 26 March 2013 - 05:12 PM

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, 26 March 2013 - 05:17 PM.


#5 samoth   Crossbones+   -  Reputation: 4783

Like
0Likes
Like

Posted 27 March 2013 - 05:53 AM

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

 

A quaternion stores cos(½Φ) as one of its components, and the cosine function has a period of .

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

 

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



#6 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
0Likes
Like

Posted 27 March 2013 - 08:15 AM

If it contains floating point it's prone to precision error; doesn't matter what data structure you use

 

that's what i suspected.


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#7 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
0Likes
Like

Posted 27 March 2013 - 08:19 AM

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, 27 March 2013 - 08:20 AM.

Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#8 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
0Likes
Like

Posted 27 March 2013 - 08:27 AM

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.


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#9 JohnnyCode   Members   -  Reputation: 219

Like
0Likes
Like

Posted 28 March 2013 - 03:39 AM

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?



#10 RobTheBloke   Crossbones+   -  Reputation: 2342

Like
0Likes
Like

Posted 28 March 2013 - 08:52 AM

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

 

A quaternion stores cos(½Φ) as one of its components, and the cosine function has a period of .

Which means you can unambiguously represent a rotation of +/- ½·2π  =  +/- π   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.



#11 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
0Likes
Like

Posted 31 March 2013 - 11:53 AM

 

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, 31 March 2013 - 11:54 AM.

Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#12 samoth   Crossbones+   -  Reputation: 4783

Like
1Likes
Like

Posted 01 April 2013 - 11:02 AM

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 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.
 
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, 01 April 2013 - 11:03 AM.


#13 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
0Likes
Like

Posted 01 April 2013 - 02:25 PM

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


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#14 Paradigm Shifter   Crossbones+   -  Reputation: 5374

Like
0Likes
Like

Posted 01 April 2013 - 02:47 PM

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.


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#15 Norman Barrows   Crossbones+   -  Reputation: 2138

Like
0Likes
Like

Posted 01 April 2013 - 03:26 PM

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.


Norm Barrows

Rockland Software Productions

"Building PC games since 1988"

 

rocklandsoftware.net

 


#16 Paradigm Shifter   Crossbones+   -  Reputation: 5374

Like
0Likes
Like

Posted 01 April 2013 - 03:31 PM

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.


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#17 samoth   Crossbones+   -  Reputation: 4783

Like
0Likes
Like

Posted 01 April 2013 - 03:39 PM

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

 

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,



#18 Paradigm Shifter   Crossbones+   -  Reputation: 5374

Like
0Likes
Like

Posted 01 April 2013 - 03:41 PM

Yeah, in maths libraries perhaps. My point was can you do it in the real world...


"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS