GP32 Trig Or Interpolation?

[Daz_Genetic]

A quick question. I have to call sin, cos and tan a few times per frame for various reasons.

I'm possibly going to put this into a lookup table, but I hate limiting the smooth animation to gain a few cycles. This could be fixed by interpolation... BUT..... Is it cheaper to just call sin,cos or tan, or would it be quicker to interpolate the values of a lookup table?

 

[mithris]

I have no idea how sin/cos is implemented, but i would think that a LUT would be better.
All the stuff i ever made used a LUT for sin/cos without interpolating at all..
And it has worked well enough for me..

---
mithris

 

[mr.spiv]

Software implementations of sin/cos/tan are rather kinky (but pretty fast anyway).. As mithris said LUT is more or less ideal for these functions. I just do stuff like: output = value * sintable[angle] and if needed to cut out the decimals just do: output >>= precision

 

[Daz_Genetic]

Yeah, but I have a variable FOV camera, so when it's zoomed in a lot, it will jump around, since 1 degree would be about 1/5th of the screen width.

I have no real way of benchmarking. Though I guess I could knock up a quick sample to see. I'm sure accessing a table, a few bitwise operations additions and a multiply should be way quicker than trig functions. But there is a chance that the processor is fast enough to outperform accessing memory. I have no idea to be honest.

I will report back with my results when I get a chance to test them.

 

[Daz_Genetic]

Just incase anyone is interested, here is the code I am now using. For simple cases, I can just look straight into the lookup table. But for cases where I need the extra precision, I can call a function which returns an interpolated value. The functions accept a fixed point angle(degrees) in 16:16 format. It must be somewhere between 0.0 and 359.99999.... (There are 361 members for interpolation reasons).

This angle is converted to an int which is used to index into the look up table. In order to interpolate, we also need the next value in the look up table. Our real value is somewhere between the first and second values obtained from the array.

In order to approximate the real value, we take the difference between the first and second value and multiply it by only the fraction part of the fixed point angle. To get the fraction part from the fixed point, we just AND it with 0xFFFF

The end result is very smooth rotations. I haven't tested it for speed, but It could be a bit faster than the math functions depending on how well they are implemented in software (something I have no idea about).

If anyone has any ideas for speeding this up, let us know. I'm sure that there's something I could have done better or faster.

#include <math.h>
#include "fixed.h"

#define FRACTION_MASK	0xFFFFL

fxd sin_table[361];
fxd cos_table[361];
fxd tan_table[361];

void init_tables(void){
	int i;
	for(i=0;i<361;i++){
  sin_table[i]=fxd_sin(deg_2_rad(int_2_fxd(i)));
  cos_table[i]=fxd_cos(deg_2_rad(int_2_fxd(i)));
  tan_table[i]=fxd_tan(deg_2_rad(int_2_fxd(i)));
	}
}

fxd sin_t(fxd angle){
	int i=fxd_2_int(angle);
	fxd v1=sin_table[i];
	return v1+fxd_mul(sin_table[i+1]-v1,angle&FRACTION_MASK);
}

fxd cos_t(fxd angle){
	int i=fxd_2_int(angle);
	fxd v1=cos_table[i];
	return v1+fxd_mul(cos_table[i+1]-v1,angle&FRACTION_MASK);
}

fxd tan_t(fxd angle){
	int i=fxd_2_int(angle);
	fxd v1=tan_table[i];
	return v1+fxd_mul(tan_table[i+1]-v1,angle&FRACTION_MASK);
}

 

[Robster]

If linear interpolation works for you, generally it's the best way of doing it.

If you need better precision, you could use gcc-3.4.0 (released Real Soon Now) which has hand-coded asm floating point math, but it'll still be much slower than what you've already done.

An intermediate solution is CORDIC, which is an iterative method of doing trig with fixed point - kind of like a binary search for the solution, so it's very simple and quick. Google for CORDIC trigonometry if you're interested.

From the code you've got, could you post the "fxd_sin" etc functions, fxd_2_int, int_2_fxd, and deg_2_rad? There's lots of optimisations you can do with 16:16 fixed point

 

[Daz_Genetic]

I don't use fxd_sin,cos,tan etc. in realtime, so it just calls the floating point version but converts the return to a fixed point version. Any help you can give me optimising the rest would help a lot.

//16.16 Fixed Point Macros
#define int_2_fxd(x) ((x)<<16)    	// Integer to fixed point
#define flt_2_fxd(x) ((fxd)((x)*65536.0+0.5))	// Float to fixed point
#define dbl_2_fxd(x) ((fxd)((x)*65536.0+0.5))	// Double to fixed point
#define fxd_2_int(x) ((x)>>16)    	// Fixed point to integer
#define fxd_2_flt(x) ((float)(x)/65536.0)  // Fixed point to float
#define fxd_2_dbl(x) ((double)(x)/65536.0)  // Fixed point to double

#define fxd_mul(x,y) (((x)*(y))>>16)  	// Multiply a fixed by a fixed
#define fxd_div(x,y) (((x)<<16)/(y))  	// Divide a fixed by a fixed

#define deg_2_rad(x) (fxd_mul((x), dbl_2_fxd(0.0174532925)))
#define rad_2_deg(x) (fxd_mul((x), dbl_2_fxd(57.2957795)))

 

[synkro]

this is 1/2 OT bit I hope you don't mind:

how does fixed work on the gp32?
where are the dis/advantages?
since there is no FPU, how much faster are fixed?

 

[mithris]

Fixed point works on GP32 in prety much the same way as on any other system.
if you are using 16:16 fixed point, you have a 16bit integer part and a 16 bit fractional part.
If you look at it with decimal numbers it would be something like this, you want to multiply 1.1 with 3.2
but you don't have a FPU, multiply both by 10 and you get 11*32, which equals 352, divide that by 10 and you get 35.2, and divide it by 10 again to get 3.52..
but ofcourse you don't use a decimal fixed point but a binary instead so you only use shifts.

The disadvantages is that the precision is a problem, specially if you use division etc, you really got to know what you are doing and make sure you don't loose too many bits in precision.

The speed, well, the speed depends very much on the precision you want, using divtables instead of a real division probably speeds things up a bit, but once again, precision is something you must consider.
additions, subtractions etc is done with the usual integer instructions so they are fast indeed.

---
mithris

 

[synkro]

ah ok, thank you so far.
so this is somekind of datatype I have to implement on my own? (doing a vector type was a hell of work)
when I use 16:16 fixed I have a precison rof 2^-16, right?
since the speed advantage is only with divtables, I think will use float LUT again, cause precision is no real matter in my current project.

 

[mithris]

You don't have to implement any datatype, a integer holds a 16:16 fixed point number.
And you can use all integer operations on it, but, the muls and divs are special cases.
0x10000 is 1.0 with 16:16, and if you multiply that with 0x20000 you would end up with a way too large number causing overflows and stuff. However the ARM cpu has a "smull" instruction letting you multiply 2 32bit integers to get a 64bit product, using that instructions and a couple of shifts solves the problem.

And with the divides the problem is this, 0x10000 / 0x10000 would give you 0x1, and you have lost 16bits of precision, which sucks.
So, what one does is to store 1/x in a divtable and use multiplication, it's important to keep track of the range which the divider will be in so you don't need a giant divtable.

And the prceision is correct, but you have to remember that it is very easy to loose some precision, expecially when you are shifting your numbers around to fit divtables etc.

 

[yaouank]

A quick question. I have to call sin, cos and tan a few times per frame for various reasons.

I'm possibly going to put this into a lookup table, but I hate limiting the smooth animation to gain a few cycles. This could be fixed by interpolation... BUT..... Is it cheaper to just call sin,cos or tan, or would it be quicker to interpolate the values of a lookup table?

If you do it "a few times per frame" (say around 10 times per frame), you should use the implemented sin and cos.
You will have the precision you are looking at and I guess computing 250 cos per second (10 cos per frame and 25 frame per second) should not be too difficult for a 133MHz CPU.