ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhd_qtree.c
Revision: 3.2
Committed: Thu Nov 20 11:38:26 1997 UTC (26 years, 10 months ago) by gregl
Content type: text/plain
Branch: MAIN
Changes since 3.1: +12 -15 lines
Log Message:
changed routine name and made it so shaketree() doesn't affect flags

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    
18 gregl 3.1 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    
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 gregl 3.2 freetree(really) /* free allocated twigs */
63 gregl 3.1 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 gregl 3.2 freetree(0); /* make sure tree is empty */
105 gregl 3.1 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 gregl 3.2 freetree(1); /* free tree also */
128 gregl 3.1 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 gregl 3.2 if (tp->flgs & BRF(i))
144     shaketree(tp->k[i].b);
145     else if (tp->k[i].l != NULL) {
146 gregl 3.1 li = tp->k[i].l - leafpile;
147     if (bleaf < tleaf ? (li < bleaf || li >= tleaf) :
148     (li < bleaf && li >= tleaf)) {
149     tmAddHisto(&tp->k[i].l->brt, 1, -1);
150     tp->k[i].l = NULL;
151     }
152     }
153     }
154    
155    
156     int
157     qtCompost(pct) /* free up some leaves */
158     int pct;
159     {
160     int nused, nclear;
161     /* figure out how many leaves to clear */
162     nclear = nleaves * pct / 100;
163     if (nclear <= 0)
164     return(0);
165     nused = tleaf > bleaf ? tleaf-bleaf : tleaf+nleaves-bleaf;
166     if (nclear >= nused) { /* clear them all */
167 gregl 3.2 freetree(0);
168 gregl 3.1 bleaf = tleaf = 0;
169     return(nused);
170     }
171     /* else clear leaves from bottom */
172     bleaf = (bleaf + nclear) % nleaves;
173     shaketree(&qtrunk);
174     return(nclear);
175     }
176    
177    
178     static
179     addleaf(lp) /* add a leaf to our tree */
180     RLEAF *lp;
181     {
182     register RTREE *tp = &qtrunk;
183     int x0=0, y0=0, x1=odev.hres, y1=odev.vres;
184     RLEAF *lo = NULL;
185     int x, y, mx, my;
186     double z;
187     FVECT ip, wp;
188     register int q;
189     /* compute leaf location */
190     VCOPY(wp, lp->wp);
191     viewloc(ip, &odev.v, wp);
192     if (ip[2] <= 0. || ip[0] < 0. || ip[0] >= 1.
193     || ip[1] < 0. || ip[1] >= 1.)
194     return;
195     x = ip[0] * odev.hres;
196     y = ip[1] * odev.vres;
197     z = ip[2];
198     /* find the place for it */
199     for ( ; ; ) {
200     q = 0; /* which quadrant? */
201     mx = (x0 + x1) >> 1;
202     my = (y0 + y1) >> 1;
203     if (x < mx) x1 = mx;
204     else {x0 = mx; q |= 01;}
205     if (y < my) y1 = my;
206     else {y0 = my; q |= 02;}
207     if (tp->flgs & BRF(q)) { /* move to next branch */
208     tp->flgs |= CHF(q); /* not sure; guess */
209     tp = tp->k[q].b;
210     continue;
211     }
212     if (tp->k[q].l == NULL) { /* found stem for leaf */
213     tp->k[q].l = lp;
214     tp->flgs |= CHF(q);
215     break;
216     }
217     /* check existing leaf */
218     if (lo != tp->k[q].l) {
219     lo = tp->k[q].l;
220     VCOPY(wp, lo->wp);
221     viewloc(ip, &odev.v, wp);
222     }
223     /* is node minimum size? */
224     if (x1-x0 <= qtMinNodesiz || y1-y0 <= qtMinNodesiz) {
225     if (z > (1.-qtDepthEps)*ip[2]) /* who is closer? */
226     return; /* old one is */
227     tp->k[q].l = lp; /* new one is */
228     tp->flgs |= CHF(q);
229     tmAddHisto(&lo->brt, 1, -1); /* drop old one */
230     break;
231     }
232     tp->flgs |= CHBRF(q); /* else grow tree */
233     tp = tp->k[q].b = newtwig();
234     tp->flgs |= CH_ANY; /* all new */
235     q = 0; /* old leaf -> new branch */
236     mx = ip[0] * odev.hres;
237     my = ip[1] * odev.vres;
238     if (mx >= (x0 + x1) >> 1) q |= 01;
239     if (my >= (y0 + y1) >> 1) q |= 02;
240     tp->k[q].l = lo;
241     }
242     tmAddHisto(&lp->brt, 1, 1); /* add leaf to histogram */
243     }
244    
245    
246     dev_value(c, p) /* add a pixel value to our output queue */
247     COLR c;
248     FVECT p;
249     {
250     register RLEAF *lp;
251    
252     lp = newleaf();
253     VCOPY(lp->wp, p);
254     tmCvColrs(&lp->brt, lp->chr, c, 1);
255     addleaf(lp);
256     }
257    
258    
259     qtReplant() /* replant our tree using new view */
260     {
261     register int i;
262    
263     if (bleaf == tleaf) /* anything to replant? */
264     return;
265 gregl 3.2 freetree(0); /* blow the tree away */
266 gregl 3.1 /* now rebuild it */
267     for (i = bleaf; i != tleaf; ) {
268     addleaf(leafpile+i);
269     if (++i >= nleaves) i = 0;
270     }
271     tmComputeMapping(0., 0., 0.); /* update the display */
272     qtUpdate();
273     }
274    
275    
276     static
277     redraw(ca, tp, x0, y0, x1, y1, l) /* redraw portion of a tree */
278     BYTE ca[3]; /* returned average color */
279     register RTREE *tp;
280     int x0, y0, x1, y1;
281     int l[2][2];
282     {
283     int csm[3], nc;
284     BYTE rgb[3];
285     int quads = CH_ANY;
286     int mx, my;
287     register int i;
288     /* compute midpoint */
289     mx = (x0 + x1) >> 1;
290     my = (y0 + y1) >> 1;
291     /* see what to do */
292     if (l[0][0] >= mx)
293     quads &= ~(CHF(2)|CHF(0));
294     else if (l[0][1] <= mx)
295     quads &= ~(CHF(3)|CHF(1));
296     if (l[1][0] >= my)
297     quads &= ~(CHF(1)|CHF(0));
298     else if (l[1][1] <= my)
299     quads &= ~(CHF(3)|CHF(2));
300     tp->flgs &= ~quads; /* mark them done */
301     csm[0] = csm[1] = csm[2] = nc = 0;
302     /* do leaves first */
303     for (i = 0; i < 4; i++)
304     if (quads & CHF(i) && !(tp->flgs & BRF(i)) &&
305     tp->k[i].l != NULL) {
306     tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1);
307     dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0,
308     i&01 ? x1 : mx, i&02 ? y1 : my);
309     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
310     nc++;
311     quads &= ~CHF(i);
312     }
313     /* now do branches */
314     for (i = 0; i < 4; i++)
315     if (quads & CHF(i) && tp->flgs & BRF(i)) {
316     redraw(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
317     i&01 ? x1 : mx, i&02 ? y1 : my, l);
318     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
319     nc++;
320     quads &= ~CHF(i);
321     }
322     if (nc > 1) {
323     ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
324     } else {
325     ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
326     }
327     if (!quads) return;
328     /* fill in gaps with average */
329     for (i = 0; i < 4; i++)
330     if (quads & CHF(i))
331     dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
332     i&01 ? x1 : mx, i&02 ? y1 : my);
333     }
334    
335    
336     static
337     update(ca, tp, x0, y0, x1, y1) /* update tree display as needed */
338     BYTE ca[3]; /* returned average color */
339     register RTREE *tp;
340     int x0, y0, x1, y1;
341     {
342     int csm[3], nc;
343     BYTE rgb[3];
344     int gaps = 0;
345     int mx, my;
346     register int i;
347     /* compute midpoint */
348     mx = (x0 + x1) >> 1;
349     my = (y0 + y1) >> 1;
350     csm[0] = csm[1] = csm[2] = nc = 0;
351     /* do leaves first */
352     for (i = 0; i < 4; i++)
353     if ((tp->flgs & CHBRF(i)) == CHF(i)) {
354     if (tp->k[i].l == NULL) {
355     gaps |= 1<<i; /* empty stem */
356     continue;
357     }
358     tmMapPixels(rgb, &tp->k[i].l->brt, tp->k[i].l->chr, 1);
359     dev_paintr(rgb, i&01 ? mx : x0, i&02 ? my : y0,
360     i&01 ? x1 : mx, i&02 ? y1 : my);
361     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
362     nc++;
363     }
364     /* now do branches */
365     for (i = 0; i < 4; i++)
366     if ((tp->flgs & CHBRF(i)) == CHBRF(i)) {
367     update(rgb, tp->k[i].b, i&01 ? mx : x0, i&02 ? my : y0,
368     i&01 ? x1 : mx, i&02 ? y1 : my);
369     csm[0] += rgb[0]; csm[1] += rgb[1]; csm[2] += rgb[2];
370     nc++;
371     }
372     if (nc > 1) {
373     ca[0] = csm[0]/nc; ca[1] = csm[1]/nc; ca[2] = csm[2]/nc;
374     } else {
375     ca[0] = csm[0]; ca[1] = csm[1]; ca[2] = csm[2];
376     }
377     /* fill in gaps with average */
378     for (i = 0; gaps && i < 4; gaps >>= 1, i++)
379     if (gaps & 01)
380     dev_paintr(ca, i&01 ? mx : x0, i&02 ? my : y0,
381     i&01 ? x1 : mx, i&02 ? y1 : my);
382     tp->flgs &= ~CH_ANY; /* all done */
383     }
384    
385    
386     qtRedraw(x0, y0, x1, y1) /* redraw part of our screen */
387     int x0, y0, x1, y1;
388     {
389     int lim[2][2];
390     BYTE ca[3];
391    
392     if (is_stump(&qtrunk))
393     return;
394     if ((lim[0][0]=x0) == 0 & (lim[1][0]=y0) == 0 &
395     (lim[0][1]=x1) == odev.hres & (lim[1][1]=y1) == odev.vres ||
396     tmTop->lumap == NULL)
397     tmComputeMapping(0., 0., 0.);
398     redraw(ca, &qtrunk, 0, 0, odev.hres, odev.vres, lim);
399     }
400    
401    
402     qtUpdate() /* update our tree display */
403     {
404     BYTE ca[3];
405    
406     if (is_stump(&qtrunk))
407     return;
408     if (tmTop->lumap == NULL)
409     tmComputeMapping(0., 0., 0.);
410     update(ca, &qtrunk, 0, 0, odev.hres, odev.vres);
411     }