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

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.

Figure 8.32 Rasterization of a right side major triangle.

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.

Figure 8.33 Worst-case scenario when clipping a triangle.

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?

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.