home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / gems / graphics / aapolysc.c < prev    next >
C/C++ Source or Header  |  1992-04-09  |  8KB  |  246 lines
  1. /* 
  2. Fast Anti-Aliasing Polygon Scan Converstion
  3. by Jack Morrison
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. /*
  8. * Anti-aliased polygon scan conversion by Jack Morrison
  9. *
  10. * This code renders a polygon, computing subpixel coverage at
  11. * 8 times Y and 16 times X display resolution for anti-aliasing.
  12. * One optimization left out for clarity is the use of incremental
  13. * interpolations. X coordinate interpolation in particular can be
  14. * with integers. See Dan Field's article in ACM Transactions on
  15. * Graphics, January 1985 for a fast incremental interpolator.
  16. */
  17. #include "GraphicsGems.h"
  18.  
  19. #define    SUBYRES    8        /* subpixel Y resolution per scanline */
  20. #define    SUBXRES    16        /* subpixel X resolution per pixel */
  21. #define    MAX_AREA    (SUBYRES*SUBXRES)
  22. #define    MODRES(y)    ((y) & 7)        /*subpixel Y modulo */
  23. #define MAX_X    0x7FFF    /* subpixel X beyond right edge */
  24.  
  25. typedef struct SurfaceStruct {  /* object shading surface info */
  26.     int    red, green, blue;           /* color components */
  27.     } Surface;
  28. /*
  29. * In  real life, SurfaceStruct will contain many more parameters as
  30. * required by the shading and rendering programs, such as diffuse
  31. * and specular factors, texture information, transparency, etc.
  32. */
  33.  
  34. typedef struct VertexStruct    {    /* polygon vertex */
  35.     Vector3    model, world,        /* geometric information */
  36.             normal, image;
  37.     int y;                    /* subpixel display coordinate */
  38.     } Vertex;
  39.  
  40. Vertex *Vleft, *VnextLeft;        /* current left edge */
  41. Vertex *Vright, *VnextRight;    /* current right edge */
  42.  
  43. struct    SubPixel  {            /* subpixel extents for scanline */
  44.     int xLeft, xRight;
  45.     } sp[SUBYRES];
  46.  
  47. int    xLmin, xLmax;        /* subpixel x extremes for scanline */
  48. int    xRmax, xRmin;        /* (for optimization shortcut) */
  49.  
  50. /* Compute sub-pixel x coordinate for vertex */
  51. extern int screenX(/* Vertex *v */);
  52.  
  53. /* Interpolate vertex information */
  54. extern void vLerp(/* double alpha, Vertex *Va, *Vb, *Vout */);
  55.  
  56. /* Render polygon for one pixel, given coverage area */
  57. /*  and bitmask */
  58. extern void renderPixel(/* int x, y, Vertex *V,
  59.                         int area, unsigned mask[], 
  60.                         Surface *object */);
  61.  
  62. /*
  63.  * Render shaded polygon
  64.  */
  65. drawPolygon(polygon, numVertex, object)
  66.     Vertex    polygon[];        /*clockwise clipped vertex list */
  67.     int    numVertex;            /*number of vertices in polygon */
  68.  
  69.     Surface *object;            /* shading parms for this object */
  70. {
  71.     Vertex *endPoly;            /* end of polygon vertex list */
  72.     Vertex VscanLeft, VscanRight;    /* interpolated vertices */                                 /* at scanline */
  73.     double aLeft, aRight;            /* interpolation ratios */
  74.     struct SubPixel *sp_ptr;        /* current subpixel info */
  75.     int xLeft, xNextLeft;            /* subpixel coordinates for */
  76.     int  xRight, xNextRight;        /* active polygon edges */
  77.     int i,y;                        
  78.  
  79. /* find vertex with minimum y (display coordinate) */
  80. Vleft = polygon;
  81. for  (i=1; i<numVertex; i++)
  82.     if  (polygon[i].y < Vleft->y)
  83.         Vleft = &polygon[i];
  84. endPoly = &polygon[numVertex-1];
  85.  
  86. /* initialize scanning edges */
  87. Vright = VnextRight = VnextLeft = Vleft;
  88.  
  89. /* prepare bottom of initial scanline - no coverage by polygon */
  90. for (i=0; i<SUBYRES; i++)
  91.     sp[i].xLeft = sp[i].xRight = -1;
  92. xLmin = xRmin = MAX_X;
  93. xLmax = xRmax = -1;
  94.  
  95. /* scan convert for each subpixel from bottom to top */
  96. for (y+Vleft->y; ; y++)    {
  97.  
  98.     while (y == VnextLeft->y)    {    /* reached next left vertex */
  99.         VnextLeft = (Vleft=VnextLeft) + 1;     /* advance */
  100.         if (VnextLeft > endPoly)            /* (wraparound) */
  101.             VnextLeft = polygon;
  102.         if (VnextLeft == Vright)    /* all y's same?  */
  103.             return;                /* (null polygon) */ 
  104.         xLeft = screenX(Vleft);
  105.         xNextLeft = screenX(VnextLeft);
  106.     }
  107.  
  108.     while (y == VnextRight->y)  { /*reached next right vertex */
  109.         VnextRight = (Vright=VnextRight) -1;
  110.         if (VnextRight < polygon)            /* (wraparound) */
  111.             VnextRight = endPoly;
  112.         xRight = screenX(Vright);
  113.         xNextRight = screenX(VnextRight);
  114.     }
  115.  
  116.     if (y>VnextLeft->y || y>VnextRight->y)    {
  117.                 /* done, mark uncovered part of last scanline */
  118.         for (; MODRES(y); y++)
  119.             sp[MODRES(y)].xLeft = sp[MODRES(y)].xRight = -1;
  120.         renderScanline(Vleft, Vright, y/SUBYRES, object);
  121.         return;
  122.     }
  123.  
  124. /*
  125.  * Interpolate sub-pixel x endpoints at this y,
  126.  * and update extremes for pixel coherence optimization
  127.  */
  128.     
  129.     sp_ptr = &sp[MODRES(y)];
  130.     aLeft = (double)(y - Vleft->y) / (VnextLeft->y - Vleft->y);
  131.     sp_ptr->xLeft = LERP(aLeft, xLeft, xNextLeft);
  132.     if (sp_ptr->xLeft < xLmin)
  133.         xLmin = sp_ptr->xLeft;
  134.     if (sp_ptr->xLeft > xLmax)
  135.         xLmax = sp_ptr->xLeft;
  136.  
  137.     aRight = (double)(y - Vright->y) / (VnextRight->y 
  138.                     - Vright->y);
  139.     sp_ptr->xRight = LERP(aRight, xRight, xNextRight);
  140.     if (sp_ptr->xRight < xRmin)
  141.         xRmin = sp_ptr->xRight;
  142.     if (sp_ptr->xRight > xRmax)
  143.         xRmax = sp_ptr->xRight;
  144.  
  145.     if (MODRES(y) == SUBYRES-1)    {    /* end of scanline */
  146.             /* interpolate edges to this scanline */
  147.         vLerp(aLeft, Vleft, VnextLeft, &VscanLeft);
  148.         vLerp(aRight, Vright, VnextRight, &VscanRight);
  149.         renderScanline(&VscanLeft, &VscanRight, y/SUBYRES,             object);
  150.         xLmin = xRmin = MAX_X;         /* reset extremes */
  151.         xLmax = xRmax = -1;
  152.     }
  153.   }
  154. }
  155.  
  156. /*
  157.  * Render one scanline of polygon
  158.  */
  159.  
  160. renderScanline(Vl, Vr, y, object)
  161.     Vertex *Vl, *Vr;     /* polygon vertices interpolated */
  162.                     /* at scanline */   
  163.     int y;            /* scanline coordinate */
  164.     Surface *object;    /* shading parms for this object */
  165. {
  166.     Vertex Vpixel;    /*object info interpolated at one pixel */
  167.     unsigned mask[SUBYRES];    /*pixel coverage bitmask */
  168.     int x;            /* leftmost subpixel of current pixel */
  169.  
  170.     for (x=SUBXRES*FLOOR(xLmin/SUBXRES); x<=xRmax; x+=SUBXRES) {
  171.         vLerp((double)(x-xLmin)/(xRmax-xLmin), Vl, Vr, &Vpixel);
  172.         computePixelMask(x, mask);
  173.         renderPixel(x/SUBXRES, y, &Vpixel,
  174.                     /*computePixel*/Coverage(x), mask, object);
  175.     }
  176. }
  177.  
  178. /*
  179.  * Compute number of subpixels covered by polygon at current pixel
  180. */
  181. /*computePixel*/Coverage(x)
  182.     int x;            /* left subpixel of pixel */
  183. {
  184.     int  area;            /* total covered area */
  185.     int partialArea;      /* covered area for current subpixel y */
  186.     int xr = x+SUBXRES-1;    /*right subpixel of pixel */
  187.     int y;
  188.  
  189.     /* shortcut for common case of fully covered pixel */
  190.     if (x>xLmax && x<xRmin)
  191.         return MAX_AREA;
  192.     
  193.     for (area=y=0; y<SUBYRES; y++) {
  194.         partialArea = MIN(sp[y].xRight, xr)
  195.              - MAX(sp[y].xLeft, x) + 1;
  196.         if (partialArea > 0)
  197.             area += partialArea;
  198.     }
  199.     return area;
  200. }
  201.  
  202. /* Compute bitmask indicating which subpixels are covered by 
  203.  * polygon at current pixel. (Not all hidden-surface methods
  204.  * need this mask. )
  205. */
  206. computePixelMask(x, mask)
  207.     int x;            /* left subpixel of pixel */
  208.     unsigned mask[];    /* output bitmask */
  209. {
  210.     static unsigned leftMaskTable[] =
  211.         { 0xFFFF, 0x7FFF, 0x3FFF, 0x1FFF, 0x0FFF, 0x07FF, 0x03FF,
  212.           0x01FF, 0x00FF, 0x007F, 0x003F, 0x001F, 0x000F,                     0x0007, 0x0003, 0x0001  };
  213.     static unsigned rightMaskTable[] = 
  214.         { 0x8000, 0xC000, 0xE000, 0xF000, 0xF800, 0xFC00,                 0xFE00, 0xFF00, 0xFF80, 0xFFC0, 0xFFE0, 0xFFF0,
  215.             0xFFF8, 0xFFFC, 0xFFFE, 0xFFFF   };
  216.     unsigned leftMask, rightMask;         /* partial masks */
  217.     int xr = x+SUBXRES-1;            /* right subpixel of pixel */
  218.     int y;
  219.  
  220. /* shortcut for common case of fully covered pixel */
  221.     if (x>xLmax && x<xRmin)     {
  222.         for (y=0; y<SUBYRES; y++)
  223.             mask[y] = 0xFFFF;
  224.     } else     {
  225.         for (y=0; y<SUBYRES; y++)    {
  226.             if (sp[y].xLeft < x)     /* completely left of pixel*/
  227.                 leftMask = 0xFFFF;
  228.             else if (sp[y].xLeft > xr)  /* completely right */    
  229.                 leftMask = 0;
  230.             else
  231.                 leftMask = leftMaskTable[sp[y].xLeft -x];
  232.  
  233.             if (sp[y].xRight > xr)      /* completely  */
  234.                                     /* right of pixel*/
  235.                 rightMask = 0xFFFF;
  236.             else if (sp[y].xRight < x)    /*completely left */
  237.                 rightMask = 0;
  238.             else
  239.                 rightMask = rightMaskTable[sp[y].xRight -x];
  240.             mask[y] = leftMask & rightMask;
  241.         }
  242.     }
  243. }
  244.  
  245.  
  246.