ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhd_qtree.c
(Generate patch)

Comparing ray/src/hd/rhd_qtree.c (file contents):
Revision 3.1 by gregl, Wed Nov 19 18:01:03 1997 UTC vs.
Revision 3.4 by gregl, Fri Nov 21 09:52:06 1997 UTC

# Line 11 | Line 11 | static char SCCSid[] = "$SunId$ SGI";
11   #include "standard.h"
12   #include "rhd_qtree.h"
13  
14 – static RLEAF    *leafpile;      /* our collection of leaf values */
15 – static int      nleaves;        /* count of leaves in our pile */
16 – static int      bleaf, tleaf;   /* bottom and top (next) leaf index (ring) */
17 –
14   RTREE   qtrunk;                 /* our quadtree trunk */
15   double  qtDepthEps = .02;       /* epsilon to compare depths (z fraction) */
16   int     qtMinNodesiz = 2;       /* minimum node dimension (pixels) */
17  
18 + static RLEAF    *leafpile;      /* our collection of leaf values */
19 + static int      nleaves;        /* count of leaves in our pile */
20 + static int      bleaf, tleaf;   /* bottom and top (next) leaf index (ring) */
21 +
22   #define TBUNDLESIZ      409     /* number of twigs in a bundle */
23  
24   static RTREE    **twigbundle;   /* free twig blocks (NULL term.) */
# Line 58 | Line 58 | memerr:
58   }
59  
60  
61 < static
62 < freetwigs(really)               /* free allocated twigs */
61 > qtFreeTree(really)              /* free allocated twigs */
62   int     really;
63   {
64          register int    i;
65  
66 <        if (tmTop != NULL)
68 <                tmClearHisto();
66 >        tmClearHisto();
67          bzero((char *)&qtrunk, sizeof(RTREE));
68          nexttwig = 0;
69          if (twigbundle == NULL)
# Line 86 | Line 84 | int    really;
84   static RLEAF *
85   newleaf()                       /* allocate a leaf from our pile */
86   {
87 <        if (tleaf++ >= nleaves)         /* get next leaf in ring */
87 >        RLEAF   *lp;
88 >        
89 >        lp = leafpile + tleaf++;
90 >        if (tleaf >= nleaves)           /* get next leaf in ring */
91                  tleaf = 0;
92          if (tleaf == bleaf)             /* need to shake some free */
93                  qtCompost(LFREEPCT);
94 <        return(leafpile + tleaf);
94 >        return(lp);
95   }
96  
97  
# Line 101 | Line 102 | int    n;
102          unsigned        nbytes;
103          register unsigned       i;
104  
105 <        freetwigs(0);           /* make sure tree is empty */
105 >        qtFreeTree(0);          /* make sure tree is empty */
106          if (n <= 0)
107                  return(0);
108          if (nleaves >= n)
# Line 124 | Line 125 | int    n;
125  
126   qtFreeLeaves()                  /* free our allocated leaves and twigs */
127   {
128 <        freetwigs(1);           /* free tree also */
128 >        qtFreeTree(1);          /* free tree also */
129          if (nleaves <= 0)
130                  return;
131          free((char *)leafpile);
# Line 140 | Line 141 | register RTREE *tp;
141          register int    i, li;
142  
143          for (i = 0; i < 4; i++)
144 <                if (tp->flgs & BRF(i)) {
145 <                        if (shaketree(tp->k[i].b))
146 <                                tp->flgs |= CHF(i);
146 <                } else if (tp->k[i].l != NULL) {
144 >                if (tp->flgs & BRF(i))
145 >                        shaketree(tp->k[i].b);
146 >                else if (tp->k[i].l != NULL) {
147                          li = tp->k[i].l - leafpile;
148                          if (bleaf < tleaf ? (li < bleaf || li >= tleaf) :
149                                          (li < bleaf && li >= tleaf)) {
150                                  tmAddHisto(&tp->k[i].l->brt, 1, -1);
151                                  tp->k[i].l = NULL;
152 –                                tp->flgs |= CHF(i);
152                          }
153                  }
155 –        return(tp->flgs & CH_ANY);
154   }
155  
156  
# Line 161 | Line 159 | qtCompost(pct)                 /* free up some leaves */
159   int     pct;
160   {
161          int     nused, nclear;
162 +
163 +        if (is_stump(&qtrunk))
164 +                return(0);
165                                  /* figure out how many leaves to clear */
166          nclear = nleaves * pct / 100;
167 +        nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf;
168 +        nclear -= nleaves - nused;      /* less what's already free */
169          if (nclear <= 0)
170                  return(0);
168 –        nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf;
171          if (nclear >= nused) {  /* clear them all */
172 <                freetwigs(0);
172 >                qtFreeTree(0);
173                  bleaf = tleaf = 0;
174                  return(nused);
175          }
176                                  /* else clear leaves from bottom */
177 <        bleaf = (bleaf + nclear) % nleaves;
177 >        bleaf += nclear;
178 >        if (bleaf >= nleaves) bleaf -= nleaves;
179          shaketree(&qtrunk);
180          return(nclear);
181   }
182  
183  
184 + RLEAF *
185 + qtFindLeaf(x, y)                /* find closest leaf to (x,y) */
186 + int     x, y;
187 + {
188 +        register RTREE  *tp = &qtrunk;
189 +        RLEAF   *lp = NULL;
190 +        int     x0=0, y0=0, x1=odev.hres, y1=odev.vres;
191 +        int     mx, my;
192 +        register int    q;
193 +                                        /* check limits */
194 +        if (x < 0 || x >= odev.hres || y < 0 || y >= odev.vres)
195 +                return(NULL);
196 +                                        /* find nearby leaf in our tree */
197 +        for ( ; ; ) {
198 +                for (q = 0; q < 4; q++)         /* find any leaf this level */
199 +                        if (!(tp->flgs & BRF(q)) && tp->k[q].l != NULL) {
200 +                                lp = tp->k[q].l;
201 +                                break;
202 +                        }
203 +                q = 0;                          /* which quadrant are we? */
204 +                mx = (x0 + x1) >> 1;
205 +                my = (y0 + y1) >> 1;
206 +                if (x < mx) x1 = mx;
207 +                else {x0 = mx; q |= 01;}
208 +                if (y < my) y1 = my;
209 +                else {y0 = my; q |= 02;}
210 +                if (tp->flgs & BRF(q)) {        /* branch down if not a leaf */
211 +                        tp = tp->k[q].b;
212 +                        continue;
213 +                }
214 +                if (tp->k[q].l != NULL)         /* good shot! */
215 +                        return(tp->k[q].l);
216 +                return(lp);                     /* else return what we have */
217 +        }
218 + }
219 +
220 +
221   static
222   addleaf(lp)                     /* add a leaf to our tree */
223   RLEAF   *lp;
# Line 265 | Line 305 | qtReplant()                    /* replant our tree using new view */
305  
306          if (bleaf == tleaf)             /* anything to replant? */
307                  return;
308 <        freetwigs(0);                   /* blow the tree away */
308 >        qtFreeTree(0);                  /* blow the tree away */
309                                          /* now rebuild it */
310          for (i = bleaf; i != tleaf; ) {
311                  addleaf(leafpile+i);
# Line 394 | Line 434 | int    x0, y0, x1, y1;
434  
435          if (is_stump(&qtrunk))
436                  return;
437 <        if ((lim[0][0]=x0) == 0 & (lim[1][0]=y0) == 0 &
438 <                (lim[0][1]=x1) == odev.hres & (lim[1][1]=y1) == odev.vres ||
439 <                        tmTop->lumap == NULL)
440 <                tmComputeMapping(0., 0., 0.);
437 >        if ((lim[0][0]=x0) <= 0 & (lim[1][0]=y0) <= 0 &
438 >                (lim[0][1]=x1) >= odev.hres-1 & (lim[1][1]=y1) >= odev.vres-1
439 >                        || tmTop->lumap == NULL)
440 >                if (tmComputeMapping(0., 0., 0.) != TM_E_OK)
441 >                        return;
442          redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
443   }
444  

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines