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

Comparing src/hd/rhd_qtree.c (file contents):
Revision 3.1 by gregl, Wed Nov 19 18:01:03 1997 UTC vs.
Revision 3.6 by gregl, Mon Nov 24 15:16:10 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  
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 –
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  
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 58 | Line 57 | memerr:
57   }
58  
59  
60 < static
62 < freetwigs(really)               /* free allocated twigs */
60 > qtFreeTree(really)              /* free allocated twigs */
61   int     really;
62   {
63          register int    i;
64  
65 <        if (tmTop != NULL)
68 <                tmClearHisto();
69 <        bzero((char *)&qtrunk, sizeof(RTREE));
65 >        qtrunk.flgs = CH_ANY;
66          nexttwig = 0;
67          if (twigbundle == NULL)
68                  return;
# Line 83 | Line 79 | int    really;
79   }
80  
81  
82 < static RLEAF *
82 > static int
83   newleaf()                       /* allocate a leaf from our pile */
84   {
85 <        if (tleaf++ >= nleaves)         /* get next leaf in ring */
86 <                tleaf = 0;
87 <        if (tleaf == bleaf)             /* need to shake some free */
85 >        int     li;
86 >        
87 >        li = qtL.tl++;
88 >        if (qtL.tl >= qtL.nl)   /* get next leaf in ring */
89 >                qtL.tl = 0;
90 >        if (qtL.tl == qtL.bl)   /* need to shake some free */
91                  qtCompost(LFREEPCT);
92 <        return(leafpile + tleaf);
92 >        return(li);
93   }
94  
95  
96 + #define LEAFSIZ         (3*sizeof(float)+sizeof(TMbright)+6*sizeof(BYTE))
97 +
98   int
99   qtAllocLeaves(n)                /* allocate space for n leaves */
100 < int     n;
100 > register int    n;
101   {
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)
109 <                return(nleaves);
110 <        else if (nleaves > 0)
111 <                free((char *)leafpile);
108 >        if (qtL.nl >= n)
109 >                return(qtL.nl);
110 >        else if (qtL.nl > 0)
111 >                free(qtL.base);
112                                  /* round space up to nearest power of 2 */
113 <        nbytes = n*sizeof(RLEAF) + 8;
113 >        nbytes = n*LEAFSIZ + 8;
114          for (i = 1024; nbytes > i; i <<= 1)
115                  ;
116 <        n = (i - 8) / sizeof(RLEAF);
117 <        leafpile = (RLEAF *)malloc(n*sizeof(RLEAF));
118 <        if (leafpile == NULL)
119 <                return(-1);
120 <        nleaves = n;
121 <        bleaf = tleaf = 0;
122 <        return(nleaves);
116 >        n = (i - 8) / LEAFSIZ;  /* should we make sure n is even? */
117 >        qtL.base = (char *)malloc(n*LEAFSIZ);
118 >        if (qtL.base == NULL)
119 >                return(0);
120 >                                /* assign larger alignment types earlier */
121 >        qtL.wp = (float (*)[3])qtL.base;
122 >        qtL.brt = (TMbright *)(qtL.wp + n);
123 >        qtL.chr = (BYTE (*)[3])(qtL.brt + n);
124 >        qtL.rgb = (BYTE (*)[3])(qtL.chr + n);
125 >        qtL.nl = n;
126 >        qtL.tml = qtL.bl = qtL.tl = 0;
127 >        return(n);
128   }
129  
130 + #undef  LEAFSIZ
131  
132 +
133   qtFreeLeaves()                  /* free our allocated leaves and twigs */
134   {
135 <        freetwigs(1);           /* free tree also */
136 <        if (nleaves <= 0)
135 >        qtFreeTree(1);          /* free tree also */
136 >        if (qtL.nl <= 0)
137                  return;
138 <        free((char *)leafpile);
139 <        leafpile = NULL;
140 <        nleaves = 0;
138 >        free(qtL.base);
139 >        qtL.base = NULL;
140 >        qtL.nl = 0;
141   }
142  
143  
# Line 141 | Line 149 | register RTREE *tp;
149  
150          for (i = 0; i < 4; i++)
151                  if (tp->flgs & BRF(i)) {
152 <                        if (shaketree(tp->k[i].b))
153 <                                tp->flgs |= CHF(i);
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 <                                tp->flgs |= CHF(i);
153 <                        }
152 >                        shaketree(tp->k[i].b);
153 >                        if (is_stump(tp->k[i].b))
154 >                                tp->flgs &= ~BRF(i);
155 >                } else if (tp->flgs & LFF(i)) {
156 >                        li = tp->k[i].li;
157 >                        if (qtL.bl < qtL.tl ?
158 >                                (li < qtL.bl || li >= qtL.tl) :
159 >                                (li < qtL.bl && li >= qtL.tl))
160 >                                tp->flgs &= ~LFF(i);
161                  }
155 –        return(tp->flgs & CH_ANY);
162   }
163  
164  
# Line 160 | Line 166 | int
166   qtCompost(pct)                  /* free up some leaves */
167   int     pct;
168   {
169 <        int     nused, nclear;
169 >        int     nused, nclear, nmapped;
170 >
171                                  /* figure out how many leaves to clear */
172 <        nclear = nleaves * pct / 100;
172 >        nclear = qtL.nl * pct / 100;
173 >        nused = qtL.tl - qtL.bl;
174 >        if (nused <= 0) nused += qtL.nl;
175 >        nclear -= qtL.nl - nused;
176          if (nclear <= 0)
177                  return(0);
168 –        nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf;
178          if (nclear >= nused) {  /* clear them all */
179 <                freetwigs(0);
180 <                bleaf = tleaf = 0;
179 >                qtFreeTree(0);
180 >                qtL.tml = qtL.bl = qtL.tl = 0;
181                  return(nused);
182          }
183                                  /* else clear leaves from bottom */
184 <        bleaf = (bleaf + nclear) % nleaves;
184 >        nmapped = qtL.tml - qtL.bl;
185 >        if (nmapped < 0) nmapped += qtL.nl;
186 >        qtL.bl += nclear;
187 >        if (qtL.bl >= qtL.nl) qtL.bl -= qtL.nl;
188 >        if (nmapped <= nclear) qtL.tml = qtL.bl;
189          shaketree(&qtrunk);
190          return(nclear);
191   }
192  
193  
194 + int
195 + qtFindLeaf(x, y)                /* find closest leaf to (x,y) */
196 + int     x, y;
197 + {
198 +        register RTREE  *tp = &qtrunk;
199 +        int     li = -1;
200 +        int     x0=0, y0=0, x1=odev.hres, y1=odev.vres;
201 +        int     mx, my;
202 +        register int    q;
203 +                                        /* check limits */
204 +        if (x < 0 || x >= odev.hres || y < 0 || y >= odev.vres)
205 +                return(-1);
206 +                                        /* find nearby leaf in our tree */
207 +        for ( ; ; ) {
208 +                for (q = 0; q < 4; q++)         /* find any leaf this level */
209 +                        if (tp->flgs & LFF(q)) {
210 +                                li = tp->k[q].li;
211 +                                break;
212 +                        }
213 +                q = 0;                          /* which quadrant are we? */
214 +                mx = (x0 + x1) >> 1;
215 +                my = (y0 + y1) >> 1;
216 +                if (x < mx) x1 = mx;
217 +                else {x0 = mx; q |= 01;}
218 +                if (y < my) y1 = my;
219 +                else {y0 = my; q |= 02;}
220 +                if (tp->flgs & BRF(q)) {        /* branch down if not a leaf */
221 +                        tp = tp->k[q].b;
222 +                        continue;
223 +                }
224 +                if (tp->flgs & LFF(q))          /* good shot! */
225 +                        return(tp->k[q].li);
226 +                return(li);                     /* else return what we have */
227 +        }
228 + }
229 +
230 +
231   static
232 < addleaf(lp)                     /* add a leaf to our tree */
233 < RLEAF   *lp;
232 > addleaf(li)                     /* add a leaf to our tree */
233 > int     li;
234   {
235          register RTREE  *tp = &qtrunk;
236          int     x0=0, y0=0, x1=odev.hres, y1=odev.vres;
237 <        RLEAF   *lo = NULL;
237 >        int     lo = -1;
238          int     x, y, mx, my;
239          double  z;
240          FVECT   ip, wp;
241          register int    q;
242                                          /* compute leaf location */
243 <        VCOPY(wp, lp->wp);
243 >        VCOPY(wp, qtL.wp[li]);
244          viewloc(ip, &odev.v, wp);
245          if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
246                          || ip[1] < 0. || ip[1] >= 1.)
# Line 212 | Line 262 | RLEAF  *lp;
262                          tp = tp->k[q].b;
263                          continue;
264                  }
265 <                if (tp->k[q].l == NULL) {       /* found stem for leaf */
266 <                        tp->k[q].l = lp;
267 <                        tp->flgs |= CHF(q);
265 >                if (!(tp->flgs & LFF(q))) {     /* found stem for leaf */
266 >                        tp->k[q].li = li;
267 >                        tp->flgs |= CHLFF(q);
268                          break;
269                  }      
270                                                  /* check existing leaf */
271 <                if (lo != tp->k[q].l) {
272 <                        lo = tp->k[q].l;
273 <                        VCOPY(wp, lo->wp);
271 >                if (lo != tp->k[q].li) {
272 >                        lo = tp->k[q].li;
273 >                        VCOPY(wp, qtL.wp[lo]);
274                          viewloc(ip, &odev.v, wp);
275                  }
276                                                  /* is node minimum size? */
277                  if (x1-x0 <= qtMinNodesiz || y1-y0 <= qtMinNodesiz) {
278                          if (z > (1.-qtDepthEps)*ip[2])  /* who is closer? */
279                                  return;                 /* old one is */
280 <                        tp->k[q].l = lp;                /* new one is */
280 >                        tp->k[q].li = li;               /* new one is */
281                          tp->flgs |= CHF(q);
232 –                        tmAddHisto(&lo->brt, 1, -1);    /* drop old one */
282                          break;
283                  }
284 <                tp->flgs |= CHBRF(q);           /* else grow tree */
284 >                tp->flgs &= ~LFF(q);            /* else grow tree */
285 >                tp->flgs |= CHBRF(q);
286                  tp = tp->k[q].b = newtwig();
237 –                tp->flgs |= CH_ANY;             /* all new */
287                  q = 0;                          /* old leaf -> new branch */
288                  mx = ip[0] * odev.hres;
289                  my = ip[1] * odev.vres;
290                  if (mx >= (x0 + x1) >> 1) q |= 01;
291                  if (my >= (y0 + y1) >> 1) q |= 02;
292 <                tp->k[q].l = lo;
292 >                tp->k[q].li = lo;
293 >                tp->flgs |= LFF(q)|CH_ANY;      /* all new */
294          }
245 –        tmAddHisto(&lp->brt, 1, 1);     /* add leaf to histogram */
295   }
296  
297  
# Line 250 | Line 299 | dev_value(c, p)                        /* add a pixel value to our output q
299   COLR    c;
300   FVECT   p;
301   {
302 <        register RLEAF  *lp;
302 >        register int    li;
303  
304 <        lp = newleaf();
305 <        VCOPY(lp->wp, p);
306 <        tmCvColrs(&lp->brt, lp->chr, c, 1);
307 <        addleaf(lp);
304 >        li = newleaf();
305 >        VCOPY(qtL.wp[li], p);
306 >        tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1);
307 >        addleaf(li);
308   }
309  
310  
311   qtReplant()                     /* replant our tree using new view */
312   {
313          register int    i;
314 <
315 <        if (bleaf == tleaf)             /* anything to replant? */
314 >                                        /* anything to replant? */
315 >        if (qtL.bl == qtL.tl)
316                  return;
317 <        freetwigs(0);                   /* blow the tree away */
318 <                                        /* now rebuild it */
319 <        for (i = bleaf; i != tleaf; ) {
320 <                addleaf(leafpile+i);
321 <                if (++i >= nleaves) i = 0;
317 >        qtFreeTree(0);                  /* blow the old tree away */
318 >                                        /* regrow it in new place */
319 >        for (i = qtL.bl; i != qtL.tl; ) {
320 >                addleaf(i);
321 >                if (++i >= qtL.nl) i = 0;
322          }
274 –        tmComputeMapping(0., 0., 0.);   /* update the display */
275 –        qtUpdate();
323   }
324  
325  
326 + qtMapLeaves(redo)               /* map our leaves to RGB */
327 + int     redo;
328 + {
329 +        int     aorg, alen, borg, blen;
330 +                                        /* recompute mapping? */
331 +        if (redo)
332 +                qtL.tml = qtL.bl;
333 +                                        /* already done? */
334 +        if (qtL.tml == qtL.tl)
335 +                return(1);
336 +                                        /* compute segments */
337 +        aorg = qtL.tml;
338 +        if (qtL.tl >= aorg) {
339 +                alen = qtL.tl - aorg;
340 +                blen = 0;
341 +        } else {
342 +                alen = qtL.nl - aorg;
343 +                borg = 0;
344 +                blen = qtL.tl;
345 +        }
346 +                                        /* (re)compute tone mapping? */
347 +        if (qtL.tml == qtL.bl) {
348 +                tmClearHisto();
349 +                tmAddHisto(qtL.brt+aorg, alen, 1);
350 +                if (blen > 0)
351 +                        tmAddHisto(qtL.brt+borg, blen, 1);
352 +                if (tmComputeMapping(0., 0., 0.) != TM_E_OK)
353 +                        return(0);
354 +        }
355 +        if (tmMapPixels(qtL.rgb+aorg, qtL.brt+aorg,
356 +                        qtL.chr+aorg, alen) != TM_E_OK)
357 +                return(0);
358 +        if (blen > 0)
359 +                tmMapPixels(qtL.rgb+borg, qtL.brt+borg,
360 +                                qtL.chr+borg, blen);
361 +        qtL.tml = qtL.tl;
362 +        return(1);
363 + }
364 +
365 +
366   static
367   redraw(ca, tp, x0, y0, x1, y1, l)       /* redraw portion of a tree */
368   BYTE    ca[3];          /* returned average color */
# Line 284 | Line 371 | int    x0, y0, x1, y1;
371   int     l[2][2];
372   {
373          int     csm[3], nc;
374 +        register BYTE   *cp;
375          BYTE    rgb[3];
376          int     quads = CH_ANY;
377          int     mx, my;
# Line 304 | Line 392 | int    l[2][2];
392          csm[0] = csm[1] = csm[2] = nc = 0;
393                                          /* do leaves first */
394          for (i = 0; i < 4; i++)
395 <                if (quads & CHF(i) && !(tp->flgs & BRF(i)) &&
396 <                                tp->k[i].l != NULL) {
397 <                        tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1);
310 <                        dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0,
395 >                if (quads & CHF(i) && tp->flgs & LFF(i)) {
396 >                        dev_paintr(cp=qtL.rgb[tp->k[i].li],
397 >                                        i&01 ? mx : x0, i&02 ? my : y0,
398                                          i&01 ? x1 : mx, i&02 ? y1 : my);
399 <                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
399 >                        csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
400                          nc++;
401                          quads &= ~CHF(i);
402                  }
# Line 343 | Line 430 | register RTREE *tp;
430   int     x0, y0, x1, y1;
431   {
432          int     csm[3], nc;
433 +        register BYTE   *cp;
434          BYTE    rgb[3];
435          int     gaps = 0;
436          int     mx, my;
# Line 352 | Line 440 | int    x0, y0, x1, y1;
440          my = (y0 + y1) >> 1;
441          csm[0] = csm[1] = csm[2] = nc = 0;
442                                          /* do leaves first */
443 <        for (i = 0; i < 4; i++)
444 <                if ((tp->flgs & CHBRF(i)) == CHF(i)) {
445 <                        if (tp->k[i].l == NULL) {
446 <                                gaps |= 1<<i;   /* empty stem */
447 <                                continue;
448 <                        }
361 <                        tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1);
362 <                        dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0,
443 >        for (i = 0; i < 4; i++) {
444 >                if (!(tp->flgs & CHF(i)))
445 >                        continue;
446 >                if (tp->flgs & LFF(i)) {
447 >                        dev_paintr(cp=qtL.rgb[tp->k[i].li],
448 >                                        i&01 ? mx : x0, i&02 ? my : y0,
449                                          i&01 ? x1 : mx, i&02 ? y1 : my);
450 <                        csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
450 >                        csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
451                          nc++;
452 <                }
452 >                } else if (!(tp->flgs & BRF(i)))
453 >                        gaps |= 1<<i;   /* empty stem */
454 >        }
455                                          /* now do branches */
456          for (i = 0; i < 4; i++)
457                  if ((tp->flgs & CHBRF(i)) == CHBRF(i)) {
# Line 386 | Line 474 | int    x0, y0, x1, y1;
474   }
475  
476  
477 < qtRedraw(x0, y0, x1, y1)        /* redraw part of our screen */
477 > qtRedraw(x0, y0, x1, y1)        /* redraw part or all of our screen */
478   int     x0, y0, x1, y1;
479   {
480          int     lim[2][2];
# Line 394 | Line 482 | int    x0, y0, x1, y1;
482  
483          if (is_stump(&qtrunk))
484                  return;
485 <        if ((lim[0][0]=x0) == 0 & (lim[1][0]=y0) == 0 &
486 <                (lim[0][1]=x1) == odev.hres & (lim[1][1]=y1) == odev.vres ||
487 <                        tmTop->lumap == NULL)
400 <                tmComputeMapping(0., 0., 0.);
485 >        if (!qtMapLeaves((lim[0][0]=x0) <= 0 & (lim[1][0]=y0) <= 0 &
486 >                (lim[0][1]=x1) >= odev.hres-1 & (lim[1][1]=y1) >= odev.vres-1))
487 >                return;
488          redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
489   }
490  
# Line 408 | Line 495 | qtUpdate()                     /* update our tree display */
495  
496          if (is_stump(&qtrunk))
497                  return;
498 <        if (tmTop->lumap == NULL)
499 <                tmComputeMapping(0., 0., 0.);
498 >        if (!qtMapLeaves(0))
499 >                return;
500          update(ca, &qtrunk, 0, 0, odev.hres, odev.vres);
501   }

Diff Legend

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