|
The shortest distance between two points is a straight line. But, as Kent points out, that's easier said than done.
March 01, 1989
URL:http://www.drdobbs.com/database/graphics-programming/184408109
Copyright © 1989, Dr. Dobb's Journal
If the lowly pixel is the foundation of computer graphics, the line is its cornerstone. Now that we've figured out how to draw a pixel on the EGA/VGA screen efficiently, it would seem that combining them to form lines is no big deal. Not so, as we'll see this month in developing a couple of ways to draw lines and some combinations thereof.
Here's the problem. A line moves between two end points in any conceivable direction. Its path varies continuously, passing through an infinite number of points. The number and positions of points on a display screen, however, are fixed. Therefore the challenge in drawing a line is to find, for any given point along its path, the nearest fixed point on the display. A line is thus represented by lighting the series of pixels lying closest to its path, as Figure 1 illustrates.
The simplest way to approximate a line is to calculate the series of points using the linear equation
where m is the slope (the amount of vertical change per x increment) and b is the y- intercept (the point where the line crosses the y axis). When m and b are known, you plug in any x and round the result to get the nearest y. Unfortunately, this method yields unacceptable performance because m is a floating-point value.
You have to use integer arithmetic if you want fast line-drawing. In 1965, IBM researcher J.E. Bresenham published an integer-based method that has become a stock item in computer graphics.
The Bresenham algorithm represents the slope with two integers, called the diagonal and nondiagonal increments, which have opposite signs. As the line progresses, they are applied to a pixel selection variable generally represented by the symbol d. The nondiagonal increment is applied when the nearest pixel is in the current row, the diagonal increment is applied when it's in an adjacent row. The sign of d indicates when the row changes, and thus selects the closest pixel. When d is negative, the pixel above is selected and the row doesn't change, and when d is positive, diagonal movement occurs to the row below.
The terms "row," "above," and "below" are only conceptual. The signs of the control variables allow the Bresenham algorithm to draw right to left, thus mathematically turning the display upside down. And when the major axis of motion is along the y axis, Bresenham mathematically rotates the display 90 degrees, one way or the other, according to the drawing direction.
That's the purpose of the code between lines 13 and 38 in Listing One, page 137, which implements the Bresenham algorithm. The result is an unbroken line representation consisting of linearly-and diagonally-adjacent pixels, drawn using only three integer addition operations in the loop starting on line 40.
Add the draw_line( ) function from Listing One to your copy of GRAFIX.C and the prototype to GRAFIX.H. In order to use the function, you must recompile GRAFIX.C and replace it in the GRAFIX.LIB file. (Note: if you purchase the DDJ companion diskette or download the code for this article from CompuServe, you will receive complete new copies of the source files containing this and other routines added this month.)
Listing Two (SPOKES.C), page 137, is a sample program that puts the Bresenham routine to work. SPOKES.C draws multicolor lines emanating from the center of the EGA display.
Programming in general develops functionality much as a brick layer builds a wall: by stacking layers of bricks (lower-level functions) according to a plan and fastening them together with the mortar of program logic. Nowhere is this more prevalent than in graphics. So far, we've made away to write pixels and used that routine to draw lines. Now we'll add another level to the hierarchy with a couple of functions that draw multiple lines.
The first is the rectangle, an object occurring so often that it needs its own function. We can describe a rectangle in terms of its width and height relative to the upper left corner. Thus the rectangle function in Listing Three page 137, is called with draw_rect (left, top, width, height). The logic of the routine combines the arguments in various ways and passes them along to the four invocations of draw_line( ) needed to draw the edges.
The other high-level function, also shown in Listing Three, is more complex. It draws a series of joined line segments and for that reason has the name polyline( ). You can use it to draw closed object such as a star or an open object such as the zigzag data representation of a line chart.
If a polyline has n edges, you need n+1 vertices to represent it. For example, a line from A to B to C consists of two segments or edges: A to B, and B to C. The vertices are the end points A, B, and C. The polyline( ) function thus requires two arguments. The first is the number of edges, and the other is an array of vertices. The vertex array consists of coordinate pairs, where v[O] = xA, v[1] = yA, v[2] = xB, v[3] = yB, and so on. Consequently, the size of the array is (n+1)*2 integers: in the case of polyline ABC, six elements.
The internal flow of polyline( ) advances along the vertices like an inchworm, drawing from the previous vertex to the current vertex. When the current vertex exceeds the number of edges plus one, the routine is finished.
Add the two routines from Listing Three to GRAFIX.C and their prototypes to GRAFIX.H, then recompile and replace the module in GRAFIX.LIB. You can then run the two small demo programs from Listings Four (BOXES.C) and Five (STAR.C), page 137, which exercise the new functions by drawing a series of rectangles (BOXES.C) and a five-pointed star.
The Bresenham algorithm --venerated though it is for its efficiency --still draws only one pixel at a time. There isn't an alternative when drawing lines that move in any direction. For strictly horizontal lines, however, we can use a special hardware feature to write up to eight pixels at a time.
The 6845 video controller's Write Mode 0 enables you to update an entire byte on each plane --that is, eight pixels --with one operation. The only stipulation is that all pixels must receive the same index value filtered by the same bitmask. In other words, the eight pixels are treated identically in a single operation. Updating eight pixels simultaneously is actually more efficient than updating one using Write Mode 2, used in the draw_point( ) routine introduced last month. This is because it's not necessary to shift the data mask in order to identify the individual pixel being written. In fact, Write Mode 0 incurs almost exactly the same overhead for eight pixels that Write Mode 2 incurs for one. The result is blazing throughput.
The hline( ) routine in Listing Six (HLINE.ASM), page 138, uses Write Mode 0 to deliver over 580,000 pixels per second on a 10-MHz AT clone when all lines completely fill each byte. The routine is slowed slightly if there are odd pixels on each end, because hline( ) must construct the masks required to update only the affected pixels. Still, worst-case performance is in the area of 450,000 pixels per second, which amounts to an 18X to 23X improvement over Bresenham.
Like draw_point( ), hline( ) is written in assembly language for maximum efficiency. Its public symbol has an underscore prefix to comply with C linkage conventions. Add the prototype
to your copy of GRAFIX.H, then assemble this routine and add it to GRAFIX.LIB using a librarian.
Note that hline( ) uses several auto variables allocated on the stack. Arguments are at positive offsets from the BP register; for local variables, subtract the sum of their sizes from the SP register, then offset negatively from BP to reach each variable, as illustrated by the EQUate directives. This is precisely the same method used by most language compilers for allocating variables local to subroutines. When exit processing moves the BP register contents back into SP, the auto variables are automatically removed from the stack.
A horizontal line lacks flexibility, of course, but it's very useful in creating solids. A case in point is a filled rectangle; simply loop through a sequence of Y coordinates, repeatedly drawing a line of the same length. Listing Seven page 141, gives the GRAFIX function fill_rect( ) for doing this. Add it to GRAFIX.C and its prototype to 7.
The program COLORS.C in Listing Eight, page 141, uses fill_rect( ) to display the default 16-color palette of the EGA and VGA. This program fills 90 percent of the 224,000-pixel screen, yet thanks to hline( ), it takes less than half a second on the AT. As you see, drawing a line --a fundamental object in computer graphics --isn't quite as trivial as it seems at first glance. Now that we've developed the basic algorithms and the beginnings of a hierarchy of graphics primitives, we can start writing serious graphics programs, and that's what we'll continue doing over the coming months.
_GRAPHICS PROGRAMMING COLUMN_
by Kent Porter
[LISTING ONE]
Copyright © 1989, Dr. Dobb's Journal
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.
y = mx + b
void far hline (int x, int y, int length);
1| void far draw_line (int x1, int y1, int x2, int y2)
2| /* Bresenham line drawing algorithm */
3| /* x1, y1 and x2, y2 are end points */
4| {
5| int w, h, d, dxd, dyd, dxn, dyn, dinc, ndinc, p;
6| register x, y;
7|
8| /* Set up */
9| x = x1; y = y1; /* start of line */
10| w = x2 - x1; /* width domain of line */
11| h = y2 - y1; /* height domain of line */
12|
13| /* Determine drawing direction */
14| if (w < 0) { /* drawing right to left */
15| w = -w; /* absolute width */
16| dxd = -1; /* x increment is negative */
17| } else /* drawing left to right */
18| dxd = 1; /* so x incr is positive */
19| if (h < 0) { /* drawing bottom to top */
20| h = -h; /* so get absolute height */
21| dyd = -1; /* y incr is negative */
22| } else /* drawing top to bottom */
23| dyd = 1; /* so y incr is positive */
24|
25| /* Determine major axis of motion */
26| if (w < h) { /* major axis is Y */
27| p = h, h = w, w = p; /* exchange height and width */
28| dxn = 0;
29| dyn = dyd;
30| } else { /* major axis is X */
31| dxn = dxd;
32| dyn = 0;
33| }
34|
35| /* Set control variables */
36| ndinc = h * 2; /* Non-diagonal increment */
37| d = ndinc - w; /* pixel selection variable */
38| dinc = d - w; /* Diagonal increment */
39|
40| /* Loop to draw the line */
41| for (p = 0; p <= w; p++) {
42| draw_point (x, y);
43| if (d < 0) { /* step non-diagonally */
44| x += dxn;
45| y += dyn;
46| d += ndinc;
47| } else { /* step diagonally */
48| x += dxd;
49| y += dyd;
50| d += dinc;
51| }
52| }
53| }
[LISTING TWO]
/* SPOKES.C: Bresenham demo */
/* Multicolored spokes emanate from center of screen */
#include <conio.h>
#include <stdio.h>
#include "grafix.h"
#define CX 320 /* Center of screen */
#define CY 175
void main()
{
int x, y, color = 1, next (int);
if (init_video (EGA)) {
/* Spokes from center to top and bottom */
for (x = 0; x <= 640; x += 80) {
color = next (color);
draw_line (x, 0, CX, CY);
color = next (color);
draw_line (x, 349, CX, CY);
}
/* Spokes from center to sides */
for (y = 70; y < 350; y += 70) {
color = next (color);
draw_line (639, y, CX, CY);
color = next (color);
draw_line (0, y, CX, CY);
}
getch(); /* Wait for a keystroke */
} else
puts ("EGA not present in system: program ended");
} /* ------------------------ */
int next (int hue) /* set/return next color */
{
set_color1 (hue++);
return ((hue > 15) ? 1 : hue); /* wrap around */
}
[LISTING THREE]
1| void far draw_rect (int xleft, int ytop, int w, int h)
2| /* Draw outline rectangle in color1 from top left corner */
3| /* w and h are width and height */
4| /* xleft and ytop are top left corner */
5| {
6| draw_line (xleft, ytop, xleft+w, ytop); /* top */
7| draw_line (xleft+w, ytop, xleft+w, ytop+h); /* right */
8| draw_line (xleft+w, ytop+h, xleft, ytop+h); /* bottom */
9| draw_line (xleft, ytop+h, xleft, ytop); /* left */
10| } /* ------------------------------------------------------ */
11|
12| void far polyline (int edges, int vertex[])
13| /* Draw multipoint line of n edges from n+1 vertices where: */
14| /* vertex [0] = x0 vertex [1] = y0 */
15| /* vertex [2] = x1 vertex [3] = y1 */
16| /* etc. */
17| {
18| int x1, y1, x2, y2, v;
19|
20| x1 = vertex[0];
21| y1 = vertex[1];
22| for (v = 2; v < (edges+1)*2; v+= 2) {
23| x2 = vertex[v];
24| y2 = vertex[v+1];
25| draw_line (x1, y1, x2, y2);
26| x1 = x2;
27| y1 = y2;
28| }
29| } /* ------------------------------------------------------ */
[LISTING FOUR]
/* BOXES.C: Demo of draw_rect() in GRAFIX.LIB */
/* Draws a big rectangle and four smaller ones */
/* K. Porter, DDJ Graphics Programming Column, March 89 */
/* ---------------------------------------------------- */
#include <conio.h>
#include "grafix.h"
main ()
{
if (init_video (EGA)) {
set_color1 (15);
draw_rect (100, 100, 440, 230);
set_color1 (14);
draw_rect (110, 110, 420, 30);
set_color1 (13);
draw_rect (110, 105, 220, 220);
set_color1 (12);
draw_rect (340, 150, 190, 100);
set_color1 (11);
draw_rect (340, 260, 190, 60);
getch(); /* wait for keystroke */
}
}
[LISTING FIVE]
/* STAR.C: Draws a star using polyline */
#include <conio.h>
#include "grafix.h"
int vert [] = { /* vertices of star */
320, 60, 420,280, 150,140,
490,140, 220,280, 320, 60
};
void main ()
{
if (init_video (EGA)) {
polyline (5, vert); /* draw */
getch(); /* wait for key */
}
}
[LISTING SIX]
; HLINE.ASM: Fast horizontal line drawing routine
; Uses 6845 Write Mode 0 to update 8 pixels at a time on EGA/VGA
; C prototype is
; void far hline (int x, int y, int length_in_pixels);
; Writes in current color1 from GRAFIX.LIB
; Microsoft MASM 5.1
; K. Porter, DDJ Graphics Programming Column, March 89
.MODEL LARGE
.CODE
PUBLIC _hline
EXTRN _color1 : BYTE ; Current palette reg for pixel
EXTRN _draw_point : PROC ; Pixel writing routine
EXTRN _vuport : WORD ; far ptr to vuport structure
; Declare arguments passed by caller
x EQU [bp+6]
y EQU [bp+8]
len EQU [bp+10]
; Declare auto variables
last EQU [bp- 2] ; Last byte to write
solbits EQU [bp- 4] ; Mask for start of line
oddsol EQU [bp- 6] ; # odd bits at start of line
eolbits EQU [bp- 8] ; Mask for end of line
oddeol EQU [bp-10] ; # odd bits at end of line
; ----------------------------
_hline PROC FAR ; ENTRY POINT TO PROC
push bp ; entry processing
mov bp, sp
sub sp, 10 ; make room for auto variables
xor ax, ax ; initialize auto variables
mov last, ax
mov solbits, ax
mov oddsol, ax
mov eolbits, ax
mov oddeol, ax
; Do nothing if line length is zero
mov bx, len ; get line length
cmp bx, 0 ; length = 0?
jnz chlen ; if not, go on
jmp quit ; else nothing to draw
; Call draw_point() with a loop if line length < 8
chlen: cmp bx, 8
jnb getvp ; go if len >= 8
mov ax, y ; get args
mov cx, x
drpt: push bx ; push remaining length
push ax ; push args to draw_point()
push cx
call _draw_point ; draw next pixel
pop cx ; clear args from stack
pop ax
pop bx ; fetch remaining length
inc cx ; next x
dec bx ; count pixel drawn
jnz drpt ; loop until thru
jmp quit ; then exit
; Point ES:[BX] to vuport structure
getvp: mov ax, _vuport+2 ; get pointer segment
mov es, ax
mov bx, _vuport ; get offset
; Clip if starting coordinates outside viewport
mov cx, y ; get y
cmp cx, es:[bx+6] ; is y within viewport?
jl checkx ; ok if so
jmp quit ; else quit
checkx: mov ax, x ; get x
cmp ax, es:[bx+4] ; is x within viewport?
jl remap ; ok if so
jmp quit ; else quit
; Map starting coordinates to current viewport
remap: add ax, es:[bx] ; offset x by vuport.left
mov x, ax ; save remapped X
add cx, es:[bx+2] ; offset y by vuport.top
mov y, cx ; save remapped Y
; Clip line length to viewport width
mov ax, es:[bx+4] ; get vuport.width
sub ax, x ; maxlength = width - starting x
add ax, es:[bx] ; + vuport.left
cmp ax, len ; if maxlength > length
jg wm0 ; length is ok
mov len, ax ; else length = maxlength
; Set 6845 for write mode 0, all planes enabled, color selected
wm0: mov dx, 03CEh
mov ax, 0005h ; Set write mode
out dx, ax
mov ax, 0FF00h ; Set/Reset reg, enable all planes
out dx, ax
mov ax, 0FF01h ; Enable set/reset reg, all planes
out dx, ax
mov dx, 03C4h ; 6845 address reg
mov al, 2 ; Data reg
mov ah, _color1 ; Palette reg planes enabled
out dx, ax ; Set color code
; Compute x coord for last byte to be written
mov bx, x ; get start of line
add bx, len ; end = start + length
mov cx, bx
and cx, 0FFF8h ; x coordinate where odd bits
mov last, cx ; at end of line begin
; Compute number of odd pixels at end of line
sub bx, cx
mov oddeol, bx ; save it
; Construct pixel mask for last byte of line
cmp bx, 0
jz bsol ; go if no odd pixels
xor ax, ax
eolb: shr ax, 1 ; shift right and
or ax, 80h ; set H/O bit
dec bl ; until mask is built
jnz eolb
mov eolbits, ax ; then save mask
; Compute number of odd pixels at start of line
bsol: mov cx, x ; get starting X again
and cx, 7 ; # of pixels from start of byte
jz saddr ; go if none
mov bx, 8
sub bx, cx ; # of pixels to write
mov oddsol, bx ; save
; Construct pixel mask for first byte of line
xor ax, ax
solb: shl ax, 1 ; shift left and
or ax, 1 ; set L/O bit
dec bl ; until mask is built
jnz solb
mov solbits, ax ; then save mask
; Translate last byte X into an address
saddr: mov ax, 0A000h
mov es, ax ; ES ==> video buffer
mov bx, y ; get row
mov ax, 80
mul bx
mov bx, ax ; BX = row offset = row * 80
push bx ; save row offset
mov ax, last ; get last byte X
mov cl, 3
shr ax, cl ; shift for col offset
add bx, ax ; last offs = row offs + col offs
mov last, bx
; Compute address of first byte (ES:[BX])
pop bx ; fetch row offset
mov ax, x ; get col offset
mov cl, 3
shr ax, cl ; shift right 3 for col offset
add bx, ax ; offset = row offs + col offs
cmp bx, last ; is first byte also last?
jz weol ; skip to end mask if so
; Write start of line
mov dx, 03CEh ; 6845 port
mov ah, solbits ; start-of-line mask
cmp ah, 0
jz w8 ; go if empty mask
mov al, 8 ; set bit mask reg
out dx, ax
mov cl, es:[bx] ; load 6845 latches
mov ax, solbits
neg al ; complement
dec al ; for reversed bit mask
and al, cl ; filter previously unset pixels
mov es:[bx], al ; clear affected bits
mov al, _color1
mov es:[bx], al ; set affected bits
inc bx ; next byte
cmp bx, last ; ready for end of line yet?
jae weol ; go if so
; Write 8 pixels at a time until last byte in line
w8: mov ax, 0FF08h ; update all pixels in byte
out dx, ax ; set bit mask reg
mov al, es:[bx] ; load 6845 latches
xor al, al
mov es:[bx], al ; clear all pixels
mov al, _color1
mov es:[bx], al ; set all bits
inc bx ; next byte
cmp bx, last ; thru?
jnz w8 ; loop if not
; Write end of line
weol: mov dx, 03CEh ; 6845 port
mov ah, eolbits ; end-of-line mask
cmp ah, 0
jz rvc ; go if empty mask
mov al, 8 ; set bit mask reg
out dx, ax
mov cl, es:[bx] ; load 6845 latches
mov ax, eolbits
neg al ; complement
dec al ; for reversed bit mask
and al, cl ; filter previously unset pixels
mov es:[bx], al ; clear affected bits
mov al, _color1
mov es:[bx], al ; set affected bits
; Restore video controller to default state
rvc: mov dx, 03CEh
mov ax, 0005h ; write mode 0, read mode 0
out dx, ax
mov ax, 0FF08h ; default bit mask
out dx, ax
mov ax, 0003h ; default function select
out dx, ax
xor ax, ax ; zero Set/Reset
out dx, ax
mov ax, 0001h ; zero Enable Set/Reset
out dx, ax
mov dx, 03C4h ; 6845 address reg
mov ax, 0F02h ; Data reg, enable all planes
out dx, ax
; End of routine
quit: mov sp, bp
pop bp
retf
_hline ENDP
END
[LISTING SEVEN]
void far fill_rect (int xleft, int ytop, int w, int h)
/* Draw solid rectangle in color1 from top left corner */
{
register y;
for (y = ytop; y < ytop+h; y++)
hline (xleft, y, w);
} /* ------------------------------------------------------ */
[LISTING EIGHT]
/* COLORS.C: Shows all colors in default palette */
#include "grafix.h"
#include <conio.h>
void main ()
{
int r, c, color;
if (init_video (EGA)) {
for (r = 0; r < 4; r++)
for (c = 0; c < 4; c++) {
color = (r * 4) + c; /* next color */
set_color1 (color);
fill_rect ((c*160), (r*80), 158, 79);
}
getch(); /* wait for keypress */
}
}