Fixed point maths, quaternions, rounding errors and normalisation.

[deimos]

Originally Posted by Steril707

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?

2:14 is to get the most accuracy for a sin table, and most geometric operations that never go outside of -1 to +1. You need 2 bits in front because of the sign.

You don't necessarily stay in 2:14, and I don't once the rotation is done. If you store your "world" coordinates in 14:2, when you multiply them with a 2:14 you get 16:16. Drop the lower word to make a whole number and you're done (which I guess is the same as what you're doing with your 8:8).

[grond]

Originally Posted by deimos

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.

Your player runs around in all possible directions. If the player runs within say 1% of a rectangular angle (i.e. almost aligned with either the x or y axes) just reset him to exactly x or y aligned for a single frame. You could even have straight passages in your levels to assure that the player sometimes runs in almost exactly x or y direction. I assume you will also have switches and doors that need to be operated. IIRC in Doom you will be aligned to exactly facing the switch when you operate it. Might be for a reason. If you store a set of camera vectors in the switch or door, you could replace your crippling camera vectors with this set of vectors each time the player operates the switch.

Of course, you could always renormalise the vectors whenever the player is not moving and fps matters less (OTOH, this might make slight distortions in the view resulting from the crippled vectors obvious because the view is suddenly changing a bit each time the player stops after running around for some time).

[deimos]

Originally Posted by grond

I assume you will also have switches and doors that need to be operated.

It's a flight simulator.

[grond]

Originally Posted by deimos

2:14 is to get the most accuracy for a sin table

I have 68k code for an integer sin/cos Taylor approximation with a maximum error of something like 0.5% somewhere. It uses four MULs, IIRC and might be 020+ only, I don't remember, I never coded for plain 68000. Using more MULs it could be made to have an error smaller than the LSB in the output variable. Of course, I wouldn't use the code for real-time calculations on a slow processor but certainly for setting up precalced tables (I'm not very fond of LUTs in general and even less so for LUTs that are loaded from disk).

Anyway, I just use an unsigned 16 bit number as input variable and a 16 bit signed number as output variable effectively turning the sine function into something like f(x)=32767*sin(2*pi*x/65536).

Not sure this is of any value to you but it popped up in my brain when reading about your 2.14 numbers while my morning coffee is still being processed...

[grond]

Originally Posted by deimos

It's a flight simulator.

Aw, damn...

[Tigerskunk]

Originally Posted by deimos

2:14 is to get the most accuracy for a sin table, and most geometric operations that never go outside of -1 to +1. You need 2 bits in front because of the sign.

You don't necessarily stay in 2:14, and I don't once the rotation is done. If you store your "world" coordinates in 14:2, when you multiply them with a 2:14 you get 16:16. Drop the lower word to make a whole number and you're done (which I guess is the same as what you're doing with your 8:8).

Ah okay, got it now...
Thanks for the explanation..

[ross]

Just in case someone need it, this is my asm sin_cos LUT generator in 2:14 precision (requires a defined quadrant).
At the end you have five quadrants (to support cos without wrap).
Full angle 2048pts.

sin_cos_generator:
		lea sin_tab+32*16*2-2(pc),a0
		move.w  (a0)+,d1
.l0		move.w  #32*16-1,d0
		movea.l a0,a1
		move.w  d1,(a1)+
.l1		move.w  -(a0),(a1)+
		dbf     d0,.l1
		move.w  -(a1),d1
		movea.l a1,a0
		lsr.w   #7,d0
.l2		move.w  d1,(a0)+
		move.w  -(a1),d1
		neg.w   d1
		dbf     d0,.l2
		bmi.b   .l0
		rts

sin_tab:
		dc.w	$0000,$0032,$0065,$0097,$00c9,$00fb,$012e,$0160,$0192,$01c4,$01f7,$0229,$025b,$028d,$02c0,$02f2
		dc.w	$0324,$0356,$0388,$03bb,$03ed,$041f,$0451,$0483,$04b5,$04e7,$051a,$054c,$057e,$05b0,$05e2,$0614
		dc.w	$0646,$0678,$06aa,$06dc,$070e,$0740,$0772,$07a4,$07d6,$0807,$0839,$086b,$089d,$08cf,$0901,$0932
		dc.w	$0964,$0996,$09c7,$09f9,$0a2b,$0a5c,$0a8e,$0ac0,$0af1,$0b23,$0b54,$0b85,$0bb7,$0be8,$0c1a,$0c4b
		dc.w	$0c7c,$0cae,$0cdf,$0d10,$0d41,$0d72,$0da4,$0dd5,$0e06,$0e37,$0e68,$0e99,$0eca,$0efb,$0f2b,$0f5c
		dc.w	$0f8d,$0fbe,$0fee,$101f,$1050,$1080,$10b1,$10e1,$1112,$1142,$1173,$11a3,$11d3,$1204,$1234,$1264
		dc.w	$1294,$12c4,$12f4,$1324,$1354,$1384,$13b4,$13e4,$1413,$1443,$1473,$14a2,$14d2,$1501,$1531,$1560
		dc.w	$1590,$15bf,$15ee,$161d,$164c,$167c,$16ab,$16da,$1709,$1737,$1766,$1795,$17c4,$17f2,$1821,$184f
		dc.w	$187e,$18ac,$18db,$1909,$1937,$1965,$1993,$19c1,$19ef,$1a1d,$1a4b,$1a79,$1aa7,$1ad4,$1b02,$1b30
		dc.w	$1b5d,$1b8a,$1bb8,$1be5,$1c12,$1c3f,$1c6c,$1c99,$1cc6,$1cf3,$1d20,$1d4d,$1d79,$1da6,$1dd3,$1dff
		dc.w	$1e2b,$1e58,$1e84,$1eb0,$1edc,$1f08,$1f34,$1f60,$1f8c,$1fb7,$1fe3,$200f,$203a,$2065,$2091,$20bc
		dc.w	$20e7,$2112,$213d,$2168,$2193,$21be,$21e8,$2213,$223d,$2268,$2292,$22bc,$22e7,$2311,$233b,$2365
		dc.w	$238e,$23b8,$23e2,$240b,$2435,$245e,$2488,$24b1,$24da,$2503,$252c,$2555,$257e,$25a6,$25cf,$25f8
		dc.w	$2620,$2648,$2671,$2699,$26c1,$26e9,$2711,$2738,$2760,$2788,$27af,$27d6,$27fe,$2825,$284c,$2873
		dc.w	$289a,$28c1,$28e7,$290e,$2935,$295b,$2981,$29a7,$29ce,$29f4,$2a1a,$2a3f,$2a65,$2a8b,$2ab0,$2ad6
		dc.w	$2afb,$2b20,$2b45,$2b6a,$2b8f,$2bb4,$2bd8,$2bfd,$2c21,$2c46,$2c6a,$2c8e,$2cb2,$2cd6,$2cfa,$2d1e
		dc.w	$2d41,$2d65,$2d88,$2dab,$2dcf,$2df2,$2e15,$2e37,$2e5a,$2e7d,$2e9f,$2ec2,$2ee4,$2f06,$2f28,$2f4a
		dc.w	$2f6c,$2f8d,$2faf,$2fd0,$2ff2,$3013,$3034,$3055,$3076,$3097,$30b8,$30d8,$30f9,$3119,$3139,$3159
		dc.w	$3179,$3199,$31b9,$31d8,$31f8,$3217,$3236,$3255,$3274,$3293,$32b2,$32d0,$32ef,$330d,$332c,$334a
		dc.w	$3368,$3386,$33a3,$33c1,$33df,$33fc,$3419,$3436,$3453,$3470,$348d,$34aa,$34c6,$34e2,$34ff,$351b
		dc.w	$3537,$3553,$356e,$358a,$35a5,$35c1,$35dc,$35f7,$3612,$362d,$3648,$3662,$367d,$3697,$36b1,$36cb
		dc.w	$36e5,$36ff,$3718,$3732,$374b,$3765,$377e,$3797,$37b0,$37c8,$37e1,$37f9,$3812,$382a,$3842,$385a
		dc.w	$3871,$3889,$38a1,$38b8,$38cf,$38e6,$38fd,$3914,$392b,$3941,$3958,$396e,$3984,$399a,$39b0,$39c5
		dc.w	$39db,$39f0,$3a06,$3a1b,$3a30,$3a45,$3a59,$3a6e,$3a82,$3a97,$3aab,$3abf,$3ad3,$3ae6,$3afa,$3b0e
		dc.w	$3b21,$3b34,$3b47,$3b5a,$3b6d,$3b7f,$3b92,$3ba4,$3bb6,$3bc8,$3bda,$3bec,$3bfd,$3c0f,$3c20,$3c31
		dc.w	$3c42,$3c53,$3c64,$3c74,$3c85,$3c95,$3ca5,$3cb5,$3cc5,$3cd5,$3ce4,$3cf4,$3d03,$3d12,$3d21,$3d30
		dc.w	$3d3f,$3d4d,$3d5b,$3d6a,$3d78,$3d86,$3d93,$3da1,$3daf,$3dbc,$3dc9,$3dd6,$3de3,$3df0,$3dfc,$3e09
		dc.w	$3e15,$3e21,$3e2d,$3e39,$3e45,$3e50,$3e5c,$3e67,$3e72,$3e7d,$3e88,$3e92,$3e9d,$3ea7,$3eb1,$3ebb
		dc.w	$3ec5,$3ecf,$3ed8,$3ee2,$3eeb,$3ef4,$3efd,$3f06,$3f0f,$3f17,$3f20,$3f28,$3f30,$3f38,$3f40,$3f47
		dc.w	$3f4f,$3f56,$3f5d,$3f64,$3f6b,$3f72,$3f78,$3f7f,$3f85,$3f8b,$3f91,$3f97,$3f9c,$3fa2,$3fa7,$3fac
		dc.w	$3fb1,$3fb6,$3fbb,$3fbf,$3fc4,$3fc8,$3fcc,$3fd0,$3fd4,$3fd7,$3fdb,$3fde,$3fe1,$3fe4,$3fe7,$3fea
		dc.w	$3fec,$3fef,$3ff1,$3ff3,$3ff5,$3ff7,$3ff8,$3ffa,$3ffb,$3ffc,$3ffd,$3ffe,$3fff,$3fff,$4000,$4000
		ds.w	32*16*4

EDIT: this LUT is designed especially for small intros where storing only a single quadrant at high-precision can be convenient.
If you are not concerned about space or you have time to pre-calculate it with same precision, then you don't need it

[Antiriad_UK]

Originally Posted by ross

Is the following too slow?

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

Oh that's a neat use of addx. I'll squirrel that away.

I'm currently committing "math crimes" and using -32768 to 32767 and then:

add.l d0,d0
swap d0

I think the spinning cubes can handle it

[ross]

I was forgetting, code to generate the quad:

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

const long double SinTableSize=2048/4; // first quad only
const long double maxvalue=16384;
const long double M_PI2=3.141592653589793238462643383279502884L/2.0L;
const long double rounding=0.5L;

int main()
{
        for(long double i=0; i<SinTableSize;)
        {
            cout << "\t" << "dc.w\t";
            for (int n=0; n<16; n++,i++)
            {
                int value=sin(i*M_PI2/SinTableSize)*maxvalue+rounding;
                cout << "$" << setfill('0') << setw(4) << hex << value;    //§+maxvalue
                if (n<15) cout << ",";
            }
            cout << endl;
        }

    return 0;
}

I know, exaggerated precision