| 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 |
} |
