This article contains the following executables: GRAFIX.H
Where I went to college, there was a professor who often strode purposefully about the campus, head high, eyes fixed resolutely on the horizon. He never looked down. Approaching a curb or stairs, he negotiated them confidently. At a door, he'd seize the knob without a flick of the eye and go inside. Sometimes, if late, he'd jog. This doesn't seem particularly remarkable until you realize that the man was totally blind.
One day I asked him how he did it. "I just count steps," he said offhandedly. "It's no big deal. I know every inch of this campus."
Then one day I ran into him in a nearby town. There, away from his well-known world, he was like other blind men, tapping his way along with a white cane. Scarcely less vigorously, I might add, but he didn't know where the obstacles were. The cane helped him find them.
Now it might seem like a far jump of the imagination to relate this blind professor to a graphics program, but there are parallels. Both move around in their worlds knowing there are things in the way, but unable to see them. To avoid hazards, both need a replacement for sight.
The person at the thinking end of a white cane finds walls, curbs, and other obstacles by detecting when the cane hits something unexpected. A program finds them by detecting a change in the pixel value. Therefore, the software white cane is a routine that senses pixels.
There are in fact several ways to get pixel information back from the display. The choice of method depends on what we're trying to accomplish. The ability to "feel" pixels and avoid obstacles gives graphics programs the freedom to do many things rather easily that would otherwise be difficult. That's exactly what a white cane does for a blind person.
This month we'll examine ways to detect individual pixels and an important application: filling closed figures.
The PC ROM BIOS Video Services furnish a built-in function to read a graphics pixel value. You place ODh into register AH and the X and Y coordinates into registers CX and DX respectively, then issue Int 10h. On return, the pixel value is in register AL. Couldn't be simpler.
Couldn't be much slower, either. I've complained about it before and I'll do it again: the ROM BIOS video routines are inexcusably slow. On my 8MHz AT clone, it takes 139.56 seconds to read all 224,000 EGA pixels, for a rate of 1605/sec.
And if you're one of those programmers who's fallen into the trap of believing faster chips make up for inefficient code, think again. Exactly the same program running on my 16MHz '386 machine takes a hair under 300 seconds, yielding a rate --if you want to call it that --of 748 pixel reads per second: less than half the throughput despite twice the cycles.
Certainly some part of this discrepancy has to do with differences in the ROM BIOS (they're both Phoenix). That's not the point. This is: Don't use the ROM BIOS pixel read. It's just too slow.
You can achieve much better pixel reading rates by going directly to the video controller with EGAPIXEL.ASM (Listing One). This routine achieves a rate of 16,500 pixels/sec. on the AT and 32,350 on my '386. Still far short of the pixel-blasting rate for the bline( ) routine, but 10.3 to 43.2 times better than the ROM BIOS Video Services.
The writing and reading of pixels have a lot in common: both have to remap the coordinates into the viewport, compute the video buffer address, and set the bit mask. Thus the first 70 or so lines of EGAPIXEL.ASM and DRAWPT.ASM (from February) are quite similar. Then things change dramatically.
Probably because pixel reading is less often done than writing, the Video Controller is less efficient at it. To write, you jam a bit pattern into a hypothetical memory location and the controller takes care of splitting it apart and updating the affected bit planes. In reading, the program has to fetch a byte from each bit plane separately and assemble the value itself, bit by bit.
The PIXVAL macro reads each bit plane for the pixel position and extracts its relevant bit. The pixel value is accumulated in register BH through rotation, reading from bit plane 3 (most significant) downward. The bytes at ES:[SI] are actually taken from the video controller's latch registers thanks to background meddling by the 6845, but the program doesn't know that. It just thinks it's reading the same memory location over and over. The pixel value accumulated in BH gets passed back to the caller (unless the location is outside the viewport, in which case -1 is returned).
Why use a macro when a loop would do? Because conditional jumps in assembly language are time-stealers. My friend Michael Abrash is doing a wonderful series of books on squeezing the utmost performance out of assembly language. Jeff Duntemann mentions it this month over in the "Structured Programming" column, and I've had a peek at the manuscript for Volume 1. Michael abhors conditional jumps, especially inside loops. I tested this routine first with a loop, then with the macro, and got a 10 percent improvement simply by eliminating the conditional jump. Now I abhor them, too.
A white cane isn't as good as eyesight, and pixel reading isn't as good as pixel writing. At best, it's a high-overhead operation. So why introduce any more overhead than absolutely necessary? In this case, a few extra bytes of code deliver more performance.
After assembling EGAPIXEL.ASM, add it to your copy of GRAFIX.LIB with the DOS command
Okay, so now we can read a pixel. What do we do with it?
RICOCHET.C in Listing Two might not be a very serious program, but it gives a feel for the possibilities. It's a variant on the idea of the rat in the maze. The screen has a border and several interior obstacles, all in white. The "rat" is a moving red pixel subject to the rule that it must always move on the diagonal. As it travels, it leaves "footprints" or, in other words, draws a line. At each step, it feels ahead for an obstacle: a white pixel. Upon encountering one, it changes direction appropriately.
The path the line takes is erratic, ricocheting around among the barriers in a frenetic pattern that gradually fills every nook and cranny of the maze with red. The fill never becomes completely solid, though, because eventually the racing rat begins retracing its steps. When that happens, the program appears to freeze; it's actually redrawing the same complex path all over again. You can stop the program any time by pressing a key.
RICOCHET is obviously neither efficient nor satisfactory as an algorithm for filling a closed figure. However, it illustrates the important point that any filling algorithm has to know where to stop. And in order to do that, it must be able to detect the border color.
The exception to this general observation is drawing solid rectangles, which we covered back in March. But fill_ rect( ) just draws a series of horizontal lines bounded by the dimensions of the object. One could also draw other regular solid polygons in this manner, such as diamonds and circles. At any point along the left edge, you can calculate the distance to the corresponding point on the right edge and draw a line. Although the visual effect indicates otherwise, that's not really filling. Instead, it's a particular application of line-drawing, and it works only for regular polygons, unless you want to do an enormous amount of computation.
A more general-purpose filling algorithm will fill any closed object, regular or otherwise. It does this by spreading "paint" outward from a known interior point --usually called the seed --until it encounters the border outlining the object. It will also leave holes in the interior, provided the closed inside figures have the same border pixel value as their container and the seed is not within one of them. The usual name for this kind of algorithm is flood fill.
The need for flood filling is obvious. As it draws the lines forming various objects, a program can't possibly remember the location of every single pixel it writes. It's like my blind professor writing on the blackboard: Once the act was done, he couldn't recall where he'd written, and sometimes he wrote right over other things. There was no white cane to help him in this case, but there is for the program. It can keep tapping ahead looking for the border pixels that comprise the brick walls for the filling algorithm.
Computer science research has produced a number of flood fill methods. Perhaps the simplest is the recursive fill, written for the GRAFIX environment as follows:
The fill restlessly spreads outward from the seed in all directions, painting pixel positions until it can no longer find any within the border.
The recursive fill works, but it has a couple of drawbacks. One is that it's not very efficient. The multiple recursive calls spend, on average, something like 75 percent of the time revisiting adjacent positions that have already been filled. Even more serious, though, is its hunger for stack space. Stack demands rise logarithmically with the size of the region being filled. Programs that use recursive fill are always in danger of crashing due to stack overflow.
A better flood fill algorithm is the line adjacency method. It too is recursive, but much less so. The amount of stack space it consumes depends more on the complexity of the polygon -- holes to work around, strange angles -- than on the size of the filled region. Nevertheless, if you're using Microsoft C or QuickC, the 2K default stack probably won't be enough.
The line adjacency algorithm thinks vertically and draws horizontally. Row by row it strives upward from the seed. Whenever it finds an unfilled row, it searches for the right and left borders and draws a line between them. It returns to the seed row when no unfilled positions remain upward, and begins striving downward in the same fashion. Because it's recursive, the algorithm remembers where it hasn't yet checked its neighboring row, and eventually it always goes back to take care of unfinished business. The procedure is done when there are no unfilled pixel positions within the closed region.
This is a somewhat simplified explanation of how the line adjacency algorithm works. For a more thorough understanding, watch it in action or, better yet, trace its execution with a debugger.
This month's contribution to the growing GRAFIX library is EGAFILL.C ( Listing Three). The module contains floodfill( ), an implementation of the line adjacency algorithm, along with some supporting functions. If you're typing in the code, you get off easy this month: All the listings are short. After compiling this module, add it to the library with
LIB grafix +egafill;
Listing Four shows the additions to your copy of GRAFIX.H. The libraries on CompuServe and the DDJ diskette both contain a complete, up-to-date version of the header file.
And finally there's Listing Five a program called FILLS.C that puts it all to work. FILLS produces three filled objects of increasing complexity, showing how the line adjacency algorithm does its thing. The first is a simple triangle. This is followed by a mis-shapen star that resembles a fighter plane. It's not actually meant to look like anything, but instead to show how the fill algorithm handles a complex shape. And finally we have a house, which is made interesting by having six unfilled islands -- the windows -- within the filled area. Note how the fill routine taps its way around them, and how it returns at the end to paint the spaces between them.
This program works fine with the default stack size in Turbo C, but with Microsoft and QuickC you have to override the 2K default with a 5K stack. You can specify this with the link option /ST:5120.
So that's how filling works with the aid of a software white cane. There are more efficient ways of doing the same thing, and sooner or later we'll get around to them. For now we have a working tool that's not difficult to understand, and which opens up new dimensions of computer graphics. Too bad that professor can't see them.
Horror story: Last week, while working on a program unrelated to this column, I clobbered the FAT on my hard disk. A 44-meg hard disk, I might add, that was nearly full. I'm still not sure how it happened. There were some problems with a wild indexing scheme, so the program probably corrupted some code that, when it got control later, did an absolute write to several FAT sectors. Naturally, I hadn't done a backup in some time ("Tomorrow I'll do it").
When you lose pieces of the FAT, you're in a heap of trouble. Just for starters I lost the entire directory for this column. Fortunately I had a backup of programs already published or in the mill, but the future stuff I was working on was gone. So were a lot of other things.
Heroics were in order, and I went to work in a panic. First I got everything off the disk that I could. Using another computer, I wrote some hasty software that allowed me to browse sectors and reconstruct broken chains manually. Talk about a blind man tapping his way around.
But what really pulled my FAT from the fire was the new Norton Utilities Advanced Edition. Between the Norton Disk Doctor (NDD) and the multifaceted NU program, I was able to find the problems and twiddle the bits to fix them. I didn't get everything back, but I got probably 90 percent of the things I cared about.
I can't say this too strongly. Norton's Advanced Edition is a superlative product. Get it. It brought me back from a catastrophe, and it might do the same for you.
All source code for articles in this issue is available on a single disk. To order, send $14.95 (Calif. residents add sales tax) to Dr. Dobb's Journal, 501 Galveston Dr., Redwood City, CA 94063, or call 800-356-2002 (from inside Calif.) or 800-533-4372 (from outside Calif.). Please specify the issue number and format (MS-DOS, Macintosh, Kaypro).
Copyright © 1989, Dr. Dobb's JournalThis Is Not The Way To Do It
The Improved White Cane
LIB grafix +egapixel;
Speaking of Filling...
void fill (int x, int y, byte border){
if (egapixel (x, y) != border){
draw_point (x, y);
fill (x+1, y, border);
fill (x-1, y, border);
fill (x, y+1, border);
fill (x, y-1, border);
}
}
Pulling My FAT from the Fire
Availability
Graphics Programming (column)
by Kent Porter
<a name="012c_0009"><a name="012c_0009">
[Listing One]
; EGAPIXEL.ASM: Reads EGA pixel value directly from video memory
; Returns pixel value at x, y, or -1 if outside viewport
; Microsoft MASM 5.1
; C prototype is
; int far egapixel (int x, int y);
; To be included in GRAFIX.LIB
; K. Porter, .MDUL/DDJ.MDNM/ ``Graphics Programming'' column, June '89
.MODEL LARGE
PUBLIC _egapixel
EXTRN _vuport : WORD ; far ptr to vuport structure
; Arguments passed from C
x EQU [bp+6] ; Arguments passed from C
y EQU [bp+8]
; Macro to build pixel value in BL
pixval MACRO
out dx, ax ; set 6845 for bit plane
mov bh, BYTE PTR es:[si] ; get byte from current bit plane
and bh, ch ; mask bit
neg bh ; and flip it
rol bx, 1 ; move to bit 0 in accum (BH)
dec ah ; next bit plane
ENDM
.CODE
_egapixel PROC FAR
push bp ; Entry processing
mov bp, sp
push si ; Save SI (used here)
; Point ES:[BX] to vuport structure
mov ax, _vuport+2 ; get pointer segment
mov es, ax
mov bx, _vuport ; get offset
; Quit if coordinates outside viewport
mov al, -1 ; return value if outside
mov cx, y ; get y
cmp cx, WORD PTR es:[bx+6] ; is y within viewport?
jge exit ; quit if not
mov dx, x ; get x
cmp dx, WORD PTR es:[bx+4] ; is x within viewport?
jge exit ; quit if not
; Map pixel coordinates to current viewport
add dx, WORD PTR es:[bx] ; offset x by vuport.left
push dx ; save remapped X (used later)
add cx, WORD PTR es:[bx+2] ; offset y by vuport.top
; Point ES to video memory segment
mov bx, 0A000h
mov es, bx
; Row offset = y * 80;
push dx ; (modified by MUL)
mov ax, cx ; get y
mov bx, 80
mul bx ; y * 80
mov bx, ax ; into BX
; Column offset = x SHR 3
pop ax ; get x back
mov cl, 3 ; shift operand
shr ax, cl ; column offset
; Complete address of pixel byte
add bx, ax ; BX = row offset + col offset
mov si, bx ; ES:SI = address
; Build bit mask for pixel
pop cx ; get x back
and cl, 7 ; isolate low-order bits
xor cl, 7 ; number of bits to shift
mov ch, 1 ; start bit mask
shl ch, cl ; shift for pixel
xor bl, bl ; accumulator for pixel value
; Set graphics controller Read Map Select Register
mov dx, 03CEh ; 6845 command register
mov ax, 0304h ; first bit plane = 3
; Read bit planes 3-0, accumulating bits in BL
pixval
pixval
pixval
pixval
; AX = return value for function
mov al, bl
; Send pixel value back in AL
exit: xor ah, ah
pop si
mov sp, bp
pop bp
retf
_egapixel ENDP
END
<a name="012c_000a"><a name="012c_000a">
[Listing Two]
/* RICOCHET.C: A line moving diagonally "feels" its way among obstacles */
/* Illustrates pixel-reading with egapixel() */
/* K. Porter, .MDUL/DDJ.MDNM/ ``Graphics Programming'' column, June '89 */
#include "grafix.h"
#include <conio.h>
void main ()
{
int x = 638; /* current X position of line */
int y = 348; /* and its Y */
int xdir = -1; /* current X direction (-1 = left, 1 = right) */
int ydir = -1; /* and Y direction (-1 = up, 1 = down */
if (init_video (EGA)) {
/* Draw a maze and border */
set_color1 (15);
draw_rect (0, 0, 639, 349);
draw_line (141, 40, 141, 119);
hline (141, 119, 120);
draw_line (421, 0, 421, 100);
hline (540, 199, 80);
hline (360, 160, 120);
hline (300, 261, 120);
draw_line (200, 259, 200, 330);
draw_line (99, 240, 99, 349);
/* Send the line bouncing around */
set_color1 (4);
while (!kbhit()) {
if (egapixel (x+xdir, y) == 15) /* feel ahead horizontally */
xdir = -xdir; /* reverse if obstacle */
if (egapixel (x, y+ydir) == 15) /* same vertically */
ydir = -ydir;
x += xdir; /* advance position */
y += ydir;
draw_point (x, y);
}
getch(); /* clear keyboard buffer */
}
}
<a name="012c_000b"><a name="012c_000b">
[Listing Three]
/* EGAFILL.C: Line adjacency flood fill algorithm for EGA */
/* For inclusion in GRAFIX.LIB */
/* K. Porter, DDJ Graphics Programming Column, June '89 */
/* ---------------------------------------------------- */
#include "grafix.h"
extern int color1; /* from GRAFIX library */
int border = 15; /* border for floodfill */
int dir = -1; /* fill direction */
void far setfillborder (int color)
{
border = color;
} /* ----------------------------------------------------------------- */
int far floodfill (int sx, int sy) /* fill bounded region */
{
int x; /* current column */
int left, rite; /* ends of current line */
byte pixel; /* detected pixel value */
int near leftborder (int, int, byte), /* local functions */
near rightborder (int, int, byte);
/* find ends of seed row */
left = leftborder (sx, sy, border);
rite = rightborder (sx, sy, border);
/* fill seed row */
draw_line (left+1, sy, rite-1, sy);
/* fill adjacent rows in same direction */
for (x = left+1; x < rite; x++) {
pixel = egapixel (x, sy+dir); /* inspect adjacent row */
if ((pixel != color1) && (pixel != border))
x = floodfill (x, sy+dir);
}
/* fill adjacent rows in opposite direction */
for (x = left+1; x < rite; x++) {
pixel = egapixel (x, sy-dir);
if ((pixel != color1) && (pixel != border))
x = floodfill (x, sy-dir);
dir = -dir;
}
for (x = left+1; x < rite; x++) {
pixel = egapixel (x, sy-dir);
if ((pixel != color1) && (pixel != border))
x = floodfill (x, sy-dir);
dir = -dir;
}
return rite;
} /* -------------------------------------------------------------- */
/* Following are local routines serving floodfill() */
int near leftborder (int x, int y, byte border)
{
byte pixel;
do {
--x;
pixel = egapixel (x, y);
if ((pixel == border) || (pixel == color1))
break;
} while (x > 0);
return x;
} /* -------------------------------------------------------------- */
int near rightborder (int x, int y, byte border)
{
byte pixel;
do {
++x;
pixel = egapixel (x, y);
if ((pixel == border) || (pixel == color1))
break;
} while (x < vp_width());
return x;
} /* -------------------------------------------------------------- */
<a name="012c_000c"><a name="012c_000c">
[Listing Four]
/* From June, '89 */
/* -------------- */
int far egapixel (int x, int y); /* get pixel value at x, y */
void far setfillborder (int color); /* border for floodfill */
int far floodfill (int sx, int sy); /* fill bounded region */
<a name="012c_000d"><a name="012c_000d">
[Listing Five]
/* FILLS.C: Various filled figures */
/* K. Porter, DDJ Graphics Programming Column, June '89 */
#include "grafix.h"
#include <conio.h>
int triangle[] = {
20,300, 120,300, 70,200, 20,300
};
int star[] = {
60, 10, 120,80, 20,60, 100,140, 140,110,
260,190, 220,70, 370,30, 180, 40, 60, 10
};
int house[] = {
400,200, 400,340, 600,340, 600,200,
500,100, 400,200
};
void main() {
int x, y;
if (init_video (EGA)) {
set_color1 (15);
polyline (3, triangle);
set_color1 (4);
setfillborder (15);
floodfill (70, 250);
set_color1 (14);
polyline (9, star);
set_color1 (6);
setfillborder (14);
floodfill (140, 80);
set_color1 (15);
polyline (5, house);
for (x = 430; x < 560; x += 60)
for (y = 220; y < 300; y += 60)
draw_rect (x, y, 20, 35);
set_color1 (7);
setfillborder (15);
floodfill (500, 200);
getch();
}
}
[GRAFIX.LIB]
/* Include file for GRAFIX.LIB */
/* EGA/VGA graphics subsystem */
/* K. Porter, DDJ Graphics Programming Column */
/* ------------------------------------------ */
/* Color constants from April, 89 */
#define Black 0 /* standard colors */
#define Blue 1
#define Green 2
#define Cyan 3
#define Red 4
#define Magenta 5
#define Brown 0x14
#define LtGray 7
#define DkGray 0x38
#define LtBlue 0x39
#define LtGreen 0x3A
#define LtCyan 0x3B
#define LtRed 0x3C
#define LtMagenta 0x3D
#define Yellow 0x3E
#define White 0x3F
#define RED0 0x00 /* basic hues for mixing */
#define RED1 0x20
#define RED2 0x04
#define RED3 0x24
#define GRN0 0x00
#define GRN1 0x10
#define GRN2 0x02
#define GRN3 0x12
#define BLU0 0x00
#define BLU1 0x08
#define BLU2 0x01
#define BLU3 0x09
#if !defined byte
#define byte unsigned char
#endif
/* Supported video modes */
#define EGA 0x10 /* EGA 640 x 350, 16/64 colors */
#define VGA16 0x11 /* VGA 640 x 480, 16/64 colors */
/* Function prototypes */
/* From February, '89 */
/* ------------------ */
int far init_video (int mode); /* init display in video mode */
void far pc_textmode (void); /* PC text mode */
void far draw_point (int x, int y); /* write pixel in color1 */
void far set_color1 (int palette_reg); /* set foreground color */
/* From March, '89 */
/* --------------- */
void far draw_line (int x1, int y1, int x2, int y2);
/* Bresenham line drawing algorithm */
void far draw_rect (int left, int top, int width, int height);
/* draw rectangle from top left corner */
void far polyline (int edges, int vertices[]); /* draw polyline */
void far hline (int x, int y, int len); /* horizontal line */
void far fill_rect (int left, int top, int width, int height);
/* draw solid rectangle in color1 starting at top left corner */
/* From April, '89 */
/* --------------- */
byte far ega_palreg (int preg); /* color in EGA palette reg */
void far set_ega_palreg (int reg, int color); /* set palette reg */
byte far colorblend (byte r, byte g, byte b); /* blend hues */
void far get_ega_colormix (int preg, int *r, int *g, int *b);
/* get mix of red, green, and blue in EGA pal register preg */
/* From May, '89 */
/* ------------- */
typedef int VP_HAN; /* viewport handle type */
void far default_viewport (int height); /* init default viewport */
VP_HAN far vp_open (int x, int y, int width, int height);
/* open viewport, make it active */
int far vp_use (VP_HAN vp); /* make vp active */
void far vp_close (VP_HAN vp); /* close viewport */
VP_HAN far vp_active (void); /* get handle of active vp */
void far vp_outline (VP_HAN vp); /* outline vp */
int far vp_width (void); /* get active viewport width */
int far vp_height (void); /* and height */
/* From June, '89 */
/* -------------- */
int far egapixel (int x, int y); /* get pixel value at x, y */
int far floodfill (int sx, int sy, /* seed coords */
int border, /* border color */
int dir, /* pass as 0 */
int pleft, int prite); /* make same as sx */
