home *** CD-ROM | disk | FTP | other *** search
/ Computer Select (Limited Edition) / Computer Select.iso / dobbs / v16n12 / grphprog.asc < prev    next >
Encoding:
Text File  |  1991-11-11  |  16.8 KB  |  446 lines
  1. _GRAPHICS PROGRAMMING COLUMN_
  2. by Michael Abrash
  3.  
  4. [LISTING ONE]
  5.  
  6. /* Returns 1 if polygon described by passed-in vertex list is monotone with
  7. respect to a vertical line, 0 otherwise. Doesn't matter if polygon is simple 
  8. (non-self-intersecting) or not. Tested with Borland C++ 2 in small model. */
  9.  
  10. #include "polygon.h"
  11.  
  12. #define SIGNUM(a) ((a>0)?1:((a<0)?-1:0))
  13.  
  14. int PolygonIsMonotoneVertical(struct PointListHeader * VertexList)
  15. {
  16.    int i, Length, DeltaYSign, PreviousDeltaYSign;
  17.    int NumYReversals = 0;
  18.    struct Point *VertexPtr = VertexList->PointPtr;
  19.  
  20.    /* Three or fewer points can't make a non-vertical-monotone polygon */
  21.    if ((Length=VertexList->Length) < 4) return(1);
  22.  
  23.    /* Scan to the first non-horizontal edge */
  24.    PreviousDeltaYSign = SIGNUM(VertexPtr[Length-1].Y - VertexPtr[0].Y);
  25.    i = 0;
  26.    while ((PreviousDeltaYSign == 0) && (i < (Length-1))) {
  27.       PreviousDeltaYSign = SIGNUM(VertexPtr[i].Y - VertexPtr[i+1].Y);
  28.       i++;
  29.    }
  30.  
  31.    if (i == (Length-1)) return(1);  /* polygon is a flat line */
  32.  
  33.    /* Now count Y reversals. Might miss one reversal, at the last vertex, but 
  34.       because reversal counts must be even, being off by one isn't a problem */
  35.    do {
  36.       if ((DeltaYSign = SIGNUM(VertexPtr[i].Y - VertexPtr[i+1].Y))
  37.             != 0) {
  38.          if (DeltaYSign != PreviousDeltaYSign) {
  39.             /* Switched Y direction; not vertical-monotone if
  40.                reversed Y direction as many as three times */
  41.             if (++NumYReversals > 2) return(0);
  42.             PreviousDeltaYSign = DeltaYSign;
  43.          }
  44.       }
  45.    } while (i++ < (Length-1));
  46.    return(1);  /* it's a vertical-monotone polygon */
  47. }
  48.  
  49.  
  50. [LISTING TWO]
  51.  
  52. /* Color-fills a convex polygon. All vertices are offset by (XOffset, YOffset).
  53. "Convex" means "monotone with respect to a vertical line"; that is, every 
  54. horizontal line drawn through the polygon at any point would cross exactly two 
  55. active edges (neither horizontal lines nor zero-length edges count as active 
  56. edges; both are acceptable anywhere in the polygon). Right & left edges may 
  57. cross (polygons may be nonsimple). Polygons that are not convex according to 
  58. this definition won't be drawn properly. (Yes, "convex" is a lousy name for 
  59. this type of polygon, but it's convenient; use "monotone-vertical" if it makes 
  60. you happier!)
  61. *******************************************************************
  62. NOTE: the low-level drawing routine, DrawHorizontalLineList, must be able to 
  63. reverse the edges, if necessary to make the correct edge left edge. It must 
  64. also expect right edge to be specified in +1 format (the X coordinate is 1 past
  65. highest coordinate to draw). In both respects, this differs from low-level 
  66. drawing routines presented in earlier columns; changes are necessary to make it
  67. possible to draw nonsimple monotone-vertical polygons; that in turn makes it 
  68. possible to use Jim Kent's test for monotone-vertical polygons.
  69. *******************************************************************
  70. Returns 1 for success, 0 if memory allocation failed */
  71.  
  72. #include <stdio.h>
  73. #include <math.h>
  74. #include <stdlib.h>
  75. #include "polygon.h"
  76.  
  77. /* Advances the index by one vertex forward through the vertex list,
  78. wrapping at the end of the list */
  79. #define INDEX_FORWARD(Index) \
  80.    Index = (Index + 1) % VertexList->Length;
  81.  
  82. /* Advances the index by one vertex backward through the vertex list,
  83. wrapping at the start of the list */
  84. #define INDEX_BACKWARD(Index) \
  85.    Index = (Index - 1 + VertexList->Length) % VertexList->Length;
  86.  
  87. /* Advances the index by one vertex either forward or backward through
  88. the vertex list, wrapping at either end of the list */
  89. #define INDEX_MOVE(Index,Direction)                                  \
  90.    if (Direction > 0)                                                \
  91.       Index = (Index + 1) % VertexList->Length;                      \
  92.    else                                                              \
  93.       Index = (Index - 1 + VertexList->Length) % VertexList->Length;
  94.  
  95. extern void ScanEdge(int, int, int, int, int, int, struct HLine **);
  96. extern void DrawHorizontalLineList(struct HLineList *, int);
  97.  
  98. int FillMonotoneVerticalPolygon(struct PointListHeader * VertexList,
  99.       int Color, int XOffset, int YOffset)
  100. {
  101.    int i, MinIndex, MaxIndex, MinPoint_Y, MaxPoint_Y;
  102.    int NextIndex, CurrentIndex, PreviousIndex;
  103.    struct HLineList WorkingHLineList;
  104.    struct HLine *EdgePointPtr;
  105.    struct Point *VertexPtr;
  106.  
  107.    /* Point to the vertex list */
  108.    VertexPtr = VertexList->PointPtr;
  109.  
  110.    /* Scan the list to find the top and bottom of the polygon */
  111.    if (VertexList->Length == 0)
  112.       return(1);  /* reject null polygons */
  113.    MaxPoint_Y = MinPoint_Y = VertexPtr[MinIndex = MaxIndex = 0].Y;
  114.    for (i = 1; i < VertexList->Length; i++) {
  115.       if (VertexPtr[i].Y < MinPoint_Y)
  116.          MinPoint_Y = VertexPtr[MinIndex = i].Y; /* new top */
  117.       else if (VertexPtr[i].Y > MaxPoint_Y)
  118.          MaxPoint_Y = VertexPtr[MaxIndex = i].Y; /* new bottom */
  119.    }
  120.  
  121.    /* Set the # of scan lines in the polygon, skipping the bottom edge */
  122.    if ((WorkingHLineList.Length = MaxPoint_Y - MinPoint_Y) <= 0)
  123.       return(1);  /* there's nothing to draw, so we're done */
  124.    WorkingHLineList.YStart = YOffset + MinPoint_Y;
  125.  
  126.    /* Get memory in which to store the line list we generate */
  127.    if ((WorkingHLineList.HLinePtr =
  128.          (struct HLine *) (malloc(sizeof(struct HLine) *
  129.          WorkingHLineList.Length))) == NULL)
  130.       return(0);  /* couldn't get memory for the line list */
  131.  
  132.    /* Scan the first edge and store the boundary points in the list */
  133.    /* Initial pointer for storing scan converted first-edge coords */
  134.    EdgePointPtr = WorkingHLineList.HLinePtr;
  135.    /* Start from the top of the first edge */
  136.    PreviousIndex = CurrentIndex = MinIndex;
  137.    /* Scan convert each line in the first edge from top to bottom */
  138.    do {
  139.       INDEX_BACKWARD(CurrentIndex);
  140.       ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
  141.             VertexPtr[PreviousIndex].Y,
  142.             VertexPtr[CurrentIndex].X + XOffset,
  143.             VertexPtr[CurrentIndex].Y, 1, 0, &EdgePointPtr);
  144.       PreviousIndex = CurrentIndex;
  145.    } while (CurrentIndex != MaxIndex);
  146.  
  147.    /* Scan the second edge and store the boundary points in the list */
  148.    EdgePointPtr = WorkingHLineList.HLinePtr;
  149.    PreviousIndex = CurrentIndex = MinIndex;
  150.    /* Scan convert the second edge, top to bottom */
  151.    do {
  152.       INDEX_FORWARD(CurrentIndex);
  153.       ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
  154.             VertexPtr[PreviousIndex].Y,
  155.             VertexPtr[CurrentIndex].X + XOffset,
  156.             VertexPtr[CurrentIndex].Y, 0, 0, &EdgePointPtr);
  157.       PreviousIndex = CurrentIndex;
  158.    } while (CurrentIndex != MaxIndex);
  159.  
  160.    /* Draw the line list representing the scan converted polygon */
  161.    DrawHorizontalLineList(&WorkingHLineList, Color);
  162.  
  163.    /* Release the line list's memory and we're successfully done */
  164.    free(WorkingHLineList.HLinePtr);
  165.    return(1);
  166. }
  167.  
  168.  
  169. [LISTING THREE]
  170.  
  171. ; Draws all pixels in list of horizontal lines passed in, in mode 13h, VGA's 
  172. ; 320x200 256-color mode. Uses REP STOS to fill each line.
  173. ; ******************************************************************
  174. ; NOTE: is able to reverse the X coords for a scan line, if necessary to make 
  175. ; XStart < XEnd. Expects whichever edge is rightmost on any scan line to be in
  176. ; +1 format; that is, XEnd is 1 greater than rightmost pixel to draw. if 
  177. ; XStart == XEnd, nothing is drawn on that scan line.
  178. ; ******************************************************************
  179. ; C near-callable as:
  180. ;     void DrawHorizontalLineList(struct HLineList * HLineListPtr, int Color);
  181. ; All assembly code tested with TASM 2.0 and MASM 5.0
  182.  
  183. SCREEN_WIDTH    equ     320
  184. SCREEN_SEGMENT  equ     0a000h
  185.  
  186. HLine   struc
  187. XStart  dw      ?       ;X coordinate of leftmost pixel in line
  188. XEnd    dw      ?       ;X coordinate of rightmost pixel in line
  189. HLine   ends
  190.  
  191. HLineList struc
  192. Lngth   dw      ?       ;# of horizontal lines
  193. YStart  dw      ?       ;Y coordinate of topmost line
  194. HLinePtr dw     ?       ;pointer to list of horz lines
  195. HLineList ends
  196.  
  197. Parms   struc
  198.                 dw      2 dup(?) ;return address & pushed BP
  199. HLineListPtr    dw      ?       ;pointer to HLineList structure
  200. Color           dw      ?       ;color with which to fill
  201. Parms   ends
  202.         .model small
  203.         .code
  204.         public _DrawHorizontalLineList
  205.         align   2
  206. _DrawHorizontalLineList proc
  207.         push    bp              ;preserve caller's stack frame
  208.         mov     bp,sp           ;point to our stack frame
  209.         push    si              ;preserve caller's register variables
  210.         push    di
  211.         cld                     ;make string instructions inc pointers
  212.  
  213.         mov     ax,SCREEN_SEGMENT
  214.         mov     es,ax   ;point ES to display memory for REP STOS
  215.  
  216.         mov     si,[bp+HLineListPtr] ;point to the line list
  217.         mov     ax,SCREEN_WIDTH ;point to the start of the first scan
  218.         mul     [si+YStart]     ; line in which to draw
  219.         mov     dx,ax           ;ES:DX points to first scan line to draw
  220.         mov     bx,[si+HLinePtr] ;point to the XStart/XEnd descriptor
  221.                                 ; for the first (top) horizontal line
  222.         mov     si,[si+Lngth]   ;# of scan lines to draw
  223.         and     si,si           ;are there any lines to draw?
  224.         jz      FillDone        ;no, so we're done
  225.         mov     al,byte ptr [bp+Color] ;color with which to fill
  226.         mov     ah,al           ;duplicate color for STOSW
  227. FillLoop:
  228.         mov     di,[bx+XStart]  ;left edge of fill on this line
  229.         mov     cx,[bx+XEnd]    ;right edge of fill
  230.         cmp     di,cx           ;is XStart > XEnd?
  231.         jle     NoSwap          ;no, we're all set
  232.         xchg    di,cx           ;yes, so swap edges
  233. NoSwap:
  234.         sub     cx,di           ;width of fill on this line
  235.         jz      LineFillDone    ;skip if zero width
  236.         add     di,dx           ;offset of left edge of fill
  237.         test    di,1            ;does fill start at an odd address?
  238.         jz      MainFill        ;no
  239.         stosb                   ;yes, draw the odd leading byte to
  240.                                 ; word-align the rest of the fill
  241.         dec     cx              ;count off the odd leading byte
  242.         jz      LineFillDone    ;done if that was the only byte
  243. MainFill:
  244.         shr     cx,1            ;# of words in fill
  245.         rep     stosw           ;fill as many words as possible
  246.         adc     cx,cx           ;1 if there's an odd trailing byte to
  247.                                 ; do, 0 otherwise
  248.         rep     stosb           ;fill any odd trailing byte
  249. LineFillDone:
  250.         add     bx,size HLine   ;point to the next line descriptor
  251.         add     dx,SCREEN_WIDTH ;point to the next scan line
  252.         dec     si              ;count off lines to fill
  253.         jnz     FillLoop
  254. FillDone:
  255.         pop     di              ;restore caller's register variables
  256.         pop     si
  257.         pop     bp              ;restore caller's stack frame
  258.         ret
  259. _DrawHorizontalLineList endp
  260.         end
  261.  
  262.  
  263.  
  264. [LISTING FOUR]
  265.  
  266. /*** Replace this... ***/
  267. extern int FillConvexPolygon(struct PointListHeader *, int, int, int);
  268.  
  269. /*** ...with this... ***/
  270. extern int FillMonotoneVerticalPolygon(struct PointListHeader *,
  271.    int, int, int);
  272. extern int PolygonIsMonotoneVertical(struct PointListHeader *);
  273.  
  274. /*** Replace this... ***/
  275. #ifdef CONVEX_CODE_LINKED
  276.    /* Pass convex polygons through to fast convex polygon filler */
  277.    if (PolygonShape == CONVEX)
  278.       return(FillConvexPolygon(VertexList, Color, XOffset, YOffset));
  279. #endif
  280.  
  281. /*** ...with this... ***/
  282. #ifdef CONVEX_CODE_LINKED
  283.    /* Pass convex polygons through to fast convex polygon filler */
  284.    if ((PolygonShape == CONVEX) ||
  285.          PolygonIsMonotoneVertical(VertexList))
  286.       return(FillMonotoneVerticalPolygon(VertexList, Color, XOffset,
  287.             YOffset));
  288. #endif
  289.  
  290.  
  291.  
  292. [LISTING FIVE]
  293.  
  294. /* POLYGON.H: Header file for polygon-filling code */
  295.  
  296. #define CONVEX    0
  297. #define NONCONVEX 1
  298. #define COMPLEX   2
  299.  
  300. /* Describes a single point (used for a single vertex) */
  301. struct Point {
  302.    int X;   /* X coordinate */
  303.    int Y;   /* Y coordinate */
  304. };
  305.  
  306. /* Describes series of points (used to store a list of vertices that describe 
  307. a polygon; each vertex is assumed to connect to the two adjacent vertices, and 
  308. last vertex is assumed to connect to the first) */
  309. struct PointListHeader {
  310.    int Length;                /* # of points */
  311.    struct Point * PointPtr;   /* pointer to list of points */
  312. };
  313.  
  314. /* Describes beginning and ending X coordinates of a single horizontal line */
  315. struct HLine {
  316.    int XStart; /* X coordinate of leftmost pixel in line */
  317.    int XEnd;   /* X coordinate of rightmost pixel in line */
  318. };
  319.  
  320. /* Describes a Length-long series of horizontal lines, all assumed to be on 
  321. contiguous scan lines starting at YStart and proceeding downward (used to 
  322. describe scan-converted polygon to low-level hardware-dependent drawing code)*/
  323. struct HLineList {
  324.    int Length;                /* # of horizontal lines */
  325.    int YStart;                /* Y coordinate of topmost line */
  326.    struct HLine * HLinePtr;   /* pointer to list of horz lines */
  327. };
  328.  
  329. /* Describes a color as an RGB triple, plus one byte for other info */
  330. struct RGB { unsigned char Red, Green, Blue, Spare; };
  331.  
  332.  
  333.  
  334. [LISTING SIX]
  335.  
  336. /* Mode set routine for VGA 640x400 16-color mode. Tested with
  337.    Borland C++ 2, in C compilation mode. */
  338.  
  339. #include <dos.h>
  340.  
  341. void Set640x400()
  342. {
  343.    union REGS regset;
  344.  
  345.    /* First, set to standard 640x350 mode (mode 10h) */
  346.    regset.x.ax = 0x0010;
  347.    int86(0x10, ®set, ®set);
  348.  
  349.    /* Modify the sync polarity bits (bits 7 & 6) of the
  350.       Miscellaneous Output register (readable at 0x3CC, writable at
  351.       0x3C2) to select the 400-scan-line vertical scanning rate */
  352.    outp(0x3C2, ((inp(0x3CC) & 0x3F) | 0x40));
  353.  
  354.    /* Now, tweak the registers needed to convert the vertical
  355.       timings from 350 to 400 scan lines */
  356.    outpw(0x3D4, 0x9C10);   /* adjust the Vertical Sync Start register
  357.                               for 400 scan lines */
  358.    outpw(0x3D4, 0x8E11);   /* adjust the Vertical Sync End register
  359.                               for 400 scan lines */
  360.    outpw(0x3D4, 0x8F12);   /* adjust the Vertical Display End
  361.                               register for 400 scan lines */
  362.    outpw(0x3D4, 0x9615);   /* adjust the Vertical Blank Start
  363.                               register for 400 scan lines */
  364.    outpw(0x3D4, 0xB916);   /* adjust the Vertical Blank End register
  365.                               for 400 scan lines */
  366. }
  367.  
  368.  
  369.  
  370. [LISTING SEVEN]
  371.  
  372. /* Sample program to exercise VGA 640x400 16-color mode page flipping, by 
  373. drawing a horizontal line at the top of page 0 and another at bottom of page 1,
  374. then flipping between them once every 30 frames. Tested with Borland C++ 2, 
  375. in C compilation mode. */
  376.  
  377. #include <dos.h>
  378. #include <conio.h>
  379.  
  380. #define SCREEN_SEGMENT  0xA000
  381. #define SCREEN_HEIGHT   400
  382. #define SCREEN_WIDTH_IN_BYTES 80
  383. #define INPUT_STATUS_1  0x3DA /* color-mode address of Input Status 1
  384.                                  register */
  385. /* The page start addresses must be even multiples of 256, because page 
  386. flipping is performed by changing only the upper start address byte */
  387. #define PAGE_0_START 0
  388. #define PAGE_1_START (400*SCREEN_WIDTH_IN_BYTES)
  389.  
  390. void main(void);
  391. void Wait30Frames(void);
  392. extern void Set640x400(void);
  393.  
  394. void main()
  395. {
  396.    int i;
  397.    unsigned int far *ScreenPtr; 
  398.    union REGS regset;
  399.  
  400.    Set640x400();  /* set to 640x400 16-color mode */
  401.  
  402.    /* Point to first line of page 0 and draw a horizontal line across screen */
  403.    FP_SEG(ScreenPtr) = SCREEN_SEGMENT;
  404.    FP_OFF(ScreenPtr) = PAGE_0_START;
  405.    for (i=0; i<(SCREEN_WIDTH_IN_BYTES/2); i++) *ScreenPtr++ = 0xFFFF;
  406.  
  407.    /* Point to last line of page 1 and draw a horizontal line across screen */
  408.    FP_OFF(ScreenPtr) =
  409.          PAGE_1_START + ((SCREEN_HEIGHT-1)*SCREEN_WIDTH_IN_BYTES);
  410.    for (i=0; i<(SCREEN_WIDTH_IN_BYTES/2); i++) *ScreenPtr++ = 0xFFFF;
  411.  
  412.    /* Now flip pages once every 30 frames until a key is pressed */
  413.    do {
  414.       Wait30Frames();
  415.  
  416.       /* Flip to page 1 */
  417.       outpw(0x3D4, 0x0C | ((PAGE_1_START >> 8) << 8));
  418.  
  419.       Wait30Frames();
  420.  
  421.       /* Flip to page 0 */
  422.       outpw(0x3D4, 0x0C | ((PAGE_0_START >> 8) << 8));
  423.    } while (kbhit() == 0);
  424.  
  425.    getch(); /* clear the key press */
  426.  
  427.    /* Return to text mode and exit */
  428.    regset.x.ax = 0x0003;   /* AL = 3 selects 80x25 text mode */
  429.    int86(0x10, ®set, ®set);
  430. }
  431.  
  432. void Wait30Frames()
  433. {
  434.    int i;
  435.  
  436.    for (i=0; i<30; i++) {
  437.       /* Wait until we're not in vertical sync, so we can catch leading edge */
  438.       while ((inp(INPUT_STATUS_1) & 0x08) != 0) ;
  439.       /* Wait until we are in vertical sync */
  440.       while ((inp(INPUT_STATUS_1) & 0x08) == 0) ;
  441.    }
  442. }
  443.  
  444.  
  445.  
  446.