ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/clumpbeams.c
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.

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id: clumpbeams.c,v 3.7 2003/11/17 02:21:53 greg Exp $";
3 #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 #define issetfl(p,i) flgop(p,i,&)
12 #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 static void gcshifti(GCOORD *gc, int ia, int di, HOLO *hp);
21 static void mkneighgrid(GCOORD ng[3*3], HOLO *hp, GCOORD *gc);
22 static int firstneigh(HOLO *hp, int b);
23
24
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 {
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 static void
55 mkneighgrid( /* compute neighborhood for grid cell */
56 GCOORD ng[3*3],
57 HOLO *hp,
58 GCOORD *gc
59 )
60 {
61 GCOORD gci0;
62 register int i, j;
63
64 for (i = 3; i--; ) {
65 gci0 = *gc;
66 gcshifti(&gci0, 0, i-1, hp);
67 for (j = 3; j--; ) {
68 *(ng+(3*i+j)) = gci0;
69 gcshifti(ng+(3*i+j), gci0.w==gc->w, j-1, hp);
70 }
71 }
72 }
73
74
75 static int
76 firstneigh( /* initialize neighbor list and return first */
77 HOLO *hp,
78 int b
79 )
80 {
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 if ((i == 4) & (j == 4)) /* don't copy starting beam */
91 continue;
92 if (wg0[i].w == wg1[j].w)
93 continue;
94 *bgc = *(wg0+i);
95 *(bgc+1) = *(wg1+j);
96 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 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 {
114 static short primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1};
115 uint32 *bflags;
116 int *bqueue;
117 int bqlen;
118 int32 bqtotal;
119 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(maxcnt*sizeof(int));
127 bflags = (uint32 *)calloc((nbeams(hp)>>5)+1,
128 sizeof(uint32));
129 if ((bqueue == NULL) | (bflags == NULL))
130 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 if (issetfl(bflags, bci))
145 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 if (issetfl(bflags, i)) /* done already? */
156 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 (*cf)(hp, bqueue, bqlen); /* transfer clump */
168 }
169 /* all done; clean up */
170 free((void *)bqueue);
171 free((void *)bflags);
172 }