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

As an aside, I want to bring your attention to the bolded sum of products (1*1 + 2*6). This product and all the others are really vector dot products (a vector is just a collection of values, like a matrix with one row). A dot product has a very explicit mathematical meaning, which we’ll get to later, but in general, you can compute the dot product of two vectors that are each 1×n by simply summing up the products of the independent components. Or, mathematically:

    Let a = [1 2 3] b = [4 5 6]

> Warning: I’m being a little cavalier right now with dot products; technically, they’re only valid for vectors, but a column or row of a matrix is really a vector. Basically, I’m in a transitional period and I don’t want to kill you. I want to help you…

    a.b = [(1*4) + (2*5) + (3*6)]

        = [32]

          1x1

Or, if you want to be a little wet ’n’ wild, it’s just a scalar.

So that’s how you multiply matrices. Another way to think of it is that if you want to compute the product of A×B, call it C. You can do this element by element. Hence, if you want the cijth element (where both i and j are zero-based), you can find it by taking the ith row of A and doting (summing the products) with the jth column of B.

At this point, I think you get the general idea of what’s going on. Let’s take a look at some code that performs matrix multiplication. First, let’s define a matrix type:

    // here’s a 3x3, useful for 2D stuff and some 3D

    typedef struct MATRIX3X3_TYP

           {

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

           } MATRIX3X3, *MATRIX3X3_PTR;

    int Mat_Mul3X3(MATRIX3X3_PTR ma,

                   MATRIX3X3_PTR mb,

                   MATRIX3X3_PTR mprod)

    {

    // this function multiplies two matrices together and

    // stores the result

    for (int row=0; row<3; row++)

        {

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

            {

            // compute dot product from row of ma

            // and column of mb

            float sum = 0; // used to hold result

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

                 {

                 // add in next product pair

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

                 } // end for index

            // insert resulting row,col element

            mprod->M[row][col] = sum;

            } // end for col

        } // end for row

    return(1);

    } // end Mat_Mul3X3

You’ll notice that there’s a lot of math going on. In general, matrix multiplication is an N3 operation, meaning that there are three nested loops. However, a number of optimizations can be used, such as testing either the multiplier or multiplicand for 0 and not performing the multiplication.

#### Transformations Using Matrices

Using matrices to perform 2D/3D transformations is a snap. Basically, what you’re going to do is multiply the point you want to be transformed against the desired transformation matrix. Or, mathematically:

    p’ = p*M

where p`’` is the transformed point, p is the original point, and M is the transformation matrix. If I haven’t mentioned that matrix multiplication is not commutative, let me do so now:

    (A*B) NOT EQUAL (B*A)

This statement is generally true unless A or B is the identity matrix or the zero matrix, or they’re the same matrix. Order counts when you’re matrix multiplying.

In this case, you’re going to convert a single (x,y) point into a single row matrix with dimension 1×3, and then pre-multiply it by a 3×3 transformation matrix. The result will also be a 1×3 row matrix, and you can pick off the first two components as the transformed x`’`,y`’`. Alas, you should have a slight problem with all this—what is the last component of the initial matrix p there for, if only two pieces of data, x and y, are needed?

In general, you’re going to represent all points like this:

    [x y 1.0]

The factor 1.0 is to make the matrix into what are called homogenous coordinates. This allows any transformed point to be scaled, and it also allows for translations in transformations. Other than that, the mathematical basis for it is unimportant. Just think of it as a dummy variable that you need. Hence, you’re going to create a matrix that’s 1×3 to hold your input point and then post-multiply it by the transformation matrix. Here are the data structures for the point or 1×3 matrix:

    typedef struct MATRIX1X3_TYP

            {

            float M[3]; // data storage

            } MATRIX1X3, *MATRIX1X3_PTR;

And here’s a function to multiply a point against a 3×3 matrix:

    int Mat_Mul1X3_3X3(MATRIX1X3_PTR ma,

                       MATRIX3X3_PTR mb,

                       MATRIX1X3_PTR mprod)

    {

    // this function multiplies a 1x3 matrix against a

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

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

            {

            // compute dot product from row of ma

            // and column of mb

            float sum = 0; // used to hold result

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

                 {

                 // add in next product pair

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

                 } // end for index

            // insert resulting col element

            mprod->M[col] = sum;

            } // end for col

    return(1);

    } // end Mat_Mul_1X3_3X3

And to create a point p with components x and y, you would do the following:

    MATRIX1X3 p = {x,y,1};

With all that in mind, let’s take a look at the transformation matrices for all the operations you’ve performed manually.

### Translation

To perform translation, you want to leave the x,y components alone while adding the translation factors to x,y. This matrix will do the job:

        |1  0  0 |

    Mt =|0  1  0 |

        |dx dy 0 |

Math Notice the necessity of the 1.0 factor in the left-hand matrix representing the point. Without it, there would be no way to perform translation.

Example:

    p = [x y 1]

                          |1  0  0 |

    p’ = p*Mt = [x y 1] * |0  1  0 | = [(x+1*dx) (y+1*dy) 1]

                          |dx dy 1 |

And if you pull out the first two elements, you get

    x’ = x+dx

    y’ = y+dy

This is exactly what you wanted.

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.