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.4 by gregl, Fri Nov 21 09:52:06 1997 UTC vs.
Revision 3.5 by gregl, Fri Nov 21 13:35:57 1997 UTC

# Line 14 | Line 14 | static char SCCSid[] = "$SunId$ SGI";
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 + struct rleaves  qtL;            /* our pile of leaves */
18  
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 –
19   #define TBUNDLESIZ      409     /* number of twigs in a bundle */
20  
21   static RTREE    **twigbundle;   /* free twig blocks (NULL term.) */
22   static int      nexttwig;       /* next free twig */
23  
24 < static RTREE    emptytree;      /* empty tree for test below */
24 > #define is_stump(t)     (!((t)->flgs & (BR_ANY|LF_ANY)))
25  
29 – #define is_stump(t)     (!bcmp((char *)(t), (char *)&emptytree, sizeof(RTREE)))
26  
31 –
27   static RTREE *
28   newtwig()                       /* allocate a twig */
29   {
# Line 63 | Line 58 | int    really;
58   {
59          register int    i;
60  
61 <        tmClearHisto();
67 <        bzero((char *)&qtrunk, sizeof(RTREE));
61 >        qtrunk.flgs = 0;
62          nexttwig = 0;
63          if (twigbundle == NULL)
64                  return;
# Line 81 | Line 75 | int    really;
75   }
76  
77  
78 < static RLEAF *
78 > static int
79   newleaf()                       /* allocate a leaf from our pile */
80   {
81 <        RLEAF   *lp;
81 >        int     li;
82          
83 <        lp = leafpile + tleaf++;
84 <        if (tleaf >= nleaves)           /* get next leaf in ring */
85 <                tleaf = 0;
86 <        if (tleaf == bleaf)             /* need to shake some free */
83 >        li = qtL.tl++;
84 >        if (qtL.tl >= qtL.nl)   /* get next leaf in ring */
85 >                qtL.tl = 0;
86 >        if (qtL.tl == qtL.bl)   /* need to shake some free */
87                  qtCompost(LFREEPCT);
88 <        return(lp);
88 >        return(li);
89   }
90  
91  
92 + #define LEAFSIZ         (3*sizeof(float)+sizeof(TMbright)+6*sizeof(BYTE))
93 +
94   int
95   qtAllocLeaves(n)                /* allocate space for n leaves */
96 < int     n;
96 > register int    n;
97   {
98          unsigned        nbytes;
99          register unsigned       i;
# Line 105 | Line 101 | int    n;
101          qtFreeTree(0);          /* make sure tree is empty */
102          if (n <= 0)
103                  return(0);
104 <        if (nleaves >= n)
105 <                return(nleaves);
106 <        else if (nleaves > 0)
107 <                free((char *)leafpile);
104 >        if (qtL.nl >= n)
105 >                return(qtL.nl);
106 >        else if (qtL.nl > 0)
107 >                free(qtL.base);
108                                  /* round space up to nearest power of 2 */
109 <        nbytes = n*sizeof(RLEAF) + 8;
109 >        nbytes = n*LEAFSIZ + 8;
110          for (i = 1024; nbytes > i; i <<= 1)
111                  ;
112 <        n = (i - 8) / sizeof(RLEAF);
113 <        leafpile = (RLEAF *)malloc(n*sizeof(RLEAF));
114 <        if (leafpile == NULL)
115 <                return(-1);
116 <        nleaves = n;
117 <        bleaf = tleaf = 0;
118 <        return(nleaves);
112 >        n = (i - 8) / LEAFSIZ;  /* should we make sure n is even? */
113 >        qtL.base = (char *)malloc(n*LEAFSIZ);
114 >        if (qtL.base == NULL)
115 >                return(0);
116 >                                /* assign larger alignment types earlier */
117 >        qtL.wp = (float (*)[3])qtL.base;
118 >        qtL.brt = (TMbright *)(qtL.wp + n);
119 >        qtL.chr = (BYTE (*)[3])(qtL.brt + n);
120 >        qtL.rgb = (BYTE (*)[3])(qtL.chr + n);
121 >        qtL.nl = n;
122 >        qtL.tml = qtL.bl = qtL.tl = 0;
123 >        return(n);
124   }
125  
126 + #undef  LEAFSIZ
127  
128 +
129   qtFreeLeaves()                  /* free our allocated leaves and twigs */
130   {
131          qtFreeTree(1);          /* free tree also */
132 <        if (nleaves <= 0)
132 >        if (qtL.nl <= 0)
133                  return;
134 <        free((char *)leafpile);
135 <        leafpile = NULL;
136 <        nleaves = 0;
134 >        free(qtL.base);
135 >        qtL.base = NULL;
136 >        qtL.nl = 0;
137   }
138  
139  
# Line 141 | Line 144 | register RTREE *tp;
144          register int    i, li;
145  
146          for (i = 0; i < 4; i++)
147 <                if (tp->flgs & BRF(i))
147 >                if (tp->flgs & BRF(i)) {
148                          shaketree(tp->k[i].b);
149 <                else if (tp->k[i].l != NULL) {
150 <                        li = tp->k[i].l - leafpile;
151 <                        if (bleaf < tleaf ? (li < bleaf || li >= tleaf) :
152 <                                        (li < bleaf && li >= tleaf)) {
153 <                                tmAddHisto(&tp->k[i].l->brt, 1, -1);
154 <                                tp->k[i].l = NULL;
155 <                        }
149 >                        if (is_stump(tp->k[i].b))
150 >                                tp->flgs &= ~BRF(i);
151 >                } else if (tp->flgs & LFF(i)) {
152 >                        li = tp->k[i].li;
153 >                        if (qtL.bl < qtL.tl ?
154 >                                (li < qtL.bl || li >= qtL.tl) :
155 >                                (li < qtL.bl && li >= qtL.tl))
156 >                                tp->flgs &= ~LFF(i);
157                  }
158   }
159  
# Line 158 | Line 162 | int
162   qtCompost(pct)                  /* free up some leaves */
163   int     pct;
164   {
165 <        int     nused, nclear;
165 >        int     nused, nclear, nmapped;
166  
163 –        if (is_stump(&qtrunk))
164 –                return(0);
167                                  /* figure out how many leaves to clear */
168 <        nclear = nleaves * pct / 100;
169 <        nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf;
170 <        nclear -= nleaves - nused;      /* less what's already free */
168 >        nclear = qtL.nl * pct / 100;
169 >        nused = qtL.tl - qtL.bl;
170 >        if (nused <= 0) nused += qtL.nl;
171 >        nclear -= qtL.nl - nused;
172          if (nclear <= 0)
173                  return(0);
174          if (nclear >= nused) {  /* clear them all */
175                  qtFreeTree(0);
176 <                bleaf = tleaf = 0;
176 >                qtL.tml = qtL.bl = qtL.tl = 0;
177                  return(nused);
178          }
179                                  /* else clear leaves from bottom */
180 <        bleaf += nclear;
181 <        if (bleaf >= nleaves) bleaf -= nleaves;
180 >        nmapped = qtL.tml - qtL.bl;
181 >        if (nmapped < 0) nmapped += qtL.nl;
182 >        qtL.bl += nclear;
183 >        if (qtL.bl >= qtL.nl) qtL.bl -= qtL.nl;
184 >        if (nmapped <= nclear) qtL.tml = qtL.bl;
185          shaketree(&qtrunk);
186          return(nclear);
187   }
188  
189  
190 < RLEAF *
190 > int
191   qtFindLeaf(x, y)                /* find closest leaf to (x,y) */
192   int     x, y;
193   {
194          register RTREE  *tp = &qtrunk;
195 <        RLEAF   *lp = NULL;
195 >        int     li = -1;
196          int     x0=0, y0=0, x1=odev.hres, y1=odev.vres;
197          int     mx, my;
198          register int    q;
199                                          /* check limits */
200          if (x < 0 || x >= odev.hres || y < 0 || y >= odev.vres)
201 <                return(NULL);
201 >                return(-1);
202                                          /* find nearby leaf in our tree */
203          for ( ; ; ) {
204                  for (q = 0; q < 4; q++)         /* find any leaf this level */
205 <                        if (!(tp->flgs & BRF(q)) && tp->k[q].l != NULL) {
206 <                                lp = tp->k[q].l;
205 >                        if (tp->flgs & LFF(q)) {
206 >                                li = tp->k[q].li;
207                                  break;
208                          }
209                  q = 0;                          /* which quadrant are we? */
# Line 211 | Line 217 | int    x, y;
217                          tp = tp->k[q].b;
218                          continue;
219                  }
220 <                if (tp->k[q].l != NULL)         /* good shot! */
221 <                        return(tp->k[q].l);
222 <                return(lp);                     /* else return what we have */
220 >                if (tp->flgs & LFF(q))          /* good shot! */
221 >                        return(tp->k[q].li);
222 >                return(li);                     /* else return what we have */
223          }
224   }
225  
226  
227   static
228 < addleaf(lp)                     /* add a leaf to our tree */
229 < RLEAF   *lp;
228 > addleaf(li)                     /* add a leaf to our tree */
229 > int     li;
230   {
231          register RTREE  *tp = &qtrunk;
232          int     x0=0, y0=0, x1=odev.hres, y1=odev.vres;
233 <        RLEAF   *lo = NULL;
233 >        int     lo = -1;
234          int     x, y, mx, my;
235          double  z;
236          FVECT   ip, wp;
237          register int    q;
238                                          /* compute leaf location */
239 <        VCOPY(wp, lp->wp);
239 >        VCOPY(wp, qtL.wp[li]);
240          viewloc(ip, &odev.v, wp);
241          if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
242                          || ip[1] < 0. || ip[1] >= 1.)
# Line 252 | Line 258 | RLEAF  *lp;
258                          tp = tp->k[q].b;
259                          continue;
260                  }
261 <                if (tp->k[q].l == NULL) {       /* found stem for leaf */
262 <                        tp->k[q].l = lp;
263 <                        tp->flgs |= CHF(q);
261 >                if (!(tp->flgs & LFF(q))) {     /* found stem for leaf */
262 >                        tp->k[q].li = li;
263 >                        tp->flgs |= CHLFF(q);
264                          break;
265                  }      
266                                                  /* check existing leaf */
267 <                if (lo != tp->k[q].l) {
268 <                        lo = tp->k[q].l;
269 <                        VCOPY(wp, lo->wp);
267 >                if (lo != tp->k[q].li) {
268 >                        lo = tp->k[q].li;
269 >                        VCOPY(wp, qtL.wp[lo]);
270                          viewloc(ip, &odev.v, wp);
271                  }
272                                                  /* is node minimum size? */
273                  if (x1-x0 <= qtMinNodesiz || y1-y0 <= qtMinNodesiz) {
274                          if (z > (1.-qtDepthEps)*ip[2])  /* who is closer? */
275                                  return;                 /* old one is */
276 <                        tp->k[q].l = lp;                /* new one is */
276 >                        tp->k[q].li = li;               /* new one is */
277                          tp->flgs |= CHF(q);
272 –                        tmAddHisto(&lo->brt, 1, -1);    /* drop old one */
278                          break;
279                  }
280 <                tp->flgs |= CHBRF(q);           /* else grow tree */
280 >                tp->flgs &= ~LFF(q);            /* else grow tree */
281 >                tp->flgs |= CHBRF(q);
282                  tp = tp->k[q].b = newtwig();
277 –                tp->flgs |= CH_ANY;             /* all new */
283                  q = 0;                          /* old leaf -> new branch */
284                  mx = ip[0] * odev.hres;
285                  my = ip[1] * odev.vres;
286                  if (mx >= (x0 + x1) >> 1) q |= 01;
287                  if (my >= (y0 + y1) >> 1) q |= 02;
288 <                tp->k[q].l = lo;
288 >                tp->k[q].li = lo;
289 >                tp->flgs |= LFF(q)|CH_ANY;      /* all new */
290          }
285 –        tmAddHisto(&lp->brt, 1, 1);     /* add leaf to histogram */
291   }
292  
293  
# Line 290 | Line 295 | dev_value(c, p)                        /* add a pixel value to our output q
295   COLR    c;
296   FVECT   p;
297   {
298 <        register RLEAF  *lp;
298 >        register int    li;
299  
300 <        lp = newleaf();
301 <        VCOPY(lp->wp, p);
302 <        tmCvColrs(&lp->brt, lp->chr, c, 1);
303 <        addleaf(lp);
300 >        li = newleaf();
301 >        VCOPY(qtL.wp[li], p);
302 >        tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1);
303 >        addleaf(li);
304   }
305  
306  
307   qtReplant()                     /* replant our tree using new view */
308   {
309          register int    i;
310 <
311 <        if (bleaf == tleaf)             /* anything to replant? */
310 >                                        /* anything to replant? */
311 >        if (qtL.bl == qtL.tl)
312                  return;
313 <        qtFreeTree(0);                  /* blow the tree away */
314 <                                        /* now rebuild it */
315 <        for (i = bleaf; i != tleaf; ) {
316 <                addleaf(leafpile+i);
317 <                if (++i >= nleaves) i = 0;
313 >        qtFreeTree(0);                  /* blow the old tree away */
314 >                                        /* regrow it in new place */
315 >        for (i = qtL.bl; i != qtL.tl; ) {
316 >                addleaf(i);
317 >                if (++i >= qtL.nl) i = 0;
318          }
314 –        tmComputeMapping(0., 0., 0.);   /* update the display */
315 –        qtUpdate();
319   }
320  
321  
322 + qtMapLeaves(redo)               /* map our leaves to RGB */
323 + int     redo;
324 + {
325 +        int     aorg, alen, borg, blen;
326 +                                        /* already done? */
327 +        if (qtL.tml == qtL.tl)
328 +                return(1);
329 +        if (redo)
330 +                qtL.tml = qtL.bl;
331 +                                        /* compute segments */
332 +        aorg = qtL.tml;
333 +        if (qtL.tl >= aorg) {
334 +                alen = qtL.tl - aorg;
335 +                blen = 0;
336 +        } else {
337 +                alen = qtL.nl - aorg;
338 +                borg = 0;
339 +                blen = qtL.tl;
340 +        }
341 +                                        /* (re)compute tone mapping? */
342 +        if (qtL.tml == qtL.bl) {
343 +                tmClearHisto();
344 +                tmAddHisto(qtL.brt+aorg, alen, 1);
345 +                if (blen > 0)
346 +                        tmAddHisto(qtL.brt+borg, blen, 1);
347 +                if (tmComputeMapping(0., 0., 0.) != TM_E_OK)
348 +                        return(0);
349 +        }
350 +        if (tmMapPixels(qtL.rgb+aorg, qtL.brt+aorg,
351 +                        qtL.chr+aorg, alen) != TM_E_OK)
352 +                return(0);
353 +        if (blen > 0)
354 +                tmMapPixels(qtL.rgb+borg, qtL.brt+borg,
355 +                                qtL.chr+borg, blen);
356 +        qtL.tml = qtL.tl;
357 +        return(1);
358 + }
359 +
360 +
361   static
362   redraw(ca, tp, x0, y0, x1, y1, l)       /* redraw portion of a tree */
363   BYTE    ca[3];          /* returned average color */
# Line 324 | Line 366 | int    x0, y0, x1, y1;
366   int     l[2][2];
367   {
368          int     csm[3], nc;
369 +        register BYTE   *cp;
370          BYTE    rgb[3];
371          int     quads = CH_ANY;
372          int     mx, my;
# Line 344 | Line 387 | int    l[2][2];
387          csm[0] = csm[1] = csm[2] = nc = 0;
388                                          /* do leaves first */
389          for (i = 0; i < 4; i++)
390 <                if (quads & CHF(i) && !(tp->flgs & BRF(i)) &&
391 <                                tp->k[i].l != NULL) {
392 <                        tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1);
350 <                        dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0,
390 >                if (quads & CHF(i) && tp->flgs & LFF(i)) {
391 >                        dev_paintr(cp=qtL.rgb[tp->k[i].li],
392 >                                        i&01 ? mx : x0, i&02 ? my : y0,
393                                          i&01 ? x1 : mx, i&02 ? y1 : my);
394 <                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
394 >                        csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
395                          nc++;
396                          quads &= ~CHF(i);
397                  }
# Line 383 | Line 425 | register RTREE *tp;
425   int     x0, y0, x1, y1;
426   {
427          int     csm[3], nc;
428 +        register BYTE   *cp;
429          BYTE    rgb[3];
430          int     gaps = 0;
431          int     mx, my;
# Line 392 | Line 435 | int    x0, y0, x1, y1;
435          my = (y0 + y1) >> 1;
436          csm[0] = csm[1] = csm[2] = nc = 0;
437                                          /* do leaves first */
438 <        for (i = 0; i < 4; i++)
439 <                if ((tp->flgs & CHBRF(i)) == CHF(i)) {
440 <                        if (tp->k[i].l == NULL) {
441 <                                gaps |= 1<<i;   /* empty stem */
442 <                                continue;
443 <                        }
401 <                        tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1);
402 <                        dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0,
438 >        for (i = 0; i < 4; i++) {
439 >                if (!(tp->flgs & CHF(i)))
440 >                        continue;
441 >                if (tp->flgs & LFF(i)) {
442 >                        dev_paintr(cp=qtL.rgb[tp->k[i].li],
443 >                                        i&01 ? mx : x0, i&02 ? my : y0,
444                                          i&01 ? x1 : mx, i&02 ? y1 : my);
445 <                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
445 >                        csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
446                          nc++;
447 <                }
447 >                } else if (!(tp->flgs & BRF(i)))
448 >                        gaps |= 1<<i;   /* empty stem */
449 >        }
450                                          /* now do branches */
451          for (i = 0; i < 4; i++)
452                  if ((tp->flgs & CHBRF(i)) == CHBRF(i)) {
# Line 426 | Line 469 | int    x0, y0, x1, y1;
469   }
470  
471  
472 < qtRedraw(x0, y0, x1, y1)        /* redraw part of our screen */
472 > qtRedraw(x0, y0, x1, y1)        /* redraw part or all of our screen */
473   int     x0, y0, x1, y1;
474   {
475          int     lim[2][2];
# Line 434 | Line 477 | int    x0, y0, x1, y1;
477  
478          if (is_stump(&qtrunk))
479                  return;
480 <        if ((lim[0][0]=x0) <= 0 & (lim[1][0]=y0) <= 0 &
481 <                (lim[0][1]=x1) >= odev.hres-1 & (lim[1][1]=y1) >= odev.vres-1
482 <                        || tmTop->lumap == NULL)
440 <                if (tmComputeMapping(0., 0., 0.) != TM_E_OK)
441 <                        return;
480 >        if (!qtMapLeaves((lim[0][0]=x0) <= 0 & (lim[1][0]=y0) <= 0 &
481 >                (lim[0][1]=x1) >= odev.hres-1 & (lim[1][1]=y1) >= odev.vres-1))
482 >                return;
483          redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
484   }
485  
# Line 449 | Line 490 | qtUpdate()                     /* update our tree display */
490  
491          if (is_stump(&qtrunk))
492                  return;
493 <        if (tmTop->lumap == NULL)
494 <                tmComputeMapping(0., 0., 0.);
493 >        if (!qtMapLeaves(0))
494 >                return;
495          update(ca, &qtrunk, 0, 0, odev.hres, odev.vres);
496   }

Diff Legend

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