ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhd_qtree.c
Revision: 3.1
Committed: Wed Nov 19 18:01:03 1997 UTC (26 years, 10 months ago) by gregl
Content type: text/plain
Branch: MAIN
Log Message:
Initial revision

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     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    
22     #define TBUNDLESIZ 409 /* number of twigs in a bundle */
23    
24     static RTREE **twigbundle; /* free twig blocks (NULL term.) */
25     static int nexttwig; /* next free twig */
26    
27     static RTREE emptytree; /* empty tree for test below */
28    
29     #define is_stump(t) (!bcmp((char *)(t), (char *)&emptytree, sizeof(RTREE)))
30    
31    
32     static RTREE *
33     newtwig() /* allocate a twig */
34     {
35     register int bi;
36    
37     if (twigbundle == NULL) { /* initialize */
38     twigbundle = (RTREE **)malloc(sizeof(RTREE *));
39     if (twigbundle == NULL)
40     goto memerr;
41     twigbundle[0] = NULL;
42     }
43     bi = nexttwig / TBUNDLESIZ;
44     if (twigbundle[bi] == NULL) { /* new block */
45     twigbundle = (RTREE **)realloc((char *)twigbundle,
46     (bi+2)*sizeof(RTREE *));
47     if (twigbundle == NULL)
48     goto memerr;
49     twigbundle[bi] = (RTREE *)calloc(TBUNDLESIZ, sizeof(RTREE));
50     if (twigbundle[bi] == NULL)
51     goto memerr;
52     twigbundle[bi+1] = NULL;
53     }
54     /* nexttwig++ % TBUNDLESIZ */
55     return(twigbundle[bi] + (nexttwig++ - bi*TBUNDLESIZ));
56     memerr:
57     error(SYSTEM, "out of memory in newtwig");
58     }
59    
60    
61     static
62     freetwigs(really) /* free allocated twigs */
63     int really;
64     {
65     register int i;
66    
67     if (tmTop != NULL)
68     tmClearHisto();
69     bzero((char *)&qtrunk, sizeof(RTREE));
70     nexttwig = 0;
71     if (twigbundle == NULL)
72     return;
73     if (!really) { /* just clear allocated blocks */
74     for (i = 0; twigbundle[i] != NULL; i++)
75     bzero((char *)twigbundle[i], TBUNDLESIZ*sizeof(RTREE));
76     return;
77     }
78     /* else "really" means free up memory */
79     for (i = 0; twigbundle[i] != NULL; i++)
80     free((char *)twigbundle[i]);
81     free((char *)twigbundle);
82     twigbundle = NULL;
83     }
84    
85    
86     static RLEAF *
87     newleaf() /* allocate a leaf from our pile */
88     {
89     if (tleaf++ >= nleaves) /* get next leaf in ring */
90     tleaf = 0;
91     if (tleaf == bleaf) /* need to shake some free */
92     qtCompost(LFREEPCT);
93     return(leafpile + tleaf);
94     }
95    
96    
97     int
98     qtAllocLeaves(n) /* allocate space for n leaves */
99     int n;
100     {
101     unsigned nbytes;
102     register unsigned i;
103    
104     freetwigs(0); /* make sure tree is empty */
105     if (n <= 0)
106     return(0);
107     if (nleaves >= n)
108     return(nleaves);
109     else if (nleaves > 0)
110     free((char *)leafpile);
111     /* round space up to nearest power of 2 */
112     nbytes = n*sizeof(RLEAF) + 8;
113     for (i = 1024; nbytes > i; i <<= 1)
114     ;
115     n = (i - 8) / sizeof(RLEAF);
116     leafpile = (RLEAF *)malloc(n*sizeof(RLEAF));
117     if (leafpile == NULL)
118     return(-1);
119     nleaves = n;
120     bleaf = tleaf = 0;
121     return(nleaves);
122     }
123    
124    
125     qtFreeLeaves() /* free our allocated leaves and twigs */
126     {
127     freetwigs(1); /* free tree also */
128     if (nleaves <= 0)
129     return;
130     free((char *)leafpile);
131     leafpile = NULL;
132     nleaves = 0;
133     }
134    
135    
136     static
137     shaketree(tp) /* shake dead leaves from tree */
138     register RTREE *tp;
139     {
140     register int i, li;
141    
142     for (i = 0; i < 4; i++)
143     if (tp->flgs & BRF(i)) {
144     if (shaketree(tp->k[i].b))
145     tp->flgs |= CHF(i);
146     } else if (tp->k[i].l != NULL) {
147     li = tp->k[i].l - leafpile;
148     if (bleaf < tleaf ? (li < bleaf || li >= tleaf) :
149     (li < bleaf && li >= tleaf)) {
150     tmAddHisto(&tp->k[i].l->brt, 1, -1);
151     tp->k[i].l = NULL;
152     tp->flgs |= CHF(i);
153     }
154     }
155     return(tp->flgs & CH_ANY);
156     }
157    
158    
159     int
160     qtCompost(pct) /* free up some leaves */
161     int pct;
162     {
163     int nused, nclear;
164     /* figure out how many leaves to clear */
165     nclear = nleaves * pct / 100;
166     if (nclear <= 0)
167     return(0);
168     nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf;
169     if (nclear >= nused) { /* clear them all */
170     freetwigs(0);
171     bleaf = tleaf = 0;
172     return(nused);
173     }
174     /* else clear leaves from bottom */
175     bleaf = (bleaf + nclear) % nleaves;
176     shaketree(&qtrunk);
177     return(nclear);
178     }
179    
180    
181     static
182     addleaf(lp) /* add a leaf to our tree */
183     RLEAF *lp;
184     {
185     register RTREE *tp = &qtrunk;
186     int x0=0, y0=0, x1=odev.hres, y1=odev.vres;
187     RLEAF *lo = NULL;
188     int x, y, mx, my;
189     double z;
190     FVECT ip, wp;
191     register int q;
192     /* compute leaf location */
193     VCOPY(wp, lp->wp);
194     viewloc(ip, &odev.v, wp);
195     if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
196     || ip[1] < 0. || ip[1] >= 1.)
197     return;
198     x = ip[0] * odev.hres;
199     y = ip[1] * odev.vres;
200     z = ip[2];
201     /* find the place for it */
202     for ( ; ; ) {
203     q = 0; /* which quadrant? */
204     mx = (x0 + x1) >> 1;
205     my = (y0 + y1) >> 1;
206     if (x < mx) x1 = mx;
207     else {x0 = mx; q |= 01;}
208     if (y < my) y1 = my;
209     else {y0 = my; q |= 02;}
210     if (tp->flgs & BRF(q)) { /* move to next branch */
211     tp->flgs |= CHF(q); /* not sure; guess */
212     tp = tp->k[q].b;
213     continue;
214     }
215     if (tp->k[q].l == NULL) { /* found stem for leaf */
216     tp->k[q].l = lp;
217     tp->flgs |= CHF(q);
218     break;
219     }
220     /* check existing leaf */
221     if (lo != tp->k[q].l) {
222     lo = tp->k[q].l;
223     VCOPY(wp, lo->wp);
224     viewloc(ip, &odev.v, wp);
225     }
226     /* is node minimum size? */
227     if (x1-x0 <= qtMinNodesiz || y1-y0 <= qtMinNodesiz) {
228     if (z > (1.-qtDepthEps)*ip[2]) /* who is closer? */
229     return; /* old one is */
230     tp->k[q].l = lp; /* new one is */
231     tp->flgs |= CHF(q);
232     tmAddHisto(&lo->brt, 1, -1); /* drop old one */
233     break;
234     }
235     tp->flgs |= CHBRF(q); /* else grow tree */
236     tp = tp->k[q].b = newtwig();
237     tp->flgs |= CH_ANY; /* all new */
238     q = 0; /* old leaf -> new branch */
239     mx = ip[0] * odev.hres;
240     my = ip[1] * odev.vres;
241     if (mx >= (x0 + x1) >> 1) q |= 01;
242     if (my >= (y0 + y1) >> 1) q |= 02;
243     tp->k[q].l = lo;
244     }
245     tmAddHisto(&lp->brt, 1, 1); /* add leaf to histogram */
246     }
247    
248    
249     dev_value(c, p) /* add a pixel value to our output queue */
250     COLR c;
251     FVECT p;
252     {
253     register RLEAF *lp;
254    
255     lp = newleaf();
256     VCOPY(lp->wp, p);
257     tmCvColrs(&lp->brt, lp->chr, c, 1);
258     addleaf(lp);
259     }
260    
261    
262     qtReplant() /* replant our tree using new view */
263     {
264     register int i;
265    
266     if (bleaf == tleaf) /* anything to replant? */
267     return;
268     freetwigs(0); /* blow the tree away */
269     /* now rebuild it */
270     for (i = bleaf; i != tleaf; ) {
271     addleaf(leafpile+i);
272     if (++i >= nleaves) i = 0;
273     }
274     tmComputeMapping(0., 0., 0.); /* update the display */
275     qtUpdate();
276     }
277    
278    
279     static
280     redraw(ca, tp, x0, y0, x1, y1, l) /* redraw portion of a tree */
281     BYTE ca[3]; /* returned average color */
282     register RTREE *tp;
283     int x0, y0, x1, y1;
284     int l[2][2];
285     {
286     int csm[3], nc;
287     BYTE rgb[3];
288     int quads = CH_ANY;
289     int mx, my;
290     register int i;
291     /* compute midpoint */
292     mx = (x0 + x1) >> 1;
293     my = (y0 + y1) >> 1;
294     /* see what to do */
295     if (l[0][0] >= mx)
296     quads &= ~(CHF(2)|CHF(0));
297     else if (l[0][1] <= mx)
298     quads &= ~(CHF(3)|CHF(1));
299     if (l[1][0] >= my)
300     quads &= ~(CHF(1)|CHF(0));
301     else if (l[1][1] <= my)
302     quads &= ~(CHF(3)|CHF(2));
303     tp->flgs &= ~quads; /* mark them done */
304     csm[0] = csm[1] = csm[2] = nc = 0;
305     /* do leaves first */
306     for (i = 0; i < 4; i++)
307     if (quads & CHF(i) && !(tp->flgs & BRF(i)) &&
308     tp->k[i].l != NULL) {
309     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,
311     i&01 ? x1 : mx, i&02 ? y1 : my);
312     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
313     nc++;
314     quads &= ~CHF(i);
315     }
316     /* now do branches */
317     for (i = 0; i < 4; i++)
318     if (quads & CHF(i) && tp->flgs & BRF(i)) {
319     redraw(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
320     i&01 ? x1 : mx, i&02 ? y1 : my, l);
321     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
322     nc++;
323     quads &= ~CHF(i);
324     }
325     if (nc > 1) {
326     ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
327     } else {
328     ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
329     }
330     if (!quads) return;
331     /* fill in gaps with average */
332     for (i = 0; i < 4; i++)
333     if (quads & CHF(i))
334     dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
335     i&01 ? x1 : mx, i&02 ? y1 : my);
336     }
337    
338    
339     static
340     update(ca, tp, x0, y0, x1, y1) /* update tree display as needed */
341     BYTE ca[3]; /* returned average color */
342     register RTREE *tp;
343     int x0, y0, x1, y1;
344     {
345     int csm[3], nc;
346     BYTE rgb[3];
347     int gaps = 0;
348     int mx, my;
349     register int i;
350     /* compute midpoint */
351     mx = (x0 + x1) >> 1;
352     my = (y0 + y1) >> 1;
353     csm[0] = csm[1] = csm[2] = nc = 0;
354     /* do leaves first */
355     for (i = 0; i < 4; i++)
356     if ((tp->flgs & CHBRF(i)) == CHF(i)) {
357     if (tp->k[i].l == NULL) {
358     gaps |= 1<<i; /* empty stem */
359     continue;
360     }
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,
363     i&01 ? x1 : mx, i&02 ? y1 : my);
364     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
365     nc++;
366     }
367     /* now do branches */
368     for (i = 0; i < 4; i++)
369     if ((tp->flgs & CHBRF(i)) == CHBRF(i)) {
370     update(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
371     i&01 ? x1 : mx, i&02 ? y1 : my);
372     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
373     nc++;
374     }
375     if (nc > 1) {
376     ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
377     } else {
378     ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
379     }
380     /* fill in gaps with average */
381     for (i = 0; gaps && i < 4; gaps >>= 1, i++)
382     if (gaps & 01)
383     dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
384     i&01 ? x1 : mx, i&02 ? y1 : my);
385     tp->flgs &= ~CH_ANY; /* all done */
386     }
387    
388    
389     qtRedraw(x0, y0, x1, y1) /* redraw part of our screen */
390     int x0, y0, x1, y1;
391     {
392     int lim[2][2];
393     BYTE ca[3];
394    
395     if (is_stump(&qtrunk))
396     return;
397     if ((lim[0][0]=x0) == 0 & (lim[1][0]=y0) == 0 &
398     (lim[0][1]=x1) == odev.hres & (lim[1][1]=y1) == odev.vres ||
399     tmTop->lumap == NULL)
400     tmComputeMapping(0., 0., 0.);
401     redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
402     }
403    
404    
405     qtUpdate() /* update our tree display */
406     {
407     BYTE ca[3];
408    
409     if (is_stump(&qtrunk))
410     return;
411     if (tmTop->lumap == NULL)
412     tmComputeMapping(0., 0., 0.);
413     update(ca, &qtrunk, 0, 0, odev.hres, odev.vres);
414     }