09 November 2019, 17:20 | #1 |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
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.
|
09 November 2019, 19:42 | #2 |
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 3,302
|
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 | |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
Quote:
|
|
09 November 2019, 21:50 | #4 |
Lemon. / Core Design
Join Date: Mar 2016
Location: Tier 5
Posts: 1,213
|
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 |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
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 |
Defendit numerus
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 54
Posts: 4,488
|
|
09 November 2019, 22:54 | #7 | |
Defendit numerus
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 54
Posts: 4,488
|
Quote:
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 | |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
Quote:
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 |
Registered User
Join Date: Jun 2015
Location: Germany
Posts: 1,924
|
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 | |||
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 3,302
|
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:
Quote:
Quote:
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 | |
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 3,302
|
Quote:
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 |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
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 | |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
But, they don't though, do they? It sounds like you're in a better position than me to explain why.
Quote:
|
|
10 November 2019, 13:36 | #14 | |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
Quote:
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 |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
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(); } 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] ... 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]); } Edit: Very slowly, 0x0FFF7544 = 0.999868, and if I run it for longer, I get 0x0FE88AC1 = 0.994273. Last edited by deimos; 21 November 2021 at 11:31. |
10 November 2019, 14:28 | #16 | |
Defendit numerus
Join Date: Mar 2017
Location: Crossing the Rubicon
Age: 54
Posts: 4,488
|
Quote:
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 |
|
10 November 2019, 14:53 | #17 | |
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
Quote:
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 | |
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 3,302
|
Quote:
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 | |||
It's coming back!
Join Date: Jul 2018
Location: comp.sys.amiga
Posts: 762
|
Quote:
Quote:
Quote:
|
|||
11 November 2019, 09:27 | #20 |
Inviyya Dude!
Join Date: Sep 2016
Location: Amiga Island
Posts: 2,793
|
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) | |
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 |
|
|