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        32      /* 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 {
        int     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   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->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 */
}


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.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].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].nr)
                        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);
}


unsigned int4
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 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");
                                        /* add it in */
        i = getcbeam(voxel[bp->ca.vi].hd, bi);
        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 */
}


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].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;
        unsigned int4   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;
                                        /* 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.23
Committed:	Mon Jul 6 18:17:00 1998 UTC (27 years, 3 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.22:	+1 -1 lines
Log Message:	fixed comment
#	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.22	#define MAXVOXEL 32 /* maximum number of active voxels */
20	gwlarson	3.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.22	int hd; /* holodeck section number */
32	gwlarson	3.21	int4 bi; /* beam index */
33			int4 nr; /* number of samples desired */
34	gregl	3.1	} cbeam = NULL; / current beam list */
35
36			static int ncbeams = 0; /* number of sorted beams in cbeam */
37			static int xcbeams = 0; /* extra (unregistered) beams past ncbeams */
38			static int maxcbeam = 0; /* size of cbeam array */
39
40			struct cellact {
41			short vi; /* voxel index */
42	gregl	3.5	short rev; /* reverse ray direction? */
43	gwlarson	3.21	VIEW vp; / view for image */
44			short hr, vr; /* image resolution */
45	gregl	3.1	}; /* action for cell */
46
47			struct beamact {
48			struct cellact ca; /* cell action */
49			GCOORD gc; /* grid coordinate */
50			}; /* beam origin and action */
51
52
53			int
54			newcbeam() /* allocate new entry at end of cbeam array */
55			{
56			int i;
57
58			if ((i = ncbeams + xcbeams++) >= maxcbeam) { /* grow array */
59			maxcbeam += CBEAMBLK;
60			if (cbeam == NULL)
61			cbeam = (struct beamcomp *)malloc(
62			maxcbeam*sizeof(struct beamcomp) );
63			else
64			cbeam = (struct beamcomp )realloc( (char )cbeam,
65			maxcbeam*sizeof(struct beamcomp) );
66			if (cbeam == NULL)
67			error(SYSTEM, "out of memory in newcbeam");
68			}
69			return(i);
70			}
71
72
73			int
74			cbeamcmp(cb1, cb2) /* compare two cbeam entries for sort: keep orphans */
75			register struct beamcomp cb1, cb2;
76			{
77			register int c;
78
79			if ((c = cb1->bi - cb2->bi)) /* sort on beam index first */
80			return(c);
81			return(cb1->hd - cb2->hd); /* use hd to resolve matches */
82			}
83
84
85			int
86			cbeamcmp2(cb1, cb2) /* compare two cbeam entries for sort: no orphans */
87			register struct beamcomp cb1, cb2;
88			{
89			register int c;
90
91	gwlarson	3.22	if (!cb1->nr) /* put orphans at the end, unsorted */
92			return(cb2->nr);
93			if (!cb2->nr)
94	gregl	3.15	return(-1);
95	gregl	3.1	if ((c = cb1->bi - cb2->bi)) /* sort on beam index first */
96			return(c);
97			return(cb1->hd - cb2->hd); /* use hd to resolve matches */
98			}
99
100
101			int
102			findcbeam(hd, bi) /* find the specified beam in our sorted list */
103			int hd, bi;
104			{
105			struct beamcomp cb;
106			register struct beamcomp *p;
107
108			if (ncbeams <= 0)
109			return(-1);
110	gwlarson	3.22	cb.hd = hd; cb.bi = bi; cb.nr = 0;
111	gregl	3.1	p = (struct beamcomp )bsearch((char )&cb, (char *)cbeam, ncbeams,
112			sizeof(struct beamcomp), cbeamcmp);
113			if (p == NULL)
114			return(-1);
115			return(p - cbeam);
116			}
117
118
119			int
120			getcbeam(hd, bi) /* get the specified beam, allocating as necessary */
121			register int hd;
122			int bi;
123			{
124			register int n;
125			/* first, look in sorted list */
126			if ((n = findcbeam(hd, bi)) >= 0)
127			return(n);
128			/* linear search through xcbeams to be sure */
129			for (n = ncbeams+xcbeams; n-- > ncbeams; )
130			if (cbeam[n].bi == bi && cbeam[n].hd == hd)
131			return(n);
132			/* check legality */
133			if (hd < 0 \| hd >= HDMAX \|\| hdlist[hd] == NULL)
134			error(INTERNAL, "illegal holodeck number in getcbeam");
135			if (bi < 1 \| bi > nbeams(hdlist[hd]))
136			error(INTERNAL, "illegal beam index in getcbeam");
137			n = newcbeam(); /* allocate and assign */
138	gwlarson	3.22	cbeam[n].nr = 0; cbeam[n].hd = hd; cbeam[n].bi = bi;
139	gregl	3.1	return(n);
140			}
141
142
143			cbeamsort(adopt) /* sort our beam list, possibly turning out orphans */
144			int adopt;
145			{
146			register int i;
147
148			if (!(ncbeams += xcbeams))
149			return;
150			xcbeams = 0;
151			qsort((char *)cbeam, ncbeams, sizeof(struct beamcomp),
152			adopt ? cbeamcmp : cbeamcmp2);
153			if (adopt)
154			return;
155			for (i = ncbeams; i--; ) /* identify orphans */
156	gwlarson	3.22	if (cbeam[i].nr)
157	gregl	3.1	break;
158			xcbeams = ncbeams - ++i; /* put orphans after ncbeams */
159			ncbeams = i;
160			}
161
162
163	gwlarson	3.21	cbeamop(op, bl, n) /* update beams on server list */
164	gregl	3.4	int op;
165	gregl	3.1	register struct beamcomp *bl;
166			int n;
167			{
168			register PACKHEAD *pa;
169			register int i;
170
171			if (n <= 0)
172			return;
173			pa = (PACKHEAD )malloc(nsizeof(PACKHEAD));
174			if (pa == NULL)
175	gwlarson	3.21	error(SYSTEM, "out of memory in cbeamop");
176	gregl	3.1	for (i = 0; i < n; i++) {
177			pa[i].hd = bl[i].hd;
178			pa[i].bi = bl[i].bi;
179	gwlarson	3.21	pa[i].nr = bl[i].nr;
180	gregl	3.16	pa[i].nc = 0;
181	gregl	3.1	}
182	gregl	3.4	serv_request(op, nsizeof(PACKHEAD), (char )pa);
183	gregl	3.1	free((char *)pa);
184			}
185
186
187	gwlarson	3.22	unsigned int4
188	gwlarson	3.21	add_voxels(vp) /* add voxels corresponding to view point */
189	gregl	3.1	FVECT vp;
190			{
191	gwlarson	3.21	int first, n, rfl = 0;
192	gregl	3.1	FVECT gp;
193			double d;
194			int dist, bestd = 0x7fff;
195			VOXL vox;
196			register int i, j, k;
197	gwlarson	3.20	/* count voxels in list already */
198	gwlarson	3.21	for (first = 0; first < MAXVOXEL && voxel[first].hd >= 0; first++)
199	gwlarson	3.20	;
200	gregl	3.1	/* find closest voxels */
201	gwlarson	3.20	for (n = first, i = 0; n < MAXVOXEL && hdlist[i]; i++) {
202	gregl	3.1	hdgrid(gp, hdlist[i], vp);
203	gwlarson	3.20	for (j = 0; n < MAXVOXEL && j < 8; j++) {
204	gregl	3.1	dist = 0;
205			for (k = 0; k < 3; k++) {
206			d = gp[k] - .5 + (j>>k & 1);
207			if (d < 0.)
208			dist += -(vox.i[k] = (int)d - 1);
209			else if ((vox.i[k] = d) >= hdlist[i]->grid[k])
210			dist += vox.i[k] -
211			hdlist[i]->grid[k] + 1;
212			}
213			if (dist > bestd) /* others were closer */
214			continue;
215			if (dist < bestd) { /* start closer list */
216	gwlarson	3.20	n = first;
217	gregl	3.1	bestd = dist;
218	gwlarson	3.21	rfl = 0;
219	gregl	3.1	}
220	gwlarson	3.20	/* check if already in list */
221			for (k = first; k--; )
222	gwlarson	3.21	if (voxel[k].hd == i &&
223			voxel[k].i[0] == vox.i[0] &&
224			voxel[k].i[1] == vox.i[1] &&
225			voxel[k].i[2] == vox.i[2])
226	gwlarson	3.20	break;
227	gwlarson	3.21	if (k >= 0) {
228			rfl \|= 1<<k;
229	gwlarson	3.20	continue;
230	gwlarson	3.21	}
231	gregl	3.1	vox.hd = i; /* add this voxel */
232	gwlarson	3.21	copystruct(&voxel[n], &vox);
233			rfl \|= 1<<n++;
234	gregl	3.1	}
235			}
236	gregl	3.9	/* check for really stupid move */
237			if (bestd > MAXDIST) {
238	gregl	3.10	error(COMMAND, "move past outer limits");
239	gregl	3.9	return(0);
240			}
241	gwlarson	3.20	if (n < MAXVOXEL)
242	gwlarson	3.21	voxel[n].hd = -1;
243			return(rfl);
244	gregl	3.1	}
245
246
247			int
248	gwlarson	3.23	dobeam(gcp, bp) /* express interest in a beam */
249	gregl	3.1	GCOORD *gcp;
250			register struct beamact *bp;
251			{
252			GCOORD gc[2];
253	gwlarson	3.21	int bi, i, n;
254	gregl	3.1	/* compute beam index */
255	gregl	3.5	if (bp->ca.rev) {
256			copystruct(gc, &bp->gc);
257			copystruct(gc+1, gcp);
258			} else {
259			copystruct(gc, gcp);
260			copystruct(gc+1, &bp->gc);
261			}
262	gregl	3.1	if ((bi = hdbindex(hdlist[voxel[bp->ca.vi].hd], gc)) <= 0)
263	gregl	3.2	error(CONSISTENCY, "bad grid coordinate in dobeam");
264	gwlarson	3.22	/* add it in */
265			i = getcbeam(voxel[bp->ca.vi].hd, bi);
266			n = npixels(bp->ca.vp, bp->ca.hr, bp->ca.vr,
267			hdlist[cbeam[i].hd], cbeam[i].bi);
268			if (n > cbeam[i].nr)
269			cbeam[i].nr = n;
270			return(i == ncbeams+xcbeams-1); /* return 1 if totally new */
271	gregl	3.1	}
272
273
274
275			int
276			docell(gcp, cap) /* find beams corresponding to cell and voxel */
277			GCOORD *gcp;
278			register struct cellact *cap;
279			{
280	gregl	3.10	register HOLO *hp = hdlist[voxel[cap->vi].hd];
281	gregl	3.1	FVECT org, dir[4];
282	gregl	3.10	FVECT vgp, cgp, vc;
283			FVECT v1, v2;
284	gregl	3.1	struct beamact bo;
285	gregl	3.10	int axmax, j;
286			double d, avmax;
287	gregl	3.1	register int i;
288	gregl	3.10	/* compute cell center */
289			cgp[gcp->w>>1] = gcp->w&1 ? hp->grid[gcp->w>>1] : 0 ;
290	gregl	3.18	cgp[hdwg0[gcp->w]] = gcp->i[0] + .5;
291			cgp[hdwg1[gcp->w]] = gcp->i[1] + .5;
292	gregl	3.10	hdworld(org, hp, cgp);
293			/* compute direction to voxel center */
294			for (i = 3; i--; )
295	gregl	3.11	vgp[i] = voxel[cap->vi].i[i] + .5;
296	gregl	3.10	hdworld(vc, hp, vgp);
297			for (i = 3; i--; )
298			vc[i] -= org[i];
299			/* compute maximum area axis */
300			axmax = -1; avmax = 0;
301			for (i = 3; i--; ) {
302			d = vgp[i] - cgp[i];
303	gregl	3.12	if (d < 0.) d = -d;
304	gregl	3.10	if (d > avmax) {
305			avmax = d;
306			axmax = i;
307	gregl	3.1	}
308			}
309	gregl	3.10	#ifdef DEBUG
310	gregl	3.12	if (axmax < 0.)
311	gregl	3.10	error(CONSISTENCY, "botched axis computation in docell");
312			#endif
313			/* compute offset vectors */
314			d = 0.5/hp->grid[j=(axmax+1)%3];
315			for (i = 3; i--; )
316			v1[i] = hp->xv[j][i] * d;
317			d = 0.5/hp->grid[j=(axmax+2)%3];
318	gregl	3.18	if (DOT(hp->wg[axmax], vc) < 0.)
319			d = -d; /* reverse vertex order */
320	gregl	3.10	for (i = 3; i--; )
321			v2[i] = hp->xv[j][i] * d;
322			/* compute voxel pyramid */
323			for (i = 3; i--; ) {
324			dir[0][i] = vc[i] - v1[i] - v2[i];
325			dir[1][i] = vc[i] + v1[i] - v2[i];
326			dir[2][i] = vc[i] + v1[i] + v2[i];
327			dir[3][i] = vc[i] - v1[i] + v2[i];
328			}
329	gregl	3.1	/* visit beams for opposite cells */
330			copystruct(&bo.ca, cap);
331			copystruct(&bo.gc, gcp);
332	gregl	3.10	return(visit_cells(org, dir, hp, dobeam, &bo));
333	gregl	3.1	}
334
335
336			int
337	gwlarson	3.21	doview(cap) /* visit cells for a given view */
338	gregl	3.1	struct cellact *cap;
339			{
340	gregl	3.5	int orient;
341	gregl	3.1	FVECT org, dir[4];
342			/* compute view pyramid */
343	gwlarson	3.21	orient = viewpyramid(org, dir, hdlist[voxel[cap->vi].hd], cap->vp);
344	gregl	3.5	if (!orient)
345			error(INTERNAL, "unusable view in doview");
346			cap->rev = orient < 0;
347	gregl	3.1	/* visit cells within pyramid */
348			return(visit_cells(org, dir, hdlist[voxel[cap->vi].hd], docell, cap));
349			}
350
351
352	gwlarson	3.21	beam_init() /* clear beam list for new view(s) */
353	gregl	3.1	{
354	gwlarson	3.21	register int i;
355			/* clear desire flags */
356			for (i = ncbeams+xcbeams; i--; )
357	gwlarson	3.22	cbeam[i].nr = 0;
358	gwlarson	3.21	voxel[0].hd = -1; /* clear voxel list */
359	gregl	3.1	}
360
361
362	gwlarson	3.21	beam_view(vn, hr, vr) /* add beam view (if advisable) */
363			VIEW *vn;
364			int hr, vr;
365	gregl	3.4	{
366	gwlarson	3.21	struct cellact ca;
367	gwlarson	3.22	unsigned int4 vfl;
368	gwlarson	3.21	/* sort our list */
369			cbeamsort(1);
370			/* add new voxels */
371			vfl = add_voxels(vn->vp);
372			if (!vfl)
373			return(0);
374			ca.vp = vn; ca.hr = hr; ca.vr = vr;
375	gwlarson	3.22	/* update our beam list */
376	gwlarson	3.21	for (ca.vi = 0; vfl; vfl >>= 1, ca.vi++)
377			if (vfl & 1)
378			doview(&ca);
379			return(1);
380	gregl	3.4	}
381
382
383	gwlarson	3.21	int
384			beam_sync(all) /* update beam list on server */
385			int all;
386	gregl	3.1	{
387			/* sort list to put orphans at end */
388			cbeamsort(0);
389	gwlarson	3.21	if (all)
390			cbeamop(DR_NEWSET, cbeam, ncbeams);
391			else
392			cbeamop(DR_ADJSET, cbeam, ncbeams+xcbeams);
393	gregl	3.1	xcbeams = 0; /* truncate our list */
394	gwlarson	3.21	return(ncbeams);
395	gregl	3.1	}