src/hd/clumpbeams.c

#ifndef lint
static const char       RCSid[] = "$Id: clumpbeams.c,v 3.7 2003/11/17 02:21:53 greg Exp $";
#endif
/*
 * Bundle holodeck beams together into clumps.
 */

#include "holo.h"

#define flgop(p,i,op)           ((p)[(i)>>5] op (1L<<((i)&0x1f)))
#define issetfl(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 void gcshifti(GCOORD *gc, int ia, int di, HOLO *hp);
static void mkneighgrid(GCOORD  ng[3*3], HOLO   *hp, GCOORD     *gc);
static int firstneigh(HOLO      *hp, int        b);


static void
gcshifti(       /* shift cell row or column */
        register GCOORD *gc,
        int     ia,
        int     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;
                }
        }
}


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

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


static int
firstneigh(             /* 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;
                        *bgc = *(wg0+i);
                        *(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());
}


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