home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / IRIT / POLY3DRS.ZIP / SCANDATA.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-05  |  16.0 KB  |  491 lines
  1. /*****************************************************************************
  2. *   Routines to    scan convert the input (polygons), which is sorted into         *
  3. * global hash table PolyHashTable according to polygons Ymin.             *
  4. *                                         *
  5. * Written by:  Gershon Elber                Ver 2.0, Mar. 1990   *
  6. *****************************************************************************/
  7.  
  8. #ifdef __MSDOS__
  9. #include <stdlib.h>
  10. #endif /* __MSDOS__ */
  11.  
  12. #include <math.h>
  13. #include <time.h>
  14. #include <stdio.h>
  15. #include <string.h>
  16. #include "program.h"
  17. #include "parser.h"
  18. #include "gif_lib.h"
  19.  
  20. /* #define DEBUG            /* Add some printing to stderr routines. */
  21.  
  22. #define Z_BUFFER_MIN_Z    -32767
  23.  
  24. static PixelType *MaskSubScanLine = NULL;
  25. static PixelType *ImageScanLine = NULL;
  26. static PixelType *MaskScanLine = NULL;
  27. static int *ZBuffer;
  28.  
  29. static void InitScanLine(void);
  30. static void ScanOnePolygon(PolygonStruct *PPolygon, int Level);
  31. static VertexStruct *GetNeighborVrtx(PolygonStruct *PPolygon, VertexStruct *V,
  32.                             VertexStruct *NotV);
  33. static void UpdateScanLine(int x1, int z1, int x2, int z2,
  34.                         int Color1, int Color2);
  35.  
  36. #ifdef DEBUG
  37. void PrintHashTable(void);
  38. void PrintPolygon(PolygonStruct *PPolygon);
  39. void PrintImageScanLine(void);
  40. #endif DEBUG
  41.  
  42. /*****************************************************************************
  43. * Routine to scan convert all polygons in PolyHashTable.             *
  44. * The real images goes to GifFile, while GifMask (if not NULL) will have a   *
  45. * booleam mask, where image was created.                     *
  46. *****************************************************************************/
  47. void ScanConvertData(GifFileType *GifFile, GifFileType *GifMask)
  48. {
  49.     char *ImageSubBGScanLine;
  50.     int i, j, k, OrigScreenXSize, OrigScreenYSize, *ImageSubScanLine,
  51.     SubSamplePixelSquare, *MinIntensityIndex, SubSamplePixel,
  52.     MinYScan = 0, SubSampleLine = 0, LineCount = 0;
  53.     long SaveTime = time(NULL);
  54.     PolygonStruct *PPolygon, *PPolygonLast;
  55.     PixelType *OneSubScanLine;
  56.  
  57.     OrigScreenXSize = ScreenXSize;
  58.     OrigScreenYSize = ScreenYSize;
  59.  
  60.     ScreenXSize *= ShadingInfo.SubSamplePixel;
  61.     ScreenYSize *= ShadingInfo.SubSamplePixel;
  62.  
  63.     if (ShadingInfo.SubSamplePixel > 1) {
  64.     OneSubScanLine = (PixelType *) MyMalloc(sizeof(PixelType) *
  65.                             OrigScreenXSize);
  66.     ImageSubScanLine = (int *) MyMalloc(sizeof(int) * OrigScreenXSize);
  67.     ImageSubBGScanLine = (char *) MyMalloc(sizeof(char) * OrigScreenXSize);
  68.     }
  69.     ImageScanLine = (PixelType *) MyMalloc(sizeof(PixelType) * ScreenXSize);
  70.     if (GifMask != NULL) {
  71.     if (ShadingInfo.SubSamplePixel > 1)
  72.         MaskSubScanLine = (PixelType *) MyMalloc(sizeof(PixelType) *
  73.                             OrigScreenXSize);
  74.     MaskScanLine = (PixelType *) MyMalloc(sizeof(PixelType) * ScreenXSize);
  75.     }
  76.     ZBuffer = (int *) MyMalloc(sizeof(int) * ScreenXSize);
  77.  
  78.     MinIntensityIndex = ShadingInfo.MinIntensityIndex;
  79.     SubSamplePixel = ShadingInfo.SubSamplePixel;
  80.     SubSamplePixelSquare = SQR(SubSamplePixel);
  81.  
  82.     fprintf(stderr, "\nPass 4, Level [%4d] =      ", OrigScreenYSize);
  83.  
  84.     for (i=0; i<ScreenYSize; i++) {                 /* Scan line i: */
  85.     /* First lets scan and delete all polygons below this scan line: */
  86.     for (j=MinYScan; j<=i; j++) {
  87.         PPolygon = PPolygonLast = PolyHashTable[j];
  88.         while (PPolygon) {
  89.         if (PPolygon -> Ymax < i) {         /* Delete this polygon. */
  90.             /* If it is first one, update the hash table also. Note  */
  91.             /* we dont free the polygon as, we are not going to      */
  92.             /* allocate anything any more, so why bather.         */
  93.             if (PPolygon == PolyHashTable[j])
  94.             PolyHashTable[j] = PPolygonLast = PPolygon =
  95.                 PPolygon -> Pnext;
  96.             else PPolygonLast -> Pnext = PPolygon = PPolygon -> Pnext;
  97.         }
  98.         else {
  99.             PPolygonLast = PPolygon;
  100.             PPolygon = PPolygon -> Pnext;
  101.         }
  102.         }
  103.         /* If this level is empty - advance the minimum level to scan: */
  104.         if (j == MinYScan && PolyHashTable[j] == NULL) MinYScan++;
  105.     }
  106.  
  107.     /* New do the scan conversion of the active polygons: */
  108.     InitScanLine();
  109.     for (j=MinYScan; j<=i; j++) {
  110.         PPolygon = PPolygonLast = PolyHashTable[j];
  111.         while (PPolygon) {
  112.         ScanOnePolygon(PPolygon, i);
  113.         PPolygonLast = PPolygon;
  114.         PPolygon = PPolygon -> Pnext;
  115.         }
  116.     }
  117.  
  118.     if (SubSamplePixel > 1) {
  119.         if (SubSampleLine == 0) {      /* Reset the sub sumpling buffers. */
  120.         memset(ImageSubScanLine, 0,
  121.                     sizeof(int) * OrigScreenXSize);
  122.         memset(OneSubScanLine, 0,
  123.                     sizeof(PixelType) * OrigScreenXSize);
  124.         memset(ImageSubBGScanLine, 0,
  125.                     sizeof(char) * OrigScreenXSize);
  126.         if (GifMask) memset(MaskSubScanLine, 0,
  127.                     sizeof(PixelType) * OrigScreenXSize);
  128.         }
  129.         for (j=0; j<ScreenXSize; j++)
  130.         if (ImageScanLine[j] == 0)
  131.             ImageSubBGScanLine[j / SubSamplePixel]++;
  132.         else {
  133.             k = j / SubSamplePixel;
  134.             ImageSubScanLine[k] += ImageScanLine[j];
  135.             OneSubScanLine[k] = ImageScanLine[j];
  136.             if (GifMask) MaskSubScanLine[k] = MaskScanLine[j] != 0 ||
  137.                                MaskSubScanLine[k];
  138.         }
  139.         SubSampleLine++;
  140.         if (SubSampleLine == SubSamplePixel) {
  141.         for (j=0; j<OrigScreenXSize; j++) {
  142.             /* Instead of Back Ground - add the lowest intensity of */
  143.             /* This color. Note we still may have problems if two   */
  144.             /* colors are averaged to a color index in between...   */
  145.             if (ImageSubScanLine[j] > 0)
  146.             ImageSubScanLine[j] += ImageSubBGScanLine[j] *
  147.                     MinIntensityIndex[OneSubScanLine[j]];
  148.             OneSubScanLine[j] = ImageSubScanLine[j] /
  149.                             SubSamplePixelSquare;
  150.         }
  151.         fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);
  152.  
  153. #            ifndef DEBUG_NO_GIF
  154.             EGifPutLine(GifFile, OneSubScanLine, OrigScreenXSize);
  155.             if (GifMask)
  156.             EGifPutLine(GifMask, MaskSubScanLine, OrigScreenXSize);
  157. #            endif DEBUG_NO_GIF
  158.  
  159.         SubSampleLine = 0;
  160.         }
  161.     }
  162.     else {
  163.         fprintf(stderr, "\b\b\b\b\b%5d", ++LineCount);
  164.  
  165. #        ifndef DEBUG_NO_GIF
  166.         EGifPutLine(GifFile, ImageScanLine, ScreenXSize);
  167.         if (GifMask)
  168.             EGifPutLine(GifMask, MaskScanLine, ScreenXSize);
  169. #        endif DEBUG_NO_GIF
  170.     }
  171.     }
  172.  
  173.     fprintf(stderr, ",  %ld seconds.", time(NULL) - SaveTime);
  174.  
  175.     ScreenXSize = OrigScreenXSize;
  176.     ScreenYSize = OrigScreenYSize;
  177. }
  178.  
  179. /*****************************************************************************
  180. * Reset all buffers to clear state:                         *
  181. *****************************************************************************/
  182. static void InitScanLine(void)
  183. {
  184.     memset(ImageScanLine, 0, sizeof(PixelType) * ScreenXSize);
  185.  
  186.     if (MaskScanLine) memset(MaskScanLine, 0, sizeof(PixelType) * ScreenXSize);
  187.  
  188.     /* Set all Zbuffer to Z_BUFFER_MIN_Z. Can be done in a regular loop as:  */
  189.     /* for (i=0; i<ScreenXSize; i++) ZBuffer[i] = Z_BUFFER_MIN_Z;            */
  190.     /* As memset allows setting of only one byte, the minimum we can set     */
  191.     /* here is -32640 which is 0x8080, so we do that instead:             */
  192.     memset(ZBuffer, 0x80, sizeof(int) * ScreenXSize);
  193. }
  194.  
  195. /*****************************************************************************
  196. * Scan convert one polygon:                             *
  197. * 1. If one of the left/right boundaries is found to be below current level  *
  198. *    that boundary edge is updated.                         *
  199. * 2. Interpolate the Color and Z value of the intersection of scan line with *
  200. *    the boundaries and call UpdateScanLine to update the buffers.         *
  201. *****************************************************************************/
  202. static void ScanOnePolygon(PolygonStruct *PPolygon, int Level)
  203. {
  204.     int x1, z1, x2, z2, Color1, Color2;
  205.     float t1, t2, *Coord1, *Coord2;
  206.     VertexStruct *V;
  207.  
  208.     /* Stage 1 - verify that both boundaries are in range: */
  209.     if (PPolygon -> Bndry1.MaxEdgeY < Level) {
  210.     V = PPolygon -> Bndry1.VMinY;
  211.     PPolygon -> Bndry1.VMinY = PPolygon -> Bndry1.VMaxY;
  212.     PPolygon -> Bndry1.VMaxY =
  213.         GetNeighborVrtx(PPolygon, PPolygon -> Bndry1.VMaxY, V);
  214.     PPolygon -> Bndry1.MaxEdgeY =
  215.         (int) PPolygon -> Bndry1.VMaxY -> Coord[1];
  216.     }
  217.  
  218.     if (PPolygon -> Bndry2.MaxEdgeY < Level) {
  219.     V = PPolygon -> Bndry2.VMinY;
  220.     PPolygon -> Bndry2.VMinY = PPolygon -> Bndry2.VMaxY;
  221.     PPolygon -> Bndry2.VMaxY =
  222.         GetNeighborVrtx(PPolygon, PPolygon -> Bndry2.VMaxY, V);
  223.     PPolygon -> Bndry2.MaxEdgeY =
  224.         (int) PPolygon -> Bndry2.VMaxY -> Coord[1];
  225.     }
  226.  
  227.     /* Stage 2 - evaluate the interpolated X & Z for this line and call      */
  228.     /* UpdateScanLine with them. Note we could do it using some sort of DDA  */
  229.     /* (integer arithmetic) but as UpdateScanLine is much more expensive     */
  230.     /* we will gain almost nothing in speed, doing that.             */
  231.     /* Also as this polygon assumed to intersect with the scan line using    */
  232.     /* integer arithmetic, it might not be so, when we actuallt evaluate it. */
  233.     /* We simply quit if that is the case.                     */
  234.     Coord1 = PPolygon -> Bndry1.VMinY -> Coord;
  235.     Coord2 = PPolygon -> Bndry1.VMaxY -> Coord;
  236.     if (ABS(Coord2[1] - Coord1[1]) == 0.0)
  237.      t1 = 0.5;
  238.     else t1 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
  239.     if (t1 < 0.0 || t1 > 1.0) return;
  240.  
  241.     x1 = Coord1[0] * t1 + Coord2[0] * (1.0 - t1);
  242.     z1 = Coord1[2] * t1 + Coord2[2] * (1.0 - t1);
  243.  
  244.     Coord1 = PPolygon -> Bndry2.VMinY -> Coord;
  245.     Coord2 = PPolygon -> Bndry2.VMaxY -> Coord;
  246.     if (ABS(Coord2[1] - Coord1[1]) == 0.0)
  247.      t2 = 0.5;
  248.     else t2 = (Coord2[1] - Level) / (Coord2[1] - Coord1[1]);
  249.     if (t2 < 0.0 || t2 > 1.0) return;
  250.  
  251.     x2 = Coord1[0] * t2 + Coord2[0] * (1.0 - t2);
  252.     z2 = Coord1[2] * t2 + Coord2[2] * (1.0 - t2);
  253.  
  254.     if (GouraudFlag) {
  255.     /* Need to interpolate the colors as well: */
  256.     Color1 = (int) (PPolygon -> Bndry1.VMinY -> Color * t1 +
  257.             PPolygon -> Bndry1.VMaxY -> Color * (1.0 - t1));
  258.     Color2 = (int) (PPolygon -> Bndry2.VMinY -> Color * t2 +
  259.             PPolygon -> Bndry2.VMaxY -> Color * (1.0 - t2));
  260.     UpdateScanLine(x1, z1, x2, z2, Color1, Color2);
  261.     }
  262.     else {
  263.  
  264.     /* Flat shading - all vertices has same intensity - pick one: */
  265.     UpdateScanLine(x1, z1, x2, z2, PPolygon -> Bndry1.VMinY -> Color,
  266.                        PPolygon -> Bndry1.VMinY -> Color);
  267.     }
  268. }
  269.  
  270. /*****************************************************************************
  271. * Returns the other neighbor of vertex V in polygon PPolygon which is not    *
  272. * the neighbor NotV.                                 *
  273. *****************************************************************************/
  274. static VertexStruct *GetNeighborVrtx(PolygonStruct *PPolygon, VertexStruct *V,
  275.                             VertexStruct *NotV)
  276. {
  277.     struct VertexStruct *List = PPolygon -> PVertex, *ListLast;
  278.  
  279.     if (List == V) {
  280.     /* The vertex is first - its neighbors are second and last in list.  */
  281.     if (List -> Pnext == NotV) {
  282.         /* We need the last one: */
  283.         while (List -> Pnext != NULL) List = List -> Pnext;
  284.         return List;
  285.     }
  286.     else return List -> Pnext;
  287.     }
  288.  
  289.     ListLast = List;
  290.     List = List -> Pnext;
  291.     while (List != NULL) {
  292.     if (List == V) {
  293.         if (ListLast == NotV) {
  294.         /* We need the next vertex instead of last one: */
  295.         if (List -> Pnext == NULL)
  296.              return PPolygon -> PVertex;
  297.         else return List -> Pnext;
  298.         }
  299.         else return ListLast;
  300.     }
  301.     ListLast = List;
  302.     List = List -> Pnext;
  303.     }
  304.     return List;         /* Should never be here - make warnings silent. */
  305. }
  306.  
  307. /*****************************************************************************
  308. * Update the scan line itself by linearly interplate the two end points for  *
  309. * all internal points of scan line if closer than old data.             *
  310. *****************************************************************************/
  311. static void UpdateScanLine(int x1, int z1, int x2, int z2,
  312.                         int Color1, int Color2)
  313. {
  314.     int i, Dx, Dz, Dc, Az, Ac, x, z, Color;
  315.     float t;
  316.  
  317.     if (x2 < x1) {
  318.     i = x2; x2 = x1; x1 = i;
  319.     i = z2; z2 = z1; z1 = i;
  320.     i = Color2; Color2 = Color1; Color1 = i;
  321.     }
  322.     if (x1 < 0) {
  323.     /* Update lower limit to zero: */
  324.     if (x2 == x1) return;
  325.     t = -x1 / (x2 - x1);
  326.     x1 = 0;
  327.     z1 = (int) (z1 * (1.0 - t) + z2 * t);
  328.     Color1 = (int) (Color1 * (1.0 - t) + Color2 * t);
  329.     }
  330.     if (x2 >= ScreenXSize) {
  331.     /* Update upper limit to ScreenXSize - 1: */
  332.     if (x2 == x1) return;
  333.     t = (x2 - (ScreenXSize - 1)) / (x2 - x1);
  334.     x2 = ScreenXSize - 1;
  335.     z2 = (int) (z1 * t + z2 * (1.0 - t));
  336.     Color2 = (int) (Color1 * t + Color2 * (1.0 - t));
  337.     }
  338.  
  339.     Dx = x2 - x1;
  340.     x = x1;
  341.     Dz = z2 - z1;
  342.     Az = -Dx;                  /* DDA accumulator of Z interpolation. */
  343.     z = z1;
  344.     Color = Color1;
  345.     if (GouraudFlag) {
  346.     Dc = Color2 - Color1;         /* Needed if Gouraud shading is in use. */
  347.     Ac = -Dx;          /* DDA accumulator of Color interpolation. */
  348.     }
  349.  
  350.     /* We are going to execute the loop once but might be stack forever in   */
  351.     /* one of the internal interplation loops, so make it non zero:         */
  352.     if (Dx == 0) Dx = 999;
  353.  
  354.     if (Dz > 0) {
  355.     while (x <= x2) {
  356.         /* Update buffers iff is closer to view point: */
  357.         if (ZBuffer[x] < z) {
  358.         ZBuffer[x] = z;
  359.         ImageScanLine[x] = Color;
  360.         if (MaskScanLine != NULL) MaskScanLine[x] = 1;
  361.         }
  362.         else
  363.         if (ZBuffer[x] == z) {
  364.         /* This case is hard to solve, and it may create high         */
  365.         /* intensity lines on polygon boundaries. To prevent from    */
  366.         /* that, update iff new color intensity is less than old on. */
  367.         if (ImageScanLine[x] < Color) ImageScanLine[x] = Color;
  368.         if (MaskScanLine != NULL) MaskScanLine[x] = 1;
  369.         }
  370.  
  371.         Az += Dz;
  372.         x++;
  373.         while (Az > 0) {
  374.         z++;
  375.         Az -= Dx;
  376.         }
  377.         if (GouraudFlag) {
  378.         if (Dc > 0) {
  379.             Ac += Dc;
  380.             while (Ac > 0) {
  381.             Color++;
  382.             Ac -= Dx;
  383.             }
  384.         }
  385.         else { /* Dc < 0 */
  386.             Ac -= Dc;
  387.             while (Ac > 0) {
  388.             Color--;
  389.             Ac -= Dx;
  390.             }
  391.         }
  392.         }
  393.     }
  394.     }
  395.     else { /* Dz < 0 */
  396.     while (x <= x2) {
  397.         /* Update buffers iff is closer to view point: */
  398.         if (ZBuffer[x] < z) {
  399.         ZBuffer[x] = z;
  400.         ImageScanLine[x] = Color;
  401.         if (MaskScanLine != NULL) MaskScanLine[x] = 1;
  402.         }
  403.         else
  404.         if (ZBuffer[x] == z) {
  405.         /* This case is hard to solve, and it may create high         */
  406.         /* intensity lines on polygon boundaries. To prevent from    */
  407.         /* that, update iff new color intensity is less than old on. */
  408.         if (ImageScanLine[x] < Color) ImageScanLine[x] = Color;
  409.         if (MaskScanLine != NULL) MaskScanLine[x] = 1;
  410.         }
  411.  
  412.         Az -= Dz;
  413.         x++;
  414.         while (Az > 0) {
  415.         z--;
  416.         Az -= Dx;
  417.         }
  418.         if (GouraudFlag) {
  419.         if (Dc > 0) {
  420.             Ac += Dc;
  421.             while (Ac > 0) {
  422.             Color++;
  423.             Ac -= Dx;
  424.             }
  425.         }
  426.         else { /* Dc < 0 */
  427.             Ac -= Dc;
  428.             while (Ac > 0) {
  429.             Color--;
  430.             Ac -= Dx;
  431.             }
  432.         }
  433.         }
  434.     }
  435.     }
  436. }
  437.  
  438. #ifdef DEBUG
  439.  
  440. /*****************************************************************************
  441. * Routine to print the content of a given edge:                     *
  442. *****************************************************************************/
  443. void PrintHashTable(void)
  444. {
  445.     int i;
  446.     PolygonStruct *PPolygon;
  447.  
  448.     for (i=0; i<ScreenYSize; i++) if (PolyHashTable[i] != NULL) {
  449.     fprintf(stderr,
  450.         "\n***************** HashTable entry %d *****************\n", i);
  451.     PPolygon = PolyHashTable[i];
  452.     while (PPolygon) {
  453.         fprintf(stderr, "\t+++++++ Polygon:\n");
  454.         PrintPolygon(PPolygon);
  455.         PPolygon = PPolygon -> Pnext;
  456.     }
  457.     }
  458. }
  459.  
  460. /*****************************************************************************
  461. * Routine to print the content of a given edge:                     *
  462. *****************************************************************************/
  463. void PrintPolygon(PolygonStruct *PPolygon)
  464. {
  465.     struct VertexStruct *PList = PPolygon -> PVertex;
  466.  
  467.     while (PList) {
  468.     fprintf(stderr, "\t%12f %12f %12f (Color = %d)\n",
  469.         PList -> Coord[0],
  470.         PList -> Coord[1],
  471.         PList -> Coord[2],
  472.         PList -> Color);
  473.     PList =    PList -> Pnext;
  474.     }
  475. }
  476.  
  477. /*****************************************************************************
  478. * Routine to print content of Image Scan Line buffer:                 *
  479. *****************************************************************************/
  480. void PrintImageScanLine(void)
  481. {
  482.     int i;
  483.  
  484.     for (i=0; i<ScreenXSize; i++) {
  485.     if (i % 26 == 0) fprintf(stderr, "\n");
  486.     fprintf(stderr, "%02x ", ImageScanLine[i]);
  487.     }
  488. }
  489.  
  490. #endif DEBUG
  491.