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, 4 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

# Content
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 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 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 freetree(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 freetree(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 freetree(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 shaketree(tp->k[i].b);
145 else if (tp->k[i].l != NULL) {
146 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 freetree(0);
168 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 freetree(0); /* blow the tree away */
266 /* 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 }