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

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 addition to the preceding functions for drawing polygons, I’ve also created fixed-point versions of the functions that run a bit faster during the rasterization phase. These are also in the library file `T3DLIB1.CPP`. They’re named with `FP` appended to each function name, but they all work the same. Basically, the only one you need to call is `Draw_TriangleFP_2D(...)`. The function generates the same image as `Draw_Triangle_2D(...)` does, but it works a bit faster. If you’re interested in fixed-point math, skip ahead to the Chapter 11, “Algorithms, Data Structures, Memory Management, and Multithreading,” which covers optimization.

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

> Note: I’m getting sloppy with the parameters here. You could probably do a lot better by defining a polygon structure here and then passing an address rather than an entire set of vertices. I’m going to leave the code “as is” for now, but keep that in mind because you’ll get to it when you do the 3D stuff.

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.

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.