VGA Mode 13h Graphics Primitives, Part 1

Atrevida Game Programming Tutorial #8
Copyright 1997, Kevin Matz, All Rights Reserved.

Prerequisites:

  • Chapter 7: Introduction to VGA Graphics Programming Using Mode 13h

       
This chapter will consider methods for drawing "graphics primitives" such as horizontal and vertical lines, slanted lines, boxes, and bars (filled rectangles). We will also consider some basic optimization strategies.

Horizontal lines

Horizontal lines are easy to draw: they are, of course, simply a set of pixels in a row. So, our first attempt at writing a horizontal line-drawing function would most likely look somewhat like this:

void HorizontalLine (int x1, int y, int x2, unsigned char color)
{
    int x;

    for (x = x1; x <= x2; x++)
        PutPixel (x, y, color);
}

This works entirely correctly, as long as the value passed via the x1 parameter is less than or equal to the value passed via x2. But can we improve on this function and make it execute faster?

Let's try a bit of optimization. (We'll learn some more basic techniques in a later chapter.) We can start by asking how many times the for loop will be executed. If we want to draw a horizontal line from coordinates (4, 2) to (9, 2), the for loop must count from 4 to 9. 4, 5, 6, 7, 8, and 9: that's six numbers, so there must be six iterations of the for loop in that case. (If you want a formula, you could use "x2 - x1 + 1".) That means that the PutPixel() function is being called six times. Calling functions and passing parameters takes time. Admittedly, it is a rather short amount of time, but if you are going to perform many, many function calls, that time can add up. Instead of a line with six pixels, imagine drawing an image to the Mode 13h screen the same way; that would mean 320 * 200 = 64000 calls to the PutPixel() function. The time spent performing the "administrative tasks" for functions that are called repetitively can slow down a program.

Let's eliminate the PutPixel() call, by putting the code for PutPixel() right inside the for loop in the HorizontalLine() function. I'll use the far pointer method for plotting pixels:

/* Put these lines near the top of your program: */
#define SCREEN_WIDTH 320
char far *ptr_to_video_segment = MK_FP(0xA000, 0x0000);

void HorizontalLine (int x1, int y, int x2, unsigned char color)
{
    int x;

    for (x = x1; x <= x2; x++)
        ptr_to_video_segment[(y * SCREEN_WIDTH) + x] = color;
}

This now eliminates function calls to a separate function.

You might ask, "Are function calls really that terrible? Should I write my programs without using functions at all?" Of course, the answer is no: "function elimination" should only be done using functions that will be called many times, in situations where speed is important. You most certainly don't want to un-structure your programs by writing them without any functions at all! So there's the catch: by putting the code of a repetitively-called function inside another, you can gain a small amount of speed, but you get many significant disadvantages:

  • your program becomes less readable
  • your program becomes less structured, maintainable and portable
  • you can change a function once, and all other functions that call it, of course, will use the "functionality" of that function. Putting the same or similar code in many places throughout your program means that, to change that functionality, you have to search through your program and change every occurrence of that code, which can become tedious and error-prone.
Let's examine our new HorizontalLine() function. Notice that there is a multiplication involved, and that that multiplication involves a value that remains constant, SCREEN_WIDTH. For that matter, y remains constant also. It would be more efficient to calculate this particular part of the expression, which remains constant throughout the for loop, outside of the loop, so it is done only once. We might write:
void HorizontalLine (int x1, int y, int x2, unsigned char color)
{
    int x;
    int y_times_screen_width;

    y_times_screen_width = y * SCREEN_WIDTH;
    for (x = x1; x <= x2; x++)
        ptr_to_video_segment[y_times_screen_width + x] = color;
}

That's quite a bit better. Multiplication and division are quite slow, at least compared to other operations such as addition and subtraction. That's why bit shifting, a much faster operation, is so often used to multiply and divide by powers of two.

That raises two questions: can we remove the multiplication entirely? And if we could, should we do so? The answer to the first question is yes, using a bit of trickery. For the latter question: optimizing this one statement, which will be executed once per function call, is not nearly as important as optimizing code that is executed many times, such as code within a loop. But, you may point out, the HorizontalLine() function itself could be called many times within a loop. So let's take a moment to optimize that one multiplication.

320 is not a power of two. But, if we play around with multiplying some numbers, we see that we can "split" a multiplication into several parts. For example, instead of 10 * 7, we can find 10 * 3, which is 30, and then 10 * 4, which is 40, and add the two "sub-products" to get 70. And 10 * 7 = 70. Try it with some other numbers -- split up one of the multiplicands, and then add the products. To use the same trick with 320, and to be efficient, we need to find two (or more) numbers that will add to 320 and are powers of two. 256 and 64 are just such numbers!

product = x * 320

product = (x * 256) + (x * 64)

And then, using the left-shifting trick:

product = (x << 8) + (x << 6)

Then, making the substitution into HorizontalLine():

void HorizontalLine (int x1, int y, int x2, unsigned char color)
{
    int x;
    int y_times_screen_width;

    y_times_screen_width = (y << 8) + (y << 6);
    for (x = x1; x <= x2; x++)
        ptr_to_video_segment[y_times_screen_width + x] = color;
}
This is a very slight improvement, and we could argue whether it was worth the extra effort or not. This is because this function now only works with video modes that have a screen width of 320 pixels. By taking out the SCREEN_WIDTH constant, we'd need to write another function for video modes with other screen widths. (Okay, so this isn't a big deal here -- other video modes use different methods of putting pixels, so we'd have to change the function anyway.)

Now we can be really picky. Notice the addition, the "y_times_screen_width + x" part, inside the for loop. It turns out that incrementation (adding one, by using "++" in C/C++) is just slightly faster than addition. So, for those who cherish pointer arithmetic, we could get:

void HorizontalLine (int x1, int y, int x2, unsigned char color)
{
    int x;
    char far *temp_ptr;

    temp_ptr = ptr_to_video_segment + (y << 8) + (y << 6) + x1;
    for (x = x1; x <= x2; x++)
        *(temp_ptr++) = color;
}

It's getting even uglier!

To get a significant speed improvement over this latest version of HorizontalLine(), you'd most likely need to use assembler. As we will see in the assembler chapters, there are particular 80x86 opcodes (such as "REP STOSB" or "REP STOSW", for the curious) which are very well suited for horizontal line drawing in Mode 13h.

One improvement to this function would be to check that x1 really is less than or equal to x2, and to swap them if they are not in order. Of course, this slows down the function somewhat, so you have to decide whether the function or the programmer using the function should do the error checking.

Vertical lines

Vertical lines are only slightly more complex to implement than horizontal lines. Here is my first shot at writing a VerticalLine() function:

void VerticalLine (int x, int y1, int y2, unsigned char color)
{
    int y;

    for (y = y1; y <= y2; y++)
        PutPixel (x, y, color);
}

Which, by using a bit of cut-and-paste, becomes:

void VerticalLine (int x, int y1, int y2, unsigned char color)
{
    int y;

    for (y = y1; y <= y2; y++)
        ptr_to_video_segment[(y * SCREEN_WIDTH) + x] = color;
}

Then, some of the optimizing tricks we used above yield the following improvement:

void VerticalLine (int x, int y1, int y2, unsigned char color)
{
    int y;
    char far *temp_ptr;

    temp_ptr = ptr_to_video_segment + (y1 << 8) + (y1 << 6) + x;
    for (y = y1; y <= y2; y++, temp_ptr += SCREEN_WIDTH)
        *temp_ptr = color;
}

Basically, instead of incrementing the pointer into video memory (which makes the pointer point to the next horizontal pixel), we're adding the width of the screen to that pointer (which makes the pointer point to the next row, in the same column).

Slanted lines

"Slanted lines" are lines that aren't horizontal or vertical. (I'm avoiding the term "diagonal", which might imply perfectly diagonal lines with slopes of 1 or -1.) The problem involved with plotting slanted lines is deciding which pixels in between the two endpoints should be considered part of the line.

Hopefully you remember the equation of a line from mathematics classes:

y = mx + b,

where x and y represent coordinates (column and row), m is the slope (the ratio of the amount of change of vertical units per horizontal unit; also referred to as "rise over run" or "delta x / delta y"), and b is the y-intercept (the position on the y-axis where the line intersects it).

You have to keep in mind the direction of the y-axis: in mathematics, the y-axis increases as it goes up; however, in our Mode 13h coordinate system, the y-axis increases as it goes down the screen. This means that slopes are reversed: a positive slope in mathematics is oriented like the forward slash ("/"), but with our coordinate system, a positive slope heads downward and to the right, like a backslash ("\").

We can simply use the equation of the line and plug in increasing values of x to get corresponding y coordinates. This was my first try:

void SlantedLine (int x1, int y1, int x2, int y2, unsigned char color)
{
    int x, temp;
    float y, slope, y_intercept;

    /* The for loop will count from x1 to x2, so swap the coordinates if
       they are not in the right order: */
    if (x1 > x2) {
        temp = x2;
        x2 = x1;
        x1 = temp;

        temp = y2;
        y2 = y1;
        y1 = temp;
    }

    /* Slope = (change in y) / (change in x) */
    slope = ((float) y2 - (float) y1) / ((float) x2 - (float) x1);
    y_intercept = (float) y1 - (slope * (float) x1);

    for (x = x1; x <= x2; x++) {
        y = ((float) x * slope) + y_intercept;
        PutPixel (x, (int) y, color);
    }
}
Notice that the y-intercept was calculated by first rearranging the equation of the line to...

b = y - mx

...and then substituting two coordinates that happen to be on the line into x and y. Both (x1, y1) and (x2, y2) are convenient, because they are the endpoints of the line.

But I made a mistake in writing the above SlantedLine() function: it only works for lines with slopes between 1 and -1. Why? Well, consider a line with a slope of, say, 0.125; this means that for every eight horizontal units, the line rises (I'll use the mathematical coordinate system for convenience) one vertical unit:

   y axis
(increasing)
    /|\
     |
     |                                    ********
     |                            ********
     |                    ********
     |            ********
     |    ********
     :
     :
        ...._______________________________________\  x axis (increasing)
                                                   /

So, if we step along the x axis, and use the equation of the line to get a matching y axis coordinate for each x coordinate, we find that the resulting line is "continuous"; that is, there are no breaks or gaps in the line.

But what about slopes greater than 1 (or less than -1)? Let's try 2. This is what we would like to get:

   y axis
(increasing)
    /|\
     |        *
     |        *
     |       *
     |       *
     |      *
     |      *
     |     *
     |     *
     |    *
     :    *
     :
        ...._______________________________________\  x axis (increasing)
                                                   /

But if we step along the x axis here, we can only get one y coordinate for each x coordinate, so we end up with something like this, which is not continuous:

   y axis
(increasing)
    /|\
     |        *
     |
     |       *
     |
     |      *
     |
     |     *
     |
     :    *
     :
        ...._______________________________________\  x axis (increasing)
                                                   /

So the above function is only good for lines that have the x axis as the major axis. The solution is to rearrange the equation of the line:

y = mx + b

mx = y - b

x = (y - b) / m

Now, given a y value, we can find the corresponding x value. Simply step along the y axis and find the matching x values for each y value.

To decide which axis we should step along, we need to determine which axis is the major axis. If we are given the coordinates of the line's endpoints, (x1, y1) and (x2, y2), we can find the horizontal distance using abs(x2 - x1) (abs() is the absolute-value function; in mathematics, we use a pair of vertical bars, like this: |x2 - x1|). The vertical distance can be found using abs(y2 - y1). Then, if the horizontal distance is greater, the x axis is the major axis; if the vertical distance is greater, the y axis is the major axis. Simply step along the major axis, find each corresponding coordinate using the line equation, and plot each point.

Here's my second version, which actually works:

void SlantedLine (int x1, int y1, int x2, int y2, unsigned char color)
{
    int delta_x, delta_y, int_x, int_y;
    float slope, float_x, float_y, y_intercept;

    delta_x = x2 - x1;
    delta_y = y2 - y1;

    if (delta_x == 0) {             /* Prevent a divide-by-zero error */
        VerticalLine (x1, y1, y2, color);
        return;
    }
    else if (delta_y == 0) {        /* HorizontalLine() is more efficient */
        HorizontalLine (x1, y1, x2, color);
        return;
    }

    /* Slope = (change in y) / (change in x) */
    slope = ((float) delta_y) / ((float) delta_x);
    y_intercept = (float) y1 - (slope * (float) x1);

    /* To use abs(), #include <stdlib.h> (or math.h) */
    if (abs(delta_x) >= abs(delta_y)) {
        /* x is the major axis: */
        if (x1 <= x2) {
            for (int_x = x1; int_x <= x2; int_x++) {
                float_y = ((float) int_x * slope) + y_intercept;
                PutPixel (int_x, (int) float_y, color);
            }
        }
        else {
            for (int_x = x2; int_x <= x1; int_x++) {
                float_y = ((float) int_x * slope) + y_intercept;
                PutPixel (int_x, (int) float_y, color);
            }
        }
    }
    else {
        /* y is the major axis: */
        if (y1 <= y2) {
            for (int_y = y1; int_y <= y2; int_y++) {
                float_x = ((float) int_y - y_intercept) / slope;
                PutPixel ((int) float_x, int_y, color);
            }
        }
        else {
            for (int_y = y2; int_y <= y1; int_y++) {
                float_x = ((float) int_y - y_intercept) / slope;
                PutPixel ((int) float_x, int_y, color);
            }
        }
    }
}

This function works, but it's incredibly slow. That's mainly because it uses floating point arithmetic. Floating point arithmetic is much, much slower than integer arithmetic, because floating point numbers are normally stored as a base and an exponent, and handling numbers that way involves more work for the processor. (Math coprocessors are another issue.) This function is also slow due to the multiplication operation (a floating-point multiplication, no less) inside the loop, as well as the call to the PutPixel() function. This function could be optimized in other ways, as well, but the resulting function would still be too slow.

For a faster line-drawing function, we need a process that avoids floating point arithmetic. We would like to use integer arithmetic, preferably with as few multiplications and divisions as possible. Fortunately, a clever computer scientist by the name of Bresenham developed a line-drawing algorithm that meets our needs.

Unfortunately, good information on Bresenham's algorithm is hard to find. It's easy to find implementations of the algorithm; I have four books and several on-disk articles that have source code examples of Bresenham line-drawing functions. But looking at source code doesn't help describe why the algorithm works, especially as the algorithm includes seemingly arbitrary expressions with no indication of how those expressions were arrived at. And, sadly, I am going to be guilty of doing the same thing here.

I'll describe here the general nature of the algorithm -- the basic idea behind it. Then I'll give a listing of the algorithm and some sample source code. But to get an actual understanding of how it works and where all of those expressions come from, I'd very strongly recommend working through the mathematical derivation described on pages 74 through 78 of "Computer Graphics: Principles and Practice (Second Edition in C)", by Foley, van Dam, Feiner and Hughes. (See the list of references to material at the end of this article.) Actually, they show the derivation of the Midpoint Line algorithm, which is essentially identical to Bresenham's line-drawing algorithm. I'd very much like to include the derivation here, but of course that would be a copyright violation. (Just as a side note, I can't recommend the terser derivation listed in the previous edition of that book, "Fundamentals of Interactive Computer Graphics", by Foley and van Dam (only), as I found it too difficult to follow.)

Bresenham's line-drawing algorithm is based on the concept of a decision variable, which keeps track of the error, or the distance between an actual point on a line and the pixel that best approximates the actual point's position.

   y-axis
(increasing)

    /|\  O         O         O         O         O <--- pixels
     |
     |                                           ******** <- "actual line"
     |                                   ********
     |   O         O         O   ******O*        O
     |                   ********
     |           ********
     :   ********
     :   O         O         O         O         O
       ....__________________________________________\  x axis (increasing)
                                                     /

For a x-major-axis line, with a (y-axis increasing as it goes up) slope between 0 and 1, such as the line in the above diagram, we step along the x axis. Using the decision variable, we determine whether the actual line passes closer to the pixel directly above the actual line or the pixel directly below it. If the lower pixel is selected, we update the decision variable, by adding a pre-calculated value to it, and then we go ahead to the next x coordinate. If the upper pixel is selected, we update the decision variable, by adding a different pre-calculated value to it, we increment the y position, and then we go ahead to the next x coordinate.

Here's the general algorithm in pseudo-code. This only works for lines in which x1 < x2, and that have (y-axis increasing as it goes down) slopes between 0 and 1; that is, lines that are sloped down and to the right (like a backslash: "\") less than 45 degrees:

Given coordinates (x1, y1) and (x2, y2) as the endpoints of the line:
Let x equal x1
Let y equal y1
Let delta_x equal x2 - x1
Let delta_y equal y2 - y1
Let d (the decision variable) equal (2 * delta_y) - delta_x
Let incr_same_y equal 2 * delta_y
Let incr_new_y equal 2 * (delta_y - delta_x)

For x = x1 to x2
Begin
    If (d > 0) then
    Begin
        Increment y
        Let d equal d + incr_new_y
    End
    Else
    Begin
        Let d equal d + incr_same_y
    End

    Draw a pixel at (x, y)
End

It's relatively simple to adapt this for other cases: for example, for lines in which x1 < x2, but with (y-axis increases as it goes down) slopes between -1 and 0, you simply change the "Increment y" to "Decrement y". When the x axis is still the major axis, but x1 > x2, you simply step backwards along x (decrement x in the for loop). When the y axis is the major axis, you step either forward or backwards along the y-axis, and either increment or decrement x; you have to take into account whether y1 > y2 or y1 < y2, and whether the slope is between 1 and infinity or -1 and negative infinity. There are eight different cases in all, one for each octant. You can implement the algorithm several different ways: you could handle each of the eight cases separately, or you could convert four of the cases to the other four cases by swapping the endpoint variables so that, for the y-major-axis cases, y1 is always less than y2, and for the x-major-axis cases, x1 is always less than x2. If you want to be clever, you can reduce the number of cases further if you're willing to create extra variables.

Here's my implementation of Bresenham's line-drawing algorithm. I've arbitrarily decided to implement it using four cases.

void Line (int x1, int y1, int x2, int y2, unsigned char color)
{
    int x, y, delta_x, delta_y, d, incr_same, incr_new, temp;

    delta_x = x2 - x1;
    delta_y = y2 - y1;

    if (delta_x == 0) {
        VerticalLine (x1, y1, y2, color);     /* For efficiency */
        return;
    } else if (delta_y == 0) {
        HorizontalLine (x1, y1, x2, color);   /* For efficiency */
        return;
    }

    if (abs(delta_x) >= abs(delta_y)) {       /* if x is the major axis: */
        if (x2 < x1) {                /* if coordinates are out of order */
            temp = x2;
            x2 = x1;
            x1 = temp;
            delta_x = -delta_x;

            temp = y2;
            y2 = y1;
            y1 = temp;
            delta_y = -delta_y;
        }

        if (y2 > y1) {              /* when it is decided to change y, y
                                                   should be incremented */
            incr_same = delta_y << 1;
            d = incr_same - delta_x;
            incr_new = (delta_y - delta_x) << 1;

            y = y1;
            for (x = x1; x <= x2; x++) {
                if (d > 0) {
                    y++;                      /* increment y here */
                    d += incr_new;
                }
                else
                    d += incr_same;
                PutPixel (x, y, color);
            }
        }
        else {                      /* when it is decided to change y, y
                                                   should be decremented */
            incr_same = delta_y << 1;
            d = incr_same + delta_x;
            incr_new = (delta_y + delta_x) << 1;

            y = y1;
            for (x = x1; x <= x2; x++) {
                if (d < 0) {
                    y--;                      /* decrement y here */
                    d += incr_new;
                }
                else
                    d += incr_same;
                PutPixel (x, y, color);
            }
        }
    }
    else {                                    /* if y is the major axis: */
        if (y2 < y1) {                /* if coordinates are out of order */
            temp = y2;
            y2 = y1;
            y1 = temp;
            delta_y = -delta_y;

            temp = x2;
            x2 = x1;
            x1 = temp;
            delta_x = -delta_x;
        }

        if (x2 > x1) {              /* when it is decided to change x, x
                                                   should be incremented */
            incr_same = delta_x << 1;
            d = incr_same - delta_y;
            incr_new = (delta_x - delta_y) << 1;

            x = x1;
            for (y = y1; y <= y2; y++) {
                if (d > 0) {
                    x++;                        /* increment x here */
                    d += incr_new;
                }
                else
                    d += incr_same;
                PutPixel (x, y, color);
            }
        }
        else {                      /* when it is decided to change x, x
                                                   should be decremented */
            incr_same = delta_x << 1;
            d = incr_same + delta_y;
            incr_new = (delta_x + delta_y) << 1;

            x = x1;
            for (y = y1; y <= y2; y++) {
                if (d < 0) {
                    x--;                      /* decrement x here */
                    d += incr_new;
                }
                else
                    d += incr_same;
                PutPixel (x, y, color);
            }
        }
    }
}

This isn't the most heavily optimized implementation. You could substitute in the contents of function PutPixel() everywhere that function is called, for example. Actually, the eight-case implementation would have the potential to be the fastest, as no extra manipulations (swapping coordinates, etc.) would have to be done. And, as always, re-writing it in assembler can increase the speed.

Just a minor note: I've used the left bit shift operator (<<) to multiply signed values by two. This works, if you try playing around with shifting two's complement binary numbers to the left. But shifting two's complement binary numbers to the right won't work: the sign bit will get dragged to the right with the rest of the digits. There's no remedy that I know of in C, but in the assembler chapters we'll discover a solution.

So, before we leave this topic, I'd like to again recommend working through the derivation in the previously mentioned textbook (see the list of referenced materials at the end of this chapter). Then, once you see the logic behind the one case that they present, you can fairly easily re-work it to figure out the rest of the eight cases.

Boxes

A box is a hollow rectangle, composed of two horizontal lines and two vertical lines. A box-drawing function is easy to implement, especially if we use our VerticalLine() and HorizontalLine() functions.

void Box (int x1, int y1, int x2, int y2, unsigned char color)
{
    HorizontalLine (x1, y1, x2, color);
    HorizontalLine (x1, y2, x2, color);
    VerticalLine (x1, y1, y2, color);
    VerticalLine (x2, y1, y2, color);
}

This isn't bad, but we can do better. When we call HorizontalLine() the first time, it operates a for loop. When we call HorizontalLine() the second time, it operates the same for loop again, counting through the same values. Instead, in Box(), we could first use one for loop, and in each iteration, we could plot pixels for both horizontal lines. We could then replace the calls to VerticalLine() with another for loop, and in each iteration of that loop, we would plot pixels for both vertical lines.

And, to be efficient, we want to avoid as much recalculation as possible. To avoid multiplications, we could use one pointer for the first horizontal line, and a second for the second horizontal line. We would calculate the intial positions for each, and then simply increment both of the pointers as we draw the horizontal lines. We could then re-use those pointers for the vertical lines, and we would add SCREEN_WIDTH to both pointers to draw the vertical lines.

void Box (int x1, int y1, int x2, int y2, unsigned char color)
{
    char far *ptr_1, *ptr_2;
    int x, y, temp;

    /* Draw horizontal lines: */
    ptr_1 = ptr_to_video_segment + (y1 << 8) + (y1 << 6) + x1;
    ptr_2 = ptr_to_video_segment + (y2 << 8) + (y2 << 6) + x1;

    for (x = x1; x <= x2; x++) {
        *(ptr_1++) = color;
        *(ptr_2++) = color;
    }

    /* Draw vertical lines: */
    temp = (y1 << 8) + (y1 << 6);
    ptr_1 = ptr_to_video_segment + temp + x1;
    ptr_2 = ptr_to_video_segment + temp + x2;

    for (y = y1; y <= y2; y++) {
        *ptr_1 = color;
        *ptr_2 = color;
        ptr_1 += SCREEN_WIDTH;
        ptr_2 += SCREEN_WIDTH;
    }
}

I was rather lazy and did not check that the coordinates were in order; that is, x1 < x2 and y1 < y2.

Here's another, very similar, method: we could use one pointer, and calculate the initial position of, say, the top left corner of the box. To draw the vertical lines, we would first plot a pixel at this first location, and then add a pre-calculated value, perhaps called x_incr1, to the pointer. If x_incr1 = x2 - x1, then the pointer would be moved to the corresponding point on the second line, where the next pixel would be plotted. Then, to get to the first line, but on the next row, we would add another pre-calculated value, x_incr2 = SCREEN_WIDTH - x_incr1, to the pointer, and then repeat. The same can be done with the horizontal lines, but it takes a little more effort to calculate the values to increment the pointer by. Here's a diagram that hopefully helps to explain how the x_incr1 and x_incr2 expressions were arrived at:

                  x1                         x2
Screen:  _________|__________________________|____________
        /                 |                               \
       |                 \|/                               |
   y1 -|          ****************************             |
       |          *     /|\                  *             |
       |          */_____|__________________\*/____________|
       |_________\*\     |         x_incr1  /*\   x_incr2  |
       |         /*      |y_incr1            *             |
       |          *     \|/                  *             |
   y2 -|          ****************************             |
       |                /|\                                |
       |                 |y_incr2                          |
        \________________|________________________________/

Bars

A filled rectangle is sometimes called a bar. There are several ways to draw a bar, but thinking of a filled rectangle as a set of lines bunched together is convenient, and an implementation of Bar() that draws a set of horizontal lines turns out to be faster than most other methods.

Let's improve on this strategy. Instead of calling HorizontalLine() within a loop, we can put that function's code into Bar(). Then, we can incorporate the technique suggested in the Boxes section. We draw a horizontal line by repeatedly incrementing a pointer, and then when we need to move to the starting position on the next line, we add a value to the pointer; in the diagram in the Boxes section, that variable is x_incr2 = SCREEN_WIDTH - (x2 - x1). But in the Bar() function, where I'll call it x_incr, it's just slightly different. It's x_incr = SCREEN_WIDTH - (x2 - x1) - 1, and the "- 1" is due to the fact that, in the horizontal-line-drawing for loop, the pointer is incremented, even in the last case. So after a horizontal line is drawn, the pointer is left pointing at the pixel immediately to the right of the line. The "- 1" is used to take this into account. It's easier to see if you examine and trace through the sample function:

void Bar (int x1, int y1, int x2, int y2, unsigned char color)
{
    char far *ptr;
    int x_incr, x, y;

    ptr = ptr_to_video_segment + (y1 << 8) + (y1 << 6) + x1;
    x_incr = SCREEN_WIDTH - (x2 - x1) - 1;

    for (y = y1; y <= y2; y++) {
        for (x = x1; x <= x2; x++)
            *(ptr++) = color;
        ptr += x_incr;
    }
}

Note that this function, like many of the previous ones, does not check that the coordinates are in the correct order.

Clearing the screen

Now that we have a functioning Bar() routine, you can use it to clear the screen in whatever color you like. You might want to construct a very short function, perhaps ClearScreen(), that calls Bar() to clear the screen.

Or, if you want to clear the screen to color 0, which is black, just call the function that sets Mode 13h! Admittedly, this isn't the best way: I don't know if it's guaranteed to work on all systems. And the speed of the mode-changing interrupt service may be questionable, as it has to set many of the VGA's registers, and then clear the screen.

Some quick suggestions

I'd recommend against simply cutting and pasting the above functions into another file, compiling them, and then either forgetting about them or using them without considering how they work. Take a few minutes and type them in (or write them down) -- this kind of activity is supposed to help you remember and understand whatever material you're trying to learn. Once you feel comfortable with the concepts behind one of the functions presented here, put away this article and write your own version of that function. Before long, you'll have your very own graphics library!

The other point I wish to mention regards optimization. There's an important piece of advice: no-one should ever claim that they have totally optimized some routine. Always keep in mind that there are always alternate methods of doing things. So, for example, it would be incredibly foolish for me to suggest that any of the sample functions presented here use the best methods of performing their respective tasks, or that they are the fastest such functions, or that they even come close. For instance, there is a very slightly faster method of drawing horizontal lines, and hence filled rectangles, although it works only in certain cases (and we'll see it in the assembler chapters). And then, it would still be ridiculous to claim that that routine could not be optimized further.

Summary

In this chapter, we've seen some methods for drawing horizontal, vertical, and slanted lines, and boxes and bars, using Mode 13h. We've also used some basic optimization strategies to improve the speed of the functions we have written.

In the next chapter, "VGA Mode 13h Graphics Primitives, Part 2", we'll see some methods for drawing circles, ellipses, and filled circles and ellipses. We'll also experiment briefly with drawing some strange curves.

References to material

Foley, James D., and Andries van Dam, Steven K. Feiner, John F. Hughes. "Computer Graphics: Principles and Practice (Second Edition in C)". USA: Addison-Wesley, 1990, 1996. ISBN: 0-201-84840-6.

(This is the graphics textbook that everyone considers the standard. For Bresenham's line-drawing algorithm or the Midpoint line algorithm, see pages 74 through 78.)

  

Copyright 1997, Kevin Matz, All Rights Reserved. Last revision date: Wed, Jun. 04, 1997.

Go back

A project