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

Here, b is the point where the line intercepts the y-axis. Again, though, this doesn’t do you any good. The fundamental problem is that you’re moving x by 1.0 each cycle. You have to move it by a much smaller amount, such as 0.01, so that you catch all the pixels and don’t skip any, or else you have to try a different approach. Astute readers will realize that now matter how small you step x, you can always find a slope that will make it skip. You need to try something else—this is the basis of Bresenham’s algorithm.

In a nutshell, Bresenham’s algorithm starts at (x0,y0), but instead of using the slope to move, it moves x by one pixel and then decides which way to move the y component so that the line it’s tracing out matches the true line as closely as possible. This is accomplished with an error term that tracks the closeness of the line being rasterized to the true line. The algorithm continually updates the error term and tries to keep the digital rasterized line as close as possible.

The algorithm basically works in quadrant I of the Cartesian plane, and the other quadrants are derived with reflections. In addition, the algorithm considers two kinds of lines: lines with slope less than 45 degrees, or m < 1, and lines with slope greater than 45 degrees, or m > 1. I like to call these x-dominate and y-dominate, respectively. Here’s some pseudocode for an x-dominate line p0(x0,y0) and p1(x1, y1):

    // initialize starting point

    x = x0;

    y = y0;

    // compute deltas

    dx = x1 – x0;

    dy = y1 – y0;

    // initialize error term

    error = 0;

    // draw line

    for (int index = 0; index < dx; index++)

        {

        // plot the pixel

        Plot_Pixel(x,y,color);

        // adjust the error

        error+=dy;

        // test the error

        if (error > dx)

           {

           // adjust error

           error-=dx;

           // move up to next line

           y--;

           } // end if

        } // end for index

That’s it! Of course, this is only for the first octant, but all the others are taken care of simply by checking signs and switching values. The algorithm is the same.

There’s one point I want to make before I show you the code, and it’s about accuracy. The algorithm continually minimizes the error between the rasterized line and the true line, but the starting conditions could be a little better. You see, you’re starting the error term at 0.0. This is actually incorrect. It would be better to somehow take into consideration the first pixel position and then set the error a little better so that it straddles the minimum and maximum error. This can be done by setting the error term to 0.5, but because you’re using integers you must scale this by 2 and then add in the contribution from dx and dy. The bottom line is, you’re going to change the final algorithm to set the error to something like this:

    // x-dominate

    error = 2*dy – dx

    // y-dominate

    error = 2*dx – dy

And then you’re going to scale the error accumulation by two accordingly. Here’s the final algorithm, implemented as a function from your library called `Draw_Line()`. Notice that it takes both of the endpoints, color, video buffer, and video pitch and draws the line:

    int Draw_Line(int x0, int y0, // starting position

                  int x1, int y1, // ending position

                  UCHAR color,    // color index

                  UCHAR *vb_start,

                  int lpitch) // video buffer and memory pitch

    {

    // this function draws a line from xo,yo to x1,y1

    // using differential error

    // terms (based on Bresenhams work)

    int dx,         // difference in x’s

        dy,         // difference in y’s

        dx2,        // dx,dy * 2

        dy2,

        x_inc,      // amount in pixel space to move during drawing

        y_inc,      // amount in pixel space to move during drawing

        error,      // the discriminant i.e. error i.e. decision variable

        index;      // used for looping

    // precompute first pixel address in video buffer

    vb_start = vb_start + x0 + y0*lpitch;

    // compute horizontal and vertical deltas

    dx = x1-x0;

    dy = y1-y0;

    // test which direction the line is going in i.e. slope angle

    if (dx>=0)

       {

       x_inc = 1;

       } // end if line is moving right

    else

       {

       x_inc = -1;

       dx    = -dx;  // need absolute value

       } // end else moving left

    // test y component of slope

    if (dy>=0)

       {

       y_inc = lpitch;

       } // end if line is moving down

    else

       {

       y_inc = -lpitch;

       dy    = -dy;  // need absolute value

       } // end else moving up

    // compute (dx,dy) * 2

    dx2 = dx << 1;

    dy2 = dy << 1;

    // now based on which delta is greater we can draw the line

    if (dx > dy)

       {

       // initialize error term

       error = dy2 - dx;

       // draw the line

       for (index=0; index <= dx; index++)

           {

           // set the pixel

           *vb_start = color;

           // test if error has overflowed

           if (error >= 0)

              {

              error-=dx2;

              // move to next line

              vb_start+=y_inc;

           } // end if error overflowed

           // adjust the error term

           error+=dy2;

           // move to the next pixel

           vb_start+=x_inc;

           } // end for

       } // end if |slope| <= 1

    else

       {

       // initialize error term

       error = dx2 - dy;

       // draw the line

       for (index=0; index <= dy; index++)

           {

           // set the pixel

           *vb_start = color;

           // test if error overflowed

           if (error >= 0)

              {

              error-=dy2;

              // move to next line

              vb_start+=x_inc;

              } // end if error overflowed

           // adjust the error term

           error+=dx2;

           // move to the next pixel

           vb_start+=y_inc;

           } // end for

       } // end else |slope| > 1

    // return success

    return(1);

    } // end Draw_Line

> Note: This function works in 8-bit modes only. However, the library has a 16-bit version as well, with the name `Draw_Line16()`.

The function basically has three main sections. The first section does all the sign and endpoint swapping and computes the x and y axes’ deltas. Then based on the dominance of the line, that is, if dx > dy, or dx <= dy ,one of two main loops draws the line.

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.