• 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
Stephany

Quaternion angle with itself > 0.001

20 posts in this topic

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
0

Share this post


Link to post
Share on other sites

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.

1

Share this post


Link to post
Share on other sites

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.

0

Share this post


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

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

 

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.

0

Share this post


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

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites


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.

0

Share this post


Link to post
Share on other sites

 


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.

0

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

 

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
0

Share this post


Link to post
Share on other sites

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.

0

Share this post


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

Share this post


Link to post
Share on other sites

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.

0

Share this post


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

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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
2

Share this post


Link to post
Share on other sites
You can also compute the angle between quaternions using
  dot_product = dot4(qa, qb);
  dot_product_squared = dot_product * dot_product;
  denominator = dot4(qa, qa) * dot4(qb, qb);
  return 2.0f * acos(sqrt(abs(dot_product_squared / denominator)));
I haven't tried it, so there could be mistakes. The idea is to not rely on the inputs being normalized, and write the expression in such a way that you are guaranteed to get exactly 0 if you qa==qb.
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