ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rholo3.c
Revision: 3.11
Committed: Wed Nov 26 21:34:28 1997 UTC (26 years, 4 months ago) by gregl
Content type: text/plain
Branch: MAIN
Changes since 3.10: +32 -27 lines
Log Message:
eliminated queue flushing in sortbeamlist()
added DS_ADJSET request for adjusting set quantities

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     * Routines for tracking beam compuatations
9     */
10    
11     #include "rholo.h"
12    
13     #define abs(x) ((x) > 0 ? (x) : -(x))
14     #define sgn(x) ((x) > 0 ? 1 : (x) < 0 ? -1 : 0)
15    
16 gregl 3.4 static PACKHEAD *complist=NULL; /* list of beams to compute */
17     static int complen=0; /* length of complist */
18     static int listpos=0; /* current list position for next_packet */
19     static int lastin= -1; /* last ordered position in list */
20 gregl 3.1
21    
22     int
23 gregl 3.2 beamcmp(b0, b1) /* comparison for descending compute order */
24     register PACKHEAD *b0, *b1;
25     {
26 gregl 3.11 return( b1->nr*(b0->nc+1) - b0->nr*(b1->nc+1) );
27 gregl 3.2 }
28    
29    
30     bundle_set(op, clist, nents) /* bundle set operation */
31     int op;
32     PACKHEAD *clist;
33     int nents;
34     {
35     BEAM *b;
36     PACKHEAD *p;
37     register int i, n;
38    
39     switch (op) {
40     case BS_NEW: /* new computation set */
41     if (complen)
42     free((char *)complist);
43     if (nents <= 0) {
44     complist = NULL;
45     listpos = complen = 0;
46     lastin = -1;
47     return;
48     }
49     complist = (PACKHEAD *)malloc(nents*sizeof(PACKHEAD));
50     if (complist == NULL)
51     goto memerr;
52     bcopy((char *)clist, (char *)complist, nents*sizeof(PACKHEAD));
53     complen = nents;
54     listpos = 0;
55     lastin = -1; /* flag for initial sort */
56     break;
57     case BS_ADD: /* add to computation set */
58 gregl 3.11 case BS_ADJ: /* adjust set quantities */
59 gregl 3.2 if (nents <= 0)
60     return;
61     /* merge any common members */
62 gregl 3.11 for (i = 0; i < complen; i++) {
63 gregl 3.2 for (n = 0; n < nents; n++)
64     if (clist[n].bi == complist[i].bi &&
65     clist[n].hd == complist[i].hd) {
66 gregl 3.11 if (op == BS_ADD)
67     complist[i].nr += clist[n].nr;
68     else /* op == BS_ADJ */
69     complist[i].nr = clist[n].nr;
70 gregl 3.2 clist[n].nr = 0;
71 gregl 3.11 clist[n].nc = 1;
72 gregl 3.2 lastin = -1; /* flag full sort */
73     break;
74     }
75 gregl 3.11 if (n >= nents)
76     clist[i].nc = bnrays(hdlist[clist[i].hd],
77     clist[i].bi);
78     }
79 gregl 3.2 /* sort updated list */
80     sortcomplist();
81     /* sort new entries */
82     qsort((char *)clist, nents, sizeof(PACKHEAD), beamcmp);
83     /* what can't we satisfy? */
84 gregl 3.11 for (n = 0; n < nents && clist[n].nr > clist[n].nc; n++)
85 gregl 3.2 ;
86 gregl 3.11 if (op == BS_ADJ)
87     nents = n;
88 gregl 3.2 if (n) { /* allocate space for merged list */
89     PACKHEAD *newlist;
90     newlist = (PACKHEAD *)malloc(
91     (complen+n)*sizeof(PACKHEAD) );
92     if (newlist == NULL)
93     goto memerr;
94     /* merge lists */
95     mergeclists(newlist, clist, n, complist, complen);
96     if (complen)
97     free((char *)complist);
98     complist = newlist;
99     complen += n;
100     }
101     listpos = 0;
102     lastin = complen-1; /* list is now sorted */
103     break;
104     case BS_DEL: /* delete from computation set */
105     if (nents <= 0)
106     return;
107     /* find each member */
108     for (i = 0; i < complen; i++)
109     for (n = 0; n < nents; n++)
110     if (clist[n].bi == complist[i].bi &&
111     clist[n].hd == complist[i].hd) {
112     if (clist[n].nr == 0 ||
113     clist[n].nr >= complist[i].nr)
114     complist[i].nr = 0;
115     else
116     complist[i].nr -= clist[n].nr;
117     lastin = -1; /* flag full sort */
118     break;
119     }
120     return; /* no display */
121     default:
122     error(CONSISTENCY, "bundle_set called with unknown operation");
123     }
124 gregl 3.8 if (outdev == NULL)
125     return;
126 gregl 3.11 n = 32*RPACKSIZ; /* allocate packet holder */
127 gregl 3.5 p = (PACKHEAD *)malloc(packsiz(n));
128 gregl 3.3 if (p == NULL)
129     goto memerr;
130     /* display what we have */
131 gregl 3.2 for (i = 0; i < nents; i++)
132 gregl 3.3 if ((b = hdgetbeam(hdlist[clist[i].hd], clist[i].bi)) != NULL) {
133 gregl 3.7 if (b->nrm > n) {
134     n = b->nrm;
135     p = (PACKHEAD *)realloc((char *)p, packsiz(n));
136     if (p == NULL)
137     goto memerr;
138     }
139 gregl 3.6 bcopy((char *)hdbray(b), (char *)packra(p),
140 gregl 3.11 b->nrm*sizeof(RAYVAL));
141 gregl 3.7 p->hd = clist[i].hd;
142     p->bi = clist[i].bi;
143 gregl 3.11 p->nr = p->nc = b->nrm;
144 gregl 3.5 disp_packet(p);
145 gregl 3.2 }
146     free((char *)p); /* clean up */
147 gregl 3.11 if (op == BS_NEW) {
148     done_packets(flush_queue()); /* empty queue, so we can... */
149     for (i = 0; i < complen; i++) /* ...get number computed */
150     complist[i].nc = bnrays(hdlist[complist[i].hd],
151     complist[i].bi);
152     }
153 gregl 3.2 return;
154     memerr:
155     error(SYSTEM, "out of memory in bundle_set");
156     }
157    
158    
159     int
160 gregl 3.1 weightf(hp, x0, x1, x2) /* voxel weighting function */
161     register HOLO *hp;
162     register int x0, x1, x2;
163     {
164     switch (vlet(OCCUPANCY)) {
165     case 'U': /* uniform weighting */
166     return(1);
167     case 'C': /* center weighting (crude) */
168     x0 += x0 - hp->grid[0] + 1;
169     x0 = abs(x0)*hp->grid[1]*hp->grid[2];
170     x1 += x1 - hp->grid[1] + 1;
171     x1 = abs(x1)*hp->grid[0]*hp->grid[2];
172     x2 += x2 - hp->grid[2] + 1;
173     x2 = abs(x2)*hp->grid[0]*hp->grid[1];
174     return(hp->grid[0]*hp->grid[1]*hp->grid[2] -
175     (x0+x1+x2)/3);
176     default:
177     badvalue(OCCUPANCY);
178     }
179     }
180    
181    
182     /* The following is by Daniel Cohen, taken from Graphics Gems IV, p. 368 */
183     long
184     lineweight(hp, x, y, z, dx, dy, dz) /* compute weights along a line */
185     HOLO *hp;
186     int x, y, z, dx, dy, dz;
187     {
188     long wres = 0;
189     int n, sx, sy, sz, exy, exz, ezy, ax, ay, az, bx, by, bz;
190    
191     sx = sgn(dx); sy = sgn(dy); sz = sgn(dz);
192     ax = abs(dx); ay = abs(dy); az = abs(dz);
193     bx = 2*ax; by = 2*ay; bz = 2*az;
194     exy = ay-ax; exz = az-ax; ezy = ay-az;
195     n = ax+ay+az + 1; /* added increment to visit last */
196     while (n--) {
197     wres += weightf(hp, x, y, z);
198     if (exy < 0) {
199     if (exz < 0) {
200     x += sx;
201     exy += by; exz += bz;
202     } else {
203     z += sz;
204     exz -= bx; ezy += by;
205     }
206     } else {
207     if (ezy < 0) {
208     z += sz;
209     exz -= bx; ezy += by;
210     } else {
211     y += sy;
212     exy -= bx; ezy -= bz;
213     }
214     }
215     }
216     return(wres);
217     }
218    
219    
220     init_global() /* initialize global ray computation */
221     {
222     long wtotal = 0;
223     int i, j;
224     int lseg[2][3];
225     double frac;
226     register int k;
227 gregl 3.3 /* free old list */
228     if (complen > 0)
229     free((char *)complist);
230 gregl 3.1 /* allocate beam list */
231     complen = 0;
232     for (j = 0; hdlist[j] != NULL; j++)
233     complen += nbeams(hdlist[j]);
234     complist = (PACKHEAD *)malloc(complen*sizeof(PACKHEAD));
235     if (complist == NULL)
236     error(SYSTEM, "out of memory in init_global");
237     /* compute beam weights */
238     k = 0;
239     for (j = 0; hdlist[j] != NULL; j++)
240     for (i = nbeams(hdlist[j]); i > 0; i--) {
241     hdlseg(lseg, hdlist[j], i);
242     complist[k].hd = j;
243     complist[k].bi = i;
244     complist[k].nr = lineweight( hdlist[j],
245     lseg[0][0], lseg[0][1], lseg[0][2],
246     lseg[1][0] - lseg[0][0],
247     lseg[1][1] - lseg[0][1],
248     lseg[1][2] - lseg[0][2] );
249     wtotal += complist[k++].nr;
250     }
251     /* adjust weights */
252     if (vdef(DISKSPACE)) {
253     frac = 1024.*1024.*vflt(DISKSPACE) / (wtotal*sizeof(RAYVAL));
254     if (frac < 0.95 | frac > 1.05)
255     while (k--)
256     complist[k].nr = frac * complist[k].nr;
257     }
258 gregl 3.4 listpos = 0; lastin = -1; /* flag initial sort */
259 gregl 3.1 }
260    
261    
262     mergeclists(cdest, cl1, n1, cl2, n2) /* merge two sorted lists */
263     PACKHEAD *cdest;
264     PACKHEAD *cl1, *cl2;
265     int n1, n2;
266     {
267     int cmp;
268    
269     while (n1 | n2) {
270     if (!n1) cmp = 1;
271     else if (!n2) cmp = -1;
272     else cmp = beamcmp(cl1, cl2);
273     if (cmp > 0) {
274     copystruct(cdest, cl2);
275     cl2++; n2--;
276     } else {
277     copystruct(cdest, cl1);
278     cl1++; n1--;
279     }
280     cdest++;
281     }
282     }
283    
284    
285     sortcomplist() /* fix our list order */
286     {
287     PACKHEAD *list2;
288 gregl 3.2 register int i;
289    
290 gregl 3.3 if (complen <= 0) /* check to see if there is even a list */
291 gregl 3.2 return;
292 gregl 3.6 if (lastin < 0 || listpos*4 >= complen*3)
293 gregl 3.1 qsort((char *)complist, complen, sizeof(PACKHEAD), beamcmp);
294     else if (listpos) { /* else sort and merge sublist */
295     list2 = (PACKHEAD *)malloc(listpos*sizeof(PACKHEAD));
296     if (list2 == NULL)
297     error(SYSTEM, "out of memory in sortcomplist");
298     bcopy((char *)complist,(char *)list2,listpos*sizeof(PACKHEAD));
299     qsort((char *)list2, listpos, sizeof(PACKHEAD), beamcmp);
300     mergeclists(complist, list2, listpos,
301     complist+listpos, complen-listpos);
302     free((char *)list2);
303     }
304 gregl 3.2 /* drop satisfied requests */
305 gregl 3.11 for (i = complen; i-- && complist[i].nr <= complist[i].nc; )
306 gregl 3.2 ;
307 gregl 3.4 if (i < 0) {
308     free((char *)complist);
309     complist = NULL;
310     complen = 0;
311     } else if (i < complen-1) {
312 gregl 3.2 list2 = (PACKHEAD *)realloc((char *)complist,
313     (i+1)*sizeof(PACKHEAD));
314     if (list2 != NULL) {
315     complist = list2;
316     complen = i+1;
317     }
318     }
319     listpos = 0; lastin = i;
320 gregl 3.1 }
321    
322    
323     /*
324     * The following routine works on the assumption that the bundle weights are
325     * more or less evenly distributed, such that computing a packet causes
326     * a given bundle to move way down in the computation order. We keep
327     * track of where the computed bundle with the highest priority would end
328     * up, and if we get further in our compute list than this, we resort the
329 gregl 3.11 * list and start again from the beginning. Since
330     * a merge sort is used, the sorting costs are minimal.
331 gregl 3.1 */
332     next_packet(p) /* prepare packet for computation */
333     register PACKET *p;
334     {
335     register int i;
336    
337 gregl 3.10 if (listpos > lastin) /* time to sort the list */
338     sortcomplist();
339 gregl 3.1 if (complen <= 0)
340     return(0);
341     p->hd = complist[listpos].hd;
342     p->bi = complist[listpos].bi;
343 gregl 3.11 p->nc = complist[listpos].nc;
344     p->nr = complist[listpos].nr - p->nc;
345 gregl 3.1 if (p->nr <= 0)
346     return(0);
347     if (p->nr > RPACKSIZ)
348     p->nr = RPACKSIZ;
349 gregl 3.11 complist[listpos].nc += p->nr; /* find where this one would go */
350     while (lastin > listpos &&
351     beamcmp(complist+lastin, complist+listpos) > 0)
352 gregl 3.1 lastin--;
353     listpos++;
354     return(1);
355     }