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
See Also: © 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
|