Category : Files from Magazines
Archive   : DDJ1291.ZIP
Filename : GRPHPROG.ASC

_GRAPHICS PROGRAMMING COLUMN_
by Michael Abrash

[LISTING ONE]

/* 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 */
}


[LISTING TWO]

/* 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
#include
#include
#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);
}


[LISTING THREE]

; 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



[LISTING FOUR]

/*** 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



[LISTING FIVE]

/* 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; };



[LISTING SIX]

/* Mode set routine for VGA 640x400 16-color mode. Tested with
Borland C++ 2, in C compilation mode. */

#include

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 */
}



[LISTING SEVEN]

/* 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
#include

#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) ;
}
}