home *** CD-ROM | disk | FTP | other *** search
/ 3D Color Clip Art / 3D_Color_Clip_Art.bin / 3d-progs / rad386 / vox.c < prev    next >
Text File  |  1996-11-15  |  6KB  |  190 lines
  1. /*
  2.     Functions dealing with the voxels.
  3.     Voxels are spacially adjacent, and together form the total 
  4.     bounding volume of the scene.
  5.     Important of the functions is create_vlist.
  6.         Creates a list of voxels pierced by the ray along its path.
  7.         The list is ordered with piercing order as the ordering.
  8.         The routine has been developed in two phases.
  9.         Phase I : A brute force algorithm (but correct) was developed.
  10.               -------------- 10 April 1991.
  11.         Phase II : A 3d DDA being tested and subsequently abanodned.
  12.               -------------- 16 April 1991.
  13.         Phase III : A 3d DDA Adapted from RayShade of Yale Univ.
  14.               -------------- 24 April 1991.
  15.         As the codes for create_vlist and create_svlist are
  16.         the adapted versions of the 3d-dda code used in Rayshade
  17.         I am obliged to put the following copyright message.
  18.  
  19.         * Copyright (C) 1989, 1991, Craig E. Kolb
  20.          * All rights reserved.
  21.          *
  22.          * This software may be freely copied, modified, and
  23.         * redistributed
  24.          * provided that this copyright notice is preserved on
  25.         * all copies.
  26.          *
  27.          * You may not distribute this software, in whole or in 
  28.         * part, as part of
  29.          * any commercial product without the express consent of
  30.         * the original authours i.e. Craig E. Kolb.
  31.  
  32.     NOTE
  33.     ----
  34.     The bruteforce method and the working 3dDDA method give slightly
  35.     different output for the cases where the ray pieces exactly a voxel
  36.     corner or edge without actually entering the voxel. So they donot
  37.     create any problem.
  38. ------
  39. sumant
  40. */
  41. #include <stdio.h>
  42. #include <math.h>
  43. #include <malloc.h>
  44.  
  45. #include "GraphicsGems.h"
  46. #include "data_structure.h"
  47. #include "vox.h"
  48. #include "raddecl.h"
  49.  
  50. Vlist *create_vlist(ray_start,ray_direction,tmin,tmax)
  51. /*
  52.     Creates the list of voxels along the ray using 3dDDA.
  53.  
  54.     IMPORTANT
  55.     --------
  56.     'create_svlist' is a duplicate of this routine with slight
  57.     modification. So any change to this routine must be propagated to 
  58.     'create_svlist'.
  59. --------
  60. sumant 24-April-91
  61. */
  62. Point3 *ray_start;
  63. Vector3 *ray_direction;
  64. double tmin,tmax;
  65. {
  66.     Vlist *vlist=NULL;
  67.     int x,stepX,outX;
  68.     double tMaxX,tDeltaX;
  69.     int y,stepY,outY;
  70.     double tMaxY,tDeltaY;
  71.     int z,stepZ,outZ;
  72.     double tMaxZ,tDeltaZ;
  73.  
  74.     double t1;
  75.  
  76.     Point3 ray_entry,ray_exit;
  77.  
  78.     point_on_line(*ray_start,*ray_direction,tmin,ray_entry);
  79.     point_on_line(*ray_start,*ray_direction,tmax,ray_exit);
  80.  
  81.     x=x2voxel(volume_grid,ray_entry.x); if (x == volume_grid.x_subdivision) x--;
  82.     if (ray_direction->x < 0.){
  83.         tMaxX = tmin + (voxel2x(volume_grid,x)-ray_entry.x)/ray_direction->x;
  84.         tDeltaX =  volume_grid.voxel_size.x/(-ray_direction->x);
  85.         stepX = outX = -1;
  86.     }
  87.     else if (ray_direction->x > 0.){
  88.         tMaxX = tmin + (voxel2x(volume_grid,x+1)-ray_entry.x)/ray_direction->x;
  89.         tDeltaX =  volume_grid.voxel_size.x/ray_direction->x;
  90.         stepX = 1;
  91.         outX = volume_grid.x_subdivision;
  92.     }
  93.     else{
  94.         tMaxX=LARGE;
  95.         tDeltaX = 0.;
  96.     }
  97.  
  98.     y=y2voxel(volume_grid,ray_entry.y); if (y == volume_grid.y_subdivision) y--;
  99.     if (ray_direction->y < 0.){
  100.         tMaxY = tmin + (voxel2y(volume_grid,y)-ray_entry.y)/ray_direction->y;
  101.         tDeltaY =  volume_grid.voxel_size.y/(-ray_direction->y);
  102.         stepY = outY = -1;
  103.     }
  104.     else if (ray_direction->y > 0.){
  105.         tMaxY = tmin + (voxel2y(volume_grid,y+1)-ray_entry.y)/ray_direction->y;
  106.         tDeltaY =  volume_grid.voxel_size.y/ray_direction->y;
  107.         stepY = 1;
  108.         outY = volume_grid.y_subdivision;
  109.     }
  110.     else{
  111.         tMaxY=LARGE;
  112.         tDeltaY = 0.;
  113.     }
  114.  
  115.     z=z2voxel(volume_grid,ray_entry.z); if (z == volume_grid.z_subdivision) z--;
  116.     if (ray_direction->z < 0.){
  117.         tMaxZ = tmin + (voxel2z(volume_grid,z)-ray_entry.z)/ray_direction->z;
  118.         tDeltaZ =  volume_grid.voxel_size.z/(-ray_direction->z);
  119.         stepZ = outZ = -1;
  120.     }
  121.     else if (ray_direction->z > 0.){
  122.         tMaxZ = tmin + (voxel2z(volume_grid,z+1)-ray_entry.z)/ray_direction->z;
  123.         tDeltaZ =  volume_grid.voxel_size.z/ray_direction->z;
  124.         stepZ = 1;
  125.         outZ = volume_grid.z_subdivision;
  126.     }
  127.     else{
  128.         tMaxZ=LARGE;
  129.         tDeltaZ = 0.;
  130.     }
  131.     t1 = tmin;
  132.     while(1){
  133.         int index=voxel_index(volume_grid,x,y,z);
  134. /*
  135.         Voxel *vox=volume_grid.voxels+index;
  136.         HitBoundingBox(&(vox->extent.min),&(vox->extent.max),
  137.             ray_start,ray_direction,&t1,&t2);
  138.         add_to_list(&vlist,index,t1,t2);
  139. */
  140.  
  141.         if ((tMaxX < tMaxY) && (tMaxX < tMaxZ)) {
  142.             add_to_list(&vlist,index,t1,tMaxX); t1 = tMaxX;
  143.             x += stepX;
  144.             if ((tmax < tMaxX) || (x == outX)) break;
  145.                         tMaxX += tDeltaX;
  146.         }else if (tMaxZ < tMaxY) {
  147.             add_to_list(&vlist,index,t1,tMaxZ); t1 = tMaxZ;
  148.             z += stepZ;
  149.                         if ((tmax < tMaxZ) || (z == outZ))
  150.                                 break;
  151.                         tMaxZ += tDeltaZ;
  152.                 } else {
  153.             add_to_list(&vlist,index,t1,tMaxY); t1 = tMaxY;
  154.                         y += stepY;
  155.                         if ((tmax < tMaxY) || (y == outY))
  156.                                 break;
  157.                         tMaxY += tDeltaY;
  158.                 }
  159.     }
  160.     return(vlist);
  161. }
  162.     
  163. int add_to_list(vlist,voxnum,t1,t2)
  164. Vlist **vlist;
  165. int voxnum;
  166. double t1,t2;
  167. {
  168.     Vlist *newvox;
  169.     static Vlist *p;
  170.     newvox=(Vlist *)malloc (sizeof(Vlist));
  171.     if (newvox==NULL) error("In Newbox");
  172.     newvox->voxnum=voxnum;
  173.     newvox->t_near=t1;
  174.     newvox->t_far=t2;
  175.     newvox->next=NULL;
  176.  
  177.     if (*vlist==NULL) *vlist = p = newvox;
  178.     else { p->next = newvox; p = newvox; }
  179. }
  180.  
  181. int purge_vlist(vlist)
  182. Vlist *vlist;
  183. {
  184.     while(vlist != NULL){
  185.         Vlist *tlist=vlist;
  186.         vlist=vlist->next;
  187.         free((char *)tlist);
  188.     }
  189. }
  190.