home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1991 / 02 / graphics.asc < prev    next >
Text File  |  1990-12-26  |  16KB  |  396 lines
  1. _GRAPHICS PROGRAMMING COLUMN_
  2. by Michael Abrash
  3.  
  4. [LISTING ONE]
  5.  
  6. /* Color-fills a convex polygon. All vertices are offset by (XOffset,
  7.    YOffset). "Convex" means that every horizontal line drawn through
  8.    the polygon at any point would cross exactly two active edges
  9.    (neither horizontal lines nor zero-length edges count as active
  10.    edges; both are acceptable anywhere in the polygon), and that the
  11.    right & left edges never cross. (It's OK for them to touch, though,
  12.    so long as the right edge never crosses over to the left of the
  13.    left edge.) Nonconvex polygons won't be drawn properly. Returns 1
  14.    for success, 0 if memory allocation failed */
  15.  
  16. #include <stdio.h>
  17. #include <math.h>
  18. #ifdef __TURBOC__
  19. #include <alloc.h>
  20. #else    /* MSC */
  21. #include <malloc.h>
  22. #endif
  23. #include "polygon.h"
  24.  
  25. /* Advances the index by one vertex forward through the vertex list,
  26.    wrapping at the end of the list */
  27. #define INDEX_FORWARD(Index) \
  28.    Index = (Index + 1) % VertexList->Length;
  29.  
  30. /* Advances the index by one vertex backward through the vertex list,
  31.    wrapping at the start of the list */
  32. #define INDEX_BACKWARD(Index) \
  33.    Index = (Index - 1 + VertexList->Length) % VertexList->Length;
  34.  
  35. /* Advances the index by one vertex either forward or backward through
  36.    the vertex list, wrapping at either end of the list */
  37. #define INDEX_MOVE(Index,Direction)                                  \
  38.    if (Direction > 0)                                                \
  39.       Index = (Index + 1) % VertexList->Length;                      \
  40.    else                                                              \
  41.       Index = (Index - 1 + VertexList->Length) % VertexList->Length;
  42.  
  43. extern void DrawHorizontalLineList(struct HLineList *, int);
  44. static void ScanEdge(int, int, int, int, int, int, struct HLine **);
  45.  
  46. int FillConvexPolygon(struct PointListHeader * VertexList, int Color,
  47.       int XOffset, int YOffset)
  48. {
  49.    int i, MinIndexL, MaxIndex, MinIndexR, SkipFirst, Temp;
  50.    int MinPoint_Y, MaxPoint_Y, TopIsFlat, LeftEdgeDir;
  51.    int NextIndex, CurrentIndex, PreviousIndex;
  52.    int DeltaXN, DeltaYN, DeltaXP, DeltaYP;
  53.    struct HLineList WorkingHLineList;
  54.    struct HLine *EdgePointPtr;
  55.    struct Point *VertexPtr;
  56.  
  57.    /* Point to the vertex list */
  58.    VertexPtr = VertexList->PointPtr;
  59.  
  60.    /* Scan the list to find the top and bottom of the polygon */
  61.    if (VertexList->Length == 0)
  62.       return(1);  /* reject null polygons */
  63.    MaxPoint_Y = MinPoint_Y = VertexPtr[MinIndexL = MaxIndex = 0].Y;
  64.    for (i = 1; i < VertexList->Length; i++) {
  65.       if (VertexPtr[i].Y < MinPoint_Y)
  66.          MinPoint_Y = VertexPtr[MinIndexL = i].Y; /* new top */
  67.       else if (VertexPtr[i].Y > MaxPoint_Y)
  68.          MaxPoint_Y = VertexPtr[MaxIndex = i].Y; /* new bottom */
  69.    }
  70.    if (MinPoint_Y == MaxPoint_Y)
  71.       return(1);  /* polygon is 0-height; avoid infinite loop below */
  72.  
  73.    /* Scan in ascending order to find the last top-edge point */
  74.    MinIndexR = MinIndexL;
  75.    while (VertexPtr[MinIndexR].Y == MinPoint_Y)
  76.       INDEX_FORWARD(MinIndexR);
  77.    INDEX_BACKWARD(MinIndexR); /* back up to last top-edge point */
  78.  
  79.    /* Now scan in descending order to find the first top-edge point */
  80.    while (VertexPtr[MinIndexL].Y == MinPoint_Y)
  81.       INDEX_BACKWARD(MinIndexL);
  82.    INDEX_FORWARD(MinIndexL); /* back up to first top-edge point */
  83.  
  84.    /* Figure out which direction through the vertex list from the top
  85.       vertex is the left edge and which is the right */
  86.    LeftEdgeDir = -1; /* assume left edge runs down thru vertex list */
  87.    if ((TopIsFlat = (VertexPtr[MinIndexL].X !=
  88.          VertexPtr[MinIndexR].X) ? 1 : 0) == 1) {
  89.       /* If the top is flat, just see which of the ends is leftmost */
  90.       if (VertexPtr[MinIndexL].X > VertexPtr[MinIndexR].X) {
  91.          LeftEdgeDir = 1;  /* left edge runs up through vertex list */
  92.          Temp = MinIndexL;       /* swap the indices so MinIndexL   */
  93.          MinIndexL = MinIndexR;  /* points to the start of the left */
  94.          MinIndexR = Temp;       /* edge, similarly for MinIndexR   */
  95.       }
  96.    } else {
  97.       /* Point to the downward end of the first line of each of the
  98.          two edges down from the top */
  99.       NextIndex = MinIndexR;
  100.       INDEX_FORWARD(NextIndex);
  101.       PreviousIndex = MinIndexL;
  102.       INDEX_BACKWARD(PreviousIndex);
  103.       /* Calculate X and Y lengths from the top vertex to the end of
  104.          the first line down each edge; use those to compare slopes
  105.          and see which line is leftmost */
  106.       DeltaXN = VertexPtr[NextIndex].X - VertexPtr[MinIndexL].X;
  107.       DeltaYN = VertexPtr[NextIndex].Y - VertexPtr[MinIndexL].Y;
  108.       DeltaXP = VertexPtr[PreviousIndex].X - VertexPtr[MinIndexL].X;
  109.       DeltaYP = VertexPtr[PreviousIndex].Y - VertexPtr[MinIndexL].Y;
  110.       if (((long)DeltaXN * DeltaYP - (long)DeltaYN * DeltaXP) < 0L) {
  111.          LeftEdgeDir = 1;  /* left edge runs up through vertex list */
  112.          Temp = MinIndexL;       /* swap the indices so MinIndexL   */
  113.          MinIndexL = MinIndexR;  /* points to the start of the left */
  114.          MinIndexR = Temp;       /* edge, similarly for MinIndexR   */
  115.       }
  116.    }
  117.  
  118.    /* Set the # of scan lines in the polygon, skipping the bottom edge
  119.       and also skipping the top vertex if the top isn't flat because
  120.       in that case the top vertex has a right edge component, and set
  121.       the top scan line to draw, which is likewise the second line of
  122.       the polygon unless the top is flat */
  123.    if ((WorkingHLineList.Length =
  124.          MaxPoint_Y - MinPoint_Y - 1 + TopIsFlat) <= 0)
  125.       return(1);  /* there's nothing to draw, so we're done */
  126.    WorkingHLineList.YStart = YOffset + MinPoint_Y + 1 - TopIsFlat;
  127.  
  128.    /* Get memory in which to store the line list we generate */
  129.    if ((WorkingHLineList.HLinePtr =
  130.          (struct HLine *) (malloc(sizeof(struct HLine) *
  131.          WorkingHLineList.Length))) == NULL)
  132.       return(0);  /* couldn't get memory for the line list */
  133.  
  134.    /* Scan the left edge and store the boundary points in the list */
  135.    /* Initial pointer for storing scan converted left-edge coords */
  136.    EdgePointPtr = WorkingHLineList.HLinePtr;
  137.    /* Start from the top of the left edge */
  138.    PreviousIndex = CurrentIndex = MinIndexL;
  139.    /* Skip the first point of the first line unless the top is flat;
  140.       if the top isn't flat, the top vertex is exactly on a right
  141.       edge and isn't drawn */
  142.    SkipFirst = TopIsFlat ? 0 : 1;
  143.    /* Scan convert each line in the left edge from top to bottom */
  144.    do {
  145.       INDEX_MOVE(CurrentIndex,LeftEdgeDir);
  146.       ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
  147.             VertexPtr[PreviousIndex].Y,
  148.             VertexPtr[CurrentIndex].X + XOffset,
  149.             VertexPtr[CurrentIndex].Y, 1, SkipFirst, &EdgePointPtr);
  150.       PreviousIndex = CurrentIndex;
  151.       SkipFirst = 0; /* scan convert the first point from now on */
  152.    } while (CurrentIndex != MaxIndex);
  153.  
  154.    /* Scan the right edge and store the boundary points in the list */
  155.    EdgePointPtr = WorkingHLineList.HLinePtr;
  156.    PreviousIndex = CurrentIndex = MinIndexR;
  157.    SkipFirst = TopIsFlat ? 0 : 1;
  158.    /* Scan convert the right edge, top to bottom. X coordinates are
  159.       adjusted 1 to the left, effectively causing scan conversion of
  160.       the nearest points to the left of but not exactly on the edge */
  161.    do {
  162.       INDEX_MOVE(CurrentIndex,-LeftEdgeDir);
  163.       ScanEdge(VertexPtr[PreviousIndex].X + XOffset - 1,
  164.             VertexPtr[PreviousIndex].Y,
  165.             VertexPtr[CurrentIndex].X + XOffset - 1,
  166.             VertexPtr[CurrentIndex].Y, 0, SkipFirst, &EdgePointPtr);
  167.       PreviousIndex = CurrentIndex;
  168.       SkipFirst = 0; /* scan convert the first point from now on */
  169.    } while (CurrentIndex != MaxIndex);
  170.  
  171.    /* Draw the line list representing the scan converted polygon */
  172.    DrawHorizontalLineList(&WorkingHLineList, Color);
  173.  
  174.    /* Release the line list's memory and we're successfully done */
  175.    free(WorkingHLineList.HLinePtr);
  176.    return(1);
  177. }
  178.  
  179. /* Scan converts an edge from (X1,Y1) to (X2,Y2), not including the
  180.    point at (X2,Y2). This avoids overlapping the end of one line with
  181.    the start of the next, and causes the bottom scan line of the
  182.    polygon not to be drawn. If SkipFirst != 0, the point at (X1,Y1)
  183.    isn't drawn. For each scan line, the pixel closest to the scanned
  184.    line without being to the left of the scanned line is chosen */
  185. static void ScanEdge(int X1, int Y1, int X2, int Y2, int SetXStart,
  186.       int SkipFirst, struct HLine **EdgePointPtr)
  187. {
  188.    int Y, DeltaX, DeltaY;
  189.    double InverseSlope;
  190.    struct HLine *WorkingEdgePointPtr;
  191.  
  192.    /* Calculate X and Y lengths of the line and the inverse slope */
  193.    DeltaX = X2 - X1;
  194.    if ((DeltaY = Y2 - Y1) <= 0)
  195.       return;     /* guard against 0-length and horizontal edges */
  196.    InverseSlope = (double)DeltaX / (double)DeltaY;
  197.  
  198.    /* Store the X coordinate of the pixel closest to but not to the
  199.       left of the line for each Y coordinate between Y1 and Y2, not
  200.       including Y2 and also not including Y1 if SkipFirst != 0 */
  201.    WorkingEdgePointPtr = *EdgePointPtr; /* avoid double dereference */
  202.    for (Y = Y1 + SkipFirst; Y < Y2; Y++, WorkingEdgePointPtr++) {
  203.       /* Store the X coordinate in the appropriate edge list */
  204.       if (SetXStart == 1)
  205.          WorkingEdgePointPtr->XStart =
  206.                X1 + (int)(ceil((Y-Y1) * InverseSlope));
  207.       else
  208.          WorkingEdgePointPtr->XEnd =
  209.                X1 + (int)(ceil((Y-Y1) * InverseSlope));
  210.    }
  211.    *EdgePointPtr = WorkingEdgePointPtr;   /* advance caller's ptr */
  212. }
  213.  
  214.  
  215. [LISTING TWO]
  216.  
  217.  
  218. /* Draws all pixels in the list of horizontal lines passed in, in
  219.    mode 13h, the VGA's 320x200 256-color mode. Uses a slow pixel-by-
  220.    pixel approach, which does have the virtue of being easily ported
  221.    to any environment. */
  222.  
  223. #include <dos.h>
  224. #include "polygon.h"
  225.  
  226. #define SCREEN_WIDTH    320
  227. #define SCREEN_SEGMENT  0xA000
  228.  
  229. static void DrawPixel(int, int, int);
  230.  
  231. void DrawHorizontalLineList(struct HLineList * HLineListPtr,
  232.       int Color)
  233. {
  234.    struct HLine *HLinePtr;
  235.    int Y, X;
  236.  
  237.    /* Point to the XStart/XEnd descriptor for the first (top)
  238.       horizontal line */
  239.    HLinePtr = HLineListPtr->HLinePtr;
  240.    /* Draw each horizontal line in turn, starting with the top one and
  241.       advancing one line each time */
  242.    for (Y = HLineListPtr->YStart; Y < (HLineListPtr->YStart +
  243.          HLineListPtr->Length); Y++, HLinePtr++) {
  244.       /* Draw each pixel in the current horizontal line in turn,
  245.          starting with the leftmost one */
  246.       for (X = HLinePtr->XStart; X <= HLinePtr->XEnd; X++)
  247.          DrawPixel(X, Y, Color);
  248.    }
  249. }
  250.  
  251. /* Draws the pixel at (X, Y) in color Color in VGA mode 13h */
  252. static void DrawPixel(int X, int Y, int Color) {
  253.    unsigned char far *ScreenPtr;
  254.  
  255. #ifdef __TURBOC__
  256.    ScreenPtr = MK_FP(SCREEN_SEGMENT, Y * SCREEN_WIDTH + X);
  257. #else    /* MSC 5.0 */
  258.    FP_SEG(ScreenPtr) = SCREEN_SEGMENT;
  259.    FP_OFF(ScreenPtr) = Y * SCREEN_WIDTH + X;
  260. #endif
  261.    *ScreenPtr = (unsigned char)Color;
  262. }
  263.  
  264.  
  265. [LISTING THREE]
  266.  
  267. /* Sample program to exercise the polygon-filling routines. This code
  268.    and all polygon-filling code has been tested with Turbo C 2.0 and
  269.    Microsoft C 5.0 */
  270.  
  271. #include <conio.h>
  272. #include <dos.h>
  273. #include "polygon.h"
  274.  
  275. /* Draws the polygon described by the point list PointList in color
  276.    Color with all vertices offset by (X,Y) */
  277. #define DRAW_POLYGON(PointList,Color,X,Y)                   \
  278.    Polygon.Length = sizeof(PointList)/sizeof(struct Point); \
  279.    Polygon.PointPtr = PointList;                            \
  280.    FillConvexPolygon(&Polygon, Color, X, Y);
  281.    
  282. void main(void);
  283. extern int FillConvexPolygon(struct PointListHeader *, int, int, int);
  284.  
  285. void main() {
  286.    int i, j;
  287.    struct PointListHeader Polygon;
  288.    static struct Point ScreenRectangle[] =
  289.          {{0,0},{320,0},{320,200},{0,200}};
  290.    static struct Point ConvexShape[] =
  291.          {{0,0},{121,0},{320,0},{200,51},{301,51},{250,51},{319,143},
  292.          {320,200},{22,200},{0,200},{50,180},{20,160},{50,140},
  293.          {20,120},{50,100},{20,80},{50,60},{20,40},{50,20}};
  294.    static struct Point Hexagon[] =
  295.          {{90,-50},{0,-90},{-90,-50},{-90,50},{0,90},{90,50}};
  296.    static struct Point Triangle1[] = {{30,0},{15,20},{0,0}};
  297.    static struct Point Triangle2[] = {{30,20},{15,0},{0,20}};
  298.    static struct Point Triangle3[] = {{0,20},{20,10},{0,0}};
  299.    static struct Point Triangle4[] = {{20,20},{20,0},{0,10}};
  300.    union REGS regset;
  301.  
  302.    /* Set the display to VGA mode 13h, 320x200 256-color mode */
  303.    regset.x.ax = 0x0013;   /* AH = 0 selects mode set function,
  304.                               AL = 0x13 selects mode 0x13
  305.                               when set as parameters for INT 0x10 */
  306.    int86(0x10, ®set, ®set);
  307.  
  308.    /* Clear the screen to cyan */
  309.    DRAW_POLYGON(ScreenRectangle, 3, 0, 0);
  310.  
  311.    /* Draw an irregular shape that meets our definition of convex but
  312.       is not convex by any normal description */
  313.    DRAW_POLYGON(ConvexShape, 6, 0, 0);
  314.    getch();    /* wait for a keypress */
  315.  
  316.    /* Draw adjacent triangles across the top half of the screen */
  317.    for (j=0; j<=80; j+=20) {
  318.       for (i=0; i<290; i += 30) {
  319.          DRAW_POLYGON(Triangle1, 2, i, j);
  320.          DRAW_POLYGON(Triangle2, 4, i+15, j);
  321.       }
  322.    }
  323.  
  324.    /* Draw adjacent triangles across the bottom half of the screen */
  325.    for (j=100; j<=170; j+=20) {
  326.       /* Do a row of pointing-right triangles */
  327.       for (i=0; i<290; i += 20) {
  328.          DRAW_POLYGON(Triangle3, 40, i, j);
  329.       }
  330.       /* Do a row of pointing-left triangles halfway between one row
  331.          of pointing-right triangles and the next, to fit between */
  332.       for (i=0; i<290; i += 20) {
  333.          DRAW_POLYGON(Triangle4, 1, i, j+10);
  334.       }
  335.    }
  336.    getch();    /* wait for a keypress */
  337.  
  338.    /* Finally, draw a series of concentric hexagons of approximately
  339.       the same proportions in the center of the screen */
  340.    for (i=0; i<16; i++) {
  341.       DRAW_POLYGON(Hexagon, i, 160, 100);
  342.       for (j=0; j<sizeof(Hexagon)/sizeof(struct Point); j++) {
  343.          /* Advance each vertex toward the center */
  344.          if (Hexagon[j].X != 0) {
  345.             Hexagon[j].X -= Hexagon[j].X >= 0 ? 3 : -3;
  346.             Hexagon[j].Y -= Hexagon[j].Y >= 0 ? 2 : -2;
  347.          } else {
  348.             Hexagon[j].Y -= Hexagon[j].Y >= 0 ? 3 : -3;
  349.          }
  350.       }
  351.    }
  352.    getch();    /* wait for a keypress */
  353.  
  354.    /* Return to text mode and exit */
  355.    regset.x.ax = 0x0003;   /* AL = 3 selects 80x25 text mode */
  356.    int86(0x10, ®set, ®set);
  357. }
  358.  
  359.  
  360. [LISTING FOUR]
  361.  
  362. /* POLYGON.H: Header file for polygon-filling code */
  363.  
  364. /* Describes a single point (used for a single vertex) */
  365. struct Point {
  366.    int X;   /* X coordinate */
  367.    int Y;   /* Y coordinate */
  368. };
  369.  
  370. /* Describes a series of points (used to store a list of vertices that
  371.    describe a polygon; each vertex is assumed to connect to the two
  372.    adjacent vertices, and the last vertex is assumed to connect to the
  373.    first) */
  374. struct PointListHeader {
  375.    int Length;                /* # of points */
  376.    struct Point * PointPtr;   /* pointer to list of points */
  377. };
  378.  
  379. /* Describes the beginning and ending X coordinates of a single
  380.    horizontal line */
  381. struct HLine {
  382.    int XStart; /* X coordinate of leftmost pixel in line */
  383.    int XEnd;   /* X coordinate of rightmost pixel in line */
  384. };
  385.  
  386. /* Describes a Length-long series of horizontal lines, all assumed to
  387.    be on contiguous scan lines starting at YStart and proceeding
  388.    downward (used to describe a scan-converted polygon to the
  389.    low-level hardware-dependent drawing code) */
  390. struct HLineList {
  391.    int Length;                /* # of horizontal lines */
  392.    int YStart;                /* Y coordinate of topmost line */
  393.    struct HLine * HLinePtr;   /* pointer to list of horz lines */
  394. };
  395.  
  396.