English Amiga Board Fixed point maths, quaternions, rounding errors and normalisation.
 Register Amiga FAQ Rules & Help Members List  /  Moderators List Today's Posts Mark Forums Read

 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.
09 November 2019, 19:42   #2
Thomas Richter
Registered User

Join Date: Jan 2019
Location: Germany
Posts: 399
Quote:
 Originally Posted by deimos 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.

09 November 2019, 21:38   #3
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 550
Quote:
 Originally Posted by Thomas Richter 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.

 09 November 2019, 21:50 #4 DanScott Lemon. / Core Design   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...
09 November 2019, 21:55   #5
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 550
Quote:
 Originally Posted by DanScott 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.

09 November 2019, 22:25   #6
ross

Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 49
Posts: 2,530
Quote:
 Originally Posted by DanScott 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

09 November 2019, 22:54   #7
ross

Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 49
Posts: 2,530
Quote:
 Originally Posted by deimos 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.

10 November 2019, 05:36   #8
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 550
Quote:
 Originally Posted by ross 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.

 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?
10 November 2019, 11:47   #10
Thomas Richter
Registered User

Join Date: Jan 2019
Location: Germany
Posts: 399
Quote:
 Originally Posted by deimos 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 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 , 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 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.

10 November 2019, 11:49   #11
Thomas Richter
Registered User

Join Date: Jan 2019
Location: Germany
Posts: 399
Quote:
 Originally Posted by deimos 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.

10 November 2019, 13:31   #12
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 550
Quote:
 Originally Posted by grond 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.

10 November 2019, 13:34   #13
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 550
Quote:
 Originally Posted by Thomas Richter 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 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.

10 November 2019, 13:36   #14
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 550
Quote:
 Originally Posted by Thomas Richter 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.

10 November 2019, 13:54   #15
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 550
Quote:
 Originally Posted by ross 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
 quaternions.zip (23.2 KB, 13 views)

Last edited by deimos; 10 November 2019 at 14:27.

10 November 2019, 14:28   #16
ross

Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 49
Posts: 2,530
Quote:
 Originally Posted by deimos 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

swap    d0
I'll use this 'rounding' when more precision is needed in my code (using partial results if possible a little better..).

10 November 2019, 14:53   #17
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 550
Quote:
 Originally Posted by ross 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.

10 November 2019, 15:51   #18
Thomas Richter
Registered User

Join Date: Jan 2019
Location: Germany
Posts: 399
Quote:
 Originally Posted by deimos 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).

10 November 2019, 16:33   #19
deimos
Registered User

Join Date: Jul 2018
Location: France
Posts: 550
Quote:
 Originally Posted by Thomas Richter 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 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 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.

 11 November 2019, 09:27 #20 Steril707 Tigerskunk!   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?

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

 Similar Threads Thread Thread Starter Forum Replies Last Post phx Coders. Asm / Hardware 18 10 November 2019 10:48 guy lateur Coders. C/C++ 21 21 July 2017 01:51 Sim085 support.WinUAE 3 11 April 2017 19:43 phx support.WinUAE 6 12 November 2014 10:03 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home News Main     Amiga scene     Retrogaming General Discussion     Nostalgia & memories Support     New to Emulation or Amiga scene         Member Introductions     support.WinUAE     support.WinFellow     support.OtherUAE     support.FS-UAE         project.AmigaLive     support.Hardware         Hardware mods         Hardware pics     support.Games     support.Demos     support.Apps     support.Amiga Forever     support.Amix     support.Other Requests     request.UAE Wishlist     request.Old Rare Games     request.Demos     request.Apps     request.Modules     request.Music     request.Other     Looking for a game name ?     Games images which need to be WHDified abime.net - Hall Of Light     HOL news     HOL suggestions and feedback     HOL data problems     HOL contributions abime.net - Amiga Magazine Rack     AMR news     AMR suggestions and feedback     AMR data problems     AMR contributions abime.net - Home Projects     project.Amiga Lore     project.EAB     project.IRC     project.Mods Jukebox     project.Wiki abime.net - Hosted Projects     project.aGTW     project.APoV     project.ClassicWB     project.Jambo!     project.Green Amiga Alien GUIDES     project.Maptapper     project.Sprites     project.WinUAE - Kaillera Other Projects     project.Amiga Demo DVD     project.Amiga Game Factory     project.CARE     project.EAB File Server     project.CD32 Conversion     project.Game Cover Art         GCA.Feedback and Suggestions         GCA.Work in Progress         GCA.Cover Requests         GCA.Usefull Programs         GCA.Helpdesk     project.KGLoad     project.MAGE     project.Missing Full Shareware Games     project.SPS (was CAPS)     project.TOSEC (amiga only)     project.WHDLoad         project.Killergorilla's WHD packs Misc     Amiga websites reviews     MarketPlace         Swapshop     Kinky Amiga Stuff     Collections     EAB's competition Coders     Coders. General         Coders. Releases         Coders. Tutorials     Coders. Asm / Hardware     Coders. System         Coders. Scripting         Coders. Nextgen     Coders. Language         Coders. C/C++         Coders. AMOS         Coders. Blitz Basic     Coders. Contest         Coders. Entries Creation     Graphics         Graphics. Work In Progress         Graphics. Finished Work         Graphics. Tutorials     Music         Music. Work In Progress         Music. Finished Work         Music. Tutorials Off Topic     OT - General     OT - Entertainment     OT - Sports     OT - Technical     OT - Gaming

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

 -- EAB3 skin ---- EAB2 skin ---- Mobile skin Archive - Top