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.

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
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;

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.

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

Drawing and Clipping Polygons

Drawing a polygon is as simple as drawing n connected line segments. You already know how to draw a line, so all you have to do to draw a polygon is loop on the vertices and connect the dots. Of course, if you want the polygon clipped, you should call the clipping function, which I've put a little wrapper around called Draw_Clip_Line(). It has the same parameterization as Draw_Line(), except it clips to the globally defined clipping region. Here's a general function to draw a POLYGON2D structure:

int Draw_Polygon2D(POLYGON2D_PTR poly, UCHAR *vbuffer, int lpitch)
{
// this function draws a POLYGON2D based on

// test if the polygon is visible
if (poly->state)
   {
   // loop thru and draw a line from vertices 1 to n
   for (int index=0; index < poly->num_verts-1; index++)
        {
        // draw line from ith to ith+1 vertex
        Draw_Clip_Line(poly->vlist[index].x+poly->x0,
                       poly->vlist[index].y+poly->y0,
                       poly->vlist[index+1].x+poly->x0,
                       poly->vlist[index+1].y+poly->y0,
                       poly->color,
                       vbuffer, lpitch);

        } // end for

       // now close up polygon
       // draw line from last vertex to 0th
        Draw_Clip_Line(poly->vlist[0].x+poly->x0,
                       poly->vlist[0].y+poly->y0,
                       poly->vlist[index].x+poly->x0,
                       poly->vlist[index].y+poly->y0,
                       poly->color,
                       vbuffer, lpitch);

   // return success
   return(1);
   } // end if
else
   return(0);

} // end Draw_Polygon2D

The only weird thing about the function is the use of (x0,y0) as the center of the polygon. This is so you can move the polygon around without messing with the individual vertices. Furthermore, defining the polygon in a relative manner from its center allows you to use what are called local coordinates rather than world coordinates. Take a look at Figure 8.15 to see the relationship between the two.

Local coordinates in relation to world coordinates.It's always much better to define polygons relative to the center of (0,0) (local coordinates) and then later transform the polygon out to a position (x,y) (world coordinates). You'll learn about local, world, and camera (the point relative to the viewpoint) coordinates in detail when you get to 3D, but for now, just take note that they exist.

As a demo, I have created DEMO8_3.CPP|EXE. It first creates an array of polygon objects, each with eight points. These polygons look like little asteroids. Then the program randomly positions these asteroids and moves (translates) them around the screen. The program works in 640x480x8 and uses page flipping to accomplish the animation. Figure 8.16 is a screen shot from the program.

All right, Mr. Spock, now you can define a polygon and draw it. The next topic I want to cover is 2D transformations—translating, rotating, and scaling polygons.