VGA Mode 13h Graphics Primitives, Part 2

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

Prerequisites:

  • Chapter 8: VGA Mode 13h Graphics Primitives, Part 1
  • some basic trigonometry

       
This chapter will briefly consider some methods for drawing circles and ellipses. We'll also experiment briefly with drawing some strange curves.

Circles

Before we begin, let me mention that "mathematically-accurate" circles drawn in Mode 13h will look distorted: they will appear to be stretched vertically. This is due to the aspect ratio of the video mode: there are 320 pixels horizontally by 200 pixels vertically. The ratios of pixels per unit distance for the horizontal and vertical directions are not equal, and so Mode 13h pixels are just slightly taller than they are wide. Try drawing a square using the Rectangle() function from the last chapter -- unless the dials on your monitor are a bit mis-adjusted, the "square" will look like a rectangle with a height that is greater than its width.

Recall from mathematics classes the equation of a circle that is centered at the origin:

 2     2     2
x  +  y  =  r  ,

where (x, y) represent coordinates on the circle, and the constant r is the radius of the circle.

Could we rewrite this equation, so that we could plug in values for two of the variables and get a result for the third? Yes, we certainly could, but we would run into a problem similar to that we experienced with the floating-point slanted line drawing routine from the previous chapter. If we were solving for y, the parts of the circle that have steep slopes would develop gaps in the line. The solution is to rewrite the equation so that we can solve it to get a result for x instead of y. Over what ranges of x and y should each version of the equation be used? When the slope of the tangent to the circle is between 0 and 1, or -1 and 0, the solve-for-y version should be used; when the slope of the tangent is between 1 and infinity, or negative infinity and -1, the solve-for-x version should be used.

Fine, but how do we determine the coordinates where the slope is either 1 or -1, so we can set up our loops? Let's use trigonometry. The following is a terribly misshapen sketch of a circle (the points of the circle are not mathematically correct; this is for illustration purposes only):

                             *********
                         ****    |    ****
                       **        |        *P   (x, y)
                      *          |        /|*
                     *           |      /  | *
                     *           |    /    | *
                    *            |  /_45deg|  *
                    *            |/___)____|__*
                    *                         *
                     *                       *
                     *                       *
                      *                     *
                       **                 **
                         ****         ****
                             *********

By drawing a 45 degree line from the the center of the circle (the origin) to the edge of the circle, as shown in the above diagram, we locate a point P on the circle where the line has a slope of -1. Notice that I've also drawn a vertical line down from the point P, so a triangle is formed.

Now that we have a triangle, we can do some basic trigonometry. We know the radius of the circle is r, so the hypotenuse of our triangle is r. Given that we have a 45 degree angle, which I'll arbitrarily call "a" (because my theta key is broken), we can find the lengths of the opposite and adjacent sides:

                     . <--- point P
      hypotenuse:   /|
               r  /  |
                /    |  opposite side:
              /_ a   |  y (vertical coordinate of point P)
            /___)____|
          adjacent side:
          x (horizontal coordinate of point P)

SIN(a) = opposite / hypotenuse = y / r; then, y = SIN(a) * r

COS(a) = adjacent / hypotenuse = x / r; then, x = COS(a) * r

Aha! Now we have a formula for finding the horizontal component x, and a formula for finding the vertical component y, given an angle and the radius of the circle! Now, in C, you can #include <math.h> to gain access to trigonometric functions such as sin() and cos(). Be careful: these functions assume radians are used instead of degrees. So, to find the coordinates we are looking for, we can first convert our 45 degree value to radians:

    45 deg         a rad
  ---------  =  ----------;  a = 45 * pi / 180
   180 deg        pi rad

Then, if we have variables a, x, and y of type float:

a = 45 * M_PI / 180;            /* M_PI is a constant (of type float),
                                   defined in math.h */
y = sin(a) * r;                 /* y coordinate */
x = cos(a) * r;                 /* x coordinate */

Now we have one coordinate out of four. To get the other three, you could use angles of 135, 225, and 315 degrees, or, you could use symmetry. Notice that one of the other coordinates we are looking for is directly below the one we found in the first quadrant; we can simply negate y and keep x the same to get the coordinate in the fourth quadrant. For the second quadrant's coordinate, just negate x, and for the third quadrant, negate both x and y.

I'm not going to provide an sample implementation for this method. If you would like to write a Circle() function using this method, by all means, go ahead; it's a good exercise. But, as you might have guessed, this method is not as efficient as we'd like. Let's try another approach.

Could we use the "y = sin(a) * r" and "x = cos(a) * r" formulas we developed above? Indeed we could: we could count through all of the degrees in the circle, from 0 to 360 (or 359), use the formulas to get (x, y) coordinate pairs, and plot the points.

This looks very nice and convenient, but there's a disadvantage. If we step through the degrees from 0 to 359, we will end up plotting 360 points, no matter what size the circle is. If we have a circle with a radius of, say, 10 pixels, we will end up re-plotting many pixels unnecessarily. And if we draw a circle with a radius of, say, 100, we'll get gaps in the circle again. But with a bit of thought, we can solve this problem: recall that the circumference of a circle can be found using 2 * pi * r. If we use an formula that is proportional to the C = 2 * pi * r formula, we can find a reasonable value for the number of pixels to plot. For safety, we should slightly over-estimate the number of pixels required. From my experimentation, I've found that "number_of_steps = (int) (2.1 * M_PI * r)" works adequately well. Then, you need to divide the 360 degrees, or the equivalent 2 * pi radians, of the circle by number_of_steps, to get the value by which the angles for each iteration differ. Observe:

/* Add this line to the top of your program: */
#include <math.h>

void FloatingPointCircle (int x, int y, int r, unsigned char color)
{
    float angle, angle_increment;
    int number_of_steps;

    number_of_steps = (int) (2.1 * M_PI * r);
    angle_increment = 2 * M_PI / number_of_steps;

    for (angle = 0; angle <= 2 * M_PI; angle += angle_increment)
        PutPixel (cos(angle) * r + x, sin(angle) * r + y, color);
}

If you typed in and tested the above function, you were probably able to watch the circle being drawn. For a graphics primitive that we might possibly want to use dozens of times per second, it's too slow. This sluggishness is due, of course, to the use of floating point calculations. It is slow due to the use of the sin() and cos() functions, which happen to be notoriously slow.

There is a way to avoid calling the sin() and cos() functions, and that is to construct what is often called a lookup table: an array storing values of a trigonometric function over range of angles. Most often, two arrays are created, one holding a set of values for sin(), and one holding a set of values for cos(). (Alternately, if you have an obsession with trigonometric identities, you could create one array for one function.) Then, instead of calculating a sine or cosine with sin() or cos(), you simply look up the value in the table. In the chapter dealing with optimization, we'll explore this topic much further.

And for another optimization technique, we can take advantage of the circle's symmetry again. Notice in the following diagram how a total of eight coordinates, one for each octant, can be obtained from one set of points on the circle:

                     (-3, 10)         (3, 10)
                 octant 3    *********     octant 2
                         ***X    |    X***
                       **        |        **
                      * \        |        / *
                     *    \      |      /    *  octant 1
           (-10, 3)  X      \    |    /      X  (10, 3)
           octant 4 *         \  |  /         *
                    *___________\|/___________*
                    *           /|\           *
          (-10, -3)  X        /  |  \        X  (10, -3)
           octant 5  *      /    |    \      *  octant 8
                      *   /      |      \   *
                       **        |        **
                         ***X    |    X***
                             *********
                    (-3, -10)         (3, -10)
                     octant 6         octant 7

Again, note that this circle is a rough sketch. You might want to try sketching various-sized circles on paper and approximating the coordinates to see how it works. So, now we only need to calculate points for one octant, and we can plot the other seven corresponding points just by adding and subtracting the x and y coordinate values from the center point.

But even with these improvements, is there a faster way to draw circles? Is there an equivalent to Bresenham's line-drawing algorithm for circles? Yes, Bresenham also developed a similar and equally clever circle-drawing algorithm, and it uses integers and avoids sine and cosine calculations altogether!

I'll show the algorithm, which works on the same principle as the line-drawing algorithm. I'd very much like to explain how it works, but to do so I would have to show the mathematical derivation, and then I would probably be partially guilty of plagiarizing material from the following source: pages 81 through 87 of "Computer Graphics, Principles and Practice (Second Edition in C)", by Foley, van Dam, Feiner, and Hughes. (See the list of referenced materials at the end of this article.) I highly recommend reading or working through the derivation to see how the values are determined.

Actually, I'll list my version of the algorithm, in pseudocode. It's slightly different from that given in the Foley and van Dam book: if you superimpose a circle drawn with one with this algorithm on top of a circle drawn with the other algorithm (with the same center coordinates and radii, but with a different color), you'll find that my version differs by one coordinate per octant, so eight pixels are different. The difference between the two circles is really not noticeable at all.

Just like the version given in the book, this version also uses the "second-order differences" technique given in Foley & van Dam, and it makes use of the eight-way symmetry trick, so it only has to run through one octant (octant 2) of the circle:

Given the integer coordinates (x, y) for the center of the circle, the integer radius radius, and the color color:

Let x_position equal -1
Let y_position equal the radius
Let d (the decision variable) equal 1 - radius
Let delta_e (the "e" means "east") equal -1
Let delta_se ("se" for "southeast") equal -2 * radius + 3

while y_position > x_position:
begin
    add 2 to delta_e
    increment x_position

    if d < 0, then
    begin
        add delta_e to d
        add 2 to delta_se
    end
    else
    begin
        add delta_se to d
        add 4 to delta_se
        decrement y_position
    end

    PutPixel (x + x_position, y + y_position, color);
    PutPixel (x + y_position, y + x_position, color);
    PutPixel (x + y_position, y - x_position, color);
    PutPixel (x + x_position, y - y_position, color);

    PutPixel (x - x_position, y - y_position, color);
    PutPixel (x - y_position, y - x_position, color);
    PutPixel (x - y_position, y + x_position, color);
    PutPixel (x - x_position, y + y_position, color);
end

And my implementation is just a translation of the above algorithm into C:

void Circle (int x, int y, int radius, unsigned char color)
{
    /* Uses my (slight) alteration of the midpoint line algorithm. */

    int x_position, y_position, d, delta_e, delta_se;

    x_position = -1;
    y_position = radius;
    d = 1 - radius;
    delta_e = -1;
    delta_se = (-radius << 1) + 3;

    while (y_position > x_position) {
        delta_e += 2;
        x_position++;

        if (d < 0) {
            d += delta_e;
            delta_se += 2;
        }
        else {
            d += delta_se;
            delta_se += 4;
            y_position--;
        }

        PutPixel (x + x_position, y + y_position, color);
        PutPixel (x + y_position, y + x_position, color);
        PutPixel (x + y_position, y - x_position, color);
        PutPixel (x + x_position, y - y_position, color);

        PutPixel (x - x_position, y - y_position, color);
        PutPixel (x - y_position, y - x_position, color);
        PutPixel (x - y_position, y + x_position, color);
        PutPixel (x - x_position, y + y_position, color);
    }
}

Ellipses

Research in progress -- this section will be completed later. It will most likely refer you to pages 88 to 91 of Foley and van Dam; see the list of referenced materials at the end of this article.

Filled circles and ellipses

Drawing a filled circle or ellipse can be done efficiently by using symmetry again. The following diagram shows how you could fill a circle with horizontal lines if (2, 15) is one point on the circle, and the circle is centered at (0, 0):

                             *********
                         ****         ****
                       **                 **
                      *                     *
                     *                       *
          (-15, 2)   X***********************X   (15, 2)
                    *                         *
                    *                         *
                    *                         *
         (-15, -2)   X***********************X   (15, -2)
                     *                       *
                      *                     *
                       **                 **
                         ****         ****
                             *********

Just substitute two calls to HorizontalLine() for the set of PutPixel() calls in the Circle() function above. You could also use vertical lines, but horizontal lines are faster.

Strange and zany curves

You can generate some odd-shaped curves by letting either the x coordinate be determined with a sine or cosine function and letting the y coordinate be determined with the other. If you use a loop, and repeatedly change the angle inputs to the sin() or cos() parts of the functions, you can generate a set of points in curved and twisted shapes. Admittedly, these curves are not really graphics primitives. But here's one suggestion for their use: the set of points generated could be used for determining the path of travel for an animated object. (We'll discuss animation in another chapter.)

This function will draw a curve that looks vaguely Lissajous-like:

void DrawLissajousLikeCurve ()
{
    float sin_angle      = 0;
    float cos_angle      = 0;

    float sin_incr       = 0.075;
    float cos_incr       = 0.11;
    /* Or try:
    float sin_incr       = 0.14;
    float cos_incr       = 0.081;
    Or:
    float sin_incr       = 0.12;
    float cos_incr       = 0.09; */

    int x, y, count;
    int old_x            = 160;
    int old_y            = 100 + 95;

    for (count = 0; count <= 2000; count++) {
        x = 160 + 155 * sin(sin_angle);
        y = 100 + 95 * cos(cos_angle);
        Line (old_x, old_y, x, y, 9);

        sin_angle += sin_incr;
        cos_angle += cos_incr;

        old_x = x;
        old_y = y;
    }
}

Or, try running this one:

void DrawBizarreCurve ()
{
    float sin_angle      = 3.5;
    float cos_angle      = -1.5;
    float sin_incr       = 0.00012;
    float cos_incr       = 0.00047;
    float cos_incr_incr  = 0.00784;
    int x, y, count;
    int old_x            = 160;
    int old_y            = 100;

    for (count = 0; count <= 200; count++) {
        x = 160 + 155 * sin(sin_angle);
        y = 100 + 95 * cos(cos_angle);
        Line (old_x, old_y, x, y, 10);

        /* Modify sin_angle and cos_angle using some arbitrary functions: */
        sin_angle += 0.008 * sin(cos_angle - sin_angle) * cos_angle +
            sin_incr;
        cos_incr_incr += 0.009 * sin(sin_angle) + cos_incr;
        cos_angle += cos_incr_incr;

        old_x = x;
        old_y = y;
    }
}

This draws part of a rather silly-looking curve. The numbers and formulas in the above function are all arbitrary. You can play around with different initial values and different angle-calculating formulas -- hopefully you'll generate curves that are nicer-looking than this one. But this curve, or another curve generated with the same techniques, could be used to represent, say, the path that an enemy spaceship should follow in some Space-Invaders-type game.

Summary

This chapter has briefly discussed different methods for plotting circles, ellipses, and filled circles and ellipses. We've also seen a basic method for drawing occassionally zany 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.

(For circles, see pages 81 through 87. For ellipses, see pages 88 to 91.)

  

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

[Go back]

A project