src/hd/clumpbeams.c

/* Copyright (c) 1998 Silicon Graphics, Inc. */

#ifndef lint
static char SCCSid[] = "$SunId$ SGI";
#endif

/*
 * Bundle holodeck beams together into clumps.
 */

#include "holo.h"

#define flgop(p,i,op)           ((p)[(i)>>5] op (1L<<((i)&0x1f)))
#define isset(p,i)              flgop(p,i,&)
#define setfl(p,i)              flgop(p,i,|=)
#define clrfl(p,i)              flgop(p,i,&=~)

static int      bneighlist[9*9-1];
static int      bneighrem;

#define nextneigh()     (bneighrem<=0 ? 0 : bneighlist[--bneighrem])

static BEAMI    *beamdir;


gcshifti(gc, ia, di, hp)        /* shift cell row or column */
register GCOORD *gc;
int     ia, di;
register HOLO   *hp;
{
        int     nw;

        if (di > 0) {
                if (++gc->i[ia] >= hp->grid[((gc->w>>1)+1+ia)%3]) {
                        nw = ((gc->w&~1) + (ia<<1) + 3) % 6;
                        gc->i[ia] = gc->i[1-ia];
                        gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
                        gc->w = nw;
                }
        } else if (di < 0) {
                if (--gc->i[ia] < 0) {
                        nw = ((gc->w&~1) + (ia<<1) + 2) % 6;
                        gc->i[ia] = gc->i[1-ia];
                        gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
                        gc->w = nw;
                }
        }
}


mkneighgrid(ng, hp, gc)         /* compute neighborhood for grid cell */
GCOORD  ng[3*3];
HOLO    *hp;
GCOORD  *gc;
{
        GCOORD  gci0;
        register int    i, j;

        for (i = 3; i--; ) {
                copystruct(&gci0, gc);
                gcshifti(&gci0, 0, i-1, hp);
                for (j = 3; j--; ) {
                        copystruct(ng+(3*i+j), &gci0);
                        gcshifti(ng+(3*i+j), gci0.w==gc->w, j-1, hp);
                }
        }
}


static int
firstneigh(hp, b)               /* initialize neighbor list and return first */
HOLO    *hp;
int     b;
{
        GCOORD  wg0[9], wg1[9], bgc[2];
        int     i, j;

        hdbcoord(bgc, hp, b);
        mkneighgrid(wg0, hp, bgc);
        mkneighgrid(wg1, hp, bgc+1);
        bneighrem = 0;
        for (i = 9; i--; )
                for (j = 9; j--; ) {
                        if (i == 4 & j == 4)    /* don't copy starting beam */
                                continue;
                        if (wg0[i].w == wg1[j].w)
                                continue;
                        copystruct(bgc, wg0+i);
                        copystruct(bgc+1, wg1+j);
                        bneighlist[bneighrem++] = hdbindex(hp, bgc);
#ifdef DEBUG
                        if (bneighlist[bneighrem-1] <= 0)
                                error(CONSISTENCY, "bad beam in firstneigh");
#endif
                }
        return(nextneigh());
}


static int
bpcmp(b1p, b2p)                 /* compare beam positions on disk */
int     *b1p, *b2p;
{
        register long   pdif = beamdir[*b1p].fo - beamdir[*b2p].fo;

        if (pdif > 0L) return(1);
        if (pdif < 0L) return(-1);
        return(0);
}


clumpbeams(hp, maxcnt, maxsiz, bf)      /* clump beams from hinp */
register HOLO   *hp;
int     maxcnt, maxsiz;
int     (*bf)();
{
        static short    primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1};
        HDBEAMI bis;
        BEAM    *bp;
        unsigned int4   *bflags;
        int     *bqueue;
        int     bqlen;
        int4    bqtotal;
        int     bc, bci, bqc, myprime;
        register int    i;
                                        /* get clump size */
        if (maxcnt <= 1)
                maxcnt = nbeams(hp);
        maxsiz /= sizeof(RAYVAL);
                                        /* allocate beam queue */
        bqueue = (int *)malloc(maxcnt*sizeof(int));
        bflags = (unsigned int4 *)calloc((nbeams(hp)>>5)+1,
                        sizeof(unsigned int4));
        if (bqueue == NULL | bflags == NULL)
                error(SYSTEM, "out of memory in clumpbeams");
                                        /* mark empty beams as done */
        for (i = nbeams(hp); i > 0; i--)
                if (!bnrays(hp, i))
                        setfl(bflags, i);
                                        /* pick a good prime step size */
        for (i = 0; primes[i]<<5 >= nbeams(hp); i++)
                ;
        while ((myprime = primes[i++]) > 1)
                if (nbeams(hp) % myprime)
                        break;
                                        /* add each input beam and neighbors */
        for (bc = bci = nbeams(hp); bc > 0; bc--,
                        bci += bci>myprime ? -myprime : nbeams(hp)-myprime) {
                if (isset(bflags, bci))
                        continue;
                bqueue[0] = bci;                /* initialize queue */
                bqlen = 1;
                bqtotal = bnrays(hp, i);
                setfl(bflags, bci);
                                                /* run through growing queue */
                for (bqc = 0; bqc < bqlen; bqc++) {
                                                /* add neighbors until full */
                        for (i = firstneigh(hp,bqueue[bqc]); i > 0;
                                        i = nextneigh()) {
                                if (isset(bflags, i))   /* done already? */
                                        continue;
                                bqueue[bqlen++] = i;    /* add it */
                                bqtotal += bnrays(hp, i);
                                setfl(bflags, i);
                                if (bqlen >= maxcnt ||
                                                (maxsiz && bqtotal >= maxsiz))
                                        break;          /* queue full */
                        }
                        if (i > 0)
                                break;
                }
                beamdir = hp->bi;               /* sort queue */
                qsort((char *)bqueue, bqlen, sizeof(*bqueue), bpcmp);
                                                /* transfer each beam */
                for (i = 0; i < bqlen; i++) {
                        bp = hdgetbeam(bis.h=hp, bis.b=bqueue[i]);
                        (*bf)(bp, &bis);
                }
                hdfreebeam(NULL, 0);            /* write & free clump */
        }
        hdsync(NULL, 0);                /* we're done -- clean up */
        free((char *)bqueue);
        free((char *)bflags);
}
Revision:	3.1
Committed:	Mon Nov 9 17:11:04 1998 UTC (25 years, 5 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Log Message:	Initial revision
#	User	Rev	Content
1	gwlarson	3.1	/* Copyright (c) 1998 Silicon Graphics, Inc. */
2
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ SGI";
5			#endif
6
7			/*
8			* Bundle holodeck beams together into clumps.
9			*/
10
11			#include "holo.h"
12
13			#define flgop(p,i,op) ((p)[(i)>>5] op (1L<<((i)&0x1f)))
14			#define isset(p,i) flgop(p,i,&)
15			#define setfl(p,i) flgop(p,i,\|=)
16			#define clrfl(p,i) flgop(p,i,&=~)
17
18			static int bneighlist[9*9-1];
19			static int bneighrem;
20
21			#define nextneigh() (bneighrem<=0 ? 0 : bneighlist[--bneighrem])
22
23			static BEAMI *beamdir;
24
25
26			gcshifti(gc, ia, di, hp) /* shift cell row or column */
27			register GCOORD *gc;
28			int ia, di;
29			register HOLO *hp;
30			{
31			int nw;
32
33			if (di > 0) {
34			if (++gc->i[ia] >= hp->grid[((gc->w>>1)+1+ia)%3]) {
35			nw = ((gc->w&~1) + (ia<<1) + 3) % 6;
36			gc->i[ia] = gc->i[1-ia];
37			gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
38			gc->w = nw;
39			}
40			} else if (di < 0) {
41			if (--gc->i[ia] < 0) {
42			nw = ((gc->w&~1) + (ia<<1) + 2) % 6;
43			gc->i[ia] = gc->i[1-ia];
44			gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
45			gc->w = nw;
46			}
47			}
48			}
49
50
51			mkneighgrid(ng, hp, gc) /* compute neighborhood for grid cell */
52			GCOORD ng[3*3];
53			HOLO *hp;
54			GCOORD *gc;
55			{
56			GCOORD gci0;
57			register int i, j;
58
59			for (i = 3; i--; ) {
60			copystruct(&gci0, gc);
61			gcshifti(&gci0, 0, i-1, hp);
62			for (j = 3; j--; ) {
63			copystruct(ng+(3*i+j), &gci0);
64			gcshifti(ng+(3*i+j), gci0.w==gc->w, j-1, hp);
65			}
66			}
67			}
68
69
70			static int
71			firstneigh(hp, b) /* initialize neighbor list and return first */
72			HOLO *hp;
73			int b;
74			{
75			GCOORD wg0[9], wg1[9], bgc[2];
76			int i, j;
77
78			hdbcoord(bgc, hp, b);
79			mkneighgrid(wg0, hp, bgc);
80			mkneighgrid(wg1, hp, bgc+1);
81			bneighrem = 0;
82			for (i = 9; i--; )
83			for (j = 9; j--; ) {
84			if (i == 4 & j == 4) /* don't copy starting beam */
85			continue;
86			if (wg0[i].w == wg1[j].w)
87			continue;
88			copystruct(bgc, wg0+i);
89			copystruct(bgc+1, wg1+j);
90			bneighlist[bneighrem++] = hdbindex(hp, bgc);
91			#ifdef DEBUG
92			if (bneighlist[bneighrem-1] <= 0)
93			error(CONSISTENCY, "bad beam in firstneigh");
94			#endif
95			}
96			return(nextneigh());
97			}
98
99
100			static int
101			bpcmp(b1p, b2p) /* compare beam positions on disk */
102			int b1p, b2p;
103			{
104			register long pdif = beamdir[b1p].fo - beamdir[b2p].fo;
105
106			if (pdif > 0L) return(1);
107			if (pdif < 0L) return(-1);
108			return(0);
109			}
110
111
112			clumpbeams(hp, maxcnt, maxsiz, bf) /* clump beams from hinp */
113			register HOLO *hp;
114			int maxcnt, maxsiz;
115			int (*bf)();
116			{
117			static short primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1};
118			HDBEAMI bis;
119			BEAM *bp;
120			unsigned int4 *bflags;
121			int *bqueue;
122			int bqlen;
123			int4 bqtotal;
124			int bc, bci, bqc, myprime;
125			register int i;
126			/* get clump size */
127			if (maxcnt <= 1)
128			maxcnt = nbeams(hp);
129			maxsiz /= sizeof(RAYVAL);
130			/* allocate beam queue */
131			bqueue = (int )malloc(maxcntsizeof(int));
132			bflags = (unsigned int4 *)calloc((nbeams(hp)>>5)+1,
133			sizeof(unsigned int4));
134			if (bqueue == NULL \| bflags == NULL)
135			error(SYSTEM, "out of memory in clumpbeams");
136			/* mark empty beams as done */
137			for (i = nbeams(hp); i > 0; i--)
138			if (!bnrays(hp, i))
139			setfl(bflags, i);
140			/* pick a good prime step size */
141			for (i = 0; primes[i]<<5 >= nbeams(hp); i++)
142			;
143			while ((myprime = primes[i++]) > 1)
144			if (nbeams(hp) % myprime)
145			break;
146			/* add each input beam and neighbors */
147			for (bc = bci = nbeams(hp); bc > 0; bc--,
148			bci += bci>myprime ? -myprime : nbeams(hp)-myprime) {
149			if (isset(bflags, bci))
150			continue;
151			bqueue[0] = bci; /* initialize queue */
152			bqlen = 1;
153			bqtotal = bnrays(hp, i);
154			setfl(bflags, bci);
155			/* run through growing queue */
156			for (bqc = 0; bqc < bqlen; bqc++) {
157			/* add neighbors until full */
158			for (i = firstneigh(hp,bqueue[bqc]); i > 0;
159			i = nextneigh()) {
160			if (isset(bflags, i)) /* done already? */
161			continue;
162			bqueue[bqlen++] = i; /* add it */
163			bqtotal += bnrays(hp, i);
164			setfl(bflags, i);
165			if (bqlen >= maxcnt \|\|
166			(maxsiz && bqtotal >= maxsiz))
167			break; /* queue full */
168			}
169			if (i > 0)
170			break;
171			}
172			beamdir = hp->bi; /* sort queue */
173			qsort((char )bqueue, bqlen, sizeof(bqueue), bpcmp);
174			/* transfer each beam */
175			for (i = 0; i < bqlen; i++) {
176			bp = hdgetbeam(bis.h=hp, bis.b=bqueue[i]);
177			(*bf)(bp, &bis);
178			}
179			hdfreebeam(NULL, 0); /* write & free clump */
180			}
181			hdsync(NULL, 0); /* we're done -- clean up */
182			free((char *)bqueue);
183			free((char *)bflags);
184			}