ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhd_qtree.c
Revision: 3.6
Committed: Mon Nov 24 15:16:10 1997 UTC (26 years, 10 months ago) by gregl
Content type: text/plain
Branch: MAIN
Changes since 3.5: +8 -3 lines
Log Message:
moved LFREEPCT to rhd_qtree.c and changed from 15% to 25%
fixed bug in trunk flag settings in qtFreeTree()
fixed bug in tone remapping routine

File Contents

# User Rev Content
1 gregl 3.1 /* Copyright (c) 1997 Silicon Graphics, Inc. */
2    
3     #ifndef lint
4     static char SCCSid[] = "$SunId$ SGI";
5     #endif
6    
7     /*
8     * Quadtree driver support routines.
9     */
10    
11     #include "standard.h"
12     #include "rhd_qtree.h"
13 gregl 3.6 /* quantity of leaves to free at a time */
14     #ifndef LFREEPCT
15     #define LFREEPCT 25
16     #endif
17 gregl 3.1
18 gregl 3.2 RTREE qtrunk; /* our quadtree trunk */
19     double qtDepthEps = .02; /* epsilon to compare depths (z fraction) */
20     int qtMinNodesiz = 2; /* minimum node dimension (pixels) */
21 gregl 3.5 struct rleaves qtL; /* our pile of leaves */
22 gregl 3.2
23 gregl 3.1 #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 gregl 3.5 #define is_stump(t) (!((t)->flgs & (BR_ANY|LF_ANY)))
29 gregl 3.1
30    
31     static RTREE *
32     newtwig() /* allocate a twig */
33     {
34     register int bi;
35    
36     if (twigbundle == NULL) { /* initialize */
37     twigbundle = (RTREE **)malloc(sizeof(RTREE *));
38     if (twigbundle == NULL)
39     goto memerr;
40     twigbundle[0] = NULL;
41     }
42     bi = nexttwig / TBUNDLESIZ;
43     if (twigbundle[bi] == NULL) { /* new block */
44     twigbundle = (RTREE **)realloc((char *)twigbundle,
45     (bi+2)*sizeof(RTREE *));
46     if (twigbundle == NULL)
47     goto memerr;
48     twigbundle[bi] = (RTREE *)calloc(TBUNDLESIZ, sizeof(RTREE));
49     if (twigbundle[bi] == NULL)
50     goto memerr;
51     twigbundle[bi+1] = NULL;
52     }
53     /* nexttwig++ % TBUNDLESIZ */
54     return(twigbundle[bi] + (nexttwig++ - bi*TBUNDLESIZ));
55     memerr:
56     error(SYSTEM, "out of memory in newtwig");
57     }
58    
59    
60 gregl 3.3 qtFreeTree(really) /* free allocated twigs */
61 gregl 3.1 int really;
62     {
63     register int i;
64    
65 gregl 3.6 qtrunk.flgs = CH_ANY;
66 gregl 3.1 nexttwig = 0;
67     if (twigbundle == NULL)
68     return;
69     if (!really) { /* just clear allocated blocks */
70     for (i = 0; twigbundle[i] != NULL; i++)
71     bzero((char *)twigbundle[i], TBUNDLESIZ*sizeof(RTREE));
72     return;
73     }
74     /* else "really" means free up memory */
75     for (i = 0; twigbundle[i] != NULL; i++)
76     free((char *)twigbundle[i]);
77     free((char *)twigbundle);
78     twigbundle = NULL;
79     }
80    
81    
82 gregl 3.5 static int
83 gregl 3.1 newleaf() /* allocate a leaf from our pile */
84     {
85 gregl 3.5 int li;
86 gregl 3.4
87 gregl 3.5 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 gregl 3.1 qtCompost(LFREEPCT);
92 gregl 3.5 return(li);
93 gregl 3.1 }
94    
95    
96 gregl 3.5 #define LEAFSIZ (3*sizeof(float)+sizeof(TMbright)+6*sizeof(BYTE))
97    
98 gregl 3.1 int
99     qtAllocLeaves(n) /* allocate space for n leaves */
100 gregl 3.5 register int n;
101 gregl 3.1 {
102     unsigned nbytes;
103     register unsigned i;
104    
105 gregl 3.3 qtFreeTree(0); /* make sure tree is empty */
106 gregl 3.1 if (n <= 0)
107     return(0);
108 gregl 3.5 if (qtL.nl >= n)
109     return(qtL.nl);
110     else if (qtL.nl > 0)
111     free(qtL.base);
112 gregl 3.1 /* round space up to nearest power of 2 */
113 gregl 3.5 nbytes = n*LEAFSIZ + 8;
114 gregl 3.1 for (i = 1024; nbytes > i; i <<= 1)
115     ;
116 gregl 3.5 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 gregl 3.1 }
129    
130 gregl 3.5 #undef LEAFSIZ
131 gregl 3.1
132 gregl 3.5
133 gregl 3.1 qtFreeLeaves() /* free our allocated leaves and twigs */
134     {
135 gregl 3.3 qtFreeTree(1); /* free tree also */
136 gregl 3.5 if (qtL.nl <= 0)
137 gregl 3.1 return;
138 gregl 3.5 free(qtL.base);
139     qtL.base = NULL;
140     qtL.nl = 0;
141 gregl 3.1 }
142    
143    
144     static
145     shaketree(tp) /* shake dead leaves from tree */
146     register RTREE *tp;
147     {
148     register int i, li;
149    
150     for (i = 0; i < 4; i++)
151 gregl 3.5 if (tp->flgs & BRF(i)) {
152 gregl 3.2 shaketree(tp->k[i].b);
153 gregl 3.5 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 gregl 3.1 }
162     }
163    
164    
165     int
166     qtCompost(pct) /* free up some leaves */
167     int pct;
168     {
169 gregl 3.5 int nused, nclear, nmapped;
170 gregl 3.4
171 gregl 3.1 /* figure out how many leaves to clear */
172 gregl 3.5 nclear = qtL.nl * pct / 100;
173     nused = qtL.tl - qtL.bl;
174     if (nused <= 0) nused += qtL.nl;
175     nclear -= qtL.nl - nused;
176 gregl 3.1 if (nclear <= 0)
177     return(0);
178     if (nclear >= nused) { /* clear them all */
179 gregl 3.3 qtFreeTree(0);
180 gregl 3.5 qtL.tml = qtL.bl = qtL.tl = 0;
181 gregl 3.1 return(nused);
182     }
183     /* else clear leaves from bottom */
184 gregl 3.5 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 gregl 3.1 shaketree(&qtrunk);
190     return(nclear);
191     }
192    
193    
194 gregl 3.5 int
195 gregl 3.3 qtFindLeaf(x, y) /* find closest leaf to (x,y) */
196     int x, y;
197     {
198     register RTREE *tp = &qtrunk;
199 gregl 3.5 int li = -1;
200 gregl 3.3 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 gregl 3.5 return(-1);
206 gregl 3.3 /* find nearby leaf in our tree */
207     for ( ; ; ) {
208     for (q = 0; q < 4; q++) /* find any leaf this level */
209 gregl 3.5 if (tp->flgs & LFF(q)) {
210     li = tp->k[q].li;
211 gregl 3.3 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 gregl 3.5 if (tp->flgs & LFF(q)) /* good shot! */
225     return(tp->k[q].li);
226     return(li); /* else return what we have */
227 gregl 3.3 }
228     }
229    
230    
231 gregl 3.1 static
232 gregl 3.5 addleaf(li) /* add a leaf to our tree */
233     int li;
234 gregl 3.1 {
235     register RTREE *tp = &qtrunk;
236     int x0=0, y0=0, x1=odev.hres, y1=odev.vres;
237 gregl 3.5 int lo = -1;
238 gregl 3.1 int x, y, mx, my;
239     double z;
240     FVECT ip, wp;
241     register int q;
242     /* compute leaf location */
243 gregl 3.5 VCOPY(wp, qtL.wp[li]);
244 gregl 3.1 viewloc(ip, &odev.v, wp);
245     if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
246     || ip[1] < 0. || ip[1] >= 1.)
247     return;
248     x = ip[0] * odev.hres;
249     y = ip[1] * odev.vres;
250     z = ip[2];
251     /* find the place for it */
252     for ( ; ; ) {
253     q = 0; /* which quadrant? */
254     mx = (x0 + x1) >> 1;
255     my = (y0 + y1) >> 1;
256     if (x < mx) x1 = mx;
257     else {x0 = mx; q |= 01;}
258     if (y < my) y1 = my;
259     else {y0 = my; q |= 02;}
260     if (tp->flgs & BRF(q)) { /* move to next branch */
261     tp->flgs |= CHF(q); /* not sure; guess */
262     tp = tp->k[q].b;
263     continue;
264     }
265 gregl 3.5 if (!(tp->flgs & LFF(q))) { /* found stem for leaf */
266     tp->k[q].li = li;
267     tp->flgs |= CHLFF(q);
268 gregl 3.1 break;
269     }
270     /* check existing leaf */
271 gregl 3.5 if (lo != tp->k[q].li) {
272     lo = tp->k[q].li;
273     VCOPY(wp, qtL.wp[lo]);
274 gregl 3.1 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 gregl 3.5 tp->k[q].li = li; /* new one is */
281 gregl 3.1 tp->flgs |= CHF(q);
282     break;
283     }
284 gregl 3.5 tp->flgs &= ~LFF(q); /* else grow tree */
285     tp->flgs |= CHBRF(q);
286 gregl 3.1 tp = tp->k[q].b = newtwig();
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 gregl 3.5 tp->k[q].li = lo;
293     tp->flgs |= LFF(q)|CH_ANY; /* all new */
294 gregl 3.1 }
295     }
296    
297    
298     dev_value(c, p) /* add a pixel value to our output queue */
299     COLR c;
300     FVECT p;
301     {
302 gregl 3.5 register int li;
303 gregl 3.1
304 gregl 3.5 li = newleaf();
305     VCOPY(qtL.wp[li], p);
306     tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1);
307     addleaf(li);
308 gregl 3.1 }
309    
310    
311     qtReplant() /* replant our tree using new view */
312     {
313     register int i;
314 gregl 3.5 /* anything to replant? */
315     if (qtL.bl == qtL.tl)
316 gregl 3.1 return;
317 gregl 3.5 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 gregl 3.1 }
323     }
324    
325    
326 gregl 3.5 qtMapLeaves(redo) /* map our leaves to RGB */
327     int redo;
328     {
329     int aorg, alen, borg, blen;
330 gregl 3.6 /* recompute mapping? */
331     if (redo)
332     qtL.tml = qtL.bl;
333 gregl 3.5 /* 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 gregl 3.1 static
367     redraw(ca, tp, x0, y0, x1, y1, l) /* redraw portion of a tree */
368     BYTE ca[3]; /* returned average color */
369     register RTREE *tp;
370     int x0, y0, x1, y1;
371     int l[2][2];
372     {
373     int csm[3], nc;
374 gregl 3.5 register BYTE *cp;
375 gregl 3.1 BYTE rgb[3];
376     int quads = CH_ANY;
377     int mx, my;
378     register int i;
379     /* compute midpoint */
380     mx = (x0 + x1) >> 1;
381     my = (y0 + y1) >> 1;
382     /* see what to do */
383     if (l[0][0] >= mx)
384     quads &= ~(CHF(2)|CHF(0));
385     else if (l[0][1] <= mx)
386     quads &= ~(CHF(3)|CHF(1));
387     if (l[1][0] >= my)
388     quads &= ~(CHF(1)|CHF(0));
389     else if (l[1][1] <= my)
390     quads &= ~(CHF(3)|CHF(2));
391     tp->flgs &= ~quads; /* mark them done */
392     csm[0] = csm[1] = csm[2] = nc = 0;
393     /* do leaves first */
394     for (i = 0; i < 4; i++)
395 gregl 3.5 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 gregl 3.1 i&01 ? x1 : mx, i&02 ? y1 : my);
399 gregl 3.5 csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
400 gregl 3.1 nc++;
401     quads &= ~CHF(i);
402     }
403     /* now do branches */
404     for (i = 0; i < 4; i++)
405     if (quads & CHF(i) && tp->flgs & BRF(i)) {
406     redraw(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
407     i&01 ? x1 : mx, i&02 ? y1 : my, l);
408     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
409     nc++;
410     quads &= ~CHF(i);
411     }
412     if (nc > 1) {
413     ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
414     } else {
415     ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
416     }
417     if (!quads) return;
418     /* fill in gaps with average */
419     for (i = 0; i < 4; i++)
420     if (quads & CHF(i))
421     dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
422     i&01 ? x1 : mx, i&02 ? y1 : my);
423     }
424    
425    
426     static
427     update(ca, tp, x0, y0, x1, y1) /* update tree display as needed */
428     BYTE ca[3]; /* returned average color */
429     register RTREE *tp;
430     int x0, y0, x1, y1;
431     {
432     int csm[3], nc;
433 gregl 3.5 register BYTE *cp;
434 gregl 3.1 BYTE rgb[3];
435     int gaps = 0;
436     int mx, my;
437     register int i;
438     /* compute midpoint */
439     mx = (x0 + x1) >> 1;
440     my = (y0 + y1) >> 1;
441     csm[0] = csm[1] = csm[2] = nc = 0;
442     /* do leaves first */
443 gregl 3.5 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 gregl 3.1 i&01 ? x1 : mx, i&02 ? y1 : my);
450 gregl 3.5 csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
451 gregl 3.1 nc++;
452 gregl 3.5 } else if (!(tp->flgs & BRF(i)))
453     gaps |= 1<<i; /* empty stem */
454     }
455 gregl 3.1 /* now do branches */
456     for (i = 0; i < 4; i++)
457     if ((tp->flgs & CHBRF(i)) == CHBRF(i)) {
458     update(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
459     i&01 ? x1 : mx, i&02 ? y1 : my);
460     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
461     nc++;
462     }
463     if (nc > 1) {
464     ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
465     } else {
466     ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
467     }
468     /* fill in gaps with average */
469     for (i = 0; gaps && i < 4; gaps >>= 1, i++)
470     if (gaps & 01)
471     dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
472     i&01 ? x1 : mx, i&02 ? y1 : my);
473     tp->flgs &= ~CH_ANY; /* all done */
474     }
475    
476    
477 gregl 3.5 qtRedraw(x0, y0, x1, y1) /* redraw part or all of our screen */
478 gregl 3.1 int x0, y0, x1, y1;
479     {
480     int lim[2][2];
481     BYTE ca[3];
482    
483     if (is_stump(&qtrunk))
484     return;
485 gregl 3.5 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 gregl 3.1 redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
489     }
490    
491    
492     qtUpdate() /* update our tree display */
493     {
494     BYTE ca[3];
495    
496     if (is_stump(&qtrunk))
497     return;
498 gregl 3.5 if (!qtMapLeaves(0))
499     return;
500 gregl 3.1 update(ca, &qtrunk, 0, 0, odev.hres, odev.vres);
501     }