home *** CD-ROM | disk | FTP | other *** search
/ AP Professional Graphics CD-ROM Library / AP Professional Graphics CD-ROM Library.iso / pc / unix / appendix / gemsiii / edgecalc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-03-17  |  16.0 KB  |  408 lines
  1. /******************************************************************************
  2. EDGE AND BIT-MASK CALCULATIONS FOR ANTI-ALIASING
  3. Russell C.H. Cheng, University of Wales, Cardiff, 21 Jan 1992.
  4.  
  5. This routine calculates the geometry of the overlap of the edges of a polygon
  6. with square pixels, using a fast alternating Bresenham error-update technique.
  7.  
  8. Entry:
  9.  Pointer to a structure (defined below) giving details of the polygon.
  10.  Pointers to precalculated bitmasks.
  11.  
  12. Exit:
  13.  The routine outputs the overlap information pixel by pixel via resultproc().
  14.  The arguments are: the pixel position, position of the endpoints of the
  15.  overlapping edge, the pixeltype, and the edgetype.
  16.  
  17.  In this implementation resultproc() uses this information to calculate the
  18.  positions of the leftmost and rightmost pixels on each scanline, and the
  19.  bitmasks of overlap of the polygon with each pixel.
  20.  
  21. Implementation Details:
  22.  (i)  The procedure resultproc() accesses external pointers: int * xl,
  23.       int * xr,  aabufftype * aabuffptr, short int * fragptr. These are
  24.       described in resultproc(). These should be globally defined.
  25.  (ii) edge_calculate() accesses polygonal information via a pointer
  26.       to the structure:
  27.          typedef struct SCRNPOLYGON
  28.             {
  29.             int numvert;         number of vertices 
  30.             float xcoord[10];    coordinates of each vertex 
  31.             float ycoord[10];    in clockwise order 
  32.             int imax;            subscript of vertex with largest y-coord 
  33.             int imin;            subscript of vertex with smallest y-coord
  34.             } SCRNPOLYGON;
  35. ******************************************************************************/
  36.  
  37. #define LARGE 10000000.0
  38. #define TRUE 1
  39. #define FALSE 0
  40.  
  41. /*==  The following two structures are included here to enable compilation,
  42.       they should normally be defined earlier for access by the main routine ==*/
  43.  
  44. typedef struct  {
  45.         unsigned short mask[4][5][5][5][5];
  46.         } aabufftype;
  47.  
  48. typedef struct  {
  49.         int numvert;      /* number of vertices */
  50.         float xcoord[10]; /* coordinates of each vertex */
  51.         float ycoord[10]; /* in clockwise order */
  52.         int imax;         /* subscript of vertex with largest y-coord */
  53.         int imin;         /* subscript of vertex with smallest y-coord */ 
  54.         } SCRNPOLYGON;
  55.  
  56.  
  57. #define NN 0 /* The different types of overlap possible in a pixel. */
  58. #define LX 1 /* See Fig.2 in the main text. */
  59. #define LY 2
  60. #define RX 3
  61. #define RY 4
  62. #define MX 5
  63. #define MY 6
  64. #define SX 7
  65. #define SY 8
  66. #define TX 9
  67. #define TY 10
  68.  
  69. #define HRES 768 /* horizontal resolution */
  70.  
  71. int rl[11][5] = {  /* Array used to select pixeltype/edgetype combinations */
  72.  0,  0, 0, 1, -1,  /* at which an xl or xr value should be set.     */
  73. -1,  0, 1, 1, -1,  /*  1 indicates where xr is set  */
  74.  0,  0, 0, 0, -1,  /* -1 indicates where xl is set  */
  75.  1, -1, 0, 1, -1,
  76.  0,  0, 0, 1,  0,
  77.  0, -1, 1, 1, -1,
  78.  0,  0, 0, 0,  0,
  79.  0,  0, 0, 1,  0,
  80.  0, -1, 0, 0,  0,
  81.  0,  0, 0, 0, -1,
  82.  0,  0, 1, 0,  0,
  83. };
  84.  
  85.  
  86. void edge_calculator(scrnfaceptr)
  87. SCRNPOLYGON * scrnfaceptr;
  88.  
  89. {
  90. void resultproc();
  91.  
  92. float delx,dely,delymp,dx_by_dy,dy_by_dx;
  93. int edgetype;
  94. float ex;                 /* Bresenham x-error variables */
  95. float exend, exstt, ex0;  /*   ''                        */
  96. float ey;                 /* Bresenham y-error variables */
  97. float eyend, eystt, ey0;  /*   ''                        */
  98. int firstleftedgetype;    /* edgetype of first left edge encountered*/
  99. int firstrightedge;       /* flag showing when 1st right-edge is reached */
  100. float hpix = 1.0;         /* Pixel edgelength */
  101. int iv, ivm1, ivp1;       /* work variables holding array subscripts */
  102. float largemp;            /* work variable used in slope calculation */
  103. int lastleftedgetype;     /* edgetype of the last left-edge */
  104. int toggle;               /* switch-flag, 1=odd, 2=even edgetypes */
  105. float xstt,xend;          /* x-positions of start and end points of edge */
  106. int xpix, xpend, xpstt;   /* current, edge-start & edge-end pixel x-coords */ 
  107. float ystt,yend;          /* y-positions of start and end points of edge */
  108. int ypix, ypend, ypstt;   /* current, edge-start & edge-end pixel y-coords */ 
  109.  
  110. /*====     Process each edge of the left-hand side of polygon      ====*/
  111. iv = scrnfaceptr->imin;               /* Find subscripts of first      */
  112. ivp1 = (iv+1) % scrnfaceptr->numvert; /* left edge and the             */
  113. xend=scrnfaceptr->xcoord[iv];  yend=scrnfaceptr->ycoord[iv]; /* coords */
  114. xpend = (int)xend; ypend = (int)yend;    /* of its starting point.     */
  115. firstleftedgetype = 0;
  116.  
  117. while(iv!=scrnfaceptr->imax) {
  118.    xpix  = xpend; ypix = ypend;               /* Get the coords of the    */
  119.    xstt= xend; ystt= yend;                    /* starting pixel of edge   */
  120.    xpstt = xpend; ypstt = ypend;              /* and the coords of the    */
  121.    xpend=(int)(xend= scrnfaceptr->xcoord[ivp1]);              /* end      */
  122.    ypend=(int)(yend= scrnfaceptr->ycoord[ivp1]);              /* pixel.   */
  123.    exend= xend-xpend; eyend= yend-ypend; /* Bresenham errors at end pixel.*/
  124.  
  125.    if(xstt<xend) {                 /*--   Left: Edgetype 1    --*/
  126.       if(firstleftedgetype==0) {   /* If at first edge,         */
  127.          firstleftedgetype = 1;    /* make a note of its type.  */
  128.          resultproc(xpix,ypix, 0.0,0.0,0.0,0.0, LX,0);
  129.                /* Special call equivalent to xl[ypix] = xpix    */
  130.          }
  131.       edgetype=1; toggle = 1;      /* Set edgetype and          */
  132.       goto gamma;                  /* go to main edge-processor.*/
  133.       }
  134.    else {                          /*--   Left: Edgetype 4    --*/
  135.       if(firstleftedgetype==0)     /* If at first edge, make    */
  136.          firstleftedgetype = 4;    /* a note of its type.       */
  137.       edgetype=4; toggle = 2;      /* Set edgetype and          */
  138.       goto gamma;                  /* go to main edge-processor.*/
  139.       }
  140.  
  141. edge_end_l:   /* The main edge-processor returns here when the edge is done*/
  142.    iv = ivp1;          /* Set subscripts for the next left edge. */
  143.    ivp1= (iv+1) % scrnfaceptr->numvert;  /* '' */
  144.    }
  145.  
  146. /*===  Make a note of the edgetype of the last edge on the left. ====*/
  147. lastleftedgetype = edgetype; 
  148.           
  149. /*==== Process each edge of the right-hand side of polygon. ====*/
  150. iv = scrnfaceptr->imin;                       /* Find subscripts of first  */
  151. ivm1= (iv+scrnfaceptr->numvert-1) % scrnfaceptr->numvert; /* right edge &  */
  152. xend=scrnfaceptr->xcoord[iv];  yend=scrnfaceptr->ycoord[iv]; /* the coords */
  153. xpend = (int)xend; ypend = (int)yend;             /* of its starting point.*/
  154.  
  155. firstrightedge = TRUE;
  156.  
  157. while(iv!=scrnfaceptr->imax) {
  158.    xpix  = xpend; ypix  = ypend;                /* get coords of the       */
  159.    xstt  = xend;    ystt  = yend;               /* starting pixel of edge  */
  160.    xpstt = xpend; ypstt = ypend;                /*        and              */
  161.    xpend=(int)(xend= scrnfaceptr->xcoord[ivm1]);   /* the coords of        */
  162.    ypend=(int)(yend= scrnfaceptr->ycoord[ivm1]);   /* the end pixel.       */
  163.    exend= xend-xpend; eyend= yend-ypend; /* Bresenham errors at end pixel. */
  164.  
  165.    if(xstt<xend) { /*--- Right: Edgetype 3 ---*/
  166.       /*-- Correct for bottom-most pixel bitmask, if necessary. --*/
  167.       if(firstrightedge == TRUE) {
  168.          firstrightedge = FALSE;
  169.          if(firstleftedgetype==1) {
  170.             exstt=(xstt-xpstt);   eystt=(ystt-ypstt);
  171.             resultproc( xpix,ypix, exstt, eystt, exstt, eystt, MY, 4); 
  172.             }
  173.           }
  174.       edgetype=3; toggle = 1;  /* Set the current edgetype and   */
  175.       goto gamma;              /* go to the main edge-processor. */
  176.       }
  177.    else {     /*--- Right: Edgetype 2 ---*/
  178.       /*-- Correct for bottom-most pixel bitmask, if necessary.  --*/
  179.       if(firstrightedge==TRUE) {
  180.          firstrightedge = FALSE;
  181.          if(firstleftedgetype==4) {
  182.             exstt=(xstt-xpstt);   eystt=(ystt-ypstt);
  183.             resultproc(xpix,ypix, exstt, eystt, exstt, eystt, MY, 3);
  184.             }
  185.             resultproc(xpix,ypix, 0.0,0.0,0.0,0.0, RX,0);
  186.                       /* Special call equivalent to xr[ypix] = xpix. */
  187.          }
  188.       edgetype=2;  toggle = 2;  /* Set the current edgetype. */
  189.       goto gamma;               /* Go to main edge-processor.*/
  190.       }
  191.  
  192. edge_end_r:   /* The main edge-processor returns here once edge is done */
  193.    iv =  ivm1;         /* set subscripts for next right-edge */
  194.    ivm1= (iv+scrnfaceptr->numvert-1) % scrnfaceptr->numvert;
  195.    }
  196.  
  197. /*=== do the final vertex bitmask correction, if necessary ===*/
  198. if(lastleftedgetype==4 && edgetype==2)
  199.    resultproc(xpend,ypend, exend, eyend, exend, eyend, MY, 1);
  200. else if(lastleftedgetype==1 && edgetype==3)
  201.    resultproc(xpend,ypend, exend, eyend, exend, eyend, MY, 2);
  202.   
  203. return;
  204.  
  205. /*=== Routine ends here, extracted code follows ======================
  206.  
  207. The following segment is the main edge-processor. It identifies the
  208. coords xpix,ypix of each pixel intersected by the edge, and the type
  209. of intersection (see Fig. 2 in the main text). All four edgetypes
  210. are handled using the switches 'edgetype' and 'toggle'
  211.  
  212. Two Bresenham 'error' quantities are used to identify the pixels:
  213.  
  214.  ex: the x-distance from the left boundary of the pixel to the
  215.  intercept of the edge with the upper boundary of the pixel.
  216.  
  217.  ey: the y-distance from the right boundary of the pixel to the
  218.  intercept of the edge with the right boundary of the pixel.
  219.  
  220. Each pixel is found from the previous one by updating either ex or
  221. ey and then testing its value to identify the type of intersection.
  222.  
  223. ex0, ey0 are initially the values of ex, ey at the starting pixel of
  224. the edge, but subsequently hold the previous values as ex,ey are
  225. updated.
  226.  
  227. =====================================================================*/
  228.  
  229. gamma:
  230.  
  231. /*=== If the edge lies entirely in one pixel, record this and finish. ===*/
  232. if( (xpix==xpend) && (ypix==ypend) ) {
  233.    resultproc(xpix,ypix, xstt-xpstt,ystt-ypstt, exend,eyend, NN, edgetype); 
  234.    switch(edgetype) {
  235.       case 3: case 2: goto edge_end_r;
  236.       case 4: case 1: goto edge_end_l;
  237.       }
  238.    } 
  239.  
  240. /*=== If not, calculate the slope of the edge. ===*/
  241. delx = xend-xstt; dely = yend-ystt;
  242. if(toggle==1) { /* edgetype 1 or 3 */
  243.    delymp =  dely;  largemp = LARGE;
  244.    }
  245. else { /* edgetype 2 or 4 */
  246.    delymp = -dely;  largemp = -LARGE; 
  247.    }
  248.  
  249. if(delx!=0)   dy_by_dx=delymp/delx; 
  250. else {
  251.    dx_by_dy = 0;  dy_by_dx = LARGE;
  252.    }
  253. if(dely!=0)   dx_by_dy=delx/dely;
  254. else {
  255.    dy_by_dx = 0; dx_by_dy = largemp;
  256.    }
  257.  
  258. /*=== Look at first pixel. ===*/
  259. ex0= xstt-xpstt;  ey0= ystt-ypstt; /* Set Bresenham error variables */
  260. ex = ex0 + dx_by_dy*(hpix-ey0);
  261.  
  262. if(toggle==1) {    /* edgetype 1 or 3 */
  263.    ey = ey0 + dy_by_dx*(hpix-ex0);
  264.    if(ex < hpix) { /* Depending on the size of ex, the pixel is of type LX */
  265.       resultproc(xpix, ypix, ex0, ey0, ex, hpix, LX, edgetype); goto alpha;
  266.       }
  267.    else {          /* or of type LY. */
  268.       resultproc(xpix, ypix, ex0, ey0, hpix, ey, LY, edgetype); goto beta;
  269.       }
  270.    }
  271. else {             /* edgetype 2 or 4 */
  272.    ey = ey0 + dy_by_dx*ex0;
  273.    if(ex > 0) {    /* Depending on the sign of ex, the pixel is of type RX */
  274.       resultproc(xpix, ypix, ex0, ey0, ex, hpix, RX, edgetype); goto alpha;
  275.       }
  276.    else {          /* or of type RY. */
  277.       resultproc(xpix, ypix, ex0, ey0,  0.0, ey, RY, edgetype); goto beta;
  278.       }
  279.    }
  280.  
  281. alpha: /*== The upper boundary just crossed; now at new y-level ==*/
  282. ypix++;
  283. ey -= hpix;
  284.  
  285. if(toggle==1) { /* edgetype 1 or 3 */
  286.    /* If at last pixel of edge, finish off edge. */
  287.    if( (ypix >= ypend) && (xpix >= xpend) ) {
  288.       resultproc(xpend,ypend, ex, 0.0, exend, eyend, RX, edgetype);
  289.       if(edgetype==1)   goto edge_end_l;
  290.       else              goto edge_end_r;
  291.       }
  292.    }
  293. else {          /* edgetype 2 or 4 */
  294.    /* If at last pixel of edge, finish off edge. */
  295.    if( (ypix >= ypend) && (xpix <= xpend) ) {
  296.       resultproc(xpend, ypend, ex, 0.0, exend, eyend, LX, edgetype);
  297.       if(edgetype==4)   goto edge_end_l;
  298.       else              goto edge_end_r;
  299.       }
  300.    }
  301.  
  302. /*=== Not yet at end of edge. Update ex and carry on. ===*/
  303. ex0 = ex;   ex += dx_by_dy;
  304. if(toggle==1) {    /* edgetype 1 or 3 */
  305.    if(ex < hpix) { /* Depending on the size of ex, pixel is of type MX */
  306.       resultproc(xpix, ypix, ex0, 0.0, ex, hpix, MX, edgetype); goto alpha;
  307.       }
  308.    else {          /* or of type SY. */
  309.       resultproc(xpix, ypix, ex0, 0.0, hpix, ey, SY, edgetype); goto beta;
  310.       }
  311.    }
  312. else {             /* edgetype 2 or 4 */
  313.    if(ex > 0) {    /* Depending on the sign of ex, pixel is of type MX */
  314.       resultproc(xpix, ypix, ex0, 0.0, ex, hpix, MX, edgetype); goto alpha;
  315.       }
  316.    else {          /* or of type TY. */
  317.       resultproc(xpix, ypix, ex0, 0.0, 0.0,  ey, TY, edgetype); goto beta;
  318.       }
  319.    }
  320.  
  321. beta:  /*== Just crossed a vertical pixel boundary; now at new x-level ==*/
  322. if(toggle==1) {    /* edgetype 1 or 3 */
  323.    xpix++;
  324.    ex -= hpix;
  325.    /* If at last pixel of edge, finish off edge. */
  326.    if( (ypix>=ypend) && (xpix>=xpend) ) {
  327.       resultproc(xpend, ypend,  0.0, ey, exend, eyend, RY, edgetype);
  328.       if(edgetype==3)   goto edge_end_r;
  329.       else              goto edge_end_l;
  330.       }
  331.    } 
  332. else {             /* edgetype 2 or 4 */
  333.    xpix--;
  334.    ex += hpix;
  335.    /* If at last pixel of edge, finish off edge. */
  336.    if( (xpix <= xpend) && (ypix >= ypend) ) {
  337.       resultproc(xpend, ypend, hpix, ey, exend, eyend, LY, edgetype);
  338.       if(edgetype==4)   goto edge_end_l;
  339.       else              goto edge_end_r;
  340.       }
  341.    }
  342.  
  343. /*=== Not yet at end of edge. Update ey, and carry on. ===*/
  344. ey0 = ey;   ey += dy_by_dx;
  345. if(toggle==1) {    /* edgetype 1 or 3 */
  346.    if(ey < hpix) { /* Depending on size of ey, pixel is of type MY */
  347.       resultproc(xpix, ypix,   0.0, ey0, hpix, ey, MY, edgetype); goto beta;
  348.       }
  349.    else {          /* or of type SX. */
  350.       resultproc(xpix, ypix,   0.0, ey0, ex, hpix, SX, edgetype); goto alpha;
  351.       }
  352.     }
  353. else {             /* edgetype 2 or 4 */
  354.    if(ey < hpix) { /* Depending on size of ey, pixel is of type MY */
  355.       resultproc(xpix, ypix,  hpix, ey0,  0.0, ey, MY, edgetype); goto beta;
  356.       }
  357.    else {          /* or of type TX. */
  358.       resultproc(xpix, ypix,  hpix, ey0, ex, hpix, TX, edgetype); goto alpha;
  359.       }
  360.    }
  361. }
  362.  
  363. /*===========================================================================
  364. This illustrates how the output from the edge calculator can be used
  365. The routine modifies externally defined arrays fragptr[], xl[] and xr[] (which
  366. are accessed via global pointers).
  367. It uses a global pointer to recognize precalculated bitmasks held in a
  368. structure.
  369. ===========================================================================*/
  370.  
  371. void resultproc(xpix,ypix,x1,y1,x2,y2,pixtype,edgetype)
  372. int xpix,ypix;           /* position of pixel to which information applies */
  373. float x1,y1,x2,y2;       /* position of the two endpoints of edge intersecting
  374.                             the polygon */
  375. int pixtype;             /* type of overlap in this pixel (NN,LX,LY,...) */
  376. int edgetype;            /* type of edge (1,2,3 or 4)         */
  377.  
  378. {
  379. extern aabufftype * aabuffptr;     /* pointer to a structure in which the
  380.             precomputed bitmasks are held. Their format is given in the text.*/
  381. extern unsigned short * fragptr; /* pointer to linear array holding bitmasks
  382.             of the overlaps of the polygon with pixels, assuming HRES
  383.             pixels per scanline. On entry each entry should be set to 0xffff */
  384. extern int * xl, * xr;          /* pointers to arrays storing positions of the
  385.           left and right edges of the polygon: xl[y] and xr[y] give the
  386.           x-position of the leftmost and rightmost pixels of the polygon on
  387.           scanline y */
  388. static float scale = 3.999; /* this should be set to just less than the ratio
  389.             of pixel to subpixel widths. The value 3.999 is for the case where
  390.             each pixel is 4x4 subpixels */
  391. int ij,ix1,ix2,iy1,iy2;
  392.  
  393. ij  = xpix + HRES*ypix;
  394. ix1 = x1*scale;  iy1 = y1*scale;
  395. ix2 = x2*scale;  iy2 = y2*scale;
  396.  
  397. /*-- adjust current bitmask by bitwise ANDing it with computed bitmask --*/
  398. if(edgetype>0)
  399.    fragptr[ij] &= aabuffptr->mask[edgetype] [ix1] [iy1] [ix2] [iy2];
  400.  
  401. /*-- record the leftmost and rightmost pixel positions, xl[y] and xr[y]
  402.      of the polygon on each scanline y --*/
  403. if      (rl[pixtype][edgetype]== 1)  xr[ypix]=xpix;
  404. else if (rl[pixtype][edgetype]==-1)  xl[ypix]=xpix;
  405.  
  406. return ;
  407. }
  408.