Transformations in the 2D Plane

As I'm sure you can tell, you're slipping into the world of mathematics—I've been sneaking up on you <BG>. Nevertheless, this stuff is fun, and if you understand the basics, there's really nothing in 3D game programming that you won't be able to tackle! So let's hit it!

You've seen translation a number of times up to this point, but you haven't really looked at a mathematical description of it, or for that matter any other transformations, like rotation and scaling. Let's take a look at each one of these concepts and how they relate to 2D vector images. Then, when you make the leap to 3D graphics, all you'll need to do is add a variable or two and take into consideration the z-axis—but we'll get to that.

Translation

Translation is nothing more than moving an object or point from one position to another. Let's assume that you have a single point, (x,y), that you want to translate by some amount, (dx,dy). The process of translation is shown in Figure 8.17.

Basically, you add the translation factors to the (x,y) coordinate, come up with a new position, and call it (xt,yt). Here's the math:

xt = x + dx;
yt = y + dy;

Here, dx,dy can be either positive or negative. If we're taking about translation with standard display coordinates, where (0,0) is in the upper-left corner, positive translations in the x-axis move an object to the right. Positive translations in the y-axis move an object down. Negative translations in the x-axis move an object to the left. And finally, negative translations in the y-axis move an object up.

To translate an entire object, you simply apply the translation transformation to the center of the object, if the object has an x,y position that all points are relative to (as does the polygon structure). If the object doesn't have a general x,y position, you must apply the formula to every point that makes up the polygon. This brings us to the concept of local and world coordinates.

Generally, in 2D/3D computer graphics you want to define all objects to have at least local and world coordinates. The local coordinates of an object are those relative to (0,0) or (0,0,0) in 3D. Then the world coordinates are found by adding the world position (x0,y0) to each of the local coordinates, in essence translating the local coordinates each by (x0,y0) to place the object. This is shown in Figure 8.18.

In light of this, in the future you may decide to add more data storage to your polygon so that you can store both local and world coordinates. In fact, you will do this later. Moreover, you'll add storage for camera coordinates. The reasoning for the added storage is that once you transform an object to world coordinates and are ready to draw it, you don't want to have to do it each frame. As long as the object doesn't move or transform, you won't have to. You can just save the last calculated world coordinates.

With that all in your little neural net, let's take a look at a general polygon translation function. It's so simple, it should be illegal <BG>.

int Translate_Polygon2D(POLYGON2D_PTR poly, int dx, int dy)
{
// this function translates the center of a polygon

// test for valid pointer
if (!poly)
   return(0);

// translate
poly->x0+=dx;
poly->y0+=dy;
// return success
return(1);

} // end Translate_Polygon2D

I think that deserves a Pentium.II.AGP double snap!!!

Rotation

Rotation of bitmaps is rather complex, but rotation of single points in the plane is almost trivial—or at least the actual rotation is. Deriving the rotation is a bit more complex, but I have a new derivation that I think is very cool. However, before I show it to you, let's take a look at what you want to do. Referring to Figure 8.19, you can see the point p0 with coordinates (x,y). You want to rotate this point an angle theta about the z-axis (which is running through the paper) to find the rotated coordinates p0¹ with coordinates (xr,yr).

Trigonometry Review

Obviously, you're going to need to use some trigonometry here. If you're rusty, here's a quick review of some basic facts.

Most trigonometry is based on the analysis of a right triangle, as shown in Figure 8.20.

Table 8.1 shows the differences between radians and degrees.

Table 8.1. Radians Versus Degrees

Degrees	Radians (pi)	Radians (Numerically)
360	2*pi	6.28
180	1*pi	3.14159
90	pi/2	1.57
57.295	pi/pi	1.0
1	pi/180	0.0175

Here are some trigonometric facts:

• There are 360 degrees in a complete circle, or 2*pi radians. Hence, there are pi radians in 180 degrees. The computer functions sin() and cos() work in radians, not degrees—remember that! Table 8.1 lists the values.

• The sum of the interior angles theta1 + theta2 + theta3 = 180 degrees or pi radians.

• Referring to the right triangle in Figure 8.20, the side opposite theta1 is called the opposite side, the side below it is called the adjacent side, and the long side is called the hypotenuse.

• The sum of the squares of the sides of a right triangle equal the square of the hypotenuse. This is called the Pythagorean theorem. Mathematically, you write it like this:

  hypotenuse2 = adjacent2 + opposite2
  

  Or sometimes you can use a, b, and c for dummy variables:

  c2 = a2 + b2
  

  Therefore, if you have two sides of a triangle, you can find the third.

• There are three main trigonometric ratios that mathematicians like to use, called the sine, cosine, and tangent. They're defined as

                   adjacent side      x
  cos(theta)  =  ---------------- = -------
                    hypotenuse        r
  

  Domain: 0 <= theta <= 2*pi

  Range: -1 to 1

                  opposite side       y
  sin(theta)    = ---------------- = -------
                   hypotenuse         r
  

  Domain: 0 <= theta <= 2*pi

  Range: -1 to 1

                  sin(theta)       opposite/hypotenuse
  tan(theta)    = --------------  = ----------------------
                  cos(theta)       adjacent/hypotenuse
  

                              opposite       y
                          = ------------ = --- = slope = M
                              adjacent       x
  

  Domain: -pi/2 <= theta <= pi/2

  Range: -infinity to +infinity

Figure 8.21 shows graphs of all the functions. Notice that all the functions are periodic (repeating) and that sin(theta) and cos(theta) have periodicity of 2*pi, while the tangent has periodicity of pi. Also, notice that tan(theta) goes to +-infinity whenever theta mod pi is pi/2.

Now, there are about a bazillion trigonometric identities and tricks, and it would take a math book to prove them all. I'm just going to give you a table of the ones that a game programmer should know. Table 8.2 lists some other trigonometric ratios, as well as some neat identities.

Table 8.2. Useful Trigonometric Identities

Cosecant	csc(theta) = 1/sin(theta)
Secant	sec(theta) = 1/cos(theta)
Cotangent	cot(theta) = 1/tan(theta)

Pythagorean theorem in terms of trig functions:

sin(theta)2 + cos(theta)2 = 1

Conversion identity:

sin(theta1) = cos(theta1 – PI/2)

Reflection identities:

sin(-theta) = -sin(theta)
cos(-theta) =  cos(theta)

Addition identities:

sin(theta1 + theta2) = sin(theta1)*cos(theta2) + cos(theta1)*sin(theta2)

cos(theta1 + theta2) = cos(theta1)*cos(theta2) - sin(theta1)*sin(theta2)

sin(theta1 - theta2) = sin(theta1)*cos(theta2) - cos(theta1)*sin(theta2)

cos(theta1 - theta2) = cos(theta1)*cos(theta2) + sin(theta1)*sin(theta2)

Of course, you could derive identities until you turned many shades of blue. In general, identities help you simplify complex trigonometric formulas so you don't have to do the math. Hence, when you come up with an algorithm based on sin, cos, tan, and so on, always take a look in a trigonometry book and see if you can simplify your math so that fewer computations are needed to get the result. Remember, speed, speed, speed!!!

Rotating a Point in a 2D Plane

Now that you have an idea of what sin, cos, and tan are, let's use them to rotate a point in a 2D plane. Take a look at Figure 8.22, which shows the setup for the rotation formulas.

Start off by showing that any point on a circle of radius R is computed as

xr = r*cos(theta)
yr = r*sin(theta)

Hence, if you always wanted to rotate a point that had coordinates (x,0), you could use this equation. However, you need to generalize a little. You want to rotate a point (x,y) about an angle theta, as shown in Figure 8.22. You can think of this in two ways: as rotating the point P, or as rotating the axes themselves. If you think of it as rotating the axes themselves, you have two coordinate systems: one before the rotation, and one after.

In the coordinate system before the rotation, you have

xr = r*cos(theta)
yr = r*sin(theta)

But after the rotation, you have

Equations 1:

xr = r*cos(theta + alpha)
yr = r*sin(theta + alpha)

Equations 2:

x = r*cos(alpha)
y = r*sin(alpha)

Here, alpha is basically the angle created from the x-axis of the new system and the position vector from the origin to P.

If you're confused, let me explain what you're doing here in another way. You always know how to find the point (x,0) rotated about theta, and if you rotate the axes by theta, you can compute P in both the old axes and the new. Then, based on these two formulas, you can come up with the rotation equations. If you take Equations 1 and use the addition identities, you'll get the following results.

Equations 3:

xr = r*cos(theta)*sin(alpha) – r*sin(theta)*sin(alpha)
yr = r*sin(theta)*cos(alpha) + r*sin(theta)*cos(alpha)

Wait a minute, let me put some boom in it. You know that x,y are also equal to

x = r*cos(alpha)
y = r*sin(alpha)

Substituting these values into the bolded parts of Equations 3 gives you the results you desire.

Equations 4, the rotation formulas:

xr = x*cos(theta) – y*sin(theta)
yr = x*sin(theta) + y*cos(theta)
Q.E.D.

Back to reality. You now know that to rotate a point (x,y) by an angle theta, you can use Equations 4. However, there is one detail to remember: The equations rotate a point in the counterclockwise direction for positive theta and in the clockwise direction for negative theta. However, there is one more problem… you did the derivation for quadrant I of the normal Cartesian coordinate system. Thus, the y-axis is inverted on the display screen and the roles of positive and negative are reversed.

Later, when you do 3D graphics, you'll transform all screen coordinates so that the x,y-axes are centered in the middle and are both pointing in the positive directions, just like quadrant I of the 2D Cartesian system. But for now, who cares?

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.

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

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 FLOATs. 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!

Scaling

After all that, anything should be easy. Scaling is almost as simple as translation. Take a look at Figure 8.24. All you need to do to scale an object is multiply each coordinate by the scaling factor.

Scaling factors that are greater than 1.0 will make the object bigger, while scaling factors less that 1.0 will make the object smaller. A scaling factor of 1.0 will do nothing. The math to scale a point (x,y) by scaling factor s, resulting in (xs,ys), is

xs = s*x
ys = s*y

Also, you can scale each axis non-uniformly—that is, with different scaling factors for the x and y coordinates, like this:

xs = sx*x
ys = sy*y

Most of the time, you want to scale equally. But you might want to make an object grow in one axis, so who knows? Here's a function that scales a polygon. It takes both an x- and a y-axis scaling factor, just in case:

int Scale_Polygon2D(POLYGON2D_PTR poly, float sx, float sy)
{
// this function scales the local coordinates of the polygon

// test for valid pointer
if (!poly)
   return(0);

// loop and scale each point
for (int curr_vert = 0; curr_vert < poly->num_verts; curr_vert++)
    {
    // scale and store result back
    poly->vlist[curr_vert].x *= sx;
    poly->vlist[curr_vert].y *= sy;

    } // end for curr_vert

// return success
return(1);

} // end Scale_Polygon2D

That one was easy, huh, hot rocks?

To scale a polygon to 1/10 its size, you would make the call

Scale_Polygon2D(&polygon, 0.1, 0.1);

Notice that the x- and y-axis scale factors are both equal to 0.1. Thus, the scaling will be uniform on each axis.

As a demo of scaling, I have created DEMO8_5.CPP|EXE. It creates a single rotating asteroid. When you press the A key, the object gets bigger by 10 percent; when you press the S key, it gets smaller by 10 percent.