Drawing Lines

Up to this point, you've drawn all of your graphical objects with either single points or bitmaps. Both of these entities are considered non-vector entities. A vector entity is something like a line or a polygon, as shown in Figure 8.1. So your first problem is figuring out how to draw a line.

You may think that drawing a line is trivial, but I assure you it's not. Drawing a line on a computer screen has a number of problems associated with it, such as finite resolution, mapping real numbers onto an integer grid, speed issues, and so forth. In many cases, a 2D or 3D image is composed of a number of points that define the polygons or faces that make up an object or scene. These points are usually in the form of real numbers, such as (10.5, 120.3) and so on.

The first problem is that a computer screen is represented by a 2D grid of whole numbers, so plotting (10.5, 120.3) is almost impossible. You can only approximate it. You might decide to truncate the coordinates and plot (10,120), or you might decide to round them and plot (11,120). Finally, you might go high-tech and decide to perform a weighted pixel plotting function that plots a number of pixels of differing intensities centered at the pixel center (10.5, 120.3), as shown in Figure 8.2.

Basically, an area filter computes how much the original pixel overlaps into the other pixel positions and then draws those pixels in the same color as the desired pixel, but with decreased intensity. This creates a much rounder-looking pixel that looks anti-aliased, but in general you have lowered your maximum resolution.

Instead of me jabbering on about line-drawing algorithms, filtering, and such, let's get to the cream pie and see a couple of really good line-drawing algorithms that you can use to compute the integer coordinates of a line from (x0,y0) to (x1,y1).

Bresenham's Algorithm

The first algorithm I want to present you with is called Bresenham's algorithm, named after the man who invented it in 1965. Originally, the algorithm was designed to draw lines on plotters, but it was later adapted to computer graphics. Let's take a quick look at how the algorithm works and then see some code. Figure 8.3 shows the general problem you're trying to solve. You want to fill in the pixels from point p1 to p2 with the pixels that most closely fit to the real line. This process is called rasterization.

If you're a little rusty on lines, let me refresh your memory. The slope of a line is related to the angle that the line makes with the x-axis. Hence, a line with slope 0 is totally horizontal, while a line with infinite slope is totally vertical. A line with slope 1.0 is diagonal or 45 degrees. Slope is defined as rise over run, or, mathematically:

         Rise     Change in y   dy        (y1–y0)
Slope = ------ = ------------- ---- = m = ---------
         Run      Change in x   dx        (x1–x0)

For example, if you have a line with coordinates p0(1,2) and p1(5,22), the slope or m is

(y2–y1)/(x2–x1) = (22–2)/(5–1) = 20/4 = 5.0

So what does the slope really mean? It means that if you increment the x-coordinate by 1.0 unit, the y-coordinate will change by 5.0 units. Okay, this is the beginning of a rasterization algorithm. At this point, you have a rough idea of how to draw a line:

Figure 8.4 shows this example for the previous values of p0 and p1.

Do you see the problem? Every time you step one pixel in x, you step 5.0 pixels in y. Therefore, you're drawing a line that has a lot of holes in it! The mistake you're making is not tracing a line, but plotting pixels as integer intervals; that is, whenever x is a whole number. In essence, you're plugging whole numbers into the equation of a line:

(y–y0) = m*(x–x0)

Here, (x,y) are the current values or pixel locations, (x0,y0) is the starting point, and m is the slope. Rearranging this a little, you have

y = m*(x–x0)+y0

So, if you let (x0,y0) be (1,2) and m be 5 as in the example, you get the following results:

x        y = 5*(x–1)+2
-----------------------------
1        2 (starting point)
2        7
3        12
4        17
5        22 (ending point)

Now, you might ask if the slope-intercept form of a line can help:

y = m*x + b

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

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.

Speeding Up the Algorithm

Looking at the code, you might think that it's fairly tight and there's no room for opti-mization. However, there are a couple of ways to speed up the algorithm. The first way is to take into consideration that all lines are symmetrical about their midpoints, as shown in Figure 8.5, so there's no need to run the algorithm for the whole line. All you have to do is halve the line and copy the other half. In theory this is solid, but implementing it is a pain because you have to worry about lines that have an odd number of pixels and then decide to draw one extra pixel at either end. Not that it's hard—just ugly.

The other optimizations have been discovered by a number of people (including myself), including Michael Abrash's algorithm Run-Slicing, Xialon Wu's Symmetric Double Step, and Rokne's Quadruple Step. Basically, all these algorithms take advantage of the consistency of the pixel patterns that make up a line. The Run-Slicing algorithm takes advantage of the fact that sometimes large runs of pixels exist, such as the line (0,0) to (100,1). The line should consist of two runs of 50 pixels. One runs from (0-49,0) and the other runs from (50-100,1), as shown in Figure 8.6.

So what's the point in doing the line algorithm on each pixel? The problem is that the setup and the innards of the algorithm are very complex, but they work for lines with very large or very small slopes.

Wu's Symmetric Double Step algorithm works on a similar premise, but instead of considering runs, it notes that for every two pixels there are only four different patterns that can occur, as shown in Figure 8.7. It's fairly easy to compute the next pattern by looking at the error term and then plotting the entire pattern, in essence moving at twice normal speed. This, coupled with symmetry, gives you a speed increase of four times over the basic Bresenham algorithm. That's the story.

For a demo of the line drawing function, take a look at DEMO8_1.CPP|EXE, which draws random lines in 640x480 mode.