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