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