home *** CD-ROM | disk | FTP | other *** search
/ Encyclopedia of Graphics File Formats Companion / GFF_CD.ISO / formats / uray / code / extent.c < prev    next >
C/C++ Source or Header  |  1994-06-20  |  7KB  |  276 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 LICENSE. 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.  *    V1.3 881203 DBW - Fixed single precision TOLerances        *
  33.  *                                    *
  34.  ************************************************************************/
  35.  
  36. #include "uray.h"
  37.  
  38.  
  39. /**************************************************************************/
  40. /* This module builds a hierarchy of oct-tree extents to speed up tracing */
  41. /**************************************************************************/
  42.  
  43.  
  44. /* union an extent and a vector. (min of the mins and max of the maxs) */
  45. void unionvector( re, v, nre )
  46. EXTENT    *re,*nre;
  47. VEC    v;
  48.     {
  49.     int        i;
  50.  
  51.     for (i = 0; i < 3; i++) {
  52.     nre->min[i] = MIN(re->min[i], v[i] );
  53.     nre->max[i] = MAX(re->max[i], v[i] );
  54.     }
  55.     }
  56.  
  57. /* union 2 extents. (min of the mins and max of the maxs) */
  58. void unionextent( e1, e2, ne )
  59. EXTENT    *e1,*e2,*ne;
  60.     {
  61.     int        i;
  62.  
  63.     for (i = 0; i < 3; i++) {
  64.     ne->min[i] = MIN(e1->min[i], e2->min[i] );
  65.     ne->max[i] = MAX(e1->max[i], e2->max[i] );
  66.     }
  67.     }
  68.  
  69. /* build all extents */
  70. void getextent(np,e)
  71. NODE    *np;
  72. EXTENT    *e;
  73.     {
  74.     EXTENT    newe;
  75.     EXTENT    *ext;
  76.     SPHERE    *sph;
  77.     RING    *flat;
  78.     int        i;
  79.     VEC        v1,v2;
  80.     FLTDBL    rad;
  81.  
  82.     /* initialize the extent */
  83.     for (i=0; i<3; i++) {
  84.     e->min[i] =  MYHUGE;
  85.     e->max[i] = -MYHUGE;
  86.     }
  87.   
  88.     while (np) {
  89.     switch (np->typ) {
  90.  
  91.         /* if an extent, build all children, then return result */
  92.         case TYP_E:
  93.         ext = (EXTENT *)np;
  94.         getextent(ext->child,&newe);
  95.         for (i = 0; i < 3; i++) {
  96.         ext->min[i] = newe.min[i];
  97.         ext->max[i] = newe.max[i];
  98.         }
  99.         break;
  100.  
  101.         /* if a sphere, build the extent for this one object */
  102.         case TYP_S:
  103.         sph = (SPHERE *)np;
  104.         rad = sqrt(sph->rad);
  105.         for (i = 0; i < 3; i++) {
  106.         newe.min[i] = sph->cen[i] - (rad + TOL);
  107.         newe.max[i] = sph->cen[i] + (rad + TOL);
  108.         }
  109.         break;
  110.  
  111.         /* if a planar, build the extent for this one object */
  112.         case TYP_T:
  113.         case TYP_Q:
  114.         case TYP_R:
  115.         flat = (RING *)np;
  116.         for (i=0; i<3; i++) {
  117.         newe.min[i] =  MYHUGE;
  118.         newe.max[i] = -MYHUGE;
  119.         }
  120.  
  121.         /* do ring specific calculations */
  122.         if (np->typ == TYP_R) {
  123.         rad = sqrt(flat->rad2);
  124.         vcomb(rad,flat->v1,flat->p0,v1);
  125.         vcomb(rad,flat->v2,v1,v2);
  126.         unionvector(&newe,v2,&newe);
  127.         vcomb(-rad,flat->v2,v1,v2);
  128.         unionvector(&newe,v2,&newe);
  129.         vcomb(-rad,flat->v1,flat->p0,v1);
  130.         vcomb(rad,flat->v2,v1,v2);
  131.         unionvector(&newe,v2,&newe);
  132.         vcomb(-rad,flat->v2,v1,v2);
  133.         unionvector(&newe,v2,&newe);
  134.         }
  135.         else {
  136.         vcomb(1.0,flat->p0,flat->v1,v1);
  137.         vcomb(1.0,flat->p0,flat->v2,v2);
  138.         unionvector(&newe,flat->p0,&newe);
  139.         unionvector(&newe,v1,&newe);
  140.         unionvector(&newe,v2,&newe);
  141.         }
  142.  
  143.         /* pad the extent (so no round off errors) */
  144.         for (i=0; i<3; i++) {
  145.         newe.min[i] -= TOL;
  146.         newe.max[i] += TOL;
  147.         }
  148.         break;
  149.         }
  150.  
  151.     /* unionextent for next level up */
  152.     unionextent(e,&newe,e);
  153.  
  154.     /* get next node */
  155.     np = np->next;
  156.     }
  157.     }
  158.  
  159.  
  160. /* this is the actual routine that builds the extent hierarchy */
  161. /* The tree can have upto SRTMAX nodes in each bucket and can be upto */
  162. /* SRTLEV levels deep. These have been tuned for optimal results */
  163.  
  164. #define SRTMAX     8    /* maximum allowed in one bucket */
  165. #define SRTLEV    16    /* sort recursion level */
  166.  
  167. NODE    *sortext(ext,lev)
  168. int    lev;
  169. EXTENT    *ext;
  170.     {
  171.     int        i,j,x,y,z;
  172.     EXTENT    *tmp,*tmp2,*curr,*next;
  173.     FLTDBL    cen,ave[3],min[3],max[3];
  174.     struct {
  175.     int    count;
  176.     EXTENT    *bkt;
  177.     } cube[2][2][2], *cp = &cube[0][0][0];
  178.  
  179.     /* init the 8 extents (to build) */
  180.     for (i=0; i< 8; i++) {
  181.     cp[i].bkt   = NULL;
  182.     cp[i].count = 0;
  183.     }
  184.     for (i=0; i<3; i++) {
  185.     min[i] =  MYHUGE;
  186.     max[i] = -MYHUGE;
  187.     }
  188.  
  189.     /* compute the extent range */
  190.     curr = ext;
  191.     while (curr) {
  192.     for (i=0; i < 3; i++) {
  193.         if (curr->min[i]<min[i]) min[i] = curr->min[i];
  194.         if (curr->max[i]>max[i]) max[i] = curr->max[i];
  195.         }
  196.     curr = (EXTENT *)curr->next;
  197.     }
  198.  
  199.     /* now compute centers of buckets */
  200.     for (i=0; i<3; i++) ave[i] = 0.5 * (min[i] + max[i]);
  201.  
  202.     /* now place eveybody in buckets */
  203.     curr = ext;
  204.     while (curr) {
  205.     next = (EXTENT *)curr->next;
  206.     for (i=0; i<3; i++) {
  207.         cen = 0.5 * (curr->max[i] + curr->min[i]);
  208.         if (cen >= ave[i]) j = 1;
  209.         else           j = 0;
  210.         switch (i) {
  211.         case 0:    x = j; break;
  212.         case 1: y = j; break;
  213.         case 2: z = j; break;
  214.         }
  215.         }
  216.     curr->next        = (NODE *)cube[x][y][z].bkt;
  217.     cube[x][y][z].bkt   = curr;
  218.     cube[x][y][z].count++;
  219.     curr            = next;
  220.     }
  221.  
  222.     /* put the buckets back together */
  223.     curr = NULL;
  224.     for (x=0; x<2; x++)
  225.     for (y=0; y<2; y++)
  226.         for (z=0; z<2; z++) {
  227.         if (!cube[x][y][z].count) continue;
  228.  
  229.         /* do we need to split up this bucket */
  230.         if (cube[x][y][z].count > SRTMAX && lev < SRTLEV) {
  231.             cube[x][y][z].bkt = tmp = 
  232.             (EXTENT *)sortext(cube[x][y][z].bkt,lev+1);
  233.             cube[x][y][z].count = 0;
  234.             while (tmp) {
  235.             cube[x][y][z].count++;
  236.             tmp = (EXTENT *)tmp->next;
  237.             }
  238.             }
  239.         if (cube[x][y][z].count != 1) {
  240.             tmp        = (EXTENT *)doalloc(TYP_E);
  241.             tmp->child    = (NODE *)cube[x][y][z].bkt;
  242.             for (i=0; i<3; i++) {
  243.             tmp->min[i] =  MYHUGE;
  244.             tmp->max[i] = -MYHUGE;
  245.             }
  246.             tmp2 = (EXTENT *)tmp->child;
  247.             while (tmp2) {
  248.             unionextent(tmp,tmp2,tmp);
  249.             tmp2 = (EXTENT *)tmp2->next;
  250.             }
  251.             cube[x][y][z].bkt = tmp;
  252.             }
  253.         cube[x][y][z].bkt->next    = (NODE *)curr;
  254.         curr            = cube[x][y][z].bkt;
  255.         }
  256.  
  257.     return((NODE *)curr);
  258.     }
  259.  
  260. /* top level extent building routine */
  261. void doextents() {
  262.     VEC        scr_v;
  263.     EXTENT  e;
  264.  
  265.     /* Get all the leafs of the extent hierarchy */
  266.     printf("Creating object extents\n");
  267.     getextent(nodes,&e);
  268.  
  269.     /* now sort objects (building extent tree) */
  270.     printf("Creating extent tree\n");
  271.     nodes = sortext(nodes,0);
  272.  
  273.     printf("Using %d extents for %d objects\n\n",extcnt,objcnt);
  274.     }
  275.  
  276.