home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / source / chapterf / filcnvx.c next >
C/C++ Source or Header  |  1997-06-18  |  8KB  |  175 lines
  1. /* Color-fills a convex polygon, using the passed-in driver to perform
  2.    all drawing. All vertices are offset by (XOffset, YOffset).
  3.    "Convex" means that every horizontal line drawn through the polygon
  4.    at any point would cross exactly two active edges (neither
  5.    horizontal lines nor zero-length edges count as active edges; both
  6.    are acceptable anywhere in the polygon), and that the right & left
  7.    edges never cross. (It's OK for them to touch, though, so long as
  8.    the right edge never crosses over to the left of the left edge.)
  9.    Nonconvex polygons won't be drawn properly. Returns 1 for success,
  10.    0 if memory allocation failed 
  11.    Tested with Borland C++ 4.02 in small model by Jim Mischel 12/16/94.
  12.    Requires L22-4.ASM
  13. */
  14. #include <stdio.h>
  15. #include <math.h>
  16. #ifdef __TURBOC__
  17. #include <alloc.h>
  18. #else    /* MSC */
  19. #include <malloc.h>
  20. #endif
  21. #include "polygon.h"
  22.  
  23. /* Advances the index by one vertex forward through the vertex list,
  24.    wrapping at the end of the list */
  25. #define INDEX_FORWARD(Index) \
  26.    Index = (Index + 1) % VertexList->Length;
  27.  
  28. /* Advances the index by one vertex backward through the vertex list,
  29.    wrapping at the start of the list */
  30. #define INDEX_BACKWARD(Index) \
  31.    Index = (Index - 1 + VertexList->Length) % VertexList->Length;
  32.  
  33. /* Advances the index by one vertex either forward or backward through
  34.    the vertex list, wrapping at either end of the list */
  35. #define INDEX_MOVE(Index,Direction)                                  \
  36.    if (Direction > 0)                                                \
  37.       Index = (Index + 1) % VertexList->Length;                      \
  38.    else                                                              \
  39.       Index = (Index - 1 + VertexList->Length) % VertexList->Length;
  40.  
  41. void ScanEdge(int, int, int, int, int, int, struct HLine **);
  42.  
  43. int FillCnvxPolyDrvr(struct PointListHeader * VertexList, int Color,
  44.       int XOffset, int YOffset, void (*DrawListFunc)())
  45. {
  46.    int i, MinIndexL, MaxIndex, MinIndexR, SkipFirst, Temp;
  47.    int MinPoint_Y, MaxPoint_Y, TopIsFlat, LeftEdgeDir;
  48.    int NextIndex, CurrentIndex, PreviousIndex;
  49.    int DeltaXN, DeltaYN, DeltaXP, DeltaYP;
  50.    struct HLineList WorkingHLineList;
  51.    struct HLine *EdgePointPtr;
  52.    struct Point *VertexPtr;
  53.  
  54.    /* Point to the vertex list */
  55.    VertexPtr = VertexList->PointPtr;
  56.  
  57.    /* Scan the list to find the top and bottom of the polygon */
  58.    if (VertexList->Length == 0)
  59.       return(1);  /* reject null polygons */
  60.    MaxPoint_Y = MinPoint_Y = VertexPtr[MinIndexL = MaxIndex = 0].Y;
  61.    for (i = 1; i < VertexList->Length; i++) {
  62.       if (VertexPtr[i].Y < MinPoint_Y)
  63.          MinPoint_Y = VertexPtr[MinIndexL = i].Y; /* new top */
  64.       else if (VertexPtr[i].Y > MaxPoint_Y)
  65.          MaxPoint_Y = VertexPtr[MaxIndex = i].Y; /* new bottom */
  66.    }
  67.    if (MinPoint_Y == MaxPoint_Y)
  68.       return(1);  /* polygon is 0-height; avoid infinite loop below */
  69.  
  70.    /* Scan in ascending order to find the last top-edge point */
  71.    MinIndexR = MinIndexL;
  72.    while (VertexPtr[MinIndexR].Y == MinPoint_Y)
  73.       INDEX_FORWARD(MinIndexR);
  74.    INDEX_BACKWARD(MinIndexR); /* back up to last top-edge point */
  75.  
  76.    /* Now scan in descending order to find the first top-edge point */
  77.    while (VertexPtr[MinIndexL].Y == MinPoint_Y)
  78.       INDEX_BACKWARD(MinIndexL);
  79.    INDEX_FORWARD(MinIndexL); /* back up to first top-edge point */
  80.  
  81.    /* Figure out which direction through the vertex list from the top
  82.       vertex is the left edge and which is the right */
  83.    LeftEdgeDir = -1; /* assume left edge runs down thru vertex list */
  84.    if ((TopIsFlat = (VertexPtr[MinIndexL].X !=
  85.          VertexPtr[MinIndexR].X) ? 1 : 0) == 1) {
  86.       /* If the top is flat, just see which of the ends is leftmost */
  87.       if (VertexPtr[MinIndexL].X > VertexPtr[MinIndexR].X) {
  88.          LeftEdgeDir = 1;  /* left edge runs up through vertex list */
  89.          Temp = MinIndexL;       /* swap the indices so MinIndexL   */
  90.          MinIndexL = MinIndexR;  /* points to the start of the left */
  91.          MinIndexR = Temp;       /* edge, similarly for MinIndexR   */
  92.       }
  93.    } else {
  94.       /* Point to the downward end of the first line of each of the
  95.          two edges down from the top */
  96.       NextIndex = MinIndexR;
  97.       INDEX_FORWARD(NextIndex);
  98.       PreviousIndex = MinIndexL;
  99.       INDEX_BACKWARD(PreviousIndex);
  100.       /* Calculate X and Y lengths from the top vertex to the end of
  101.          the first line down each edge; use those to compare slopes
  102.          and see which line is leftmost */
  103.       DeltaXN = VertexPtr[NextIndex].X - VertexPtr[MinIndexL].X;
  104.       DeltaYN = VertexPtr[NextIndex].Y - VertexPtr[MinIndexL].Y;
  105.       DeltaXP = VertexPtr[PreviousIndex].X - VertexPtr[MinIndexL].X;
  106.       DeltaYP = VertexPtr[PreviousIndex].Y - VertexPtr[MinIndexL].Y;
  107.       if (((long)DeltaXN * DeltaYP - (long)DeltaYN * DeltaXP) < 0L) {
  108.          LeftEdgeDir = 1;  /* left edge runs up through vertex list */
  109.          Temp = MinIndexL;       /* swap the indices so MinIndexL   */
  110.          MinIndexL = MinIndexR;  /* points to the start of the left */
  111.          MinIndexR = Temp;       /* edge, similarly for MinIndexR   */
  112.       }
  113.    }
  114.  
  115.    /* Set the # of scan lines in the polygon, skipping the bottom edge
  116.       and also skipping the top vertex if the top isn't flat because
  117.       in that case the top vertex has a right edge component, and set
  118.       the top scan line to draw, which is likewise the second line of
  119.       the polygon unless the top is flat */
  120.    if ((WorkingHLineList.Length =
  121.          MaxPoint_Y - MinPoint_Y - 1 + TopIsFlat) <= 0)
  122.       return(1);  /* there's nothing to draw, so we're done */
  123.    WorkingHLineList.YStart = YOffset + MinPoint_Y + 1 - TopIsFlat;
  124.  
  125.    /* Get memory in which to store the line list we generate */
  126.    if ((WorkingHLineList.HLinePtr =
  127.          (struct HLine *) (malloc(sizeof(struct HLine) *
  128.          WorkingHLineList.Length))) == NULL)
  129.       return(0);  /* couldn't get memory for the line list */
  130.  
  131.    /* Scan the left edge and store the boundary points in the list */
  132.    /* Initial pointer for storing scan converted left-edge coords */
  133.    EdgePointPtr = WorkingHLineList.HLinePtr;
  134.    /* Start from the top of the left edge */
  135.    PreviousIndex = CurrentIndex = MinIndexL;
  136.    /* Skip the first point of the first line unless the top is flat;
  137.       if the top isn't flat, the top vertex is exactly on a right
  138.       edge and isn't drawn */
  139.    SkipFirst = TopIsFlat ? 0 : 1;
  140.    /* Scan convert each line in the left edge from top to bottom */
  141.    do {
  142.       INDEX_MOVE(CurrentIndex,LeftEdgeDir);
  143.       ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
  144.             VertexPtr[PreviousIndex].Y,
  145.             VertexPtr[CurrentIndex].X + XOffset,
  146.             VertexPtr[CurrentIndex].Y, 1, SkipFirst, &EdgePointPtr);
  147.       PreviousIndex = CurrentIndex;
  148.       SkipFirst = 0; /* scan convert the first point from now on */
  149.    } while (CurrentIndex != MaxIndex);
  150.  
  151.    /* Scan the right edge and store the boundary points in the list */
  152.    EdgePointPtr = WorkingHLineList.HLinePtr;
  153.    PreviousIndex = CurrentIndex = MinIndexR;
  154.    SkipFirst = TopIsFlat ? 0 : 1;
  155.    /* Scan convert the right edge, top to bottom. X coordinates are
  156.       adjusted 1 to the left, effectively causing scan conversion of
  157.       the nearest points to the left of but not exactly on the edge */
  158.    do {
  159.       INDEX_MOVE(CurrentIndex,-LeftEdgeDir);
  160.       ScanEdge(VertexPtr[PreviousIndex].X + XOffset - 1,
  161.             VertexPtr[PreviousIndex].Y,
  162.             VertexPtr[CurrentIndex].X + XOffset - 1,
  163.             VertexPtr[CurrentIndex].Y, 0, SkipFirst, &EdgePointPtr);
  164.       PreviousIndex = CurrentIndex;
  165.       SkipFirst = 0; /* scan convert the first point from now on */
  166.    } while (CurrentIndex != MaxIndex);
  167.  
  168.    /* Draw the line list representing the scan converted polygon */
  169.    (*DrawListFunc)(&WorkingHLineList, Color);
  170.  
  171.    /* Release the line list's memory and we're successfully done */
  172.    free(WorkingHLineList.HLinePtr);
  173.    return(1);
  174. }
  175.