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

All you do is send the function the endpoints of the line, and it clips them to the clipping rectangle defined by the globals:

    int min_clip_x = 0,      // clipping rectangle

        max_clip_x = SCREEN_WIDTH-1,

        min_clip_y = 0,

        max_clip_y = SCREEN_HEIGHT-1;

I usually set these globals to the size of the screen. The only detail about the function is that it takes the parameters as a call by the reference, so the variables can be modified. Make copies if you don’t want the variables to be changed. Here’s an example of the function in use:

    // clip the line (x1,y1) to (x2,y2)

    // make copies

    int clipped_x1 = x1,

        clipped_y1 = y1,

        clipped_x2 = x2,

        clipped_y2 = y2;

    // clip the line

    Clip_Line(clipped_x1, clipped_y1,

              clipped_x2, clipped_y2);

When the function returns the `clipped_*` variables, they will have new clipped values based on the clipping rectangle stored in the globals.

The demo, `DEMO8_2.CPP|EXE`, creates a 200×200 clipping region that is centered on the screen and then draws random lines within it. Notice how they’re clipped <BG>.

### Wireframe Polygons

Now that you know how to draw lines and clip them to a rectangle, you’re ready to move on to higher order objects such as polygons. Figure 8.13 illustrates a number of different polygons: a triangle, a square, and a pentagon. A polygon consists of three or more connected points and is closed. Also, polygons can be either convex or concave.

Figure 8.13 Some general polygons.

Math One way to test for concavity is the following: If you can draw a line from any two edges of a polygon and the line falls outside the polygon, the polygon is concave.

There is a mathematical definition and proof to prove that a polygon is convex or concave, but in general a convex polygon has no “dents” in it, while a concave polygon does.

Now I want to give you some ideas about how you might represent 2D polygonal objects and manipulate them.

#### Polygon Data Structures

In a game, the selection of data structures is of the utmost importance. Forget everything you ever learned about using complex data structures and concentrate on one thing—speed! In a game, you must access data all the time because the game is being rendered based on it. You must consider the ease of access, the size of the data, and the relative size the data is accessed by the processor cache, as well as the second-level cache and so forth. The bottom line is that having a 1000Mhz processor isn’t going to help much if you can’t get to your data effectively and quickly.

My rules of thumb when designing data structures are these:

  • Keep it simple.
  • Use static arrays for small structures that you know the size of, within 25 percent.
  • Use linked lists when it makes sense.
  • Use trees and other exotic data structures only if it’s going to make the code run faster, not just because it’s cool!
  • Finally, think ahead when you’re designing data structures. Don’t corner yourself into not allowing new features or inventing some absurd limit on objects.

Anyway, enough preaching. Let’s take a look at a very basic structure for a polygon. Assume that a polygon can have a large number of vertices. That limits the static array to hold the vertices, so the storage will have to be dynamic for the actual vertices. Other than that, you’ll need the polygon’s (x,y) position, its velocity (more on this later), its color, and maybe some state information to track attributes that you may not think of. Here’s my first hack at it:

    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

C++ This is a perfect place for C++ and a class, but I want to keep it simple in case you’re a straight C user. However, as an exercise, I would like all C++ programmers to convert all this polygon stuff into a nice class.

    VERTEX2DI *vlist; // pointer to vertex list

    } POLYGON2D, *POLYGON2D_PTR;

Not bad, but you’re missing something here: the definition of `VERTEX2DI`. Again, this is typical when you’re designing data structures. You haven’t defined everything, but know you need something. Let’s define `VERTEX2DI` now. Basically, it’s just an integer-accurate 2D vertex:

    typedef struct VERTEX2DI_TYP

    {

    int x,y;

    } VERTEX2DI, *VERTEX2DI_PTR;

Math In many 2D/3D engines, all vertices are only accurate to whole numbers. Of course, this makes all scaling and rotation transformations less than accurate. The problem with floating-point numbers is that they’re slow to convert to integers. Even though the Pentium can perform floating-point math as fast or faster than integer math, the conversion to integer at the end of rasterization kills you. This isn’t an issue as long as the conversion happens at the very end, but if you keep going back and forth, you will kill your performance. The bottom line is that if you can hang with integer accuracy, do so exclusively. Otherwise, go to floating-point, but keep the conversions down!

At this point, you have nice data structure to hold a vertex and a polygon. Figure 8.14 depicts the structure abstractly in relationship to a real polygon.

Figure 8.14 The polygon data structure.

About the only thing you need to do to the `POLYGON` structure to use it is allocate the memory for the actual vertex storage, which you would do with something like this:

    POLYGON2D triangle; // our polygon

    // initialize the triangle

    triangle.state       = 1; // turn it on

    triangle.num_verts   = 3; // triangle

    triangle.x0          = 100; // position it

C++

Note that I’ve used the C++ `new` operator to allocate the memory. Thus, I’ll have to use the `delete` operator to delete it. In straight C, the allocation would look like

    (VERTEX2DI_PTR)malloc(triangle.num_verts*sizeof(VERTEX2DI)).

    triangle.y0          = 100;

    triangle.xv          = 0; // initial velocity

    triangle.yv          = 0;

    triangle.color       = 50;  // assume 8-bit mode index 50

    triangle.vlist       = new VERTEX2DI[triangle.num_verts];

Fantabulous! Now let’s see how to draw one of these things.

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.