home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / GRAPHICS / rayshade.lzh / grid.c < prev    next >
Text File  |  1990-05-08  |  10KB  |  361 lines
  1. /*
  2.  * grid.c
  3.  *
  4.  * Copyright (C) 1989, Craig E. Kolb
  5.  *
  6.  * This software may be freely copied, modified, and redistributed,
  7.  * provided that this copyright notice is preserved on all copies.
  8.  *
  9.  * There is no warranty or other guarantee of fitness for this software,
  10.  * it is provided solely .  Bug reports or fixes may be sent
  11.  * to the author, who may or may not act on them as he desires.
  12.  *
  13.  * You may not include this software in a program or other software product
  14.  * without supplying the source, or without informing the end-user that the
  15.  * source is available for no extra charge.
  16.  *
  17.  * If you modify this software, you should include a notice giving the
  18.  * name of the person performing the modification, the date of modification,
  19.  * and the reason for such modification.
  20.  *
  21.  * $Id: grid.c,v 3.0.1.1 90/02/12 13:16:36 craig Exp $
  22.  *
  23.  * $Log:    grid.c,v $
  24.  * Revision 3.0.1.1  90/02/12  13:16:36  craig
  25.  * patch4: Changed obj->counter to pointer when SHAREDMEM is defined.
  26.  * 
  27.  * Revision 3.0  89/10/27  02:05:50  craig
  28.  * Baseline for first official release.
  29.  * 
  30.  */
  31. #include <stdio.h>
  32. #include "constants.h"
  33. #include "typedefs.h"
  34. #include "funcdefs.h"
  35.  
  36. extern double CheckVoxel(), intersect();
  37. unsigned long    raynumber = 1;        /* Current "ray number". */
  38.                     /* (should be "grid number") */
  39. /*
  40.  * Intersect ray with grid, returning distance from "pos" to
  41.  * nearest intersection with an object in the grid.  Returns 0.
  42.  * if no intersection.
  43.  */
  44. double
  45. int_grid(grid, source, ray, hitinfo)
  46. Grid *grid;
  47. Primitive *source;
  48. Ray *ray;
  49. HitInfo *hitinfo;
  50. {
  51.     ObjList *list;
  52.     Object *tmpobj;
  53.     double dist, mindist, offset, tMaxX, tMaxY, tMaxZ;
  54.     double tDeltaX, tDeltaY, tDeltaZ, *raybounds[2][3];
  55.     int stepX, stepY, stepZ, outX, outY, outZ, x, y, z;
  56.     HitInfo infotmp;
  57.     Vector curpos, nXp, nYp, nZp, np, pDeltaX, pDeltaY, pDeltaZ;
  58.     unsigned long counter;
  59.  
  60.     mindist = FAR_AWAY;
  61.  
  62.     /*
  63.      * The "raynumber" scheme prevents us from performing unnecessary
  64.      * ray/object intersection tests. Since an object may span more than
  65.      * one voxel, it is possible that such an object will be tested more
  66.      * than once as we move from voxel-to-voxel. The idea here is to
  67.      * increment "raynumber" once when we begin a ray/grid intersection
  68.      * test. Whenever we check for intersection with an object in
  69.      * the grid, we assign that object's "counter" field the current value
  70.      * of "raynumber".  On subsequent calls to CheckVoxel, if the object's
  71.      * "counter" is greater than or equal to the value "raynumber" had
  72.      * when we started tracing the current grid, we know that we've already
  73.      * checked that object.  This isn't as straight-forward as one
  74.      * might think due to instantiation -- one may have several
  75.      * instances of the same object in a grid.  By incrementing raynumber
  76.      * whenever we being a new ray/grid int. test, we guarantee that
  77.      * we will check for intersection with the objects in the grid
  78.      * at most once.
  79.      */
  80.     infotmp.totaltrans = hitinfo->totaltrans;
  81.     /*
  82.      * Check unbounded objects.
  83.      */
  84.     for (list = grid->unbounded ; list; list = list->next) {
  85.         tmpobj = list->data;
  86.         dist = intersect(tmpobj, source, ray, &infotmp);
  87.         if (dist > 0. && dist < mindist) {
  88.             *hitinfo = infotmp;
  89.             mindist = dist;
  90.         }
  91.     }
  92.  
  93.     /*
  94.      * If outside of the bounding box, check to see if we
  95.      * hit it.
  96.      */
  97.     if (OutOfBounds(&ray->pos, grid->bounds)) {
  98.         offset = IntBounds(ray, grid->bounds);
  99.         if (offset <= 0.)
  100.             /*
  101.              * Ray never hit grid space.
  102.              */
  103.             return (mindist == FAR_AWAY ? 0. : mindist);
  104.         else if (mindist < offset)
  105.             /*
  106.              * Hit an unbounded object closer than grid.
  107.              */
  108.             return mindist;
  109.         /*
  110.          * else
  111.          *    The ray enters voxels space before it hits
  112.          *     an unbounded object.
  113.          */
  114.         addscaledvec(ray->pos, offset, ray->dir, &curpos);
  115.     } else {
  116.         offset = 0.;
  117.         curpos = ray->pos;
  118.     }
  119.  
  120.     counter = raynumber++;
  121.     /*
  122.      * Kludge:  Voxel space is mapped as [start, end),
  123.      * and we want it to be [start, end].
  124.      */
  125.     x = x2voxel(grid, curpos.x);
  126.     if (x == grid->xsize)
  127.         x = grid->xsize -1;
  128.     y = y2voxel(grid, curpos.y);
  129.     if (y == grid->ysize)
  130.         y = grid->ysize -1;
  131.     z = z2voxel(grid, curpos.z);
  132.     if (z == grid->zsize)
  133.         z = grid->zsize -1;
  134.  
  135.     /*
  136.      * tMaxX is the absolute distance from the ray origin we must move
  137.      *        to get to the next voxel in the X
  138.      *        direction.  It is incrementally updated
  139.      *         by DDA as we move from voxel-to-voxel.
  140.      * tDeltaX is the relative amount along the ray we move to
  141.      *        get to the next voxel in the X direction. Thus,
  142.      *        when we decide to move in the X direction,
  143.      *         we increment tMaxX by tDeltaX.
  144.      */
  145.     if (ray->dir.x < 0.) {
  146.         stepX = outX = -1;
  147.         tMaxX = (voxel2x(grid, x) - curpos.x) / ray->dir.x;
  148.         tDeltaX = grid->voxsize[X] / - ray->dir.x;
  149.         raybounds[LOW][X] = &np.x;
  150.         raybounds[HIGH][X] = &curpos.x;
  151.     } else if (ray->dir.x > 0.) {
  152.         stepX = 1;
  153.         outX = grid->xsize;
  154.         tMaxX = (voxel2x(grid, x+1) - curpos.x) / ray->dir.x;
  155.         tDeltaX = grid->voxsize[X] / ray->dir.x;
  156.         raybounds[LOW][X] = &curpos.x;
  157.         raybounds[HIGH][X] = &np.x;
  158.     } else {
  159.         tMaxX = FAR_AWAY;
  160.         raybounds[LOW][X] = &curpos.x;
  161.         raybounds[HIGH][X] = &np.x;
  162.         tDeltaX = 0.;
  163.     }
  164.  
  165.     if (ray->dir.y < 0.) {
  166.         stepY = outY = -1;
  167.         tMaxY = (voxel2y(grid, y) - curpos.y) / ray->dir.y;
  168.         tDeltaY = grid->voxsize[Y] / - ray->dir.y;
  169.         raybounds[LOW][Y] = &np.y;
  170.         raybounds[HIGH][Y] = &curpos.y;
  171.     } else if (ray->dir.y > 0.) {
  172.         stepY = 1;
  173.         outY = grid->ysize;
  174.         tMaxY = (voxel2y(grid, y+1) - curpos.y) / ray->dir.y;
  175.         tDeltaY = grid->voxsize[Y] / ray->dir.y;
  176.         raybounds[LOW][Y] = &curpos.y;
  177.         raybounds[HIGH][Y] = &np.y;
  178.     } else {
  179.         tMaxY = FAR_AWAY;
  180.         raybounds[LOW][Y] = &curpos.y;
  181.         raybounds[HIGH][Y] = &np.y;
  182.         tDeltaY = 0.;
  183.     }
  184.  
  185.     if (ray->dir.z < 0.) {
  186.         stepZ = outZ = -1;
  187.         tMaxZ = (voxel2z(grid, z) - curpos.z) / ray->dir.z;
  188.         tDeltaZ = grid->voxsize[Z] / - ray->dir.z;
  189.         raybounds[LOW][Z] = &np.z;
  190.         raybounds[HIGH][Z] = &curpos.z;
  191.     } else if (ray->dir.z > 0.) {
  192.         stepZ = 1;
  193.         outZ = grid->zsize;
  194.         tMaxZ = (voxel2z(grid, z+1) - curpos.z) / ray->dir.z;
  195.         tDeltaZ = grid->voxsize[Z] / ray->dir.z;
  196.         raybounds[LOW][Z] = &curpos.z;
  197.         raybounds[HIGH][Z] = &np.z;
  198.     } else {
  199.         tMaxZ = FAR_AWAY;
  200.         raybounds[LOW][Z] = &curpos.z;
  201.         raybounds[HIGH][Z] = &np.z;
  202.         tDeltaZ = 0.;
  203.     }
  204.  
  205.     /*
  206.      * We've already moved from the ray origin along the ray to "hitpoint"
  207.      * by "offset" units in order to reach the grid.
  208.      */
  209.     tMaxX += offset;
  210.     tMaxY += offset;
  211.     tMaxZ += offset;
  212.  
  213.     pDeltaX.x = tDeltaX * ray->dir.x;
  214.     pDeltaX.y = tDeltaX * ray->dir.y;
  215.     pDeltaX.z = tDeltaX * ray->dir.z;
  216.     pDeltaY.x = tDeltaY * ray->dir.x;
  217.     pDeltaY.y = tDeltaY * ray->dir.y;
  218.     pDeltaY.z = tDeltaY * ray->dir.z;
  219.     pDeltaZ.x = tDeltaZ * ray->dir.x;
  220.     pDeltaZ.y = tDeltaZ * ray->dir.y;
  221.     pDeltaZ.z = tDeltaZ * ray->dir.z;
  222.  
  223.     nXp.x = ray->pos.x + tMaxX * ray->dir.x;
  224.     nXp.y = ray->pos.y + tMaxX * ray->dir.y;
  225.     nXp.z = ray->pos.z + tMaxX * ray->dir.z;
  226.     nYp.x = ray->pos.x + tMaxY * ray->dir.x;
  227.     nYp.y = ray->pos.y + tMaxY * ray->dir.y;
  228.     nYp.z = ray->pos.z + tMaxY * ray->dir.z;
  229.     nZp.x = ray->pos.x + tMaxZ * ray->dir.x;
  230.     nZp.y = ray->pos.y + tMaxZ * ray->dir.y;
  231.     nZp.z = ray->pos.z + tMaxZ * ray->dir.z;
  232.  
  233.     while (1) {
  234.         if (tMaxX < tMaxY) {
  235.             if (tMaxX < tMaxZ) {
  236.                 np = nXp;
  237.                 if ((list = grid->cells[x][y][z]))
  238.                     mindist = CheckVoxel(list,source,ray,
  239.                     raybounds,hitinfo,counter,mindist);
  240.                 x += stepX;
  241.                 if (mindist < tMaxX || x == outX)
  242.                     break;
  243.                 tMaxX += tDeltaX;
  244.                 curpos = nXp;
  245.                 nXp.x += pDeltaX.x;
  246.                 nXp.y += pDeltaX.y;
  247.                 nXp.z += pDeltaX.z;
  248.             } else {
  249.                 np = nZp;
  250.                 if ((list = grid->cells[x][y][z]))
  251.                     mindist = CheckVoxel(list,source,ray,
  252.                     raybounds, hitinfo,counter,mindist);
  253.                 z += stepZ;
  254.                 if (mindist < tMaxZ || z == outZ)
  255.                     break;
  256.                 tMaxZ += tDeltaZ;
  257.                 curpos = nZp;
  258.                 nZp.x += pDeltaZ.x;
  259.                 nZp.y += pDeltaZ.y;
  260.                 nZp.z += pDeltaZ.z;
  261.             }
  262.         } else {
  263.             if (tMaxY < tMaxZ) {
  264.                 np = nYp;
  265.                 if ((list = grid->cells[x][y][z]))
  266.                     mindist = CheckVoxel(list,source,ray,
  267.                     raybounds,hitinfo,counter,mindist);
  268.                 y += stepY;
  269.                 if (mindist < tMaxY || y == outY)
  270.                     break;
  271.                 tMaxY += tDeltaY;
  272.                 curpos = nYp;
  273.                 nYp.x += pDeltaY.x;
  274.                 nYp.y += pDeltaY.y;
  275.                 nYp.z += pDeltaY.z;
  276.             } else {
  277.                 np = nZp;
  278.                 if ((list = grid->cells[x][y][z]))
  279.                     mindist = CheckVoxel(list,source,ray,
  280.                     raybounds, hitinfo,counter,mindist);
  281.                 z += stepZ;
  282.                 if (mindist < tMaxZ || z == outZ)
  283.                     break;
  284.                 tMaxZ += tDeltaZ;
  285.                 curpos = nZp;
  286.                 nZp.x += pDeltaZ.x;
  287.                 nZp.y += pDeltaZ.y;
  288.                 nZp.z += pDeltaZ.z;
  289.             }
  290.         }
  291.  
  292.     }
  293.     if (mindist == FAR_AWAY)
  294.         return 0.;
  295.     return mindist;
  296.  
  297. }
  298.  
  299. /*
  300.  * Intersect ray with objects in grid cell.  Note that there are a many ways
  301.  * to speed up this routine, all of which uglify the code to a large extent.
  302.  */
  303. double
  304. CheckVoxel(list,source,ray,raybounds,hitinfo,counter,mindist)
  305. ObjList *list;
  306. Primitive *source;
  307. Ray *ray;
  308. double *raybounds[2][3];
  309. HitInfo *hitinfo;
  310. unsigned long counter;
  311. double mindist;
  312. {
  313.     Object *obj;
  314.     HitInfo tmpinfo;
  315.     double dist, lx, hx, ly, hy, lz, hz;
  316.  
  317.     tmpinfo.totaltrans = hitinfo->totaltrans;
  318.  
  319.     lx = *raybounds[LOW][X];
  320.     hx = *raybounds[HIGH][X];
  321.     ly = *raybounds[LOW][Y];
  322.     hy = *raybounds[HIGH][Y];
  323.     lz = *raybounds[LOW][Z];
  324.     hz = *raybounds[HIGH][Z];
  325.  
  326.     for (; list; list = list->next) {
  327.         obj = list->data;
  328.         /*
  329.          * If object's counter is greater than or equal to the
  330.          * number associated with the current grid,
  331.          * don't bother checking again.  In addition, if the
  332.          * bounding box of the ray's extent in the voxel does
  333.          * not intersect the bounding box of the object, don't bother.
  334.          */
  335. #ifdef SHAREDMEM
  336.         if (*obj->counter >= counter ||
  337. #else
  338.         if (obj->counter >= counter ||
  339. #endif
  340.             obj->bounds[LOW][X] > hx ||
  341.             obj->bounds[HIGH][X] < lx ||
  342.             obj->bounds[LOW][Y] > hy ||
  343.             obj->bounds[HIGH][Y] < ly ||
  344.             obj->bounds[LOW][Z] > hz ||
  345.             obj->bounds[HIGH][Z] < lz)
  346.             continue;
  347. #ifdef SHAREDMEM
  348.         *obj->counter = counter;
  349. #else
  350.         obj->counter = counter;
  351. #endif
  352.         dist = intersect(obj, source, ray, &tmpinfo);
  353.         if (dist > 0. && dist < mindist) {
  354.             *hitinfo = tmpinfo;
  355.             mindist = dist;
  356.         }
  357.     }
  358.  
  359.     return mindist;
  360. }
  361.