Archived

This topic is now archived and is closed to further replies.

Trig functions and lookup tables

This topic is 6521 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

I have found a document on gamedev.net about lookup tables. I have decided to use one for calculating the angles of a circle (360 in my lookup table). The code goes like this: float LookUpCircleCos[360]; float LookUpCircleSin[360]; void InitLookUpCircle(void) { int Degrees; for(Drgrees = 0; Degrees < 360; Degrees++) { LookUpCircleSin = sin(rad(Degrees)); LookUpCircleCos = cos(rad(Degrees)); } } this is basically the original pascal code put into c. now, i have 2 problems. 1st: which header file has the "rad" function (couldn''t see it in math.h), and second of all, how the hell do i use it! I know how to use arrays, but i dont know how to apply the numbers to my data. example: 1 2 o o <-this o should be a further down, not possible in ascii // o c how do i get point1 to transform to point2 (c is the center of rotation)? any help appreciated MENTAL

Share on other sites
well, first, you need to access the correct index into the table in your table generation:

LookUpCircleSin[Degrees] = ...

but there is no "rad" function (that i know of). to convert from degrees to radians multiply degrees by (pi/180).

now to apply, just plug your angle into lookup table:

where c = {x,y} center point
and o = {x,y} object point
where LengthOfRotationArm is the distance from object point to center point

o.x = (LookUpCircleCos[deg] * LengthOfRotationArm) + c.x
o.y = (LookUpCircleSin[deg] * LengthOfRotationArm) + c.y

those should be the correct transformations.

crazy166
some people think i'm crazy, some people know it

Share on other sites
Probably a little something like this.

There is no degrees to radians converter function in C,
you have to make it yourself - most programmers use either a #define or an inline function, such as:

thats basically what''s in Quake 1, where M_PI is your own definition of PI. Then you just call it DEG2RAD(angle)
so the trg function becomes:

Right, now I see a couple of obvious mistakes in your code,
when you go
it should be,
that will put the correct angle in the correct element
of the array.
So, once you''ve created these lookup tables, instead of
calling sin(DEG2RAD(angle)); everytime you need an angle
computed, you just go LookUpCircleSin[angle];
a lot faster, I think.

Hope some of that rambling helped.

-Mezz

Share on other sites
also, just because there are 360 degrees in a circle, doesn''t mean you can''t use 1000 sin and cos values around the circle. using 720 values in table would give you half degree precision.
this can be noticeable as the object gets far from center point and movement between degrees gets choppy.

to calc these values just:
for ( x < 1000 )
lookupsin[x] = sin( (6.28 / 1000)*x )

then your circular movement is much smoother as you go from 1 to 1000.

crazy166
some people think i'm crazy, some people know it

Share on other sites
I think look up tables are not what you should be implementing here. The problem is you are trying to perform a 2d rotation, look up tables will not answer problems..

A look up table is, just as its name suggests, a table. It''s a table of pre-calculated values, in this case of cos(angle) and sin(angle).

The theory is, asking the cpu for sin() or cosine() is slow, but once you set up a look up table you can obtain the values from it instead.

ie sin(angle) now becomes LookUpCircleSin[angle]

You see?

Personally, I''m against using look up tables anymore for sin and cosine. The problem is, you will always have to round off your angles to some accuracy or another. In this case it''s whole degrees, what happens when you need sin(0.23423)?

Look up tables are good for more complex formulae, rather than sines. If I get a complex formula, consisting of several multiplies etc etc, I decide on an accuracy for the results, then use a look-up table.

BUT before I do that, I ALWAYS leave the full formula in the main loop while I test the rest of the program. Only when everything else around it is working, will I swap it for a look up table, then I''ll carefully test it to see what difference it has made (not to performance, but to accuracy!)

Do a search for some information on 2D rotations, and be prepared for some matrix math!

Leave look up tables for now!

Cheers

Matt

Check out my project at: www.btinternet.com/~Matthew.Bennett

Share on other sites
Look up tables for sin and cos are almost a must, since sin and cos take a long time for the computer to process, while look up tables go much faster

From what I can see, you are trying to rotate a point (x,y) around a center origin (cx,cy) by an certain angle.

Here''s the formula:

new_x = (cos_look_up[angle] - sin_look_up[angle]) + cx;
new_y = (cos_look_up[angle] + sin_look_up[angle]) + cy;

I hope this is right since its from memory

Share on other sites
Thank you all very much for the helpful information. I''ve got the lookup tables working perfectly now, and I now know what do do with them.

to 3DModelMan: the reason I''m using lookup tables is because the game is in full 3D, but I only need to rotate objects around 2 axis, so the lookup tables would leave more time for drawing.

to mezz: sorry about the mistake in the code. i did actually mean to put the [Degrees] in, i just forgot (this code was written on the spot, not a cut-and-paste job

thanks for the Rad function too. Maybe ANSI should have put on in their c library guidelines. Oh well.

MENTAL

Share on other sites
Oh dear. I''ve just noticed something. how do you apply the loopup tables to the angle? 2 people are saying 2 different things

is it this:

o.x = (LookUpCircleCos[deg] * LengthOfRotationArm) + c.x
o.y = (LookUpCircleSin[deg] * LengthOfRotationArm) + c.y

or this:

o.x = (cos_look_up[angle] - sin_look_up[angle]) + c.x;
o.y = (cos_look_up[angle] + sin_look_up[angle]) + c.y;

or do both work?

MENTAL

Share on other sites
Hi,

I learned that lookup tables for sine and cosine are done with. They take an enormous cache hit, that slows your program more down then using the standard sin and cosine methods.

Unless you are calling sine and cosine several times after eachother ofcourse. But that is most of the times not the case.

Jaap Suter

Share on other sites
quote:
Original post by MENTAL
is it this:

o.x = (LookUpCircleCos[deg] * LengthOfRotationArm) + c.x
o.y = (LookUpCircleSin[deg] * LengthOfRotationArm) + c.y

or this:

o.x = (cos_look_up[angle] - sin_look_up[angle]) + c.x;
o.y = (cos_look_up[angle] + sin_look_up[angle]) + c.y;
MENTAL

Well, it should be the first one.

x = cos( angle );
y = sin( angle );

This will give you the x,y position on a one unit circle, so, if you simply multiply by the radius, you are extending that point our from the midpoint of the circle, and it will extend in the correct direction.
so:

x = cos_lookup_table( angle ) * radius;
y = sin_lookup_table( angle ) * radius;

The larger the radius, the less precision you will have, though.

then, you will need to offset your x and y positions depending on where the midpoint of your circle is, so just change the previous example to:

x = ( cos_lookup_table( angle ) * radius ) + mid_x;
y = ( sin_lookup_table( angle ) * radius ) + mid_y;

You may need to reverse the y value to something like:

y = mid_y - ( sin_lookup_table( angle ) * radius );

But only if you are working in the fourth quadrant, like the coordinate system of the computer monitor. It all depends how you set it up, though, you could always make that transformation later. Sorry if I wasn''t clear with that last bit.
-Evan

By the way, you may want to pick up a trig book... they''re kind of fun.

Share on other sites
quote:
Original post by s9801758

I learned that lookup tables for sine and cosine are done with. They take an enormous cache hit, that slows your program more down then using the standard sin and cosine methods.

Jaap Suter

Whatever, man. It all depends how you do it. If you are simply using 360 floats, I don''t think that''ll translate into a enormous cache hit. If you are doing a million levels of precision, then yeah, you would probably run into problems. I''ve actually never really looked into how sin() cos() are implemented, but the only way that it would be faster than a small lookup table is if it was built into hardware, and even then I''m not sure how much faster it would be.

Share on other sites
Ahem, for sin and cos, if you have 360 different angles/entries, look-up tables are ALWAYS FASTER!!!!
I KNOW THIS!!
Just make a demo that plots cirlces using sin and cos, and then make the same demo with sin and cos look-up tables. Tables with make it zoom by much faster. Someone said that tables make the program take a performance hit, and I don''t what they were smoking, unless they meant a HUGE table.

Share on other sites
RE: performance

Here''s a little rule of tumb.

When in doubt, make a little demo to see the results.

Share on other sites
quote:

Ahem, for sin and cos, if you have 360 different angles/entries, look-up tables are ALWAYS FASTER!!!!

You know, there are very few true absolute statements in life....

Anyways, sin and cosine are implemented in the FPU (FSIN, FCOS instructions for you asm heads. See Sec 7.5.7 in the "Intel Architecture Software Developer''s Manual, Volume 1" if you don''t believe me.) A call to FSIN takes about 20 clock cycles. In comparison an L2 cache miss can take 40-50 cycles. (Exact numbers depend on which processor you have.) So for sufficiently infrequent calls of trig functions (or sufficiently bad memory layouts), there *is* a performance hit in using lookup tables, no matter what size they are.

Share on other sites
The gods have spoken - now let it be!

Thanks SiCrane.

Zipster - Next time you compile your ''demo'', try setting the processor to Pentium.....

Bye now

Matt

Check out my project at: www.btinternet.com/~Matthew.Bennett

Share on other sites
Now, let''s be fair, Matt, the demo he described is very sin/cos intensive. It will be faster to use table lookup, if all you are doing is drawing a circle. But, if your program requires only a single sin/cos every frame then it will probably be slower to use a table lookup, even if you only have 360 entries in the table.

Share on other sites
Hey, i read it in a book. Don''t blame me, blame Andre!!

Share on other sites
Argh! this wasn''t ment to be a flame war!

I only used 360 degrees as an example, and for a simple value for the variable i. I am infact using 1000 possible angles, and have found that lookup tables are much faster.

Thank you derek day for actually answering the question .

If I was just plotting circle it would be ok, but some of the meshes that need rotating consist of hundreds of verticies (one has well over 1000 - damn does it look good though), so the lookup tables are much quicker.

One more problem: I have found that some angles need to be rotated by the Z axis. would the by any chance:

x = ( cos_lookup_table( angle ) * radius ) + mid_x;
y = ( sin_lookup_table( angle ) * radius ) + mid_y;
z = ( tan_lookup_table( angle ) * radius ) + mid_z;

I''m only guessing because it''s the last trig function left

anyhelp appriciated.

MENTAL

PS: STOP FLAMING EACH OTHER!!!
P.P.S: I wouldn''t trust those intel books if i were you, unless it''s not actually written by someone at intel - they have a habit of lying (ok ok, i''m a hypocrite. now we can all stop flaming)

Share on other sites
I didn''t see anyone flaming anyone, so I donno about that one...

Anywayz, I always use look-up tables for trig functions, since I''m always using hundreds of calulations per frame whenever i use sin and cos, tan and sec, csc and cot, etc.

Share on other sites
Nothing I said was meant as a flame, but *I* was amazed at the difference it made when I was told to do that!!

OK it''s a very obvious step, but for me it wasn''t...

Anyway, I still hold with my original post. Use cos() and sin() first until you''re sure everything is working....

Cheers

Matt

Check out my project at: www.btinternet.com/~Matthew.Bennett