--- ray/src/hd/rhdisp2.c 1997/11/19 18:01:03 3.1 +++ ray/src/hd/rhdisp2.c 1998/05/14 10:13:50 3.20 @@ -1,34 +1,39 @@ -/* Copyright (c) 1997 Silicon Graphics, Inc. */ +/* Copyright (c) 1998 Silicon Graphics, Inc. */ #ifndef lint static char SCCSid[] = "$SunId$ SGI"; #endif /* - * Holodeck beam tracking + * Holodeck beam tracking for display process */ #include "rholo.h" #include "rhdisp.h" #include "rhdriver.h" -extern int *getviewcells(); +#ifndef MAXDIST +#define MAXDIST 42 /* maximum distance outside section */ +#endif +#define MAXVOXEL 16 /* maximum number of active voxels */ + +extern GCOORD *getviewcells(); + +static VIEW dvw; /* current view corresponding to beam list */ + typedef struct { - int hd; /* holodeck section number */ + int hd; /* holodeck section number (-1 if inactive) */ int i[3]; /* voxel index (may be outside section) */ } VOXL; /* a voxel */ -static VOXL voxel[8] = { /* current voxel list */ - {-1}, {-1}, {-1}, {-1}, - {-1}, {-1}, {-1}, {-1} -}; +static VOXL voxel[MAXVOXEL] = {{-1}}; /* current voxel list */ #define CBEAMBLK 1024 /* cbeam allocation block size */ static struct beamcomp { - short wants; /* flags telling which voxels want us */ - short hd; /* holodeck section number */ + unsigned short wants; /* flags telling which voxels want us */ + unsigned short hd; /* holodeck section number */ int bi; /* beam index */ } *cbeam = NULL; /* current beam list */ @@ -36,13 +41,12 @@ static int ncbeams = 0; /* number of sorted beams in c static int xcbeams = 0; /* extra (unregistered) beams past ncbeams */ static int maxcbeam = 0; /* size of cbeam array */ - struct cellact { short vi; /* voxel index */ short add; /* zero means delete */ + short rev; /* reverse ray direction? */ }; /* action for cell */ - struct beamact { struct cellact ca; /* cell action */ GCOORD gc; /* grid coordinate */ @@ -89,6 +93,8 @@ register struct beamcomp *cb1, *cb2; if (!cb1->wants) /* put orphans at the end, unsorted */ return(cb2->wants); + if (!cb2->wants) + return(-1); if ((c = cb1->bi - cb2->bi)) /* sort on beam index first */ return(c); return(cb1->hd - cb2->hd); /* use hd to resolve matches */ @@ -157,7 +163,8 @@ int adopt; } -cbeamadd(bl, n, v, hr, vr) /* add beams to server list */ +cbeamop(op, bl, n, v, hr, vr) /* update beams on server list */ +int op; register struct beamcomp *bl; int n; VIEW *v; @@ -171,50 +178,30 @@ int hr, vr; pa = (PACKHEAD *)malloc(n*sizeof(PACKHEAD)); if (pa == NULL) error(SYSTEM, "out of memory in cbeamadd"); - for (i = 0; i < n; i++) - pa[i].nr = npixels(v, hr, vr, - hdlist[pa[i].hd=bl[i].hd], - pa[i].bi=bl[i].bi) / 8; - - serv_request(DR_ADDSET, n*sizeof(PACKHEAD), (char *)pa); - free((char *)pa); -} - - -cbeamdel(bl, n) /* delete unwanted beam requests */ -register struct beamcomp *bl; -int n; -{ - register PACKHEAD *pa; - register int i; - - if (n <= 0) - return; - pa = (PACKHEAD *)malloc(n*sizeof(PACKHEAD)); - if (pa == NULL) - error(SYSTEM, "out of memory in cbeamdel"); for (i = 0; i < n; i++) { pa[i].hd = bl[i].hd; pa[i].bi = bl[i].bi; - pa[i].nr = 0; /* removes any request */ + pa[i].nr = v==NULL ? 0 : + npixels(v, hr, vr, hdlist[bl[i].hd], bl[i].bi); + pa[i].nc = 0; } - serv_request(DR_DELSET, n*sizeof(PACKHEAD), (char *)pa); + serv_request(op, n*sizeof(PACKHEAD), (char *)pa); free((char *)pa); } int set_voxels(vl, n) /* set new voxel array */ -VOXL vl[8]; +VOXL vl[MAXVOXEL]; int n; { short wmap[256]; - int vmap[8]; + int vmap[MAXVOXEL]; int comn = 0; int no; register int i, j; /* find common voxels */ - for (j = 0; j < 8 && voxel[j].hd >= 0; j++) { + for (j = 0; j < MAXVOXEL && voxel[j].hd >= 0; j++) { vmap[j] = -1; for (i = n; i--; ) if (!bcmp((char *)(vl+i), (char *)(voxel+j), @@ -236,27 +223,30 @@ int n; cbeam[i].wants = wmap[cbeam[i].wants]; /* update our voxel list */ bcopy((char *)vl, (char *)voxel, n*sizeof(VOXL)); - for (j = n; j < 8; j++) - voxel[j].hd = -1; + if (n < MAXVOXEL) + voxel[n].hd = -1; return(comn); /* return bit array of common voxels */ } int get_voxels(vl, vp) /* find voxels corresponding to view point */ -VOXL vl[8]; +VOXL vl[MAXVOXEL]; FVECT vp; { - int n = 0; + int first, n; FVECT gp; double d; int dist, bestd = 0x7fff; VOXL vox; register int i, j, k; + /* count voxels in list already */ + for (first = 0; first < MAXVOXEL && vl[first].hd >= 0; first++) + ; /* find closest voxels */ - for (i = 0; n < 8 && hdlist[i]; i++) { + for (n = first, i = 0; n < MAXVOXEL && hdlist[i]; i++) { hdgrid(gp, hdlist[i], vp); - for (j = 0; n < 8 && j < 8; j++) { + for (j = 0; n < MAXVOXEL && j < 8; j++) { dist = 0; for (k = 0; k < 3; k++) { d = gp[k] - .5 + (j>>k & 1); @@ -269,14 +259,30 @@ FVECT vp; if (dist > bestd) /* others were closer */ continue; if (dist < bestd) { /* start closer list */ - n = 0; + n = first; bestd = dist; } + /* check if already in list */ + for (k = first; k--; ) + if (vl[k].hd == i && + vl[k].i[0] == vox.i[0] && + vl[k].i[1] == vox.i[1] && + vl[k].i[2] == vox.i[2]) + break; + if (k >= 0) + continue; vox.hd = i; /* add this voxel */ copystruct(&vl[n], &vox); n++; } } + /* check for really stupid move */ + if (bestd > MAXDIST) { + error(COMMAND, "move past outer limits"); + return(0); + } + if (n < MAXVOXEL) + vl[n].hd = -1; return(n); } @@ -289,10 +295,15 @@ register struct beamact *bp; GCOORD gc[2]; int bi, i; /* compute beam index */ - copystruct(gc, gcp); - copystruct(gc+1, &bp->gc); + if (bp->ca.rev) { + copystruct(gc, &bp->gc); + copystruct(gc+1, gcp); + } else { + copystruct(gc, gcp); + copystruct(gc+1, &bp->gc); + } if ((bi = hdbindex(hdlist[voxel[bp->ca.vi].hd], gc)) <= 0) - return(0); /* should report an error? */ + error(CONSISTENCY, "bad grid coordinate in dobeam"); if (bp->ca.add) { /* add it in */ i = getcbeam(voxel[bp->ca.vi].hd, bi); cbeam[i].wants |= 1<ca.vi; /* say we want it */ @@ -314,34 +325,59 @@ docell(gcp, cap) /* find beams corresponding to cell a GCOORD *gcp; register struct cellact *cap; { + register HOLO *hp = hdlist[voxel[cap->vi].hd]; FVECT org, dir[4]; - FVECT gp, cv[4], vc; + FVECT vgp, cgp, vc; + FVECT v1, v2; struct beamact bo; + int axmax, j; + double d, avmax; register int i; - /* compute cell vertices */ - hdcell(cv, hdlist[voxel[cap->vi].hd], gcp); - /* compute cell and voxel centers */ - for (i = 0; i < 3; i++) { - org[i] = 0.5*(cv[0][i] + cv[2][i]); - gp[i] = voxel[cap->vi].i[i] + 0.5; - } - hdworld(vc, hdlist[voxel[cap->vi].hd], gp); - /* compute voxel pyramid using vector trick */ - for (i = 0; i < 3; i++) { - dir[0][i] = vc[i] - cv[0][i]; /* to 3 */ - dir[2][i] = vc[i] - cv[3][i]; /* to 0 */ - if (gcp->w & 1) { /* watch vertex order! */ - dir[1][i] = vc[i] - cv[2][i]; /* to 1 */ - dir[3][i] = vc[i] - cv[1][i]; /* to 2 */ - } else { - dir[1][i] = vc[i] - cv[1][i]; /* to 2 */ - dir[3][i] = vc[i] - cv[2][i]; /* to 1 */ + /* compute cell center */ + cgp[gcp->w>>1] = gcp->w&1 ? hp->grid[gcp->w>>1] : 0 ; + cgp[hdwg0[gcp->w]] = gcp->i[0] + .5; + cgp[hdwg1[gcp->w]] = gcp->i[1] + .5; + hdworld(org, hp, cgp); + /* compute direction to voxel center */ + for (i = 3; i--; ) + vgp[i] = voxel[cap->vi].i[i] + .5; + hdworld(vc, hp, vgp); + for (i = 3; i--; ) + vc[i] -= org[i]; + /* compute maximum area axis */ + axmax = -1; avmax = 0; + for (i = 3; i--; ) { + d = vgp[i] - cgp[i]; + if (d < 0.) d = -d; + if (d > avmax) { + avmax = d; + axmax = i; } } +#ifdef DEBUG + if (axmax < 0.) + error(CONSISTENCY, "botched axis computation in docell"); +#endif + /* compute offset vectors */ + d = 0.5/hp->grid[j=(axmax+1)%3]; + for (i = 3; i--; ) + v1[i] = hp->xv[j][i] * d; + d = 0.5/hp->grid[j=(axmax+2)%3]; + if (DOT(hp->wg[axmax], vc) < 0.) + d = -d; /* reverse vertex order */ + for (i = 3; i--; ) + v2[i] = hp->xv[j][i] * d; + /* compute voxel pyramid */ + for (i = 3; i--; ) { + dir[0][i] = vc[i] - v1[i] - v2[i]; + dir[1][i] = vc[i] + v1[i] - v2[i]; + dir[2][i] = vc[i] + v1[i] + v2[i]; + dir[3][i] = vc[i] - v1[i] + v2[i]; + } /* visit beams for opposite cells */ copystruct(&bo.ca, cap); copystruct(&bo.gc, gcp); - return(visit_cells(org, dir, hdlist[voxel[cap->vi].hd], dobeam, &bo)); + return(visit_cells(org, dir, hp, dobeam, &bo)); } @@ -350,17 +386,15 @@ doview(cap, vp) /* visit cells for a given view */ struct cellact *cap; VIEW *vp; { + int orient; FVECT org, dir[4]; /* compute view pyramid */ - if (vp->type == VT_PAR) goto viewerr; - if (viewray(org, dir[0], vp, 0., 0.) < -FTINY) goto viewerr; - if (viewray(org, dir[1], vp, 0., 1.) < -FTINY) goto viewerr; - if (viewray(org, dir[2], vp, 1., 1.) < -FTINY) goto viewerr; - if (viewray(org, dir[3], vp, 1., 0.) < -FTINY) goto viewerr; + orient = viewpyramid(org, dir, hdlist[voxel[cap->vi].hd], vp); + if (!orient) + error(INTERNAL, "unusable view in doview"); + cap->rev = orient < 0; /* visit cells within pyramid */ return(visit_cells(org, dir, hdlist[voxel[cap->vi].hd], docell, cap)); -viewerr: - error(INTERNAL, "unusable view in doview"); } @@ -369,80 +403,110 @@ int voxi; VIEW *vold, *vnew; { int netchange = 0; - int *ocl, *ncl; - struct cellact ca; + struct cellact oca, nca; int ocnt, ncnt; - int c; + int nmatch = 0; + GCOORD *ogcl, *ngcl; + register int c; register GCOORD *ogcp, *ngcp; /* get old and new cell lists */ - ocl = getviewcells(hdlist[voxel[voxi].hd], vold); - ncl = getviewcells(hdlist[voxel[voxi].hd], vnew); - if (ocl != NULL) { - ocnt = *ocl; ogcp = (GCOORD *)(ocl+1); - } else { - ocnt = 0; ogcp = NULL; + ogcp = ogcl = getviewcells(&ocnt, hdlist[voxel[voxi].hd], vold); + ngcp = ngcl = getviewcells(&ncnt, hdlist[voxel[voxi].hd], vnew); + /* set up actions */ + oca.vi = nca.vi = voxi; + oca.add = 0; nca.add = 1; + if ((oca.rev = ocnt < 0)) + ocnt = -ocnt; + if ((nca.rev = ncnt < 0)) + ncnt = -ncnt; + if (oca.rev == nca.rev) { /* count matches */ + int oc = ocnt, nc = ncnt; + while (oc > 0 & nc > 0) { + c = cellcmp(ogcp, ngcp); + if (c >= 0) { ngcp++; nc--; } + if (c <= 0) { ogcp++; oc--; } + nmatch += c==0; + } + ogcp = ogcl; ngcp = ngcl; } - if (ncl != NULL) { - ncnt = *ncl; ngcp = (GCOORD *)(ncl+1); - } else { - ncnt = 0; ngcp = NULL; + if (nmatch < ocnt>>1) { /* faster to just delete old cells? */ + for (c = ncbeams; c--; ) + if (cbeam[c].wants & 1< 0 & ncnt > 0) - if ((c = cellcmp(ogcp, ngcp)) > 0) { - ca.add = 1; /* new cell */ - netchange += docell(ngcp++, &ca); + if ((c = cellcmp(ogcp, ngcp)) > 0) { /* new cell */ + netchange += docell(ngcp++, &nca); ncnt--; - } else if (c < 0) { - ca.add = 0; /* obsolete cell */ - netchange -= docell(ogcp++, &ca); + } else if (c < 0) { /* old cell */ + netchange -= docell(ogcp++, &oca); ocnt--; - } else { - ogcp++; ocnt--; /* unchanged cell */ + } else { /* same cell */ + ogcp++; ocnt--; ngcp++; ncnt--; } /* take care of list tails */ - for (ca.add = 1; ncnt > 0; ncnt--) - docell(ngcp++, &ca); - for (ca.add = 0; ocnt > 0; ocnt--) - docell(ogcp++, &ca); + for ( ; ncnt > 0; ncnt--) + netchange += docell(ngcp++, &nca); + for ( ; ocnt > 0; ocnt--) + netchange -= docell(ogcp++, &oca); /* clean up */ - if (ocl != NULL) free((char *)ocl); - if (ncl != NULL) free((char *)ncl); + if (ogcl != NULL) free((char *)ogcl); + if (ngcl != NULL) free((char *)ngcl); return(netchange); } -beam_view(vo, vn) /* change beam view */ -VIEW *vo, *vn; +int +beam_sync() /* synchronize beams on server */ { + cbeamop(DR_NEWSET, cbeam, ncbeams, &odev.v, odev.hres, odev.vres); + return(ncbeams); +} + + +beam_view(vn) /* change beam view (if advisable) */ +VIEW *vn; +{ struct cellact ca; - VOXL vlnew[8]; + VOXL vlnew[MAXVOXEL]; int n, comn; - if (!vn->type) { /* clear our beam list */ + if (vn == NULL || !vn->type) { /* clear our beam list */ set_voxels(vlnew, 0); - cbeamdel(cbeam, ncbeams); + cbeamop(DR_DELSET, cbeam, ncbeams, NULL, 0, 0); ncbeams = 0; - return; + dvw.type = 0; + return(1); } /* find our new voxels */ n = get_voxels(vlnew, vn->vp); + if (dvw.type && !n) { + copystruct(vn, &dvw); /* cancel move */ + return(0); + } /* set the new voxels */ comn = set_voxels(vlnew, n); - if (!vo->type) + if (!dvw.type) comn = 0; ca.add = 1; /* update our beam list */ for (ca.vi = n; ca.vi--; ) if (comn & 1<