ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rholo3.c
Revision: 3.27
Committed: Thu Jan 7 22:04:49 1999 UTC (25 years, 2 months ago) by gwlarson
Content type: text/plain
Branch: MAIN
Changes since 3.26: +57 -3 lines
Log Message:
created hdfragflags variable for controlling fragment deallocation
added "chunky" sorting mode to rholo to decrease file fragmentation problems

File Contents

# Content
1 /* Copyright (c) 1998 Silicon Graphics, Inc. */
2
3 #ifndef lint
4 static char SCCSid[] = "$SunId$ SGI";
5 #endif
6
7 /*
8 * Routines for tracking beam compuatations
9 */
10
11 #include "rholo.h"
12
13 #ifndef NFRAG2CHUNK
14 #define NFRAG2CHUNK 4096 /* number of fragments to start chunking */
15 #endif
16
17 #ifndef abs
18 #define abs(x) ((x) > 0 ? (x) : -(x))
19 #endif
20 #ifndef sgn
21 #define sgn(x) ((x) > 0 ? 1 : (x) < 0 ? -1 : 0)
22 #endif
23
24 #define rchunk(n) (((n)+(RPACKSIZ/2))/RPACKSIZ)
25
26 static PACKHEAD *complist=NULL; /* list of beams to compute */
27 static int complen=0; /* length of complist */
28 static int listpos=0; /* current list position for next_packet */
29 static int lastin= -1; /* last ordered position in list */
30 static int chunky=0; /* clump beams together on disk */
31
32
33 int
34 beamcmp(b0, b1) /* comparison for compute order */
35 register PACKHEAD *b0, *b1;
36 {
37 BEAMI *bip0, *bip1;
38 register long c;
39 /* first check desired quantities */
40 if (chunky)
41 c = rchunk(b1->nr)*(rchunk(b0->nc)+1) -
42 rchunk(b0->nr)*(rchunk(b1->nc)+1);
43 else
44 c = b1->nr*(b0->nc+1) - b0->nr*(b1->nc+1);
45 if (c) return(c);
46 /* only one file, so skip the following: */
47 #if 0
48 /* next, check file descriptors */
49 c = hdlist[b0->hd]->fd - hdlist[b1->hd]->fd;
50 if (c) return(c);
51 #endif
52 /* finally, check file positions */
53 bip0 = &hdlist[b0->hd]->bi[b0->bi];
54 bip1 = &hdlist[b1->hd]->bi[b1->bi];
55 /* put diskless beams last */
56 if (!bip0->nrd)
57 return(bip1->nrd > 0);
58 if (!bip1->nrd)
59 return(-1);
60 c = bip0->fo - bip1->fo;
61 return(c < 0 ? -1 : c > 0);
62 }
63
64
65 int
66 beamidcmp(b0, b1) /* comparison for beam searching */
67 register PACKHEAD *b0, *b1;
68 {
69 register int c = b0->hd - b1->hd;
70
71 if (c) return(c);
72 return(b0->bi - b1->bi);
73 }
74
75
76 int
77 dispbeam(b, hb) /* display a holodeck beam */
78 register BEAM *b;
79 register HDBEAMI *hb;
80 {
81 static int n = 0;
82 static PACKHEAD *p = NULL;
83
84 if (b == NULL)
85 return;
86 if (b->nrm > n) { /* (re)allocate packet holder */
87 n = b->nrm;
88 if (p == NULL) p = (PACKHEAD *)malloc(packsiz(n));
89 else p = (PACKHEAD *)realloc((char *)p, packsiz(n));
90 if (p == NULL)
91 error(SYSTEM, "out of memory in dispbeam");
92 }
93 /* assign packet fields */
94 bcopy((char *)hdbray(b), (char *)packra(p), b->nrm*sizeof(RAYVAL));
95 p->nr = p->nc = b->nrm;
96 for (p->hd = 0; hdlist[p->hd] != hb->h; p->hd++)
97 if (hdlist[p->hd] == NULL)
98 error(CONSISTENCY, "unregistered holodeck in dispbeam");
99 p->bi = hb->b;
100 disp_packet(p); /* display it */
101 }
102
103
104 bundle_set(op, clist, nents) /* bundle set operation */
105 int op;
106 PACKHEAD *clist;
107 int nents;
108 {
109 int oldnr, n;
110 HDBEAMI *hbarr;
111 register PACKHEAD *csm;
112 register int i;
113 /* search for common members */
114 for (csm = clist+nents; csm-- > clist; )
115 csm->nc = -1;
116 qsort((char *)clist, nents, sizeof(PACKHEAD), beamidcmp);
117 for (i = 0; i < complen; i++) {
118 csm = (PACKHEAD *)bsearch((char *)(complist+i), (char *)clist,
119 nents, sizeof(PACKHEAD), beamidcmp);
120 if (csm == NULL)
121 continue;
122 oldnr = complist[i].nr;
123 csm->nc = complist[i].nc;
124 switch (op) {
125 case BS_ADD: /* add to count */
126 complist[i].nr += csm->nr;
127 csm->nr = 0;
128 break;
129 case BS_ADJ: /* reset count */
130 complist[i].nr = csm->nr;
131 csm->nr = 0;
132 break;
133 case BS_DEL: /* delete count */
134 if (csm->nr == 0 || csm->nr >= complist[i].nr)
135 complist[i].nr = 0;
136 else
137 complist[i].nr -= csm->nr;
138 break;
139 }
140 if (complist[i].nr != oldnr)
141 lastin = -1; /* flag sort */
142 }
143 /* record computed rays for uncommon beams */
144 for (csm = clist+nents; csm-- > clist; )
145 if (csm->nc < 0)
146 csm->nc = bnrays(hdlist[csm->hd], csm->bi);
147 /* complete list operations */
148 switch (op) {
149 case BS_NEW: /* new computation set */
150 listpos = 0; lastin = -1;
151 if (complen) /* free old list */
152 free((char *)complist);
153 complist = NULL;
154 if (!(complen = nents))
155 return;
156 complist = (PACKHEAD *)malloc(nents*sizeof(PACKHEAD));
157 if (complist == NULL)
158 goto memerr;
159 bcopy((char *)clist, (char *)complist, nents*sizeof(PACKHEAD));
160 break;
161 case BS_ADD: /* add to computation set */
162 case BS_ADJ: /* adjust set quantities */
163 if (nents <= 0)
164 return;
165 sortcomplist(); /* sort updated list & new entries */
166 qsort((char *)clist, nents, sizeof(PACKHEAD), beamcmp);
167 /* what can't we satisfy? */
168 for (i = nents, csm = clist; i-- && csm->nr > csm->nc; csm++)
169 ;
170 n = csm - clist;
171 if (op == BS_ADJ) { /* don't regenerate adjusted beams */
172 for (++i; i-- && csm->nr > 0; csm++)
173 ;
174 nents = csm - clist;
175 }
176 if (n) { /* allocate space for merged list */
177 PACKHEAD *newlist;
178 newlist = (PACKHEAD *)malloc(
179 (complen+n)*sizeof(PACKHEAD) );
180 if (newlist == NULL)
181 goto memerr;
182 /* merge lists */
183 mergeclists(newlist, clist, n, complist, complen);
184 if (complen)
185 free((char *)complist);
186 complist = newlist;
187 complen += n;
188 }
189 listpos = 0;
190 lastin = complen-1; /* list is now sorted */
191 break;
192 case BS_DEL: /* delete from computation set */
193 return; /* already done */
194 default:
195 error(CONSISTENCY, "bundle_set called with unknown operation");
196 }
197 if (outdev == NULL || !nents) /* nothing to display? */
198 return;
199 /* load and display beams we have */
200 hbarr = (HDBEAMI *)malloc(nents*sizeof(HDBEAMI));
201 for (i = nents; i--; ) {
202 hbarr[i].h = hdlist[clist[i].hd];
203 hbarr[i].b = clist[i].bi;
204 }
205 hdloadbeams(hbarr, nents, dispbeam);
206 free((char *)hbarr);
207 if (hdfragflags&FF_READ) {
208 listpos = 0;
209 lastin = -1; /* need to re-sort list */
210 }
211 return;
212 memerr:
213 error(SYSTEM, "out of memory in bundle_set");
214 }
215
216
217 double
218 beamvolume(hp, bi) /* compute approximate volume of a beam */
219 HOLO *hp;
220 int bi;
221 {
222 GCOORD gc[2];
223 FVECT cp[4], edgeA, edgeB, cent[2];
224 FVECT v, crossp[2], diffv;
225 double vol[2];
226 register int i;
227 /* get grid coordinates */
228 if (!hdbcoord(gc, hp, bi))
229 error(CONSISTENCY, "bad beam index in beamvolume");
230 for (i = 0; i < 2; i++) { /* compute cell area vectors */
231 hdcell(cp, hp, gc+i);
232 VSUM(edgeA, cp[1], cp[0], -1.0);
233 VSUM(edgeB, cp[3], cp[1], -1.0);
234 fcross(crossp[i], edgeA, edgeB);
235 /* compute center */
236 cent[i][0] = 0.5*(cp[0][0] + cp[2][0]);
237 cent[i][1] = 0.5*(cp[0][1] + cp[2][1]);
238 cent[i][2] = 0.5*(cp[0][2] + cp[2][2]);
239 }
240 /* compute difference vector */
241 VSUM(diffv, cent[1], cent[0], -1.0);
242 for (i = 0; i < 2; i++) { /* compute volume contributions */
243 vol[i] = 0.5*DOT(crossp[i], diffv);
244 if (vol[i] < 0.) vol[i] = -vol[i];
245 }
246 return(vol[0] + vol[1]); /* return total volume */
247 }
248
249
250 init_global() /* initialize global ray computation */
251 {
252 long wtotal = 0;
253 double frac;
254 int i;
255 register int j, k;
256 /* free old list and empty queue */
257 if (complen > 0) {
258 free((char *)complist);
259 done_packets(flush_queue());
260 }
261 /* allocate beam list */
262 complen = 0;
263 for (j = 0; hdlist[j] != NULL; j++)
264 complen += nbeams(hdlist[j]);
265 complist = (PACKHEAD *)malloc(complen*sizeof(PACKHEAD));
266 if (complist == NULL)
267 error(SYSTEM, "out of memory in init_global");
268 /* compute beam weights */
269 k = 0;
270 for (j = 0; hdlist[j] != NULL; j++) {
271 frac = 512. * VLEN(hdlist[j]->wg[0]) *
272 VLEN(hdlist[j]->wg[1]) *
273 VLEN(hdlist[j]->wg[2]);
274 for (i = nbeams(hdlist[j]); i > 0; i--) {
275 complist[k].hd = j;
276 complist[k].bi = i;
277 complist[k].nr = frac*beamvolume(hdlist[j], i) + 0.5;
278 complist[k].nc = bnrays(hdlist[j], i);
279 wtotal += complist[k++].nr;
280 }
281 }
282 /* adjust weights */
283 if (vdef(DISKSPACE))
284 frac = 1024.*1024.*vflt(DISKSPACE) / (wtotal*sizeof(RAYVAL));
285 else
286 frac = 1024.*1024.*16384. / (wtotal*sizeof(RAYVAL));
287 while (k--)
288 complist[k].nr = frac*complist[k].nr + 0.5;
289 listpos = 0; lastin = -1; /* perform initial sort */
290 sortcomplist();
291 /* no view vicinity */
292 myeye.rng = 0;
293 }
294
295
296 mergeclists(cdest, cl1, n1, cl2, n2) /* merge two sorted lists */
297 register PACKHEAD *cdest;
298 register PACKHEAD *cl1, *cl2;
299 int n1, n2;
300 {
301 register int cmp;
302
303 while (n1 | n2) {
304 if (!n1) cmp = 1;
305 else if (!n2) cmp = -1;
306 else cmp = beamcmp(cl1, cl2);
307 if (cmp > 0) {
308 copystruct(cdest, cl2);
309 cl2++; n2--;
310 } else {
311 copystruct(cdest, cl1);
312 cl1++; n1--;
313 }
314 cdest++;
315 }
316 }
317
318
319 sortcomplist() /* fix our list order */
320 {
321 PACKHEAD *list2;
322 int listlen;
323 register int i;
324
325 if (complen <= 0) /* check to see if there is even a list */
326 return;
327 if (!chunky) /* check to see if fragment list is full */
328 if (!hdfragOK(hdlist[0]->fd, &listlen, NULL)
329 #if NFRAG2CHUNK
330 || listlen >= NFRAG2CHUNK
331 #endif
332 ) {
333 #ifdef DEBUG
334 error(WARNING, "using chunky comparison mode");
335 #endif
336 chunky++; /* use "chunky" comparison */
337 lastin = -1; /* need to re-sort list */
338 }
339 if (lastin < 0 || listpos*4 >= complen*3)
340 qsort((char *)complist, complen, sizeof(PACKHEAD), beamcmp);
341 else if (listpos) { /* else sort and merge sublist */
342 list2 = (PACKHEAD *)malloc(listpos*sizeof(PACKHEAD));
343 if (list2 == NULL)
344 error(SYSTEM, "out of memory in sortcomplist");
345 bcopy((char *)complist,(char *)list2,listpos*sizeof(PACKHEAD));
346 qsort((char *)list2, listpos, sizeof(PACKHEAD), beamcmp);
347 mergeclists(complist, list2, listpos,
348 complist+listpos, complen-listpos);
349 free((char *)list2);
350 }
351 /* drop satisfied requests */
352 for (i = complen; i-- && complist[i].nr <= complist[i].nc; )
353 ;
354 if (i < 0) {
355 free((char *)complist);
356 complist = NULL;
357 complen = 0;
358 } else if (i < complen-1) {
359 list2 = (PACKHEAD *)realloc((char *)complist,
360 (i+1)*sizeof(PACKHEAD));
361 if (list2 != NULL)
362 complist = list2;
363 complen = i+1;
364 }
365 listpos = 0; lastin = i;
366 }
367
368
369 /*
370 * The following routine works on the assumption that the bundle weights are
371 * more or less evenly distributed, such that computing a packet causes
372 * a given bundle to move way down in the computation order. We keep
373 * track of where the computed bundle with the highest priority would end
374 * up, and if we get further in our compute list than this, we re-sort the
375 * list and start again from the beginning. Since
376 * a merge sort is used, the sorting costs are minimal.
377 */
378 next_packet(p, n) /* prepare packet for computation */
379 register PACKET *p;
380 int n;
381 {
382 register int i;
383
384 if (listpos > lastin) /* time to sort the list */
385 sortcomplist();
386 if (complen <= 0)
387 return(0);
388 p->hd = complist[listpos].hd;
389 p->bi = complist[listpos].bi;
390 p->nc = complist[listpos].nc;
391 p->nr = complist[listpos].nr - p->nc;
392 if (p->nr <= 0)
393 return(0);
394 #ifdef DEBUG
395 if (n < 1 | n > RPACKSIZ)
396 error(CONSISTENCY, "next_packet called with bad n value");
397 #endif
398 if (p->nr > n)
399 p->nr = n;
400 complist[listpos].nc += p->nr; /* find where this one would go */
401 if (hdgetbeam(hdlist[p->hd], p->bi) != NULL)
402 hdfreefrag(hdlist[p->hd], p->bi);
403 while (lastin > listpos &&
404 beamcmp(complist+lastin, complist+listpos) > 0)
405 lastin--;
406 listpos++;
407 return(1);
408 }