ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhdisp2.c
Revision: 3.20
Committed: Thu May 14 10:13:50 1998 UTC (25 years, 11 months ago) by gwlarson
Content type: text/plain
Branch: MAIN
Changes since 3.19: +30 -17 lines
Log Message:
partial edit towards multiple views

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