Jump to content

  • Log In with Google      Sign In   
  • Create Account


Quaternion angle with itself > 0.001

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

#1 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 03 August 2014 - 10:55 AM

Hey guys,

I'm in the process of working out my math library, and so I was testing out a function that returns the angle between two quaternions..

{ return 2.0f * acos( Abs( Dot4( qa, qb ) ) ); }

 

.. but for some reason, I'm either getting a lot of floating point error in the result, or I'm not checking for a situation that I should be. While testing a quaternion (which was generated by a random axis+angle rotation and appears to be very close to normalized)..

{ x=0.0172970667 y=-0.0245058369 z=0.0205858145, w=-0.999337912    }

.. with itself, I'm getting a result angle of 0.00138106791 (or almost 0.1 degrees)..

 

I'm just wondering if this is acceptable error when working with float variables? And is there anything I can do to improve this issue other than switching to double type or something else as drastic?

 

edit note: After testing some more, the highest "error angle" I've been able to generate (through random axis-angles) is 0.001953125. And that was getting the angle (from itself) of a quaternion generated by the axis @ angle: { -0.833756,0.551120,-0.033417 @ 2.960138559341 } (quaternion result: { -0.830327,0.548853,-0.033279,0.090603 } )

 

Thank you


Edited by Stephany, 03 August 2014 - 11:16 AM.


Sponsor:

#2 WiredCat   Members   -  Reputation: 257

Like
1Likes
Like

Posted 03 August 2014 - 11:20 AM

well you could check long double for it

 

 

just make something lie this 

 

 

rewrite dot4 so it will get quaterions (like old did but i will operate on long doubles and will return long double)

ofc function returns long double

then  return  2.0 * acosl( fabsl( DotDouble4( qa, qb ) ) ); }

 

this could use the best precision for floats

 

 

anyway try to rotate something by in ex 90 degrees and try to find that angle.



#3 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 03 August 2014 - 11:30 AM

After further testing, it seems I was wrong when I said my quaternions were very close to normalized.

 

Apparently, my quaternion axis-angle rotation was not generating perfectly normalized results. Even though the lengths were around 0.9999+, it was enough to generate the angle differences above.

 

In the same test loops I used above, I normalized the quaternion after creating it from an axis+angle, and the angle between itself was exactly 0.

 

So what I've learned from this is that I have to normalize every quaternion I create from an axis+angle, even if the input axis was normalized..?

 

Sorry, I should have tested further before asking.

Thanks again.



#4 WiredCat   Members   -  Reputation: 257

Like
0Likes
Like

Posted 03 August 2014 - 01:32 PM

yes many have such problems, they forget to normalize them :)



#5 SeanMiddleditch   Members   -  Reputation: 5288

Like
0Likes
Like

Posted 03 August 2014 - 02:54 PM

Numerical stability is a pain. Sometimes you have to really think through your algorithms and rewrite them to be somewhat less efficient but more stable. There's a _lot_ of work required to really understand numeric stability with floats. I don't myself pretend to really understand it. This is one of the (many) reasons why you should just use an existing well-tested math library written by math and CS experts rather than trying to create your own.

#6 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 03 August 2014 - 04:43 PM

I just wanted to point a couple things out. I can't be 100% sure, but I believe the original quaternions were already normalized. After a lot of testing and examining, it looks as though the normalization simply traded error on one side for error on the other side, which resulted in a SEEMINGLY better angle result. I noticed this because I can literally renormalize a quaternion over and over again, and get different results each time.

 

I wanted to point this out because I am now no longer positive that a quaternion constructed from a normalized axis + angle will need normalized after being constructed. From what I've seen (from a lot of extreme random axis+angle generation), it is pretty much already normalized within a decent error tolerance.

 

edit: Here are the results:

 

q1: error-angle[0.00119] construct-length[0.999999880791], normalize-length[1.000000119209] quaternion[ -0.388950,-0.416175,-0.421772,0.705426 ]

q2: error-angle[0.00138] construct-length[0.999999880791], normalize-length[1.000000119209] quaternion[ -0.865744,0.019881,0.467512,0.177554 ]

q3: error-angle[0.00154] construct-length[0.999999880791], normalize-length[1.000000119209] quaternion[ -0.777527,-0.501608,-0.192569,0.326739 ]

(notice the error is always exactly 0.000000119209 distance from 1)

 

Numerical stability is a pain. Sometimes you have to really think through your algorithms and rewrite them to be somewhat less efficient but more stable. There's a _lot_ of work required to really understand numeric stability with floats. I don't myself pretend to really understand it. This is one of the (many) reasons why you should just use an existing well-tested math library written by math and CS experts rather than trying to create your own.

 

I agree. But from my limited experience, it seems next to impossible to create a 3D sim (regardless of a math library) without having to deal with these errors in some form or another anyway. Even something as simple as 1+1=2 can turn your game world upside-down if its not interpreted as 1+1=almost definitely 2.

 

Essentially, my engine relies on a very select subset of vital functions, so I really don't have a lot of work cut out for me. But getting this stumped on one function isn't really getting that point across, is it?

 

Thanks smile.png


Edited by Stephany, 03 August 2014 - 04:56 PM.


#7 Álvaro   Crossbones+   -  Reputation: 12997

Like
2Likes
Like

Posted 04 August 2014 - 05:47 AM

I just wanted to point a couple things out. I can't be 100% sure, but I believe the original quaternions were already normalized. After a lot of testing and examining, it looks as though the normalization simply traded error on one side for error on the other side, which resulted in a SEEMINGLY better angle result. I noticed this because I can literally renormalize a quaternion over and over again, and get different results each time.


I think the quaternion you posted originally was not properly normalized. Do you care to post a particular quaternion for which the renormalization isn't stable?


Even something as simple as 1+1=2 can turn your game world upside-down if its not interpreted as 1+1=almost definitely 2.


That seems to indicate you don't understand floating-point numbers very much: 1 + 1 is most definitely exactly 2.

#8 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 05 August 2014 - 11:45 AM

 

I just wanted to point a couple things out. I can't be 100% sure, but I believe the original quaternions were already normalized. After a lot of testing and examining, it looks as though the normalization simply traded error on one side for error on the other side, which resulted in a SEEMINGLY better angle result. I noticed this because I can literally renormalize a quaternion over and over again, and get different results each time.

I think the quaternion you posted originally was not properly normalized. Do you care to post a particular quaternion for which the renormalization isn't stable?

 

Well, it was as normalized as my normalize function will seem to allow it to be. And yeah, sure. Let me type something up..

 

Each line is of the same quaternion, renormalized again:

0.768565058708, 0.393124073744, 0.112918674946, 0.491945981979 (length: 1.000000119209)
0.768564939499, 0.393124014139, 0.112918660045, 0.491945922375 (length: 0.999999940395)
0.768565058708, 0.393124073744, 0.112918674946, 0.491945981979 (length: 0.999999940395)

 

another example:

-0.384467869997, -0.321283340454, 0.054897289723, 0.863682806492 (length: 1.000000119209)
-0.384467810392, -0.321283310652, 0.054897282273, 0.863682687283 (length: 0.999999940395)
-0.384467869997, -0.321283340454, 0.054897289723, 0.863682806492 (length: 0.999999940395)

 

one more:

0.335628807545, 0.205629050732, 0.067485921085, 0.916796505451 (length: 1.000000119209)
0.335628777742, 0.205629020929, 0.067485913634, 0.916796386242 (length: 0.999999940395)
0.335628807545, 0.205629050732, 0.067485921085, 0.916796505451 (length: 0.999999940395)

 

The error in length is always exactly 0.000000119209 away from 1. On the third attempt, I get the quaternion from the first with the length from the second. I assume this is because of digits beyond what I've printed out. I didn't try any further than 3 normalizes, but I assume it will jump back and forth.

 

 

Even something as simple as 1+1=2 can turn your game world upside-down if its not interpreted as 1+1=almost definitely 2.


That seems to indicate you don't understand floating-point numbers very much: 1 + 1 is most definitely exactly 2.

 

 

 

Sorry, I meant for that to be an exaggeration. You are correct, nonetheless.



#9 Álvaro   Crossbones+   -  Reputation: 12997

Like
0Likes
Like

Posted 05 August 2014 - 12:30 PM

I took your examples and tried to normalize them myself:
 

0.76856505870819091797, 0.39312407374382019043, 0.11291867494583129883, 0.49194598197937011719 (length: 1.00000011920928955078)
0.76856493949890136719, 0.39312401413917541504, 0.11291866004467010498, 0.49194592237472534180 (length: 1.00000000000000000000)
0.76856493949890136719, 0.39312401413917541504, 0.11291866004467010498, 0.49194592237472534180 (length: 1.00000000000000000000)

-0.38446786999702453613, -0.32128334045410156250, 0.05489728972315788269, 0.86368280649185180664 (length: 1.00000011920928955078)
-0.38446781039237976074, -0.32128331065177917480, 0.05489728227257728577, 0.86368268728256225586 (length: 1.00000000000000000000)
-0.38446781039237976074, -0.32128331065177917480, 0.05489728227257728577, 0.86368268728256225586 (length: 1.00000000000000000000)

0.33562880754470825195, 0.20562905073165893555, 0.06748592108488082886, 0.91679650545120239258 (length: 1.00000000000000000000)
0.33562880754470825195, 0.20562905073165893555, 0.06748592108488082886, 0.91679650545120239258 (length: 1.00000000000000000000)
0.33562880754470825195, 0.20562905073165893555, 0.06748592108488082886, 0.91679650545120239258 (length: 1.00000000000000000000)


Here's my code:
#include <cmath>
#include <cstdio>
#include <boost/math/quaternion.hpp>

typedef float Real;
typedef boost::math::quaternion<Real> Q;

void show_two_normalizations(Q q) {
  for (int i = 0; i < 3; ++i) {
    std::printf("%.20f, %.20f, %.20f, %.20f (length: %.20f)\n",
                q.R_component_1(),
                q.R_component_2(),
                q.R_component_3(),
                q.R_component_4(),
                abs(q));
    Real inv_length = 1 / abs(q);
    q *= inv_length;
  }
  std::puts("");
}

int main() {
  show_two_normalizations(Q(0.768565058708, 0.393124073744, 0.112918674946, 0.491945981979));
  show_two_normalizations(Q(-0.384467869997, -0.321283340454, 0.054897289723, 0.863682806492));
  show_two_normalizations(Q(0.335628807545, 0.205629050732, 0.067485921085, 0.916796505451));
}


#10 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 05 August 2014 - 05:03 PM

Sorry, I'm not sure I understand what you're trying to show me?

 

To be clear, the floating point errors didn't concern me as much as wanting to make sure the angle function is doing its job. I mean if there's something obvious I'm doing to produce the errors, I will gladly work to correct it, but AFAIK, its inherent to basic math.

 

Thanks again :)



#11 Lactose!   GDNet+   -  Reputation: 3277

Like
0Likes
Like

Posted 05 August 2014 - 06:18 PM


Sorry, I'm not sure I understand what you're trying to show me?

Looks like normalizing multiple times, with the results remaining stable and lengths equal to 1.00000000000000000000.



#12 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 05 August 2014 - 09:29 PM

 


Sorry, I'm not sure I understand what you're trying to show me?

Looks like normalizing multiple times, with the results remaining stable and lengths equal to 1.00000000000000000000.

 

 

I understood what was happening, I just didn't understand the purpose of it. But now I notice he's using boost, so I think I get the point.



#13 Álvaro   Crossbones+   -  Reputation: 12997

Like
0Likes
Like

Posted 06 August 2014 - 07:38 AM

I understood what was happening, I just didn't understand the purpose of it. But now I notice he's using boost, so I think I get the point.


And now I think that you don't: Using boost has nothing to do with anything. My point is that perhaps your renormalization procedure is broken, since the straight-forward code I wrote doesn't exhibit the undesired behavior you described. Perhaps you should post your renormalization code, because it might explain why you are seeing what you are seeing.

#14 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 06 August 2014 - 05:21 PM

 

I understood what was happening, I just didn't understand the purpose of it. But now I notice he's using boost, so I think I get the point.


And now I think that you don't: Using boost has nothing to do with anything. My point is that perhaps your renormalization procedure is broken, since the straight-forward code I wrote doesn't exhibit the undesired behavior you described. Perhaps you should post your renormalization code, because it might explain why you are seeing what you are seeing.

 

It's just a basic normalize method, scaling the quaternion by the inverse of its length [1 / sqrt( Dot(q,q) )] or [ 1 / sqrt(x*x + y*y + z*z + w*w) ]. But I'm pretty sure it's actually the way I compute the length that is causing the rounding error.

 

Looking at boost's abs() function, which I'm having difficulty tracing through all of their define usage, but I believe they are dividing all of the quaternion's components by the highest absolute component value, then squaring, then summing, then multiplying the result length with the highest absolute component value. I guess it may be worth the extra cycles to get rid of the small error.


Edited by Stephany, 06 August 2014 - 05:35 PM.


#15 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 07 August 2014 - 12:05 PM

It seems that even boost's method doesn't fix the problem. It slightly improves the rate that error happens, but I'm still encountering error every 4-5 random quaternions. For example, here are a few that boost cannot normalize:

 

 0.17163053154945374000, 0.53784161806106567000, -0.38471391797065735000, 0.73024976253509521000

 0.08311198651790618900, 0.03789226338267326400,  0.23039449751377106000, 0.96880078315734863000

-0.01666167378425598100, 0.09404919296503067000, -0.17354997992515564000, 0.98018240928649902000

 

I honestly don't believe the extra computations are worth it, if it only resolves the error in 1 out of every 5 problematic quaternions. Not unless I can come up with some alterations that eliminate it completely.



#16 Álvaro   Crossbones+   -  Reputation: 12997

Like
0Likes
Like

Posted 07 August 2014 - 02:43 PM

It's in the nature of floating-point numbers that the length of a vector cannot be made to be exactly 1. The question is, why is this a problem for you? Just make sure all of your code is tolerant to quaternions whose length is close to 1.

#17 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 07 August 2014 - 04:48 PM

It's in the nature of floating-point numbers that the length of a vector cannot be made to be exactly 1. The question is, why is this a problem for you?

 

I only became concerned about the error when you suspected my normalization was broken, because I assumed you knew what you were doing. What was the point of taking my random quaternions and showing that you could make their length exactly one if they cannot be made to be exactly one?

 

Since you can completely change which vectors normalize without visible error with small alterations to the math, posting code that shows perfect normalization is as simple as choosing the right math for specific vectors. I just don't understand why you would want to.

 

Anyway, I was able to reduce the chance to encounter normalization error from boost's 75% to almost 80% (testing with completely random components, 80% of the quaternions normalized so that their length == exactly 1). In addition, I was able to dump out the need to use abs() on each component. I am still playing around with it, and will post the function code when I'm finished. If I can get the chance for error low enough, I may consider actually using it.



#18 Álvaro   Crossbones+   -  Reputation: 12997

Like
0Likes
Like

Posted 08 August 2014 - 04:21 AM

I apologize for the confusion I may have introduced. You didn't (and still haven't) posted any code, so I tried to reproduce your results and I failed. Then I posted my attempt and you took it as advice for how to do things, which it wasn't intended to be. The only part that you should learn from what I did is to show complete information, including code to go with what you observe, so others can reproduce what you see.

#19 Stephany   Members   -  Reputation: 136

Like
0Likes
Like

Posted 08 August 2014 - 03:32 PM

I've been toying around with the algorithm to compute the length, and (believe) I've discovered a few (strange) things. The results I posted in the previous post was while generating random axis+angle rotations. So all of those quaternions were already close to being normalized (within 0.001 or so). I thought this might not be the best testing environment, so I changed it to generate random quaternions of two random types (50% of both) - both are completely random (using boost's randomizer) - the first type has a length ranging from 0.7 to 1.3, and the second type has a length ranging from 0.0001 to 1000.

 

With these quaternions, boost's method encounters error for about 45% of them, so apparently it is optimized to deal with nearly-normalized values (makes sense). However, I've been goofing around, toying with numbers, and I've found that if I multiply all of the squared components by the specific value 5.9292812347412109, then multiply the resulting length by its inverse, I get no error in over 94% of all of the quaternions. I then tried using this number again with just the crazy quaternions (+/- 1000), getting 94% accuracy, and then just on nearly-normalized quaternions (+/- 0.3), getting 93% accuracy, so the quaternion values don't seem to influence it much at all.

 

I don't pretend to understand why its happening, and was actually hoping someone out there may be able to shed some light on it. Also, I'm wondering if this is somehow machine-specific, or if its something that can be used universally on the standard floating point model. As a total side-note, I was able to get 96% error free with the value 83.852615356445313, but I like the idea of using a smaller value better, and the improvement wasn't significant.

 

Here's the code I've been messing around with. I apologize in advance if, like I said, I'm accidentally rigging the results in some way, or doing something really dumb here. But I appreciate anyone testing it out to see how well it works.



real ComputeLength(real x,real y,real z,real w)
{
    // square all components
    x *= x;
    y *= y;
    z *= z;
    w *= w;

    // prepare crazy scaler with inverse
    real mc = 5.9292812347412109f;
    real mi = 1 / mc;
    mi *= mi;

    // compute length scaled by crazy scaler inverse, then scale back to normal
    return mc * sqrt( x*mi + y*mi + z*mi + w*mi );
}

I apologize for the confusion I may have introduced. You didn't (and still haven't) posted any code, so I tried to reproduce your results and I failed.

 

I thought I did post all of the code you asked to see. As I said, my original normalization code literally multiplies the components of the quaternion by the inverse of its length - literally { this.Scale( 1 / sqrt(x*x + y*y + z*z + w*w) ); }, where Scale() simply multiplies the components by the scaler given. If there's something else you want to see, let me know.

 

The only part that you should learn from what I did is to show complete information, including code to go with what you observe, so others can reproduce what you see.

 

Well, I tried to post all of the code that I thought was relevant. But I'm inexperienced when it comes to battling floating point error, so I don't really know what is relevant. But you are free to look at any of my code you wish. Just let me know what you would like to see.


Edited by Stephany, 08 August 2014 - 03:34 PM.


#20 quasar3d   Members   -  Reputation: 687

Like
2Likes
Like

Posted 13 August 2014 - 10:58 AM

Hey guys,

I'm in the process of working out my math library, and so I was testing out a function that returns the angle between two quaternions..

{ return 2.0f * acos( Abs( Dot4( qa, qb ) ) ); }

 

.. but for some reason, I'm either getting a lot of floating point error in the result, or I'm not checking for a situation that I should be. While testing a quaternion (which was generated by a random axis+angle rotation and appears to be very close to normalized)..

{ x=0.0172970667 y=-0.0245058369 z=0.0205858145, w=-0.999337912    }

.. with itself, I'm getting a result angle of 0.00138106791 (or almost 0.1 degrees)..

 

I'm just wondering if this is acceptable error when working with float variables? And is there anything I can do to improve this issue other than switching to double type or something else as drastic?

 

edit note: After testing some more, the highest "error angle" I've been able to generate (through random axis-angles) is 0.001953125. And that was getting the angle (from itself) of a quaternion generated by the axis @ angle: { -0.833756,0.551120,-0.033417 @ 2.960138559341 } (quaternion result: { -0.830327,0.548853,-0.033279,0.090603 } )

 

Thank you

 

The reason why the error gets so big, is that the inverse cosine function is very steep around 1. This has the effect that the (even exact) inverse cosine of a dot product which is only a tiny bit off, will give a pretty big angle difference.

 

For example, the cosine of 0.1 degree is 0.99999847691, and so if your dot product would give 0.99999847691 (which is a pretty good approximation of 1), the angle you get will be around 0.1

 

I bet that the reason why, after renormalizing your quaternions, you did get the correct result, was that this gave a dot product of exactly 1, but I don't think this will work for all quaternions. There will certainly be normalized quaternions, which give a dot product with themselves not exactly equal to 1.

 

The good news is that it's only this bad when you're computing the angle between quaternions which are almost parallel. For quaternions which are not nearly parallel, the result will be more accurate.


Edited by quasar3d, 13 August 2014 - 11:11 AM.






PARTNERS