--- ray/src/hd/rhdisp2.c 1997/11/21 18:17:37 3.5 +++ ray/src/hd/rhdisp2.c 1998/12/10 10:45:55 3.28 @@ -1,4 +1,4 @@ -/* Copyright (c) 1997 Silicon Graphics, Inc. */ +/* Copyright (c) 1998 Silicon Graphics, Inc. */ #ifndef lint static char SCCSid[] = "$SunId$ SGI"; @@ -11,43 +11,39 @@ static char SCCSid[] = "$SunId$ SGI"; #include "rholo.h" #include "rhdisp.h" #include "rhdriver.h" +#include "random.h" -extern GCOORD *getviewcells(); +#ifndef MAXDIST +#define MAXDIST 42 /* maximum distance outside section */ +#endif +#ifndef NVSAMPS +#define NVSAMPS 16384 /* number of ray samples per view */ +#endif +#ifndef MEYERNG +#define MEYERNG 0.1 /* target mean eye range (rel. to grid) */ +#endif +#ifndef MAXTODO +#define MAXTODO 3 /* maximum sections to look at */ +#endif +#ifndef MAXDRAT +#define MAXDRAT 3.0 /* maximum distance ratio btwn. cand. sect. */ +#endif -typedef struct { - 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} -}; - #define CBEAMBLK 1024 /* cbeam allocation block size */ static struct beamcomp { - short wants; /* flags telling which voxels want us */ - short hd; /* holodeck section number */ + int hd; /* holodeck section number */ int bi; /* beam index */ + int4 nr; /* number of samples desired */ } *cbeam = NULL; /* current beam list */ +VIEWPOINT cureye; /* current eye position */ + static int ncbeams = 0; /* number of sorted beams in cbeam */ 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 */ -}; /* beam origin and action */ - - int newcbeam() /* allocate new entry at end of cbeam array */ { @@ -86,8 +82,10 @@ register struct beamcomp *cb1, *cb2; { register int c; - if (!cb1->wants) /* put orphans at the end, unsorted */ - return(cb2->wants); + if (!cb1->nr) /* put orphans at the end, unsorted */ + return(cb2->nr); + if (!cb2->nr) + 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 */ @@ -103,7 +101,7 @@ int hd, bi; if (ncbeams <= 0) return(-1); - cb.wants = 0; cb.hd = hd; cb.bi = bi; + cb.hd = hd; cb.bi = bi; cb.nr = 0; p = (struct beamcomp *)bsearch((char *)&cb, (char *)cbeam, ncbeams, sizeof(struct beamcomp), cbeamcmp); if (p == NULL) @@ -131,7 +129,7 @@ int bi; if (bi < 1 | bi > nbeams(hdlist[hd])) error(INTERNAL, "illegal beam index in getcbeam"); n = newcbeam(); /* allocate and assign */ - cbeam[n].wants = 0; cbeam[n].hd = hd; cbeam[n].bi = bi; + cbeam[n].nr = 0; cbeam[n].hd = hd; cbeam[n].bi = bi; return(n); } @@ -149,19 +147,17 @@ int adopt; if (adopt) return; for (i = ncbeams; i--; ) /* identify orphans */ - if (cbeam[i].wants) + if (cbeam[i].nr) break; xcbeams = ncbeams - ++i; /* put orphans after ncbeams */ ncbeams = i; } -cbeamop(op, bl, n, v, hr, vr) /* update beams on server list */ +cbeamop(op, bl, n) /* update beams on server list */ int op; register struct beamcomp *bl; int n; -VIEW *v; -int hr, vr; { register PACKHEAD *pa; register int i; @@ -170,12 +166,12 @@ int hr, vr; return; pa = (PACKHEAD *)malloc(n*sizeof(PACKHEAD)); if (pa == NULL) - error(SYSTEM, "out of memory in cbeamadd"); + error(SYSTEM, "out of memory in cbeamop"); for (i = 0; i < n; i++) { pa[i].hd = bl[i].hd; pa[i].bi = bl[i].bi; - pa[i].nr = v==NULL ? 0 : - npixels(v, hr, vr, hdlist[bl[i].hd], bl[i].bi); + pa[i].nr = bl[i].nr; + pa[i].nc = 0; } serv_request(op, n*sizeof(PACKHEAD), (char *)pa); free((char *)pa); @@ -183,259 +179,147 @@ int hr, vr; int -set_voxels(vl, n) /* set new voxel array */ -VOXL vl[8]; -int n; +comptodo(tdl, vw) /* compute holodeck sections in view */ +int tdl[MAXTODO+1]; +VIEW *vw; { - short wmap[256]; - int vmap[8]; - int comn = 0; - int no; + int n = 0; + FVECT gp, dv; + double dist2[MAXTODO+1], thisdist2; register int i, j; - /* find common voxels */ - for (j = 0; j < 8 && voxel[j].hd >= 0; j++) { - vmap[j] = -1; - for (i = n; i--; ) - if (!bcmp((char *)(vl+i), (char *)(voxel+j), - sizeof(VOXL))) { - vmap[j] = i; - comn |= 1<vp); + for (j = 0; j < 3; j++) + if (gp[j] < 0.) + dv[j] = -gp[j]; + else if (gp[j] > hdlist[i]->grid[j]) + dv[j] = gp[j] - hdlist[i]->grid[j]; + else + dv[j] = 0.; + thisdist2 = DOT(dv,dv); + for (j = n; j > 0 && thisdist2 < dist2[j-1]; j--) { + tdl[j] = tdl[j-1]; + dist2[j] = dist2[j-1]; + } + tdl[j] = i; + dist2[j] = thisdist2; + if (n < MAXTODO) + n++; } - no = comn ? j : 0; /* compute flag mapping */ - for (i = 256; i--; ) { - wmap[i] = 0; - for (j = no; j--; ) - if (vmap[j] >= 0 && i & 1< MAXDIST*MAXDIST) { + error(COMMAND, "move past outer limits"); + return(0); } - /* fix cbeam flags */ - for (i = ncbeams; i--; ) - 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; - return(comn); /* return bit array of common voxels */ + /* avoid big differences */ + for (j = 1; j < n; j++) + if (dist2[j] > MAXDRAT*MAXDRAT*dist2[j-1]) + n = j; + tdl[n] = -1; + return(n); } -int -get_voxels(vl, vp) /* find voxels corresponding to view point */ -VOXL vl[8]; -FVECT vp; +addview(hd, vw, hres, vres) /* add view for section */ +int hd; +VIEW *vw; +int hres, vres; { - static int lastn = 0, lastd = -1; - int n = 0; - FVECT gp; - double d; - int dist, bestd = 0x7fff; - VOXL vox; - register int i, j, k; - /* find closest voxels */ - for (i = 0; n < 8 && hdlist[i]; i++) { - hdgrid(gp, hdlist[i], vp); - for (j = 0; n < 8 && j < 8; j++) { - dist = 0; - for (k = 0; k < 3; k++) { - d = gp[k] - .5 + (j>>k & 1); - if (d < 0.) - dist += -(vox.i[k] = (int)d - 1); - else if ((vox.i[k] = d) >= hdlist[i]->grid[k]) - dist += vox.i[k] - - hdlist[i]->grid[k] + 1; - } - if (dist > bestd) /* others were closer */ + int sampquant; + int h, v, shr, svr; + GCOORD gc[2]; + FVECT rorg, rdir; + /* compute sampling grid */ + if (hres|vres && hres*vres <= NVSAMPS) { + shr = hres; svr = vres; + sampquant = 1; + } else { + shr = sqrt(NVSAMPS/viewaspect(vw)) + .5; + svr = (NVSAMPS + shr/2)/shr; + sampquant = (hres*vres + shr*svr/2)/(shr*svr); + } + /* intersect sample rays with section */ + for (v = svr; v--; ) + for (h = shr; h--; ) { + if (viewray(rorg, rdir, vw, (v+frandom())/svr, + (h+frandom())/shr) < -FTINY) continue; - if (dist < bestd) { /* start closer list */ - n = 0; - bestd = dist; - } - vox.hd = i; /* add this voxel */ - copystruct(&vl[n], &vox); - n++; + if (hdinter(gc, NULL, NULL, hdlist[hd], rorg, rdir) + >= FHUGE) + continue; + cbeam[getcbeam(hd,hdbindex(hdlist[hd],gc))].nr += + sampquant; } - } - /* warn of dangerous moves */ - if (n < lastn && bestd >= lastd) - error(WARNING, "moving outside holodeck section"); - else if (n > lastn && bestd <= lastd) - error(WARNING, "moving inside holodeck section"); - lastd = bestd; - return(lastn = n); } -int -dobeam(gcp, bp) /* express interest or disintrest in a beam */ -GCOORD *gcp; -register struct beamact *bp; +beam_init(fresh) /* clear beam list for new view(s) */ +int fresh; { - GCOORD gc[2]; - int bi, i; - /* compute beam index */ - 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) - 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 */ - return(i == ncbeams+xcbeams-1); /* return 1 if totally new */ - } - /* else delete it */ - i = findcbeam(voxel[bp->ca.vi].hd, bi); - if (i >= 0 && cbeam[i].wants & 1<ca.vi) { - cbeam[i].wants &= ~(1<ca.vi); /* we don't want it */ - return(1); /* indicate change */ - } - return(0); + register int i; + + if (fresh) /* discard old beams? */ + ncbeams = xcbeams = 0; + else /* else clear sample requests */ + for (i = ncbeams+xcbeams; i--; ) + cbeam[i].nr = 0; + cureye.rng = 0.; } - -int -docell(gcp, cap) /* find beams corresponding to cell and voxel */ -GCOORD *gcp; -register struct cellact *cap; +beam_view(vn, hr, vr) /* add beam view (if advisable) */ +VIEW *vn; +int hr, vr; { - FVECT org, dir[4]; - FVECT gp, cv[4], vc; - struct beamact bo; + int todo[MAXTODO+1], n; + double hdgsiz, d; + register HOLO *hp; 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; + /* sort our list */ + cbeamsort(1); + /* add view to nearby sections */ + if (!(n = comptodo(todo, vn))) + return(0); + for (i = 0; i < n; i++) + addview(todo[i], vn, hr, vr); + if (MEYERNG <= FTINY || vn->type == VT_PAR) + return(1); + hdgsiz = 0.; /* compute mean grid size */ + for (i = 0; i < n; i++) { + hp = hdlist[todo[i]]; + hdgsiz += 1./3. / VLEN(hp->wg[0]) + + 1./3. / VLEN(hp->wg[1]) + + 1./3. / VLEN(hp->wg[2]) ; } - 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 */ - } + hdgsiz /= (double)n; + /* add to current eye position */ + if (cureye.rng <= FTINY) { + VCOPY(cureye.vpt, vn->vp); + cureye.rng = MEYERNG * hdgsiz; + } else if ((d = sqrt(dist2(vn->vp,cureye.vpt))) + MEYERNG*hdgsiz > + cureye.rng) { + for (i = 3; i--; ) + cureye.vpt[i] = 0.5*(cureye.vpt[i] + vn->vp[i]); + cureye.rng = 0.5*(cureye.rng + MEYERNG*hdgsiz + d); } - /* 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(1); } int -doview(cap, vp) /* visit cells for a given view */ -struct cellact *cap; -VIEW *vp; +beam_sync(all) /* update beam list on server */ +int all; { - int orient; - FVECT org, dir[4]; - /* compute view pyramid */ - 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)); -} - - -mvview(voxi, vold, vnew) /* move view for a voxel */ -int voxi; -VIEW *vold, *vnew; -{ - int netchange = 0; - struct cellact oca, nca; - int ocnt, ncnt; - int c; - register GCOORD *ogcp, *ngcp; - /* get old and new cell lists */ - ogcp = getviewcells(&ocnt, hdlist[voxel[voxi].hd], vold); - ngcp = getviewcells(&ncnt, hdlist[voxel[voxi].hd], vnew); - /* set up actions */ - oca.vi = nca.vi = voxi; - oca.rev = nca.rev = 0; - oca.add = 0; nca.add = 1; - if ((oca.rev = ocnt < 0)) - ocnt = -ocnt; - if ((nca.rev = ncnt < 0)) - ncnt = -ncnt; - /* add and delete cells in order */ - while (ocnt > 0 & ncnt > 0) - if ((c = cellcmp(ogcp, ngcp)) > 0) { /* new cell */ - netchange += docell(ngcp++, &nca); - ncnt--; - } else if (c < 0) { /* obsolete cell */ - netchange -= docell(ogcp++, &oca); - ocnt--; - } else { /* same cell? */ - if (oca.rev != nca.rev) /* not */ - netchange += docell(ngcp, &nca) - - docell(ogcp, &oca); - ogcp++; ocnt--; - ngcp++; ncnt--; - } - /* take care of list tails */ - for ( ; ncnt > 0; ncnt--) - netchange += docell(ngcp++, &nca); - for ( ; ocnt > 0; ocnt--) - netchange -= docell(ogcp++, &oca); - /* clean up */ - if (ogcp != NULL) free((char *)ogcp); - if (ngcp != NULL) free((char *)ngcp); - return(netchange); -} - - -beam_sync() /* synchronize beams on server */ -{ - cbeamop(DR_NEWSET, cbeam, ncbeams, &odev.v, odev.hres, odev.vres); -} - - -beam_view(vo, vn) /* change beam view */ -VIEW *vo, *vn; -{ - struct cellact ca; - VOXL vlnew[8]; - int n, comn; - - if (!vn->type) { /* clear our beam list */ - set_voxels(vlnew, 0); - cbeamop(DR_DELSET, cbeam, ncbeams, NULL, 0, 0); - ncbeams = 0; - return; - } - /* find our new voxels */ - n = get_voxels(vlnew, vn->vp); - /* set the new voxels */ - comn = set_voxels(vlnew, n); - if (!vo->type) - comn = 0; - ca.add = 1; /* update our beam list */ - for (ca.vi = n; ca.vi--; ) - if (comn & 1<