Driving south from Carmel, California, along the wild, vertical cliffs of the Big Sur coastline, you pass a sign saying "Curves Next 67 Miles." A couple of hours and 67 miles later, you come to another sign saying "Curves Next 42 Miles." I guess some bureaucrat figured that 67 miles' worth of bad news was all your average motorist could handle at one time.
The drive through Big Sur is one of the most spectacular collections of curves in the world. In one respect, however, there's nothing unusual about it. Nearly everything in nature consists of curves. Look around. Just about the only straight lines you see are man-made.
The reason we've concentrated so far on straight lines in computer graphics is that they're easy to deal with and easy to understand. However, if graphics is to depict real-world objects it has to draw curves.
This is a difficult subject. Whole careers in computer science are devoted to the investigation of curves. So I'll be more honest than that nameless bureaucrat and tell you up front that there are a full 109 miles of curves ahead. However, we're going to take them the same way most people travel through Big Sur: In stages, with stops along the way.
We begin this month with two relatively simple curves that can be used to depict most rounded objects. The first is the ellipse, which can also draw a circle. The other is the conic spline, a remarkably supple object forming an arc. The road through Big Sur can be likened to a connected string of conic splines. In due course later, we'll consider cubic and Bezier splines, which are useful for concisely expressing complex curves in two and three dimensions. But first let's do the easier stuff.
Remember Bresenham? He's the guy we talked about in March, who invented a way to draw straight lines efficiently. Well, Bresenham didn't stop there to rest on his laurels. He went on to figure out how to draw ellipses without using floating point arithmetic. If you want a good exposition of the Bresenham method, see Algorithms 14 and 15 in James Blinn's article "How Many Ways Can You Draw a Circle?" (DDJ, September 1997). That article will also give you an insight into the complexities of even something as apparently simple as a circle.
The easiest way to make a circle is to rely on classical trigonometry. Given any angle, you find the corresponding point on the circle as follows:
The problem is that it's computationally intensive. The sine and cosine are periodic floating point functions that take a lot of resources (that is, time) to calculate. It wouldn't matter much if every computer was equipped with floating point hardware such as an '87 chip. However, few are, relying instead on time-hungry floating point emulation in software. Integer operations are much faster, and that's why Bresenham and others have quested for better methods.
With so many learned folks studying the problem, it's inevitable that variants on the Bresenham algorithm have appeared. The one we discuss here is called the midpoint algorithm. Wilton's PROGRAMMER'S GUIDE TO PC & PS/2 VIDEO SYSTEMS (1987, Microsoft Press) devotes most of Chapter 7 to this algorithm, so I won't go into much depth; if you're serious about graphics, get this book.
In nature, an ellipse is a circle elongated in some direction. To simplify matters, the Bresenham algorithm and its derivatives impose a limit: An ellipse can be elongated either horizontally or vertically, but not on the diagonal. (The conic splines discussed later remove this restriction.) If we can describe an ellipse as a stretched circle, then it's also fair to say that a circle is an ellipse in which both axes have the same length. That's why the method works for both true circles and ellipses, and why the terms are interchangeable.
The midpoint algorithm assumes that we start at point {0, y} and proceed through one quadrant, or 90 degrees of angular motion, to point {x, 0} (where y is the vertical semiaxis and x is the horizontal). In other words, it only worries about the upper-right quadrant of the ellipse. Corresponding points for the other three quadrants are found by adding to and subtracting from the center coordinates.
As the curve forms the exact edge advances, moving among and between pixel positions on the raster display, just like a slanting straight line. To draw a reasonably accurate representation, then, it's necessary to find out which fixed pixel is closest to the real curve at any given point. We could do this in the classic sine/cosine method by rounding the results of the calculations. To save that overhead, the Bresenham algorithm uses a decision variable called, by convention, d.
In general, if d is positive, then the curve lies below the midpoint between two vertically adjacent pixels, so the pixel below is selected. Otherwise the pixel above is closer. When the curve has advanced through half its arc (first octant) the tendency of motion becomes more downward than rightward. Thus the algorithm switches its orientation to select between horizontally adjacent pixels. A negative value for d means that the nearer pixel is outside the ellipse. The algorithm steps on a pixel-by-pixel basis, assuring an unbroken curve on the display. (Gaps sometimes occur using the "pure" Bresenham method.) The first octant advances the X in each iteration and selects the nearest Y. The second octant advances by Y and picks the appropriate X. The value of d changes each time by a pair of values called dx and dy by Wilton. The ellipse( ) function implementing this algorithm (Listing One) refers to them as xd and yd to avoid conflict with the virtual coordinate functions.
The values of xd and yd, using the function's names, are updated at each step by values that remain constant for the duration of the call. These constants reflect the rate of change in the curve, taking into account the tension between the X and Y semiaxes. Thus, xd and yd maintain a running total of the effects of angular motion along the curving path. The value of d is controlled by applying xd and yd, and so the sign of d selects the nearest pixel to each successive point.
Because the polynomial constants of angular motion are computed outside the loop and all values are 16- or 32-bit integers, the midpoint algorithm is efficient while drawing a smooth, unbroken, and accurate representation of the ellipse.
Want to see? First compile ELLIPSE.C and add it to your copy of GRAFIX.LIB with the command
Next, add the two prototypes from Listing Twoto GRAFIX.H. And then compile, link, and run CIRCLES.C from Listing Three. It draws a true circle and two ellipses.
Graphics literature sometimes explains that the term spline derives from the loftsman's spline, a piece of thin flexible material used to round inside edges. The analogy is lost on me inasmuch as I don't know what a loftsman does, nor do I care. A more useful analogy is to the fanciful curlicued French curves used by draftsmen (which is perhaps as meaningless to you). At any rate, spline is a term often used in computer graphics to mean an open curve.
There are several kinds of splines. The simplest is the conic spline, so called because it exists inside a triangular outline (or "hull"). Conceptually, the hull is a V-shaped set of three points. The curve itself goes between the two end points of the V. As it crosses the open space, the intersection of the hull's two sides -- the point of the V -- attracts the curve, causing it to bend inward. The amount of curvature depends on the depth of the enclosing cone.
Figure 1 illustrates a couple of conic splines. Note that the points where the curve meets the sides of the cone are called knots, and the attractor is called the control point. As you'll see shortly, the orientation of one of the sides doesn't have to be horizontal despite what the drawings suggest.
The curve in Figure 1a bends through more than 90 degrees, while that in Figure 1b falls somewhat short of a quarter-circle. Nevertheless, both curves represent one quadrant of an ellipse. Figure 2 shows how. Consequently, the conic spline isn't really attracted to its control point, but is instead rotating around the ellipse's center. In doing so it travels between the opposite corners of a parallelogram completed by the center and control point.
So, why not just use the midpoint algorithm to plot a conic spline, drawing only the affected quadrant? Because the ellipses defining a spline don't necessarily have vertical and horizontal axes. Remember, Bresenham imposes that as a condition on his ellipses. We could draw conic splines with the midpoint method, but the sides would always have to be at perpendicular angles. Thus, we couldn't draw the curves in Figure 1.
The spline in Figure 1a illustrates the problem. Two-thirds of the way between Knots A and B, the curve bends beyond 90 degrees and begins moving back in the opposite horizontal direction. It started out going right, and now it's going left. If we rotated the whole thing, a similar problem would exist with going first up, then down, or vice versa. The midpoint algorithm simply can't handle this because it expects the axes to be orthogonal.
We need a more capable algorithm. That's what the arc() function in ARC.C (Listing Four) provides. This algorithm uses fixed point arithmetic to approximate floating point without the overhead. The fixed point values are long integers with a fractional value in the lower 16 bits. This accounts for the left shifts when setting up the control values, and also for the constant HALFPI. The arc sweeps through a quarter-turn, or PI/2 radians, so we calculate HALFPI as (3.1415927 / 2) << 16, which works out to 102,944.
The whole idea of this algorithm is somewhat like that of Bresenham, though it doesn't look like it. The values vx and vy give offsets for the current point relative to the center of the ellipse (x0 and y0). The ux and uy variables accumulate angular motion as the curve progresses. Because vx, vy, and ux, uy interact with each other, in effect updating each others values at the bottom of the loop, the angular motion to the right (when drawing Figure 1a) gradually slows and eventually backtracks.
Everything depends on the pixel density variable called "den," which provides a power of 2 by which to multiply and divide the control values. The sense of this rests upon the effect of shifting an integer. Every time you shift one bit to the right, you divide by 2. Three shifts to the right is division by 8, four is division by 16, and so on. Multiplication by a power of 2 similarly occurs when shifting left.
The algorithm draws a predictable number of pixels depending on the value of den. When den is 10, it draws 804 pixels between the knots. The number of pixels decreases by half each time den decrements by one. In computing the pixel density factor, then, the algorithm determines approximately how far the curve has to travel, and assigns the appropriate power of 2 to control its motion.
The exact number of pixels needed to draw an unbroken curve depends on the depth of the cone and the distance between knots. The algorithm might attempt to write a pixel in the same position more than once, so the loop tracks the previous position and only allows a write when the new position is different; the comparison is computationally cheaper than a rewrite.
See, I told you curves aren't easy. But because the conic algorithm uses only integers with fractional values in the lower 16 bits, it draws splines efficiently.
Compile ARC.C, then put it into the library with
Now you're ready to see some conic splines in action.
The first example is CONICS.C in Listing Five. This program vividly illustrates the relationship between a curve and its enclosing cone. The curves are in white, their hulls in red.
The next example, HANGER.C in Listing Six draws a coat hanger to demonstrate how conic splines can be joined with each other and with lines to construct real-world images. The secret lies in forming continuous joints. You do this by placing one knot and the control point on the same plane as the line that continues the curve, and starting or ending the line at the knot. For example, the bottom of the hanger is on Y coordinate 260, and its right end is at X-500. The right spline's knot is also at {500, 260} and its control point similarly lies on Y=260. The result is a smooth joint; the spline appears to be a continuation of the wire that bends around to the right shoulder of the hanger. The hook at the top joins four conic curves. In each case, the joints occur at coincident knots and the control points of any two adjacent curves lie on the same plane such that a line passing through them also passes through the common knot.
The final example, BALL.C in Listing Seven combines ellipses, curves, and floodfills to form the shaded 3-D image of a ball resting on its shadow. This is a brute-force approach to shading, a subject that still lies in the far distant future of this column, but the visual result is the roughly the same. The flow of the program should be apparent; the message is that we have now reached the point of being able to produce reasonably good graphics with the tools developed here.
Forty-two more miles of curves to go. Time for a rest stop.
Copyright © 1989, Dr. Dobb's Journal'Round and 'Round We Go
This seems so simple that one wonders why circle-making is a big deal. LIB grafix +ellipse;
Just Partway 'Round, Thanks
LIB grafix +arc;
Kent completed this installment of his "Graphics Programming" column shortly before he passed away. Even though the series will end with this issue, we'd like to hear how you're using some of the ideas Kent's introduced in this space. Drop us a note about your program or, better yet, write an article and share your applications with others. -- eds
GRAPHICS PROGRAMMING COLUMN
by Kent Porter
[LISTING ONE]
/* ELLIPSE.C: Midpoint algorithm for drawing an ellipse */
/* Based on Wilton's "VIDEO SYSTEMS," pp 230-231 */
/* For inclusion in GRAFIX.LIB */
/* K. Porter, DDJ Graphics Programming Column, 8/89 */
#include "grafix.h"
void far ellipse (int cx, int cy, /* center x, y */
int horiz_rad, int vert_rad) /* radii ("semi-axes") */
{
int x = 0, y = vert_rad; /* starting coords for curve */
long asq = (long) horiz_rad * horiz_rad; /* a^2 */
long a2sq = asq + asq; /* 2a^2 */
long bsq = (long) vert_rad * vert_rad; /* b^2 */
long b2sq = bsq + bsq; /* 2b^2 */
long d, xd, yd; /* control values */
/* Initialize control values */
d = bsq - asq * vert_rad + asq / 4L; /* b^2 - a^2b + a^2/4 */
xd = 0L;
yd = a2sq * vert_rad; /* 2a^2b */
/* Loop to draw first half of quadrant */
while (xd < yd) {
draw_point (cx+x, cy+y); /* set pixels in all quadrants */
draw_point (cx-x, cy+y);
draw_point (cx+x, cy-y);
draw_point (cx-x, cy-y);
if (d > 0L) { /* if nearest pixel is toward the center */
--y; /* move toward center */
yd -= a2sq; /* update control values */
d -= yd;
}
++x; /* next horiz point */
xd += b2sq; /* update control values */
d += bsq + xd;
}
/* Loop to draw second half of quadrant */
d += (3L * (asq-bsq) / 2L - (xd+yd)) / 2L;
while (y >= 0) { /* do until y = 0 */
draw_point (cx+x, cy+y); /* set pixels in all quadrants */
draw_point (cx-x, cy+y);
draw_point (cx+x, cy-y);
draw_point (cx-x, cy-y);
if (d < 0L) { /* if nearest pixel is outside ellipse */
++x; /* move away from center */
xd += b2sq; /* update control values */
d += xd;
}
--y; /* next vertical point */
yd -= a2sq; /* update control values */
d += asq - yd;
}
} /* --------------- */
[LISTING TWO]
Caption: Add these entries to your copy of GRAFIX.H
/* From August '89 */
/* --------------- */
void far ellipse /* draw ellipse */
(int cx, int cy, /* at center x, y */
int horiz_rad, int vert_rad); /* radii (semi-axes) */
void far arc (int x1, int y1, int x2, int y2, int xc, int yc);
/* draw conic spline, where knots are at x1, y1 and */
/* and x2, y2, control point is at xc, yc */
[LISTING THREE]
/* CIRCLES.C: Draws several ellipses to demo ellipse() function */
/* K. Porter, DDJ Graphics Programming Column, Aug '89 */
#include <conio.h>
#include "grafix.h"
void main ()
{
if (init_video (EGA)) {
setcoords (-400, 300, 400, -300);
/* draw a true circle in upper center of screen */
ellipse (dx(0), dy(100), dxunits (150), dyunits (150));
/* tall skinny ellipse to left */
set_color1 (13); /* light magenta */
ellipse (dx(-300), dy(0), dxunits (50), dyunits (250));
/* short fat ellipse lower right */
set_color1 (10); /* light green */
ellipse (dx(150), dy(-200), dxunits (200), dyunits (30));
/* hold for keypress, then quit */
getch();
}
}
[LISTING FOUR]
/* ARC.C: Draws a conic spline using fixed point math */
/* Knots are at x1, y1 and x2, y2, control pt at xc, yc */
/* For inclusion in GRAFIX.LIB */
/* K. Porter, DDJ Graphics Programming Column, Aug '89 */
#include "grafix.h"
#include <math.h>
#define HALFPI 102944L /* fixed-point PI/2 */
void far arc (int x1, int y1, int x2, int y2, int xc, int yc)
{
int i, x, y, prevx = -1, prevy = -1;
int delta_x, delta_y, delta_t, dt = 804, den = 10;
long vx, vy, ux, uy, x0, y0;
/* fixed-point control values for this arc */
vx = (long)(xc - x2) << 16; /* distance to start */
vy = (long)(yc - y2) << 16;
ux = (long)(xc - x1) << 16; /* current point adjustment factor */
uy = (long)(yc - y1) << 16;
x0 = ((long)x1 << 16) - vx; /* center of arc */
y0 = ((long)y1 << 16) - vy;
/* compute pixel density factor (2^den) */
delta_x = (labs (vx) + labs (ux)) >> 16;
delta_y = (labs (vy) + labs (uy)) >> 16;
delta_t = delta_x + delta_y;
while (dt > delta_t) {
dt /= 2;
--den;
}
for (i = (int)((HALFPI << den) >> 16); i >= 0; --i) {
x = (int)((x0 + vx) >> 16); /* current position */
y = (int)((y0 + vy) >> 16);
if ((x != prevx) || (y != prevy)) /* if not same as last point */
draw_point (x, y); /* draw new point */
prevx = x; /* remember this position */
prevy = y;
ux -= vx >> den; /* advance arc */
uy -= vy >> den; /* division by 2^den */
vx += ux >> den;
vy += uy >> den;
}
}
[LISTING FIVE]
/* CONICS.C: Draws several conic splines and their enclosing hulls */
/* K. Porter, DDJ Graphics Programming Column, Aug '89 */
#include <conio.h>
#include "grafix.h"
void main ()
{
if (init_video (EGA)) {
/* Fig. 1a */
set_color1 (12); /* red hull */
draw_line ( 5, 20, 250, 20);
draw_line (50, 180, 250, 20);
set_color1 (15); /* white curve */
arc (5, 20, 50, 180, 250, 20);
/* Fig. 1b */
set_color1 (12); /* red hull */
draw_line (630, 20, 520, 20);
draw_line (470, 120, 520, 20);
set_color1 (15); /* white curve */
arc (630, 20, 470, 120, 520, 20);
/* acute conic in the center */
set_color1 (12);
draw_line (200, 330, 370, 40);
draw_line (340, 200, 370, 40);
set_color1 (15);
arc (200, 330, 340, 200, 370, 40);
/* wait for keypress and quit */
getch();
}
}
[LISTING SIX]
/* HANGER.C: Draws a coat hanger with lines and conic splines */
/* K. Porter, DDJ Graphics Programming Column, Aug '89 */
#include <conio.h>
#include "grafix.h"
void main ()
{
if (init_video (EGA)) {
/* draw body of hanger */
draw_line (320, 180, 140, 240); /* left top */
arc (140, 240, 140, 260, 80, 260); /* left end */
draw_line (140, 260, 500, 260); /* bottom */
arc (500, 260, 500, 240, 560, 260); /* right end */
draw_line (500, 240, 320, 180); /* right top */
/* draw hook at top */
arc (320, 180, 310, 160, 320, 168);
arc (310, 160, 300, 140, 300, 154);
arc (300, 140, 320, 120, 300, 120);
arc (320, 120, 340, 140, 340, 120);
/* wait for keypress and quit */
getch();
}
}
[LISTING SEVEN]
/* BALL.C: Ball throwing a shadow */
#include "grafix.h"
#include <conio.h>
void main ()
{
if (init_video (EGA)) {
setcoords (-320, 240, 319, -239);
/* Draw the backdrop in dark blue */
set_color1 (1);
fill_rect (0, 0, 639, 150);
/* Draw the floor in light blue */
set_color1 (9);
fill_rect (0, 150, 639, 199);
/* Create shadow on floor */
set_color1 (8); /* dark gray */
ellipse (dx(0), dy(-160), 160, 25);
setfillborder (8);
floodfill (dx(0), dy(-130));
/* Draw the ball */
set_color1 (7); /* light gray */
ellipse (dx(0), dy(0), dxunits (150), dyunits (150));
/* Shade the ball underneath */
arc (dx(-150), dy(0), dx(150), dy(0), dx(0), dy(-50));
setfillborder (7);
floodfill (dx(0), dy(-25));
/* Shade the ball white on top */
set_color1 (15);
floodfill (dx(0), dy (145));
/* Hold for keypress and quit */
getch();
}
}