home *** CD-ROM | disk | FTP | other *** search
/ Graphics Programming Black Book (Special Edition) / BlackBook.bin / disk1 / xsharp22 / drawtexp.c < prev    next >
Text File  |  1997-06-18  |  10KB  |  242 lines
  1. /* Draws a bitmap, mapped to a convex polygon (draws a texture-mapped
  2.    polygon). "Convex" means that every vertical line drawn through
  3.    the polygon at any point would cross exactly two active edges
  4.    (neither vertical edges nor zero-length edges count as active
  5.    edges; both are acceptable anywhere in the polygon), and that the
  6.    top & bottom edges never cross. Nonconvex polygons won't be drawn
  7.    properly. Note that scanning is done in columns, to avoid
  8.    per-pixel plane mapping. Can't fail. */
  9.  
  10. #include <stdio.h>
  11. #include <math.h>
  12. #include "polygon.h"
  13.  
  14. /* Describes the current location and stepping, in both the source and
  15.    the destination, of an edge. Mirrors structure in DRAWTEXP.C. */
  16. typedef struct {
  17.    int Direction;    /* through edge list; 1 for a right edge (forward
  18.                         through vertex list), -1 for a left edge (backward
  19.                         through vertex list) */
  20.    int RemainingScans;  /* height left to scan out in dest */
  21.    int CurrentEnd;      /* vertex # of end of current edge */
  22.    Fixedpoint SourceX;     /* current X location in source for this edge */
  23.    Fixedpoint SourceY;     /* current Y location in source for this edge */
  24.    Fixedpoint SourceStepX; /* X step in source for X step in dest of 1 */
  25.    Fixedpoint SourceStepY; /* Y step in source for X step in dest of 1 */
  26.                         /* variables used for all-integer Bresenham's-type
  27.                            Y stepping through the dest, needed for precise
  28.                            pixel placement to avoid gaps */
  29.    int DestY;           /* current Y location in dest for this edge */
  30.    int DestYIntStep;    /* whole part of dest Y step per column X step */
  31.    int DestYDirection;  /* -1 or 1 to indicate which way Y steps
  32.                            (left/right) */
  33.    int DestYErrTerm;    /* current error term for dest Y stepping */
  34.    int DestYAdjUp;      /* amount to add to error term per column move */
  35.    int DestYAdjDown;    /* amount to subtract from error term when the
  36.                            error term turns over */
  37. } EdgeScan;
  38.  
  39. int StepEdge(EdgeScan *);
  40. int SetUpEdge(EdgeScan *, int);
  41. void ScanOutLine(EdgeScan *, EdgeScan *);
  42. int GetImagePixel(char *, int, int, int);
  43.  
  44. /* Statics to save time that would otherwise be spent passing them to
  45.    subroutines. */
  46. int DestX;
  47. static int MaxVert, NumVerts;
  48. static Point * VertexPtr;
  49. static Point * TexVertsPtr;
  50. char * TexMapBits;
  51. int TexMapWidth;
  52.  
  53. /* Draws a texture-mapped polygon, given a list of destination polygon
  54.    vertices, a list of corresponding source texture polygon vertices, and a
  55.    pointer to the source texture's descriptor. */
  56. void DrawTexturedPolygon(PointListHeader * Polygon, Point * TexVerts,
  57.    TextureMap * TexMap)
  58. {
  59.    int MinX, MaxX, MinVert, i;
  60.    EdgeScan TopEdge, BottomEdge;
  61.  
  62.    NumVerts = Polygon->Length;
  63.    VertexPtr = Polygon->PointPtr;
  64.    TexVertsPtr = TexVerts;
  65.    TexMapBits = TexMap->TexMapBits;
  66.    TexMapWidth = TexMap->TexMapWidth;
  67.  
  68.    /* Nothing to draw if less than 3 vertices */
  69.    if (NumVerts < 3) {
  70.       return;
  71.    }
  72.  
  73.    /* Scan through the destination polygon vertices and find the left of
  74.       the top and bottom edges, taking advantage of our knowledge that
  75.       vertices run in a clockwise direction (else this polygon wouldn't
  76.       be visible due to backface removal) */
  77.    MinX = 32767;
  78.    MaxX = -32768;
  79.    for (i=0; i<NumVerts; i++) {
  80.       if (VertexPtr[i].X < MinX) {
  81.          MinX = VertexPtr[i].X;
  82.          MinVert = i;
  83.       }
  84.       if (VertexPtr[i].X > MaxX) {
  85.          MaxX = VertexPtr[i].X;
  86.          MaxVert = i;
  87.       }
  88.    }
  89.  
  90.    /* Reject flat (0-pixel-high) polygons */
  91.    if (MinX >= MaxX) {
  92.       return;
  93.    }
  94.  
  95.    /* The destination X coordinate is not edge specific; it applies to
  96.       both edges, since we always step X by 1 */
  97.    DestX = MinX;
  98.  
  99.    /* Set up to scan the initial top and bottom edges of the source and
  100.       destination polygons. We always step the destination polygon edges
  101.       by one in X, so calculate the corresponding destination Y step for
  102.       each edge, and then the corresponding source image Y and X steps */
  103.    TopEdge.Direction = 1;     /* set up top edge first */
  104.    SetUpEdge(&TopEdge, MinVert);
  105.    BottomEdge.Direction = -1; /* set up bottom edge */
  106.    SetUpEdge(&BottomEdge, MinVert);
  107.  
  108.    /* Step across destination edges one column at a time. At each
  109.       column, find the corresponding edge points in the source image. Scan
  110.       between the edge points in the source, drawing the corresponding
  111.       pixels down the current column in the destination polygon. (We
  112.       know which way the top and bottom edges run through the vertex list
  113.       because visible (non-backface-culled) polygons always have the vertices
  114.       in clockwise order as seen from the viewpoint) */
  115.    for (;;) {
  116.       /* Done if off right of clip rectangle */
  117.       if (DestX >= ClipMaxX) {
  118.          return;
  119.       }
  120.  
  121.       /* Draw only if inside X bounds of clip rectangle */
  122.       if (DestX >= ClipMinX) {
  123.          /* Draw the column between the two current edges */
  124.          ScanOutLine(&TopEdge, &BottomEdge);
  125.       }
  126.  
  127.       /* Advance the source and destination polygon edges, ending if we've
  128.          scanned all the way to the right of the polygon */
  129.       if (!StepEdge(&TopEdge)) {
  130.          break;
  131.       }
  132.       if (!StepEdge(&BottomEdge)) {
  133.          break;
  134.       }
  135.       DestX++;
  136.    }
  137. }
  138.  
  139. /* Steps an edge one column in the destination, and the corresponding
  140.    distance in the source. If an edge runs out, starts a new edge if there
  141.    is one. Returns 1 for success, or 0 if there are no more edges to scan. */
  142. int StepEdge(EdgeScan * Edge)
  143. {
  144.    /* Count off the column we stepped last time; if this edge is
  145.       finished, try to start another one */
  146.    if (--Edge->RemainingScans == 0) {
  147.       /* Set up the next edge; done if there is no next edge */
  148.       if (SetUpEdge(Edge, Edge->CurrentEnd) == 0) {
  149.          return(0);  /* no more edges; done drawing polygon */
  150.       }
  151.       return(1);     /* all set to draw the new edge */
  152.    }
  153.  
  154.    /* Step the current source edge */
  155.    Edge->SourceY += Edge->SourceStepY;
  156.    Edge->SourceX += Edge->SourceStepX;
  157.  
  158.    /* Step dest Y with Bresenham-style variables, to get precise dest pixel
  159.       placement and avoid gaps */
  160.    Edge->DestY += Edge->DestYIntStep;  /* whole pixel step */
  161.    /* Do error term stuff for fractional pixel Y step handling */
  162.    if ((Edge->DestYErrTerm += Edge->DestYAdjUp) > 0) {
  163.       Edge->DestY += Edge->DestYDirection;
  164.       Edge->DestYErrTerm -= Edge->DestYAdjDown;
  165.    }
  166.  
  167.    return(1);
  168. }
  169.  
  170. /* Sets up an edge to be scanned; the edge starts at StartVert and proceeds
  171.    in direction Edge->Direction through the vertex list. Edge->Direction must
  172.    be set prior to call; -1 to scan a bottom edge (backward through the vertex
  173.    list), 1 to scan a top edge (forward through the vertex list).
  174.    Automatically skips over 0-height edges. Returns 1 for success, or 0 if
  175.    there are no more edges to scan. This is a little tricky because we do
  176.    column-oriented scanning to avoid plane stuff, but still want to have the
  177.    same fill conventions as normal polygons (top and left inclusive, bottom
  178.    and right exclusive). We do this by biasing the edges appropriately:
  179.  
  180.    edges with non-negative slopes: ceiling(y+1)
  181.    edges with negative slopes: ceiling(y)
  182.  
  183.    where bottom edge coordinates are non-inclusive for filling, and top
  184.    edge coordinates are inclusive.
  185.  */
  186. int SetUpEdge(EdgeScan * Edge, int StartVert)
  187. {
  188.    int NextVert, DestYHeight;
  189.    Fixedpoint DestXWidth;
  190.  
  191.    for (;;) {
  192.       /* Done if this edge starts at the rightmost vertex */
  193.       if (StartVert == MaxVert) {
  194.          return(0);
  195.       }
  196.  
  197.       /* Advance to the next vertex, wrapping if we run off the start or end
  198.          of the vertex list */
  199.       NextVert = StartVert + Edge->Direction;
  200.       if (NextVert >= NumVerts) {
  201.          NextVert = 0;
  202.       } else if (NextVert < 0) {
  203.          NextVert = NumVerts - 1;
  204.       }
  205.  
  206.       /* Calculate the variables for this edge and done if this is not a
  207.          zero-height edge */
  208.       if ((Edge->RemainingScans =
  209.             VertexPtr[NextVert].X - VertexPtr[StartVert].X) != 0) {
  210.          DestXWidth = INT_TO_FIXED(Edge->RemainingScans);
  211.          Edge->CurrentEnd = NextVert;
  212.          Edge->SourceY = INT_TO_FIXED(TexVertsPtr[StartVert].Y);
  213.          Edge->SourceX = INT_TO_FIXED(TexVertsPtr[StartVert].X);
  214.          Edge->SourceStepY = FixedDiv(INT_TO_FIXED(TexVertsPtr[NextVert].Y) -
  215.                Edge->SourceY, DestXWidth);
  216.          Edge->SourceStepX = FixedDiv(INT_TO_FIXED(TexVertsPtr[NextVert].X) -
  217.                Edge->SourceX, DestXWidth);
  218.  
  219.          /* Set up Bresenham-style variables for dest Y stepping */
  220.          if ((DestYHeight =
  221.                (VertexPtr[NextVert].Y - VertexPtr[StartVert].Y)) <= 0) {
  222.             /* Set up for drawing bottom to top */
  223.             Edge->DestYDirection = -1;
  224.             DestYHeight = -DestYHeight;
  225.             Edge->DestYIntStep = -(DestYHeight / Edge->RemainingScans);
  226.             Edge->DestY = VertexPtr[StartVert].Y;
  227.          } else {
  228.             /* Set up for drawing top to bottom */
  229.             Edge->DestYDirection = 1;
  230.             Edge->DestYIntStep = DestYHeight / Edge->RemainingScans;
  231.             Edge->DestY = VertexPtr[StartVert].Y + 1;
  232.          }
  233.          Edge->DestYErrTerm = 1 - Edge->RemainingScans;
  234.          Edge->DestYAdjUp = DestYHeight % Edge->RemainingScans;
  235.          Edge->DestYAdjDown = Edge->RemainingScans;
  236.          return(1);  /* success */
  237.       }
  238.       StartVert = NextVert;   /* keep looking for a non-0-height edge */
  239.    }
  240. }
  241.  
  242.