src/hd/rhdisp2.c

/* Copyright (c) 1998 Silicon Graphics, Inc. */

#ifndef lint
static char SCCSid[] = "$SunId$ SGI";
#endif

/*
 * Holodeck beam tracking for display process
 */

#include "rholo.h"
#include "rhdisp.h"
#include "rhdriver.h"

#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 (-1 if inactive) */
        int     i[3];           /* voxel index (may be outside section) */
} VOXL;                 /* a voxel */

static VOXL voxel[MAXVOXEL] = {{-1}};   /* current voxel list */

#define CBEAMBLK        1024    /* cbeam allocation block size */

static struct beamcomp {
        unsigned short  wants;  /* flags telling which voxels want us */
        unsigned short  hd;     /* holodeck section number */
        int     bi;             /* beam index */
} *cbeam = NULL;        /* current beam list */

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 */
{
        int     i;

        if ((i = ncbeams + xcbeams++) >= maxcbeam) {    /* grow array */
                maxcbeam += CBEAMBLK;
                if (cbeam == NULL)
                        cbeam = (struct beamcomp *)malloc(
                                        maxcbeam*sizeof(struct beamcomp) );
                else
                        cbeam = (struct beamcomp *)realloc( (char *)cbeam,
                                        maxcbeam*sizeof(struct beamcomp) );
                if (cbeam == NULL)
                        error(SYSTEM, "out of memory in newcbeam");
        }
        return(i);
}


int
cbeamcmp(cb1, cb2)      /* compare two cbeam entries for sort: keep orphans */
register struct beamcomp        *cb1, *cb2;
{
        register int    c;

        if ((c = cb1->bi - cb2->bi))    /* sort on beam index first */
                return(c);
        return(cb1->hd - cb2->hd);      /* use hd to resolve matches */
}


int
cbeamcmp2(cb1, cb2)     /* compare two cbeam entries for sort: no orphans */
register struct beamcomp        *cb1, *cb2;
{
        register int    c;

        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 */
}


int
findcbeam(hd, bi)       /* find the specified beam in our sorted list */
int     hd, bi;
{
        struct beamcomp cb;
        register struct beamcomp        *p;

        if (ncbeams <= 0)
                return(-1);
        cb.wants = 0; cb.hd = hd; cb.bi = bi;
        p = (struct beamcomp *)bsearch((char *)&cb, (char *)cbeam, ncbeams,
                        sizeof(struct beamcomp), cbeamcmp);
        if (p == NULL)
                return(-1);
        return(p - cbeam);
}


int
getcbeam(hd, bi)        /* get the specified beam, allocating as necessary */
register int    hd;
int     bi;
{
        register int    n;
                                /* first, look in sorted list */
        if ((n = findcbeam(hd, bi)) >= 0)
                return(n);
                                /* linear search through xcbeams to be sure */
        for (n = ncbeams+xcbeams; n-- > ncbeams; )
                if (cbeam[n].bi == bi && cbeam[n].hd == hd)
                        return(n);
                                /* check legality */
        if (hd < 0 | hd >= HDMAX || hdlist[hd] == NULL)
                error(INTERNAL, "illegal holodeck number in getcbeam");
        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;
        return(n);
}


cbeamsort(adopt)        /* sort our beam list, possibly turning out orphans */
int     adopt;
{
        register int    i;

        if (!(ncbeams += xcbeams))
                return;
        xcbeams = 0;
        qsort((char *)cbeam, ncbeams, sizeof(struct beamcomp),
                        adopt ? cbeamcmp : cbeamcmp2);
        if (adopt)
                return;
        for (i = ncbeams; i--; )        /* identify orphans */
                if (cbeam[i].wants)
                        break;
        xcbeams = ncbeams - ++i;        /* put orphans after ncbeams */
        ncbeams = i;
}


cbeamop(op, bl, n, v, hr, vr)   /* update beams on server list */
int     op;
register struct beamcomp        *bl;
int     n;
VIEW    *v;
int     hr, vr;
{
        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 cbeamadd");
        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].nc = 0;
        }
        serv_request(op, n*sizeof(PACKHEAD), (char *)pa);
        free((char *)pa);
}


int
set_voxels(vl, n)       /* set new voxel array */
VOXL    vl[MAXVOXEL];
int     n;
{
        short   wmap[256];
        int     vmap[MAXVOXEL];
        int     comn = 0;
        int     no;
        register int    i, j;
                                        /* find common voxels */
        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),
                                        sizeof(VOXL))) {
                                vmap[j] = i;
                                comn |= 1<<i;
                                break;
                        }
        }
        no = comn ? j : 0;              /* compute flag mapping */
        for (i = 256; i--; ) {
                wmap[i] = 0;
                for (j = no; j--; )
                        if (vmap[j] >= 0 && i & 1<<j)
                                wmap[i] |= 1<<vmap[j];
        }
                                        /* 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));
        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[MAXVOXEL];
FVECT   vp;
{
        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 (n = first, i = 0; n < MAXVOXEL && hdlist[i]; i++) {
                hdgrid(gp, hdlist[i], vp);
                for (j = 0; n < MAXVOXEL && 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 */
                                continue;
                        if (dist < bestd) {     /* start closer list */
                                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);
}


int
dobeam(gcp, bp)         /* express interest or disintrest in a beam */
GCOORD  *gcp;
register struct beamact *bp;
{
        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<<bp->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<<bp->ca.vi) {
                cbeam[i].wants &= ~(1<<bp->ca.vi);      /* we don't want it */
                return(1);                      /* indicate change */
        }
        return(0);
}


int
docell(gcp, cap)        /* find beams corresponding to cell and voxel */
GCOORD  *gcp;
register struct cellact *cap;
{
        register HOLO   *hp = hdlist[voxel[cap->vi].hd];
        FVECT   org, dir[4];
        FVECT   vgp, cgp, vc;
        FVECT   v1, v2;
        struct beamact  bo;
        int     axmax, j;
        double  d, avmax;
        register int    i;
                                /* 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, hp, dobeam, &bo));
}


int
doview(cap, vp)                 /* visit cells for a given view */
struct cellact  *cap;
VIEW    *vp;
{
        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     nmatch = 0;
        GCOORD  *ogcl, *ngcl;
        register int    c;
        register GCOORD *ogcp, *ngcp;
                                /* get old and new cell lists */
        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 (nmatch < ocnt>>1) {         /* faster to just delete old cells? */
                for (c = ncbeams; c--; )
                        if (cbeam[c].wants & 1<<voxi) {
                                cbeam[c].wants &= ~(1<<voxi);
                                netchange--;
                        }
                free((char *)ogcl);
                ogcl = NULL; ocnt = 0;
        }
                                /* 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) {                     /* old cell */
                        netchange -= docell(ogcp++, &oca);
                        ocnt--;
                } else {                                /* same cell */
                        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 (ogcl != NULL) free((char *)ogcl);
        if (ngcl != NULL) free((char *)ngcl);
        return(netchange);
}


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[MAXVOXEL];
        int     n, comn;

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