_GRAPHICS PROGRAMMING COLUMN_
by Michael Abrash


[LISTING ONE]

/* Draws all pixels in the list of horizontal lines passed in, in
   mode 13h, the VGA's 320x200 256-color mode. Uses memset to fill
   each line, which is much faster than using DrawPixel but requires
   that a large data model (compact, large, or huge) be in use when
   running in real mode or 286 protected mode.
   All C code tested with Turbo C++ */

#include <string.h>
#include <dos.h>
#include "polygon.h"

#define SCREEN_WIDTH    320
#define SCREEN_SEGMENT  0xA000

void DrawHorizontalLineList(struct HLineList * HLineListPtr,
      int Color)
{
   struct HLine *HLinePtr;
   int Length, Width;
   unsigned char far *ScreenPtr;

   /* Point to the start of the first scan line on which to draw */
   ScreenPtr = MK_FP(SCREEN_SEGMENT,
         HLineListPtr->YStart * SCREEN_WIDTH);

   /* Point to the XStart/XEnd descriptor for the first (top)
      horizontal line */
   HLinePtr = HLineListPtr->HLinePtr;
   /* Draw each horizontal line in turn, starting with the top one and
      advancing one line each time */
   Length = HLineListPtr->Length;
   while (Length-- > 0) {
      /* Draw the whole horizontal line if it has a positive width */
      if ((Width = HLinePtr->XEnd - HLinePtr->XStart + 1) > 0)
         memset(ScreenPtr + HLinePtr->XStart, Color, Width);
      HLinePtr++;                /* point to next scan line X info */
      ScreenPtr += SCREEN_WIDTH; /* point to next scan line start */
   }
}


[LISTING TWO]

/* Scan converts an edge from (X1,Y1) to (X2,Y2), not including the
   point at (X2,Y2). If SkipFirst == 1, the point at (X1,Y1) isn't
   drawn; if SkipFirst == 0, it is. For each scan line, the pixel
   closest to the scanned edge without being to the left of the
   scanned edge is chosen. Uses an all-integer approach for speed and
   precision */

#include <math.h>
#include "polygon.h"

void ScanEdge(int X1, int Y1, int X2, int Y2, int SetXStart,
      int SkipFirst, struct HLine **EdgePointPtr)
{
   int Y, DeltaX, Height, Width, AdvanceAmt, ErrorTerm, i;
   int ErrorTermAdvance, XMajorAdvanceAmt;
   struct HLine *WorkingEdgePointPtr;

   WorkingEdgePointPtr = *EdgePointPtr; /* avoid double dereference */
   AdvanceAmt = ((DeltaX = X2 - X1) > 0) ? 1 : -1;
                            /* direction in which X moves (Y2 is
                               always > Y1, so Y always counts up) */

   if ((Height = Y2 - Y1) <= 0)  /* Y length of the edge */
      return;     /* guard against 0-length and horizontal edges */

   /* Figure out whether the edge is vertical, diagonal, X-major
      (mostly horizontal), or Y-major (mostly vertical) and handle
      appropriately */
   if ((Width = abs(DeltaX)) == 0) {
      /* The edge is vertical; special-case by just storing the same
         X coordinate for every scan line */
      /* Scan the edge for each scan line in turn */
      for (i = Height - SkipFirst; i-- > 0; WorkingEdgePointPtr++) {
         /* Store the X coordinate in the appropriate edge list */
         if (SetXStart == 1)
            WorkingEdgePointPtr->XStart = X1;
         else
            WorkingEdgePointPtr->XEnd = X1;
      }
   } else if (Width == Height) {
      /* The edge is diagonal; special-case by advancing the X
         coordinate 1 pixel for each scan line */
      if (SkipFirst) /* skip the first point if so indicated */
         X1 += AdvanceAmt; /* move 1 pixel to the left or right */
      /* Scan the edge for each scan line in turn */
      for (i = Height - SkipFirst; i-- > 0; WorkingEdgePointPtr++) {
         /* Store the X coordinate in the appropriate edge list */
         if (SetXStart == 1)
            WorkingEdgePointPtr->XStart = X1;
         else
            WorkingEdgePointPtr->XEnd = X1;
         X1 += AdvanceAmt; /* move 1 pixel to the left or right */
      }
   } else if (Height > Width) {
      /* Edge is closer to vertical than horizontal (Y-major) */
      if (DeltaX >= 0)
         ErrorTerm = 0; /* initial error term going left->right */
      else
         ErrorTerm = -Height + 1;   /* going right->left */
      if (SkipFirst) {   /* skip the first point if so indicated */
         /* Determine whether it's time for the X coord to advance */
         if ((ErrorTerm += Width) > 0) {
            X1 += AdvanceAmt; /* move 1 pixel to the left or right */
            ErrorTerm -= Height; /* advance ErrorTerm to next point */
         }
      }
      /* Scan the edge for each scan line in turn */
      for (i = Height - SkipFirst; i-- > 0; WorkingEdgePointPtr++) {
         /* Store the X coordinate in the appropriate edge list */
         if (SetXStart == 1)
            WorkingEdgePointPtr->XStart = X1;
         else
            WorkingEdgePointPtr->XEnd = X1;
         /* Determine whether it's time for the X coord to advance */
         if ((ErrorTerm += Width) > 0) {
            X1 += AdvanceAmt; /* move 1 pixel to the left or right */
            ErrorTerm -= Height; /* advance ErrorTerm to correspond */
         }
      }
   } else {
      /* Edge is closer to horizontal than vertical (X-major) */
      /* Minimum distance to advance X each time */
      XMajorAdvanceAmt = (Width / Height) * AdvanceAmt;
      /* Error term advance for deciding when to advance X 1 extra */
      ErrorTermAdvance = Width % Height;
      if (DeltaX >= 0)
         ErrorTerm = 0; /* initial error term going left->right */
      else
         ErrorTerm = -Height + 1;   /* going right->left */
      if (SkipFirst) {   /* skip the first point if so indicated */
         X1 += XMajorAdvanceAmt;    /* move X minimum distance */
         /* Determine whether it's time for X to advance one extra */
         if ((ErrorTerm += ErrorTermAdvance) > 0) {
            X1 += AdvanceAmt;       /* move X one more */
            ErrorTerm -= Height; /* advance ErrorTerm to correspond */
         }
      }
      /* Scan the edge for each scan line in turn */
      for (i = Height - SkipFirst; i-- > 0; WorkingEdgePointPtr++) {
         /* Store the X coordinate in the appropriate edge list */
         if (SetXStart == 1)
            WorkingEdgePointPtr->XStart = X1;
         else
            WorkingEdgePointPtr->XEnd = X1;
         X1 += XMajorAdvanceAmt;    /* move X minimum distance */
         /* Determine whether it's time for X to advance one extra */
         if ((ErrorTerm += ErrorTermAdvance) > 0) {
            X1 += AdvanceAmt;       /* move X one more */
            ErrorTerm -= Height; /* advance ErrorTerm to correspond */
         }
      }
   }

   *EdgePointPtr = WorkingEdgePointPtr;   /* advance caller's ptr */
}



[LISTING THREE]

; Draws all pixels in the list of horizontal lines passed in, in
; mode 13h, the VGA's 320x200 256-color mode. Uses REP STOS to fill
; each 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
	sub	cx,di
	js	LineFillDone	;skip if negative width
	inc	cx		;width of fill on this line
	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]

; Scan converts an edge from (X1,Y1) to (X2,Y2), not including the
; point at (X2,Y2). If SkipFirst == 1, the point at (X1,Y1) isn't
; drawn; if SkipFirst == 0, it is. For each scan line, the pixel
; closest to the scanned edge without being to the left of the scanned
; edge is chosen. Uses an all-integer approach for speed & precision.
; C near-callable as:
;    void ScanEdge(int X1, int Y1, int X2, int Y2, int SetXStart,
;	  int SkipFirst, struct HLine **EdgePointPtr);
; Edges must not go bottom to top; that is, Y1 must be <= Y2.
; Updates the pointer pointed to by EdgePointPtr to point to the next
;  free entry in the array of HLine structures.

HLine	struc
XStart	dw	?	;X coordinate of leftmost pixel in scan line
XEnd	dw	?	;X coordinate of rightmost pixel in scan line
HLine	ends

Parms	struc
		dw	2 dup(?) ;return address & pushed BP
X1		dw	?	;X start coord of edge
Y1		dw	?	;Y start coord of edge
X2		dw	?	;X end coord of edge
Y2		dw	?	;Y end coord of edge
SetXStart	dw	?	;1 to set the XStart field of each
				; HLine struc, 0 to set XEnd
SkipFirst	dw	?	;1 to skip scanning the first point
				; of the edge, 0 to scan first point
EdgePointPtr	dw	?	;pointer to a pointer to the array of
				; HLine structures in which to store
				; the scanned X coordinates
Parms	ends

;Offsets from BP in stack frame of local variables.
AdvanceAmt      equ     -2
Height          equ     -4
LOCAL_SIZE      equ     4	;total size of local variables

	.model small
	.code
	public _ScanEdge
	align	2
_ScanEdge	proc
	push	bp		;preserve caller's stack frame
	mov	bp,sp		;point to our stack frame
        sub     sp,LOCAL_SIZE   ;allocate space for local variables
	push	si		;preserve caller's register variables
	push	di
	mov	di,[bp+EdgePointPtr]
	mov	di,[di]		;point to the HLine array
	cmp	[bp+SetXStart],1 ;set the XStart field of each HLine
				; struc?
	jz	HLinePtrSet	;yes, DI points to the first XStart
	add	di,XEnd		;no, point to the XEnd field of the
				; first HLine struc
HLinePtrSet:
	mov	bx,[bp+Y2]
	sub	bx,[bp+Y1]	;edge height
	jle	ToScanEdgeExit	;guard against 0-length & horz edges
	mov	[bp+Height],bx	;Height = Y2 - Y1
	sub	cx,cx		;assume ErrorTerm starts at 0 (true if
                                ; we're moving right as we draw)
	mov	dx,1		;assume AdvanceAmt = 1 (move right)
	mov	ax,[bp+X2]
	sub	ax,[bp+X1]      ;DeltaX = X2 - X1
        jz      IsVertical     	;it's a vertical edge--special case it
	jns	SetAdvanceAmt	;DeltaX >= 0
	mov	cx,1		;DeltaX < 0 (move left as we draw)
	sub	cx,bx		;ErrorTerm = -Height + 1
	neg	dx		;AdvanceAmt = -1 (move left)
        neg     ax              ;Width = abs(DeltaX)
SetAdvanceAmt:
	mov	[bp+AdvanceAmt],dx
; Figure out whether the edge is diagonal, X-major (more horizontal),
; or Y-major (more vertical) and handle appropriately.
	cmp	ax,bx		;if Width==Height, it's a diagonal edge
	jz	IsDiagonal	;it's a diagonal edge--special case
	jb	YMajor		;it's a Y-major (more vertical) edge
				;it's an X-major (more horz) edge
        sub     dx,dx           ;prepare DX:AX (Width) for division
        div     bx		;Width/Height
				;DX = error term advance per scan line
	mov	si,ax		;SI = minimum # of pixels to advance X
				; on each scan line
        test    [bp+AdvanceAmt],8000h ;move left or right?
        jz      XMajorAdvanceAmtSet ;right, already set
        neg     si              ;left, negate the distance to advance
				; on each scan line
XMajorAdvanceAmtSet:            ;
	mov	ax,[bp+X1]	;starting X coordinate
        cmp     [bp+SkipFirst],1 ;skip the first point?
        jz	XMajorSkipEntry	;yes
XMajorLoop:
	mov	[di],ax		;store the current X value
	add	di,size HLine	;point to the next HLine struc
XMajorSkipEntry:
	add	ax,si		;set X for the next scan line
	add	cx,dx		;advance error term
	jle	XMajorNoAdvance ;not time for X coord to advance one
				; extra
	add	ax,[bp+AdvanceAmt] ;advance X coord one extra
        sub     cx,[bp+Height]  ;adjust error term back
XMajorNoAdvance:
        dec     bx		;count off this scan line
        jnz     XMajorLoop
	jmp	ScanEdgeDone
	align	2
ToScanEdgeExit:
	jmp	ScanEdgeExit
        align	2
IsVertical:
	mov	ax,[bp+X1]	;starting (and only) X coordinate
	sub	bx,[bp+SkipFirst] ;loop count = Height - SkipFirst
        jz      ScanEdgeExit 	;no scan lines left after skipping 1st
VerticalLoop:
	mov	[di],ax		;store the current X value
	add	di,size HLine	;point to the next HLine struc
	dec	bx		;count off this scan line
	jnz	VerticalLoop
	jmp	ScanEdgeDone
        align	2
IsDiagonal:
	mov	ax,[bp+X1]	;starting X coordinate
        cmp     [bp+SkipFirst],1 ;skip the first point?
	jz	DiagonalSkipEntry ;yes
DiagonalLoop:	
	mov	[di],ax		;store the current X value
	add	di,size HLine	;point to the next HLine struc
DiagonalSkipEntry:
	add	ax,dx		;advance the X coordinate
	dec	bx		;count off this scan line
	jnz	DiagonalLoop
	jmp	ScanEdgeDone
        align	2
YMajor:
	push	bp		;preserve stack frame pointer
	mov	si,[bp+X1]	;starting X coordinate
        cmp     [bp+SkipFirst],1 ;skip the first point?
	mov	bp,bx		;put Height in BP for error term calcs
        jz	YMajorSkipEntry	;yes, skip the first point
YMajorLoop:
	mov	[di],si		;store the current X value
	add	di,size HLine	;point to the next HLine struc
YMajorSkipEntry:
	add	cx,ax		;advance the error term
	jle	YMajorNoAdvance ;not time for X coord to advance
	add	si,dx		;advance the X coordinate
        sub     cx,bp		;adjust error term back
YMajorNoAdvance:
        dec     bx		;count off this scan line
        jnz     YMajorLoop
	pop	bp		;restore stack frame pointer
ScanEdgeDone:
	cmp	[bp+SetXStart],1 ;were we working with XStart field?
	jz	UpdateHLinePtr	;yes, DI points to the next XStart
	sub	di,XEnd		;no, point back to the XStart field
UpdateHLinePtr:
	mov	bx,[bp+EdgePointPtr] ;point to pointer to HLine array
	mov	[bx],di		;update caller's HLine array pointer
ScanEdgeExit:
	pop	di		;restore caller's register variables
	pop	si
        mov     sp,bp           ;deallocate local variables
	pop	bp		;restore caller's stack frame
	ret
_ScanEdge	endp
	end