home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / raytrace / rayshade / src / raytrace.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-04-30  |  12.3 KB  |  490 lines
  1. /*
  2.  * raytrace.c
  3.  *
  4.  * Copyright (C) 1989, 1991, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * $Id: raytrace.c,v 4.0.1.1 92/01/10 17:13:02 cek Exp Locker: cek $
  17.  *
  18.  * $Log:    raytrace.c,v $
  19.  * Revision 4.0.1.1  92/01/10  17:13:02  cek
  20.  * patch3: Made status report print actual scanline number.
  21.  * 
  22.  * Revision 4.0  91/07/17  14:50:49  kolb
  23.  * Initial version.
  24.  * 
  25.  */
  26.  
  27. #include "rayshade.h"
  28. #include "atmosphere.h"
  29. #include "surface.h"
  30. #include "sampling.h"
  31. #include "options.h"
  32. #include "stats.h"
  33. #include "raytrace.h"
  34. #include "viewing.h"
  35.  
  36. #define UNSAMPLED    -1
  37. #define SUPERSAMPLED    -2
  38.  
  39. typedef struct {
  40.     Pixel    *pix;    /* Pixel values */
  41.     int    *samp;    /* Sample number */
  42. } Scanline;
  43.  
  44. static int        *SampleNumbers;
  45. static void    RaytraceInit();
  46.  
  47. static Ray    TopRay;                /* Top-level ray. */
  48. Float        SampleTime();
  49.  
  50. Pixel        WhitePix = {1., 1., 1., 1.},
  51.         BlackPix = {0., 0., 0., 0.};
  52.  
  53. /*
  54.  * "Dither matrices" used to encode the 'number' of a ray that samples a
  55.  * particular portion of a pixel.  Hand-coding is ugly, but...
  56.  */
  57. static int OneSample[1] =     {0};
  58. static int TwoSamples[4] =    {0, 2,
  59.                  3, 1};
  60. static int ThreeSamples[9] =    {0, 2, 7,
  61.                  6, 5, 1,
  62.                  3, 8, 4};
  63. static int FourSamples[16] =    { 0,  8,  2, 10,
  64.                  12,  4, 14,  6,
  65.                   3, 11,  1,  9,
  66.                  15,  7, 13,  5};
  67. static int FiveSamples[25] =    { 0,  8, 23, 17,  2,
  68.                  19, 12,  4, 20, 15,
  69.                   3, 21, 16,  9,  6,
  70.                  14, 10, 24,  1, 13,
  71.                  22,  7, 18, 11,  5};
  72. static int SixSamples[36] =    { 6, 32,  3, 34, 35,  1,
  73.                   7, 11, 27, 28,  8, 30,
  74.                  24, 14, 16, 15, 23, 19,
  75.                  13, 20, 22, 21, 17, 18,
  76.                  25, 29, 10,  9, 26, 12,
  77.                  36,  5, 33,  4,  2, 31};
  78. static int SevenSamples[49] =    {22, 47, 16, 41, 10, 35,  4,
  79.                   5, 23, 48, 17, 42, 11, 29,
  80.                  30,  6, 24, 49, 18, 36, 12,
  81.                  13, 31,  7, 25, 43, 19, 37,
  82.                  38, 14, 32,  1, 26, 44, 20,
  83.                  21, 39,  8, 33,  2, 27, 45,
  84.                  46, 15, 40,  9, 34,  3, 28};
  85. static int EightSamples[64] =    { 8, 58, 59,  5,  4, 62, 63,  1,
  86.                  49, 15, 14, 52, 53, 11, 10, 56,
  87.                  41, 23, 22, 44, 45, 19, 18, 48,
  88.                  32, 34, 35, 29, 28, 38, 39, 25,
  89.                  40, 26, 27, 37, 36, 30, 31, 33,
  90.                  17, 47, 46, 20, 21, 43, 42, 24,
  91.                   9, 55, 54, 12, 13, 51, 50, 16,
  92.                  64,  2,  3, 61, 60,  6,  7, 57};
  93.  
  94. void    AdaptiveRefineScanline(), FullySamplePixel(), FullySampleScanline(),
  95.     SingleSampleScanline();
  96. static int    ExcessiveContrast();
  97. static Scanline scan0, scan1, scan2;
  98.  
  99.  
  100. void
  101. raytrace(argc, argv)
  102. int argc;
  103. char **argv;
  104. {
  105.     int y, *tmpsamp;
  106.     Pixel *tmppix;
  107.     Float usertime, systime, lasttime;
  108.  
  109.     /*
  110.      * If this is the first frame,
  111.      * allocate scanlines, etc.
  112.      */
  113.     if (Options.framenum == Options.startframe)
  114.         RaytraceInit();
  115.     /*
  116.      * The top-level ray TopRay always has as its origin the
  117.      * eye position and as its medium NULL, indicating that it
  118.      * is passing through a medium with index of refraction
  119.      * equal to DefIndex.
  120.      */
  121.     TopRay.pos = Camera.pos;
  122.     TopRay.media = (Medium *)0;
  123.     TopRay.depth = 0;
  124.  
  125.     /*
  126.      * Always fully sample the bottom and top rows and the left
  127.      * and right column of pixels.  This minimizes artifacts that
  128.      * may arise when piecing together images.
  129.      */
  130.     FullySampleScanline(0, &scan0);
  131.  
  132.     SingleSampleScanline(1, &scan1);
  133.     FullySamplePixel(0, 1, &scan1.pix[0], &scan1.samp[0]);
  134.     FullySamplePixel(Screen.xsize -1, 1, &scan1.pix[Screen.xsize -1],
  135.         &scan1.samp[Screen.xsize -1]);
  136.  
  137.     lasttime = 0;
  138.     for (y = 1; y < Screen.ysize; y++) {
  139.         SingleSampleScanline(y+1, &scan2);
  140.         FullySamplePixel(0, y+1, &scan2.pix[0], &scan2.samp[0]);
  141.         FullySamplePixel(Screen.xsize -1, y+1,
  142.             &scan2.pix[Screen.xsize -1],
  143.             &scan2.samp[Screen.xsize -1]);
  144.  
  145.         if (Sampling.sidesamples > 1)
  146.             AdaptiveRefineScanline(y,&scan0,&scan1,&scan2);
  147.  
  148.         PictureWriteLine(scan0.pix);
  149.  
  150.         tmppix = scan0.pix;
  151.         tmpsamp = scan0.samp;
  152.         scan0.pix = scan1.pix;
  153.         scan0.samp = scan1.samp;
  154.         scan1.pix = scan2.pix;
  155.         scan1.samp = scan2.samp;
  156.         scan2.pix = tmppix;
  157.         scan2.samp = tmpsamp;
  158.  
  159.         if ((y+Screen.miny-1) % Options.report_freq == 0) {
  160.             fprintf(Stats.fstats,"Finished line %d (%lu rays",
  161.                         y+Screen.miny-1,
  162.                         Stats.EyeRays);
  163.             if (Options.verbose) {
  164.                 /*
  165.                  * Report total CPU and split times.
  166.                  */
  167.                 RSGetCpuTime(&usertime, &systime);
  168.                 fprintf(Stats.fstats,", %2.2f sec,",
  169.                         usertime+systime);
  170.                 fprintf(Stats.fstats," %2.2f split",
  171.                         usertime+systime-lasttime);
  172.                 lasttime = usertime+systime;
  173.             }
  174.             fprintf(Stats.fstats,")\n");
  175.             (void)fflush(Stats.fstats);
  176.         }
  177.  
  178.     }
  179.     /*
  180.      * Supersample last scanline.
  181.      */
  182.     for (y = 1; y < Screen.xsize -1; y++) {
  183.         if (scan0.samp[y] != SUPERSAMPLED)
  184.             FullySamplePixel(y, Screen.ysize -1,
  185.                 &scan0.pix[y],
  186.                 &scan0.samp[y]);
  187.     }
  188.     PictureWriteLine(scan0.pix);
  189. }
  190.  
  191. void
  192. SingleSampleScanline(line, data)
  193. int line;
  194. Scanline *data;
  195. {
  196.     Float upos, vpos, yp;
  197.     int x, usamp, vsamp;
  198.     Pixel tmp;
  199.  
  200.     yp = line + Screen.miny - 0.5*Sampling.filterwidth;
  201.     for (x = 0; x < Screen.xsize; x++) {
  202.         /*
  203.          * Pick a sample number...
  204.          */
  205.         data->samp[x] = nrand() * Sampling.totsamples;
  206.         /*
  207.          * Take sample corresponding to sample #.
  208.          */
  209.         usamp = data->samp[x] % Sampling.sidesamples;
  210.         vsamp = data->samp[x] / Sampling.sidesamples;
  211.  
  212.         vpos = yp + vsamp * Sampling.filterdelta;
  213.         upos = x + Screen.minx - 0.5*Sampling.filterwidth +
  214.                 usamp*Sampling.filterdelta;
  215.         if (Options.jitter) {
  216.             vpos += nrand()*Sampling.filterdelta;
  217.             upos += nrand()*Sampling.filterdelta;
  218.         }
  219.         TopRay.time = SampleTime(SampleNumbers[data->samp[x]]);
  220.         SampleScreen(upos, vpos, &TopRay,
  221.             &data->pix[x], SampleNumbers[data->samp[x]]);
  222.         if (Options.samplemap)
  223.             data->pix[x].alpha = 0;
  224.     }
  225. }
  226.  
  227. void
  228. FullySampleScanline(line, data)
  229. int line;
  230. Scanline *data;
  231. {
  232.     int x;
  233.  
  234.     for (x = 0; x < Screen.xsize; x++) {
  235.         data->samp[x] = UNSAMPLED;
  236.         FullySamplePixel(x, line, &data->pix[x], &data->samp[x]);
  237.     }
  238. }
  239.  
  240. void
  241. FullySamplePixel(xp, yp, pix, prevsamp)
  242. int xp, yp;
  243. Pixel *pix;
  244. int *prevsamp;
  245. {
  246.     Float upos, vpos, u, v;
  247.     int x, y, sampnum;
  248.     Pixel ctmp;
  249.  
  250.     if (*prevsamp == SUPERSAMPLED)
  251.         return;    /* already done */
  252.  
  253.     Stats.SuperSampled++;
  254.     if (*prevsamp == UNSAMPLED) {
  255.         /*
  256.          * No previous sample; initialize to black.
  257.          */
  258.         pix->r = pix->g = pix->b = pix->alpha = 0.;
  259.     } else {
  260.         if (Sampling.sidesamples == 1) {
  261.             *prevsamp = SUPERSAMPLED;
  262.             return;
  263.         }
  264.         x = *prevsamp % Sampling.sidesamples;
  265.         y = *prevsamp / Sampling.sidesamples;
  266.         pix->r *= Sampling.filter[x][y];
  267.         pix->g *= Sampling.filter[x][y];
  268.         pix->b *= Sampling.filter[x][y];
  269.         pix->alpha *= Sampling.filter[x][y];
  270.     }
  271.  
  272.     sampnum = 0;
  273.     xp += Screen.minx;
  274.     vpos = Screen.miny + yp - 0.5*Sampling.filterwidth;
  275.     for (y = 0; y < Sampling.sidesamples; y++,
  276.          vpos += Sampling.filterdelta) {
  277.         upos = xp - 0.5*Sampling.filterwidth;
  278.         for (x = 0; x < Sampling.sidesamples; x++,
  279.              upos += Sampling.filterdelta) {
  280.             if (sampnum != *prevsamp) {
  281.                 if (Options.jitter) {
  282.                     u = upos + nrand()*Sampling.filterdelta;
  283.                     v = vpos + nrand()*Sampling.filterdelta;
  284.                 } else {
  285.                     u = upos;
  286.                     v = vpos;
  287.                 }
  288.                 TopRay.time = SampleTime(SampleNumbers[sampnum]);
  289.                 SampleScreen(u, v, &TopRay, &ctmp,
  290.                     SampleNumbers[sampnum]);
  291.                 pix->r += ctmp.r*Sampling.filter[x][y];
  292.                 pix->g += ctmp.g*Sampling.filter[x][y];
  293.                 pix->b += ctmp.b*Sampling.filter[x][y];
  294.                 pix->alpha += ctmp.alpha*Sampling.filter[x][y];
  295.             }
  296.             if (++sampnum == Sampling.totsamples)
  297.                 sampnum = 0;
  298.         }
  299.     }
  300.  
  301.     if (Options.samplemap)
  302.         pix->alpha = 255;
  303.  
  304.     *prevsamp = SUPERSAMPLED;
  305. }
  306.  
  307. void
  308. AdaptiveRefineScanline(y, scan0, scan1, scan2)
  309. int y;
  310. Scanline *scan0, *scan1, *scan2;
  311. {
  312.     int x, done;
  313.  
  314.     /*
  315.      * Walk down scan1, looking at 4-neighbors for excessive contrast.
  316.      * If found, supersample *all* neighbors not already supersampled.
  317.      * The process is repeated until either there are no
  318.      * high-contrast regions or all such regions are already supersampled.
  319.      */
  320.  
  321.     do {
  322.         done = TRUE;
  323.         for (x = 1; x < Screen.xsize -1; x++) {
  324.             /*
  325.               * Find min and max RGB for area we care about
  326.              */
  327.             if (ExcessiveContrast(x, scan0->pix, scan1->pix,
  328.                 scan2->pix)) {
  329.                 if (scan1->samp[x-1] != SUPERSAMPLED) {
  330.                     done = FALSE;
  331.                     FullySamplePixel(x-1, y,
  332.                         &scan1->pix[x-1],
  333.                         &scan1->samp[x-1]);
  334.                 }
  335.                 if (scan0->samp[x] != SUPERSAMPLED) {
  336.                     done = FALSE;
  337.                     FullySamplePixel(x, y-1,
  338.                         &scan0->pix[x],
  339.                         &scan0->samp[x]);
  340.                 }
  341.                 if (scan1->samp[x+1] != SUPERSAMPLED) {
  342.                     done = FALSE;
  343.                     FullySamplePixel(x+1, y,
  344.                         &scan1->pix[x+1],
  345.                         &scan1->samp[x+1]);
  346.                 }
  347.                 if (scan2->samp[x] != SUPERSAMPLED) {
  348.                     done = FALSE;
  349.                     FullySamplePixel(x, y+1,
  350.                         &scan2->pix[x],
  351.                         &scan2->samp[x]);
  352.                 }
  353.                 if (scan1->samp[x] != SUPERSAMPLED) {
  354.                     done = FALSE;
  355.                     FullySamplePixel(x, y,
  356.                         &scan1->pix[x],
  357.                         &scan1->samp[x]);
  358.                 }
  359.             }
  360.         }
  361.     } while (!done);
  362. }
  363.  
  364. static int
  365. ExcessiveContrast(x, pix0, pix1, pix2)
  366. int x;
  367. Pixel *pix0, *pix1, *pix2;
  368. {
  369.     Float mini, maxi, sum, diff;
  370.  
  371.     maxi = max(pix0[x].r, pix1[x-1].r);
  372.     if (pix1[x].r > maxi) maxi = pix1[x].r;
  373.     if (pix1[x+1].r > maxi) maxi = pix1[x+1].r;
  374.     if (pix2[x].r > maxi) maxi = pix2[x].r;
  375.  
  376.     mini = min(pix0[x].r, pix1[x-1].r);
  377.     if (pix1[x].r < mini) mini = pix1[x].r;
  378.     if (pix1[x+1].r < mini) mini = pix1[x+1].r;
  379.     if (pix2[x].r < mini) mini = pix2[x].r;
  380.  
  381.     diff = maxi - mini;
  382.     sum = maxi + mini;
  383.     if (sum > EPSILON && diff/sum > Options.contrast.r)
  384.         return TRUE;
  385.  
  386.     maxi = max(pix0[x].g, pix1[x-1].g);
  387.     if (pix1[x].g > maxi) maxi = pix1[x].g;
  388.     if (pix1[x+1].g > maxi) maxi = pix1[x+1].g;
  389.     if (pix2[x].g > maxi) maxi = pix2[x].g;
  390.  
  391.     mini = min(pix0[x].g, pix1[x-1].g);
  392.     if (pix1[x].g < mini) mini = pix1[x].g;
  393.     if (pix1[x+1].g < mini) mini = pix1[x+1].g;
  394.     if (pix2[x].g < mini) mini = pix2[x].g;
  395.  
  396.     diff = maxi - mini;
  397.     sum = maxi + mini;
  398.  
  399.     if (sum > EPSILON && diff/sum > Options.contrast.g)
  400.         return TRUE;
  401.  
  402.     maxi = max(pix0[x].b, pix1[x-1].b);
  403.     if (pix1[x].b > maxi) maxi = pix1[x].b;
  404.     if (pix1[x+1].b > maxi) maxi = pix1[x+1].b;
  405.     if (pix2[x].b > maxi) maxi = pix2[x].b;
  406.  
  407.     mini = min(pix0[x].b, pix1[x-1].b);
  408.     if (pix1[x].b < mini) mini = pix1[x].b;
  409.     if (pix1[x+1].b < mini) mini = pix1[x+1].b;
  410.     if (pix2[x].b < mini) mini = pix2[x].b;
  411.  
  412.     diff = maxi - mini;
  413.     sum = maxi + mini;
  414.     if (sum > EPSILON && diff/sum > Options.contrast.b)
  415.         return TRUE;
  416.  
  417.     return FALSE;
  418. }
  419.  
  420. Float
  421. SampleTime(sampnum)
  422. int sampnum;
  423. {
  424.     Float window, jitter = 0.0, res;
  425.  
  426.     if (Options.shutterspeed <= 0.)
  427.         return Options.framestart;
  428.     if (Options.jitter)
  429.         jitter = nrand();
  430.     window = Options.shutterspeed / Sampling.totsamples;
  431.     res = Options.framestart + window * (sampnum + jitter);
  432.     TimeSet(res);
  433.     return res;
  434. }
  435.  
  436. static void
  437. RaytraceInit()
  438. {
  439.  
  440.     switch (Sampling.sidesamples) {
  441.         case 1:
  442.             SampleNumbers = OneSample;
  443.             break;
  444.         case 2:
  445.             SampleNumbers = TwoSamples;
  446.             break;
  447.         case 3:
  448.             SampleNumbers = ThreeSamples;
  449.             break;
  450.         case 4:
  451.             SampleNumbers = FourSamples;
  452.             break;
  453.         case 5:
  454.             SampleNumbers = FiveSamples;
  455.             break;
  456.         case 6:
  457.             SampleNumbers = SixSamples;
  458.             break;
  459.         case 7:
  460.             SampleNumbers = SevenSamples;
  461.             break;
  462.         case 8:
  463.             SampleNumbers = EightSamples;
  464.             break;
  465.         default:
  466. /*
  467. #if defined(__WATCOMC__) || defined(__BORLANDC__)
  468.             RLerror(RL_PANIC,
  469.                 "Only 3-8 rays/pixel not supported.","","","");
  470. #else
  471. */
  472.             RLerror(RL_PANIC,
  473.                 "Sorry, %d rays/pixel not supported.\n",
  474.                     Sampling.totsamples,"","");
  475. /*#endif
  476. */
  477.     }
  478.  
  479.     /*
  480.      * Allocate pixel arrays and arrays to store sampling info.
  481.      */
  482.     scan0.pix = (Pixel *)RayMalloc(Screen.xsize * sizeof(Pixel));
  483.     scan1.pix = (Pixel *)RayMalloc(Screen.xsize * sizeof(Pixel));
  484.     scan2.pix = (Pixel *)RayMalloc(Screen.xsize * sizeof(Pixel));
  485.  
  486.     scan0.samp = (int *)RayMalloc(Screen.xsize * sizeof(int));
  487.     scan1.samp = (int *)RayMalloc(Screen.xsize * sizeof(int));
  488.     scan2.samp = (int *)RayMalloc(Screen.xsize * sizeof(int));
  489. }
  490.