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(maxcnt*sizeof(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 |
} |