ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhdisp2.c
Revision: 3.2
Committed: Thu Nov 20 14:46:07 1997 UTC (26 years, 5 months ago) by gregl
Content type: text/plain
Branch: MAIN
Changes since 3.1: +5 -7 lines
Log Message:
added consistency check

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 gregl 3.2 * Holodeck beam tracking for display process
9 gregl 3.1 */
10    
11     #include "rholo.h"
12     #include "rhdisp.h"
13     #include "rhdriver.h"
14    
15     extern int *getviewcells();
16    
17     typedef struct {
18 gregl 3.2 int hd; /* holodeck section number (-1 if inactive) */
19 gregl 3.1 int i[3]; /* voxel index (may be outside section) */
20     } VOXL; /* a voxel */
21    
22     static VOXL voxel[8] = { /* current voxel list */
23     {-1}, {-1}, {-1}, {-1},
24     {-1}, {-1}, {-1}, {-1}
25     };
26    
27     #define CBEAMBLK 1024 /* cbeam allocation block size */
28    
29     static struct beamcomp {
30     short wants; /* flags telling which voxels want us */
31     short hd; /* holodeck section number */
32     int bi; /* beam index */
33     } *cbeam = NULL; /* current beam list */
34    
35     static int ncbeams = 0; /* number of sorted beams in cbeam */
36     static int xcbeams = 0; /* extra (unregistered) beams past ncbeams */
37     static int maxcbeam = 0; /* size of cbeam array */
38    
39     struct cellact {
40     short vi; /* voxel index */
41     short add; /* zero means delete */
42     }; /* action for cell */
43    
44     struct beamact {
45     struct cellact ca; /* cell action */
46     GCOORD gc; /* grid coordinate */
47     }; /* beam origin and action */
48    
49    
50     int
51     newcbeam() /* allocate new entry at end of cbeam array */
52     {
53     int i;
54    
55     if ((i = ncbeams + xcbeams++) >= maxcbeam) { /* grow array */
56     maxcbeam += CBEAMBLK;
57     if (cbeam == NULL)
58     cbeam = (struct beamcomp *)malloc(
59     maxcbeam*sizeof(struct beamcomp) );
60     else
61     cbeam = (struct beamcomp *)realloc( (char *)cbeam,
62     maxcbeam*sizeof(struct beamcomp) );
63     if (cbeam == NULL)
64     error(SYSTEM, "out of memory in newcbeam");
65     }
66     return(i);
67     }
68    
69    
70     int
71     cbeamcmp(cb1, cb2) /* compare two cbeam entries for sort: keep orphans */
72     register struct beamcomp *cb1, *cb2;
73     {
74     register int c;
75    
76     if ((c = cb1->bi - cb2->bi)) /* sort on beam index first */
77     return(c);
78     return(cb1->hd - cb2->hd); /* use hd to resolve matches */
79     }
80    
81    
82     int
83     cbeamcmp2(cb1, cb2) /* compare two cbeam entries for sort: no orphans */
84     register struct beamcomp *cb1, *cb2;
85     {
86     register int c;
87    
88     if (!cb1->wants) /* put orphans at the end, unsorted */
89     return(cb2->wants);
90     if ((c = cb1->bi - cb2->bi)) /* sort on beam index first */
91     return(c);
92     return(cb1->hd - cb2->hd); /* use hd to resolve matches */
93     }
94    
95    
96     int
97     findcbeam(hd, bi) /* find the specified beam in our sorted list */
98     int hd, bi;
99     {
100     struct beamcomp cb;
101     register struct beamcomp *p;
102    
103     if (ncbeams <= 0)
104     return(-1);
105     cb.wants = 0; cb.hd = hd; cb.bi = bi;
106     p = (struct beamcomp *)bsearch((char *)&cb, (char *)cbeam, ncbeams,
107     sizeof(struct beamcomp), cbeamcmp);
108     if (p == NULL)
109     return(-1);
110     return(p - cbeam);
111     }
112    
113    
114     int
115     getcbeam(hd, bi) /* get the specified beam, allocating as necessary */
116     register int hd;
117     int bi;
118     {
119     register int n;
120     /* first, look in sorted list */
121     if ((n = findcbeam(hd, bi)) >= 0)
122     return(n);
123     /* linear search through xcbeams to be sure */
124     for (n = ncbeams+xcbeams; n-- > ncbeams; )
125     if (cbeam[n].bi == bi && cbeam[n].hd == hd)
126     return(n);
127     /* check legality */
128     if (hd < 0 | hd >= HDMAX || hdlist[hd] == NULL)
129     error(INTERNAL, "illegal holodeck number in getcbeam");
130     if (bi < 1 | bi > nbeams(hdlist[hd]))
131     error(INTERNAL, "illegal beam index in getcbeam");
132     n = newcbeam(); /* allocate and assign */
133     cbeam[n].wants = 0; cbeam[n].hd = hd; cbeam[n].bi = bi;
134     return(n);
135     }
136    
137    
138     cbeamsort(adopt) /* sort our beam list, possibly turning out orphans */
139     int adopt;
140     {
141     register int i;
142    
143     if (!(ncbeams += xcbeams))
144     return;
145     xcbeams = 0;
146     qsort((char *)cbeam, ncbeams, sizeof(struct beamcomp),
147     adopt ? cbeamcmp : cbeamcmp2);
148     if (adopt)
149     return;
150     for (i = ncbeams; i--; ) /* identify orphans */
151     if (cbeam[i].wants)
152     break;
153     xcbeams = ncbeams - ++i; /* put orphans after ncbeams */
154     ncbeams = i;
155     }
156    
157    
158     cbeamadd(bl, n, v, hr, vr) /* add beams to server list */
159     register struct beamcomp *bl;
160     int n;
161     VIEW *v;
162     int hr, vr;
163     {
164     register PACKHEAD *pa;
165     register int i;
166    
167     if (n <= 0)
168     return;
169     pa = (PACKHEAD *)malloc(n*sizeof(PACKHEAD));
170     if (pa == NULL)
171     error(SYSTEM, "out of memory in cbeamadd");
172     for (i = 0; i < n; i++)
173     pa[i].nr = npixels(v, hr, vr,
174     hdlist[pa[i].hd=bl[i].hd],
175     pa[i].bi=bl[i].bi) / 8;
176    
177     serv_request(DR_ADDSET, n*sizeof(PACKHEAD), (char *)pa);
178     free((char *)pa);
179     }
180    
181    
182     cbeamdel(bl, n) /* delete unwanted beam requests */
183     register struct beamcomp *bl;
184     int n;
185     {
186     register PACKHEAD *pa;
187     register int i;
188    
189     if (n <= 0)
190     return;
191     pa = (PACKHEAD *)malloc(n*sizeof(PACKHEAD));
192     if (pa == NULL)
193     error(SYSTEM, "out of memory in cbeamdel");
194     for (i = 0; i < n; i++) {
195     pa[i].hd = bl[i].hd;
196     pa[i].bi = bl[i].bi;
197     pa[i].nr = 0; /* removes any request */
198     }
199     serv_request(DR_DELSET, n*sizeof(PACKHEAD), (char *)pa);
200     free((char *)pa);
201     }
202    
203    
204     int
205     set_voxels(vl, n) /* set new voxel array */
206     VOXL vl[8];
207     int n;
208     {
209     short wmap[256];
210     int vmap[8];
211     int comn = 0;
212     int no;
213     register int i, j;
214     /* find common voxels */
215     for (j = 0; j < 8 && voxel[j].hd >= 0; j++) {
216     vmap[j] = -1;
217     for (i = n; i--; )
218     if (!bcmp((char *)(vl+i), (char *)(voxel+j),
219     sizeof(VOXL))) {
220     vmap[j] = i;
221     comn |= 1<<i;
222     break;
223     }
224     }
225     no = comn ? j : 0; /* compute flag mapping */
226     for (i = 256; i--; ) {
227     wmap[i] = 0;
228     for (j = no; j--; )
229     if (vmap[j] >= 0 && i & 1<<j)
230     wmap[i] |= 1<<vmap[j];
231     }
232     /* fix cbeam flags */
233     for (i = ncbeams; i--; )
234     cbeam[i].wants = wmap[cbeam[i].wants];
235     /* update our voxel list */
236     bcopy((char *)vl, (char *)voxel, n*sizeof(VOXL));
237     for (j = n; j < 8; j++)
238     voxel[j].hd = -1;
239     return(comn); /* return bit array of common voxels */
240     }
241    
242    
243     int
244     get_voxels(vl, vp) /* find voxels corresponding to view point */
245     VOXL vl[8];
246     FVECT vp;
247     {
248     int n = 0;
249     FVECT gp;
250     double d;
251     int dist, bestd = 0x7fff;
252     VOXL vox;
253     register int i, j, k;
254     /* find closest voxels */
255     for (i = 0; n < 8 && hdlist[i]; i++) {
256     hdgrid(gp, hdlist[i], vp);
257     for (j = 0; n < 8 && j < 8; j++) {
258     dist = 0;
259     for (k = 0; k < 3; k++) {
260     d = gp[k] - .5 + (j>>k & 1);
261     if (d < 0.)
262     dist += -(vox.i[k] = (int)d - 1);
263     else if ((vox.i[k] = d) >= hdlist[i]->grid[k])
264     dist += vox.i[k] -
265     hdlist[i]->grid[k] + 1;
266     }
267     if (dist > bestd) /* others were closer */
268     continue;
269     if (dist < bestd) { /* start closer list */
270     n = 0;
271     bestd = dist;
272     }
273     vox.hd = i; /* add this voxel */
274     copystruct(&vl[n], &vox);
275     n++;
276     }
277     }
278     return(n);
279     }
280    
281    
282     int
283     dobeam(gcp, bp) /* express interest or disintrest in a beam */
284     GCOORD *gcp;
285     register struct beamact *bp;
286     {
287     GCOORD gc[2];
288     int bi, i;
289     /* compute beam index */
290     copystruct(gc, gcp);
291     copystruct(gc+1, &bp->gc);
292     if ((bi = hdbindex(hdlist[voxel[bp->ca.vi].hd], gc)) <= 0)
293 gregl 3.2 error(CONSISTENCY, "bad grid coordinate in dobeam");
294 gregl 3.1 if (bp->ca.add) { /* add it in */
295     i = getcbeam(voxel[bp->ca.vi].hd, bi);
296     cbeam[i].wants |= 1<<bp->ca.vi; /* say we want it */
297     return(i == ncbeams+xcbeams-1); /* return 1 if totally new */
298     }
299     /* else delete it */
300     i = findcbeam(voxel[bp->ca.vi].hd, bi);
301     if (i >= 0 && cbeam[i].wants & 1<<bp->ca.vi) {
302     cbeam[i].wants &= ~(1<<bp->ca.vi); /* we don't want it */
303     return(1); /* indicate change */
304     }
305     return(0);
306     }
307    
308    
309    
310     int
311     docell(gcp, cap) /* find beams corresponding to cell and voxel */
312     GCOORD *gcp;
313     register struct cellact *cap;
314     {
315     FVECT org, dir[4];
316     FVECT gp, cv[4], vc;
317     struct beamact bo;
318     register int i;
319     /* compute cell vertices */
320     hdcell(cv, hdlist[voxel[cap->vi].hd], gcp);
321     /* compute cell and voxel centers */
322     for (i = 0; i < 3; i++) {
323     org[i] = 0.5*(cv[0][i] + cv[2][i]);
324     gp[i] = voxel[cap->vi].i[i] + 0.5;
325     }
326     hdworld(vc, hdlist[voxel[cap->vi].hd], gp);
327     /* compute voxel pyramid using vector trick */
328     for (i = 0; i < 3; i++) {
329     dir[0][i] = vc[i] - cv[0][i]; /* to 3 */
330     dir[2][i] = vc[i] - cv[3][i]; /* to 0 */
331     if (gcp->w & 1) { /* watch vertex order! */
332     dir[1][i] = vc[i] - cv[2][i]; /* to 1 */
333     dir[3][i] = vc[i] - cv[1][i]; /* to 2 */
334     } else {
335     dir[1][i] = vc[i] - cv[1][i]; /* to 2 */
336     dir[3][i] = vc[i] - cv[2][i]; /* to 1 */
337     }
338     }
339     /* visit beams for opposite cells */
340     copystruct(&bo.ca, cap);
341     copystruct(&bo.gc, gcp);
342     return(visit_cells(org, dir, hdlist[voxel[cap->vi].hd], dobeam, &bo));
343     }
344    
345    
346     int
347     doview(cap, vp) /* visit cells for a given view */
348     struct cellact *cap;
349     VIEW *vp;
350     {
351     FVECT org, dir[4];
352     /* compute view pyramid */
353     if (vp->type == VT_PAR) goto viewerr;
354     if (viewray(org, dir[0], vp, 0., 0.) < -FTINY) goto viewerr;
355     if (viewray(org, dir[1], vp, 0., 1.) < -FTINY) goto viewerr;
356     if (viewray(org, dir[2], vp, 1., 1.) < -FTINY) goto viewerr;
357     if (viewray(org, dir[3], vp, 1., 0.) < -FTINY) goto viewerr;
358     /* visit cells within pyramid */
359     return(visit_cells(org, dir, hdlist[voxel[cap->vi].hd], docell, cap));
360     viewerr:
361     error(INTERNAL, "unusable view in doview");
362     }
363    
364    
365     mvview(voxi, vold, vnew) /* move view for a voxel */
366     int voxi;
367     VIEW *vold, *vnew;
368     {
369     int netchange = 0;
370     int *ocl, *ncl;
371     struct cellact ca;
372     int ocnt, ncnt;
373     int c;
374     register GCOORD *ogcp, *ngcp;
375     /* get old and new cell lists */
376     ocl = getviewcells(hdlist[voxel[voxi].hd], vold);
377     ncl = getviewcells(hdlist[voxel[voxi].hd], vnew);
378     if (ocl != NULL) {
379     ocnt = *ocl; ogcp = (GCOORD *)(ocl+1);
380     } else {
381     ocnt = 0; ogcp = NULL;
382     }
383     if (ncl != NULL) {
384     ncnt = *ncl; ngcp = (GCOORD *)(ncl+1);
385     } else {
386     ncnt = 0; ngcp = NULL;
387     }
388     ca.vi = voxi; /* add and delete cells */
389     while (ocnt > 0 & ncnt > 0)
390     if ((c = cellcmp(ogcp, ngcp)) > 0) {
391     ca.add = 1; /* new cell */
392     netchange += docell(ngcp++, &ca);
393     ncnt--;
394     } else if (c < 0) {
395     ca.add = 0; /* obsolete cell */
396     netchange -= docell(ogcp++, &ca);
397     ocnt--;
398     } else {
399     ogcp++; ocnt--; /* unchanged cell */
400     ngcp++; ncnt--;
401     }
402     /* take care of list tails */
403     for (ca.add = 1; ncnt > 0; ncnt--)
404 gregl 3.2 netchange += docell(ngcp++, &ca);
405 gregl 3.1 for (ca.add = 0; ocnt > 0; ocnt--)
406 gregl 3.2 netchange -= docell(ogcp++, &ca);
407 gregl 3.1 /* clean up */
408     if (ocl != NULL) free((char *)ocl);
409     if (ncl != NULL) free((char *)ncl);
410     return(netchange);
411     }
412    
413    
414     beam_view(vo, vn) /* change beam view */
415     VIEW *vo, *vn;
416     {
417     struct cellact ca;
418     VOXL vlnew[8];
419     int n, comn;
420    
421     if (!vn->type) { /* clear our beam list */
422     set_voxels(vlnew, 0);
423     cbeamdel(cbeam, ncbeams);
424     ncbeams = 0;
425     return;
426     }
427     /* find our new voxels */
428     n = get_voxels(vlnew, vn->vp);
429     /* set the new voxels */
430     comn = set_voxels(vlnew, n);
431     if (!vo->type)
432     comn = 0;
433     ca.add = 1; /* update our beam list */
434     for (ca.vi = n; ca.vi--; )
435     if (comn & 1<<ca.vi) /* change which cells we see */
436     mvview(ca.vi, vo, vn);
437     else /* else add all new cells */
438     doview(&ca, vn);
439     /* inform server of new beams */
440     cbeamadd(cbeam+ncbeams, xcbeams, vn, odev.hres, odev.vres);
441     /* sort list to put orphans at end */
442     cbeamsort(0);
443     /* tell server to delete orphans */
444     cbeamdel(cbeam+ncbeams, xcbeams);
445     xcbeams = 0; /* truncate our list */
446     }