ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhdisp2.c
Revision: 3.15
Committed: Mon Dec 15 20:40:46 1997 UTC (26 years, 4 months ago) by gregl
Content type: text/plain
Branch: MAIN
Changes since 3.14: +2 -0 lines
Log Message:
fixed bug in orphan sorting

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