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

#### Triangulating Quads

So let’s see… you can draw a triangle and a quad, but how do you draw a polygon with more than four vertices? You could triangulate the polygon, as shown in Figure 8.34. Although this is a good approach, and many graphics engines do just this (especially hardware), it’s a bit too complex of a problem to solve in general.

Figure 8.34 Triangulating a large, multisided polygon.

However, if the polygon is constrained to be convex (as yours are), it’s much simpler. There are many algorithms to do this, but the one I generally use is recursive in nature and very simple. Figure 8.35 shows the steps of a five-sided convex polygon being triangulated.

Figure 8.35 A possible triangulation algorithm visualized.

Note in Figure 8.35 that there are several possible valid triangulations. Thus, there may be heuristics and/or some kind of evaluation function applied to optimize the triangulation. For example, it may be a good idea to triangulate with the triangles that have nearly the same area, or first you might want to try to create very large triangles.

Whatever the case, it’s something to think about in relation to your final engine. Anyway, here’s a general algorithm that gets the job done.

Given a convex polygon with n vertices (n can be even or odd) in CC or CW order to triangulate…

  1. If the number of vertices left to process is greater than three, continue to step 2; otherwise, stop.
  2. Take the first three vertices and create a triangle with them.
  3. Split off the new triangle and recursively process step 2 with the remaining (n-1) vertices.

In essence, the algorithm keeps “peeling” off triangles and then resubmitting the remaining vertices back to the algorithm. It’s very stupid and it doesn’t do any preprocessing or testing, but it works. And of course, once you’re done converting the polygon into triangles, you can send each one down the rasterization pipeline to the triangle renderer.

Okay, that’s enough of that boooorrrrrriiinnnggg algorithm. Now let’s look at another approach to rasterizing a general convex polygon the hard way. If you think in terms of how you rasterized a triangle, it’s simply a matter of housekeeping to rasterize an n-sided convex polygon.

Take a look at Figure 8.36 to see the algorithm in action. In general, what you’re going to do is sort the vertices from top to bottom and left to right so you have a sorted array of vertices in CW order this time. Then, starting from the topmost vertex, you’re going to start rasterizing the two edges (left and right) emanating from the top vertex. When one of the edges comes to the point where it hits another vertex on the right or left side, you’ll recompute the rasterization interpolants—that is, the `dx_left` or `dx_right` values—and continue until the polygon is rasterized.

Figure 8.36 Rasterizing an n-sided convex polygon without triangulation.

That’s really all there is to it. A flow chart for the algorithm is shown in Figure 8.37. Again, there are a number of boundary details to worry about, such as being careful not to put one of the edge interpolators out of sync during a vertex transition, but that’s about it. And again, you can clip using image space or object space. Let’s talk about this for a moment.

Figure 8.37 A flowchart of the general n-sided convex polygon-rendering algorithm.

When you’re rasterizing triangles, you don’t want to clip in image space because you could end up with a six-sided polygon if all vertices are clipped. This would be bad because you’d have to convert the new polygon back into triangles. However, because your new algorithm likes general polygons, who cares about adding vertices?

Nevertheless, you need to consider one point—can a convex polygon be turned concave during a clipping operation? Absolutely, but (there’s always a “but,” and this time it’s a good one) only if the clipping region is itself concave. Thus, clipping the convex polygon to the rectangle of the screen will at worst add one vertex per vertex that falls out of the clipping region.

This is usually the best approach when you’re rasterizing an n-sided polygon—that is, to clip in object space and then rasterize the polygon without internal scanline clipping code. This is the approach you’ll take here.

The following function takes a standard `POLYGON2D_PTR`, along with the frame buffer address and memory pitch, and then rasterizes the sent polygon. Of course, the polygon must be convex, and all vertex points must be within the clipping region because the function doesn’t clip. Here’s the function prototype:

    void Draw_Filled_Polygon2D(POLYGON2D_PTR poly,

                              UCHAR *vbuffer, int mempitch);

To draw a square centered at 320,240 with sides 100×100, here’s what you would do:

    POLYGON2D square; // used to hold the square

    // define points of object (must be convex)

    VERTEX2DF square_vertices[4]

                     = {-50,-50, 50,-50, 50,50,-50, 50};

    // initialize square

    object.state       = 1;   // turn it on

    object.num_verts   = 4;

    object.x0          = 320;

    object.y0          = 240;

    object.xv          = 0;

    object.yv          = 0;

    object.color       = 255; // white

    object.vlist       = new VERTEX2DF [square.num_verts];

    // copy the vertices into polygon

    for (int index = 0; index < square.num_verts; index++)

        square.vlist[index] = square_vertices[index];

    // .. in the main game loop

    Draw_Filled_Polygon2D(&square, (UCHAR *)ddsd.lpSurface, ddsd.lPitch);

> Tip: Whenever you write a rasterization function, it’s always a good idea to test if it can successfully render an object as it rotates. Many times when you test a rasterization function, you end up sending it “easy” coordinates. However, by rotating an object, you get all kinds of tweaked-out values. If the function can hang through a complete 360-degree rotation, you know it’s good to go!

UHHHH! Can you feel that, baby? Anyway, I would show you the listing of the function, but it’s rather large. However, you can see the code for yourself in `DEMO8_9.CPP|EXE`, which illustrates the use of the function by rotating around a four-sided polygon (a square) and then calling the fill function to draw the polygon. But instead of drawing the square using two triangles, the function rasterizes the polygon directly—without clipping.

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.