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

# 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 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 }