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

### Scaling

To scale a point relative to the origin, you want to multiply the x,y components by scaling factors sx and sy, respectively. In addition, you want no translation during the scaling operation. Here’s the matrix you want:

        |sx  0   0|

    Ms =|0   sy  0|

        |0   0   1|

    Eg. p = [x y 1]

                          |sx  0   0|

    p’ = p*Ms = [x y 1] * |0   sy  0| = [(x*sx) (y*sy) 1]

                          |0   0   1|

Math Note the 1 in the lower-right corner of the transformation matrix. Technically, it’s not necessary because you’re never going to use the result from the third column. Hence, you’re wasting math cycles. The question is, can you remove the last column of all the transformation matrices and use a 3×2 instead? Let’s see the rotation matrix before you answer that…

Again, this is the desired result for scaling; that is

    x’ = sx*x

    y’ = sy*y

### Rotation

The rotation matrix is the most complex of all the transformations because it’s full of trig functions. Basically, you want to rotate the input point by using the rotation equations. To achieve this, you must look at the rotation equations, pick the operators, and then push them into a matrix. In addition, you don’t want any translation, so the bottom row in positions 0 and 1 will be 0. Here’s the matrix that does the job:

         | cos  ×  sin × |

    Mr = |-sin  ×  cos × |

         | 0    0      1 |

    Eg. p = [x y 1]

                          | cos  ×  sin × |

    p' = p*Mr = [x y 1] * |-sin  ×  cos × | =

                          | 0    0      1 |

    p' = [(x*cos × – y*sin ×) (x*sin × + y*cos ×) 1]

Which is correct!

Before moving on to polygons, let’s discuss the question that was posed before in reference to using a 3×2 post-multiplication matrix rather than a 3×3. It looks as if the last term in all the matrix multiplications is completely discarded, in addition to always being 1.0. Both of these statements are true.

Therefore, for the transformations that you’ve performed thus far, you can use a 3×2. However, I wanted to use a 3×3 to make a point about homogenous matrices and coordinates. The significance of the last 1.0 is this (in reality, let’s refer to it as q): To convert the coordinates to their final correct form after the transformation is complete, you would divide by the factor q, or in other words:

    p' =[x y q]

    x' = x/q

    y' = y/q

However, because q = 1 in this case, the divisions are unnecessary, as is the computation of q. Nonetheless, this factor will have importance later in the discussion of 3D graphics, so keep it in mind.

In any case, with this new information, you can change a couple of data structures and store all points in a 1×2 and all transformation matrices in a 3×2, using the following data structures and transform function:

    // the transformation matrix

    typedef struct MATRIX3X2_TYP

            {

            float M[3][2]; // data storage

            } MATRIX3X2, *MATRIX3X2_PTR;

    // our 2D point

    typedef struct MATRIX1X2_TYP

            {

            float M[2]; // data storage

            } MATRIX1X2, *MATRIX1X2_PTR;

    int Mat_Mul1X2_3X2(MATRIX1X2_PTR ma,

                       MATRIX3X2_PTR mb,

                       MATRIX1X2_PTR mprod)

    {

    // this function multiplies a 1x2 matrix against a

    // 3x2 matrix – ma*mb and stores the result

    // using a dummy element for the 3rd element of the 1x2

    // to make the matrix multiply valid i.e. 1x3 X 3x2

        for (int col=0; col<2; col++)

            {

            // compute dot product from row of ma

            // and column of mb

            float sum = 0; // used to hold result

            for (int index=0; index<2; index++)

                 {

                 // add in next product pair

                 sum+=(ma->M[index]*mb->M[index][col]);

                 } // end for index

            // add in last element * 1

            sum+= mb[index][col];

            // insert resulting col element

            mprod->M[col] = sum;

            } // end for col

    return(1);

    } // end Mat_Mul_1X2_3X2

> Note: You must always multiply a m × r matrix by an r × n matrix. In other words, the inner dimension must be equal. Obviously, 1×2 and 3×2 don’t work because 2 is not equal to 3. However, in the code, you can add a dummy element 1.0 to each of the 1×2’s, making them into 1×3’s, just for the math to work out.

For a demo of using matrices in a program, check out `DEMO8_6.CPP|EXE`. I’ve created a polygon that resembles a little spaceship in wire frame, and you can scale, rotate, and translate it. Take a look at Figure 8.26 for a screen shot.

Figure 8.26 `DEMO8_6.EXE` in action.

Here are the control keys for this demo:

Esc | Exits the demo.
A | Scales up 10%.
S | Scales down 10%.
Z | Rotates counterclockwise.
X | Rotates clockwise.
Arrow keys | Translates in x and y.

### Solid Filled Polygons

Let’s take a break from all the math and get back to something a little more tangible, shall we? One of the most basic requirements of a 3D engine, and many 2D engines, is to draw a solid or filled polygon, as shown in Figure 8.27. This is the next problem you’re going to tackle.

Figure 8.27 Filling a polygon.

There are a number of ways to draw filled polygons. However, because the point of all this is to create 2D/3D games, you want to be able to draw a filled polygon that can be a single color or texture-mapped, as shown in Figure 8.28. For now let’s leave texture mapping alone until we get to the 3D stuff and just figure out how to draw a solid polygon of any color.

Figure 8.28 A solid shaded polygon versus a texture-mapped polygon.

Before you solve the problem, you must clearly define what it is that you’re trying to solve. The first constraint is that all polygons must be convex, so no holes or weird shapes are allowed. Then you have to decide how complex the polygon can be. Can it have three sides, four sides, or any number of sides? This is a definite issue, and you must employ a different algorithm for polygons that have more than three sides (four-sided polygons or quadrilaterals can be broken into two triangles).

Thus, I’m going to show you how to fill both general polygons and triangles (which will be the basis of the final 3D engine you create).

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.