English Amiga Board


Go Back   English Amiga Board > Coders > Coders. General

 
 
Thread Tools
Old 09 November 2019, 17:20   #1
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Fixed point maths, quaternions, rounding errors and normalisation.

I’ve just updated the 3D game thing I’m writing to use quaternions to hold the orientation / attitude of the camera and the objects I’m rendering.

It all seems to work and was not difficult to code. I’m reasonably happy with it.

But, I know there are rounding errors accumulating each time I pre-multiply the current quaternion with one that represents the change in orientation. All the literature says to expect this in the form of the quaternion drifting away from unit length, and to rectify it, once it has reached a certain point, by dividing the quaternion by its length, thus returning it to a unit length.

I’m using fixed point maths for everything. Currently 16 bits, 2 before the point, 14 after.

My rounding errors so far are small, but they do exist. They don’t become a problem in the small demo / play about code that I have at the moment, but I do suspect that they’ll cause issues over the time it takes to play the game for real.

I have questions about the use of quaternions in this way.
  • Is 2:14 fixed point format enough precision for this? Should I keep my precision when creating the rotation matrix that results from them? If so, how high? 2:30? And should I embiggen my sine table to match?

  • How far should I let the quaternions drift before I normalise them? Inversely, how do I calculate when it’s possible for the normalisation to be beneficial given the limitations of the fixed point maths, including the calculation of the length which involves a square root.
deimos is offline  
Old 09 November 2019, 19:42   #2
Thomas Richter
Registered User
 
Join Date: Jan 2019
Location: Germany
Posts: 399
Quote:
Originally Posted by deimos View Post
Is 2:14 fixed point format enough precision for this?
Without knowing your target precision, nobody can answer. But why do you use quaternions for this and not ordinary rotation matrices? It seems to overly complicate the thing (plus, having to take care about both real and imaginary part). For computing the square root in fixed point, I provided an algorithm. It is not hard to do that.
Thomas Richter is offline  
Old 09 November 2019, 21:38   #3
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Quote:
Originally Posted by Thomas Richter View Post
Without knowing your target precision, nobody can answer. But why do you use quaternions for this and not ordinary rotation matrices? It seems to overly complicate the thing (plus, having to take care about both real and imaginary part). For computing the square root in fixed point, I provided an algorithm. It is not hard to do that.
Thomas, I'm not sure how you're trying to help. Would you like me to explain the issues that "ordinary rotation matrices" bring, and how the use of quaternions overcome them, while leading to more efficient code? Or are you confused about the supposedly "imaginary" nature of quaternions? And with regard to square root algorithms, I can point you to one from a trusted, published, source.
deimos is offline  
Old 09 November 2019, 21:50   #4
DanScott
Lemon. / Core Design

DanScott's Avatar
 
Join Date: Mar 2016
Location: Sunny Bournemouth, UK
Posts: 619
I just wonder if ultimately this (quaternions) would be slower than standard 3x3 matrix math on Amiga?

Btw, I work in Unity on a daily basis, and most of the maths is "under the hood" so to speak...
DanScott is offline  
Old 09 November 2019, 21:55   #5
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Quote:
Originally Posted by DanScott View Post
I just wonder if ultimately this (quaternions) would be slower than standard 3x3 matrix math on Amiga?
Standard approach is to convert to a matrix before you do all your vertices, so, no. Instead of creating and maintaining a matrix, you just convert, and the number of calculations is the same for the bit that matters.
deimos is offline  
Old 09 November 2019, 22:25   #6
ross
Per aspera ad astra

ross's Avatar
 
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 49
Posts: 2,530
Quote:
Originally Posted by DanScott View Post
Btw, I work in Unity on a daily basis, and most of the maths is "under the hood" so to speak...
And "under the hood" Unity use quaternions
ross is offline  
Old 09 November 2019, 22:54   #7
ross
Per aspera ad astra

ross's Avatar
 
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 49
Posts: 2,530
Quote:
Originally Posted by deimos View Post
I have questions about the use of quaternions in this way.
  • Is 2:14 fixed point format enough precision for this? Should I keep my precision when creating the rotation matrix that results from them? If so, how high? 2:30? And should I embiggen my sine table to match?

  • How far should I let the quaternions drift before I normalise them? Inversely, how do I calculate when it’s possible for the normalisation to be beneficial given the limitations of the fixed point maths, including the calculation of the length which involves a square root.
I can't help you with this because your 3D math is sure much advanced than mine (I can only rotate some stupid cubes, some polygons or some stars in space )
And in any case I never used quaternions.
But for the various matrix calculations I used 2:14 and the results always seemed good to me.
If you want to continue using a bare 68k, 2:30 it's not an option, the internal ALU is 16-bit, so even a simple sum would require many more cycles.
I am very curious to see your results with quaternions.
ross is offline  
Old 10 November 2019, 05:36   #8
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Quote:
Originally Posted by ross View Post
I can't help you with this because your 3D math is sure much advanced than mine (I can only rotate some stupid cubes, some polygons or some stars in space )
And in any case I never used quaternions.
But for the various matrix calculations I used 2:14 and the results always seemed good to me.
If you want to continue using a bare 68k, 2:30 it's not an option, the internal ALU is 16-bit, so even a simple sum would require many more cycles.
I am very curious to see your results with quaternions.
I'm definitely sticking with bare 68k.

Maybe 2:30 can be an option if it's restricted to a tiny section of code where the performance isn't critical though? Maybe it's necessary for the normalisation step, which may turn out to be very infrequent. These are things I just don't know.

I will try and upload an executable and log files later.
deimos is offline  
Old 10 November 2019, 08:08   #9
grond
Registered User

 
Join Date: Jun 2015
Location: Germany
Posts: 769
In a Doom-type game you could just reset the vectors each time the player view more or less aligns with one of the base vectors. Who would notice, when turning around, that one turn had a slightly smaller or larger angle to make the camera vector hit a right angle?
grond is offline  
Old 10 November 2019, 11:47   #10
Thomas Richter
Registered User
 
Join Date: Jan 2019
Location: Germany
Posts: 399
Quote:
Originally Posted by deimos View Post
Thomas, I'm not sure how you're trying to help.
By asking the right questions and providing code. How can one answer the question whether a given precision is good enough without knowing what good enough means? If the peak error (l^infty) of the rotated vector is to be estimated, a hard error bound is given by the l^1 row norm of the errors of the rotation matrix.



Quote:
Originally Posted by deimos View Post
Would you like me to explain the issues that "ordinary rotation matrices" bring
It is the obvious approach, isn't it? I do not see any issues, I just wonder why this rather obvious approach is not used.



Quote:
Originally Posted by deimos View Post

, and how the use of quaternions overcome them, while leading to more efficient code? Or are you confused about the supposedly "imaginary" nature of quaternions?
No, I just wonder why one picks quaternions when rotation matrices do the job. Even more so as quaternions (aka SU(2)) are not fully equivalent to rotation matrices (SO(3)), but only up to a sign the former can pick up, see https://en.wikipedia.org/wiki/3D_rot...SO(3)_and_SU(2)



Quote:
Originally Posted by deimos View Post


And with regard to square root algorithms, I can point you to one from a trusted, published, source.
Is an international standard good enough for you? The described algorithm is an integer implementation of it - actually, it is pretty much known and not novel. It is also the binary version of the manual "pen and paper" digit-by-digit square root.



If this makes you feel any better, mathieeedoubbas uses the same algorithm, for the IEEE mantissa of double precision numbers.
Thomas Richter is offline  
Old 10 November 2019, 11:49   #11
Thomas Richter
Registered User
 
Join Date: Jan 2019
Location: Germany
Posts: 399
Quote:
Originally Posted by deimos View Post
Maybe it's necessary for the normalisation step, which may turn out to be very infrequent. These are things I just don't know.

Look, once again, without knowing the precision you want to reach in the application (as in, "how precise do the vectors you attempt to rotate have to be over how many iterations"), nobody would be able to answer.
Thomas Richter is offline  
Old 10 November 2019, 13:31   #12
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Quote:
Originally Posted by grond View Post
In a Doom-type game you could just reset the vectors each time the player view more or less aligns with one of the base vectors. Who would notice, when turning around, that one turn had a slightly smaller or larger angle to make the camera vector hit a right angle?
I don't think I have any opportunities like that, unfortunately. Possibly when the player changes camera angle or performs an action like shooting which would disguise any adjustments that the normalisation would cause, but I think I need to be more regular than that.
deimos is offline  
Old 10 November 2019, 13:34   #13
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Quote:
Originally Posted by Thomas Richter View Post
rotation matrices do the job
But, they don't though, do they? It sounds like you're in a better position than me to explain why.

Quote:
Originally Posted by Thomas Richter View Post
Is an international standard good enough for you? The described algorithm is an integer implementation of it - actually, it is pretty much known and not novel. It is also the binary version of the manual "pen and paper" digit-by-digit square root.



If this makes you feel any better, mathieeedoubbas uses the same algorithm, for the IEEE mantissa of double precision numbers.
It might surprise you, but I didn't actually come here to discuss square root algorithms.
deimos is offline  
Old 10 November 2019, 13:36   #14
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Quote:
Originally Posted by Thomas Richter View Post
Look, once again, without knowing the precision you want to reach in the application (as in, "how precise do the vectors you attempt to rotate have to be over how many iterations"), nobody would be able to answer.
I came here looking for advice from people with experience.

Perhaps someone with experience could say, "well, game engine x renormalises its quaternions when they drift more than y% away from unit length". That would be a worthwhile contribution to the conversation.

Or they could explain how to calculate the limitations of the particular fixed point size used in order to work out when it's not even worth trying to normalise. That would be helpful too.

We could even discuss the cost of normalisation to try and work out how often we can afford to normalise.

But to refuse to engage until your question is answered is unhelpful, particularly as it's a question that, a) can only be answered through experience, b) you have provided no help or guidance is how to answer, and c) may not even be relevant once the limitations of the fixed point maths are taken into account.
deimos is offline  
Old 10 November 2019, 13:54   #15
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Quote:
Originally Posted by ross View Post
I am very curious to see your results with quaternions.
I've attached the latest executable and the log output it generates.

My main loop currently does this:

Code:
    for (;;) {
        // ... stuff

        GameControls_Tick();

        Quaternion q;
        QuaternionFromOrientation(&q, &gameControls.controlSurfaces);

        Quaternion r = ((Entity *) cyclone)->attitude;

        MultiplyQuaternions(&((Entity *) cyclone)->attitude, &r, &q);
        PrintQuaternion("a", &((Entity *) cyclone)->attitude);

        DrawScreen();
    }
The output is something like this:

Code:
a = (4000, 0000, 0000, 0000) [10000000]
a = (4000, 0000, 0000, 0000) [10000000]
a = (4000, FF9B, 0000, 0000) [100027D9]
a = (3FFD, FED2, 0000, 0000) [0FFFE44D]
a = (3FF4, FDA4, 0000, 0000) [0FFF91A0]
a = (3FE0, FC12, 0000, 0000) [0FFF7544]
...
The last column is the square of the length of the quaternion without the right shift that would normally be done after multiplying fixed point numbers.

Code:
LONG QuaternionLengthSquared(const Quaternion * q) {
    return ((LONG) q->value[A] * (LONG) q->value[A] +
            (LONG) q->value[B] * (LONG) q->value[B] +
            (LONG) q->value[C] * (LONG) q->value[C] +
            (LONG) q->value[D] * (LONG) q->value[D]);
}
You can see it drifts away from 1 (<<28).

Edit: Very slowly, 0x0FFF7544 = 0.999868, and if I run it for longer, I get 0x0FE88AC1 = 0.994273.
Attached Files
File Type: zip quaternions.zip (23.2 KB, 13 views)

Last edited by deimos; 10 November 2019 at 14:27.
deimos is offline  
Old 10 November 2019, 14:28   #16
ross
Per aspera ad astra

ross's Avatar
 
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 49
Posts: 2,530
Quote:
Originally Posted by deimos View Post
The last column is the square of the length of the quaternion without the right shift that would normally be done after multiplying fixed point numbers.
Is the following too slow?

Code:
    moveq   #0,d1           ;but can be an useful value from a previous calc    
    move.l  #$0FFFE44D,d0   ;your 4.28 partial result

    add.l   d0,d0
    add.l   d0,d0
    add.w   d0,d0
    swap    d0
    addx.w  d1,d0           ;2.14
I'll use this 'rounding' when more precision is needed in my code (using partial results if possible a little better..).
ross is offline  
Old 10 November 2019, 14:53   #17
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Quote:
Originally Posted by ross View Post
Is the following too slow?

Code:
    moveq   #0,d1           ;but can be an useful value from a previous calc    
    move.l  #$0FFFE44D,d0   ;your 4.28 partial result

    add.l   d0,d0
    add.l   d0,d0
    add.w   d0,d0
    swap    d0
    addx.w  d1,d0           ;2.14
I'll use this 'rounding' when more precision is needed in my code (using partial results if possible a little better..).
Thanks, but I think you're answering the wrong question. There's nothing wrong with the 4.28 numbers, it's the rest of them that need to be corrected.

The square root of the 4.28 number is the length of the quaternion (think vector) described by the 2.14 numbers. If there were no rounding errors then the 4.28 number would always be 1<<28, but because we're always moving the quaternion (by multiplying it with another one representing where the control stick is pointed), the rounding errors build up, leading to a quaternion that is slightly off unit length. I need to divide the four 2:14 numbers by the square root of the 4.28 number (or multiply by the inverse square root, but I don't think that's possible in fixed point).

I need to work out, first, when is the division actually possible with the fixed point maths, and second, when do I want to do it? I see these two questions as interlinked, as the answer to the second may be forced by the first.

Last edited by deimos; 10 November 2019 at 16:52.
deimos is offline  
Old 10 November 2019, 15:51   #18
Thomas Richter
Registered User
 
Join Date: Jan 2019
Location: Germany
Posts: 399
Quote:
Originally Posted by deimos View Post
Perhaps someone with experience could say, "well, game engine x renormalises its quaternions when they drift more than y% away from unit length". That would be a worthwhile contribution to the conversation.
I doubt there is an answer like this. The answer is more likely: If your screen has a resolution of W, and you multiply a vector with a matrix to obtain a position on the screen, what is the resolution to ensure that the placement of such a vector is pixel-precise after N multiplications. That is an answer I can give, but for that, the screen dimension needs to be known, and the number of multiplications needs to be known.


If you have a f-fractional bit matrix, then clearly, the resulting relative error of a multiplication with a 4x4 matrix can not be higher than 4*2^-f. If you have a screen resolution of W pixel, then you get a maxmal absolute error of W*4*2^-f. Approximately, after N iterations, you get an error of N*W*4*2^-f pixels.


This is not really "high mathematics", just some basic estimates.



Concerning quaternions: After thinking about it, I believe you must be using homogeneous coordinates. In such a case, the sign collected from the SU(2) rotations (instead of SO(3) = rotation matrices) does not matter. But without seeing your formulae, it is hard to tell. I'm also not clear why this should be better than the typical 4x4 matrices you use for coordinate computation in projective space (aka "homogeneous coordinates).
Thomas Richter is offline  
Old 10 November 2019, 16:33   #19
deimos
Registered User

 
Join Date: Jul 2018
Location: France
Posts: 550
Quote:
Originally Posted by Thomas Richter View Post
I doubt there is an answer like this. The answer is more likely: If your screen has a resolution of W, and you multiply a vector with a matrix to obtain a position on the screen, what is the resolution to ensure that the placement of such a vector is pixel-precise after N multiplications. That is an answer I can give, but for that, the screen dimension needs to be known, and the number of multiplications needs to be known.
That's swell, but it would be an answer to a question that wasn't asked.

Quote:
Originally Posted by Thomas Richter View Post
If you have a f-fractional bit matrix, then clearly, the resulting relative error of a multiplication with a 4x4 matrix can not be higher than 4*2^-f. If you have a screen resolution of W pixel, then you get a maxmal absolute error of W*4*2^-f. Approximately, after N iterations, you get an error of N*W*4*2^-f pixels.
Except we haven't moved from quaternion to matrix yet. And given that the quaternion is the only point where we can attempt to rectify the rounding errors, and the 14 bits of precision and effective [-2, +2) range we have will certainly constrain us, can we calculate the earliest we can normalise, knowing that we need to divide by the norm (or multiply by it's inverse) and that involves a square root?

Quote:
Originally Posted by Thomas Richter View Post
Concerning quaternions: After thinking about it, I believe you must be using homogeneous coordinates. In such a case, the sign collected from the SU(2) rotations (instead of SO(3) = rotation matrices) does not matter. But without seeing your formulae, it is hard to tell. I'm also not clear why this should be better than the typical 4x4 matrices you use for coordinate computation in projective space (aka "homogeneous coordinates).
Nope. We are concerned only with rotation here. Translation and the perspective transform occur separately (and must do, as they rely on a different level of precision in their fixed point maths), so it's all normal, not homogeneous coordinates.
deimos is offline  
Old 11 November 2019, 09:27   #20
Steril707
Tigerskunk!

Steril707's Avatar
 
Join Date: Sep 2016
Location: Amiga Island
Posts: 1,455
Just for understanding, when I use fixed point I do with 8:8. Which is for movement of BOBs or Sprites on a 2d screen.

How can you just use 2:14? I mean, two bits for the coordinates of the whole number seems a bit small, isn't it?
How does this work?
Steril707 is offline  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Aimed missiles and fixed-point divisions phx Coders. Asm / Hardware 18 10 November 2019 10:48
[vbcc/win] Doing some maths.. guy lateur Coders. C/C++ 21 21 July 2017 01:51
WinUAE Assembly dump from point to point? Sim085 support.WinUAE 3 11 April 2017 19:43
FPU rounding issues phx support.WinUAE 6 12 November 2014 10:03
PFS2 disk errors unable to be fixed by diskvalid basshead support.Apps 9 07 October 2012 10:21

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 07:26.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, vBulletin Solutions Inc.
Page generated in 0.10039 seconds with 16 queries