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.

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.

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

Types of Triangles and Quadrilaterals

First off, let's take a look at a general quadrilateral, shown in Figure 8.29. The quadrilateral can be decomposed into two triangles, ta and tb, which simplifies the problem of drawing a quadrilateral. Therefore, you can now concentrate on drawing a single triangle, which you can then use to draw either a triangle or a quadrilateral. Refer to Figure 8.30 and let's get busy.

First, there are only four possible types of triangles that you can generate. Let's label them:

• Flat top— This is a triangle that has a flat top, or in other words, the two topmost vertices have the same y coordinate.

• Flat bottom— This is a triangle that has a flat bottom, or in other words, the two bottommost vertices have the same y coordinate.

• Right side major— This is a triangle in which all three vertices have different y coordinates, but the longest side of the triangle slopes to the right.

• Left side major— This is a triangle in which all three vertices have different y coordinates, but the longest side of the triangle slopes to the left.

The first two types are the easiest to rasterize because each triangle leg is the same length (you'll see why that's important shortly). However, the latter two types are just as easy if you first decompose them into a pair of flat bottom and flat top triangles. You may or may not want to do this, but I usually do. If you don't, your rasterizer will need to contain steering logic to help with the slope changes on the side of the triangle with the two sides. Anyway, this will be much clearer once you see some examples.

Drawing Triangles and Quadrilaterals

Drawing a triangle is much like drawing a line, in that you must trace out the pixels of the edges to be drawn and then fill the triangle line by line. This is shown in Figure 8.31 for a flat bottom triangle. As you can see, once the slope of each edge is computed, you can simply move down each scanline, adjust the x endpoints xs and xe based on the slope (or more accurately 1/slope), and then draw a connecting line.

You don't need to use Bresenham's algorithm because you aren't interested in drawing a line. You're only interested in seeing where the line intersects the pixel centers at each integer interval. Here's the algorithm for the flat bottom triangle fill:

Of course, the initial conditions and boundary conditions for the algorithm take a little care to get right, but that's all there is to it, more or less—fairly simple. Now, before I show you anything else, let's talk about optimization for a minute.

At first glance, you might be tempted to use floating-point math for the edge tracing, which would work fine. However, the problem isn't that floating-point math is slower than integer math on a Pentium; the problem is that at some point, you'll have to convert the floating-point number into an integer.

If you let the compiler do it, you're looking at around 60 cycles. If you do it manually with FPU code, you can make it happen in about 10-20 cycles (remember, you need to convert to integers and then store). In any case, I refuse to lose 40 cycles on each raster line just to find my endpoints! Thus, you're going to create a floating-point version to show you the algorithm, but the final production model will use fixed-point math (which I'll brief you on in a moment).

Let's implement the flat bottom triangle rasterizer based on floating-point. First, let's label as shown in Figure 8.31. Here's the algorithm:

// compute deltas
float dxy_left  = (x2-x0)/(y2-y0);
float dxy_right = (x1-x0)/(y1-y0);

// set starting and ending points for edge trace
float xs = x0;
float xe = x0;

// draw each scanline
for (int y=y0; y <= y1; y++)
    {
    // draw a line from xs to xe at y in color c
    Draw_Line((int)xs, (int)xe, y, c);

    // move down one scanline
    xs+=dxy_left;
    xe+=dxy_right;

    } // end for y

Now, let's talk about some of the details of the algorithm and what's missing. First off, the algorithm truncates the endpoints each scanline. This is probably a bad thing because you're throwing away information. A better approach would be to round the value of each endpoint by adding 0.5 before converting to integer. Another problem has to do with the initial conditions. On the first iteration, the algorithm draws a line that's a single pixel wide. This works, but it's definitely a place for optimization.

Now, let's see if you can write the algorithm for a flat top triangle based on what you know. All you need to do is label the vertices, as shown in Figure 8.31, and then change the algorithm's initial conditions slightly so that the left and right interpolants are correctly computed. Here are the changes:

// compute deltas
float dxy_left  = (x2-x0)/(y2-y0);
float dxy_right = (x2-x1)/(y2-y1);

// set starting and ending points for edge trace
float xs = x0;
float xe = x1;

// draw each scanline
for (int y=y0; y <= y2; y++)
    {
    // draw a line from xs to xe at y in color c
    Draw_Line((int)(xs+0.5), (int)(xe+0.5), y, c);

    // move down one scanline
    xs+=dxy_left;
    xe+=dxy_right;

    } // end for y

Who's baaaaddd? Anyway, back to reality—you're halfway there. At this point, you can draw a triangle that has a flat top or a flat bottom, and you know that a triangle that doesn't have a flat top or bottom can be decomposed into one that does. Let's take a look at that problem and how to handle it.

Figure 8.32 shows a right side major triangle. Without proof, if you can rasterize a right side major triangle, the left side major is trivial. The first thing to notice is that you can start the algorithm off the same way you do for a flat bottom—that is, by starting the edge interpolators from the same starting point. The problem occurs when the left interpolator gets to the second vertex. This is where you need to make some changes. In essence, you must recompute the left side interpolant and continue rasterizing.

There are a number of ways to solve the problem. In the inner loop, you could draw the first part of the triangle up to the slope change, recompute the left side interpolant, and continue. Or you could do some triangular decomposition and break the triangle into two triangles (flat top and flat bottom) and then call the code you already have that draws a flat top and flat bottom triangle.

The latter is the technique you'll employ at this point. If you later find that this technique is inadequate in the 3D arena, change up and try the other method.

Triangular Deconstruction Details

Before I show you the code that draws a complete 8-bit colored triangle, I want to talk about a few more details involved in writing the algorithm correctly.

To decompose the triangle into a two triangles, one with a flat bottom and the other with a flat top, is a bit tricky. In essence, you need to take the height of the short side up until the first point where the slope changes, and then use this to find the point on the long side you'll use to partition the triangle. Basically, you take the vertical span from the top of the triangle and then, instead of interpolating one scanline on the long side, you interpolate n scanlines all at once by multiplying.

The result is equivalent to manually walking down the long edge of the triangle scanline by scanline. Then, once you have the correct point where you want to split the triangles, you simply make a call to your top and bottom triangle rasterizer and the triangle is drawn! Figure 8.32 showed the details of the splitting algorithm.

In addition to making the split, there comes another little problem—overdraw. If you send common vertices for the top triangle and the bottom triangle, the single scanline that is common to both will be rasterized twice. This isn't a big deal, but it's something to think about. You might want to step down on the bottom triangle one scanline to avoid the overdraw of the common scanline.

Almost ready… let's see, what else? Yes, what about clipping? If you recall, there are two ways to clip: object space and image space. Object space is great, but if you clip your triangle to the rectangle of the screen, in the very worst case you could add four more vertices! Take a look at Figure 8.33 to see this illustrated.

Instead you'll take the easy route and clip in image space as the polygon is being drawn, but you'll at least clip each scanline rather than each pixel. Moreover, you'll do some trivial rejection tests to determine if clipping is needed at all. If not, you'll jump to a part of the code that runs without clipping tests to run faster. Sound good?

Finally, while we're on the subject of trivial rejection and tests, we need to address all the degenerate cases of a triangle, such as a single point and a straight horizontal or vertical line. The code should test for these cases without blowing up! And of course, you can't assume that the vertices are in the correct order when sent to the function, so you'll sort them top to bottom, left to right. That way you'll have a known starting point. With all that in mind, here are the three functions that make up your 8-bit triangle drawing engine.

This function draws a triangle with a flat top:

void Draw_Top_Tri(int x1,int y1,
                  int x2,int y2,
                  int x3,int y3,
                  int color,
                  UCHAR *dest_buffer, int mempitch)
{
// this function draws a triangle that has a flat top

float dx_right,    // the dx/dy ratio of the right edge of line
      dx_left,     // the dx/dy ratio of the left edge of line
      xs,xe,       // the starting and ending points of the edges
      height;      // the height of the triangle

int temp_x,        // used during sorting as temps
    temp_y,
    right,         // used by clipping
    left;

// destination address of next scanline
UCHAR  *dest_addr = NULL;
// test order of x1 and x2
if (x2 < x1)
   {
   temp_x = x2;
   x2     = x1;
   x1     = temp_x;
   } // end if swap

// compute delta's
height = y3-y1;

dx_left  = (x3-x1)/height;
dx_right = (x3-x2)/height;

// set starting points
xs = (float)x1;
xe = (float)x2+(float)0.5;

// perform y clipping
if (y1 < min_clip_y)
   {
   // compute new xs and ys
   xs = xs+dx_left*(float)(-y1+min_clip_y);
   xe = xe+dx_right*(float)(-y1+min_clip_y);

   // reset y1
   y1=min_clip_y;

   } // end if top is off screen

if (y3>max_clip_y)
   y3=max_clip_y;

// compute starting address in video memory
dest_addr = dest_buffer+y1*mempitch;

// test if x clipping is needed
if (x1>=min_clip_x && x1<=max_clip_x &&
    x2>=min_clip_x && x2<=max_clip_x &&
    x3>=min_clip_x && x3<=max_clip_x)
    {
    // draw the triangle
    for (temp_y=y1; temp_y<=y3; temp_y++,dest_addr+=mempitch)
        {
        memset((UCHAR *)dest_addr+(unsigned int)xs,
                color,(unsigned int)(xe-xs+1));

        // adjust starting point and ending point
        xs+=dx_left;
        xe+=dx_right;

        } // end for

    } // end if no x clipping needed
else
   {
   // clip x axis with slower version

   // draw the triangle  
   for (temp_y=y1; temp_y<=y3; temp_y++,dest_addr+=mempitch)
       {
       // do x clip
       left  = (int)xs;
       right = (int)xe;

       // adjust starting point and ending point
       xs+=dx_left;
       xe+=dx_right;
       // clip line
       if (left < min_clip_x)
          {
          left = min_clip_x;

          if (right < min_clip_x)
             continue;
          }

       if (right > max_clip_x)
          {
          right = max_clip_x;

          if (left > max_clip_x)
             continue;
          }

       memset((UCHAR  *)dest_addr+(unsigned int)left,
              color,(unsigned int)(right-left+1));

       } // end for

   } // end else x clipping needed

} // end Draw_Top_Tri

This function draws a triangle with a flat bottom:

void Draw_Bottom_Tri(int x1,int y1,
                     int x2,int y2,
                     int x3,int y3,
                     int color,
                     UCHAR *dest_buffer, int mempitch)
{
// this function draws a triangle that has a flat bottom

float dx_right,    // the dx/dy ratio of the right edge of line
      dx_left,     // the dx/dy ratio of the left edge of line
      xs,xe,       // the starting and ending points of the edges
      height;      // the height of the triangle

int temp_x,        // used during sorting as temps
    temp_y,
    right,         // used by clipping
    left;

// destination address of next scanline
UCHAR  *dest_addr;

// test order of x1 and x2
if (x3 < x2)
   {
   temp_x = x2;
   x2     = x3;
   x3     = temp_x;
   } // end if swap

// compute delta's
height = y3-y1;

dx_left  = (x2-x1)/height;
dx_right = (x3-x1)/height;

// set starting points
xs = (float)x1;
xe = (float)x1; // +(float)0.5;

// perform y clipping
if (y1<min_clip_y)
   {
   // compute new xs and ys
   xs = xs+dx_left*(float)(-y1+min_clip_y);
   xe = xe+dx_right*(float)(-y1+min_clip_y);

   // reset y1
   y1=min_clip_y;

   } // end if top is off screen

if (y3>max_clip_y)
   y3=max_clip_y;

// compute starting address in video memory
dest_addr = dest_buffer+y1*mempitch;

// test if x clipping is needed
if (x1>=min_clip_x && x1<=max_clip_x &&
    x2>=min_clip_x && x2<=max_clip_x &&
    x3>=min_clip_x && x3<=max_clip_x)
    {
    // draw the triangle
    for (temp_y=y1; temp_y<=y3; temp_y++,dest_addr+=mempitch)
        {
        memset((UCHAR  *)dest_addr+(unsigned int)xs,
                color,(unsigned int)(xe-xs+1));

        // adjust starting point and ending point
        xs+=dx_left;
        xe+=dx_right;

        } // end for

    } // end if no x clipping needed
else
   {
   // clip x axis with slower version

   // draw the triangle

   for (temp_y=y1; temp_y<=y3; temp_y++,dest_addr+=mempitch)
       {
       // do x clip
       left  = (int)xs;
       right = (int)xe;

       // adjust starting point and ending point
       xs+=dx_left;
       xe+=dx_right;

       // clip line
       if (left < min_clip_x)
          {
          left = min_clip_x;

          if (right < min_clip_x)
             continue;
          }

       if (right > max_clip_x)
          {
          right = max_clip_x;

          if (left > max_clip_x)
             continue;
          }

       memset((UCHAR  *)dest_addr+(unsigned int)left,
              color,(unsigned int)(right-left+1));

       } // end for

   } // end else x clipping needed

} // end Draw_Bottom_Tri

And finally, this function draws a general triangle by splitting it into a flat top and flat bottom if needed:

void Draw_Triangle_2D(int x1,int y1,
                      int x2,int y2,
                      int x3,int y3,
                      int color,
                 UCHAR *dest_buffer, int mempitch)
{
// this function draws a triangle on the destination buffer
// it decomposes all triangles into a pair of flat top, flat bottom

int temp_x, // used for sorting
    temp_y,
    new_x;

// test for h lines and v lines
if ((x1==x2 && x2==x3)  ||  (y1==y2 && y2==y3))
   return;

// sort p1,p2,p3 in ascending y order
if (y2<y1)
   {
   temp_x = x2;
   temp_y = y2;
   x2     = x1;
   y2     = y1;
   x1     = temp_x;
   y1     = temp_y;
   } // end if

// now we know that p1 and p2 are in order
if (y3<y1)
   {
   temp_x = x3;
   temp_y = y3;
   x3     = x1;
   y3     = y1;
   x1     = temp_x;
   y1     = temp_y;
   } // end if

// finally test y3 against y2
if (y3<y2)
   {
   temp_x = x3;
   temp_y = y3;
   x3     = x2;
   y3     = y2;
   x2     = temp_x;
   y2     = temp_y;

   } // end if
// do trivial rejection tests for clipping
if ( y3<min_clip_y || y1>max_clip_y ||
    (x1<min_clip_x && x2<min_clip_x && x3<min_clip_x) ||
    (x1>max_clip_x && x2>max_clip_x && x3>max_clip_x) )
   return;

// test if top of triangle is flat
if (y1==y2)
   {
   Draw_Top_Tri(x1,y1,x2,y2,x3,y3,color, dest_buffer, mempitch);
   } // end if
else
if (y2==y3)
   {
   Draw_Bottom_Tri(x1,y1,x2,y2,x3,y3,color, dest_buffer, mempitch);
   } // end if bottom is flat
else
   {
   // general triangle that's needs to be broken up along long edge
   new_x = x1 + (int)(0.5+(float)(y2-y1)*(float)(x3-x1)/(float)(y3-y1));

   // draw each sub-triangle
   Draw_Bottom_Tri(x1,y1,new_x,y2,x2,y2,color, dest_buffer, mempitch);
   Draw_Top_Tri(x2,y2,new_x,y2,x3,y3,color, dest_buffer, mempitch);

   } // end else

} // end Draw_Triangle_2D

To use the function, you need only call the last function because it internally calls the other support functions. Here's an example of calling the function to draw a triangle with the coordinates (100,100), (200,150), (40,200) in color 30:

Draw_Triangle_2D(100,100, 200,150, 40,200, 30, back_buffer, back_pitch);

In general, you should send the coordinates in counterclockwise as they wind around the triangle. At this point it doesn't matter, but when you get to 3D, this detail becomes very important because a number of the 3D algorithms look at the vertex order to determine the front- or back-facing property of the polygon.

For an example of the polygon function in action, take a look at DEMO8_7.CPP|EXE. It draws randomly clipped triangles in 8-bit mode. Note that the global clipping region is defined by the general rectangular clipping variables:

int min_clip_x = 0,                             // clipping rectangle
    max_clip_x = (SCREEN_WIDTH-1),
    min_clip_y = 0,
    max_clip_y = (SCREEN_HEIGHT-1);

Now, let's move on to more complex rasterization techniques used for polygons with more than three vertices.

The General Case of Rasterizing a Quadrilateral

As you can see, rasterizing a simple triangle isn't the easiest thing in the world. Hence, you could assume that rasterizing polygons with more than three vertices is even harder. Guess what? It is!

Rasterizing a quadrilateral isn't bad if you split it into two triangles. For example, take a look back at Figure 8.29, where you see a quad being split into two triangles. Essentially, you can use this simple deterministic algorithm to split any quad into a two triangles:

Given that the polygon vertices are labeled 0, 1, 2, 3 in some order, such as CW (clockwise)…

Triangle 1 is composed of vertices 0, 1, 3

Triangle 2 is composed of vertices 1, 2, 3

That's it, home slice <BG>.

With that in mind, to create a quad rasterizer, you can simply implement the previous code into a function that does the splitting. I've done this for you in a function called Draw_QuadFP_2D(...). There isn't a floating-point version. Anyway, here's the code for it:

inline void Draw_QuadFP_2D(int x0,int y0,
                    int x1,int y1,
                    int x2,int y2,
                    int x3, int y3,
                    int color,
                    UCHAR *dest_buffer, int mempitch)
{
// this function draws a 2D quadrilateral

// simply call the triangle function 2x, let it do all the work
Draw_TriangleFP_2D(x0,y0,x1,y1,x3,y3,color,dest_buffer,mempitch);
Draw_TriangleFP_2D(x1,y1,x2,y2,x3,y3,color,dest_buffer,mempitch);

} // end Draw_QuadFP_2D

The function is identical to the triangle function, except that it takes one more vertex. For an example of this function in use, take a look at DEMO8_8.CPP|EXE. It creates a number of random quads and draws them on the screen.

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.

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.

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…

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.

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.

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 100x100, 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);

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.