Sign in to follow this  
ari556655

fast sin/cos

Recommended Posts

I use a 2d raytracing-like algorithm to determine if and how objects are to be lit and at the start of every ray I call the below function:
[Source]
Point castray(Point src, float angle, float length)
{
	Point ray = src;

	ray.x += (cos(angle) * length);
	ray.y -= (sin(angle) * length);

      return ray;
}
[/Source]
Might anyone have source code for creating a fast, simple, and inaccurate sin/cos table. I'm horrible at math(And I don't just mean bad, I mean horrendous), and have been unable to implement any of the examples I've come across so far on this site. Also I use radians and not degrees. I know a lot of people will say it's not worth it but if I can even squeeze 2-5 fps out of it I'll be happy. Also if anyone knows a quick and less accurate version of atan2 I'd love to have it as well. Thanks.

Share this post


Link to post
Share on other sites
The fastest inaccurate sin/cos calculation is going to be a lookup table. You can create a static array that you populate once (on application load for example) and then use that for all of your math calculations.

Share this post


Link to post
Share on other sites
Have you thought of using a look up table?



// These arrays will hold the Sin and Cos look-up tables
float Sin_LUT[361];
float Cos_LUT[361];

// Routine to build trig lookup tables
void _stdcall Build_SinCos_Tables(void)
{
int angle;
float rad;
for (angle=0; angle<361; angle++) {
rad = angle * 0.017453; // Degrees to Radians
Sin_LUT[angle] = sin(rad); // Build Sin table
Cos_LUT[angle] = cos(rad); // Build Cos table
}
}

int degrees = convert(angle);
ray.x += (Cos_LUT[degrees] * length);
ray.y -= (Sin_LUT[degrees] * length);




Build the look up tables during set up, then use them as needed. A lookup is always faster than a lengthy series of calculations.

If 360 degrees are too coarse, expand the size of each look up table to 360 * 10 and adjust the radian conversion factor in the look up table build function to compensate for tenths of a degree. This means cutting the circle into 3600 slices, with 3600 elements in both look up tables. The fractional degree value has to be multiplied by 10 and converted to integer to work as an index in the array.




Share this post


Link to post
Share on other sites
Look-up tables seem reasonable, but keep in mind that they will be global data. Profile the program and see whether cache misses are costly (much like lookups into virtual function tables are costly).

An alternative is to use low-degree polynomial approximations with hard-coded coefficients. See my mathematics page, files Wm4Math.{h,cpp}.

Share this post


Link to post
Share on other sites
Quote:
Original post by ari556655
I use a 2d raytracing-like algorithm to determine if and how objects are to be lit and at the start of every ray I call the below function: [...] Also if anyone knows a quick and less accurate version of atan2 I'd love to have it as well.


You aren't by any chance calculating the angles for the castray routine by using atan2? If so, you can most likely skip the whole angle concept which will most likely be much, MUCH faster.

Share this post


Link to post
Share on other sites
There's an x87 instruction, fsincos, that computes sin and cos of an angle at the same time. It's probably twice as fast as separate calls to sin and cos, and has the same accuracy. Are you using C++?

Share this post


Link to post
Share on other sites
I agree that he probably doesn't need to use angles at all. Few problems need them. If he explains a little bit better what he is trying to do and what the loop looks like, we can probably suggest alternative ways to formulate the Math without angles.

Share this post


Link to post
Share on other sites
AMD has the Core Math Library which has a fast sin/cos. Since you are computing both sin and cos, it is faster to compute both together. Take a look here. There is a fastsincos which will do both.

Share this post


Link to post
Share on other sites
It's probable that you don't need sin/cos at all; for example, if you're casting rays in regular angular intervals, and the outer loop is something like for (...; angle += angle_step) { Point p = castray(src, angle, length); ... }, then you can use simple trigonometric equations:

sin(a+b) = sin(a)cos(b)+cos(a)sin(b)
cos(a+b) = cos(a)cos(b)-sin(a)sin(b)

with these you can compute sin/cos of the starting angle and of the angle step, and then reevaluate sin/cos for the current angle with a couple of multiplications/additions.

Share this post


Link to post
Share on other sites
Quote:
Original post by zeux
It's probable that you don't need sin/cos at all; for example, if you're casting rays in regular angular intervals, and the outer loop is something like for (...; angle += angle_step) { Point p = castray(src, angle, length); ... }, then you can use simple trigonometric equations:

sin(a+b) = sin(a)cos(b)+cos(a)sin(b)
cos(a+b) = cos(a)cos(b)-sin(a)sin(b)

with these you can compute sin/cos of the starting angle and of the angle step, and then reevaluate sin/cos for the current angle with a couple of multiplications/additions.


Please allow me to simplify that:


const float step_x = cosf(angle);
const float step_z = -sinf(angle);
...
for (float len=epsilon; len<MAX_LEN; len+=STEP_SIZE) {
ray.x += step_x;
ray.z += step_z;
}


That way, you not only save the sin/cos in that inner loop, but in fact you are even saving some muls for free.

A more canonical alternative would be even simpler:


ray.direction = (...).normalize();
...
const Vector step = ray.direction * STEP_SIZE;
for (float len=epsilon; len<MAX_LEN; len+=STEP_SIZE) {
ray.x += step.x;
ray.z += step.z;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by phresnel
Quote:
Original post by zeux
It's probable that you don't need sin/cos at all; for example, if you're casting rays in regular angular intervals, and the outer loop is something like for (...; angle += angle_step) { Point p = castray(src, angle, length); ... }, then you can use simple trigonometric equations:

sin(a+b) = sin(a)cos(b)+cos(a)sin(b)
cos(a+b) = cos(a)cos(b)-sin(a)sin(b)

with these you can compute sin/cos of the starting angle and of the angle step, and then reevaluate sin/cos for the current angle with a couple of multiplications/additions.


Please allow me to simplify that:


const float step_x = cosf(angle);
const float step_z = -sinf(angle);
...
for (float len=epsilon; len<MAX_LEN; len+=STEP_SIZE) {
ray.x += step_x;
ray.z += step_z;
}


That way, you not only save the sin/cos in that inner loop, but in fact you are even saving some muls for free.


Except now you are computing something completely different. :)

The code you quoted was doing repeated rotations, and yours is doing repeated translations. Of course, repeated translations might be what the OP needed. We should probably stop guessing until the he posts the loop that calls `castray'.

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
The code you quoted was doing repeated rotations, and yours is doing repeated translations.


Argh. Undercaffeination. Sorry.

Quote:
Of course, repeated translations might be what the OP needed. We should probably stop guessing until the he posts the loop that calls `castray'.

Yes :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this