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.3 by gregl, Thu Nov 20 18:03:43 1997 UTC vs.
Revision 3.8 by gregl, Tue Nov 25 14:24:39 1997 UTC

# Line 10 | Line 10 | static char SCCSid[] = "$SunId$ SGI";
10  
11   #include "standard.h"
12   #include "rhd_qtree.h"
13 +                                /* quantity of leaves to free at a time */
14 + #ifndef LFREEPCT
15 + #define LFREEPCT        25
16 + #endif
17  
18   RTREE   qtrunk;                 /* our quadtree trunk */
19   double  qtDepthEps = .02;       /* epsilon to compare depths (z fraction) */
20   int     qtMinNodesiz = 2;       /* minimum node dimension (pixels) */
21 + struct rleaves  qtL;            /* our pile of leaves */
22  
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 –
23   #define TBUNDLESIZ      409     /* number of twigs in a bundle */
24  
25   static RTREE    **twigbundle;   /* free twig blocks (NULL term.) */
26   static int      nexttwig;       /* next free twig */
27  
28 < static RTREE    emptytree;      /* empty tree for test below */
28 > #define is_stump(t)     (!((t)->flgs & (BR_ANY|LF_ANY)))
29  
29 – #define is_stump(t)     (!bcmp((char *)(t), (char *)&emptytree, sizeof(RTREE)))
30  
31 –
31   static RTREE *
32   newtwig()                       /* allocate a twig */
33   {
# Line 63 | Line 62 | int    really;
62   {
63          register int    i;
64  
65 <        if (tmTop != NULL)
67 <                tmClearHisto();
68 <        bzero((char *)&qtrunk, sizeof(RTREE));
69 <        nexttwig = 0;
65 >        qtrunk.flgs = CH_ANY;   /* chop down tree */
66          if (twigbundle == NULL)
67                  return;
68 +        i = (TBUNDLESIZ-1+nexttwig)/TBUNDLESIZ;
69 +        nexttwig = 0;
70          if (!really) {          /* just clear allocated blocks */
71 <                for (i = 0; twigbundle[i] != NULL; i++)
71 >                while (i--)
72                          bzero((char *)twigbundle[i], TBUNDLESIZ*sizeof(RTREE));
73                  return;
74          }
# Line 82 | Line 80 | int    really;
80   }
81  
82  
83 < static RLEAF *
83 > static int
84   newleaf()                       /* allocate a leaf from our pile */
85   {
86 <        if (tleaf++ >= nleaves)         /* get next leaf in ring */
87 <                tleaf = 0;
88 <        if (tleaf == bleaf)             /* need to shake some free */
86 >        int     li;
87 >        
88 >        li = qtL.tl++;
89 >        if (qtL.tl >= qtL.nl)   /* get next leaf in ring */
90 >                qtL.tl = 0;
91 >        if (qtL.tl == qtL.bl)   /* need to shake some free */
92                  qtCompost(LFREEPCT);
93 <        return(leafpile + tleaf);
93 >        return(li);
94   }
95  
96  
97 + #define LEAFSIZ         (3*sizeof(float)+sizeof(TMbright)+6*sizeof(BYTE))
98 +
99   int
100   qtAllocLeaves(n)                /* allocate space for n leaves */
101 < int     n;
101 > register int    n;
102   {
103          unsigned        nbytes;
104          register unsigned       i;
# Line 103 | Line 106 | int    n;
106          qtFreeTree(0);          /* make sure tree is empty */
107          if (n <= 0)
108                  return(0);
109 <        if (nleaves >= n)
110 <                return(nleaves);
111 <        else if (nleaves > 0)
112 <                free((char *)leafpile);
109 >        if (qtL.nl >= n)
110 >                return(qtL.nl);
111 >        else if (qtL.nl > 0)
112 >                free(qtL.base);
113                                  /* round space up to nearest power of 2 */
114 <        nbytes = n*sizeof(RLEAF) + 8;
114 >        nbytes = n*LEAFSIZ + 8;
115          for (i = 1024; nbytes > i; i <<= 1)
116                  ;
117 <        n = (i - 8) / sizeof(RLEAF);
118 <        leafpile = (RLEAF *)malloc(n*sizeof(RLEAF));
119 <        if (leafpile == NULL)
120 <                return(-1);
121 <        nleaves = n;
122 <        bleaf = tleaf = 0;
123 <        return(nleaves);
117 >        n = (i - 8) / LEAFSIZ;  /* should we make sure n is even? */
118 >        qtL.base = (char *)malloc(n*LEAFSIZ);
119 >        if (qtL.base == NULL)
120 >                return(0);
121 >                                /* assign larger alignment types earlier */
122 >        qtL.wp = (float (*)[3])qtL.base;
123 >        qtL.brt = (TMbright *)(qtL.wp + n);
124 >        qtL.chr = (BYTE (*)[3])(qtL.brt + n);
125 >        qtL.rgb = (BYTE (*)[3])(qtL.chr + n);
126 >        qtL.nl = n;
127 >        qtL.tml = qtL.bl = qtL.tl = 0;
128 >        return(n);
129   }
130  
131 + #undef  LEAFSIZ
132  
133 +
134   qtFreeLeaves()                  /* free our allocated leaves and twigs */
135   {
136          qtFreeTree(1);          /* free tree also */
137 <        if (nleaves <= 0)
137 >        if (qtL.nl <= 0)
138                  return;
139 <        free((char *)leafpile);
140 <        leafpile = NULL;
141 <        nleaves = 0;
139 >        free(qtL.base);
140 >        qtL.base = NULL;
141 >        qtL.nl = 0;
142   }
143  
144  
# Line 139 | Line 149 | register RTREE *tp;
149          register int    i, li;
150  
151          for (i = 0; i < 4; i++)
152 <                if (tp->flgs & BRF(i))
152 >                if (tp->flgs & BRF(i)) {
153                          shaketree(tp->k[i].b);
154 <                else if (tp->k[i].l != NULL) {
155 <                        li = tp->k[i].l - leafpile;
156 <                        if (bleaf < tleaf ? (li < bleaf || li >= tleaf) :
157 <                                        (li < bleaf && li >= tleaf)) {
158 <                                tmAddHisto(&tp->k[i].l->brt, 1, -1);
159 <                                tp->k[i].l = NULL;
160 <                        }
154 >                        if (is_stump(tp->k[i].b))
155 >                                tp->flgs &= ~BRF(i);
156 >                } else if (tp->flgs & LFF(i)) {
157 >                        li = tp->k[i].li;
158 >                        if (qtL.bl < qtL.tl ?
159 >                                (li < qtL.bl || li >= qtL.tl) :
160 >                                (li < qtL.bl && li >= qtL.tl))
161 >                                tp->flgs &= ~LFF(i);
162                  }
163   }
164  
# Line 156 | Line 167 | int
167   qtCompost(pct)                  /* free up some leaves */
168   int     pct;
169   {
170 <        int     nused, nclear;
170 >        int     nused, nclear, nmapped;
171 >
172                                  /* figure out how many leaves to clear */
173 <        nclear = nleaves * pct / 100;
173 >        nclear = qtL.nl * pct / 100;
174 >        nused = qtL.tl - qtL.bl;
175 >        if (nused <= 0) nused += qtL.nl;
176 >        nclear -= qtL.nl - nused;
177          if (nclear <= 0)
178                  return(0);
164 –        nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf;
179          if (nclear >= nused) {  /* clear them all */
180                  qtFreeTree(0);
181 <                bleaf = tleaf = 0;
181 >                qtL.tml = qtL.bl = qtL.tl = 0;
182                  return(nused);
183          }
184                                  /* else clear leaves from bottom */
185 <        bleaf = (bleaf + nclear) % nleaves;
185 >        nmapped = qtL.tml - qtL.bl;
186 >        if (nmapped < 0) nmapped += qtL.nl;
187 >        qtL.bl += nclear;
188 >        if (qtL.bl >= qtL.nl) qtL.bl -= qtL.nl;
189 >        if (nmapped <= nclear) qtL.tml = qtL.bl;
190          shaketree(&qtrunk);
191          return(nclear);
192   }
193  
194  
195 < RLEAF *
195 > int
196   qtFindLeaf(x, y)                /* find closest leaf to (x,y) */
197   int     x, y;
198   {
199          register RTREE  *tp = &qtrunk;
200 <        RLEAF   *lp = NULL;
200 >        int     li = -1;
201          int     x0=0, y0=0, x1=odev.hres, y1=odev.vres;
202          int     mx, my;
203          register int    q;
204                                          /* check limits */
205          if (x < 0 || x >= odev.hres || y < 0 || y >= odev.vres)
206 <                return(NULL);
206 >                return(-1);
207                                          /* find nearby leaf in our tree */
208          for ( ; ; ) {
209                  for (q = 0; q < 4; q++)         /* find any leaf this level */
210 <                        if (!(tp->flgs & BRF(q)) && tp->k[q].l != NULL) {
211 <                                lp = tp->k[q].l;
210 >                        if (tp->flgs & LFF(q)) {
211 >                                li = tp->k[q].li;
212                                  break;
213                          }
214                  q = 0;                          /* which quadrant are we? */
# Line 204 | Line 222 | int    x, y;
222                          tp = tp->k[q].b;
223                          continue;
224                  }
225 <                if (tp->k[q].l != NULL)         /* good shot! */
226 <                        return(tp->k[q].l);
227 <                return(lp);                     /* else return what we have */
225 >                if (tp->flgs & LFF(q))          /* good shot! */
226 >                        return(tp->k[q].li);
227 >                return(li);                     /* else return what we have */
228          }
229   }
230  
231  
232   static
233 < addleaf(lp)                     /* add a leaf to our tree */
234 < RLEAF   *lp;
233 > addleaf(li)                     /* add a leaf to our tree */
234 > int     li;
235   {
236          register RTREE  *tp = &qtrunk;
237          int     x0=0, y0=0, x1=odev.hres, y1=odev.vres;
238 <        RLEAF   *lo = NULL;
238 >        int     lo = -1;
239          int     x, y, mx, my;
240          double  z;
241          FVECT   ip, wp;
242          register int    q;
243                                          /* compute leaf location */
244 <        VCOPY(wp, lp->wp);
244 >        VCOPY(wp, qtL.wp[li]);
245          viewloc(ip, &odev.v, wp);
246          if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
247                          || ip[1] < 0. || ip[1] >= 1.)
# Line 245 | Line 263 | RLEAF  *lp;
263                          tp = tp->k[q].b;
264                          continue;
265                  }
266 <                if (tp->k[q].l == NULL) {       /* found stem for leaf */
267 <                        tp->k[q].l = lp;
268 <                        tp->flgs |= CHF(q);
266 >                if (!(tp->flgs & LFF(q))) {     /* found stem for leaf */
267 >                        tp->k[q].li = li;
268 >                        tp->flgs |= CHLFF(q);
269                          break;
270                  }      
271                                                  /* check existing leaf */
272 <                if (lo != tp->k[q].l) {
273 <                        lo = tp->k[q].l;
274 <                        VCOPY(wp, lo->wp);
272 >                if (lo != tp->k[q].li) {
273 >                        lo = tp->k[q].li;
274 >                        VCOPY(wp, qtL.wp[lo]);
275                          viewloc(ip, &odev.v, wp);
276                  }
277                                                  /* is node minimum size? */
278                  if (x1-x0 <= qtMinNodesiz || y1-y0 <= qtMinNodesiz) {
279                          if (z > (1.-qtDepthEps)*ip[2])  /* who is closer? */
280                                  return;                 /* old one is */
281 <                        tp->k[q].l = lp;                /* new one is */
281 >                        tp->k[q].li = li;               /* new one is */
282                          tp->flgs |= CHF(q);
265 –                        tmAddHisto(&lo->brt, 1, -1);    /* drop old one */
283                          break;
284                  }
285 <                tp->flgs |= CHBRF(q);           /* else grow tree */
285 >                tp->flgs &= ~LFF(q);            /* else grow tree */
286 >                tp->flgs |= CHBRF(q);
287                  tp = tp->k[q].b = newtwig();
270 –                tp->flgs |= CH_ANY;             /* all new */
288                  q = 0;                          /* old leaf -> new branch */
289                  mx = ip[0] * odev.hres;
290                  my = ip[1] * odev.vres;
291                  if (mx >= (x0 + x1) >> 1) q |= 01;
292                  if (my >= (y0 + y1) >> 1) q |= 02;
293 <                tp->k[q].l = lo;
293 >                tp->k[q].li = lo;
294 >                tp->flgs |= LFF(q)|CH_ANY;      /* all new */
295          }
278 –        tmAddHisto(&lp->brt, 1, 1);     /* add leaf to histogram */
296   }
297  
298  
# Line 283 | Line 300 | dev_value(c, p)                        /* add a pixel value to our output q
300   COLR    c;
301   FVECT   p;
302   {
303 <        register RLEAF  *lp;
303 >        register int    li;
304  
305 <        lp = newleaf();
306 <        VCOPY(lp->wp, p);
307 <        tmCvColrs(&lp->brt, lp->chr, c, 1);
308 <        addleaf(lp);
305 >        li = newleaf();
306 >        VCOPY(qtL.wp[li], p);
307 >        tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1);
308 >        addleaf(li);
309   }
310  
311  
312   qtReplant()                     /* replant our tree using new view */
313   {
314          register int    i;
315 <
316 <        if (bleaf == tleaf)             /* anything to replant? */
315 >                                        /* anything to replant? */
316 >        if (qtL.bl == qtL.tl)
317                  return;
318 <        qtFreeTree(0);                  /* blow the tree away */
319 <                                        /* now rebuild it */
320 <        for (i = bleaf; i != tleaf; ) {
321 <                addleaf(leafpile+i);
322 <                if (++i >= nleaves) i = 0;
318 >        qtFreeTree(0);                  /* blow the old tree away */
319 >                                        /* regrow it in new place */
320 >        for (i = qtL.bl; i != qtL.tl; ) {
321 >                addleaf(i);
322 >                if (++i >= qtL.nl) i = 0;
323          }
307 –        tmComputeMapping(0., 0., 0.);   /* update the display */
308 –        qtUpdate();
324   }
325  
326  
327 + qtMapLeaves(redo)               /* map our leaves to RGB */
328 + int     redo;
329 + {
330 +        int     aorg, alen, borg, blen;
331 +                                        /* recompute mapping? */
332 +        if (redo)
333 +                qtL.tml = qtL.bl;
334 +                                        /* already done? */
335 +        if (qtL.tml == qtL.tl)
336 +                return(1);
337 +                                        /* compute segments */
338 +        aorg = qtL.tml;
339 +        if (qtL.tl >= aorg) {
340 +                alen = qtL.tl - aorg;
341 +                blen = 0;
342 +        } else {
343 +                alen = qtL.nl - aorg;
344 +                borg = 0;
345 +                blen = qtL.tl;
346 +        }
347 +                                        /* (re)compute tone mapping? */
348 +        if (qtL.tml == qtL.bl) {
349 +                tmClearHisto();
350 +                tmAddHisto(qtL.brt+aorg, alen, 1);
351 +                if (blen > 0)
352 +                        tmAddHisto(qtL.brt+borg, blen, 1);
353 +                if (tmComputeMapping(0., 0., 0.) != TM_E_OK)
354 +                        return(0);
355 +        }
356 +        if (tmMapPixels(qtL.rgb+aorg, qtL.brt+aorg,
357 +                        qtL.chr+aorg, alen) != TM_E_OK)
358 +                return(0);
359 +        if (blen > 0)
360 +                tmMapPixels(qtL.rgb+borg, qtL.brt+borg,
361 +                                qtL.chr+borg, blen);
362 +        qtL.tml = qtL.tl;
363 +        return(1);
364 + }
365 +
366 +
367   static
368 < redraw(ca, tp, x0, y0, x1, y1, l)       /* redraw portion of a tree */
314 < BYTE    ca[3];          /* returned average color */
368 > redraw(tp, x0, y0, x1, y1, l)   /* mark portion of a tree for redraw */
369   register RTREE  *tp;
370   int     x0, y0, x1, y1;
371   int     l[2][2];
372   {
319 –        int     csm[3], nc;
320 –        BYTE    rgb[3];
373          int     quads = CH_ANY;
374          int     mx, my;
375          register int    i;
# Line 327 | Line 379 | int    l[2][2];
379                                          /* see what to do */
380          if (l[0][0] >= mx)
381                  quads &= ~(CHF(2)|CHF(0));
382 <        else if (l[0][1] <= mx)
382 >        else if (l[0][1] < mx)
383                  quads &= ~(CHF(3)|CHF(1));
384          if (l[1][0] >= my)
385                  quads &= ~(CHF(1)|CHF(0));
386 <        else if (l[1][1] <= my)
386 >        else if (l[1][1] < my)
387                  quads &= ~(CHF(3)|CHF(2));
388 <        tp->flgs &= ~quads;             /* mark them done */
389 <        csm[0] = csm[1] = csm[2] = nc = 0;
338 <                                        /* do leaves first */
388 >        tp->flgs |= quads;              /* mark quadrants for update */
389 >                                        /* climb the branches */
390          for (i = 0; i < 4; i++)
391 <                if (quads & CHF(i) && !(tp->flgs & BRF(i)) &&
392 <                                tp->k[i].l != NULL) {
342 <                        tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1);
343 <                        dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0,
344 <                                        i&01 ? x1 : mx, i&02 ? y1 : my);
345 <                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
346 <                        nc++;
347 <                        quads &= ~CHF(i);
348 <                }
349 <                                        /* now do branches */
350 <        for (i = 0; i < 4; i++)
351 <                if (quads & CHF(i) && tp->flgs & BRF(i)) {
352 <                        redraw(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
391 >                if (tp->flgs & BRF(i) && quads & CHF(i))
392 >                        redraw(tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
393                                          i&01 ? x1 : mx, i&02 ? y1 : my, l);
354 –                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
355 –                        nc++;
356 –                        quads &= ~CHF(i);
357 –                }
358 –        if (nc > 1) {
359 –                ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
360 –        } else {
361 –                ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
362 –        }
363 –        if (!quads) return;
364 –                                        /* fill in gaps with average */
365 –        for (i = 0; i < 4; i++)
366 –                if (quads & CHF(i))
367 –                        dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
368 –                                        i&01 ? x1 : mx, i&02 ? y1 : my);
394   }
395  
396  
# Line 376 | Line 401 | register RTREE *tp;
401   int     x0, y0, x1, y1;
402   {
403          int     csm[3], nc;
404 +        register BYTE   *cp;
405          BYTE    rgb[3];
406          int     gaps = 0;
407          int     mx, my;
# Line 385 | Line 411 | int    x0, y0, x1, y1;
411          my = (y0 + y1) >> 1;
412          csm[0] = csm[1] = csm[2] = nc = 0;
413                                          /* do leaves first */
414 <        for (i = 0; i < 4; i++)
415 <                if ((tp->flgs & CHBRF(i)) == CHF(i)) {
416 <                        if (tp->k[i].l == NULL) {
417 <                                gaps |= 1<<i;   /* empty stem */
392 <                                continue;
393 <                        }
394 <                        tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1);
395 <                        dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0,
396 <                                        i&01 ? x1 : mx, i&02 ? y1 : my);
397 <                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
414 >        for (i = 0; i < 4; i++) {
415 >                if (tp->flgs & LFF(i)) {
416 >                        cp = qtL.rgb[tp->k[i].li];
417 >                        csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
418                          nc++;
419 <                }
419 >                        if (tp->flgs & CHF(i))
420 >                                dev_paintr(cp, i&01 ? mx : x0, i&02 ? my : y0,
421 >                                               i&01 ? x1 : mx, i&02 ? y1 : my);
422 >                } else if ((tp->flgs & CHBRF(i)) == CHF(i))
423 >                        gaps |= 1<<i;   /* empty stem */
424 >        }
425                                          /* now do branches */
426          for (i = 0; i < 4; i++)
427                  if ((tp->flgs & CHBRF(i)) == CHBRF(i)) {
# Line 419 | Line 444 | int    x0, y0, x1, y1;
444   }
445  
446  
447 < qtRedraw(x0, y0, x1, y1)        /* redraw part of our screen */
447 > qtRedraw(x0, y0, x1, y1)        /* redraw part or all of our screen */
448   int     x0, y0, x1, y1;
449   {
450          int     lim[2][2];
426 –        BYTE    ca[3];
451  
452          if (is_stump(&qtrunk))
453                  return;
454 <        if ((lim[0][0]=x0) == 0 & (lim[1][0]=y0) == 0 &
455 <                (lim[0][1]=x1) == odev.hres & (lim[1][1]=y1) == odev.vres ||
456 <                        tmTop->lumap == NULL)
457 <                tmComputeMapping(0., 0., 0.);
434 <        redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
454 >        if (!qtMapLeaves((lim[0][0]=x0) <= 0 & (lim[1][0]=y0) <= 0 &
455 >                (lim[0][1]=x1) >= odev.hres-1 & (lim[1][1]=y1) >= odev.vres-1))
456 >                return;
457 >        redraw(&qtrunk, 0, 0, odev.hres, odev.vres, lim);
458   }
459  
460  
# Line 441 | Line 464 | qtUpdate()                     /* update our tree display */
464  
465          if (is_stump(&qtrunk))
466                  return;
467 <        if (tmTop->lumap == NULL)
468 <                tmComputeMapping(0., 0., 0.);
467 >        if (!qtMapLeaves(0))
468 >                return;
469          update(ca, &qtrunk, 0, 0, odev.hres, odev.vres);
470   }

Diff Legend

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