src/hd/clumpbeams.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#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])


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


clumpbeams(hp, maxcnt, maxsiz, cf)      /* clump beams from hinp */
register HOLO   *hp;
int     maxcnt, maxsiz;
int     (*cf)();
{
        static short    primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1};
        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;
                }
                (*cf)(hp, bqueue, bqlen);       /* transfer clump */
        }
                                        /* all done; clean up */
        free((void *)bqueue);
        free((void *)bflags);
}
Revision:	3.3
Committed:	Sat Feb 22 02:07:24 2003 UTC (22 years, 8 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad3R5
Changes since 3.2:	+3 -6 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	gwlarson	3.1	#ifndef lint
2	greg	3.3	static const char RCSid[] = "$Id$";
3	gwlarson	3.1	#endif
4			/*
5			* Bundle holodeck beams together into clumps.
6			*/
7
8			#include "holo.h"
9
10			#define flgop(p,i,op) ((p)[(i)>>5] op (1L<<((i)&0x1f)))
11			#define isset(p,i) flgop(p,i,&)
12			#define setfl(p,i) flgop(p,i,\|=)
13			#define clrfl(p,i) flgop(p,i,&=~)
14
15			static int bneighlist[9*9-1];
16			static int bneighrem;
17
18			#define nextneigh() (bneighrem<=0 ? 0 : bneighlist[--bneighrem])
19
20
21			gcshifti(gc, ia, di, hp) /* shift cell row or column */
22			register GCOORD *gc;
23			int ia, di;
24			register HOLO *hp;
25			{
26			int nw;
27
28			if (di > 0) {
29			if (++gc->i[ia] >= hp->grid[((gc->w>>1)+1+ia)%3]) {
30			nw = ((gc->w&~1) + (ia<<1) + 3) % 6;
31			gc->i[ia] = gc->i[1-ia];
32			gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
33			gc->w = nw;
34			}
35			} else if (di < 0) {
36			if (--gc->i[ia] < 0) {
37			nw = ((gc->w&~1) + (ia<<1) + 2) % 6;
38			gc->i[ia] = gc->i[1-ia];
39			gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0;
40			gc->w = nw;
41			}
42			}
43			}
44
45
46			mkneighgrid(ng, hp, gc) /* compute neighborhood for grid cell */
47			GCOORD ng[3*3];
48			HOLO *hp;
49			GCOORD *gc;
50			{
51			GCOORD gci0;
52			register int i, j;
53
54			for (i = 3; i--; ) {
55			copystruct(&gci0, gc);
56			gcshifti(&gci0, 0, i-1, hp);
57			for (j = 3; j--; ) {
58			copystruct(ng+(3*i+j), &gci0);
59			gcshifti(ng+(3*i+j), gci0.w==gc->w, j-1, hp);
60			}
61			}
62			}
63
64
65			static int
66			firstneigh(hp, b) /* initialize neighbor list and return first */
67			HOLO *hp;
68			int b;
69			{
70			GCOORD wg0[9], wg1[9], bgc[2];
71			int i, j;
72
73			hdbcoord(bgc, hp, b);
74			mkneighgrid(wg0, hp, bgc);
75			mkneighgrid(wg1, hp, bgc+1);
76			bneighrem = 0;
77			for (i = 9; i--; )
78			for (j = 9; j--; ) {
79			if (i == 4 & j == 4) /* don't copy starting beam */
80			continue;
81			if (wg0[i].w == wg1[j].w)
82			continue;
83			copystruct(bgc, wg0+i);
84			copystruct(bgc+1, wg1+j);
85			bneighlist[bneighrem++] = hdbindex(hp, bgc);
86			#ifdef DEBUG
87			if (bneighlist[bneighrem-1] <= 0)
88			error(CONSISTENCY, "bad beam in firstneigh");
89			#endif
90			}
91			return(nextneigh());
92			}
93
94
95	gwlarson	3.2	clumpbeams(hp, maxcnt, maxsiz, cf) /* clump beams from hinp */
96	gwlarson	3.1	register HOLO *hp;
97			int maxcnt, maxsiz;
98	gwlarson	3.2	int (*cf)();
99	gwlarson	3.1	{
100			static short primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1};
101			unsigned int4 *bflags;
102			int *bqueue;
103			int bqlen;
104			int4 bqtotal;
105			int bc, bci, bqc, myprime;
106			register int i;
107			/* get clump size */
108			if (maxcnt <= 1)
109			maxcnt = nbeams(hp);
110			maxsiz /= sizeof(RAYVAL);
111			/* allocate beam queue */
112			bqueue = (int )malloc(maxcntsizeof(int));
113			bflags = (unsigned int4 *)calloc((nbeams(hp)>>5)+1,
114			sizeof(unsigned int4));
115			if (bqueue == NULL \| bflags == NULL)
116			error(SYSTEM, "out of memory in clumpbeams");
117			/* mark empty beams as done */
118			for (i = nbeams(hp); i > 0; i--)
119			if (!bnrays(hp, i))
120			setfl(bflags, i);
121			/* pick a good prime step size */
122			for (i = 0; primes[i]<<5 >= nbeams(hp); i++)
123			;
124			while ((myprime = primes[i++]) > 1)
125			if (nbeams(hp) % myprime)
126			break;
127			/* add each input beam and neighbors */
128			for (bc = bci = nbeams(hp); bc > 0; bc--,
129			bci += bci>myprime ? -myprime : nbeams(hp)-myprime) {
130			if (isset(bflags, bci))
131			continue;
132			bqueue[0] = bci; /* initialize queue */
133			bqlen = 1;
134			bqtotal = bnrays(hp, i);
135			setfl(bflags, bci);
136			/* run through growing queue */
137			for (bqc = 0; bqc < bqlen; bqc++) {
138			/* add neighbors until full */
139			for (i = firstneigh(hp,bqueue[bqc]); i > 0;
140			i = nextneigh()) {
141			if (isset(bflags, i)) /* done already? */
142			continue;
143			bqueue[bqlen++] = i; /* add it */
144			bqtotal += bnrays(hp, i);
145			setfl(bflags, i);
146			if (bqlen >= maxcnt \|\|
147			(maxsiz && bqtotal >= maxsiz))
148			break; /* queue full */
149			}
150			if (i > 0)
151			break;
152			}
153	gwlarson	3.2	(cf)(hp, bqueue, bqlen); / transfer clump */
154	gwlarson	3.1	}
155	gwlarson	3.2	/* all done; clean up */
156	greg	3.3	free((void *)bqueue);
157			free((void *)bflags);
158	gwlarson	3.1	}