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

#define MAXTODO         3       /* maximum sections to look at */
#define MAXDRAT         3.0     /* maximum distance ratio */

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

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


beam_view(vn, hr, vr)           /* add beam view (if advisable) */
VIEW    *vn;
int     hr, vr;
{
        int     todo[MAXTODO+1];
        int     n;
                                        /* sort our list */
        cbeamsort(1);
                                        /* add view to nearby sections */
        if (!(n = comptodo(todo, vn)))
                return(0);
        while (n--)
                addview(todo[n], vn, hr, vr);
        return(1);
}


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