home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / source / chapter41 / l41-2.c < prev    next >
C/C++ Source or Header  |  1997-06-18  |  5KB  |  119 lines
  1. /* Color-fills a convex polygon. All vertices are offset by (XOffset, YOffset).
  2. "Convex" means "monotone with respect to a vertical line"; that is, every 
  3. horizontal line drawn through the polygon at any point would cross exactly two 
  4. active edges (neither horizontal lines nor zero-length edges count as active 
  5. edges; both are acceptable anywhere in the polygon). Right & left edges may 
  6. cross (polygons may be nonsimple). Polygons that are not convex according to 
  7. this definition won't be drawn properly. (Yes, "convex" is a lousy name for 
  8. this type of polygon, but it's convenient; use "monotone-vertical" if it makes 
  9. you happier!)
  10. *******************************************************************
  11. NOTE: the low-level drawing routine, DrawHorizontalLineList, must be able to 
  12. reverse the edges, if necessary to make the correct edge left edge. It must 
  13. also expect right edge to be specified in +1 format (the X coordinate is 1 past
  14. highest coordinate to draw). In both respects, this differs from low-level 
  15. drawing routines presented in earlier columns; changes are necessary to make it
  16. possible to draw nonsimple monotone-vertical polygons; that in turn makes it 
  17. possible to use Jim Kent's test for monotone-vertical polygons.
  18. *******************************************************************
  19. Returns 1 for success, 0 if memory allocation failed.
  20.   Tested with Borland C++ 4.02 in small model by Jim Mischel 12/16/94.
  21.   See build instructions in L21-1.C.
  22. */
  23.  
  24. #include <stdio.h>
  25. #include <math.h>
  26. #include <stdlib.h>
  27. #include "polygon.h"
  28.  
  29. /* Advances the index by one vertex forward through the vertex list,
  30. wrapping at the end of the list */
  31. #define INDEX_FORWARD(Index) \
  32.    Index = (Index + 1) % VertexList->Length;
  33.  
  34. /* Advances the index by one vertex backward through the vertex list,
  35. wrapping at the start of the list */
  36. #define INDEX_BACKWARD(Index) \
  37.    Index = (Index - 1 + VertexList->Length) % VertexList->Length;
  38.  
  39. /* Advances the index by one vertex either forward or backward through
  40. the vertex list, wrapping at either end of the list */
  41. #define INDEX_MOVE(Index,Direction)                                  \
  42.    if (Direction > 0)                                                \
  43.       Index = (Index + 1) % VertexList->Length;                      \
  44.    else                                                              \
  45.       Index = (Index - 1 + VertexList->Length) % VertexList->Length;
  46.  
  47. extern void ScanEdge(int, int, int, int, int, int, struct HLine **);
  48. extern void DrawHorizontalLineList(struct HLineList *, int);
  49.  
  50. int FillMonotoneVerticalPolygon(struct PointListHeader * VertexList,
  51.       int Color, int XOffset, int YOffset)
  52. {
  53.    int i, MinIndex, MaxIndex, MinPoint_Y, MaxPoint_Y;
  54.    int NextIndex, CurrentIndex, PreviousIndex;
  55.    struct HLineList WorkingHLineList;
  56.    struct HLine *EdgePointPtr;
  57.    struct Point *VertexPtr;
  58.  
  59.    /* Point to the vertex list */
  60.    VertexPtr = VertexList->PointPtr;
  61.  
  62.    /* Scan the list to find the top and bottom of the polygon */
  63.    if (VertexList->Length == 0)
  64.       return(1);  /* reject null polygons */
  65.    MaxPoint_Y = MinPoint_Y = VertexPtr[MinIndex = MaxIndex = 0].Y;
  66.    for (i = 1; i < VertexList->Length; i++) {
  67.       if (VertexPtr[i].Y < MinPoint_Y)
  68.          MinPoint_Y = VertexPtr[MinIndex = i].Y; /* new top */
  69.       else if (VertexPtr[i].Y > MaxPoint_Y)
  70.          MaxPoint_Y = VertexPtr[MaxIndex = i].Y; /* new bottom */
  71.    }
  72.  
  73.    /* Set the # of scan lines in the polygon, skipping the bottom edge */
  74.    if ((WorkingHLineList.Length = MaxPoint_Y - MinPoint_Y) <= 0)
  75.       return(1);  /* there's nothing to draw, so we're done */
  76.    WorkingHLineList.YStart = YOffset + MinPoint_Y;
  77.  
  78.    /* Get memory in which to store the line list we generate */
  79.    if ((WorkingHLineList.HLinePtr =
  80.          (struct HLine *) (malloc(sizeof(struct HLine) *
  81.          WorkingHLineList.Length))) == NULL)
  82.       return(0);  /* couldn't get memory for the line list */
  83.  
  84.    /* Scan the first edge and store the boundary points in the list */
  85.    /* Initial pointer for storing scan converted first-edge coords */
  86.    EdgePointPtr = WorkingHLineList.HLinePtr;
  87.    /* Start from the top of the first edge */
  88.    PreviousIndex = CurrentIndex = MinIndex;
  89.    /* Scan convert each line in the first edge from top to bottom */
  90.    do {
  91.       INDEX_BACKWARD(CurrentIndex);
  92.       ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
  93.             VertexPtr[PreviousIndex].Y,
  94.             VertexPtr[CurrentIndex].X + XOffset,
  95.             VertexPtr[CurrentIndex].Y, 1, 0, &EdgePointPtr);
  96.       PreviousIndex = CurrentIndex;
  97.    } while (CurrentIndex != MaxIndex);
  98.  
  99.    /* Scan the second edge and store the boundary points in the list */
  100.    EdgePointPtr = WorkingHLineList.HLinePtr;
  101.    PreviousIndex = CurrentIndex = MinIndex;
  102.    /* Scan convert the second edge, top to bottom */
  103.    do {
  104.       INDEX_FORWARD(CurrentIndex);
  105.       ScanEdge(VertexPtr[PreviousIndex].X + XOffset,
  106.             VertexPtr[PreviousIndex].Y,
  107.             VertexPtr[CurrentIndex].X + XOffset,
  108.             VertexPtr[CurrentIndex].Y, 0, 0, &EdgePointPtr);
  109.       PreviousIndex = CurrentIndex;
  110.    } while (CurrentIndex != MaxIndex);
  111.  
  112.    /* Draw the line list representing the scan converted polygon */
  113.    DrawHorizontalLineList(&WorkingHLineList, Color);
  114.  
  115.    /* Release the line list's memory and we're successfully done */
  116.    free(WorkingHLineList.HLinePtr);
  117.    return(1);
  118. }
  119.