GRAPHICS PROGRAMMING
Potato Heads, Fast VGAs, and More
Michael Abrash
I'm not a doomsayer who thinks American education lags hopelessly behind the rest of the Westem world, but a recent experience did make me wonder. Not so long ago, I received a letter from one Melvyn J. Lafitte requesting that I spend some time in this column describing fast 3-D animation techniques. Melvyn hoped that I would be so kind as to discuss, among other things, hidden surface removal and perspective projection, performed in real time, of course, and preferably in mode X. Sound familiar?
Melvyn shared with me a hidden surface approach that he had developed. His technique invoked defining polygon vertices in clockwise order, as viewed from the visible side. Then, he explained, one can use the cross-product equations found in any math book to determine which way the perpendicular to the polygon is pointing. Better yet, be pointed out, it's necessary to calculate only the Z component of the perpendicular, and only the sign of the Z component need actually be tested.
What Melvyn described is, of course, backface removal, a key hidden-surface technique that we've used heavily over the past three months. In general, other hidden surface techniques must be used in conjunction with backface removal, but backface removal is nonetheless important and highly efficient. Simply put, Melvyn had devised for himself one of the fundamental techniques of 3-D drawing.
Melvyn is from Moens, France. At the time he wrote me, Melvyn was 17 years old. Try to imagine any American 17-year-old of your acquaintance inventing backface removal. Try to imagine any teenager you know even using the phrase "the cross-product equations found in any math book." Not to mention that Melvyn was able to write a highly technical letter in English; and if Melvyn's English was something less than flawless, it was perfectly understandable, and, in my experience, vastly better than an average, or even well-educated, American's French. Please understand, I believe we Americans excel in a wide variety of ways, but I worry that when it comes to math and foreign languages, we are becoming a nation of têtes depomme de pomme de terre.
Anyway, Melvyn has gotten his wish over the last few months; we've been busy with some pretty intense 3-D animation for quite a while now. It's time to take a break and catch up with the mail.
A dual monitor system--one VGA, one monochrome adapter--is virtually mandatory for serious PC graphics development, because the debugger output has to have somewhere to show up without disturbing the graphics program being debugged. Sure, you can use a remote system, but that requires two computers and tends to be annoyingly slow. A two monitor setup is cheaper and more convenient, and just about every graphics developer I know goes the two-monitor route.
Unfortunately, it's well documented that the presence of an 8 bit monochrome adapter forces any and all, 16-bit VGAs to revert to 8-bit operation. (See my May, 1990 DDJ article, Demystifying 16-Bit VGA.) Each access to the VGA can then transfer only 1 byte, just as if the VGA had an 8-bit connector. At the very least, that halves the per formance of word-sized accesses to VGA display memory, as in the case of REP STOSW, which is typically used to fill rectangles. At the worst, it also causes some buses to think the adapter was designed for the PC, and therefore to insert additional wait states to slow accesses down to the PC's miserably slow bus speed, typically halving the performance of all accesses to VGA display memory. Worse, the two speed reductions are multiplicative, so access to VGA display memory can take as much as four times longer if an 8-bit monochrome card is installed. The end result is that if an 8-bit monochrome adapter is installed, your souped-up 386 or 486 16-bit Super-VGA system can wind up with 8-bit VGA performance that's scarcely faster than IBM's original adapter.
The solution is obvious: Buy a 16-bit monochrome card. Except that there aren't any that I know of. Monochrome cards are low-end, low-margin items, and no one is going to bother making a 16-bit version for the tiny fraction of users who want two monitors and both know and care about the speed implications of 8-bit monochrome adapters. (I'd gladly pay an extra $50 for a 16-bit monochrome adapter, in case anyone's listening.)
So a hardware solution isn't feasible but a software solution is, Listing One (page 148) shows that solution, in the form of a utility, SETBUS, contributed by STB BIOS guru Charles Marslett. SET BUS can force any VGA based on the Tseng Labs ET4000 chip into 16-bit mode even if a monochrome adapter is installed. Just run the utility, and your VGA will once again provide the unfettered 16 bit performance you enjoyed before you installed a monochrome adapter. Both John Bridges's VIDSPEED and my Zen timer measure raw memory speed on the ET4000-based VGA in my dual-monitor system at 4.3 times faster after SETBUS 16 than it normally is. Before you get too excited, bear in mind that the improvement you'll actually see with real-world applications will vary from one VGA-based package to another, depending on how intensively display memory is accessed and whether word operands are used, and will generally be less sometimes much less than four times. Windows, for example, clearly spends most of its time doing things other than accessing display memory; it's visibly faster after SETBUS 16, but not even two times as fast. Still, SETBUS makes all VGA software at least somewhat faster, and it's a lot cheaper than faster video hardware.
Is there a downside to SETBUS? There sure is. When SETBUS 16 is in effect, your monochrome screen will do screwy things whenever you access it, because the VGA interferes with those memory accesses. I can't even guarantee that you won't damage something if you use the monochrome adapter while SETBUS 16 is in effect, although I've been doing that myself with no problems. In short, use SETBUS at your own risk.
So what good is SETBUS if if means you can't use your monochrome adapter? Oh, you can still use your monochrome adapter just fine, you just can't get 16-bit VGA at the same time. The trick is to use batch files so that you get 16-bit VGA when you need it, and a ftinctional monochmme display when vou need that; that is, use batch files to put your VGA in the right state at the right time. For example. you could put SETBUS 16 at the start of the batch files you use to start Windows and other color display-only programs, and SETBUS 8 at the end; that way, graphics programs would run at full speed, but the monochrome adapter would still work fine the rest of the time.
Yes, SETBUS is a bit of a nuisance, but it's worth it; what's the point of paying for a 16-bit VGA if it's always an 8-bit VGA? SETBUS isn't perfect, but it's given me back the full graphics performance of my system, and it'll do just fine u ntil someone comes out with a 16-bit monochrome adapter.
Thanks, Charles!
Tom Moran, of Saratoga, Calif., decided to port the X-Sharp 3-D antmatton package we've been developing over the past four months to Ada, and caught three bugs in the process. Two of the bugs have no effect, but the third is significant, because it's a bug in the matrix concatenation code. This bug shows up only when the concatenation involves a translation as well as a rotation, but when that happens, things go bad in a hurry. The bug rears its ugly head when performing translation from world space to view space; I didn't catch it myself because I'd performed only rotation to view space, not translation. In any case, Listing One from last month fixes this problem (I snuck the fix in at the last minute), and the current distribution version of X-Sharp fixes all known bugs.
X-Sharp is available as the file X-SHARPn.ARC in the DDJ Forum on CompuServe, on M&T Online, and in the graphic.disp conference on Bix. Alternatively, you can send me a 360K or 720K formatted diskette and an addressed, stamped diskette mailer, care of DDJ 411 Borel Ave., San Mateo, CA 94402.,and I'll send you the latest copy of X-Sharp. There's no charge, but it'd be very much appreciated if you'd slip in a dollar or so to help out the folks at the Vermont Association for the Blind and Visually Impaired. I'm available on a daily basis to discuss X-Sharp on M&T Online and Bix (user name mabrash in both cases).
Bill Lindley, of Mesa, Ariz., wrote to suggest that when programming the VGA to a nonstandard mode such as the 640x400 page-flipped 16-color mode I discussed in the December column, it's a good idea to tell the BIOS about the new screen size, for a couple of reasons. For one thing, pop-up utilities often use the BIOS variables; Bill's memory-resident screen printer, EGAD Screen Print, determines the number of scan lines to print by multiplying the BIOS "number of text rows" variable times the "character height" variable. For another, the BIOS itself may do a poor job of displaying text if not given proper information; the active text area may not mawh the screen dimensions, or an inappropriate graphics font may be used. (Of course, the BIOS isn't going to be able to display text anyway in highly nonstandard modes such as mode x, but it will do fine in slightly nonstandard modes such as 640x400 16-color mode.) In the case of the 640x400 16-color model discussed in December, Bill suggests that the code in Listing Two (page 148) be called immediately after putting the VGA into that mode, in order to tell the BIOS that we're working with 25 rows of 16-pixel-high text. I think this is an excellent suggestion; it can't hurt, and may save you from getting aggravating tech support calls down the road.
Performance whiz David Stafford, of Borland Japan, sent along the strange but effective idea of bitblt compiling. Bitblts, as you likely know, are operations that combine parts of one or more source bitmaps and a destination bitmap, using logical operations such as AND, OR, and replace. Bitblts are at the core of bitmapped windowing graphics, and therefore deserving of considerable attention to performance.
Normally, a standard, two-operand bitblt is processed by picking up each source byte in turn, processing it if necessary (for example, for transparency or monochrome-to-color expansion), and combining it appropriately with the destination. The processing for transparency or color expansion can take a fair amount of time, and even operations such as straight replace require that the source be read, which takes at least some time.
Now imagine this. You, the programmer, have an 8x8 monochrome icon that you'll repeatedly draw, color-expanded, with transparency. (That is, 1 bits in the icon turn into the foreground color, which is then drawn to the destination, and 0 bits in the icon cause the destination to be preserved.) You could do this with code such as that in Listing Three (page 148), which color expands, checks for transparency, and draws in a single step, as shown in Figure 1. That works fine, but something seems a little out of kilter from a performance perspective, because the color expansion and transparency check are done exactly the same way every time the icon is drawn. Why do all that work n times rather than once?
The compiled bitblt alternative, which does expansion and transparency just once, is shown in Listing Four (page 150). Function CompileReplaceXpar() turns the icon's data not into other data, but rather into code that performs a bitblt with the transparent replace raster op. In other words, this function compiles the icon's data, together with the raster op (replace), the color expansion, and the need for transparency, into code that does exactly what a standard blt would have done, as shown in Figure 2. Function ExecuteCompiled() then executes the compiled code and produces precisely the same results as the equivalent blt. There's one important difference, though: ExecuteCompiled() doesn't have to do any testing, branching, or even reading of the source, so it's much faster than Listing Three, three times faster, in fact, when the sample test shown in Listing Five (page 150) is run on a fast 16-bit VGA. Listing Four could be optimized further in a number of ways, such as rewriting the bitblt compiler function in assembler, putting the compiled code in the code segment to avoid far branches, and using 16-bit MOVs and 0- or 1-byte addressing displacements whenever possible. For now, though. I just want to give you a taste of the power of compiled bitblts--and a three-times speed-up should do the trick.
Usually, it pays to turn code into data, in the form of jump tables, lookup tables, state machines, and the like. Occasionally, though, it pays to turn data into code, as in the case of compiled bitblts. Strange concept, impressive results.
If you want a broad understanding of the math that underlies computer graphics, I highly recommend Mathematical Elements for Computer Graphics, Second Edition, by David F. Rogers and J. Alan Adams (McGraw-Hill, 1990, ISBN 0-07-053529-9). Unlike Foley and van Dam's Computer Graphics, this is not an encyclopedic graphics reference, nor does it mean to be; rather, it pulls together the mathematical theory behind several fundamental areas of computer graphics. After the traditional and largely pointless first chapter on graphics hardware, the book covers two-dimensional transformations, three-dimensional transformations, plane curves, space curves, and surface description and generation, all in a straightforward and thorough fashion. This is not light reading, although I found it easier going than Foley and van Dam; the tone is that of a textbook (albeit without exercises for the reader), and an amazing volume of information is dispensed, in the form of clear, concise explanations and examples, over the course of about 500 pages. Particularly noteworthy are the 130 pages on space curves, including Béziers and B-splines, and the 100 pages on surfaces. In short, this book is an excellent and serious introduction to the mathematics of computer graphics.
Next month, we'll do some more 3-D animation, and maybe something else as well. There's way more in the topic backlog than I'll ever have room to cover in this column, so please write and let me know what you'd like to see most. Don't follow the lead of Gonzalo Medina, though, who wrote me from Venezuela in Spanish. Although I had six years of Spanish in high school, I can't read it for beans. So call me Mr. Potato Head, if you want--but write me in English.
Copyright © 1992, Dr. Dobb's Journal16-bit VGA and a Monochrome Screen
X-Sharp Bug Fixes
Keep the BIOS Informed
Bifblt Compiling
Suggested Reading
Next Time
_GRAPHICS PROGRAMMING COLUMN_
by Michael Abrash
[LISTING ONE]<a name="012b_000b">
/* Utility to force an ET4000-based VGA into 16- or 8-bit operation even if
a monochrome adapter is in the system. (Note that only 16-bit memory access,
not 16-bit I/O, is enabled; the I/O state is not altered.) The monochrome
adapter won't work properly while SETBUS 16 is in effect. Tested with
Borland C++ 3.0. Courtesy of Charles Marslett of STB. Commented and
reformatted by Michael Abrash. */
/***************************************************************************
* This utility isn't known to cause problems, but use it at your own risk, as
* the monochrome and VGA adapters will both respond to accesses to monochrome
* display memory while SETBUS 16 is in effect, resulting in bus contention.
**************************************************************************/
#include <dos.h>
#include <stdio.h>
#include <string.h>
void main(int argc, char *argv[])
{
int crtc, val;
union REGS regset;
if (inp(0x3CC) & 0x01) /* decide where to address the CRT */
crtc = 0x3D4; /* Controller by reading the I/O */
else /* Address Select bit of the */
crtc = 0x3B4; /* Miscellaneous Output register */
outportb(0x3BF, 0x03); /* key sequence to enable access to */
outportb(crtc+4, 0xA0); /* ET4000-specific registers */
outportb(crtc, 0x36); /* get the current setting of the Video */
val = inp(crtc+1); /* System Configuration 1 register */
/* Decide whether 16- or 8-bit access desired, and configure accordingly */
if (argc == 2) {
if (strcmp(argv[1], "16") == 0) {
outportb(crtc+1, val | 0x40); /* 16-bit memory access */
goto ModeSet;
} else if (strcmp(argv[1], "8") == 0) {
outportb(crtc+1, val & 0xBF); /* 8-bit memory access */
ModeSet:
regset.x.ax = 0x0003;
int86(0x10, ®set, ®set); /* do a text mode mode set */
exit(0);
}
}
fprintf(stderr, "Usage: SETBUS 16\n");
fprintf(stderr, " or SETBUS 8\n");
exit(1);
}
<a name="012b_000c">
<a name="012b_000d">[LISTING TWO]<a name="012b_000d">
/* Function to tell the BIOS to set up properly sized characters for 25 rows of
16 pixel high text in 640x400 graphics mode. Call immediately after mode set.
Based on a contribution by Bill Lindley. */
#include <dos.h>
void Set640x400()
{
union REGS regs;
regs.h.ah = 0x11; /* character generator function */
regs.h.al = 0x24; /* use ROM 8x16 character set for graphics */
regs.h.bl = 2; /* 25 rows */
int86(0x10, ®s, ®s); /* invoke the BIOS video interrupt
to set up the text */
}
<a name="012b_000e">
<a name="012b_000f">[LISTING THREE]<a name="012b_000f">
/* Draws the 8x8 monochrome icon pointed to by IconPtr at coordinates (X,Y) in
the DestWidth-wide bitmap starting at DestSeg:0, using the transparent
replace raster op and color Color. Destination bitmap must be an
8-bit-per-pixel bitmap. 1-bits in the pattern are converted to drawing color
and drawn, and 0-bits are skipped over, preserving destination (that is, are
transparent). Tested with Borland C++ 3.0; when USE_C is 0, uses
BC++ dependent inline assembly. */
#define USE_C 0 /* set to 1 to compile C code, 0 to compile assembler */
#if !USE_C
#pragma inline /* tell the compiler there's inline ASM code */
#else
#include <dos.h>
#endif
void DrawReplaceXpar(unsigned int X, unsigned int Y,
unsigned int DestSeg, unsigned int DestWidth,
unsigned int Color, unsigned char *IconPtr)
{
#if USE_C
unsigned char far *ScreenPtr, Temp;
int i,j;
/* Point to the first destination pixel */
ScreenPtr = MK_FP(DestSeg, Y*DestWidth+X);
for (i=0; i<8; i++) { /* do the 8 icon rows */
Temp = *IconPtr++; /* get the next icon row */
for (j=0; j<8; j++) { /* do the 8 pixels per icon row */
if (Temp & 0x80) /* draw this pixel if the */
*ScreenPtr = Color; /* corresponding icon bit is 1 */
ScreenPtr++; /* point to the next destination pixel */
Temp <<= 1; /* shift the next icon bit into place */
}
/* Point to the start of the next row */
ScreenPtr += DestWidth - 8;
}
#else
asm cld /* make LODSB increment SI */
asm mov es,DestSeg /* point ES to the bitmap */
asm mov ax,Y
asm mov bx,DestWidth
asm mul bx /* DestWidth*Y+X = offset of first */
asm add ax,X /* dest pixel */
asm mov di,ax /* point ES:DI to the first dest pixel */
asm mov si,IconPtr /* point DS:SI to the first icon byte */
asm mov dx,8 /* we'll do 8 rows */
asm mov ah,byte ptr Color /* color we'll draw with */
asm sub bx,8 /* offset from end of one dest row to start of next */
RowLoop:
asm lodsb /* get the next icon row */
asm mov cx,8 /* we'll do 8 pixels on each row */
PixelLoop:
asm shl al,1 /* shift the next icon bit into CF */
asm jnc NoDraw /* bit is 0, so don't draw */
asm mov es:[di],ah /* bit is 1, so draw this pixel */
NoDraw:
asm inc di /* point to the next destination pixel */
asm loop PixelLoop /* do the next pixel */
asm add di,bx /* point to the start of the next dest row */
asm dec dx /* count down rows */
asm jnz RowLoop /* do the next row */
#endif
}
<a name="012b_0010">
<a name="012b_0011">[LISTING FOUR]<a name="012b_0011">
/* Compiled bitblit code for drawing the 8x8 monochrome icon pointed to by
IconPtr at coordinates (X,Y) in the DestWidth-wide bitmap starting at
DestSeg:0, using the transparent replace raster op and color Color.
CompileReplaceXpar() generates code to perform desired bitblit, and
ExecuteCompiled() executes that code to perform bitblit. Generally faster than
a standard approach when drawing the same icon many times, because this way
color expansion, transparency, and reading the source are only performed once,
at expansion time, rather than every time an icon is drawn. Destination bitmap
must be an 8-bit-per-pixel bitmap. 1-bits in pattern are converted to drawing
color and drawn, and 0-bits are skipped over, preserving destination (that is,
are transparent). Tested with Borland C++ 3.0; uses BC++ dependent inline
assembly. */
#pragma inline /* tell the compiler there's inline ASM code */
/* Generates far-callable code to bitblit the specified icon, and stores code
in BufferToCompileInto. Code is simply a series of MOV [DI+xxxx],AL
instructions, where xxxx is the offset from upper left corner of icon of
each pixel to be drawn. */
void CompileReplaceXpar(unsigned int DestWidth,
unsigned char *IconPtr, unsigned char *BufferToCompileInto)
{
unsigned int i, j, PixelOffset = 0;
unsigned char Temp;
for (i=0; i<8; i++) { /* do the 8 icon rows */
Temp = *IconPtr++; /* get the next icon row */
for (j=0; j<8; j++) { /* do the 8 pixels per icon row */
if (Temp & 0x80) { /* generate the code to draw this pixel if the
corresponding icon bit is 1. Code is the hex bytes
for the instruction MOV [DI+PixelOffset],AL */
*BufferToCompileInto++ = 0x88; /* MOV opcode */
*BufferToCompileInto++ = 0x85; /* mod-reg-rm byte */
*((unsigned int *)BufferToCompileInto)++ = PixelOffset;
/* addressing displacement */
}
PixelOffset++; /* point to the next destination pixel */
Temp <<= 1; /* shift the next icon bit into place */
}
/* Point to the start of the next row in the destination */
PixelOffset += DestWidth - 8;
}
/* Put a RET at the end to return to the calling code, and done */
*BufferToCompileInto = 0xCB; /* RETF instruction = 0xCB */
}
void ExecuteCompiled(unsigned int X, unsigned int Y,
unsigned int DestSeg, unsigned int DestWidth, unsigned int Color,
unsigned char far *BufferToExecute)
{
asm push ds /* preserve the default data segment */
asm mov ds,DestSeg /* point ES to the bitmap */
asm mov ax,Y
asm mul word ptr DestWidth /* DestWidth*Y+X = offset of */
asm add ax,X /* first dest pixel */
asm mov di,ax /* point ES:DI to the first dest pixel */
asm mov al,Color /* color with which to draw */
asm call dword ptr BufferToExecute
/* perform a far call to execute the
compiled bitblit code, and done */
asm pop ds /* restore the default data segment */
}
<a name="012b_0012">
<a name="012b_0013">[LISTING FIVE]<a name="012b_0013">
/* Sample program to tile screen with an 8x8 monochrome icon.
Tested with Borland C++ 3.0. */
#include <dos.h>
#include <conio.h>
#define USE_COMPILED_BITBLITS 1 /* set to 1 and link to Listing 4 to use
compiled biblits, set to 0 and link to
Listing 3 to use conventional bitblits */
#define SCREEN_WIDTH 320
#define SCREEN_HEIGHT 200
#define SCREEN_SEGMENT 0xa000
#if USE_COMPILED_BITBLITS
extern void CompileReplaceXpar(unsigned int, unsigned char *, unsigned char *);
extern void ExecuteCompiled(unsigned int, unsigned int, unsigned int,
unsigned int, unsigned int, unsigned char far *);
#else
extern void DrawReplaceXpar(unsigned int, unsigned int,
unsigned int, unsigned int, unsigned int, unsigned char *);
#endif
static unsigned char TestIcon[8] =
{0x88, 0x44, 0x22, 0x11, 0x11, 0x22, 0x44, 0x88};
#if USE_COMPILED_BITBLITS
/* Storage for the compiled icon-drawing code; must be large enough for the
largest possible code size, because no error checking is performed */
static unsigned char CompiledBuffer[1000];
#endif
void main()
{
unsigned int x, y;
union REGS regset;
#if USE_COMPILED_BITBLITS
unsigned char far *CompiledBufferPtr;
#endif
regset.x.ax = 0x0013; /* AL = 0x13 selects 320x200 */
int86(0x10, ®set, ®set); /* 256-color graphics mode */
#if USE_COMPILED_BITBLITS
/* Generate the code for drawing the icon with the transparent
replace raster op, and store the code in CompiledBuffer */
CompileReplaceXpar(SCREEN_WIDTH, TestIcon, CompiledBuffer);
CompiledBufferPtr = MK_FP(_DS, CompiledBuffer);
#endif
/* Tile TestIcon over the entire screen */
for (y=0; y<SCREEN_HEIGHT; y += 8) {
for (x=0; x<SCREEN_WIDTH; x += 8) {
#if USE_COMPILED_BITBLITS
/* Draw the icon by executing the code in CompiledBuffer */
ExecuteCompiled(x, y, SCREEN_SEGMENT, SCREEN_WIDTH, 14,
CompiledBufferPtr);
#else
/* Draw the icon with the transparent replace raster op, color
expanding it and handling transparency on the fly */
DrawReplaceXpar(x, y, SCREEN_SEGMENT, SCREEN_WIDTH, 14,TestIcon);
#endif
}
}
getch(); /* wait for a key press */
regset.x.ax = 0x0003; /* AL = 3 selects 80x25 text mode */
int86(0x10, ®set, ®set); /* return to text mode */
exit(1); /* done */
}
