ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhdisp2.c
Revision: 3.16
Committed: Tue Dec 16 11:57:32 1997 UTC (26 years, 4 months ago) by gregl
Content type: text/plain
Branch: MAIN
Changes since 3.15: +45 -18 lines
Log Message:
add to beam list in two stages -- prioritize bundles through viewpoint

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