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