home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume18 / mtvraytrace / part01 / bound.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-26  |  3.6 KB  |  177 lines
  1. /***********************************************************************
  2.  * $Author: markv $
  3.  * $Revision: 1.3 $
  4.  * $Date: 88/10/31 14:47:22 $
  5.  * $Log:    bound.c,v $
  6.  * Revision 1.3  88/10/31  14:47:22  markv
  7.  * Removed the noisy printout which gave the bounds of the scene...
  8.  * 
  9.  * Revision 1.2  88/09/14  13:54:46  markv
  10.  * Check for overflow of array Prims[].  Should fix problems
  11.  * with rendering the gears at size factor 4.
  12.  * 
  13.  * Revision 1.1  88/09/11  11:00:36  markv
  14.  * Initial revision
  15.  * 
  16.  ***********************************************************************/
  17. #include <stdio.h>
  18. #include <math.h>
  19. #include "defs.h"
  20. #include "extern.h"
  21.  
  22. /*
  23.  * This function attempts to use median cut
  24.  * to generate tighter bounding volumes than the old
  25.  * code...
  26.  */
  27.  
  28. BuildBoundingSlabs()
  29. {
  30.     int low = 0 ;
  31.     int high, i ;
  32.  
  33.     high = nPrims ;
  34.     while (SortAndSplit(low, high) == 0) {
  35.         low = high ;
  36.         high = nPrims ;
  37.     }
  38.     fprintf(stderr, "%s: after adding bounding volumes, %d prims\n",
  39.         Progname, nPrims) ;
  40.     fprintf(stderr, "%s: extent of scene\n", Progname) ;
  41. #ifdef NOISY
  42.     for (i = 0 ; i < NSLABS; i++) {
  43.         fprintf(stderr, "%s: <%g -- %g>\n",
  44.                 Progname,
  45.                 Root -> o_dmin[i],
  46.                 Root -> o_dmax[i]) ;
  47.     }
  48. #endif /* NOISY */
  49. }
  50.  
  51. static int Axis ;
  52.  
  53. int 
  54. compslabs(a, b)
  55.  Object **a, **b ;
  56. {
  57.     Flt am, bm ;
  58.  
  59.     am = (*a) -> o_dmin[Axis] + (*a) -> o_dmax[Axis] ;
  60.     bm = (*b) -> o_dmin[Axis] + (*b) -> o_dmax[Axis] ;
  61.  
  62.     if (am < bm)
  63.         return (-1) ;
  64.     else if (am == bm)
  65.         return (0) ;
  66.     else
  67.         return (1) ;
  68. }
  69.  
  70. int
  71. FindAxis(first, last)
  72.  int first, last ;
  73. {
  74.     Flt    mins[NSLABS] ;
  75.     Flt    maxs[NSLABS] ;
  76.     int    i, j , which ;
  77.     Flt     d = -HUGE, e ;
  78.     for (i = 0 ; i < NSLABS ; i++) {
  79.         mins[i] = HUGE ;
  80.         maxs[i] = -HUGE ;
  81.     }
  82.  
  83.     for (i = first ; i < last ; i++) {
  84.         for (j = 0 ; j < NSLABS ; j++) {
  85.             if (Prims[i] -> o_dmin[j] < mins[j])
  86.                 mins[j] = Prims[i] -> o_dmin [j] ;
  87.             if (Prims[i] -> o_dmin[j] > maxs[j])
  88.                 maxs[j] = Prims[i] -> o_dmax [j] ;
  89.         }
  90.     }
  91.  
  92.     for (i = 0 ; i < NSLABS ; i++) {
  93.         e = maxs[i] - mins[i] ;
  94.         if (e > d) {
  95.             d = e ;
  96.             which = i ;
  97.         }
  98.     }
  99.     return(which) ;
  100. }
  101.  
  102. SortAndSplit(first, last)
  103.  int first, last ;
  104. {
  105.     Object * cp ;
  106.     CompositeData * cd ;
  107.     int size, i, j ;
  108.     Flt dmin, dmax ;
  109.     int m ;
  110.  
  111.     Axis = FindAxis(first, last) ;
  112.  
  113.     size = last - first ;
  114.  
  115.     /*
  116.      * actually, we could do this faster in several ways.
  117.      * we could use a logn algorithm to find the median
  118.      * along the given axis, and then a linear algorithm to 
  119.      * partition along the axis. Oh well...
  120.      */
  121.  
  122.     qsort((char *) (Prims + first), size, sizeof (Object *), compslabs) ;
  123.  
  124.     if (size <= BUNCHINGFACTOR) {
  125.         /* build a box to contain them */
  126.  
  127.         cp = (Object *) malloc (sizeof(Object)) ;
  128.         cp -> o_type = T_COMPOSITE ;
  129.         cp -> o_procs = & NullProcs ;     /* die if you call any     */
  130.         cp -> o_surf = NULL ;        /* no surface...    */
  131.         cd = (CompositeData *) malloc (sizeof(CompositeData)) ;
  132.         cd -> c_size = size ;
  133.  
  134.         for(i = 0 ; i < size ; i++) {
  135.             cd -> c_object[i] = Prims[first + i] ;
  136.         }
  137.  
  138.         for (i = 0 ; i < NSLABS ; i++ ) {
  139.             dmin = HUGE ;
  140.             dmax = -HUGE ;
  141.             for (j = 0 ; j < size ; j++) {
  142.                 if (cd -> c_object[j] -> o_dmin[i] < dmin)
  143.                     dmin = cd -> c_object[j] -> o_dmin[i] ;
  144.                 if (cd -> c_object[j] -> o_dmax[i] > dmax)
  145.                     dmax = cd -> c_object[j] -> o_dmax[i] ;
  146.             }
  147.             cp -> o_dmin[i] = dmin ;
  148.             cp -> o_dmax[i] = dmax ;
  149.         }
  150.         cp -> o_data = (void *) cd ;
  151.         Root = cp ;
  152.         if (nPrims < MAXPRIMS) {
  153.             Prims[nPrims ++] = cp ;
  154.             return (1) ;
  155.         } else {
  156.             fprintf(stderr, "too many primitives, max is %d\n",
  157.                 MAXPRIMS) ;
  158.                 exit(0);
  159.         }
  160.     } else {
  161.         m = (first + last) / 2 ;
  162.         SortAndSplit(first, m) ;
  163.         SortAndSplit(m , last) ;
  164.         return (0) ;
  165.     }
  166. }
  167.     
  168.  
  169. InitSlabs()
  170. {
  171.     int i ;
  172.  
  173.     for (i = 0 ; i < NSLABS ; i ++) {
  174.         VecNormalize(Slab[i]) ;
  175.     }
  176. }
  177.