Tricks of the Windows Game Programming Gurus:Vector Rasterization and 2D Transformations

All ITKnowledge Source Code Search Tips Advanced Search |

| Tricks of the Windows Game Programming Gurus by Andre LaMothe Sams, Macmillan Computer Publishing ISBN: 0672313618 Pub Date: 09/27/99

Search this book:

Previous | Table of Contents | Next

Rotating a Polygon

Taking all of your immense knowledge, let’s write a rotation function that rotates a polygon:

    int Rotate_Polygon2D(POLYGON2D_PTR poly, float theta)

    {

    // this function rotates the local coordinates of the polygon

    // test for valid pointer

    if (!poly)

       return(0);

    // loop and rotate each point, very crude, no lookup!!!

    for (int curr_vert = 0; curr_vert < poly->num_verts; curr_vert++)

        {

        // perform rotation

        float xr =  poly->vlist[curr_vert].x *cos(theta) –

                    poly->vlist[curr_vert].y*sin(theta);

        float yr = poly->vlist[curr_vert].x*sin(theta) +

                   poly->vlist[curr_vert].y*cos(theta);

        // store result back

        poly->vlist[curr_vert].x = xr;

        poly->vlist[curr_vert].y = yr;

        } // end for curr_vert

    // return success

    return(1);

    } // end Rotate_Polygon2D

There are a few things you should note. First, the math is performed in floating-point and then the results are stored as integers, so there’s loss of precision.

Next, the function takes the angle in radians rather than degrees because the function uses the math libraries’ `sin()` and `cos()` functions, which use radians. The loss of accuracy isn’t a huge problem, but the use of trig functions in a real-time program is just about as ugly as it gets. What you need to do is create a lookup table that has the sine and cosine values for, say, 0–360 degrees already precomputed, and then replace the library function calls to `sin()` and `cos()` with table lookups.

The question is, how do you design the table? This really depends on the situation. Some programmers might want to use a single `BYTE` to index into the table. Thus, it would have 256 virtual degrees that made up a circle, as shown in Figure 8.23.

Figure 8.23 Breaking a circle into 256 virtual degrees.

It’s up to you and the situation, but usually I like to make the table hold the angles from 0–359 degrees. Here’s how you might create such tables:

    // storage for our tables

    float cos_look[360];

    float sin_look[360];

    // generate the tables

    for (int ang = 0; ang < 360; ang++)

        {

        // convert ang to radians

        float theta = (float)ang*3.14159/180;

        // insert next entry into table

        cos_look[ang] = cos(theta);

        sin_look[ang] = sin(theta);

        } // end for ang

Then we can rewrite our rotation function to take an angle from 0–359 and use the tables by replacing the `sin()` and `cos()` with `sin_look[]` and `cos_look[]`, respectively:

    int Rotate_Polygon2D(POLYGON2D_PTR poly, int theta)

    {

    // this function rotates the local coordinates of the polygon

    // test for valid pointer

    if (!poly)

       return(0);

    // loop and rotate each point, very crude, no lookup!!!

    for (int curr_vert = 0; curr_vert < poly->num_verts; curr_vert++)

        {

        // perform rotation

        float xr = poly->vlist[curr_vert].x*cos_look[theta] –

                   poly->vlist[curr_vert].y*sin_look[theta];

        float yr = poly->vlist[curr_vert].x*sin_look[theta] +

                   poly->vlist[curr_vert].y*cos_look[theta];

        // store result back

        poly->vlist[curr_vert].x = xr;

        poly->vlist[curr_vert].y = yr;

        } // end for curr_vert

    // return success

    return(1);

    } // end Rotate_Polygon2D

> Note: Note that all this rotation stuff mangles the original polygon’s coordinates. Sure, if you rotate 10 degrees, you can then rotate –10 degrees to get back to the original vertices, but you will slowly lose your original vertex coordinates due to integer truncation and rounding. This is the reason for having a second set of coordinates stored in the polygon structure. It can hold transformations, and you always keep the originals too, so you can refresh your data if need be. More on this later.

To rotate a `POLYGON2D` object 10 degrees, you would make the call

    Rotate_Polygon2D(&object, 10);

A Word on Accuracy

I originally wrote this demo with integers to hold the local vertices. But to my dismay, the values degraded into fuzz within just a few rotations. Thus, I had to rewrite the demo to use `FLOAT`s. You must redefine your `POLYGON2D` structure to contain a floating-point-accurate vertex rather than an integer-accurate vertex.

There are two ways around this. One is to have a local and transformed (world) set of coordinates that are both integers, convert the local coordinates to floats, perform the transformation, store the result in the transformed coordinates, and then render. Then, on the next frame, use the local coordinates again. That way, no error creeps into the local coordinates.

Or you can just keep one set of local/transformed coordinates in floating-point. This is what I did. Hence, you have two new data structures for a vertex and for a polygon:

    // a 2D vertex

    typedef struct VERTEX2DF_TYP

            {

            float x,y; // the vertex

            } VERTEX2DF, *VERTEX2DF_PTR;

    // a 2D polygon

    typedef struct POLYGON2D_TYP

            {

            int state;        // state of polygon

            int num_verts;    // number of vertices

            int x0,y0;        // position of center of polygon

            int xv,yv;        // initial velocity

            DWORD color;      // could be index or PALETTENTRY

            VERTEX2DF *vlist; // pointer to vertex list

            } POLYGON2D, *POLYGON2D_PTR;

I just replaced the vertex list with the new floating-point vertex so I wouldn’t have to rewrite everything. Now, both the translation and rotation work, although translation is still integer-based. Of course, I could have done this before writing about it, but I want you to see the process in action, the give and take of game programming. You hope that things will work out, but if they don’t, you take a step back and try again <BG>.

For an example of using both the translation and rotation functions, I have taken `DEMO8_3.CPP` and modified it into `DEMO8_4.CPP|EXE`. It rotates all the asteroids at various rates. The program also uses the lookup tables. Take a look!

Previous | Table of Contents | Next

Copyright © Macmillan Computer Publishing, Inc.

Products | Contact Us | About Us | Privacy | Ad Info | Home
Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.