home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 231.lha / URay_v1.0 / extent.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-04  |  6.9 KB  |  275 lines
  1. /************************************************************************
  2.  *                                    *
  3.  *            Copyright (c) 1988, David B. Wecker            *
  4.  *                All Rights Reserved                *
  5.  *                                    *
  6.  * This file is part of DBW_uRAY                    *
  7.  *                                    *
  8.  * DBW_uRAY is distributed in the hope that it will be useful, but    *
  9.  * WITHOUT ANY WARRANTY. No author or distributor accepts        *
  10.  * responsibility to anyone for the consequences of using it or for    *
  11.  * whether it serves any particular purpose or works at all, unless    *
  12.  * he says so in writing. Refer to the DBW_uRAY General Public        *
  13.  * License for full details.                        *
  14.  *                                    *
  15.  * Everyone is granted permission to copy, modify and redistribute    *
  16.  * DBW_uRAY, but only under the conditions described in the        *
  17.  * DBW_uRAY General Public License. A copy of this license is        *
  18.  * supposed to have been given to you along with DBW_uRAY so you    *
  19.  * can know your rights and responsibilities. It should be in a file    *
  20.  * named COPYING. Among other things, the copyright notice and this    *
  21.  * notice must be preserved on all copies.                *
  22.  ************************************************************************
  23.  *                                    *
  24.  * Authors:                                *
  25.  *    DBW - David B. Wecker                        *
  26.  *                                    *
  27.  * Versions:                                *
  28.  *    V1.0 881023 DBW    - First released version            *
  29.  *    V1.1 881110 DBW - Fixed scan coherence code            *
  30.  *    V1.2 881125 DBW - Removed ALL scan coherence code (useless)    *
  31.  *              added "fat" extent boxes            *
  32.  *                                    *
  33.  ************************************************************************/
  34.  
  35. #include "uray.h"
  36.  
  37.  
  38. /**************************************************************************/
  39. /* This module builds a hierarchy of oct-tree extents to speed up tracing */
  40. /**************************************************************************/
  41.  
  42.  
  43. /* union an extent and a vector. (min of the mins and max of the maxs) */
  44. void unionvector( re, v, nre )
  45. EXTENT    *re,*nre;
  46. VEC    v;
  47.     {
  48.     int        i;
  49.  
  50.     for (i = 0; i < 3; i++) {
  51.     nre->min[i] = MIN(re->min[i], v[i] );
  52.     nre->max[i] = MAX(re->max[i], v[i] );
  53.     }
  54.     }
  55.  
  56. /* union 2 extents. (min of the mins and max of the maxs) */
  57. void unionextent( e1, e2, ne )
  58. EXTENT    *e1,*e2,*ne;
  59.     {
  60.     int        i;
  61.  
  62.     for (i = 0; i < 3; i++) {
  63.     ne->min[i] = MIN(e1->min[i], e2->min[i] );
  64.     ne->max[i] = MAX(e1->max[i], e2->max[i] );
  65.     }
  66.     }
  67.  
  68. /* build all extents */
  69. void getextent(np,e)
  70. NODE    *np;
  71. EXTENT    *e;
  72.     {
  73.     EXTENT    newe;
  74.     EXTENT    *ext;
  75.     SPHERE    *sph;
  76.     RING    *flat;
  77.     int        i;
  78.     VEC        v1,v2;
  79.     FLTDBL    rad;
  80.  
  81.     /* initialize the extent */
  82.     for (i=0; i<3; i++) {
  83.     e->min[i] =  MYHUGE;
  84.     e->max[i] = -MYHUGE;
  85.     }
  86.   
  87.     while (np) {
  88.     switch (np->typ) {
  89.  
  90.         /* if an extent, build all children, then return result */
  91.         case TYP_E:
  92.         ext = (EXTENT *)np;
  93.         getextent(ext->child,&newe);
  94.         for (i = 0; i < 3; i++) {
  95.         ext->min[i] = newe.min[i];
  96.         ext->max[i] = newe.max[i];
  97.         }
  98.         break;
  99.  
  100.         /* if a sphere, build the extent for this one object */
  101.         case TYP_S:
  102.         sph = (SPHERE *)np;
  103.         rad = sqrt(sph->rad);
  104.         for (i = 0; i < 3; i++) {
  105.         newe.min[i] = sph->cen[i] - (rad + TOL);
  106.         newe.max[i] = sph->cen[i] + (rad + TOL);
  107.         }
  108.         break;
  109.  
  110.         /* if a planar, build the extent for this one object */
  111.         case TYP_T:
  112.         case TYP_Q:
  113.         case TYP_R:
  114.         flat = (RING *)np;
  115.         for (i=0; i<3; i++) {
  116.         newe.min[i] =  MYHUGE;
  117.         newe.max[i] = -MYHUGE;
  118.         }
  119.  
  120.         /* do ring specific calculations */
  121.         if (np->typ == TYP_R) {
  122.         rad = sqrt(flat->rad2);
  123.         vcomb(rad,flat->v1,flat->p0,v1);
  124.         vcomb(rad,flat->v2,v1,v2);
  125.         unionvector(&newe,v2,&newe);
  126.         vcomb(-rad,flat->v2,v1,v2);
  127.         unionvector(&newe,v2,&newe);
  128.         vcomb(-rad,flat->v1,flat->p0,v1);
  129.         vcomb(rad,flat->v2,v1,v2);
  130.         unionvector(&newe,v2,&newe);
  131.         vcomb(-rad,flat->v2,v1,v2);
  132.         unionvector(&newe,v2,&newe);
  133.         }
  134.         else {
  135.         vcomb(1.0,flat->p0,flat->v1,v1);
  136.         vcomb(1.0,flat->p0,flat->v2,v2);
  137.         unionvector(&newe,flat->p0,&newe);
  138.         unionvector(&newe,v1,&newe);
  139.         unionvector(&newe,v2,&newe);
  140.         }
  141.  
  142.         /* pad the extent (so no round off errors) */
  143.         for (i=0; i<3; i++) {
  144.         newe.min[i] -= TOL;
  145.         newe.max[i] += TOL;
  146.         }
  147.         break;
  148.         }
  149.  
  150.     /* unionextent for next level up */
  151.     unionextent(e,&newe,e);
  152.  
  153.     /* get next node */
  154.     np = np->next;
  155.     }
  156.     }
  157.  
  158.  
  159. /* this is the actual routine that builds the extent hierarchy */
  160. /* The tree can have upto SRTMAX nodes in each bucket and can be upto */
  161. /* SRTLEV levels deep. These have been tuned for optimal results */
  162.  
  163. #define SRTMAX     8    /* maximum allowed in one bucket */
  164. #define SRTLEV    16    /* sort recursion level */
  165.  
  166. NODE    *sortext(ext,lev)
  167. int    lev;
  168. EXTENT    *ext;
  169.     {
  170.     int        i,j,x,y,z;
  171.     EXTENT    *tmp,*tmp2,*curr,*next;
  172.     FLTDBL    cen,ave[3],min[3],max[3];
  173.     struct {
  174.     int    count;
  175.     EXTENT    *bkt;
  176.     } cube[2][2][2], *cp = &cube[0][0][0];
  177.  
  178.     /* init the 8 extents (to build) */
  179.     for (i=0; i< 8; i++) {
  180.     cp[i].bkt   = NULL;
  181.     cp[i].count = 0;
  182.     }
  183.     for (i=0; i<3; i++) {
  184.     min[i] =  MYHUGE;
  185.     max[i] = -MYHUGE;
  186.     }
  187.  
  188.     /* compute the extent range */
  189.     curr = ext;
  190.     while (curr) {
  191.     for (i=0; i < 3; i++) {
  192.         if (curr->min[i]<min[i]) min[i] = curr->min[i];
  193.         if (curr->max[i]>max[i]) max[i] = curr->max[i];
  194.         }
  195.     curr = (EXTENT *)curr->next;
  196.     }
  197.  
  198.     /* now compute centers of buckets */
  199.     for (i=0; i<3; i++) ave[i] = 0.5 * (min[i] + max[i]);
  200.  
  201.     /* now place eveybody in buckets */
  202.     curr = ext;
  203.     while (curr) {
  204.     next = (EXTENT *)curr->next;
  205.     for (i=0; i<3; i++) {
  206.         cen = 0.5 * (curr->max[i] + curr->min[i]);
  207.         if (cen >= ave[i]) j = 1;
  208.         else           j = 0;
  209.         switch (i) {
  210.         case 0:    x = j; break;
  211.         case 1: y = j; break;
  212.         case 2: z = j; break;
  213.         }
  214.         }
  215.     curr->next        = (NODE *)cube[x][y][z].bkt;
  216.     cube[x][y][z].bkt   = curr;
  217.     cube[x][y][z].count++;
  218.     curr            = next;
  219.     }
  220.  
  221.     /* put the buckets back together */
  222.     curr = NULL;
  223.     for (x=0; x<2; x++)
  224.     for (y=0; y<2; y++)
  225.         for (z=0; z<2; z++) {
  226.         if (!cube[x][y][z].count) continue;
  227.  
  228.         /* do we need to split up this bucket */
  229.         if (cube[x][y][z].count > SRTMAX && lev < SRTLEV) {
  230.             cube[x][y][z].bkt = tmp = 
  231.             (EXTENT *)sortext(cube[x][y][z].bkt,lev+1);
  232.             cube[x][y][z].count = 0;
  233.             while (tmp) {
  234.             cube[x][y][z].count++;
  235.             tmp = (EXTENT *)tmp->next;
  236.             }
  237.             }
  238.         if (cube[x][y][z].count != 1) {
  239.             tmp        = (EXTENT *)doalloc(TYP_E);
  240.             tmp->child    = (NODE *)cube[x][y][z].bkt;
  241.             for (i=0; i<3; i++) {
  242.             tmp->min[i] =  MYHUGE;
  243.             tmp->max[i] = -MYHUGE;
  244.             }
  245.             tmp2 = (EXTENT *)tmp->child;
  246.             while (tmp2) {
  247.             unionextent(tmp,tmp2,tmp);
  248.             tmp2 = (EXTENT *)tmp2->next;
  249.             }
  250.             cube[x][y][z].bkt = tmp;
  251.             }
  252.         cube[x][y][z].bkt->next    = (NODE *)curr;
  253.         curr            = cube[x][y][z].bkt;
  254.         }
  255.  
  256.     return((NODE *)curr);
  257.     }
  258.  
  259. /* top level extent building routine */
  260. void doextents() {
  261.     VEC        scr_v;
  262.     EXTENT  e;
  263.  
  264.     /* Get all the leafs of the extent hierarchy */
  265.     printf("Creating object extents\n");
  266.     getextent(nodes,&e);
  267.  
  268.     /* now sort objects (building extent tree) */
  269.     printf("Creating extent tree\n");
  270.     nodes = sortext(nodes,0);
  271.  
  272.     printf("Using %d extents for %d objects\n\n",extcnt,objcnt);
  273.     }
  274.  
  275.