ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhd_qtree.c
Revision: 3.3
Committed: Thu Nov 20 18:03:43 1997 UTC (26 years, 10 months ago) by gregl
Content type: text/plain
Branch: MAIN
Changes since 3.2: +42 -6 lines
Log Message:
added qtFindLeaf() and made qtFreeTree() global (dunno why yet)

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