Back to index

radiance  4R0+20100331
octree.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: octree.c,v 2.8 2009/11/01 04:41:55 greg Exp $";
00003 #endif
00004 /*
00005  *  octree.c - routines dealing with octrees and cubes.
00006  */
00007 
00008 #include "copyright.h"
00009 
00010 #include  "standard.h"
00011 
00012 #include  "octree.h"
00013 
00014 OCTREE  *octblock[MAXOBLK];        /* our octree */
00015 static OCTREE  ofreelist = EMPTY;  /* freed octree nodes */
00016 static OCTREE  treetop = 0;        /* next free node */
00017 
00018 
00019 OCTREE
00020 octalloc()                  /* allocate an octree */
00021 {
00022        OCTREE  freet;
00023 
00024        if ((freet = ofreelist) != EMPTY) {
00025               ofreelist = octkid(freet, 0);
00026               return(freet);
00027        }
00028        freet = treetop;
00029        if (octti(freet) == 0) {
00030               errno = 0;
00031               if (octbi(freet) >= MAXOBLK)
00032                      return(EMPTY);
00033               if ((octblock[octbi(freet)] = (OCTREE *)malloc(
00034                             (unsigned)OCTBLKSIZ*8*sizeof(OCTREE))) == NULL)
00035                      return(EMPTY);
00036        }
00037        treetop++;
00038        return(freet);
00039 }
00040 
00041 
00042 void
00043 octfree(ot)                 /* free an octree */
00044 OCTREE  ot;
00045 {
00046        int  i;
00047 
00048        if (!istree(ot))
00049               return;
00050        for (i = 0; i < 8; i++)
00051               octfree(octkid(ot, i));
00052        octkid(ot, 0) = ofreelist;
00053        ofreelist = ot;
00054 }
00055 
00056 
00057 void
00058 octdone()                   /* free EVERYTHING */
00059 {
00060        int    i;
00061 
00062        for (i = 0; i < MAXOBLK; i++) {
00063               if (octblock[i] == NULL)
00064                      break;
00065               free((void *)octblock[i]);
00066               octblock[i] = NULL;
00067        }
00068        ofreelist = EMPTY;
00069        treetop = 0;
00070 }
00071 
00072 
00073 OCTREE
00074 combine(ot)                 /* recursively combine nodes */
00075 OCTREE  ot;
00076 {
00077        int  i;
00078        OCTREE  ores;
00079 
00080        if (!istree(ot))     /* not a tree */
00081               return(ot);
00082        ores = octkid(ot, 0) = combine(octkid(ot, 0));
00083        for (i = 1; i < 8; i++)
00084               if ((octkid(ot, i) = combine(octkid(ot, i))) != ores)
00085                      ores = ot;
00086        if (!istree(ores)) { /* all were identical leaves */
00087               octkid(ot, 0) = ofreelist;
00088               ofreelist = ot;
00089        }
00090        return(ores);
00091 }
00092 
00093 
00094 void
00095 culocate(cu, pt)            /* locate point within cube */
00096 CUBE  *cu;
00097 FVECT  pt;
00098 {
00099        int  i;
00100        int  branch;
00101 
00102        while (istree(cu->cutree)) {
00103               cu->cusize *= 0.5;
00104               branch = 0;
00105               for (i = 0; i < 3; i++)
00106                      if (cu->cuorg[i] + cu->cusize <= pt[i]) {
00107                             cu->cuorg[i] += cu->cusize;
00108                             branch |= 1 << i;
00109                      }
00110               cu->cutree = octkid(cu->cutree, branch);
00111        }
00112 }
00113 
00114 
00115 int
00116 incube(cu, pt)                     /* determine if a point is inside a cube */
00117 CUBE  *cu;
00118 FVECT  pt;
00119 {
00120        if (cu->cuorg[0] > pt[0] || pt[0] >= cu->cuorg[0] + cu->cusize)
00121               return(0);
00122        if (cu->cuorg[1] > pt[1] || pt[1] >= cu->cuorg[1] + cu->cusize)
00123               return(0);
00124        if (cu->cuorg[2] > pt[2] || pt[2] >= cu->cuorg[2] + cu->cusize)
00125               return(0);
00126        return(1);
00127 }