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 |
|
24 |
gcshifti(gc, ia, di, hp) /* shift cell row or column */ |
25 |
register GCOORD *gc; |
26 |
int ia, di; |
27 |
register HOLO *hp; |
28 |
{ |
29 |
int nw; |
30 |
|
31 |
if (di > 0) { |
32 |
if (++gc->i[ia] >= hp->grid[((gc->w>>1)+1+ia)%3]) { |
33 |
nw = ((gc->w&~1) + (ia<<1) + 3) % 6; |
34 |
gc->i[ia] = gc->i[1-ia]; |
35 |
gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0; |
36 |
gc->w = nw; |
37 |
} |
38 |
} else if (di < 0) { |
39 |
if (--gc->i[ia] < 0) { |
40 |
nw = ((gc->w&~1) + (ia<<1) + 2) % 6; |
41 |
gc->i[ia] = gc->i[1-ia]; |
42 |
gc->i[1-ia] = gc->w&1 ? hp->grid[((nw>>1)+2-ia)%3]-1 : 0; |
43 |
gc->w = nw; |
44 |
} |
45 |
} |
46 |
} |
47 |
|
48 |
|
49 |
mkneighgrid(ng, hp, gc) /* compute neighborhood for grid cell */ |
50 |
GCOORD ng[3*3]; |
51 |
HOLO *hp; |
52 |
GCOORD *gc; |
53 |
{ |
54 |
GCOORD gci0; |
55 |
register int i, j; |
56 |
|
57 |
for (i = 3; i--; ) { |
58 |
copystruct(&gci0, gc); |
59 |
gcshifti(&gci0, 0, i-1, hp); |
60 |
for (j = 3; j--; ) { |
61 |
copystruct(ng+(3*i+j), &gci0); |
62 |
gcshifti(ng+(3*i+j), gci0.w==gc->w, j-1, hp); |
63 |
} |
64 |
} |
65 |
} |
66 |
|
67 |
|
68 |
static int |
69 |
firstneigh(hp, b) /* initialize neighbor list and return first */ |
70 |
HOLO *hp; |
71 |
int b; |
72 |
{ |
73 |
GCOORD wg0[9], wg1[9], bgc[2]; |
74 |
int i, j; |
75 |
|
76 |
hdbcoord(bgc, hp, b); |
77 |
mkneighgrid(wg0, hp, bgc); |
78 |
mkneighgrid(wg1, hp, bgc+1); |
79 |
bneighrem = 0; |
80 |
for (i = 9; i--; ) |
81 |
for (j = 9; j--; ) { |
82 |
if (i == 4 & j == 4) /* don't copy starting beam */ |
83 |
continue; |
84 |
if (wg0[i].w == wg1[j].w) |
85 |
continue; |
86 |
copystruct(bgc, wg0+i); |
87 |
copystruct(bgc+1, wg1+j); |
88 |
bneighlist[bneighrem++] = hdbindex(hp, bgc); |
89 |
#ifdef DEBUG |
90 |
if (bneighlist[bneighrem-1] <= 0) |
91 |
error(CONSISTENCY, "bad beam in firstneigh"); |
92 |
#endif |
93 |
} |
94 |
return(nextneigh()); |
95 |
} |
96 |
|
97 |
|
98 |
clumpbeams(hp, maxcnt, maxsiz, cf) /* clump beams from hinp */ |
99 |
register HOLO *hp; |
100 |
int maxcnt, maxsiz; |
101 |
int (*cf)(); |
102 |
{ |
103 |
static short primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1}; |
104 |
unsigned int4 *bflags; |
105 |
int *bqueue; |
106 |
int bqlen; |
107 |
int4 bqtotal; |
108 |
int bc, bci, bqc, myprime; |
109 |
register int i; |
110 |
/* get clump size */ |
111 |
if (maxcnt <= 1) |
112 |
maxcnt = nbeams(hp); |
113 |
maxsiz /= sizeof(RAYVAL); |
114 |
/* allocate beam queue */ |
115 |
bqueue = (int *)malloc(maxcnt*sizeof(int)); |
116 |
bflags = (unsigned int4 *)calloc((nbeams(hp)>>5)+1, |
117 |
sizeof(unsigned int4)); |
118 |
if (bqueue == NULL | bflags == NULL) |
119 |
error(SYSTEM, "out of memory in clumpbeams"); |
120 |
/* mark empty beams as done */ |
121 |
for (i = nbeams(hp); i > 0; i--) |
122 |
if (!bnrays(hp, i)) |
123 |
setfl(bflags, i); |
124 |
/* pick a good prime step size */ |
125 |
for (i = 0; primes[i]<<5 >= nbeams(hp); i++) |
126 |
; |
127 |
while ((myprime = primes[i++]) > 1) |
128 |
if (nbeams(hp) % myprime) |
129 |
break; |
130 |
/* add each input beam and neighbors */ |
131 |
for (bc = bci = nbeams(hp); bc > 0; bc--, |
132 |
bci += bci>myprime ? -myprime : nbeams(hp)-myprime) { |
133 |
if (isset(bflags, bci)) |
134 |
continue; |
135 |
bqueue[0] = bci; /* initialize queue */ |
136 |
bqlen = 1; |
137 |
bqtotal = bnrays(hp, i); |
138 |
setfl(bflags, bci); |
139 |
/* run through growing queue */ |
140 |
for (bqc = 0; bqc < bqlen; bqc++) { |
141 |
/* add neighbors until full */ |
142 |
for (i = firstneigh(hp,bqueue[bqc]); i > 0; |
143 |
i = nextneigh()) { |
144 |
if (isset(bflags, i)) /* done already? */ |
145 |
continue; |
146 |
bqueue[bqlen++] = i; /* add it */ |
147 |
bqtotal += bnrays(hp, i); |
148 |
setfl(bflags, i); |
149 |
if (bqlen >= maxcnt || |
150 |
(maxsiz && bqtotal >= maxsiz)) |
151 |
break; /* queue full */ |
152 |
} |
153 |
if (i > 0) |
154 |
break; |
155 |
} |
156 |
(*cf)(hp, bqueue, bqlen); /* transfer clump */ |
157 |
} |
158 |
/* all done; clean up */ |
159 |
free((char *)bqueue); |
160 |
free((char *)bflags); |
161 |
} |