edgecalc.c

[Game.Programming].Academic - Graphics Gems (6 books source code)

/******************************************************************************
EDGE AND BIT-MASK CALCULATIONS FOR ANTI-ALIASING
Russell C.H. Cheng, University of Wales, Cardiff, 21 Jan 1992.

This routine calculates the geometry of the overlap of the edges of a polygon
with square pixels, using a fast alternating Bresenham error-update technique.

Entry:
 Pointer to a structure (defined below) giving details of the polygon.
 Pointers to precalculated bitmasks.

Exit:
 The routine outputs the overlap information pixel by pixel via resultproc().
 The arguments are: the pixel position, position of the endpoints of the
 overlapping edge, the pixeltype, and the edgetype.

 In this implementation resultproc() uses this information to calculate the
 positions of the leftmost and rightmost pixels on each scanline, and the
 bitmasks of overlap of the polygon with each pixel.
 
Implementation Details:
 (i)  The procedure resultproc() accesses external pointers: int * xl,
      int * xr,  aabufftype * aabuffptr, short int * fragptr. These are
      described in resultproc(). These should be globally defined.
 (ii) edge_calculate() accesses polygonal information via a pointer
      to the structure:
         typedef struct SCRNPOLYGON
            {
            int numvert;         number of vertices 
            float xcoord[10];    coordinates of each vertex 
            float ycoord[10];    in clockwise order 
            int imax;            subscript of vertex with largest y-coord 
            int imin;            subscript of vertex with smallest y-coord
            } SCRNPOLYGON;
******************************************************************************/

#define LARGE 10000000.0
#define TRUE 1
#define FALSE 0

/*==  The following two structures are included here to enable compilation,
      they should normally be defined earlier for access by the main routine ==*/

typedef struct  {
        unsigned short mask[4][5][5][5][5];
        } aabufftype;

typedef struct  {
        int numvert;      /* number of vertices */
        float xcoord[10]; /* coordinates of each vertex */
        float ycoord[10]; /* in clockwise order */
        int imax;         /* subscript of vertex with largest y-coord */
        int imin;         /* subscript of vertex with smallest y-coord */ 
        } SCRNPOLYGON;


#define NN 0 /* The different types of overlap possible in a pixel. */
#define LX 1 /* See Fig.2 in the main text. */
#define LY 2
#define RX 3
#define RY 4
#define MX 5
#define MY 6
#define SX 7
#define SY 8
#define TX 9
#define TY 10

#define HRES 768 /* horizontal resolution */

int rl[11][5] = {  /* Array used to select pixeltype/edgetype combinations */
 0,  0, 0, 1, -1,  /* at which an xl or xr value should be set.     */
-1,  0, 1, 1, -1,  /*  1 indicates where xr is set  */
 0,  0, 0, 0, -1,  /* -1 indicates where xl is set  */
 1, -1, 0, 1, -1,
 0,  0, 0, 1,  0,
 0, -1, 1, 1, -1,
 0,  0, 0, 0,  0,
 0,  0, 0, 1,  0,
 0, -1, 0, 0,  0,
 0,  0, 0, 0, -1,
 0,  0, 1, 0,  0,
};


void edge_calculator(scrnfaceptr)
SCRNPOLYGON * scrnfaceptr;

{
void resultproc();

float delx,dely,delymp,dx_by_dy,dy_by_dx;
int edgetype;
float ex;                 /* Bresenham x-error variables */
float exend, exstt, ex0;  /*   ''                        */
float ey;                 /* Bresenham y-error variables */
float eyend, eystt, ey0;  /*   ''                        */
int firstleftedgetype;    /* edgetype of first left edge encountered*/
int firstrightedge;       /* flag showing when 1st right-edge is reached */
float hpix = 1.0;         /* Pixel edgelength */
int iv, ivm1, ivp1;       /* work variables holding array subscripts */
float largemp;            /* work variable used in slope calculation */
int lastleftedgetype;     /* edgetype of the last left-edge */
int toggle;               /* switch-flag, 1=odd, 2=even edgetypes */
float xstt,xend;          /* x-positions of start and end points of edge */
int xpix, xpend, xpstt;   /* current, edge-start & edge-end pixel x-coords */ 
float ystt,yend;          /* y-positions of start and end points of edge */
int ypix, ypend, ypstt;   /* current, edge-start & edge-end pixel y-coords */ 

/*====     Process each edge of the left-hand side of polygon      ====*/
iv = scrnfaceptr->imin;               /* Find subscripts of first      */
ivp1 = (iv+1) % scrnfaceptr->numvert; /* left edge and the             */
xend=scrnfaceptr->xcoord[iv];  yend=scrnfaceptr->ycoord[iv]; /* coords */
xpend = (int)xend; ypend = (int)yend;    /* of its starting point.     */
firstleftedgetype = 0;

while(iv!=scrnfaceptr->imax) {
   xpix  = xpend; ypix = ypend;               /* Get the coords of the    */
   xstt= xend; ystt= yend;                    /* starting pixel of edge   */
   xpstt = xpend; ypstt = ypend;              /* and the coords of the    */
   xpend=(int)(xend= scrnfaceptr->xcoord[ivp1]);              /* end      */
   ypend=(int)(yend= scrnfaceptr->ycoord[ivp1]);              /* pixel.   */
   exend= xend-xpend; eyend= yend-ypend; /* Bresenham errors at end pixel.*/

   if(xstt<xend) {                 /*--   Left: Edgetype 1    --*/
      if(firstleftedgetype==0) {   /* If at first edge,         */
         firstleftedgetype = 1;    /* make a note of its type.  */
         resultproc(xpix,ypix, 0.0,0.0,0.0,0.0, LX,0);
               /* Special call equivalent to xl[ypix] = xpix    */
         }
      edgetype=1; toggle = 1;      /* Set edgetype and          */
      goto gamma;                  /* go to main edge-processor.*/
      }
   else {                          /*--   Left: Edgetype 4    --*/
      if(firstleftedgetype==0)     /* If at first edge, make    */
         firstleftedgetype = 4;    /* a note of its type.       */
      edgetype=4; toggle = 2;      /* Set edgetype and          */
      goto gamma;                  /* go to main edge-processor.*/
      }

edge_end_l:   /* The main edge-processor returns here when the edge is done*/
   iv = ivp1;          /* Set subscripts for the next left edge. */
   ivp1= (iv+1) % scrnfaceptr->numvert;  /* '' */
   }

/*===  Make a note of the edgetype of the last edge on the left. ====*/
lastleftedgetype = edgetype; 
          
/*==== Process each edge of the right-hand side of polygon. ====*/
iv = scrnfaceptr->imin;                       /* Find subscripts of first  */
ivm1= (iv+scrnfaceptr->numvert-1) % scrnfaceptr->numvert; /* right edge &  */
xend=scrnfaceptr->xcoord[iv];  yend=scrnfaceptr->ycoord[iv]; /* the coords */
xpend = (int)xend; ypend = (int)yend;             /* of its starting point.*/

firstrightedge = TRUE;

while(iv!=scrnfaceptr->imax) {
   xpix  = xpend; ypix  = ypend;                /* get coords of the       */
   xstt  = xend;    ystt  = yend;               /* starting pixel of edge  */
   xpstt = xpend; ypstt = ypend;                /*        and              */
   xpend=(int)(xend= scrnfaceptr->xcoord[ivm1]);   /* the coords of        */
   ypend=(int)(yend= scrnfaceptr->ycoord[ivm1]);   /* the end pixel.       */
   exend= xend-xpend; eyend= yend-ypend; /* Bresenham errors at end pixel. */

   if(xstt<xend) { /*--- Right: Edgetype 3 ---*/
      /*-- Correct for bottom-most pixel bitmask, if necessary. --*/
      if(firstrightedge == TRUE) {
         firstrightedge = FALSE;
         if(firstleftedgetype==1) {
            exstt=(xstt-xpstt);   eystt=(ystt-ypstt);
            resultproc( xpix,ypix, exstt, eystt, exstt, eystt, MY, 4); 
            }
          }
      edgetype=3; toggle = 1;  /* Set the current edgetype and   */
      goto gamma;              /* go to the main edge-processor. */
      }
   else {     /*--- Right: Edgetype 2 ---*/
      /*-- Correct for bottom-most pixel bitmask, if necessary.  --*/
      if(firstrightedge==TRUE) {
         firstrightedge = FALSE;
         if(firstleftedgetype==4) {
            exstt=(xstt-xpstt);   eystt=(ystt-ypstt);
            resultproc(xpix,ypix, exstt, eystt, exstt, eystt, MY, 3);
            }
            resultproc(xpix,ypix, 0.0,0.0,0.0,0.0, RX,0);
                      /* Special call equivalent to xr[ypix] = xpix. */
         }
      edgetype=2;  toggle = 2;  /* Set the current edgetype. */
      goto gamma;               /* Go to main edge-processor.*/
      }

edge_end_r:   /* The main edge-processor returns here once edge is done */
   iv =  ivm1;         /* set subscripts for next right-edge */
   ivm1= (iv+scrnfaceptr->numvert-1) % scrnfaceptr->numvert;
   }

/*=== do the final vertex bitmask correction, if necessary ===*/
if(lastleftedgetype==4 && edgetype==2)
   resultproc(xpend,ypend, exend, eyend, exend, eyend, MY, 1);
else if(lastleftedgetype==1 && edgetype==3)
   resultproc(xpend,ypend, exend, eyend, exend, eyend, MY, 2);
  
return;