🔒 Locked

fast sin/cos

Started by ari556655 Jun 5, 2009 at 5:41 PM 11 replies 11.3k views

Original Post

Jun 5, 2009 at 5:41 PM

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.

alagtriste

Jun 5, 2009 at 5:51 PM

Hope that helps:
Fast sin/cos

trojanman

Jun 5, 2009 at 6:21 PM

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.

LessBread

Jun 5, 2009 at 6:33 PM

Have you thought of using a look up table?

// These arrays will hold the Sin and Cos look-up tablesfloat Sin_LUT[361];float Cos_LUT[361];// Routine to build trig lookup tablesvoid _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.

Dave Eberly

Jun 5, 2009 at 6:38 PM

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

Lord Crc

Jun 6, 2009 at 1:47 AM

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.

AshleysBrain

Jun 7, 2009 at 12:38 PM

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++?

alvaro

Jun 7, 2009 at 1:36 PM

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.

_Sigma

Jun 7, 2009 at 1:45 PM

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.

zeux

Jun 7, 2009 at 2:06 PM

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.

phresnel

Jun 8, 2009 at 3:00 AM

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;}

alvaro

Jun 8, 2009 at 6:06 AM

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

phresnel

Jun 8, 2009 at 6:22 AM

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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.