ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhd_qtree.c
Revision: 3.5
Committed: Fri Nov 21 13:35:57 1997 UTC (26 years, 10 months ago) by gregl
Content type: text/plain
Branch: MAIN
Changes since 3.4: +152 -111 lines
Log Message:
changed definition of global leaf pile to make tone mapping work better

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    
14 gregl 3.2 RTREE qtrunk; /* our quadtree trunk */
15     double qtDepthEps = .02; /* epsilon to compare depths (z fraction) */
16     int qtMinNodesiz = 2; /* minimum node dimension (pixels) */
17 gregl 3.5 struct rleaves qtL; /* our pile of leaves */
18 gregl 3.2
19 gregl 3.1 #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 gregl 3.5 #define is_stump(t) (!((t)->flgs & (BR_ANY|LF_ANY)))
25 gregl 3.1
26    
27     static RTREE *
28     newtwig() /* allocate a twig */
29     {
30     register int bi;
31    
32     if (twigbundle == NULL) { /* initialize */
33     twigbundle = (RTREE **)malloc(sizeof(RTREE *));
34     if (twigbundle == NULL)
35     goto memerr;
36     twigbundle[0] = NULL;
37     }
38     bi = nexttwig / TBUNDLESIZ;
39     if (twigbundle[bi] == NULL) { /* new block */
40     twigbundle = (RTREE **)realloc((char *)twigbundle,
41     (bi+2)*sizeof(RTREE *));
42     if (twigbundle == NULL)
43     goto memerr;
44     twigbundle[bi] = (RTREE *)calloc(TBUNDLESIZ, sizeof(RTREE));
45     if (twigbundle[bi] == NULL)
46     goto memerr;
47     twigbundle[bi+1] = NULL;
48     }
49     /* nexttwig++ % TBUNDLESIZ */
50     return(twigbundle[bi] + (nexttwig++ - bi*TBUNDLESIZ));
51     memerr:
52     error(SYSTEM, "out of memory in newtwig");
53     }
54    
55    
56 gregl 3.3 qtFreeTree(really) /* free allocated twigs */
57 gregl 3.1 int really;
58     {
59     register int i;
60    
61 gregl 3.5 qtrunk.flgs = 0;
62 gregl 3.1 nexttwig = 0;
63     if (twigbundle == NULL)
64     return;
65     if (!really) { /* just clear allocated blocks */
66     for (i = 0; twigbundle[i] != NULL; i++)
67     bzero((char *)twigbundle[i], TBUNDLESIZ*sizeof(RTREE));
68     return;
69     }
70     /* else "really" means free up memory */
71     for (i = 0; twigbundle[i] != NULL; i++)
72     free((char *)twigbundle[i]);
73     free((char *)twigbundle);
74     twigbundle = NULL;
75     }
76    
77    
78 gregl 3.5 static int
79 gregl 3.1 newleaf() /* allocate a leaf from our pile */
80     {
81 gregl 3.5 int li;
82 gregl 3.4
83 gregl 3.5 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 gregl 3.1 qtCompost(LFREEPCT);
88 gregl 3.5 return(li);
89 gregl 3.1 }
90    
91    
92 gregl 3.5 #define LEAFSIZ (3*sizeof(float)+sizeof(TMbright)+6*sizeof(BYTE))
93    
94 gregl 3.1 int
95     qtAllocLeaves(n) /* allocate space for n leaves */
96 gregl 3.5 register int n;
97 gregl 3.1 {
98     unsigned nbytes;
99     register unsigned i;
100    
101 gregl 3.3 qtFreeTree(0); /* make sure tree is empty */
102 gregl 3.1 if (n <= 0)
103     return(0);
104 gregl 3.5 if (qtL.nl >= n)
105     return(qtL.nl);
106     else if (qtL.nl > 0)
107     free(qtL.base);
108 gregl 3.1 /* round space up to nearest power of 2 */
109 gregl 3.5 nbytes = n*LEAFSIZ + 8;
110 gregl 3.1 for (i = 1024; nbytes > i; i <<= 1)
111     ;
112 gregl 3.5 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 gregl 3.1 }
125    
126 gregl 3.5 #undef LEAFSIZ
127 gregl 3.1
128 gregl 3.5
129 gregl 3.1 qtFreeLeaves() /* free our allocated leaves and twigs */
130     {
131 gregl 3.3 qtFreeTree(1); /* free tree also */
132 gregl 3.5 if (qtL.nl <= 0)
133 gregl 3.1 return;
134 gregl 3.5 free(qtL.base);
135     qtL.base = NULL;
136     qtL.nl = 0;
137 gregl 3.1 }
138    
139    
140     static
141     shaketree(tp) /* shake dead leaves from tree */
142     register RTREE *tp;
143     {
144     register int i, li;
145    
146     for (i = 0; i < 4; i++)
147 gregl 3.5 if (tp->flgs & BRF(i)) {
148 gregl 3.2 shaketree(tp->k[i].b);
149 gregl 3.5 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 gregl 3.1 }
158     }
159    
160    
161     int
162     qtCompost(pct) /* free up some leaves */
163     int pct;
164     {
165 gregl 3.5 int nused, nclear, nmapped;
166 gregl 3.4
167 gregl 3.1 /* figure out how many leaves to clear */
168 gregl 3.5 nclear = qtL.nl * pct / 100;
169     nused = qtL.tl - qtL.bl;
170     if (nused <= 0) nused += qtL.nl;
171     nclear -= qtL.nl - nused;
172 gregl 3.1 if (nclear <= 0)
173     return(0);
174     if (nclear >= nused) { /* clear them all */
175 gregl 3.3 qtFreeTree(0);
176 gregl 3.5 qtL.tml = qtL.bl = qtL.tl = 0;
177 gregl 3.1 return(nused);
178     }
179     /* else clear leaves from bottom */
180 gregl 3.5 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 gregl 3.1 shaketree(&qtrunk);
186     return(nclear);
187     }
188    
189    
190 gregl 3.5 int
191 gregl 3.3 qtFindLeaf(x, y) /* find closest leaf to (x,y) */
192     int x, y;
193     {
194     register RTREE *tp = &qtrunk;
195 gregl 3.5 int li = -1;
196 gregl 3.3 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 gregl 3.5 return(-1);
202 gregl 3.3 /* find nearby leaf in our tree */
203     for ( ; ; ) {
204     for (q = 0; q < 4; q++) /* find any leaf this level */
205 gregl 3.5 if (tp->flgs & LFF(q)) {
206     li = tp->k[q].li;
207 gregl 3.3 break;
208     }
209     q = 0; /* which quadrant are we? */
210     mx = (x0 + x1) >> 1;
211     my = (y0 + y1) >> 1;
212     if (x < mx) x1 = mx;
213     else {x0 = mx; q |= 01;}
214     if (y < my) y1 = my;
215     else {y0 = my; q |= 02;}
216     if (tp->flgs & BRF(q)) { /* branch down if not a leaf */
217     tp = tp->k[q].b;
218     continue;
219     }
220 gregl 3.5 if (tp->flgs & LFF(q)) /* good shot! */
221     return(tp->k[q].li);
222     return(li); /* else return what we have */
223 gregl 3.3 }
224     }
225    
226    
227 gregl 3.1 static
228 gregl 3.5 addleaf(li) /* add a leaf to our tree */
229     int li;
230 gregl 3.1 {
231     register RTREE *tp = &qtrunk;
232     int x0=0, y0=0, x1=odev.hres, y1=odev.vres;
233 gregl 3.5 int lo = -1;
234 gregl 3.1 int x, y, mx, my;
235     double z;
236     FVECT ip, wp;
237     register int q;
238     /* compute leaf location */
239 gregl 3.5 VCOPY(wp, qtL.wp[li]);
240 gregl 3.1 viewloc(ip, &odev.v, wp);
241     if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
242     || ip[1] < 0. || ip[1] >= 1.)
243     return;
244     x = ip[0] * odev.hres;
245     y = ip[1] * odev.vres;
246     z = ip[2];
247     /* find the place for it */
248     for ( ; ; ) {
249     q = 0; /* which quadrant? */
250     mx = (x0 + x1) >> 1;
251     my = (y0 + y1) >> 1;
252     if (x < mx) x1 = mx;
253     else {x0 = mx; q |= 01;}
254     if (y < my) y1 = my;
255     else {y0 = my; q |= 02;}
256     if (tp->flgs & BRF(q)) { /* move to next branch */
257     tp->flgs |= CHF(q); /* not sure; guess */
258     tp = tp->k[q].b;
259     continue;
260     }
261 gregl 3.5 if (!(tp->flgs & LFF(q))) { /* found stem for leaf */
262     tp->k[q].li = li;
263     tp->flgs |= CHLFF(q);
264 gregl 3.1 break;
265     }
266     /* check existing leaf */
267 gregl 3.5 if (lo != tp->k[q].li) {
268     lo = tp->k[q].li;
269     VCOPY(wp, qtL.wp[lo]);
270 gregl 3.1 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 gregl 3.5 tp->k[q].li = li; /* new one is */
277 gregl 3.1 tp->flgs |= CHF(q);
278     break;
279     }
280 gregl 3.5 tp->flgs &= ~LFF(q); /* else grow tree */
281     tp->flgs |= CHBRF(q);
282 gregl 3.1 tp = tp->k[q].b = newtwig();
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 gregl 3.5 tp->k[q].li = lo;
289     tp->flgs |= LFF(q)|CH_ANY; /* all new */
290 gregl 3.1 }
291     }
292    
293    
294     dev_value(c, p) /* add a pixel value to our output queue */
295     COLR c;
296     FVECT p;
297     {
298 gregl 3.5 register int li;
299 gregl 3.1
300 gregl 3.5 li = newleaf();
301     VCOPY(qtL.wp[li], p);
302     tmCvColrs(&qtL.brt[li], qtL.chr[li], c, 1);
303     addleaf(li);
304 gregl 3.1 }
305    
306    
307     qtReplant() /* replant our tree using new view */
308     {
309     register int i;
310 gregl 3.5 /* anything to replant? */
311     if (qtL.bl == qtL.tl)
312 gregl 3.1 return;
313 gregl 3.5 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 gregl 3.1 }
319     }
320    
321    
322 gregl 3.5 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 gregl 3.1 static
362     redraw(ca, tp, x0, y0, x1, y1, l) /* redraw portion of a tree */
363     BYTE ca[3]; /* returned average color */
364     register RTREE *tp;
365     int x0, y0, x1, y1;
366     int l[2][2];
367     {
368     int csm[3], nc;
369 gregl 3.5 register BYTE *cp;
370 gregl 3.1 BYTE rgb[3];
371     int quads = CH_ANY;
372     int mx, my;
373     register int i;
374     /* compute midpoint */
375     mx = (x0 + x1) >> 1;
376     my = (y0 + y1) >> 1;
377     /* see what to do */
378     if (l[0][0] >= mx)
379     quads &= ~(CHF(2)|CHF(0));
380     else if (l[0][1] <= mx)
381     quads &= ~(CHF(3)|CHF(1));
382     if (l[1][0] >= my)
383     quads &= ~(CHF(1)|CHF(0));
384     else if (l[1][1] <= my)
385     quads &= ~(CHF(3)|CHF(2));
386     tp->flgs &= ~quads; /* mark them done */
387     csm[0] = csm[1] = csm[2] = nc = 0;
388     /* do leaves first */
389     for (i = 0; i < 4; i++)
390 gregl 3.5 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 gregl 3.1 i&01 ? x1 : mx, i&02 ? y1 : my);
394 gregl 3.5 csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
395 gregl 3.1 nc++;
396     quads &= ~CHF(i);
397     }
398     /* now do branches */
399     for (i = 0; i < 4; i++)
400     if (quads & CHF(i) && tp->flgs & BRF(i)) {
401     redraw(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
402     i&01 ? x1 : mx, i&02 ? y1 : my, l);
403     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
404     nc++;
405     quads &= ~CHF(i);
406     }
407     if (nc > 1) {
408     ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
409     } else {
410     ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
411     }
412     if (!quads) return;
413     /* fill in gaps with average */
414     for (i = 0; i < 4; i++)
415     if (quads & CHF(i))
416     dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
417     i&01 ? x1 : mx, i&02 ? y1 : my);
418     }
419    
420    
421     static
422     update(ca, tp, x0, y0, x1, y1) /* update tree display as needed */
423     BYTE ca[3]; /* returned average color */
424     register RTREE *tp;
425     int x0, y0, x1, y1;
426     {
427     int csm[3], nc;
428 gregl 3.5 register BYTE *cp;
429 gregl 3.1 BYTE rgb[3];
430     int gaps = 0;
431     int mx, my;
432     register int i;
433     /* compute midpoint */
434     mx = (x0 + x1) >> 1;
435     my = (y0 + y1) >> 1;
436     csm[0] = csm[1] = csm[2] = nc = 0;
437     /* do leaves first */
438 gregl 3.5 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 gregl 3.1 i&01 ? x1 : mx, i&02 ? y1 : my);
445 gregl 3.5 csm[0] += cp[0]; csm[1] += cp[1]; csm[2] += cp[2];
446 gregl 3.1 nc++;
447 gregl 3.5 } else if (!(tp->flgs & BRF(i)))
448     gaps |= 1<<i; /* empty stem */
449     }
450 gregl 3.1 /* now do branches */
451     for (i = 0; i < 4; i++)
452     if ((tp->flgs & CHBRF(i)) == CHBRF(i)) {
453     update(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
454     i&01 ? x1 : mx, i&02 ? y1 : my);
455     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
456     nc++;
457     }
458     if (nc > 1) {
459     ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
460     } else {
461     ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
462     }
463     /* fill in gaps with average */
464     for (i = 0; gaps && i < 4; gaps >>= 1, i++)
465     if (gaps & 01)
466     dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
467     i&01 ? x1 : mx, i&02 ? y1 : my);
468     tp->flgs &= ~CH_ANY; /* all done */
469     }
470    
471    
472 gregl 3.5 qtRedraw(x0, y0, x1, y1) /* redraw part or all of our screen */
473 gregl 3.1 int x0, y0, x1, y1;
474     {
475     int lim[2][2];
476     BYTE ca[3];
477    
478     if (is_stump(&qtrunk))
479     return;
480 gregl 3.5 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 gregl 3.1 redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
484     }
485    
486    
487     qtUpdate() /* update our tree display */
488     {
489     BYTE ca[3];
490    
491     if (is_stump(&qtrunk))
492     return;
493 gregl 3.5 if (!qtMapLeaves(0))
494     return;
495 gregl 3.1 update(ca, &qtrunk, 0, 0, odev.hres, odev.vres);
496     }