edgecalc.c

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

/*=== Routine ends here, extracted code follows ======================

The following segment is the main edge-processor. It identifies the
coords xpix,ypix of each pixel intersected by the edge, and the type
of intersection (see Fig. 2 in the main text). All four edgetypes
are handled using the switches 'edgetype' and 'toggle'

Two Bresenham 'error' quantities are used to identify the pixels:

 ex: the x-distance from the left boundary of the pixel to the
 intercept of the edge with the upper boundary of the pixel.
 
 ey: the y-distance from the right boundary of the pixel to the
 intercept of the edge with the right boundary of the pixel.

Each pixel is found from the previous one by updating either ex or
ey and then testing its value to identify the type of intersection.

ex0, ey0 are initially the values of ex, ey at the starting pixel of
the edge, but subsequently hold the previous values as ex,ey are
updated.

=====================================================================*/

gamma:

/*=== If the edge lies entirely in one pixel, record this and finish. ===*/
if( (xpix==xpend) && (ypix==ypend) ) {
   resultproc(xpix,ypix, xstt-xpstt,ystt-ypstt, exend,eyend, NN, edgetype); 
   switch(edgetype) {
      case 3: case 2: goto edge_end_r;
      case 4: case 1: goto edge_end_l;
      }
   } 

/*=== If not, calculate the slope of the edge. ===*/
delx = xend-xstt; dely = yend-ystt;
if(toggle==1) { /* edgetype 1 or 3 */
   delymp =  dely;  largemp = LARGE;
   }
else { /* edgetype 2 or 4 */
   delymp = -dely;  largemp = -LARGE; 
   }

if(delx!=0)   dy_by_dx=delymp/delx; 
else {
   dx_by_dy = 0;  dy_by_dx = LARGE;
   }
if(dely!=0)   dx_by_dy=delx/dely;
else {
   dy_by_dx = 0; dx_by_dy = largemp;
   }

/*=== Look at first pixel. ===*/
ex0= xstt-xpstt;  ey0= ystt-ypstt; /* Set Bresenham error variables */
ex = ex0 + dx_by_dy*(hpix-ey0);

if(toggle==1) {    /* edgetype 1 or 3 */
   ey = ey0 + dy_by_dx*(hpix-ex0);
   if(ex < hpix) { /* Depending on the size of ex, the pixel is of type LX */
      resultproc(xpix, ypix, ex0, ey0, ex, hpix, LX, edgetype); goto alpha;
      }
   else {          /* or of type LY. */
      resultproc(xpix, ypix, ex0, ey0, hpix, ey, LY, edgetype); goto beta;
      }
   }
else {             /* edgetype 2 or 4 */
   ey = ey0 + dy_by_dx*ex0;
   if(ex > 0) {    /* Depending on the sign of ex, the pixel is of type RX */
      resultproc(xpix, ypix, ex0, ey0, ex, hpix, RX, edgetype); goto alpha;
      }
   else {          /* or of type RY. */
      resultproc(xpix, ypix, ex0, ey0,  0.0, ey, RY, edgetype); goto beta;
      }
   }

alpha: /*== The upper boundary just crossed; now at new y-level ==*/
ypix++;
ey -= hpix;

if(toggle==1) { /* edgetype 1 or 3 */
   /* If at last pixel of edge, finish off edge. */
   if( (ypix >= ypend) && (xpix >= xpend) ) {
      resultproc(xpend,ypend, ex, 0.0, exend, eyend, RX, edgetype);
      if(edgetype==1)   goto edge_end_l;
      else              goto edge_end_r;
      }
   }
else {          /* edgetype 2 or 4 */
   /* If at last pixel of edge, finish off edge. */
   if( (ypix >= ypend) && (xpix <= xpend) ) {
      resultproc(xpend, ypend, ex, 0.0, exend, eyend, LX, edgetype);
      if(edgetype==4)   goto edge_end_l;
      else              goto edge_end_r;
      }
   }

/*=== Not yet at end of edge. Update ex and carry on. ===*/
ex0 = ex;   ex += dx_by_dy;
if(toggle==1) {    /* edgetype 1 or 3 */
   if(ex < hpix) { /* Depending on the size of ex, pixel is of type MX */
      resultproc(xpix, ypix, ex0, 0.0, ex, hpix, MX, edgetype); goto alpha;
      }
   else {          /* or of type SY. */
      resultproc(xpix, ypix, ex0, 0.0, hpix, ey, SY, edgetype); goto beta;
      }
   }
else {             /* edgetype 2 or 4 */
   if(ex > 0) {    /* Depending on the sign of ex, pixel is of type MX */
      resultproc(xpix, ypix, ex0, 0.0, ex, hpix, MX, edgetype); goto alpha;
      }
   else {          /* or of type TY. */
      resultproc(xpix, ypix, ex0, 0.0, 0.0,  ey, TY, edgetype); goto beta;
      }
   }

beta:  /*== Just crossed a vertical pixel boundary; now at new x-level ==*/
if(toggle==1) {    /* edgetype 1 or 3 */
   xpix++;
   ex -= hpix;
   /* If at last pixel of edge, finish off edge. */
   if( (ypix>=ypend) && (xpix>=xpend) ) {
      resultproc(xpend, ypend,  0.0, ey, exend, eyend, RY, edgetype);
      if(edgetype==3)   goto edge_end_r;
      else              goto edge_end_l;
      }
   } 
else {             /* edgetype 2 or 4 */
   xpix--;
   ex += hpix;
   /* If at last pixel of edge, finish off edge. */
   if( (xpix <= xpend) && (ypix >= ypend) ) {
      resultproc(xpend, ypend, hpix, ey, exend, eyend, LY, edgetype);
      if(edgetype==4)   goto edge_end_l;
      else              goto edge_end_r;
      }
   }

/*=== Not yet at end of edge. Update ey, and carry on. ===*/
ey0 = ey;   ey += dy_by_dx;
if(toggle==1) {    /* edgetype 1 or 3 */
   if(ey < hpix) { /* Depending on size of ey, pixel is of type MY */
      resultproc(xpix, ypix,   0.0, ey0, hpix, ey, MY, edgetype); goto beta;
      }
   else {          /* or of type SX. */
      resultproc(xpix, ypix,   0.0, ey0, ex, hpix, SX, edgetype); goto alpha;
      }
    }
else {             /* edgetype 2 or 4 */
   if(ey < hpix) { /* Depending on size of ey, pixel is of type MY */
      resultproc(xpix, ypix,  hpix, ey0,  0.0, ey, MY, edgetype); goto beta;
      }
   else {          /* or of type TX. */
      resultproc(xpix, ypix,  hpix, ey0, ex, hpix, TX, edgetype); goto alpha;
      }
   }
}

/*===========================================================================
This illustrates how the output from the edge calculator can be used
The routine modifies externally defined arrays fragptr[], xl[] and xr[] (which
are accessed via global pointers).
It uses a global pointer to recognize precalculated bitmasks held in a
structure.
===========================================================================*/

void resultproc(xpix,ypix,x1,y1,x2,y2,pixtype,edgetype)
int xpix,ypix;           /* position of pixel to which information applies */
float x1,y1,x2,y2;       /* position of the two endpoints of edge intersecting
                            the polygon */
int pixtype;             /* type of overlap in this pixel (NN,LX,LY,...) */
int edgetype;            /* type of edge (1,2,3 or 4)         */

{
extern aabufftype * aabuffptr;     /* pointer to a structure in which the
            precomputed bitmasks are held. Their format is given in the text.*/
extern unsigned short * fragptr; /* pointer to linear array holding bitmasks
            of the overlaps of the polygon with pixels, assuming HRES
            pixels per scanline. On entry each entry should be set to 0xffff */
extern int * xl, * xr;          /* pointers to arrays storing positions of the
          left and right edges of the polygon: xl[y] and xr[y] give the
          x-position of the leftmost and rightmost pixels of the polygon on
          scanline y */
static float scale = 3.999; /* this should be set to just less than the ratio
            of pixel to subpixel widths. The value 3.999 is for the case where
            each pixel is 4x4 subpixels */
int ij,ix1,ix2,iy1,iy2;

ij  = xpix + HRES*ypix;
ix1 = x1*scale;  iy1 = y1*scale;
ix2 = x2*scale;  iy2 = y2*scale;

/*-- adjust current bitmask by bitwise ANDing it with computed bitmask --*/
if(edgetype>0)
   fragptr[ij] &= aabuffptr->mask[edgetype] [ix1] [iy1] [ix2] [iy2];

/*-- record the leftmost and rightmost pixel positions, xl[y] and xr[y]
     of the polygon on each scanline y --*/
if      (rl[pixtype][edgetype]== 1)  xr[ypix]=xpix;
else if (rl[pixtype][edgetype]==-1)  xl[ypix]=xpix;

return ;
}