Catching up (various topics re-examined)

 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.

 [BACK] Back

Discuss this article in the forums


Date this article was posted to GameDev.net: 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Michael Abrash's Articles

© 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!