home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1991 / 06 / grap_pr.asc < prev    next >
Text File  |  1991-05-02  |  19KB  |  502 lines
  1. _GRAPHICS PROGRAMMING COLUMN_
  2. by Michael Abrash
  3.  
  4.  
  5.  
  6. [LISTING ONE]
  7.  
  8. /* Color-fills an arbitrarily-shaped polygon described by VertexList.
  9. If the first and last points in VertexList are not the same, the path
  10. around the polygon is automatically closed. All vertices are offset
  11. by (XOffset, YOffset). Returns 1 for success, 0 if memory allocation
  12. failed. All C code tested with Turbo C++.
  13. If the polygon shape is known in advance, speedier processing may be
  14. enabled by specifying the shape as follows: "convex" - a rubber band
  15. stretched around the polygon would touch every vertex in order;
  16. "nonconvex" - the polygon is not self-intersecting, but need not be
  17. convex; "complex" - the polygon may be self-intersecting, or, indeed,
  18. any sort of polygon at all. Complex will work for all polygons; convex
  19. is fastest. Undefined results will occur if convex is specified for a
  20. nonconvex or complex polygon.
  21. Define CONVEX_CODE_LINKED if the fast convex polygon filling code from
  22. the February 1991 column is linked in. Otherwise, convex polygons are
  23. handled by the complex polygon filling code.
  24. Nonconvex is handled as complex in this implementation. See text for a
  25. discussion of faster nonconvex handling */
  26.  
  27. #include <stdio.h>
  28. #include <math.h>
  29. #ifdef __TURBOC__
  30. #include <alloc.h>
  31. #else    /* MSC */
  32. #include <malloc.h>
  33. #endif
  34. #include "polygon.h"
  35.  
  36. #define SWAP(a,b) {temp = a; a = b; b = temp;}
  37.  
  38. struct EdgeState {
  39.    struct EdgeState *NextEdge;
  40.    int X;
  41.    int StartY;
  42.    int WholePixelXMove;
  43.    int XDirection;
  44.    int ErrorTerm;
  45.    int ErrorTermAdjUp;
  46.    int ErrorTermAdjDown;
  47.    int Count;
  48. };
  49.  
  50. extern void DrawHorizontalLineSeg(int, int, int, int);
  51. extern int FillConvexPolygon(struct PointListHeader *, int, int, int);
  52. static void BuildGET(struct PointListHeader *, struct EdgeState *,
  53.    int, int);
  54. static void MoveXSortedToAET(int);
  55. static void ScanOutAET(int, int);
  56. static void AdvanceAET(void);
  57. static void XSortAET(void);
  58.  
  59. /* Pointers to global edge table (GET) and active edge table (AET) */
  60. static struct EdgeState *GETPtr, *AETPtr;
  61.  
  62. int FillPolygon(struct PointListHeader * VertexList, int Color,
  63.       int PolygonShape, int XOffset, int YOffset)
  64. {
  65.    struct EdgeState *EdgeTableBuffer;
  66.    int CurrentY;
  67.  
  68. #ifdef CONVEX_CODE_LINKED
  69.    /* Pass convex polygons through to fast convex polygon filler */
  70.    if (PolygonShape == CONVEX)
  71.       return(FillConvexPolygon(VertexList, Color, XOffset, YOffset));
  72. #endif
  73.  
  74.    /* It takes a minimum of 3 vertices to cause any pixels to be
  75.       drawn; reject polygons that are guaranteed to be invisible */
  76.    if (VertexList->Length < 3)
  77.       return(1);
  78.    /* Get enough memory to store the entire edge table */
  79.    if ((EdgeTableBuffer =
  80.          (struct EdgeState *) (malloc(sizeof(struct EdgeState) *
  81.          VertexList->Length))) == NULL)
  82.       return(0);  /* couldn't get memory for the edge table */
  83.    /* Build the global edge table */
  84.    BuildGET(VertexList, EdgeTableBuffer, XOffset, YOffset);
  85.    /* Scan down through the polygon edges, one scan line at a time,
  86.       so long as at least one edge remains in either the GET or AET */
  87.    AETPtr = NULL;    /* initialize the active edge table to empty */
  88.    CurrentY = GETPtr->StartY; /* start at the top polygon vertex */
  89.    while ((GETPtr != NULL) || (AETPtr != NULL)) {
  90.       MoveXSortedToAET(CurrentY);  /* update AET for this scan line */
  91.       ScanOutAET(CurrentY, Color); /* draw this scan line from AET */
  92.       AdvanceAET();                /* advance AET edges 1 scan line */
  93.       XSortAET();                  /* resort on X */
  94.       CurrentY++;                  /* advance to the next scan line */
  95.    }
  96.    /* Release the memory we've allocated and we're done */
  97.    free(EdgeTableBuffer);
  98.    return(1);
  99. }
  100.  
  101. /* Creates a GET in the buffer pointed to by NextFreeEdgeStruc from
  102.    the vertex list. Edge endpoints are flipped, if necessary, to
  103.    guarantee all edges go top to bottom. The GET is sorted primarily
  104.    by ascending Y start coordinate, and secondarily by ascending X
  105.    start coordinate within edges with common Y coordinates */
  106. static void BuildGET(struct PointListHeader * VertexList,
  107.       struct EdgeState * NextFreeEdgeStruc, int XOffset, int YOffset)
  108. {
  109.    int i, StartX, StartY, EndX, EndY, DeltaY, DeltaX, Width, temp;
  110.    struct EdgeState *NewEdgePtr;
  111.    struct EdgeState *FollowingEdge, **FollowingEdgeLink;
  112.    struct Point *VertexPtr;
  113.  
  114.    /* Scan through the vertex list and put all non-0-height edges into
  115.       the GET, sorted by increasing Y start coordinate */
  116.    VertexPtr = VertexList->PointPtr;   /* point to the vertex list */
  117.    GETPtr = NULL;    /* initialize the global edge table to empty */
  118.    for (i = 0; i < VertexList->Length; i++) {
  119.       /* Calculate the edge height and width */
  120.       StartX = VertexPtr[i].X + XOffset;
  121.       StartY = VertexPtr[i].Y + YOffset;
  122.       /* The edge runs from the current point to the previous one */
  123.       if (i == 0) {
  124.          /* Wrap back around to the end of the list */
  125.          EndX = VertexPtr[VertexList->Length-1].X + XOffset;
  126.          EndY = VertexPtr[VertexList->Length-1].Y + YOffset;
  127.       } else {
  128.          EndX = VertexPtr[i-1].X + XOffset;
  129.          EndY = VertexPtr[i-1].Y + YOffset;
  130.       }
  131.       /* Make sure the edge runs top to bottom */
  132.       if (StartY > EndY) {
  133.          SWAP(StartX, EndX);
  134.          SWAP(StartY, EndY);
  135.       }
  136.       /* Skip if this can't ever be an active edge (has 0 height) */
  137.       if ((DeltaY = EndY - StartY) != 0) {
  138.          /* Allocate space for this edge's info, and fill in the
  139.             structure */
  140.          NewEdgePtr = NextFreeEdgeStruc++;
  141.          NewEdgePtr->XDirection =   /* direction in which X moves */
  142.                ((DeltaX = EndX - StartX) > 0) ? 1 : -1;
  143.          Width = abs(DeltaX);
  144.          NewEdgePtr->X = StartX;
  145.          NewEdgePtr->StartY = StartY;
  146.          NewEdgePtr->Count = DeltaY;
  147.          NewEdgePtr->ErrorTermAdjDown = DeltaY;
  148.          if (DeltaX >= 0)  /* initial error term going L->R */
  149.             NewEdgePtr->ErrorTerm = 0;
  150.          else              /* initial error term going R->L */
  151.             NewEdgePtr->ErrorTerm = -DeltaY + 1;
  152.          if (DeltaY >= Width) {     /* Y-major edge */
  153.             NewEdgePtr->WholePixelXMove = 0;
  154.             NewEdgePtr->ErrorTermAdjUp = Width;
  155.          } else {                   /* X-major edge */
  156.             NewEdgePtr->WholePixelXMove =
  157.                   (Width / DeltaY) * NewEdgePtr->XDirection;
  158.             NewEdgePtr->ErrorTermAdjUp = Width % DeltaY;
  159.          }
  160.          /* Link the new edge into the GET so that the edge list is
  161.             still sorted by Y coordinate, and by X coordinate for all
  162.             edges with the same Y coordinate */
  163.          FollowingEdgeLink = &GETPtr;
  164.          for (;;) {
  165.             FollowingEdge = *FollowingEdgeLink;
  166.             if ((FollowingEdge == NULL) ||
  167.                   (FollowingEdge->StartY > StartY) ||
  168.                   ((FollowingEdge->StartY == StartY) &&
  169.                   (FollowingEdge->X >= StartX))) {
  170.                NewEdgePtr->NextEdge = FollowingEdge;
  171.                *FollowingEdgeLink = NewEdgePtr;
  172.                break;
  173.             }
  174.             FollowingEdgeLink = &FollowingEdge->NextEdge;
  175.          }
  176.       }
  177.    }
  178. }
  179.  
  180. /* Sorts all edges currently in the active edge table into ascending
  181.    order of current X coordinates */
  182. static void XSortAET() {
  183.    struct EdgeState *CurrentEdge, **CurrentEdgePtr, *TempEdge;
  184.    int SwapOccurred;
  185.  
  186.    /* Scan through the AET and swap any adjacent edges for which the
  187.       second edge is at a lower current X coord than the first edge.
  188.       Repeat until no further swapping is needed */
  189.    if (AETPtr != NULL) {
  190.       do {
  191.          SwapOccurred = 0;
  192.          CurrentEdgePtr = &AETPtr;
  193.          while ((CurrentEdge = *CurrentEdgePtr)->NextEdge != NULL) {
  194.             if (CurrentEdge->X > CurrentEdge->NextEdge->X) {
  195.                /* The second edge has a lower X than the first;
  196.                   swap them in the AET */
  197.                TempEdge = CurrentEdge->NextEdge->NextEdge;
  198.                *CurrentEdgePtr = CurrentEdge->NextEdge;
  199.                CurrentEdge->NextEdge->NextEdge = CurrentEdge;
  200.                CurrentEdge->NextEdge = TempEdge;
  201.                SwapOccurred = 1;
  202.             }
  203.             CurrentEdgePtr = &(*CurrentEdgePtr)->NextEdge;
  204.          }
  205.       } while (SwapOccurred != 0);
  206.    }
  207. }
  208.  
  209. /* Advances each edge in the AET by one scan line.
  210.    Removes edges that have been fully scanned. */
  211. static void AdvanceAET() {
  212.    struct EdgeState *CurrentEdge, **CurrentEdgePtr;
  213.  
  214.    /* Count down and remove or advance each edge in the AET */
  215.    CurrentEdgePtr = &AETPtr;
  216.    while ((CurrentEdge = *CurrentEdgePtr) != NULL) {
  217.       /* Count off one scan line for this edge */
  218.       if ((--(CurrentEdge->Count)) == 0) {
  219.          /* This edge is finished, so remove it from the AET */
  220.          *CurrentEdgePtr = CurrentEdge->NextEdge;
  221.       } else {
  222.          /* Advance the edge's X coordinate by minimum move */
  223.          CurrentEdge->X += CurrentEdge->WholePixelXMove;
  224.          /* Determine whether it's time for X to advance one extra */
  225.          if ((CurrentEdge->ErrorTerm +=
  226.                CurrentEdge->ErrorTermAdjUp) > 0) {
  227.             CurrentEdge->X += CurrentEdge->XDirection;
  228.             CurrentEdge->ErrorTerm -= CurrentEdge->ErrorTermAdjDown;
  229.          }
  230.          CurrentEdgePtr = &CurrentEdge->NextEdge;
  231.       }
  232.    }
  233. }
  234.  
  235. /* Moves all edges that start at the specified Y coordinate from the
  236.    GET to the AET, maintaining the X sorting of the AET. */
  237. static void MoveXSortedToAET(int YToMove) {
  238.    struct EdgeState *AETEdge, **AETEdgePtr, *TempEdge;
  239.    int CurrentX;
  240.  
  241.    /* The GET is Y sorted. Any edges that start at the desired Y
  242.       coordinate will be first in the GET, so we'll move edges from
  243.       the GET to AET until the first edge left in the GET is no longer
  244.       at the desired Y coordinate. Also, the GET is X sorted within
  245.       each Y coordinate, so each successive edge we add to the AET is
  246.       guaranteed to belong later in the AET than the one just added */
  247.    AETEdgePtr = &AETPtr;
  248.    while ((GETPtr != NULL) && (GETPtr->StartY == YToMove)) {
  249.       CurrentX = GETPtr->X;
  250.       /* Link the new edge into the AET so that the AET is still
  251.          sorted by X coordinate */
  252.       for (;;) {
  253.          AETEdge = *AETEdgePtr;
  254.          if ((AETEdge == NULL) || (AETEdge->X >= CurrentX)) {
  255.             TempEdge = GETPtr->NextEdge;
  256.             *AETEdgePtr = GETPtr;  /* link the edge into the AET */
  257.             GETPtr->NextEdge = AETEdge;
  258.             AETEdgePtr = &GETPtr->NextEdge;
  259.             GETPtr = TempEdge;   /* unlink the edge from the GET */
  260.             break;
  261.          } else {
  262.             AETEdgePtr = &AETEdge->NextEdge;
  263.          }
  264.       }
  265.    }
  266. }
  267.  
  268. /* Fills the scan line described by the current AET at the specified Y
  269.    coordinate in the specified color, using the odd/even fill rule */
  270. static void ScanOutAET(int YToScan, int Color) {
  271.    int LeftX;
  272.    struct EdgeState *CurrentEdge;
  273.  
  274.    /* Scan through the AET, drawing line segments as each pair of edge
  275.       crossings is encountered. The nearest pixel on or to the right
  276.       of left edges is drawn, and the nearest pixel to the left of but
  277.       not on right edges is drawn */
  278.    CurrentEdge = AETPtr;
  279.    while (CurrentEdge != NULL) {
  280.       LeftX = CurrentEdge->X;
  281.       CurrentEdge = CurrentEdge->NextEdge;
  282.       DrawHorizontalLineSeg(YToScan, LeftX, CurrentEdge->X-1, Color);
  283.       CurrentEdge = CurrentEdge->NextEdge;
  284.    }
  285. }
  286.  
  287.  
  288. [LISTING TWO]
  289.  
  290. /* Draws all pixels in the horizontal line segment passed in, from
  291.    (LeftX,Y) to (RightX,Y), in the specified color in mode 13h, the
  292.    VGA's 320x200 256-color mode. Both LeftX and RightX are drawn. No
  293.    drawing will take place if LeftX > RightX. */
  294.  
  295. #include <dos.h>
  296. #include "polygon.h"
  297.  
  298. #define SCREEN_WIDTH    320
  299. #define SCREEN_SEGMENT  0xA000
  300.  
  301. static void DrawPixel(int, int, int);
  302.  
  303. void DrawHorizontalLineSeg(Y, LeftX, RightX, Color) {
  304.    int X;
  305.  
  306.    /* Draw each pixel in the horizontal line segment, starting with
  307.       the leftmost one */
  308.    for (X = LeftX; X <= RightX; X++)
  309.       DrawPixel(X, Y, Color);
  310. }
  311.  
  312. /* Draws the pixel at (X, Y) in color Color in VGA mode 13h */
  313. static void DrawPixel(int X, int Y, int Color) {
  314.    unsigned char far *ScreenPtr;
  315.  
  316. #ifdef __TURBOC__
  317.    ScreenPtr = MK_FP(SCREEN_SEGMENT, Y * SCREEN_WIDTH + X);
  318. #else    /* MSC 5.0 */
  319.    FP_SEG(ScreenPtr) = SCREEN_SEGMENT;
  320.    FP_OFF(ScreenPtr) = Y * SCREEN_WIDTH + X;
  321. #endif
  322.    *ScreenPtr = (unsigned char) Color;
  323. }
  324.  
  325.  
  326. [LISTING THREE]
  327.  
  328. /* POLYGON.H: Header file for polygon-filling code */
  329.  
  330. #define CONVEX    0
  331. #define NONCONVEX 1
  332. #define COMPLEX   2
  333.  
  334. /* Describes a single point (used for a single vertex) */
  335. struct Point {
  336.    int X;   /* X coordinate */
  337.    int Y;   /* Y coordinate */
  338. };
  339. /* Describes a series of points (used to store a list of vertices that
  340.    describe a polygon; each vertex connects to the two adjacent
  341.    vertices; the last vertex is assumed to connect to the first) */
  342. struct PointListHeader {
  343.    int Length;                /* # of points */
  344.    struct Point * PointPtr;   /* pointer to list of points */
  345. };
  346. /* Describes the beginning and ending X coordinates of a single
  347.    horizontal line (used only by fast polygon fill code) */
  348. struct HLine {
  349.    int XStart; /* X coordinate of leftmost pixel in line */
  350.    int XEnd;   /* X coordinate of rightmost pixel in line */
  351. };
  352. /* Describes a Length-long series of horizontal lines, all assumed to
  353.    be on contiguous scan lines starting at YStart and proceeding
  354.    downward (used to describe a scan-converted polygon to the
  355.    low-level hardware-dependent drawing code) (used only by fast
  356.    polygon fill code) */
  357. struct HLineList {
  358.    int Length;                /* # of horizontal lines */
  359.    int YStart;                /* Y coordinate of topmost line */
  360.    struct HLine * HLinePtr;   /* pointer to list of horz lines */
  361. };
  362.  
  363.  
  364.  
  365. [LISTING FOUR]
  366.  
  367. /* Sample program to exercise the polygon-filling routines */
  368.  
  369. #include <conio.h>
  370. #include <dos.h>
  371. #include "polygon.h"
  372.  
  373. #define DRAW_POLYGON(PointList,Color,Shape,X,Y)             \
  374.    Polygon.Length = sizeof(PointList)/sizeof(struct Point); \
  375.    Polygon.PointPtr = PointList;                            \
  376.    FillPolygon(&Polygon, Color, Shape, X, Y);
  377.    
  378. void main(void);
  379. extern int FillPolygon(struct PointListHeader *, int, int, int, int);
  380.  
  381. void main() {
  382.    int i, j;
  383.    struct PointListHeader Polygon;
  384.    static struct Point Polygon1[] =
  385.          {{0,0},{100,150},{320,0},{0,200},{220,50},{320,200}};
  386.    static struct Point Polygon2[] =
  387.          {{0,0},{320,0},{320,200},{0,200},{0,0},{50,50},
  388.           {270,50},{270,150},{50,150},{50,50}};
  389.    static struct Point Polygon3[] =
  390.          {{0,0},{10,0},{105,185},{260,30},{15,150},{5,150},{5,140},
  391.           {260,5},{300,5},{300,15},{110,200},{100,200},{0,10}};
  392.    static struct Point Polygon4[] =
  393.          {{0,0},{30,-20},{30,0},{0,20},{-30,0},{-30,-20}};
  394.    static struct Point Triangle1[] = {{30,0},{15,20},{0,0}};
  395.    static struct Point Triangle2[] = {{30,20},{15,0},{0,20}};
  396.    static struct Point Triangle3[] = {{0,20},{20,10},{0,0}};
  397.    static struct Point Triangle4[] = {{20,20},{20,0},{0,10}};
  398.    union REGS regset;
  399.  
  400.    /* Set the display to VGA mode 13h, 320x200 256-color mode */
  401.    regset.x.ax = 0x0013;
  402.    int86(0x10, ®set, ®set);
  403.  
  404.    /* Draw three complex polygons */
  405.    DRAW_POLYGON(Polygon1, 15, COMPLEX, 0, 0);
  406.    getch();    /* wait for a keypress */
  407.    DRAW_POLYGON(Polygon2, 5, COMPLEX, 0, 0);
  408.    getch();    /* wait for a keypress */
  409.    DRAW_POLYGON(Polygon3, 3, COMPLEX, 0, 0);
  410.    getch();    /* wait for a keypress */
  411.  
  412.    /* Draw some adjacent nonconvex polygons */
  413.    for (i=0; i<5; i++) {
  414.       for (j=0; j<8; j++) {
  415.          DRAW_POLYGON(Polygon4, 16+i*8+j, NONCONVEX, 40+(i*60),
  416.                30+(j*20));
  417.       }
  418.    }
  419.    getch();    /* wait for a keypress */
  420.  
  421.    /* Draw adjacent triangles across the screen */
  422.    for (j=0; j<=80; j+=20) {
  423.       for (i=0; i<290; i += 30) {
  424.          DRAW_POLYGON(Triangle1, 2, CONVEX, i, j);
  425.          DRAW_POLYGON(Triangle2, 4, CONVEX, i+15, j);
  426.       }
  427.    }
  428.    for (j=100; j<=170; j+=20) {
  429.       /* Do a row of pointing-right triangles */
  430.       for (i=0; i<290; i += 20) {
  431.          DRAW_POLYGON(Triangle3, 40, CONVEX, i, j);
  432.       }
  433.       /* Do a row of pointing-left triangles halfway between one row
  434.          of pointing-right triangles and the next, to fit between */
  435.       for (i=0; i<290; i += 20) {
  436.          DRAW_POLYGON(Triangle4, 1, CONVEX, i, j+10);
  437.       }
  438.    }
  439.    getch();    /* wait for a keypress */
  440.  
  441.    /* Return to text mode and exit */
  442.    regset.x.ax = 0x0003;
  443.    int86(0x10, ®set, ®set);
  444. }
  445.  
  446.  
  447.  
  448. [LISTING FIVE]
  449.  
  450.  
  451. ; Draws all pixels in the horizontal line segment passed in, from
  452. ;  (LeftX,Y) to (RightX,Y), in the specified color in mode 13h, the
  453. ;  VGA's 320x200 256-color mode. No drawing will take place if
  454. ;  LeftX > RightX. Tested with TASM 2.0
  455. ; C near-callable as:
  456. ;       void DrawHorizontalLineSeg(Y, LeftX, RightX, Color);
  457.  
  458. SCREEN_WIDTH    equ     320
  459. SCREEN_SEGMENT  equ     0a000h
  460.  
  461. Parms   struc
  462.         dw      2 dup(?) ;return address & pushed BP
  463. Y       dw      ?       ;Y coordinate of line segment to draw
  464. LeftX   dw      ?       ;left endpoint of the line segment
  465. RightX  dw      ?       ;right endpoint of the line segment
  466. Color   dw      ?       ;color in which to draw the line segment
  467. Parms   ends
  468.  
  469.         .model small
  470.         .code
  471.         public _DrawHorizontalLineSeg
  472.         align   2
  473. _DrawHorizontalLineSeg  proc
  474.         push    bp              ;preserve caller's stack frame
  475.         mov     bp,sp           ;point to our stack frame
  476.         push    di              ;preserve caller's register variable
  477.         cld                     ;make string instructions inc pointers
  478.         mov     ax,SCREEN_SEGMENT
  479.         mov     es,ax           ;point ES to display memory
  480.         mov     di,[bp+LeftX]
  481.         mov     cx,[bp+RightX]
  482.         sub     cx,di           ;width of line
  483.         jl      DrawDone        ;RightX < LeftX; no drawing to do
  484.         inc     cx              ;include both endpoints
  485.         mov     ax,SCREEN_WIDTH
  486.         mul     [bp+Y]          ;offset of scan line on which to draw
  487.         add     di,ax           ;ES:DI points to start of line seg
  488.         mov     al,byte ptr [bp+Color] ;color in which to draw
  489.         mov     ah,al           ;put color in AH for STOSW
  490.         shr     cx,1            ;# of words to fill
  491.         rep     stosw           ;fill a word at a time
  492.         adc     cx,cx
  493.         rep     stosb           ;draw the odd byte, if any
  494. DrawDone:
  495.         pop     di              ;restore caller's register variable
  496.         pop     bp              ;restore caller's stack frame
  497.         ret
  498. _DrawHorizontalLineSeg  endp
  499.         end
  500.  
  501.  
  502.