home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / radsrc22 / src / common / octree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-12  |  2.4 KB  |  121 lines
  1. /* Copyright (c) 1986 Regents of the University of California */
  2.  
  3. #ifndef lint
  4. static char SCCSid[] = "@(#)octree.c 2.1 11/12/91 LBL";
  5. #endif
  6.  
  7. /*
  8.  *  octree.c - routines dealing with octrees and cubes.
  9.  *
  10.  *     7/28/85
  11.  */
  12.  
  13. #include  "standard.h"
  14.  
  15. #include  "octree.h"
  16.  
  17. OCTREE  *octblock[MAXOBLK];        /* our octree */
  18. static OCTREE  ofreelist = EMPTY;    /* freed octree nodes */
  19. static OCTREE  treetop = 0;        /* next free node */
  20.  
  21.  
  22. OCTREE
  23. octalloc()            /* allocate an octree */
  24. {
  25.     register OCTREE  freet;
  26.  
  27.     if ((freet = ofreelist) != EMPTY) {
  28.         ofreelist = octkid(freet, 0);
  29.         return(freet);
  30.     }
  31.     freet = treetop;
  32.     if (octti(freet) == 0) {
  33.         errno = 0;
  34.         if (octbi(freet) >= MAXOBLK)
  35.             return(EMPTY);
  36.         if ((octblock[octbi(freet)] = (OCTREE *)bmalloc(
  37.                 (unsigned)256*8*sizeof(OCTREE))) == NULL)
  38.             return(EMPTY);
  39.     }
  40.     treetop += 8;
  41.     return(freet);
  42. }
  43.  
  44.  
  45. octfree(ot)            /* free an octree */
  46. register OCTREE  ot;
  47. {
  48.     register int  i;
  49.  
  50.     if (!istree(ot))
  51.         return;
  52.     for (i = 0; i < 8; i++)
  53.         octfree(octkid(ot, i));
  54.     octkid(ot, 0) = ofreelist;
  55.     ofreelist = ot;
  56. }
  57.  
  58.  
  59. OCTREE
  60. combine(ot)            /* recursively combine nodes */
  61. register OCTREE  ot;
  62. {
  63.     register int  i;
  64.     register OCTREE  ores;
  65.  
  66.     if (!istree(ot))    /* not a tree */
  67.         return(ot);
  68.     ores = octkid(ot, 0) = combine(octkid(ot, 0));
  69.     for (i = 1; i < 8; i++)
  70.         if ((octkid(ot, i) = combine(octkid(ot, i))) != ores)
  71.             ores = ot;
  72.     if (!istree(ores)) {    /* all were identical leaves */
  73.         octkid(ot, 0) = ofreelist;
  74.         ofreelist = ot;
  75.     }
  76.     return(ores);
  77. }
  78.  
  79.  
  80. culocate(cu, pt)        /* locate point within cube */
  81. register CUBE  *cu;
  82. register FVECT  pt;
  83. {
  84.     register int  i;
  85.     int  branch;
  86.  
  87.     while (istree(cu->cutree)) {
  88.         cu->cusize *= 0.5;
  89.         branch = 0;
  90.         for (i = 0; i < 3; i++)
  91.             if (cu->cuorg[i] + cu->cusize <= pt[i]) {
  92.                 cu->cuorg[i] += cu->cusize;
  93.                 branch |= 1 << i;
  94.             }
  95.         cu->cutree = octkid(cu->cutree, branch);
  96.     }
  97. }
  98.  
  99.  
  100. cucopy(cu1, cu2)        /* copy cu2 into cu1 */
  101. register CUBE  *cu1, *cu2;
  102. {
  103.     cu1->cutree = cu2->cutree;
  104.     cu1->cusize = cu2->cusize;
  105.     VCOPY(cu1->cuorg, cu2->cuorg);
  106. }
  107.  
  108.  
  109. incube(cu, pt)            /* determine if a point is inside a cube */
  110. register CUBE  *cu;
  111. register FVECT  pt;
  112. {
  113.     if (cu->cuorg[0] > pt[0] || pt[0] >= cu->cuorg[0] + cu->cusize)
  114.         return(0);
  115.     if (cu->cuorg[1] > pt[1] || pt[1] >= cu->cuorg[1] + cu->cusize)
  116.         return(0);
  117.     if (cu->cuorg[2] > pt[2] || pt[2] >= cu->cuorg[2] + cu->cusize)
  118.         return(0);
  119.     return(1);
  120. }
  121.