Journal: Dr. Dobb's Journal Dec 1991 v16 n12 p131(8) ----------------------------------------------------------------------------- Title: Catching up. (Graphics Programming) (Column) Author: Abrash, Michael. AttFile: Program: GP-DEC91.ASC Antialiasing & Sierra Hicolor. Abstract: Various topics discussed in previous columns are re-examined. The author was criticized for using non-standard terminology to describe polygons in several columns. Three categories are defined in the X-Window System: complex, nonconvex and convex; each is a specialized subset of the preceding one. The X Window System names were used to describe the types of polygons that can be drawn with each of the polygon filling techniques, but the names do not accurately describe the diverse types of polygons that the techniques can draw. Turbo Debugger is one of the most popular debuggers in use, but it messes with the VGA's registers when it gets control, even when it is run on a monochrome screen and the application is run on a color screen. Turbo Debugger cannot debug page flipping, among other types of graphics; solutions to this problem are described. ----------------------------------------------------------------------------- Descriptors.. Product: Turbo Debugger (Program development software) (Usage). Topic: Graphics Software Programming Instruction Program Development Techniques Software Design Debugging Tools X Windows (Standard) VGA Standard High Resolution Program Development Software. Feature: illustration program chart. ----------------------------------------------------------------------------- Full Text: It's been nigh on a year now since I started this column, and it's time to catch up on some interesting odds and ends that I've been unsuccessfully trying to squeeze in for the better part of that time. No, I haven't forgotten that I said I'd start in on 3-D animation this month, but it's been put off until next month. Now, calm down; I know I promised, it's just that these things take time to do properly; you wouldn't want me to start off prematurely and end up with, God forbid, slow 3-D animation, would you? Don't send nasty letters; I'll get to it next month, honest I will. The funny thing of it is, 3-D perspective drawing is basically pretty easy. Shading (at least in its simpler aspects) is relatively easy, too. Even hidden surface handling isn't bad--given lots of memory and processor power. The memory is easy enough to come by in 386 protected mode, but the processor power isn't. We're talking major silicon here, Intel i860s or, better yet, Crays; 386s don't cut the mustard, so some sleight of hand is in order. Fixed point arithmetic can replace floating point. Table look-ups can stand in for excruciatingly slow sine and cosine functions. Fast, approximate antialiasing can be used instead of precise but slow techniques. The real trick, though, is some combination of restrictions and techniques that allows real-time hidden surface removal. There are at least a dozen ways to remove hidden surfaces, but the fast ones don't always work, and the ones that always work are slow. Workstations deal with this by using dedicated hardware to perform z-buffering, or by applying MIPS by the bushel to sorting, or the like. Because we can't do any of that, I'm still pondering the best way to wring real-time hidden surface handling out of a 386. So, this month, catching up; next month, 3-D animation. If I bug out again next month, then write nasty letters. At least I'll know you care. Nomenclature Blues Bill Huber wrote to take me to task--and a well-deserved kick in the fanny it was, I might add--for my use of non-standard terminology in describing polygons in February, March, and June columns. The X-Window System defines three categories of polygons: complex, nonconvex, and convex. These three categories, each a specialized subset of the preceding category, not-so-coincidentally map quite nicely to three increasingly fast polygon filling techniques. Therefore, I used the XWS names to describe the sorts of polygons that can be drawn with each of the polygon filling techniques. The problem is that those names don't accurately describe all the sorts of polygons that the techniques are capable of drawing. Convex polygons are those for which no interior angle is greater than 180 degrees. The "convex" drawing approach described in February and March actually handles a number of polygons that are not convex; in fact, it can draw any polygon through which no horizontal line can be drawn that intersects the boundary more than twice. (In other words, the boundary reverses Y direction exactly twice, disregarding polygons that have degenerated into horizontal lines, which I'm going to ignore.) Bill was kind enough to send me the pages out of Computational Geometry, An Introduction (Springer-Verlag, 1988) that describe the correct terminology; such polygons are, in fact, "monotone with respect to a vertical line" (which unfortunately makes a rather long #define variable). Actually, to be a tad more precise, I'd call them "monotone with respect to a vertical line and simple," where "simple" means "not self-intersecting." Similarly, the polygon type I called "nonconvex" is actually "simple," and I suppose what I called "complex" should be referred to as "nonsimple," or maybe just "none of the above." This may seem like nit-picking, but actually, it isn't; what it's really about is the tremendous importance of having a shared language. In one of his books, Richard Feynman describes having developed his own mathematical framework, complete with his own notation and terminology, in high school. When he got to college and started working with other people who were at his level, he suddenly understood that people can't share ideas effectively unless they speak the same language; otherwise, they waste a great deal of time on misunderstandings and explanation. Or, as Bill Huber put it, "You are free to adopt your own terminology when it suits your purposes well. But you risk losing or confusing those who could be among your most astute readers--those who already have been trained in the same or a related field." Ditto. Likewise. D'accord. and mea culpa; I shall endeavor to watch my language in the future. Nomenclature in Action Just to show you how much different proper description and interchange of ideas can be, consider the case of identifying convex polygons. Several months back, a nonfunctional method for identifying such polygons--checking for exactly two X direction changes and two Y direction changes around the perimeter of the polygon--crept into this column by accident. That method, as I have since noted, does not work. Still, a fast method of checking for convex polygons would be highly desirable, because such polygons can be drawn with the fast code from the March column, rather than the relatively slow, general-purpose code from the June column. Now consider Bill's point that we're not limited to drawing convex polygons in our "convex fill" code, but can actually handle any simple polygon that's monotone with respect to a vertical line. Additionally, consider Anton Treuenfels's point, made back in the August column, that life gets simpler if we stop worrying about which edge of a polygon is the left edge and which is the right, and instead just scan out each raster line starting at whichever edge is left-most. Now, what do we have? What we have is an approach passed along by Jim Kent, of Autodesk Animator fame. If we modify the low-level code to check which edge is left-most on each scan line and start drawing there, as just described, then we can handle any polygon that's monotone with respect to a vertical line regardless of whether the edges cross. (I'll call this "monotone-vertical" from now on; if anyone wants to correct that terminology, jump right in.) In other words, we can then handle nonsimple polygons that are monotone-vertical; self-intersection is no longer a problem. Then, we just scan around the polygon's perimeter looking for exactly two direction reversals along the Y axis only, and if that proves to be the case, we can handle the polygon at high speed. Figure 1 shows polygons that can be drawn by a monotone-vertical capable filler; Figure 2 shows some that cannot. Listing One (page 149) shows code to test whether a polygon is appropriately monotone. This test lends itself beautifully to assembly language implementation, because it's basically nothing but pointers and conditionals; unfortunately, I don't have room for an assembly version this month, but translation from Listing One is pretty straight-forward, should you care to do so yourself. Listing Two and Three (page 149) are variants of the fast convex polygon fill code from March, modified to be able to handle all monotone-vertical polygons, including nonsimple ones; the edge-scanning code (Listing Four from March) remains the same, and so is not shown here. Listing Four (page 150) shows the changes needed to convert Listing One from June to employ the vertical-monotone detection test and use the fast vertical-monotone drawing code whenever possible; note that Listing Five from June is also required in order for this code to link. Listing Five (page 150) this month is the latest version of the polygon.h header file. Is monotone-vertical polygon detection worth all this trouble? Under the right circumstances, you bet. In a situation where a great many polygons are being drawn, and the application either doesn't know whether they're monotone-vertical or has no way to tell the polygon filler that they are, performance can be increased considerably if most polygons are, in fact, monotone-vertical. This potential performance advantage is helped along by the surprising fact that Jim's test for monotone-vertical status is simpler and faster than my original, non-functional test for convexity. See what accurate terminology and effective communiation can do? Graphics Debugging with Turbo Debugger I don't know what debugger you use, but I'd be willing to wager that more of you than not use the same one I do, Turbo Debugger. It's powerful, the interface is good (although arguably it lost some ease of use in the transition to mouse support and CUA compatibility), and it's obviously the debugger of choice if you're using a Borland compiler. I would be remiss, however, if I failed to warn you of a serious problem with TD when it comes to debugging graphics programs. The problem, simply put, is that TD mucks about with the VGA's registers when it gets control, even when you're running TD on a monochrome screen and your app on a color screen, courtesy of the -do switch. Although TD has no business fooling around with the VGA's registers in that case, seeing as how it's not using the color screen, that's not the problem; the problem is that when TD resumes execution of the app, it doesn't put all the VGA's registers back the way it found them. Given that the VGA's registers are readable, this inteference is unnecessary; it's also unfortunate, because it makes it impossible to debug some kinds of graphics with TD without a second computer available. What sorts of graphics can't TD debug? Page flipping, for one; when it gets control, TD seems to force the start address of the displayed portion of the bitmap back to 0, thereby displaying page 0 whether you like it or not. Setting VGA registers manually via the I/O feature in the CPU window is also intefered with; often, hand-entered register settings just don't stick. Mode X (320x240, 256 colors, as discussed in the July through September columns) is messed up quite royally at times; some of the nonstandard register settings required to create mode X are apparently undone. There may be other problems, but those I've mentioned are enough to limit TD's ability to debug many sorts of graphics, especially animation. There is a solution, as it happens: Get another computer, run a serial link from your main to the second computer, and debug your programs running on that system via TDREMOTE. When running in remote mode, TD doesn't mess with any registers, and becomes an ideal graphics debugging tool. The downside, of course, is that you have to have a second computer; also, TDREMOTE is slower in almost every respect than TD. Hi-Res VGA Page Flipping This is one of those odd little items that might come in handy someday. The background is this: On a standard VGA, hi-res mode is mode 12h, which offers 640x480 resolution with 16 colors. That's a nice mode, with plenty of pixels, and square ones at that, but it lacks one thing--page flipping. The problem is that the mode 12h bitmap is 144 Kbytes in size, and the VGA has only 256 Kbytes total, too little memory for two of those monster mode 12h pages. With only one page, flipping is obviously out of the question, and without page flipping, top-flight, hi-res animation can't be implemented. The standard fallback is to use the EGA's hi-res mode, mode 10h (640x350, 16 colors) for page flipping, but this mode is less than ideal for a couple of reasons: It offers sharply lower vertical resolution, and it's lousy for handling scaled-up CGA graphics, because the vertical resolution is a fractional multiple--1.75 times, to be exact--of that of the CGA. CGA resolution may not seem important these days, but many images were originally created for the CGA, as were many graphics packages and games, and it's at least convenient to be able to handle CGA graphics easily. There are a couple of interesting, if imperfect, solutions to the problem of hi-res page flipping. One is to use the split screen to enable page flipping only in the top two-thirds of the screen; see "VGA Split-Screen Animation," in the June, 1991 issue of PC Techniques, for details (and for details on the mechanics of page flipping, as well). This doesn't address the CGA problem, but it does yield square pixels and a full 640x480 screen resolution, although not all those pixels are flippable. A second solution is to program the screen to a 640x400 mode. such a mode uses almost every byte of display memory (64,000 bytes, actually; you could add another few lines, if you really wanted to), and thereby provides the highest resolution possible on the VGA for a fully page-flipped display. It maps well to CGA resolutions, being either identical or double in both dimensions. As an added benefit, it offers an easy-on-the-eyes 70-Hz frame rate, as opposed to the 60 Hz that is the best that mode 12h can offer, due to the design of standard VGA monitors. Best of all, perhaps, is that 640x400 16-color mode is easy to set up. The key to 640x400 mode is understanding that on a VGA, mode 10h (640x350) is, at heart, a 400-scan-line mode. What I mean by that is that in mode 10h, the Vertical Total register, which controls the total number of scan lines, both displayed and nondisplayed, is set to 447, exactly the same as in the VGA's text modes, which do in fact support 400 scan lines. A properly sized and centered display is achieved in mode 10h by setting the polarity of the sync pulses to tell the monitor to scan vertically at a faster rate (to make fewer lines fill the screen), by starting the overscan after 350 lines, and by setting the vertical sync and blanking pulses appropriately for the faster vertical scanning rate. Changing those settings is all that's required to turn mode 10h into a 640x400 mode, and that's easy to do, as illustrated by Listing Six (page 150), which provides mode set code for 640x400 mode. In 640x400, 16-color mode, page 0 runs from offset 0 to offset 31,999 (7CFFh), and page 1 runs from offset 32,000 (7D00h) to 63,999 (0F9FFh). Page 1 is selected by programming the Start Address registers (CRTC registers 0Ch, the high 8 bits, and 0Dh, the low 8 bits) to 7D00h. Actually, because the low byte of the start address is 0 for both pages, you can page flip simply by writing 0 or 7Dh to the Start Address High register (CRTC register 0Ch); this has the benefit of eliminating a nasty class of potential synchronization bugs that can arise when both registers must be set. Listing Seven (page 150) illustrates simple 640x480 page flipping. The 640x400 mode isn't exactly earth-shaking, but it can come in handy for page flipping and CGA emulation, and I'm sure that some of you will find it useful at one time or another. Modifying VGA Registers EGA registers are not readable. VGA registers are readable. This revelation will not come as news to most of you, but many programmers still insist on setting entire VGA registers even when they're modifying only selected bits, as if they were programming the EGA. This comes to mind because I recently received a query inquiring why write mode 1 (in which the contents of the latches are copied directly to display memory) didn't work in mode X. Actually, write mode 1 does work in mode X; it didn't work when this particular correspondent enabled it because he did so by writing the value 01h to the Graphics Mode register. As it happens, the write mode field is only one of several fields in that register, as shown in Figure 3. In 256-color modes, one of the other fields--bit 6, which enables 256-color pixel formatting--is not 0, and setting it to 0 messes the screen up quite thoroughly. The correct way to set a field within a VGA register is, of course, to read the register, mask off the desired field, insert the desired setting, and write the result back to the register. In the case of setting the VGA to write mode 1, consult Example 1. This approach is more of a nuisance than simply setting the whole register, but it's safer. It's also slower; for cases where you must set a field repeatedly, it might be worthwhile to read and mask the register once at the start, and save it in a variable, so that the value is readily available in memory and need not be repeatedly read from the port. This approach is especially attractive because INs are much slower than memory accesses on 386 and 486 machines. Astute readers may wonder why I didn't put a delay sequence, such as JMP $+2, between the IN and OUT involving the same register. There are, after all, guidelines from IBM specifying that a certain period should be allowed to elapse before a second access to an I/O port is attempted, because not all devices can respond as rapidly as a 286 or faster chip can access a port. My answer is that while I can't guarantee that a delay isn't needed, I've never found a VGA that required one; I suspect that the delay specification has more to do with motherboard chips such as the timer, the interrupt controller, and the like, and I sure hate to waste the delay time if it's not necessary. However, I've never been able to find anyone with the definitive word on whether delays might ever be needed when accessing VGAs, so if you know the gospel truth, or if you know of a VGA/processor combo that does require delays, please drop me a line. You'd be doing a favor for a whole generation of graphics programmers who aren't sure whether they're skating on thin ice without delays.