src/hd/rhdisp3.c

#ifndef lint
static const char       RCSid[] = "$Id: rhdisp3.c,v 3.17 2018/01/24 04:39:52 greg Exp $";
#endif
/*
 * Holodeck beam support for display process
 */

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

struct cellist {
        GCOORD  *cl;
        int     n;
};


int
npixels(vp, hr, vr, hp, bi)     /* compute appropriate nrays to evaluate */
VIEW    *vp;
int     hr, vr;
HOLO    *hp;
int     bi;
{
        VIEW    vrev;
        GCOORD  gc[2];
        FVECT   cp[4], ip[4], pf, pb;
        double  af, ab, sf2, sb2, dfb2, df2, db2, penalty;
        int     i;
                                        /* special case */
        if (hr <= 0 | vr <= 0)
                return(0);
                                        /* compute cell corners in image */
        if (!hdbcoord(gc, hp, bi))
                error(CONSISTENCY, "bad beam index in npixels");
        hdcell(cp, hp, gc+1);           /* find cell on front image */
        for (i = 3; i--; )              /* compute front center */
                pf[i] = 0.5*(cp[0][i] + cp[2][i]);
        sf2 = 0.25*dist2(cp[0], cp[2]); /* compute half diagonal length */
        for (i = 0; i < 4; i++) {       /* compute visible quad */
                if (viewloc(ip[i], vp, cp[i]) <= 0) {
                        af = 0;
                        goto getback;
                }
                ip[i][0] *= (double)hr; /* scale by resolution */
                ip[i][1] *= (double)vr;
        }
                                        /* compute front area */
        af = (ip[1][0]-ip[0][0])*(ip[2][1]-ip[0][1]) -
                (ip[2][0]-ip[0][0])*(ip[1][1]-ip[0][1]);
        af += (ip[2][0]-ip[3][0])*(ip[1][1]-ip[3][1]) -
                (ip[1][0]-ip[3][0])*(ip[2][1]-ip[3][1]);
        af *= af >= 0 ? 0.5 : -0.5;
getback:
        vrev = *vp;             /* compute reverse view */
        for (i = 0; i < 3; i++) {
                vrev.vdir[i] = -vp->vdir[i];
                vrev.vup[i] = -vp->vup[i];
                vrev.hvec[i] = -vp->hvec[i];
                vrev.vvec[i] = -vp->vvec[i];
        }
        hdcell(cp, hp, gc);             /* find cell on back image */
        for (i = 3; i--; )              /* compute rear center */
                pb[i] = 0.5*(cp[0][i] + cp[2][i]);
        sb2 = 0.25*dist2(cp[0], cp[2]); /* compute half diagonal length */
        for (i = 0; i < 4; i++) {       /* compute visible quad */
                if (viewloc(ip[i], &vrev, cp[i]) <= 0) {
                        ab = 0;
                        goto finish;
                }
                ip[i][0] *= (double)hr; /* scale by resolution */
                ip[i][1] *= (double)vr;
        }
                                        /* compute back area */
        ab = (ip[1][0]-ip[0][0])*(ip[2][1]-ip[0][1]) -
                (ip[2][0]-ip[0][0])*(ip[1][1]-ip[0][1]);
        ab += (ip[2][0]-ip[3][0])*(ip[1][1]-ip[3][1]) -
                (ip[1][0]-ip[3][0])*(ip[2][1]-ip[3][1]);
        ab *= ab >= 0 ? 0.5 : -0.5;
finish:         /* compute penalty based on dist. sightline - viewpoint */
        df2 = dist2(vp->vp, pf);
        db2 = dist2(vp->vp, pb);
        dfb2 = dist2(pf, pb);
        penalty = dfb2 + df2 - db2;
        penalty = df2 - 0.25*penalty*penalty/dfb2;
        if (df2 > db2)  penalty /= df2 <= dfb2 ? sb2 : sb2*df2/dfb2;
        else            penalty /= db2 <= dfb2 ? sf2 : sf2*db2/dfb2;
        if (penalty < 1.) penalty = 1.;
                                        /* round off smaller non-zero area */
        if (ab <= FTINY || (af > FTINY && af <= ab))
                return((int)(af/penalty + 0.5));
        return((int)(ab/penalty + 0.5));
}


/*
 * The ray directions that define the pyramid in visit_cells() needn't
 * be normalized, but they must be given in clockwise order as seen
 * from the pyramid's apex (origin).
 * If no cell centers fall within the domain, the closest cell is visited.
 */
int
visit_cells(orig, pyrd, hp, vf, dp)     /* visit cells within a pyramid */
FVECT   orig, pyrd[4];          /* pyramid ray directions in clockwise order */
HOLO    *hp;
int     (*vf)();
char    *dp;
{
        int     ncalls = 0, n = 0;
        int     inflags = 0;
        FVECT   gp, pn[4], lo, ld;
        double  po[4], lbeg, lend, d, t;
        GCOORD  gc, gc2[2];
        int     i;
                                        /* figure out whose side we're on */
        hdgrid(gp, hp, orig);
        for (i = 0; i < 3; i++) {
                inflags |= (gp[i] > FTINY) << (i<<1);
                inflags |= (gp[i] < hp->grid[i]-FTINY) << (i<<1 | 1);
        }
                                        /* compute pyramid planes */
        for (i = 0; i < 4; i++) {
                fcross(pn[i], pyrd[i], pyrd[(i+1)&03]);
                po[i] = DOT(pn[i], orig);
        }
                                        /* traverse each wall */
        for (gc.w = 0; gc.w < 6; gc.w++) {
                if (!(inflags & 1<<gc.w))       /* origin on wrong side */
                        continue;
                                        /* scanline algorithm */
                for (gc.i[1] = hp->grid[hdwg1[gc.w]]; gc.i[1]--; ) {
                                                /* compute scanline */
                        gp[gc.w>>1] = gc.w&1 ? hp->grid[gc.w>>1] : 0;
                        gp[hdwg0[gc.w]] = 0;
                        gp[hdwg1[gc.w]] = gc.i[1] + 0.5;
                        hdworld(lo, hp, gp);
                        gp[hdwg0[gc.w]] = 1;
                        hdworld(ld, hp, gp);
                        ld[0] -= lo[0]; ld[1] -= lo[1]; ld[2] -= lo[2];
                                                /* find scanline limits */
                        lbeg = 0; lend = hp->grid[hdwg0[gc.w]];
                        for (i = 0; i < 4; i++) {
                                t = DOT(pn[i], lo) - po[i];
                                d = -DOT(pn[i], ld);
                                if (d > FTINY) {                /* <- plane */
                                        if ((t /= d) < lend)
                                                lend = t;
                                } else if (d < -FTINY) {        /* plane -> */
                                        if ((t /= d) > lbeg)
                                                lbeg = t;
                                } else if (t < 0) {             /* outside */
                                        lend = -1;
                                        break;
                                }
                        }
                        if (lbeg >= lend)
                                continue;
                        i = lend + .5;          /* visit cells on this scan */
                        for (gc.i[0] = lbeg + .5; gc.i[0] < i; gc.i[0]++) {
                                n += (*vf)(&gc, dp);
                                ncalls++;
                        }
                }
        }
        if (ncalls)                     /* got one at least */
                return(n);
                                        /* else find closest cell */
        VSUM(ld, pyrd[0], pyrd[1], 1.);
        VSUM(ld, ld, pyrd[2], 1.);
        VSUM(ld, ld, pyrd[3], 1.);
#if 0
        if (normalize(ld) == 0.0)       /* technically not necessary */
                return(0);
#endif
        d = hdinter(gc2, NULL, &t, hp, orig, ld);
        if (d >= FHUGE || t <= 0.)
                return(0);
        return((*vf)(gc2+1, dp));       /* visit it */
}


sect_behind(hp, vp)             /* check if section is "behind" viewpoint */
HOLO    *hp;
VIEW    *vp;
{
        FVECT   hcent;
                                        /* compute holodeck section center */
        VSUM(hcent, hp->orig, hp->xv[0], 0.5);
        VSUM(hcent, hcent, hp->xv[1], 0.5);
        VSUM(hcent, hcent, hp->xv[2], 0.5);
                                        /* behind if center is behind */
        return(DOT(vp->vdir,hcent) < DOT(vp->vdir,vp->vp));
}


viewpyramid(org, dir, hp, vp)   /* compute view pyramid */
FVECT   org, dir[4];
HOLO    *hp;
VIEW    *vp;
{
        int     i;
                                        /* check view type */
        if (vp->type == VT_PAR)
                return(0);
                                        /* in front or behind? */
        if (!sect_behind(hp, vp)) {
                if (viewray(org, dir[0], vp, 0., 0.) < -FTINY)
                        return(0);
                if (viewray(org, dir[1], vp, 0., 1.) < -FTINY)
                        return(0);
                if (viewray(org, dir[2], vp, 1., 1.) < -FTINY)
                        return(0);
                if (viewray(org, dir[3], vp, 1., 0.) < -FTINY)
                        return(0);
                return(1);
        }                               /* reverse pyramid */
        if (viewray(org, dir[3], vp, 0., 0.) < -FTINY)
                return(0);
        if (viewray(org, dir[2], vp, 0., 1.) < -FTINY)
                return(0);
        if (viewray(org, dir[1], vp, 1., 1.) < -FTINY)
                return(0);
        if (viewray(org, dir[0], vp, 1., 0.) < -FTINY)
                return(0);
        for (i = 0; i < 3; i++) {
                dir[0][i] = -dir[0][i];
                dir[1][i] = -dir[1][i];
                dir[2][i] = -dir[2][i];
                dir[3][i] = -dir[3][i];
        }
        return(-1);
}


int
addcell(gcp, cl)                /* add a cell to a list */
GCOORD  *gcp;
struct cellist  *cl;
{
        *(cl->cl+cl->n) = *gcp;
        cl->n++;
        return(1);
}


int
cellcmp(gcp1, gcp2)             /* visit_cells() cell ordering */
GCOORD  *gcp1, *gcp2;
{
        int     c;

        if ((c = gcp1->w - gcp2->w))
                return(c);
        if ((c = gcp2->i[1] - gcp1->i[1]))      /* wg1 is reverse-ordered */
                return(c);
        return(gcp1->i[0] - gcp2->i[0]);
}


GCOORD *
getviewcells(np, hp, vp)        /* get ordered cell list for section view */
int     *np;            /* returned number of cells (negative if reversed) */
HOLO    *hp;
VIEW    *vp;
{
        FVECT   org, dir[4];
        int     orient;
        struct cellist  cl;
                                        /* compute view pyramid */
        *np = 0;
        orient = viewpyramid(org, dir, hp, vp);
        if (!orient)
                return(NULL);
                                        /* allocate enough list space */
        cl.n = 2*(      hp->grid[0]*hp->grid[1] +
                        hp->grid[0]*hp->grid[2] +
                        hp->grid[1]*hp->grid[2] );
        cl.cl = (GCOORD *)malloc(cl.n*sizeof(GCOORD));
        if (cl.cl == NULL)
                goto memerr;
        cl.n = 0;                       /* add cells within pyramid */
        visit_cells(org, dir, hp, addcell, (char *)&cl);
        if (!cl.n) {
                free((void *)cl.cl);
                return(NULL);
        }
        *np = cl.n * orient;
#if 0
        /* We're just going to free this memory in a moment, and list is
         * sorted automatically by visit_cells(), so we don't need this.
         */
                                        /* optimize memory use */
        cl.cl = (GCOORD *)realloc((void *)cl.cl, cl.n*sizeof(GCOORD));
        if (cl.cl == NULL)
                goto memerr;
                                        /* sort the list */
        qsort((char *)cl.cl, cl.n, sizeof(GCOORD), cellcmp);
#endif
        return(cl.cl);
memerr:
        error(SYSTEM, "out of memory in getviewcells");
}


void
gridlines(                      /* run through holodeck section grid lines */
        void    (*f)(FVECT wp[2])
)
{
        int     hd, w, i;
        int     g0, g1;
        FVECT   wp[2], mov;
        double  d;
                                        /* do each wall on each section */
        for (hd = 0; hdlist[hd] != NULL; hd++)
                for (w = 0; w < 6; w++) {
                        g0 = hdwg0[w];
                        g1 = hdwg1[w];
                        d = 1.0/hdlist[hd]->grid[g0];
                        mov[0] = d * hdlist[hd]->xv[g0][0];
                        mov[1] = d * hdlist[hd]->xv[g0][1];
                        mov[2] = d * hdlist[hd]->xv[g0][2];
                        if (w & 1) {
                                VSUM(wp[0], hdlist[hd]->orig,
                                                hdlist[hd]->xv[w>>1], 1.);
                                VSUM(wp[0], wp[0], mov, 1.);
                        } else
                                VCOPY(wp[0], hdlist[hd]->orig);
                        VSUM(wp[1], wp[0], hdlist[hd]->xv[g1], 1.);
                        for (i = hdlist[hd]->grid[g0]; ; ) {    /* g0 lines */
                                (*f)(wp);
                                if (!--i) break;
                                wp[0][0] += mov[0]; wp[0][1] += mov[1];
                                wp[0][2] += mov[2]; wp[1][0] += mov[0];
                                wp[1][1] += mov[1]; wp[1][2] += mov[2];
                        }
                        d = 1.0/hdlist[hd]->grid[g1];
                        mov[0] = d * hdlist[hd]->xv[g1][0];
                        mov[1] = d * hdlist[hd]->xv[g1][1];
                        mov[2] = d * hdlist[hd]->xv[g1][2];
                        if (w & 1)
                                VSUM(wp[0], hdlist[hd]->orig,
                                                hdlist[hd]->xv[w>>1], 1.);
                        else
                                VSUM(wp[0], hdlist[hd]->orig, mov, 1.);
                        VSUM(wp[1], wp[0], hdlist[hd]->xv[g0], 1.);
                        for (i = hdlist[hd]->grid[g1]; ; ) {    /* g1 lines */
                                (*f)(wp);
                                if (!--i) break;
                                wp[0][0] += mov[0]; wp[0][1] += mov[1];
                                wp[0][2] += mov[2]; wp[1][0] += mov[0];
                                wp[1][1] += mov[1]; wp[1][2] += mov[2];
                        }
                }
}
Revision:	3.18
Committed:	Fri Oct 5 19:19:16 2018 UTC (7 years ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R2
Changes since 3.17:	+14 -14 lines
Log Message:	Removed extraneous "extern" and "register" qualifiers
#	User	Rev	Content
1	gregl	3.1	#ifndef lint
2	greg	3.18	static const char RCSid[] = "$Id: rhdisp3.c,v 3.17 2018/01/24 04:39:52 greg Exp $";
3	gregl	3.1	#endif
4			/*
5	gregl	3.2	* Holodeck beam support for display process
6	gregl	3.1	*/
7
8			#include "rholo.h"
9			#include "rhdisp.h"
10
11	gregl	3.4	struct cellist {
12			GCOORD *cl;
13			int n;
14			};
15	gregl	3.1
16	gregl	3.4
17	gregl	3.1	int
18	gwlarson	3.10	npixels(vp, hr, vr, hp, bi) /* compute appropriate nrays to evaluate */
19	greg	3.18	VIEW *vp;
20	gregl	3.1	int hr, vr;
21			HOLO *hp;
22			int bi;
23			{
24	gregl	3.5	VIEW vrev;
25	gregl	3.1	GCOORD gc[2];
26	gwlarson	3.10	FVECT cp[4], ip[4], pf, pb;
27			double af, ab, sf2, sb2, dfb2, df2, db2, penalty;
28	greg	3.18	int i;
29	gwlarson	3.11	/* special case */
30			if (hr <= 0 \| vr <= 0)
31			return(0);
32	gregl	3.1	/* compute cell corners in image */
33			if (!hdbcoord(gc, hp, bi))
34			error(CONSISTENCY, "bad beam index in npixels");
35	gregl	3.5	hdcell(cp, hp, gc+1); /* find cell on front image */
36	gwlarson	3.10	for (i = 3; i--; ) /* compute front center */
37			pf[i] = 0.5*(cp[0][i] + cp[2][i]);
38			sf2 = 0.25dist2(cp[0], cp[2]); / compute half diagonal length */
39			for (i = 0; i < 4; i++) { /* compute visible quad */
40	greg	3.17	if (viewloc(ip[i], vp, cp[i]) <= 0) {
41	gregl	3.5	af = 0;
42			goto getback;
43	gregl	3.4	}
44	gregl	3.5	ip[i][0] = (double)hr; / scale by resolution */
45			ip[i][1] *= (double)vr;
46	gregl	3.4	}
47	gregl	3.5	/* compute front area */
48			af = (ip[1][0]-ip[0][0])*(ip[2][1]-ip[0][1]) -
49			(ip[2][0]-ip[0][0])*(ip[1][1]-ip[0][1]);
50			af += (ip[2][0]-ip[3][0])*(ip[1][1]-ip[3][1]) -
51			(ip[1][0]-ip[3][0])*(ip[2][1]-ip[3][1]);
52	gwlarson	3.10	af *= af >= 0 ? 0.5 : -0.5;
53	gregl	3.5	getback:
54	schorsch	3.14	vrev = vp; / compute reverse view */
55	gregl	3.5	for (i = 0; i < 3; i++) {
56			vrev.vdir[i] = -vp->vdir[i];
57			vrev.vup[i] = -vp->vup[i];
58			vrev.hvec[i] = -vp->hvec[i];
59			vrev.vvec[i] = -vp->vvec[i];
60			}
61			hdcell(cp, hp, gc); /* find cell on back image */
62	gwlarson	3.10	for (i = 3; i--; ) /* compute rear center */
63			pb[i] = 0.5*(cp[0][i] + cp[2][i]);
64			sb2 = 0.25dist2(cp[0], cp[2]); / compute half diagonal length */
65			for (i = 0; i < 4; i++) { /* compute visible quad */
66	greg	3.17	if (viewloc(ip[i], &vrev, cp[i]) <= 0) {
67	gwlarson	3.10	ab = 0;
68			goto finish;
69			}
70	gregl	3.1	ip[i][0] = (double)hr; / scale by resolution */
71			ip[i][1] *= (double)vr;
72			}
73	gregl	3.5	/* compute back area */
74			ab = (ip[1][0]-ip[0][0])*(ip[2][1]-ip[0][1]) -
75	gregl	3.1	(ip[2][0]-ip[0][0])*(ip[1][1]-ip[0][1]);
76	gregl	3.5	ab += (ip[2][0]-ip[3][0])*(ip[1][1]-ip[3][1]) -
77	gregl	3.1	(ip[1][0]-ip[3][0])*(ip[2][1]-ip[3][1]);
78	gwlarson	3.10	ab *= ab >= 0 ? 0.5 : -0.5;
79			finish: /* compute penalty based on dist. sightline - viewpoint */
80			df2 = dist2(vp->vp, pf);
81			db2 = dist2(vp->vp, pb);
82			dfb2 = dist2(pf, pb);
83			penalty = dfb2 + df2 - db2;
84			penalty = df2 - 0.25penaltypenalty/dfb2;
85			if (df2 > db2) penalty /= df2 <= dfb2 ? sb2 : sb2*df2/dfb2;
86			else penalty /= db2 <= dfb2 ? sf2 : sf2*db2/dfb2;
87			if (penalty < 1.) penalty = 1.;
88			/* round off smaller non-zero area */
89			if (ab <= FTINY \|\| (af > FTINY && af <= ab))
90			return((int)(af/penalty + 0.5));
91			return((int)(ab/penalty + 0.5));
92	gregl	3.1	}
93
94
95			/*
96			* The ray directions that define the pyramid in visit_cells() needn't
97			* be normalized, but they must be given in clockwise order as seen
98			* from the pyramid's apex (origin).
99	gregl	3.8	* If no cell centers fall within the domain, the closest cell is visited.
100	gregl	3.1	*/
101			int
102			visit_cells(orig, pyrd, hp, vf, dp) /* visit cells within a pyramid */
103			FVECT orig, pyrd[4]; /* pyramid ray directions in clockwise order */
104	greg	3.18	HOLO *hp;
105	gregl	3.1	int (*vf)();
106			char *dp;
107			{
108	gregl	3.8	int ncalls = 0, n = 0;
109	gregl	3.1	int inflags = 0;
110			FVECT gp, pn[4], lo, ld;
111			double po[4], lbeg, lend, d, t;
112	gregl	3.8	GCOORD gc, gc2[2];
113	greg	3.18	int i;
114	gregl	3.1	/* figure out whose side we're on */
115			hdgrid(gp, hp, orig);
116			for (i = 0; i < 3; i++) {
117			inflags \|= (gp[i] > FTINY) << (i<<1);
118			inflags \|= (gp[i] < hp->grid[i]-FTINY) << (i<<1 \| 1);
119			}
120			/* compute pyramid planes */
121			for (i = 0; i < 4; i++) {
122			fcross(pn[i], pyrd[i], pyrd[(i+1)&03]);
123			po[i] = DOT(pn[i], orig);
124			}
125			/* traverse each wall */
126			for (gc.w = 0; gc.w < 6; gc.w++) {
127			if (!(inflags & 1<<gc.w)) /* origin on wrong side */
128			continue;
129			/* scanline algorithm */
130	gregl	3.9	for (gc.i[1] = hp->grid[hdwg1[gc.w]]; gc.i[1]--; ) {
131	gregl	3.1	/* compute scanline */
132			gp[gc.w>>1] = gc.w&1 ? hp->grid[gc.w>>1] : 0;
133	gregl	3.9	gp[hdwg0[gc.w]] = 0;
134			gp[hdwg1[gc.w]] = gc.i[1] + 0.5;
135	gregl	3.1	hdworld(lo, hp, gp);
136	gregl	3.9	gp[hdwg0[gc.w]] = 1;
137	gregl	3.1	hdworld(ld, hp, gp);
138	gregl	3.2	ld[0] -= lo[0]; ld[1] -= lo[1]; ld[2] -= lo[2];
139	gregl	3.1	/* find scanline limits */
140	gregl	3.9	lbeg = 0; lend = hp->grid[hdwg0[gc.w]];
141	gregl	3.1	for (i = 0; i < 4; i++) {
142			t = DOT(pn[i], lo) - po[i];
143			d = -DOT(pn[i], ld);
144	gregl	3.2	if (d > FTINY) { /* <- plane */
145	gregl	3.1	if ((t /= d) < lend)
146			lend = t;
147	gregl	3.2	} else if (d < -FTINY) { /* plane -> */
148	gregl	3.1	if ((t /= d) > lbeg)
149			lbeg = t;
150	gregl	3.3	} else if (t < 0) { /* outside */
151			lend = -1;
152			break;
153			}
154	gregl	3.1	}
155	gregl	3.3	if (lbeg >= lend)
156			continue;
157	gregl	3.1	i = lend + .5; /* visit cells on this scan */
158	gregl	3.8	for (gc.i[0] = lbeg + .5; gc.i[0] < i; gc.i[0]++) {
159	gregl	3.1	n += (*vf)(&gc, dp);
160	gregl	3.8	ncalls++;
161			}
162	gregl	3.1	}
163			}
164	gregl	3.8	if (ncalls) /* got one at least */
165			return(n);
166			/* else find closest cell */
167			VSUM(ld, pyrd[0], pyrd[1], 1.);
168			VSUM(ld, ld, pyrd[2], 1.);
169			VSUM(ld, ld, pyrd[3], 1.);
170			#if 0
171			if (normalize(ld) == 0.0) /* technically not necessary */
172			return(0);
173			#endif
174			d = hdinter(gc2, NULL, &t, hp, orig, ld);
175			if (d >= FHUGE \|\| t <= 0.)
176			return(0);
177			return((vf)(gc2+1, dp)); / visit it */
178	gregl	3.1	}
179
180
181	gregl	3.4	sect_behind(hp, vp) /* check if section is "behind" viewpoint */
182	greg	3.18	HOLO *hp;
183			VIEW *vp;
184	gregl	3.4	{
185			FVECT hcent;
186			/* compute holodeck section center */
187			VSUM(hcent, hp->orig, hp->xv[0], 0.5);
188			VSUM(hcent, hcent, hp->xv[1], 0.5);
189			VSUM(hcent, hcent, hp->xv[2], 0.5);
190			/* behind if center is behind */
191			return(DOT(vp->vdir,hcent) < DOT(vp->vdir,vp->vp));
192			}
193
194
195			viewpyramid(org, dir, hp, vp) /* compute view pyramid */
196			FVECT org, dir[4];
197			HOLO *hp;
198			VIEW *vp;
199			{
200	greg	3.18	int i;
201	gregl	3.4	/* check view type */
202			if (vp->type == VT_PAR)
203			return(0);
204			/* in front or behind? */
205			if (!sect_behind(hp, vp)) {
206			if (viewray(org, dir[0], vp, 0., 0.) < -FTINY)
207			return(0);
208			if (viewray(org, dir[1], vp, 0., 1.) < -FTINY)
209			return(0);
210			if (viewray(org, dir[2], vp, 1., 1.) < -FTINY)
211			return(0);
212			if (viewray(org, dir[3], vp, 1., 0.) < -FTINY)
213			return(0);
214			return(1);
215			} /* reverse pyramid */
216			if (viewray(org, dir[3], vp, 0., 0.) < -FTINY)
217			return(0);
218			if (viewray(org, dir[2], vp, 0., 1.) < -FTINY)
219			return(0);
220			if (viewray(org, dir[1], vp, 1., 1.) < -FTINY)
221			return(0);
222			if (viewray(org, dir[0], vp, 1., 0.) < -FTINY)
223			return(0);
224			for (i = 0; i < 3; i++) {
225			dir[0][i] = -dir[0][i];
226			dir[1][i] = -dir[1][i];
227			dir[2][i] = -dir[2][i];
228			dir[3][i] = -dir[3][i];
229			}
230			return(-1);
231			}
232
233
234	gregl	3.1	int
235			addcell(gcp, cl) /* add a cell to a list */
236			GCOORD *gcp;
237	greg	3.18	struct cellist *cl;
238	gregl	3.1	{
239	schorsch	3.14	(cl->cl+cl->n) = gcp;
240	gregl	3.4	cl->n++;
241	gregl	3.1	return(1);
242			}
243
244
245			int
246			cellcmp(gcp1, gcp2) /* visit_cells() cell ordering */
247	greg	3.18	GCOORD gcp1, gcp2;
248	gregl	3.1	{
249	greg	3.18	int c;
250	gregl	3.1
251			if ((c = gcp1->w - gcp2->w))
252			return(c);
253			if ((c = gcp2->i[1] - gcp1->i[1])) /* wg1 is reverse-ordered */
254			return(c);
255			return(gcp1->i[0] - gcp2->i[0]);
256			}
257
258
259	gregl	3.4	GCOORD *
260			getviewcells(np, hp, vp) /* get ordered cell list for section view */
261			int np; / returned number of cells (negative if reversed) */
262	greg	3.18	HOLO *hp;
263	gregl	3.1	VIEW *vp;
264			{
265			FVECT org, dir[4];
266	gregl	3.4	int orient;
267			struct cellist cl;
268	gregl	3.1	/* compute view pyramid */
269	gregl	3.4	*np = 0;
270			orient = viewpyramid(org, dir, hp, vp);
271			if (!orient)
272			return(NULL);
273	gregl	3.1	/* allocate enough list space */
274	gregl	3.4	cl.n = 2( hp->grid[0]hp->grid[1] +
275			hp->grid[0]*hp->grid[2] +
276			hp->grid[1]*hp->grid[2] );
277			cl.cl = (GCOORD )malloc(cl.nsizeof(GCOORD));
278			if (cl.cl == NULL)
279	gregl	3.1	goto memerr;
280	gregl	3.4	cl.n = 0; /* add cells within pyramid */
281	gwlarson	3.11	visit_cells(org, dir, hp, addcell, (char *)&cl);
282	gregl	3.4	if (!cl.n) {
283	greg	3.12	free((void *)cl.cl);
284	gregl	3.1	return(NULL);
285			}
286	gregl	3.4	np = cl.n orient;
287	gregl	3.1	#if 0
288	gregl	3.2	/* We're just going to free this memory in a moment, and list is
289			* sorted automatically by visit_cells(), so we don't need this.
290			*/
291	gregl	3.4	/* optimize memory use */
292	greg	3.13	cl.cl = (GCOORD )realloc((void )cl.cl, cl.n*sizeof(GCOORD));
293	gregl	3.4	if (cl.cl == NULL)
294			goto memerr;
295	gregl	3.1	/* sort the list */
296	gregl	3.4	qsort((char *)cl.cl, cl.n, sizeof(GCOORD), cellcmp);
297	gregl	3.1	#endif
298	gregl	3.4	return(cl.cl);
299	gregl	3.1	memerr:
300			error(SYSTEM, "out of memory in getviewcells");
301			}
302	gregl	3.6
303
304	greg	3.18	void
305	schorsch	3.15	gridlines( /* run through holodeck section grid lines */
306			void (*f)(FVECT wp[2])
307			)
308	gregl	3.6	{
309	greg	3.18	int hd, w, i;
310	gregl	3.6	int g0, g1;
311	gregl	3.7	FVECT wp[2], mov;
312	gregl	3.6	double d;
313			/* do each wall on each section */
314			for (hd = 0; hdlist[hd] != NULL; hd++)
315			for (w = 0; w < 6; w++) {
316	gregl	3.9	g0 = hdwg0[w];
317			g1 = hdwg1[w];
318	gregl	3.7	d = 1.0/hdlist[hd]->grid[g0];
319			mov[0] = d * hdlist[hd]->xv[g0][0];
320			mov[1] = d * hdlist[hd]->xv[g0][1];
321			mov[2] = d * hdlist[hd]->xv[g0][2];
322			if (w & 1) {
323	gregl	3.6	VSUM(wp[0], hdlist[hd]->orig,
324			hdlist[hd]->xv[w>>1], 1.);
325	gregl	3.7	VSUM(wp[0], wp[0], mov, 1.);
326			} else
327			VCOPY(wp[0], hdlist[hd]->orig);
328			VSUM(wp[1], wp[0], hdlist[hd]->xv[g1], 1.);
329			for (i = hdlist[hd]->grid[g0]; ; ) { /* g0 lines */
330	gregl	3.6	(*f)(wp);
331	gregl	3.7	if (!--i) break;
332			wp[0][0] += mov[0]; wp[0][1] += mov[1];
333			wp[0][2] += mov[2]; wp[1][0] += mov[0];
334			wp[1][1] += mov[1]; wp[1][2] += mov[2];
335	gregl	3.6	}
336	gregl	3.7	d = 1.0/hdlist[hd]->grid[g1];
337			mov[0] = d * hdlist[hd]->xv[g1][0];
338			mov[1] = d * hdlist[hd]->xv[g1][1];
339			mov[2] = d * hdlist[hd]->xv[g1][2];
340			if (w & 1)
341	gregl	3.6	VSUM(wp[0], hdlist[hd]->orig,
342			hdlist[hd]->xv[w>>1], 1.);
343	gregl	3.7	else
344			VSUM(wp[0], hdlist[hd]->orig, mov, 1.);
345			VSUM(wp[1], wp[0], hdlist[hd]->xv[g0], 1.);
346			for (i = hdlist[hd]->grid[g1]; ; ) { /* g1 lines */
347	gregl	3.6	(*f)(wp);
348	gregl	3.7	if (!--i) break;
349			wp[0][0] += mov[0]; wp[0][1] += mov[1];
350			wp[0][2] += mov[2]; wp[1][0] += mov[0];
351			wp[1][1] += mov[1]; wp[1][2] += mov[2];
352	gregl	3.6	}
353			}
354			}