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

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 int2   wants;  /* flags telling which voxels want us */
        unsigned int2   hd;     /* holodeck section number */
        int4    bi;             /* beam index */
        int4    nr;             /* number of samples desired */
} *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? */
        VIEW    *vp;            /* view for image */
        short   hr, vr;         /* image resolution */
};              /* 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; cb.nr = 0;
        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 = cbeam[n].nr = 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)              /* update beams on server list */
int     op;
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 cbeamop");
        for (i = 0; i < n; i++) {
                pa[i].hd = bl[i].hd;
                pa[i].bi = bl[i].bi;
                pa[i].nr = bl[i].nr;
                pa[i].nc = 0;
        }
        serv_request(op, n*sizeof(PACKHEAD), (char *)pa);
        free((char *)pa);
}


add_voxels(vp)          /* add voxels corresponding to view point */
FVECT   vp;
{
        int     first, n, rfl = 0;
        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 && voxel[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;
                                rfl = 0;
                        }
                                                /* check if already in list */
                        for (k = first; k--; )
                                if (voxel[k].hd == i &&
                                                voxel[k].i[0] == vox.i[0] &&
                                                voxel[k].i[1] == vox.i[1] &&
                                                voxel[k].i[2] == vox.i[2])
                                        break;
                        if (k >= 0) {
                                rfl |= 1<<k;
                                continue;
                        }
                        vox.hd = i;             /* add this voxel */
                        copystruct(&voxel[n], &vox);
                        rfl |= 1<<n++;
                }
        }
                                        /* check for really stupid move */
        if (bestd > MAXDIST) {
                error(COMMAND, "move past outer limits");
                return(0);
        }
        if (n < MAXVOXEL)
                voxel[n].hd = -1;
        return(rfl);
}


int
dobeam(gcp, bp)         /* express interest or disintrest in a beam */
GCOORD  *gcp;
register struct beamact *bp;
{
        GCOORD  gc[2];
        int     bi, i, n;
                                        /* 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 */
                n = npixels(bp->ca.vp, bp->ca.hr, bp->ca.vr,
                                hdlist[cbeam[i].hd], cbeam[i].bi);
                if (n > cbeam[i].nr)
                        cbeam[i].nr = n;
                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 */
                if (!cbeam[i].wants)
                        cbeam[i].nr = 0;
                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)                     /* visit cells for a given view */
struct cellact  *cap;
{
        int     orient;
        FVECT   org, dir[4];
                                        /* compute view pyramid */
        orient = viewpyramid(org, dir, hdlist[voxel[cap->vi].hd], cap->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));
}


beam_init()                     /* clear beam list for new view(s) */
{
        register int    i;
                                        /* clear desire flags */
        for (i = ncbeams+xcbeams; i--; )
                cbeam[i].wants = cbeam[i].nr = 0;
        voxel[0].hd = -1;               /* clear voxel list */
}


beam_view(vn, hr, vr)           /* add beam view (if advisable) */
VIEW    *vn;
int     hr, vr;
{
        struct cellact  ca;
        int     vfl;
                                        /* sort our list */
        cbeamsort(1);
                                        /* add new voxels */
        vfl = add_voxels(vn->vp);
        if (!vfl)
                return(0);
        ca.vp = vn; ca.hr = hr; ca.vr = vr;
        ca.add = 1;                     /* update our beam list */
        for (ca.vi = 0; vfl; vfl >>= 1, ca.vi++)
                if (vfl & 1)
                        doview(&ca);
        return(1);
}


int
beam_sync(all)                  /* update beam list on server */
int     all;
{
                                        /* sort list to put orphans at end */
        cbeamsort(0);
        if (all)
                cbeamop(DR_NEWSET, cbeam, ncbeams);
        else
                cbeamop(DR_ADJSET, cbeam, ncbeams+xcbeams);
        xcbeams = 0;                    /* truncate our list */
        return(ncbeams);
}
Revision:	3.21
Committed:	Thu May 14 13:23:00 1998 UTC (27 years, 5 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.20:	+66 -171 lines
Log Message:	added multiple device view capability
#	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.1	typedef struct {
22	gregl	3.2	int hd; /* holodeck section number (-1 if inactive) */
23	gregl	3.1	int i[3]; /* voxel index (may be outside section) */
24			} VOXL; /* a voxel */
25
26	gwlarson	3.20	static VOXL voxel[MAXVOXEL] = {{-1}}; /* current voxel list */
27	gregl	3.1
28			#define CBEAMBLK 1024 /* cbeam allocation block size */
29
30			static struct beamcomp {
31	gwlarson	3.21	unsigned int2 wants; /* flags telling which voxels want us */
32			unsigned int2 hd; /* holodeck section number */
33			int4 bi; /* beam index */
34			int4 nr; /* number of samples desired */
35	gregl	3.1	} cbeam = NULL; / current beam list */
36
37			static int ncbeams = 0; /* number of sorted beams in cbeam */
38			static int xcbeams = 0; /* extra (unregistered) beams past ncbeams */
39			static int maxcbeam = 0; /* size of cbeam array */
40
41			struct cellact {
42			short vi; /* voxel index */
43			short add; /* zero means delete */
44	gregl	3.5	short rev; /* reverse ray direction? */
45	gwlarson	3.21	VIEW vp; / view for image */
46			short hr, vr; /* image resolution */
47	gregl	3.1	}; /* action for cell */
48
49			struct beamact {
50			struct cellact ca; /* cell action */
51			GCOORD gc; /* grid coordinate */
52			}; /* beam origin and action */
53
54
55			int
56			newcbeam() /* allocate new entry at end of cbeam array */
57			{
58			int i;
59
60			if ((i = ncbeams + xcbeams++) >= maxcbeam) { /* grow array */
61			maxcbeam += CBEAMBLK;
62			if (cbeam == NULL)
63			cbeam = (struct beamcomp *)malloc(
64			maxcbeam*sizeof(struct beamcomp) );
65			else
66			cbeam = (struct beamcomp )realloc( (char )cbeam,
67			maxcbeam*sizeof(struct beamcomp) );
68			if (cbeam == NULL)
69			error(SYSTEM, "out of memory in newcbeam");
70			}
71			return(i);
72			}
73
74
75			int
76			cbeamcmp(cb1, cb2) /* compare two cbeam entries for sort: keep orphans */
77			register struct beamcomp cb1, cb2;
78			{
79			register int c;
80
81			if ((c = cb1->bi - cb2->bi)) /* sort on beam index first */
82			return(c);
83			return(cb1->hd - cb2->hd); /* use hd to resolve matches */
84			}
85
86
87			int
88			cbeamcmp2(cb1, cb2) /* compare two cbeam entries for sort: no orphans */
89			register struct beamcomp cb1, cb2;
90			{
91			register int c;
92
93			if (!cb1->wants) /* put orphans at the end, unsorted */
94			return(cb2->wants);
95	gregl	3.15	if (!cb2->wants)
96			return(-1);
97	gregl	3.1	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	gwlarson	3.21	cb.wants = 0; cb.hd = hd; cb.bi = bi; cb.nr = 0;
113	gregl	3.1	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	gwlarson	3.21	cbeam[n].wants = cbeam[n].nr = 0; cbeam[n].hd = hd; cbeam[n].bi = bi;
141	gregl	3.1	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	gwlarson	3.21	cbeamop(op, bl, n) /* update beams on server list */
166	gregl	3.4	int op;
167	gregl	3.1	register struct beamcomp *bl;
168			int n;
169			{
170			register PACKHEAD *pa;
171			register int i;
172
173			if (n <= 0)
174			return;
175			pa = (PACKHEAD )malloc(nsizeof(PACKHEAD));
176			if (pa == NULL)
177	gwlarson	3.21	error(SYSTEM, "out of memory in cbeamop");
178	gregl	3.1	for (i = 0; i < n; i++) {
179			pa[i].hd = bl[i].hd;
180			pa[i].bi = bl[i].bi;
181	gwlarson	3.21	pa[i].nr = bl[i].nr;
182	gregl	3.16	pa[i].nc = 0;
183	gregl	3.1	}
184	gregl	3.4	serv_request(op, nsizeof(PACKHEAD), (char )pa);
185	gregl	3.1	free((char *)pa);
186			}
187
188
189	gwlarson	3.21	add_voxels(vp) /* add voxels corresponding to view point */
190	gregl	3.1	FVECT vp;
191			{
192	gwlarson	3.21	int first, n, rfl = 0;
193	gregl	3.1	FVECT gp;
194			double d;
195			int dist, bestd = 0x7fff;
196			VOXL vox;
197			register int i, j, k;
198	gwlarson	3.20	/* count voxels in list already */
199	gwlarson	3.21	for (first = 0; first < MAXVOXEL && voxel[first].hd >= 0; first++)
200	gwlarson	3.20	;
201	gregl	3.1	/* find closest voxels */
202	gwlarson	3.20	for (n = first, i = 0; n < MAXVOXEL && hdlist[i]; i++) {
203	gregl	3.1	hdgrid(gp, hdlist[i], vp);
204	gwlarson	3.20	for (j = 0; n < MAXVOXEL && j < 8; j++) {
205	gregl	3.1	dist = 0;
206			for (k = 0; k < 3; k++) {
207			d = gp[k] - .5 + (j>>k & 1);
208			if (d < 0.)
209			dist += -(vox.i[k] = (int)d - 1);
210			else if ((vox.i[k] = d) >= hdlist[i]->grid[k])
211			dist += vox.i[k] -
212			hdlist[i]->grid[k] + 1;
213			}
214			if (dist > bestd) /* others were closer */
215			continue;
216			if (dist < bestd) { /* start closer list */
217	gwlarson	3.20	n = first;
218	gregl	3.1	bestd = dist;
219	gwlarson	3.21	rfl = 0;
220	gregl	3.1	}
221	gwlarson	3.20	/* check if already in list */
222			for (k = first; k--; )
223	gwlarson	3.21	if (voxel[k].hd == i &&
224			voxel[k].i[0] == vox.i[0] &&
225			voxel[k].i[1] == vox.i[1] &&
226			voxel[k].i[2] == vox.i[2])
227	gwlarson	3.20	break;
228	gwlarson	3.21	if (k >= 0) {
229			rfl \|= 1<<k;
230	gwlarson	3.20	continue;
231	gwlarson	3.21	}
232	gregl	3.1	vox.hd = i; /* add this voxel */
233	gwlarson	3.21	copystruct(&voxel[n], &vox);
234			rfl \|= 1<<n++;
235	gregl	3.1	}
236			}
237	gregl	3.9	/* check for really stupid move */
238			if (bestd > MAXDIST) {
239	gregl	3.10	error(COMMAND, "move past outer limits");
240	gregl	3.9	return(0);
241			}
242	gwlarson	3.20	if (n < MAXVOXEL)
243	gwlarson	3.21	voxel[n].hd = -1;
244			return(rfl);
245	gregl	3.1	}
246
247
248			int
249			dobeam(gcp, bp) /* express interest or disintrest in a beam */
250			GCOORD *gcp;
251			register struct beamact *bp;
252			{
253			GCOORD gc[2];
254	gwlarson	3.21	int bi, i, n;
255	gregl	3.1	/* compute beam index */
256	gregl	3.5	if (bp->ca.rev) {
257			copystruct(gc, &bp->gc);
258			copystruct(gc+1, gcp);
259			} else {
260			copystruct(gc, gcp);
261			copystruct(gc+1, &bp->gc);
262			}
263	gregl	3.1	if ((bi = hdbindex(hdlist[voxel[bp->ca.vi].hd], gc)) <= 0)
264	gregl	3.2	error(CONSISTENCY, "bad grid coordinate in dobeam");
265	gregl	3.1	if (bp->ca.add) { /* add it in */
266			i = getcbeam(voxel[bp->ca.vi].hd, bi);
267			cbeam[i].wants \|= 1<<bp->ca.vi; /* say we want it */
268	gwlarson	3.21	n = npixels(bp->ca.vp, bp->ca.hr, bp->ca.vr,
269			hdlist[cbeam[i].hd], cbeam[i].bi);
270			if (n > cbeam[i].nr)
271			cbeam[i].nr = n;
272	gregl	3.1	return(i == ncbeams+xcbeams-1); /* return 1 if totally new */
273			}
274			/* else delete it */
275			i = findcbeam(voxel[bp->ca.vi].hd, bi);
276			if (i >= 0 && cbeam[i].wants & 1<<bp->ca.vi) {
277			cbeam[i].wants &= ~(1<<bp->ca.vi); /* we don't want it */
278	gwlarson	3.21	if (!cbeam[i].wants)
279			cbeam[i].nr = 0;
280	gregl	3.1	return(1); /* indicate change */
281			}
282			return(0);
283			}
284
285
286
287			int
288			docell(gcp, cap) /* find beams corresponding to cell and voxel */
289			GCOORD *gcp;
290			register struct cellact *cap;
291			{
292	gregl	3.10	register HOLO *hp = hdlist[voxel[cap->vi].hd];
293	gregl	3.1	FVECT org, dir[4];
294	gregl	3.10	FVECT vgp, cgp, vc;
295			FVECT v1, v2;
296	gregl	3.1	struct beamact bo;
297	gregl	3.10	int axmax, j;
298			double d, avmax;
299	gregl	3.1	register int i;
300	gregl	3.10	/* compute cell center */
301			cgp[gcp->w>>1] = gcp->w&1 ? hp->grid[gcp->w>>1] : 0 ;
302	gregl	3.18	cgp[hdwg0[gcp->w]] = gcp->i[0] + .5;
303			cgp[hdwg1[gcp->w]] = gcp->i[1] + .5;
304	gregl	3.10	hdworld(org, hp, cgp);
305			/* compute direction to voxel center */
306			for (i = 3; i--; )
307	gregl	3.11	vgp[i] = voxel[cap->vi].i[i] + .5;
308	gregl	3.10	hdworld(vc, hp, vgp);
309			for (i = 3; i--; )
310			vc[i] -= org[i];
311			/* compute maximum area axis */
312			axmax = -1; avmax = 0;
313			for (i = 3; i--; ) {
314			d = vgp[i] - cgp[i];
315	gregl	3.12	if (d < 0.) d = -d;
316	gregl	3.10	if (d > avmax) {
317			avmax = d;
318			axmax = i;
319	gregl	3.1	}
320			}
321	gregl	3.10	#ifdef DEBUG
322	gregl	3.12	if (axmax < 0.)
323	gregl	3.10	error(CONSISTENCY, "botched axis computation in docell");
324			#endif
325			/* compute offset vectors */
326			d = 0.5/hp->grid[j=(axmax+1)%3];
327			for (i = 3; i--; )
328			v1[i] = hp->xv[j][i] * d;
329			d = 0.5/hp->grid[j=(axmax+2)%3];
330	gregl	3.18	if (DOT(hp->wg[axmax], vc) < 0.)
331			d = -d; /* reverse vertex order */
332	gregl	3.10	for (i = 3; i--; )
333			v2[i] = hp->xv[j][i] * d;
334			/* compute voxel pyramid */
335			for (i = 3; i--; ) {
336			dir[0][i] = vc[i] - v1[i] - v2[i];
337			dir[1][i] = vc[i] + v1[i] - v2[i];
338			dir[2][i] = vc[i] + v1[i] + v2[i];
339			dir[3][i] = vc[i] - v1[i] + v2[i];
340			}
341	gregl	3.1	/* visit beams for opposite cells */
342			copystruct(&bo.ca, cap);
343			copystruct(&bo.gc, gcp);
344	gregl	3.10	return(visit_cells(org, dir, hp, dobeam, &bo));
345	gregl	3.1	}
346
347
348			int
349	gwlarson	3.21	doview(cap) /* visit cells for a given view */
350	gregl	3.1	struct cellact *cap;
351			{
352	gregl	3.5	int orient;
353	gregl	3.1	FVECT org, dir[4];
354			/* compute view pyramid */
355	gwlarson	3.21	orient = viewpyramid(org, dir, hdlist[voxel[cap->vi].hd], cap->vp);
356	gregl	3.5	if (!orient)
357			error(INTERNAL, "unusable view in doview");
358			cap->rev = orient < 0;
359	gregl	3.1	/* visit cells within pyramid */
360			return(visit_cells(org, dir, hdlist[voxel[cap->vi].hd], docell, cap));
361			}
362
363
364	gwlarson	3.21	beam_init() /* clear beam list for new view(s) */
365	gregl	3.1	{
366	gwlarson	3.21	register int i;
367			/* clear desire flags */
368			for (i = ncbeams+xcbeams; i--; )
369			cbeam[i].wants = cbeam[i].nr = 0;
370			voxel[0].hd = -1; /* clear voxel list */
371	gregl	3.1	}
372
373
374	gwlarson	3.21	beam_view(vn, hr, vr) /* add beam view (if advisable) */
375			VIEW *vn;
376			int hr, vr;
377	gregl	3.4	{
378	gwlarson	3.21	struct cellact ca;
379			int vfl;
380			/* sort our list */
381			cbeamsort(1);
382			/* add new voxels */
383			vfl = add_voxels(vn->vp);
384			if (!vfl)
385			return(0);
386			ca.vp = vn; ca.hr = hr; ca.vr = vr;
387			ca.add = 1; /* update our beam list */
388			for (ca.vi = 0; vfl; vfl >>= 1, ca.vi++)
389			if (vfl & 1)
390			doview(&ca);
391			return(1);
392	gregl	3.4	}
393
394
395	gwlarson	3.21	int
396			beam_sync(all) /* update beam list on server */
397			int all;
398	gregl	3.1	{
399			/* sort list to put orphans at end */
400			cbeamsort(0);
401	gwlarson	3.21	if (all)
402			cbeamop(DR_NEWSET, cbeam, ncbeams);
403			else
404			cbeamop(DR_ADJSET, cbeam, ncbeams+xcbeams);
405	gregl	3.1	xcbeams = 0; /* truncate our list */
406	gwlarson	3.21	return(ncbeams);
407	gregl	3.1	}