ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhdisp2.c
Revision: 3.10
Committed: Mon Dec 8 19:03:01 1997 UTC (26 years, 4 months ago) by gregl
Content type: text/plain
Branch: MAIN
Changes since 3.9: +47 -22 lines
Log Message:
improved docell() algorithm for better coverage

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