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

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

Figure 8.29 A general four-sided quadrilateral.

Figure 8.30 General triangle types.

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.

Figure 8.31 Rasterization of a triangle.

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:

  1. First, compute the ratio dx/dy for the left side and the right side. Basically, this is 1/slope. You need it because you’re going to use a vertically oriented approach. Thus, you want to know the change in x for each y, which is simply dx/dy or 1/M. Call these values `dxy_left` and `dxy_right` for the left and right side, respectively.
  2. Starting at the topmost vertex (x0,y0), set xs=xe=x0 and y=y0.
  3. Add `dxy_left` to xs and `dxy_right` to xe. This will trace the endpoints to fill.
  4. Draw a line from (xs,y) to (xe,y).
  5. Go back to step 3 until the height of the triangle from the top to the bottom has been rasterized.

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

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.