GRAPHICS PROGRAMMING
CATCHING UP
Michael Abrash
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 unsuccesfully 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.
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 terminolgy in describing polygons in the 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 Hubert 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.
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. Listings 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, nonfunctional test for convexity.
See what accurate terminology and effective communication can do?
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 interference 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 interfered 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 system 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.
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 earthshaking, 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.
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 this ice without delays.
Copyright © 1991, Dr. Dobb's JournalNomenclature Blues
Nomenclature in Action
Graphics Debugging with Turbo Debugger
Example 1: The proper sequence for setting write mode 1
mov dx,3ceh ;Graphics Controller Index
mov al,5 ;Graphics Mode reg index
out dx,al ;point GC index to G_MODE
inc dx ;Graphics Controller Data
in al,dx ;get current mode setting
and al,not 3 ;mask off write mode field
or a1,1 ;set write mode field to 1
out dx,a1 ;set write mode 1
Hi-Res VGA Page Flipping
Modifying VGA Registers
_GRAPHICS PROGRAMMING COLUMN_
by Michael Abrash
[LISTING ONE]<a name="02a8_000b">
/* Returns 1 if polygon described by passed-in vertex list is monotone with
respect to a vertical line, 0 otherwise. Doesn't matter if polygon is simple
(non-self-intersecting) or not. Tested with Borland C++ 2 in small model. */
#include "polygon.h"
#define SIGNUM(a) ((a>0)?1:((a<0)?-1:0))
int PolygonIsMonotoneVertical(struct PointListHeader * VertexList)
{
int i, Length, DeltaYSign, PreviousDeltaYSign;
int NumYReversals = 0;
struct Point *VertexPtr = VertexList->PointPtr;
/* Three or fewer points can't make a non-vertical-monotone polygon */
if ((Length=VertexList->Length) < 4) return(1);
/* Scan to the first non-horizontal edge */
PreviousDeltaYSign = SIGNUM(VertexPtr[Length-1].Y - VertexPtr[0].Y);
i = 0;
while ((PreviousDeltaYSign == 0) && (i < (Length-1))) {
PreviousDeltaYSign = SIGNUM(VertexPtr[i].Y - VertexPtr[i+1].Y);
i++;
}
if (i == (Length-1)) return(1); /* polygon is a flat line */
/* Now count Y reversals. Might miss one reversal, at the last vertex, but
because reversal counts must be even, being off by one isn't a problem */
do {
if ((DeltaYSign = SIGNUM(VertexPtr[i].Y - VertexPtr[i+1].Y))
!= 0) {
if (DeltaYSign != PreviousDeltaYSign) {
/* Switched Y direction; not vertical-monotone if
reversed Y direction as many as three times */
if (++NumYReversals > 2) return(0);
PreviousDeltaYSign = DeltaYSign;
}
}
} while (i++ < (Length-1));
return(1); /* it's a vertical-monotone polygon */
}
<a name="02a8_000c">
<a name="02a8_000d">[LISTING TWO]<a name="02a8_000d">
/* Color-fills a convex polygon. All vertices are offset by (XOffset, YOffset).
"Convex" means "monotone with respect to a vertical line"; that is, every
horizontal line drawn through the polygon at any point would cross exactly two
active edges (neither horizontal lines nor zero-length edges count as active
edges; both are acceptable anywhere in the polygon). Right & left edges may
cross (polygons may be nonsimple). Polygons that are not convex according to
this definition won't be drawn properly. (Yes, "convex" is a lousy name for
this type of polygon, but it's convenient; use "monotone-vertical" if it makes
you happier!)
*******************************************************************
NOTE: the low-level drawing routine, DrawHorizontalLineList, must be able to
reverse the edges, if necessary to make the correct edge left edge. It must
also expect right edge to be specified in +1 format (the X coordinate is 1 past
highest coordinate to draw). In both respects, this differs from low-level
drawing routines presented in earlier columns; changes are necessary to make it
possible to draw nonsimple monotone-vertical polygons; that in turn makes it
possible to use Jim Kent's test for monotone-vertical polygons.
*******************************************************************
Returns 1 for success, 0 if memory allocation failed */
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include "polygon.h"
/* Advances the index by one vertex forward through the vertex list,
wrapping at the end of the list */
#define INDEX_FORWARD(Index) \
Index = (Index + 1) % VertexList->Length;
/* Advances the index by one vertex backward through the vertex list,
wrapping at the start of the list */
#define INDEX_BACKWARD(Index) \
Index = (Index - 1 + VertexList->Length) % VertexList->Length;
/* Advances the index by one vertex either forward or backward through
the vertex list, wrapping at either end of the list */
#define INDEX_MOVE(Index,Direction) \
if (Direction > 0) \
Index = (Index + 1) % VertexList->Length; \
else \
Index = (Index - 1 + VertexList->Length) % VertexList->Length;
extern void ScanEdge(int, int, int, int, int, int, struct HLine **);
extern void DrawHorizontalLineList(struct HLineList *, int);
int FillMonotoneVerticalPolygon(struct PointListHeader * VertexList,
int Color, int XOffset, int YOffset)
{
int i, MinIndex, MaxIndex, MinPoint_Y, MaxPoint_Y;
int NextIndex, CurrentIndex, PreviousIndex;
struct HLineList WorkingHLineList;
struct HLine *EdgePointPtr;
struct Point *VertexPtr;
/* Point to the vertex list */
VertexPtr = VertexList->PointPtr;
/* Scan the list to find the top and bottom of the polygon */
if (VertexList->Length == 0)
return(1); /* reject null polygons */
MaxPoint_Y = MinPoint_Y = VertexPtr[MinIndex = MaxIndex = 0].Y;
for (i = 1; i < VertexList->Length; i++) {
if (VertexPtr[i].Y < MinPoint_Y)
MinPoint_Y = VertexPtr[MinIndex = i].Y; /* new top */
else if (VertexPtr[i].Y > MaxPoint_Y)
MaxPoint_Y = VertexPtr[MaxIndex = i].Y; /* new bottom */
}
/* Set the # of scan lines in the polygon, skipping the bottom edge */
if ((WorkingHLineList.Length = MaxPoint_Y - MinPoint_Y) <= 0)
return(1); /* there's nothing to draw, so we're done */
WorkingHLineList.YStart = YOffset + MinPoint_Y;
/* Get memory in which to store the line list we generate */
if ((WorkingHLineList.HLinePtr =
(struct HLine *) (malloc(sizeof(struct HLine) *
WorkingHLineList.Length))) == NULL)
return(0); /* couldn't get memory for the line list */
/* Scan the first edge and store the boundary points in the list */
/* Initial pointer for storing scan converted first-edge coords */
EdgePointPtr = WorkingHLineList.HLinePtr;
/* Start from the top of the first edge */
PreviousIndex = CurrentIndex = MinIndex;
/* Scan convert each line in the first edge from top to bottom */
do {
INDEX_BACKWARD(CurrentIndex);
ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
VertexPtr[PreviousIndex].Y,
VertexPtr[CurrentIndex].X + XOffset,
VertexPtr[CurrentIndex].Y, 1, 0, &EdgePointPtr);
PreviousIndex = CurrentIndex;
} while (CurrentIndex != MaxIndex);
/* Scan the second edge and store the boundary points in the list */
EdgePointPtr = WorkingHLineList.HLinePtr;
PreviousIndex = CurrentIndex = MinIndex;
/* Scan convert the second edge, top to bottom */
do {
INDEX_FORWARD(CurrentIndex);
ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
VertexPtr[PreviousIndex].Y,
VertexPtr[CurrentIndex].X + XOffset,
VertexPtr[CurrentIndex].Y, 0, 0, &EdgePointPtr);
PreviousIndex = CurrentIndex;
} while (CurrentIndex != MaxIndex);
/* Draw the line list representing the scan converted polygon */
DrawHorizontalLineList(&WorkingHLineList, Color);
/* Release the line list's memory and we're successfully done */
free(WorkingHLineList.HLinePtr);
return(1);
}
<a name="02a8_000e">
<a name="02a8_000f">[LISTING THREE]<a name="02a8_000f">
; Draws all pixels in list of horizontal lines passed in, in mode 13h, VGA's
; 320x200 256-color mode. Uses REP STOS to fill each line.
; ******************************************************************
; NOTE: is able to reverse the X coords for a scan line, if necessary to make
; XStart < XEnd. Expects whichever edge is rightmost on any scan line to be in
; +1 format; that is, XEnd is 1 greater than rightmost pixel to draw. if
; XStart == XEnd, nothing is drawn on that scan line.
; ******************************************************************
; C near-callable as:
; void DrawHorizontalLineList(struct HLineList * HLineListPtr, int Color);
; All assembly code tested with TASM 2.0 and MASM 5.0
SCREEN_WIDTH equ 320
SCREEN_SEGMENT equ 0a000h
HLine struc
XStart dw ? ;X coordinate of leftmost pixel in line
XEnd dw ? ;X coordinate of rightmost pixel in line
HLine ends
HLineList struc
Lngth dw ? ;# of horizontal lines
YStart dw ? ;Y coordinate of topmost line
HLinePtr dw ? ;pointer to list of horz lines
HLineList ends
Parms struc
dw 2 dup(?) ;return address & pushed BP
HLineListPtr dw ? ;pointer to HLineList structure
Color dw ? ;color with which to fill
Parms ends
.model small
.code
public _DrawHorizontalLineList
align 2
_DrawHorizontalLineList proc
push bp ;preserve caller's stack frame
mov bp,sp ;point to our stack frame
push si ;preserve caller's register variables
push di
cld ;make string instructions inc pointers
mov ax,SCREEN_SEGMENT
mov es,ax ;point ES to display memory for REP STOS
mov si,[bp+HLineListPtr] ;point to the line list
mov ax,SCREEN_WIDTH ;point to the start of the first scan
mul [si+YStart] ; line in which to draw
mov dx,ax ;ES:DX points to first scan line to draw
mov bx,[si+HLinePtr] ;point to the XStart/XEnd descriptor
; for the first (top) horizontal line
mov si,[si+Lngth] ;# of scan lines to draw
and si,si ;are there any lines to draw?
jz FillDone ;no, so we're done
mov al,byte ptr [bp+Color] ;color with which to fill
mov ah,al ;duplicate color for STOSW
FillLoop:
mov di,[bx+XStart] ;left edge of fill on this line
mov cx,[bx+XEnd] ;right edge of fill
cmp di,cx ;is XStart > XEnd?
jle NoSwap ;no, we're all set
xchg di,cx ;yes, so swap edges
NoSwap:
sub cx,di ;width of fill on this line
jz LineFillDone ;skip if zero width
add di,dx ;offset of left edge of fill
test di,1 ;does fill start at an odd address?
jz MainFill ;no
stosb ;yes, draw the odd leading byte to
; word-align the rest of the fill
dec cx ;count off the odd leading byte
jz LineFillDone ;done if that was the only byte
MainFill:
shr cx,1 ;# of words in fill
rep stosw ;fill as many words as possible
adc cx,cx ;1 if there's an odd trailing byte to
; do, 0 otherwise
rep stosb ;fill any odd trailing byte
LineFillDone:
add bx,size HLine ;point to the next line descriptor
add dx,SCREEN_WIDTH ;point to the next scan line
dec si ;count off lines to fill
jnz FillLoop
FillDone:
pop di ;restore caller's register variables
pop si
pop bp ;restore caller's stack frame
ret
_DrawHorizontalLineList endp
end
<a name="02a8_0010">
<a name="02a8_0011">[LISTING FOUR]<a name="02a8_0011">
/*** Replace this... ***/
extern int FillConvexPolygon(struct PointListHeader *, int, int, int);
/*** ...with this... ***/
extern int FillMonotoneVerticalPolygon(struct PointListHeader *,
int, int, int);
extern int PolygonIsMonotoneVertical(struct PointListHeader *);
/*** Replace this... ***/
#ifdef CONVEX_CODE_LINKED
/* Pass convex polygons through to fast convex polygon filler */
if (PolygonShape == CONVEX)
return(FillConvexPolygon(VertexList, Color, XOffset, YOffset));
#endif
/*** ...with this... ***/
#ifdef CONVEX_CODE_LINKED
/* Pass convex polygons through to fast convex polygon filler */
if ((PolygonShape == CONVEX) ||
PolygonIsMonotoneVertical(VertexList))
return(FillMonotoneVerticalPolygon(VertexList, Color, XOffset,
YOffset));
#endif
<a name="02a8_0012">
<a name="02a8_0013">[LISTING FIVE]<a name="02a8_0013">
/* POLYGON.H: Header file for polygon-filling code */
#define CONVEX 0
#define NONCONVEX 1
#define COMPLEX 2
/* Describes a single point (used for a single vertex) */
struct Point {
int X; /* X coordinate */
int Y; /* Y coordinate */
};
/* Describes series of points (used to store a list of vertices that describe
a polygon; each vertex is assumed to connect to the two adjacent vertices, and
last vertex is assumed to connect to the first) */
struct PointListHeader {
int Length; /* # of points */
struct Point * PointPtr; /* pointer to list of points */
};
/* Describes beginning and ending X coordinates of a single horizontal line */
struct HLine {
int XStart; /* X coordinate of leftmost pixel in line */
int XEnd; /* X coordinate of rightmost pixel in line */
};
/* Describes a Length-long series of horizontal lines, all assumed to be on
contiguous scan lines starting at YStart and proceeding downward (used to
describe scan-converted polygon to low-level hardware-dependent drawing code)*/
struct HLineList {
int Length; /* # of horizontal lines */
int YStart; /* Y coordinate of topmost line */
struct HLine * HLinePtr; /* pointer to list of horz lines */
};
/* Describes a color as an RGB triple, plus one byte for other info */
struct RGB { unsigned char Red, Green, Blue, Spare; };
<a name="02a8_0014">
<a name="02a8_0015">[LISTING SIX]<a name="02a8_0015">
/* Mode set routine for VGA 640x400 16-color mode. Tested with
Borland C++ 2, in C compilation mode. */
#include <dos.h>
void Set640x400()
{
union REGS regset;
/* First, set to standard 640x350 mode (mode 10h) */
regset.x.ax = 0x0010;
int86(0x10, ®set, ®set);
/* Modify the sync polarity bits (bits 7 & 6) of the
Miscellaneous Output register (readable at 0x3CC, writable at
0x3C2) to select the 400-scan-line vertical scanning rate */
outp(0x3C2, ((inp(0x3CC) & 0x3F) | 0x40));
/* Now, tweak the registers needed to convert the vertical
timings from 350 to 400 scan lines */
outpw(0x3D4, 0x9C10); /* adjust the Vertical Sync Start register
for 400 scan lines */
outpw(0x3D4, 0x8E11); /* adjust the Vertical Sync End register
for 400 scan lines */
outpw(0x3D4, 0x8F12); /* adjust the Vertical Display End
register for 400 scan lines */
outpw(0x3D4, 0x9615); /* adjust the Vertical Blank Start
register for 400 scan lines */
outpw(0x3D4, 0xB916); /* adjust the Vertical Blank End register
for 400 scan lines */
}
<a name="02a8_0016">
<a name="02a8_0017">[LISTING SEVEN]<a name="02a8_0017">
/* Sample program to exercise VGA 640x400 16-color mode page flipping, by
drawing a horizontal line at the top of page 0 and another at bottom of page 1,
then flipping between them once every 30 frames. Tested with Borland C++ 2,
in C compilation mode. */
#include <dos.h>
#include <conio.h>
#define SCREEN_SEGMENT 0xA000
#define SCREEN_HEIGHT 400
#define SCREEN_WIDTH_IN_BYTES 80
#define INPUT_STATUS_1 0x3DA /* color-mode address of Input Status 1
register */
/* The page start addresses must be even multiples of 256, because page
flipping is performed by changing only the upper start address byte */
#define PAGE_0_START 0
#define PAGE_1_START (400*SCREEN_WIDTH_IN_BYTES)
void main(void);
void Wait30Frames(void);
extern void Set640x400(void);
void main()
{
int i;
unsigned int far *ScreenPtr;
union REGS regset;
Set640x400(); /* set to 640x400 16-color mode */
/* Point to first line of page 0 and draw a horizontal line across screen */
FP_SEG(ScreenPtr) = SCREEN_SEGMENT;
FP_OFF(ScreenPtr) = PAGE_0_START;
for (i=0; i<(SCREEN_WIDTH_IN_BYTES/2); i++) *ScreenPtr++ = 0xFFFF;
/* Point to last line of page 1 and draw a horizontal line across screen */
FP_OFF(ScreenPtr) =
PAGE_1_START + ((SCREEN_HEIGHT-1)*SCREEN_WIDTH_IN_BYTES);
for (i=0; i<(SCREEN_WIDTH_IN_BYTES/2); i++) *ScreenPtr++ = 0xFFFF;
/* Now flip pages once every 30 frames until a key is pressed */
do {
Wait30Frames();
/* Flip to page 1 */
outpw(0x3D4, 0x0C | ((PAGE_1_START >> 8) << 8));
Wait30Frames();
/* Flip to page 0 */
outpw(0x3D4, 0x0C | ((PAGE_0_START >> 8) << 8));
} while (kbhit() == 0);
getch(); /* clear the key press */
/* Return to text mode and exit */
regset.x.ax = 0x0003; /* AL = 3 selects 80x25 text mode */
int86(0x10, ®set, ®set);
}
void Wait30Frames()
{
int i;
for (i=0; i<30; i++) {
/* Wait until we're not in vertical sync, so we can catch leading edge */
while ((inp(INPUT_STATUS_1) & 0x08) != 0) ;
/* Wait until we are in vertical sync */
while ((inp(INPUT_STATUS_1) & 0x08) == 0) ;
}
}
