Free JavaScript Editor Ajax Editor

↑

Main Page

## Transformations in the 2D PlaneAs 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. ## TranslationTranslation 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. ## Figure 8.17. Translating a single point.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. ## Figure 8.18. Translation of an object and the resulting vertices.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!!! ## RotationRotation 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 ## Figure 8.19. The rotation of a point.## Trigonometry ReviewObviously, 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. ## Figure 8.20. The right triangle.Table 8.1 shows the differences between radians and degrees.
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: hypotenuse ^{2}= adjacent^{2}+ opposite^{2}Or sometimes you can use a, b, and c for dummy variables: c ^{2}= a^{2}+ b^{2}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
MATH Note the use of the terms domain and range. These simply mean the input and the output, respectively. Figure 8.21 shows graphs of all the functions. Notice that all the functions are periodic (repeating) and that ## Figure 8.21. Graphs of basic trigonometric functions.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.
Pythagorean theorem in terms of trig functions: sin(theta) 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 PlaneNow 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. ## Figure 8.22. Derivation of the rotation equations.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, 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. MATH For you math-heads, this derivation is very similar to a polar-only rotation with conversion to Cartesian coordinates at the end. That's how I came up with it. 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 PolygonTaking 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' The question is, how do you design the table? This really depends on the situation. Some programmers might want to use a single ## 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 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 Rotate_Polygon2D(&object, 10); 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. ## A Word on AccuracyI 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 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 ## ScalingAfter 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. ## Figure 8.24. The math of scaling.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 NOTE You may notice that the mouse pointer is visible on most demos. If you want to make it disappear (which is a good idea for games in general), you can make a call to the Win32 function |

↓

Ajax Editor JavaScript Editor