Thread: Sin Tables (and rotations)

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    361

    Sin Tables (and rotations)

    Hullo again all,

    Camera rotations are something that've been bothering me for a long time, and I've read suggestions about looking up in sin tables in the past, but only recently really started thinking about it. (I haven't really done any research into these, I just read the words "eventually you'll just look it up in a sin table", and this is how I interpretted it).

    For those that are just reading this for fun, and don't understand the problem, it's that calling sin and other trig functions in C/C++ gets pretty slow if you do it all the time (very bad when trying to render lots of objects on the fly).

    So, for my solution...

    Since the problem lies in calling sin on the fly, being slow, I figure creating the table once at the beginning of my program is the way to go.

    I'm thinking of making a class, oh, I dunno, cSinTable.

    In it will be an array with 62832 float elements (0 to 62831).
    Code:
    #define TABLE_ELEMENTS 62832 //Note: 6.28318 is roughly two Pi
    float sine[TABLE_ELEMENTS];
    Generation will look something like this:
    Code:
    for(int X = 0; X < TABLE_ELEMENTS; X++)
    {
    	sine[X] = sinf((float)X / 1000.0f);
    }
    Then, with the added complexity of having to multiply your float numbers by 1000, this table will have instant access time (hooray for array implementation) to all numbers from 0 to 2 Pi (keeping in mind 2 Pi is the same as 0, so that 62833th element isn't necessary) in 0.0001 increments.

    I.e. if you want to find the sin of 0.5
    EDIT: I mentioned this would be a class...
    Code:
    Function would look like this...
    float cSinTable::MySin(float X)
    {
    	return sine[(int)(X * 1000)];
    }
    //Use this to call the function...
    SinTable.MySin(0.5)
    Issues that could arise:
    - Too much typecasting (values changed/too much data loss?)
    - Writing code to avoid overflows (if the user wants the sin of 3 pi, there must be a way to reduce it until it is within less than 2 Pi and greater than 0). A while loop that keeps subtracting 2 Pi until this condition is met could get the job done though. Since the point of this is rotations though, the angle should never really be anywhere close to that high.

    Anyways, that's my idea, I was wondering what you all thought about it (is that the usual way to do it?). Any other problems that might arise that you can spot? Anything obvious I missed?

    Just to note, that code was very quickly put together for this post, but hopefully I didn't make any ridiculous errors there.

    Thanks for any input
    Last edited by Epo; 05-26-2005 at 03:24 PM. Reason: It's sunny outside
    Pentium 4 - 2.0GHz, 512MB RAM
    NVIDIA GeForce4 MX 440
    WinXP
    Visual Studio .Net 2003
    DX9 October 2004 Update (R.I.P. VC++ 6.0 Compatability)

  2. #2
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Lookups are slower than computing the actual sine and with lookup tables you have a very good chance at thrashing the cache.

    They had their place at one point in computer history but that time has since past.

    Check out the Intel docs concerning the sine function and the floating point SSE2 and/or SSE1 instructions - you will see that it has come a long way since the old days.

    Floating point now is nearly as fast, and in some cases, faster than integral mathematics. They truly have done some amazing things with the FPU in recent years.

    Besides I cannot think of many game programming problems where you would actually have to compute the sine.

  3. #3
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    What if he isn't developing on the PC? Maybe he's working on a handheld device that only has emulated floating point support? You would get drastic penalties in that case.

    Anyway, if you are developing on PC (And you probably are) then why don't you just wait until you get something up and going before worrying too much over optimization. Wait until you pin-point sin / cos calculations as being your bottle neck with a profiler or similar tool. I don't think will be the major bottle neck of your application by a long shot.
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

  4. #4
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    I don't even want to think about developing for something other than a PC

    So, tables are dead eh? Well, that solves that. It's too bad, I was feelin' so good about coming up with that Ah well

    I'm trying to get camera movement down right now in this little project, and walking/strafing are working fine, it's just that I'm having troubles with the rotations. I've been trying to get around this for a long time now, and a while back
    (this thread: http://cboard.cprogramming.com/showthread.php?t=64232)
    I was using sinf and cosf to just calculate trig distances and change the LookAt vector of my camera.

    Bubba gave me some code to look at there, and it helped some, but I just don't have the background yet to completely understand calls like D3DXVec3TransformCoord and a few others yet (MSDN wasn't too great about it). So I've been trying to find another way and improve my understanding since then, but as you can see, I'm still stuck here

    (2 hours later)

    Since writing that up there, I've been going over my code, and I think I'm going to scrap my current camera class. I'm gonna figure it out first, and THEN I'm gonna code it. I'll look over that code from so long ago again Bubba, and hopefully I'll get a bit further this time.

    But back on this topic, goodbye sin tables Thanks guys
    Pentium 4 - 2.0GHz, 512MB RAM
    NVIDIA GeForce4 MX 440
    WinXP
    Visual Studio .Net 2003
    DX9 October 2004 Update (R.I.P. VC++ 6.0 Compatability)

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I would venture to guess that with modern technology where it is and based on how far the PC has come, few, if any, modern gaming and/or handheld devices would not have native floating point support. I think even cell phones probably have a floating point unit somewhere in the circuitry.

    The PC didn't have an FPU in the early years because it either was not invented yet, not practical or perhaps not thought to be a necessity, or not financially possible.

  6. #6
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    The only handheld with floating point capability is the PSP. Cell phones do not have FPU's.

  7. #7
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    I never realized that FPUs were such a hassle to add in. Well I guess, seeing how int and floats are stored in memory, it's a lot less complex to just stick with integers. That's pretty interesting...

    And...on rotations...is it REALLY this easy??? (I drummed this up this morning in about 5 minutes now that I can use sinf and cosf)
    Code:
    //Only rotates Y-axis right now
    void cCamera::LookAround(float RotX, float RotY, float RotZ)
    {
    	rotY += RotY;
    
    	LookAt = D3DXVECTOR3(Position.x + sinf(rotY), LookAt.y, Position.z + cosf(rotY));
    
    	bUpdateCamera = true;
    }
    
    void cCamera::Update(IDirect3DDevice9* D3DDevice)
    {
    	D3DXMatrixLookAtLH(&matView, &Position, &LookAt, &Up);
    	D3DDevice->SetTransform(D3DTS_VIEW, &matView);
    
    	bUpdateCamera = false;
    }
    Where rotY is a float holding the rotation value, RotY indicates the change in Y's rotation each frame, and Update() only fires when bUpdateCamera has been set to true...

    I sure hope there's more to this...cause 3 months of grief should not be solved this easily...(even though it's working pretty good right now...)

    The only problem is that, while rotating, it looks somewhat...muddled...not really skipping, but just...something is off. Vague, I know. Kind of a quality loss? I don't know how to explain it

    But yeah, there it is...

    On a random note, I just got mesh loading to work by keeping a linked list of meshes, then an additional linked list of coordinates for the meshes. I.e. 100 ships now do not require loading 100 of the same mesh (just one mesh and 100 position coordinates). Speed's up huge since that (especially loading times). I know it has nothing to do with this, but the guy I'm working on this project with isn't around, and I just had to share it with someone
    Pentium 4 - 2.0GHz, 512MB RAM
    NVIDIA GeForce4 MX 440
    WinXP
    Visual Studio .Net 2003
    DX9 October 2004 Update (R.I.P. VC++ 6.0 Compatability)

  8. #8
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by Bubba
    few, if any, modern gaming and/or handheld devices would not have native floating point support. I think even cell phones probably have a floating point unit somewhere in the circuitry.
    There are many platforms without floating-point support. For example, that's why people have written the integer-only ogg vorbis codec: http://www.xiph.org/ogg/vorbis/
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  9. #9
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    More of a math question...

    Individually,
    Code:
    LookAt = D3DXVECTOR3(Position.x + sinf(rotY), LookAt.y, Position.z + cosf(rotY));
    Handles horizontal turning (looking left/right)

    And
    Code:
    LookAt = D3DXVECTOR3(LookAt.x, Position.y - sinf(rotX), Position.z + cosf(rotX));
    Handles vertical turning (looking up/down)

    But! When put together
    Code:
    LookAt = D3DXVECTOR3(Position.x + sinf(rotY), Position.y - sinf(rotX), Position.z + cosf(rotX) + cosf(rotY));
    This does not handle both. Does anybody know the proper calculation for the z coordinate? I've been messing around with it and I just can't find the right one that won't bomb out on me. I've tried sin cos and even tan in almost every combination imagineable (I've also tried drawing it out on paper to find the right relation), but I just can't figure this out.

    Any thoughts?
    Pentium 4 - 2.0GHz, 512MB RAM
    NVIDIA GeForce4 MX 440
    WinXP
    Visual Studio .Net 2003
    DX9 October 2004 Update (R.I.P. VC++ 6.0 Compatability)

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    You are not using the class correctly.

    Pitch - Rotation about the x axis - in an airplane, the up and down motion of the aircraft in respect to the horizon. Alters the thrust vector of the aircraft or the forward motion of the aircraft and displaces the lift (up) vector.

    Yaw - Rotation about the Y axis - in an airplane, the side to side or what is known as yaw motion in an aircraft - created when the rudder is deflected from neutral position.

    Roll - Rotation about the Z axis - in an airplane, - bank angle of the wings with respect to 0 degree upright flight - when the lift vector of the aircraft is exact opposite that of gravity or is facing straight up at 90 degrees and is perpendicularl to the earth's surface at all times (theoretically)

    The camera class has everything you need to alter these. You should NOT be touching the 3 basis vectors.

    Right 1.0f,0.0f,0.0f
    Up -> 0.0f,1.0f,0.0f
    Look -> 0.0f,0.0f,1.0f

    Walking can be accomplished via the Camera::walk() function or by translating along the positive look vector for forward, or negative look vector for backwards. Sliding can be accomplished by writing a function that will translate the camera along the right vector or the negative right vector. Flying/Jumping/Ducking can be accomplished by translating along the up vector or the negative up vector.

    These three basis vectors are always orthogonal and they are always pointing in the right direction. So if you pitch up 35 degrees and roll 35 degrees - the look vector is pointing up 35 degrees so when you move forward, you are still moving exactly where the camera is pointing. So no matter camera orientation, up is always up, right is always right, and look is always look.


    Note that if you specify Camera::LandObject - you can only walk in one plane - you cannot traverse planes unless you have a plane to walk on, just like on earth.

    With Camera::AirObject you can rotate around any axis and number of degrees and the object will NOT undergo gimbal lock. This is handled by using axis rotations or rotations about an arbitrary axis.

    If you wish to make the camera swing around an object simply translate out away from the object a set distance and then transform using the camera view matrix.

    Note that you can use these transformations for all objects in a game. It makes it a lot easier when you when object A to rotate this way or that and then move forward. This is a simple Yaw() followed by a Walk().

    This code will accomplish mouse look for you.
    Code:
    void GetMouseInput(void)
    {
      //Mouse input
      LONG lx, ly, cx, cy;
    
      //Get info from mouse
      Mouse->Update();
    
      //Get last mouse position
      Mouse->GetMousePosition(&lx,&ly,LAST);
    
      //Get current mouse position
      Mouse->GetMousePosition(&cx,&cy,CURRENT);
    
      //Debug section only
      #ifdef DEBUG_MODE
        char txt[80];
        sprintf(txt,"X:%u Y:%u LX:%u LY:%u",lx,ly,cx,cy);
        DebugFont->DrawText(900,10,0xFFFFFFFF,txt);
      #endif
    
      //Find difference between last and current position
      int diffx=cx-lx;
      int diffy=cy-ly;
    
      //Adjust for sensitivity - could also use frametime
      float movex=((float)diffx*.005f);
      float movey=((float)diffy*.005f);
    
      //Rotate around Y axis - turn left/right
      TheCamera.yaw(movex);
    
      //Rotate around X axis - look up/down
      TheCamera.pitch(movey);
    }
    You will need this version of the mouse class for the code to work. I changed some things to allow easier retrieval of the current and the last position of the mouse. It will save the last position of the mouse prior to the mouse being moved to a new location. When the mouse is moved again, it will save, and move. Essentially the former current position is now the last.

    The coefficent I multiply for mouse movement will directly affect the sensitivity of the mouse. You should probably allow the player to alter this value within a pre-set range so they can adjust it to their liking.
    Last edited by VirtualAce; 05-27-2005 at 12:13 PM.

  11. #11
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    I haven't actually been using that class because there were a few things in there that I just didn't understand what they were doing/why they were there, so I tried writing my own. I'll attach it for the sake of knowledge. Though LookAround() isn't very functional, the rest is, and if anybody wants to take a look at it, there it is.

    I tried using this class in the past though, but I ran into some snags. I'll give it another shot now, since my class doesn't work, and yours does. That adds a bit of credit But I'm going to try and understand this before I do...

    So no matter camera orientation, up is always up, right is always right, and look is always look.
    Relative to where you're looking? It seems to me that what you're saying is that if I look straight up, then my Look vector will be (0, 1, 0), and my Up vector will be somewhere along the horizontal axis, perpendicular to my Right vector? Though you did say that you never touch the 3 basis vectors, so maybe I'm understanding this wrong.

    But if not, wouldn't that mean an attempt to jump, with the Up vector along the horizontal axis, would result in some pretty crazy outcomes? On that note, anytime you're not looking perfectly horizontal?

    Just a note: And I know it won't, cause obviously this is working for you. But I'm still trying to understand how this is going to work first...

    Thanks alot for, not just now, but all the times you've put the time into explaining these things to me

    EDIT:
    Is a starting position of (0, 0, 0) for the camera always assumed? If Look is (0, 0, 1)...
    Pentium 4 - 2.0GHz, 512MB RAM
    NVIDIA GeForce4 MX 440
    WinXP
    Visual Studio .Net 2003
    DX9 October 2004 Update (R.I.P. VC++ 6.0 Compatability)

  12. #12
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    Scratch those questions. It's all clicking at once now.

    But, I was wondering what D3DXVec3TransformCoord() does. MSDN isn't too kind with an explanation (least not one I can understand).

    Also, do D3DXMatrixRotationAxis() and the other D3DX___ functions used use up a lot of resources? Or are they relatively quick calls? For comparison, my understanding is that:

    D3DXMatrixLookAtLH(&matView, &Position, &Look, &Up);
    D3DDevice->SetTransform(D3DTS_VIEW, &matView);

    Are pretty rough when it comes to speed...
    Pentium 4 - 2.0GHz, 512MB RAM
    NVIDIA GeForce4 MX 440
    WinXP
    Visual Studio .Net 2003
    DX9 October 2004 Update (R.I.P. VC++ 6.0 Compatability)

  13. #13
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    You must create the matrix and you must do the transform. No way around it.

  14. #14

    Join Date
    May 2005
    Posts
    1,042
    Are pretty rough when it comes to speed...
    Well, relatively speaking all of that vector/matrix processing is 'expensive', but...it's also pretty necessary! I would also expect the DX and similar libs to typically have fast implementations

  15. #15
    Registered User
    Join Date
    Jun 2003
    Posts
    361
    Cool cool, good to know

    And I just wanna say thanks again to all the help I've gotten here, namely that class Bubba, but everyone else too. I've finally gotten the camera movement down, which makes me ridiculously happy, and I've rendered a 3D grid of starships that I've just been flying through for hours on end. It's not really that much fun after two minutes, but it works! So that's exciting enough for me
    Pentium 4 - 2.0GHz, 512MB RAM
    NVIDIA GeForce4 MX 440
    WinXP
    Visual Studio .Net 2003
    DX9 October 2004 Update (R.I.P. VC++ 6.0 Compatability)

Popular pages Recent additions subscribe to a feed