home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / raytrace / rayshade / src / grid.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-09  |  12.0 KB  |  500 lines
  1. /*
  2.  * grid.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: grid.c,v 4.0.1.1 91/10/04 15:55:37 cek Exp Locker: cek $
  17.  *
  18.  * $Log:    grid.c,v $
  19.  * Revision 4.0.1.1  91/10/04  15:55:37  cek
  20.  * patch1: Removed straight floating point comparisons.
  21.  * 
  22.  * Revision 4.0  91/07/17  14:38:02  kolb
  23.  * Initial version.
  24.  * 
  25.  */
  26. #include "geom.h"
  27. #include "grid.h"
  28.  
  29. static Methods *iGridMethods = NULL;
  30. static char gridName[] = "grid";
  31.  
  32. static unsigned long raynumber = 1;        /* Current "ray number". */
  33.                         /* (should be "grid number") */
  34. static void engrid(), GridFreeVoxels();
  35. static int pos2grid(), CheckVoxel();
  36.  
  37. Grid *
  38. GridCreate(x, y, z)
  39. int x, y, z;
  40. {
  41.     Grid *grid;
  42.  
  43.     if (x < 1 || y < 1 || z < 1) {
  44.         RLerror(RL_WARN, "Invalid grid specification.\n");
  45.         return (Grid *)NULL;
  46.     }
  47.     grid = (Grid *)share_calloc(1, sizeof(Grid));
  48.     grid->xsize = x;
  49.     grid->ysize = y;
  50.     grid->zsize = z;
  51.     return grid;    
  52. }
  53.  
  54. char *
  55. GridName()
  56. {
  57.     return gridName;
  58. }
  59.  
  60. /*
  61.  * Intersect ray with grid, returning distance from "pos" to
  62.  * nearest intersection with an object in the grid.  Returns 0.
  63.  * if no intersection.
  64.  */
  65. int
  66. GridIntersect(grid, ray, hitlist, mindist, maxdist)
  67. Grid *grid;
  68. Ray *ray;
  69. HitList *hitlist;
  70. Float mindist, *maxdist;
  71. {
  72.     GeomList *list;
  73.     Geom *obj;
  74.     int hit;
  75.     Float offset, tMaxX, tMaxY, tMaxZ;
  76.     Float tDeltaX, tDeltaY, tDeltaZ, *raybounds[2][3];
  77.     int stepX, stepY, stepZ, outX, outY, outZ, x, y, z;
  78.     Vector curpos, nXp, nYp, nZp, np, pDeltaX, pDeltaY, pDeltaZ;
  79.     unsigned long counter;
  80.  
  81.     hit = FALSE;
  82.     /*
  83.      * Check unbounded objects.
  84.      */
  85.     for (obj = grid->unbounded ; obj; obj = obj->next) {
  86.         if (intersect(obj, ray, hitlist, mindist, maxdist))
  87.             hit = TRUE;
  88.     }
  89.  
  90.     /*
  91.      * If outside of the bounding box, check to see if we
  92.      * hit it.
  93.      */
  94.     VecAddScaled(ray->pos, mindist, ray->dir, &curpos);
  95.     if (OutOfBounds(&curpos, grid->bounds)) {
  96.         offset = *maxdist;
  97.         if (!BoundsIntersect(ray, grid->bounds, mindist, &offset))
  98.             /*
  99.              * Ray never hit grid space.
  100.              */
  101.             return hit;
  102.         /*
  103.          * else
  104.          *    The ray enters voxel space before it hits
  105.          *     an unbounded object.
  106.          */
  107.         VecAddScaled(ray->pos, offset, ray->dir, &curpos);
  108.     } else
  109.         offset = mindist;
  110.  
  111.     counter = raynumber++;
  112.  
  113.     /*
  114.      * tMaxX is the absolute distance from the ray origin we must move
  115.      *        to get to the next voxel in the X
  116.      *        direction.  It is incrementally updated
  117.      *         by DDA as we move from voxel-to-voxel.
  118.      * tDeltaX is the relative amount along the ray we move to
  119.      *        get to the next voxel in the X direction. Thus,
  120.      *        when we decide to move in the X direction,
  121.      *         we increment tMaxX by tDeltaX.
  122.      */
  123.     x = x2voxel(grid, curpos.x);
  124.     if (x == grid->xsize)
  125.         x--;
  126.     if (fabs(ray->dir.x) < EPSILON) {
  127.         tMaxX = FAR_AWAY;
  128.         raybounds[LOW][X] = &curpos.x;
  129.         raybounds[HIGH][X] = &np.x;
  130.         tDeltaX = 0.;
  131.     } else if (ray->dir.x < 0.) {
  132.         tMaxX = offset + (voxel2x(grid, x) - curpos.x) / ray->dir.x;
  133.         tDeltaX = grid->voxsize[X] / - ray->dir.x;
  134.         stepX = outX = -1;
  135.         raybounds[LOW][X] = &np.x;
  136.         raybounds[HIGH][X] = &curpos.x;
  137.     } else {
  138.         tMaxX = offset + (voxel2x(grid, x+1) - curpos.x) / ray->dir.x;
  139.         tDeltaX = grid->voxsize[X] / ray->dir.x;
  140.         stepX = 1;
  141.         outX = grid->xsize;
  142.         raybounds[LOW][X] = &curpos.x;
  143.         raybounds[HIGH][X] = &np.x;
  144.     }
  145.  
  146.     y = y2voxel(grid, curpos.y);
  147.     if (y == grid->ysize)
  148.         y--;
  149.  
  150.     if (fabs(ray->dir.y) < EPSILON) {
  151.         tMaxY = FAR_AWAY;
  152.         raybounds[LOW][Y] = &curpos.y;
  153.         raybounds[HIGH][Y] = &np.y;
  154.         tDeltaY = 0.;
  155.     } else if (ray->dir.y < 0.) {
  156.         tMaxY = offset + (voxel2y(grid, y) - curpos.y) / ray->dir.y;
  157.         tDeltaY = grid->voxsize[Y] / - ray->dir.y;
  158.         stepY = outY = -1;
  159.         raybounds[LOW][Y] = &np.y;
  160.         raybounds[HIGH][Y] = &curpos.y;
  161.     } else {
  162.         tMaxY = offset + (voxel2y(grid, y+1) - curpos.y) / ray->dir.y;
  163.         tDeltaY = grid->voxsize[Y] / ray->dir.y;
  164.         stepY = 1;
  165.         outY = grid->ysize;
  166.         raybounds[LOW][Y] = &curpos.y;
  167.         raybounds[HIGH][Y] = &np.y;
  168.     }
  169.  
  170.     z = z2voxel(grid, curpos.z);
  171.     if (z == grid->zsize)
  172.         z--;
  173.     if (fabs(ray->dir.z) < EPSILON) {
  174.         tMaxZ = FAR_AWAY;
  175.         raybounds[LOW][Z] = &curpos.z;
  176.         raybounds[HIGH][Z] = &np.z;
  177.         tDeltaZ = 0.;
  178.     } else if (ray->dir.z < 0.) {
  179.         tMaxZ = offset + (voxel2z(grid, z) - curpos.z) / ray->dir.z;
  180.         tDeltaZ = grid->voxsize[Z] / - ray->dir.z;
  181.         stepZ = outZ = -1;
  182.         raybounds[LOW][Z] = &np.z;
  183.         raybounds[HIGH][Z] = &curpos.z;
  184.     } else {
  185.         tMaxZ = offset + (voxel2z(grid, z+1) - curpos.z) / ray->dir.z;
  186.         tDeltaZ = grid->voxsize[Z] / ray->dir.z;
  187.         stepZ = 1;
  188.         outZ = grid->zsize;
  189.         raybounds[LOW][Z] = &curpos.z;
  190.         raybounds[HIGH][Z] = &np.z;
  191.     }
  192.  
  193.     VecScale(tDeltaX, ray->dir, &pDeltaX);
  194.     VecScale(tDeltaY, ray->dir, &pDeltaY);
  195.     VecScale(tDeltaZ, ray->dir, &pDeltaZ);
  196.  
  197.     VecAddScaled(ray->pos, tMaxX, ray->dir, &nXp);
  198.     VecAddScaled(ray->pos, tMaxY, ray->dir, &nYp);
  199.     VecAddScaled(ray->pos, tMaxZ, ray->dir, &nZp);
  200.  
  201.     while (TRUE) {
  202.         list = grid->cells[x][y][z];
  203.         if (tMaxX < tMaxY && tMaxX < tMaxZ) {
  204.             if (list) {
  205.                 np = nXp;
  206.                     if (CheckVoxel(list,ray,raybounds,
  207.                         hitlist,counter,offset,maxdist))
  208.                     hit = TRUE;
  209.             }
  210.             x += stepX;
  211.             if (*maxdist < tMaxX || x == outX)
  212.                 break;
  213.             tMaxX += tDeltaX;
  214.             curpos = nXp;
  215.             nXp.x += pDeltaX.x;
  216.             nXp.y += pDeltaX.y;
  217.             nXp.z += pDeltaX.z;
  218.         } else if (tMaxZ < tMaxY) {
  219.             if (list) {
  220.                 np = nZp;
  221.                     if (CheckVoxel(list,ray, raybounds,
  222.                         hitlist,counter,offset,maxdist))
  223.                     hit = TRUE;
  224.             }
  225.             z += stepZ;
  226.             if (*maxdist < tMaxZ || z == outZ)
  227.                 break;
  228.             tMaxZ += tDeltaZ;
  229.             curpos = nZp;
  230.             nZp.x += pDeltaZ.x;
  231.             nZp.y += pDeltaZ.y;
  232.             nZp.z += pDeltaZ.z;
  233.         } else {
  234.             if (list) {
  235.                 np = nYp;
  236.                     if (CheckVoxel(list,ray,raybounds,
  237.                         hitlist,counter,offset,maxdist))
  238.                     hit = TRUE;
  239.             }
  240.             y += stepY;
  241.             if (*maxdist < tMaxY || y == outY)
  242.                 break;
  243.             tMaxY += tDeltaY;
  244.             curpos = nYp;
  245.             nYp.x += pDeltaY.x;
  246.             nYp.y += pDeltaY.y;
  247.             nYp.z += pDeltaY.z;
  248.         }
  249.     }
  250.     return hit;
  251. }
  252.  
  253. /*
  254.  * Intersect ray with objects in grid cell.  Note that there are a many ways
  255.  * to speed up this routine, all of which uglify the code to a large extent.
  256.  */
  257. static int
  258. CheckVoxel(list,ray,raybounds,hitlist,counter,mindist,maxdist)
  259. GeomList *list;
  260. Ray *ray;
  261. Float *raybounds[2][3];
  262. HitList *hitlist;
  263. unsigned long counter;
  264. Float mindist, *maxdist;
  265. {
  266.     Geom *obj;
  267.     int hit;
  268.     Float lx, hx, ly, hy, lz, hz;
  269.  
  270.     lx = *raybounds[LOW][X];
  271.     hx = *raybounds[HIGH][X];
  272.     ly = *raybounds[LOW][Y];
  273.     hy = *raybounds[HIGH][Y];
  274.     lz = *raybounds[LOW][Z];
  275.     hz = *raybounds[HIGH][Z];
  276.  
  277.     hit = FALSE;
  278.  
  279.     do {
  280.         obj = list->obj;
  281.         /*
  282.          * If object's counter is greater than or equal to the
  283.          * number associated with the current grid,
  284.          * don't bother checking again.  In addition, if the
  285.          * bounding box of the ray's extent in the voxel does
  286.          * not intersect the bounding box of the object, don't bother.
  287.          */
  288. #ifdef SHAREDMEM
  289.         if (*obj->counter < counter &&
  290. #else
  291.         if (obj->counter < counter &&
  292. #endif
  293.             obj->bounds[LOW][X] <= hx  &&
  294.             obj->bounds[HIGH][X] >= lx &&
  295.             obj->bounds[LOW][Y] <= hy  &&
  296.             obj->bounds[HIGH][Y] >= ly &&
  297.             obj->bounds[LOW][Z] <= hz  &&
  298.             obj->bounds[HIGH][Z] >= lz) {
  299. #ifdef SHAREDMEM
  300.             *obj->counter = counter;
  301. #else
  302.             obj->counter = counter;
  303. #endif
  304.             if (intersect(obj, ray, hitlist, mindist, maxdist))
  305.                 hit = TRUE;
  306.         }
  307.     } while ((list = list->next) != (GeomList *)0);
  308.  
  309.     return hit;
  310. }
  311.  
  312. int
  313. GridConvert(grid, objlist)
  314. Grid *grid;
  315. Geom *objlist;
  316. {
  317.     int num;
  318.  
  319.     /*
  320.      * Keep linked list of all bounded objects in grid; it may come
  321.      * in handy.
  322.      */
  323.     grid->objects = objlist;
  324.     for (num = 0; objlist; objlist = objlist->next)
  325.         num += objlist->prims;
  326.  
  327.     return num;
  328. }
  329.  
  330. void
  331. GridBounds(grid, bounds)
  332. Grid *grid;
  333. Float bounds[2][3];
  334. {
  335.     Geom *obj, *ltmp;
  336.     int x, y, i;
  337.  
  338.     BoundsInit(bounds);
  339.     /*
  340.      * For each object on the list,
  341.      * compute its bounds...
  342.      */
  343.     /*
  344.      * Find bounding box of bounded objects and get list of
  345.      * unbounded objects.
  346.      */
  347.     grid->unbounded = GeomComputeAggregateBounds(&grid->objects,
  348.                 grid->unbounded, grid->bounds);
  349.  
  350.     BoundsCopy(grid->bounds, bounds);
  351.  
  352.     grid->voxsize[X] = (grid->bounds[HIGH][X]-grid->bounds[LOW][X])/
  353.                 grid->xsize;
  354.     grid->voxsize[Y] = (grid->bounds[HIGH][Y]-grid->bounds[LOW][Y])/
  355.                 grid->ysize;
  356.     grid->voxsize[Z] = (grid->bounds[HIGH][Z]-grid->bounds[LOW][Z])/
  357.                 grid->zsize;
  358.  
  359.     if (grid->cells == (GeomList ****)NULL) {
  360.         /*
  361.           * Allocate voxels.
  362.           */
  363.         grid->cells = (GeomList ****)share_malloc(grid->xsize *
  364.                     sizeof(GeomList ***));
  365.         for (x = 0; x < grid->xsize; x++) {
  366.             grid->cells[x] = (GeomList ***)share_malloc(grid->ysize *
  367.                 sizeof(GeomList **));
  368.             for (y = 0; y < grid->ysize; y++)
  369.                 grid->cells[x][y] = (GeomList **)share_calloc(
  370.                     (unsigned)grid->zsize,sizeof(GeomList *));
  371.         }
  372.     } else {
  373.         /*
  374.          * New frame...
  375.          * Free up the objlists in each voxel.
  376.          */
  377.         GridFreeVoxels(grid);
  378.     }
  379.  
  380.     /*
  381.      * objlist now holds a linked list of bounded objects.
  382.      */
  383.     for (ltmp = grid->objects; ltmp != (Geom *)0; ltmp = ltmp->next)
  384.         engrid(ltmp, grid);
  385. }
  386.  
  387. static void
  388. GridFreeVoxels(grid)
  389. Grid *grid;
  390. {
  391.     int x, y, z;
  392.     GeomList *cell, *next;
  393.  
  394.     for (x = 0; x < grid->xsize; x++) {
  395.         for (y = 0; y < grid->ysize; y++) {
  396.             for (z = 0; z < grid->zsize; z++) {
  397.                 for (cell = grid->cells[x][y][z]; cell; cell = next) {
  398.                     next = cell->next;
  399.                     free((voidstar)cell);
  400.                 }
  401.                 grid->cells[x][y][z] = (GeomList *)NULL;
  402.             }
  403.         }
  404.     }
  405. }
  406.  
  407. Methods *
  408. GridMethods()
  409. {
  410.     if (iGridMethods == (Methods *)NULL) {
  411.         iGridMethods = MethodsCreate();
  412.         iGridMethods->methods = GridMethods;
  413.         iGridMethods->create = (GeomCreateFunc *)GridCreate;
  414.         iGridMethods->intersect = GridIntersect;
  415.         iGridMethods->name = GridName;
  416.         iGridMethods->convert = GridConvert;
  417.         iGridMethods->bounds = GridBounds;
  418.         iGridMethods->checkbounds = FALSE;
  419.         iGridMethods->closed = TRUE;
  420.     }
  421.     return iGridMethods;
  422. }
  423.  
  424. /*
  425.  * Place an object in a grid.
  426.  */
  427. static void
  428. engrid(obj, grid)
  429. Geom *obj;
  430. Grid *grid;
  431. {
  432.     int x, y, z, low[3], high[3];
  433.     GeomList *ltmp;
  434.  
  435.     /*
  436.      * This routine should *never* be passed an unbounded object, but...
  437.      */
  438.     if (!pos2grid(grid, obj->bounds[LOW], low) ||
  439.         !pos2grid(grid, obj->bounds[HIGH], high) ||
  440.         obj->bounds[LOW][X] > obj->bounds[HIGH][X]) {
  441.         /*
  442.          * Geom is partially on wholly outside of
  443.          * grid -- this should never happen, but just
  444.          * in case...
  445.          */
  446.         RLerror(RL_ABORT, "Engrid got an unbounded object?!\n");
  447.         return;
  448.         }
  449.  
  450.     /*
  451.      * For each voxel that intersects the object's bounding
  452.      * box, add pointer to this object to voxel's linked list.
  453.       */
  454.     for (x = low[X]; x <= high[X]; x++) {
  455.         for (y = low[Y]; y <= high[Y]; y++) {
  456.             for (z = low[Z]; z <= high[Z]; z++) {
  457.                 ltmp = (GeomList *)share_malloc(sizeof(GeomList));
  458.                 ltmp->obj = obj;
  459.                 ltmp->next = grid->cells[x][y][z];
  460.                 grid->cells[x][y][z] = ltmp;
  461.             }
  462.         }
  463.     }
  464. }
  465.  
  466. /*
  467.  * Convert 3D point to index into grid's voxels.
  468.  */
  469. static int
  470. pos2grid(grid, pos, index)
  471. Grid *grid;
  472. Float pos[3];
  473. int index[3];
  474. {
  475.     index[X] = (int)(x2voxel(grid, pos[0]));
  476.     index[Y] = (int)(y2voxel(grid, pos[1]));
  477.     index[Z] = (int)(z2voxel(grid, pos[2]));
  478.  
  479.     if (index[X] == grid->xsize)
  480.         index[X]--;
  481.     if (index[Y] == grid->ysize)
  482.         index[Y]--;
  483.     if (index[Z] == grid->zsize)
  484.         index[Z]--;
  485.  
  486.     if (index[X] < 0 || index[X] >= grid->xsize ||
  487.         index[Y] < 0 || index[Y] >= grid->ysize ||
  488.         index[Z] < 0 || index[Z] >= grid->zsize)
  489.         return FALSE;
  490.     return TRUE;
  491. }
  492.  
  493. void
  494. GridMethodRegister(meth)
  495. UserMethodType meth;
  496. {
  497.     if (iGridMethods)
  498.         iGridMethods->user = meth;
  499. }
  500.