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"
#include "random.h"

#ifndef MAXDIST
#define MAXDIST         42      /* maximum distance outside section */
#endif
#ifndef NVSAMPS
#define NVSAMPS         4096    /* number of ray samples per view */
#endif
#ifndef MEYERNG
#define MEYERNG         0.2     /* target mean eye range (rel. to grid) */
#endif
#ifndef MAXTODO
#define MAXTODO         3       /* maximum sections to look at */
#endif
#ifndef MAXDRAT
#define MAXDRAT         3.0     /* maximum distance ratio btwn. cand. sect. */
#endif

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

static struct beamcomp {
        int     hd;             /* holodeck section number */
        int     bi;             /* beam index */
        int4    nr;             /* number of samples desired */
} *cbeam = NULL;        /* current beam list */

VIEWPOINT       cureye;         /* current eye position */

static int      ncbeams = 0;    /* number of sorted beams in cbeam */
static int      xcbeams = 0;    /* extra (unregistered) beams past ncbeams */
static int      maxcbeam = 0;   /* size of cbeam array */


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);
}


int
comptodo(tdl, vw)               /* compute holodeck sections in view */
int     tdl[MAXTODO+1];
VIEW    *vw;
{
        int     n = 0;
        FVECT   gp, dv;
        double  dist2[MAXTODO+1], thisdist2;
        register int    i, j;
                                        /* find closest MAXTODO sections */
        for (i = 0; hdlist[i]; i++) {
                hdgrid(gp, hdlist[i], vw->vp);
                for (j = 0; j < 3; j++)
                        if (gp[j] < 0.)
                                dv[j] = -gp[j];
                        else if (gp[j] > hdlist[i]->grid[j])
                                dv[j] = gp[j] - hdlist[i]->grid[j];
                        else
                                dv[j] = 0.;
                thisdist2 = DOT(dv,dv);
                for (j = n; j > 0 && thisdist2 < dist2[j-1]; j--) {
                        tdl[j] = tdl[j-1];
                        dist2[j] = dist2[j-1];
                }
                tdl[j] = i;
                dist2[j] = thisdist2;
                if (n < MAXTODO)
                        n++;
        }
                                        /* watch for bad move */
        if (n && dist2[0] > MAXDIST*MAXDIST) {
                error(COMMAND, "move past outer limits");
                return(0);
        }
                                        /* avoid big differences */
        for (j = 1; j < n; j++)
                if (dist2[j] > MAXDRAT*MAXDRAT*dist2[j-1])
                        n = j;
        tdl[n] = -1;
        return(n);
}


addview(hd, vw, hres, vres)     /* add view for section */
int     hd;
VIEW    *vw;
int     hres, vres;
{
        int     sampquant;
        int     h, v, shr, svr;
        GCOORD  gc[2];
        FVECT   rorg, rdir;
                                /* compute sampling grid */
        if (hres|vres && hres*vres <= NVSAMPS) {
                shr = hres; svr = vres;
                sampquant = 1;
        } else {
                shr = sqrt(NVSAMPS/viewaspect(vw)) + .5;
                svr = (NVSAMPS + shr/2)/shr;
                sampquant = (hres*vres + shr*svr/2)/(shr*svr);
        }
                                /* intersect sample rays with section */
        for (v = svr; v--; )
                for (h = shr; h--; ) {
                        if (viewray(rorg, rdir, vw, (v+frandom())/svr,
                                                (h+frandom())/shr) < -FTINY)
                                continue;
                        if (hdinter(gc, NULL, NULL, hdlist[hd], rorg, rdir)
                                                >= FHUGE)
                                continue;
                        cbeam[getcbeam(hd,hdbindex(hdlist[hd],gc))].nr +=
                                        sampquant;
                }
}


beam_init(fresh)                /* clear beam list for new view(s) */
int     fresh;
{
        register int    i;

        if (fresh)                      /* discard old beams? */
                ncbeams = xcbeams = 0;
        else                            /* else clear sample requests */
                for (i = ncbeams+xcbeams; i--; )
                        cbeam[i].nr = 0;
        cureye.rng = 0.;
}


beam_view(vn, hr, vr)           /* add beam view (if advisable) */
VIEW    *vn;
int     hr, vr;
{
        int     todo[MAXTODO+1], n;
        double  hdgsiz, d;
        register HOLO   *hp;
        register int    i;
                                        /* sort our list */
        cbeamsort(1);
                                        /* add view to nearby sections */
        if (!(n = comptodo(todo, vn)))
                return(0);
        for (i = 0; i < n; i++)
                addview(todo[i], vn, hr, vr);
        if (MEYERNG <= FTINY || vn->type == VT_PAR)
                return(1);
        hdgsiz = 0.;                    /* compute mean grid size */
        for (i = 0; i < n; i++) {
                hp = hdlist[todo[i]];
                hdgsiz +=       1./3. / VLEN(hp->wg[0]) +
                                1./3. / VLEN(hp->wg[1]) +
                                1./3. / VLEN(hp->wg[2]) ;
        }
        hdgsiz /= (double)n;
                                        /* add to current eye position */
        if (cureye.rng <= FTINY) {
                VCOPY(cureye.vpt, vn->vp);
                cureye.rng = MEYERNG * hdgsiz;
        } else if ((d = sqrt(dist2(vn->vp,cureye.vpt))) + MEYERNG*hdgsiz >
                        cureye.rng) {
                for (i = 3; i--; )
                        cureye.vpt[i] = 0.5*(cureye.vpt[i] + vn->vp[i]);
                cureye.rng = 0.5*(cureye.rng + MEYERNG*hdgsiz + d);
        }
        return(1);
}


int
beam_sync(all)                  /* update beam list on server */
int     all;
{
                                        /* set new eye position */
        serv_request(DR_VIEWPOINT, sizeof(VIEWPOINT), (char *)&cureye);
                                        /* sort list (put orphans at end) */
        cbeamsort(all < 0);
                                        /* send beam request */
        if (all)
                cbeamop(DR_NEWSET, cbeam, ncbeams);
        else
                cbeamop(DR_ADJSET, cbeam, ncbeams+xcbeams);
        xcbeams = 0;                    /* truncate our list */
        return(ncbeams);
}
Revision:	3.27
Committed:	Thu Dec 3 15:18:08 1998 UTC (26 years, 10 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.26:	+5 -4 lines
Log Message:	minor efficiency hack
#	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	gwlarson	3.25	#include "random.h"
15	gregl	3.1
16	gregl	3.9	#ifndef MAXDIST
17	gregl	3.14	#define MAXDIST 42 /* maximum distance outside section */
18	gregl	3.9	#endif
19	gwlarson	3.25	#ifndef NVSAMPS
20			#define NVSAMPS 4096 /* number of ray samples per view */
21			#endif
22	gwlarson	3.26	#ifndef MEYERNG
23			#define MEYERNG 0.2 /* target mean eye range (rel. to grid) */
24			#endif
25			#ifndef MAXTODO
26	gwlarson	3.25	#define MAXTODO 3 /* maximum sections to look at */
27	gwlarson	3.26	#endif
28			#ifndef MAXDRAT
29			#define MAXDRAT 3.0 /* maximum distance ratio btwn. cand. sect. */
30			#endif
31	gwlarson	3.20
32	gregl	3.1	#define CBEAMBLK 1024 /* cbeam allocation block size */
33
34			static struct beamcomp {
35	gwlarson	3.22	int hd; /* holodeck section number */
36	gwlarson	3.24	int bi; /* beam index */
37	gwlarson	3.21	int4 nr; /* number of samples desired */
38	gregl	3.1	} cbeam = NULL; / current beam list */
39
40	gwlarson	3.26	VIEWPOINT cureye; /* current eye position */
41
42	gregl	3.1	static int ncbeams = 0; /* number of sorted beams in cbeam */
43			static int xcbeams = 0; /* extra (unregistered) beams past ncbeams */
44			static int maxcbeam = 0; /* size of cbeam array */
45
46
47			int
48			newcbeam() /* allocate new entry at end of cbeam array */
49			{
50			int i;
51
52			if ((i = ncbeams + xcbeams++) >= maxcbeam) { /* grow array */
53			maxcbeam += CBEAMBLK;
54			if (cbeam == NULL)
55			cbeam = (struct beamcomp *)malloc(
56			maxcbeam*sizeof(struct beamcomp) );
57			else
58			cbeam = (struct beamcomp )realloc( (char )cbeam,
59			maxcbeam*sizeof(struct beamcomp) );
60			if (cbeam == NULL)
61			error(SYSTEM, "out of memory in newcbeam");
62			}
63			return(i);
64			}
65
66
67			int
68			cbeamcmp(cb1, cb2) /* compare two cbeam entries for sort: keep orphans */
69			register struct beamcomp cb1, cb2;
70			{
71			register int c;
72
73			if ((c = cb1->bi - cb2->bi)) /* sort on beam index first */
74			return(c);
75			return(cb1->hd - cb2->hd); /* use hd to resolve matches */
76			}
77
78
79			int
80			cbeamcmp2(cb1, cb2) /* compare two cbeam entries for sort: no orphans */
81			register struct beamcomp cb1, cb2;
82			{
83			register int c;
84
85	gwlarson	3.22	if (!cb1->nr) /* put orphans at the end, unsorted */
86			return(cb2->nr);
87			if (!cb2->nr)
88	gregl	3.15	return(-1);
89	gregl	3.1	if ((c = cb1->bi - cb2->bi)) /* sort on beam index first */
90			return(c);
91			return(cb1->hd - cb2->hd); /* use hd to resolve matches */
92			}
93
94
95			int
96			findcbeam(hd, bi) /* find the specified beam in our sorted list */
97			int hd, bi;
98			{
99			struct beamcomp cb;
100			register struct beamcomp *p;
101
102			if (ncbeams <= 0)
103			return(-1);
104	gwlarson	3.22	cb.hd = hd; cb.bi = bi; cb.nr = 0;
105	gregl	3.1	p = (struct beamcomp )bsearch((char )&cb, (char *)cbeam, ncbeams,
106			sizeof(struct beamcomp), cbeamcmp);
107			if (p == NULL)
108			return(-1);
109			return(p - cbeam);
110			}
111
112
113			int
114			getcbeam(hd, bi) /* get the specified beam, allocating as necessary */
115			register int hd;
116			int bi;
117			{
118			register int n;
119			/* first, look in sorted list */
120			if ((n = findcbeam(hd, bi)) >= 0)
121			return(n);
122			/* linear search through xcbeams to be sure */
123			for (n = ncbeams+xcbeams; n-- > ncbeams; )
124			if (cbeam[n].bi == bi && cbeam[n].hd == hd)
125			return(n);
126			/* check legality */
127			if (hd < 0 \| hd >= HDMAX \|\| hdlist[hd] == NULL)
128			error(INTERNAL, "illegal holodeck number in getcbeam");
129			if (bi < 1 \| bi > nbeams(hdlist[hd]))
130			error(INTERNAL, "illegal beam index in getcbeam");
131			n = newcbeam(); /* allocate and assign */
132	gwlarson	3.22	cbeam[n].nr = 0; cbeam[n].hd = hd; cbeam[n].bi = bi;
133	gregl	3.1	return(n);
134			}
135
136
137			cbeamsort(adopt) /* sort our beam list, possibly turning out orphans */
138			int adopt;
139			{
140			register int i;
141
142			if (!(ncbeams += xcbeams))
143			return;
144			xcbeams = 0;
145			qsort((char *)cbeam, ncbeams, sizeof(struct beamcomp),
146			adopt ? cbeamcmp : cbeamcmp2);
147			if (adopt)
148			return;
149			for (i = ncbeams; i--; ) /* identify orphans */
150	gwlarson	3.22	if (cbeam[i].nr)
151	gregl	3.1	break;
152			xcbeams = ncbeams - ++i; /* put orphans after ncbeams */
153			ncbeams = i;
154			}
155
156
157	gwlarson	3.21	cbeamop(op, bl, n) /* update beams on server list */
158	gregl	3.4	int op;
159	gregl	3.1	register struct beamcomp *bl;
160			int n;
161			{
162			register PACKHEAD *pa;
163			register int i;
164
165			if (n <= 0)
166			return;
167			pa = (PACKHEAD )malloc(nsizeof(PACKHEAD));
168			if (pa == NULL)
169	gwlarson	3.21	error(SYSTEM, "out of memory in cbeamop");
170	gregl	3.1	for (i = 0; i < n; i++) {
171			pa[i].hd = bl[i].hd;
172			pa[i].bi = bl[i].bi;
173	gwlarson	3.21	pa[i].nr = bl[i].nr;
174	gregl	3.16	pa[i].nc = 0;
175	gregl	3.1	}
176	gregl	3.4	serv_request(op, nsizeof(PACKHEAD), (char )pa);
177	gregl	3.1	free((char *)pa);
178			}
179
180
181	gwlarson	3.25	int
182			comptodo(tdl, vw) /* compute holodeck sections in view */
183			int tdl[MAXTODO+1];
184			VIEW *vw;
185	gregl	3.1	{
186	gwlarson	3.25	int n = 0;
187			FVECT gp, dv;
188			double dist2[MAXTODO+1], thisdist2;
189			register int i, j;
190			/* find closest MAXTODO sections */
191			for (i = 0; hdlist[i]; i++) {
192			hdgrid(gp, hdlist[i], vw->vp);
193			for (j = 0; j < 3; j++)
194			if (gp[j] < 0.)
195			dv[j] = -gp[j];
196			else if (gp[j] > hdlist[i]->grid[j])
197			dv[j] = gp[j] - hdlist[i]->grid[j];
198			else
199			dv[j] = 0.;
200			thisdist2 = DOT(dv,dv);
201			for (j = n; j > 0 && thisdist2 < dist2[j-1]; j--) {
202			tdl[j] = tdl[j-1];
203			dist2[j] = dist2[j-1];
204	gregl	3.1	}
205	gwlarson	3.25	tdl[j] = i;
206			dist2[j] = thisdist2;
207			if (n < MAXTODO)
208			n++;
209	gregl	3.1	}
210	gwlarson	3.25	/* watch for bad move */
211			if (n && dist2[0] > MAXDIST*MAXDIST) {
212	gregl	3.10	error(COMMAND, "move past outer limits");
213	gregl	3.9	return(0);
214			}
215	gwlarson	3.25	/* avoid big differences */
216			for (j = 1; j < n; j++)
217			if (dist2[j] > MAXDRATMAXDRATdist2[j-1])
218			n = j;
219			tdl[n] = -1;
220			return(n);
221	gregl	3.1	}
222
223
224	gwlarson	3.25	addview(hd, vw, hres, vres) /* add view for section */
225			int hd;
226			VIEW *vw;
227			int hres, vres;
228	gregl	3.1	{
229	gwlarson	3.25	int sampquant;
230			int h, v, shr, svr;
231	gregl	3.1	GCOORD gc[2];
232	gwlarson	3.25	FVECT rorg, rdir;
233			/* compute sampling grid */
234			if (hres\|vres && hres*vres <= NVSAMPS) {
235			shr = hres; svr = vres;
236			sampquant = 1;
237	gregl	3.5	} else {
238	gwlarson	3.25	shr = sqrt(NVSAMPS/viewaspect(vw)) + .5;
239			svr = (NVSAMPS + shr/2)/shr;
240			sampquant = (hresvres + shrsvr/2)/(shr*svr);
241	gregl	3.5	}
242	gwlarson	3.25	/* intersect sample rays with section */
243			for (v = svr; v--; )
244			for (h = shr; h--; ) {
245			if (viewray(rorg, rdir, vw, (v+frandom())/svr,
246			(h+frandom())/shr) < -FTINY)
247			continue;
248			if (hdinter(gc, NULL, NULL, hdlist[hd], rorg, rdir)
249			>= FHUGE)
250			continue;
251			cbeam[getcbeam(hd,hdbindex(hdlist[hd],gc))].nr +=
252			sampquant;
253	gregl	3.1	}
254			}
255
256
257	gwlarson	3.24	beam_init(fresh) /* clear beam list for new view(s) */
258			int fresh;
259	gregl	3.1	{
260	gwlarson	3.21	register int i;
261	gwlarson	3.24
262			if (fresh) /* discard old beams? */
263			ncbeams = xcbeams = 0;
264			else /* else clear sample requests */
265			for (i = ncbeams+xcbeams; i--; )
266			cbeam[i].nr = 0;
267	gwlarson	3.26	cureye.rng = 0.;
268	gregl	3.1	}
269
270
271	gwlarson	3.21	beam_view(vn, hr, vr) /* add beam view (if advisable) */
272			VIEW *vn;
273			int hr, vr;
274	gregl	3.4	{
275	gwlarson	3.26	int todo[MAXTODO+1], n;
276			double hdgsiz, d;
277			register HOLO *hp;
278			register int i;
279	gwlarson	3.21	/* sort our list */
280			cbeamsort(1);
281	gwlarson	3.25	/* add view to nearby sections */
282			if (!(n = comptodo(todo, vn)))
283	gwlarson	3.21	return(0);
284	gwlarson	3.26	for (i = 0; i < n; i++)
285			addview(todo[i], vn, hr, vr);
286			if (MEYERNG <= FTINY \|\| vn->type == VT_PAR)
287			return(1);
288	gwlarson	3.27	hdgsiz = 0.; /* compute mean grid size */
289	gwlarson	3.26	for (i = 0; i < n; i++) {
290			hp = hdlist[todo[i]];
291	gwlarson	3.27	hdgsiz += 1./3. / VLEN(hp->wg[0]) +
292			1./3. / VLEN(hp->wg[1]) +
293			1./3. / VLEN(hp->wg[2]) ;
294	gwlarson	3.26	}
295	gwlarson	3.27	hdgsiz /= (double)n;
296	gwlarson	3.26	/* add to current eye position */
297			if (cureye.rng <= FTINY) {
298			VCOPY(cureye.vpt, vn->vp);
299			cureye.rng = MEYERNG * hdgsiz;
300			} else if ((d = sqrt(dist2(vn->vp,cureye.vpt))) + MEYERNG*hdgsiz >
301			cureye.rng) {
302			for (i = 3; i--; )
303			cureye.vpt[i] = 0.5*(cureye.vpt[i] + vn->vp[i]);
304			cureye.rng = 0.5(cureye.rng + MEYERNGhdgsiz + d);
305			}
306	gwlarson	3.21	return(1);
307	gregl	3.4	}
308
309
310	gwlarson	3.21	int
311			beam_sync(all) /* update beam list on server */
312			int all;
313	gregl	3.1	{
314	gwlarson	3.26	/* set new eye position */
315			serv_request(DR_VIEWPOINT, sizeof(VIEWPOINT), (char *)&cureye);
316	gwlarson	3.24	/* sort list (put orphans at end) */
317			cbeamsort(all < 0);
318	gwlarson	3.26	/* send beam request */
319	gwlarson	3.21	if (all)
320			cbeamop(DR_NEWSET, cbeam, ncbeams);
321			else
322			cbeamop(DR_ADJSET, cbeam, ncbeams+xcbeams);
323	gregl	3.1	xcbeams = 0; /* truncate our list */
324	gwlarson	3.21	return(ncbeams);
325	gregl	3.1	}